The number of 3-SAT functions

The number of 3-SAT functions

-
Jeff Kahn, Rutgers University
Fine Hall 224

We are interested in the number, say $G(k,n)$, of k-SAT functions of $n$ variables (a k-SAT function being a Boolean function representable by a k-SAT formula in, say, conjunctive normal form).We show that $G(3,n)$ is asymptotic to $2^{n + {n \choose 3}}$, a strong form of a conjecture of Bollobas, Brightwell and Leader.
(The corresponding result for 2-SAT was conjectured by BB&L, and proved by Peter Allen and (independently but later) by the present authors. As usual, the case $k=2$ doesn't seem to shed much light on larger $k$, while one expects (hopes) that $k=3$ is about as hard to handle as a general fixed $k$.) Joint with Liviu Ilinca