\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Choongbum Lee}
%
%
\medskip
\noindent
%
%
{\bf On the Size of Minimal Unsatisfiable Formulas}
%
%
\vskip 5mm
\noindent
%
%
%
%
An unsatisfiable formula is called minimal if it becomes satisfiable
whenever any of its clauses are removed. We construct minimal
unsatisfiable $k$-SAT formulas with $\Omega(n^k)$ clauses for $k \geq
3$, thereby negatively answering a question of Rosenfeld. This should
be compared to the result of Lov\'asz [Studia Scientiarum
Mathematicarum Hungarica 11, 1974, p113-114] which asserts that a
critically 3-chromatic $k$-uniform hypergraph can have at most
${n\choose k-1}$ edges.



\bye