The number of 3SAT functions
The number of 3SAT functions

Jeff Kahn, Rutgers University
Fine Hall 224
We are interested in the number, say $G(k,n)$, of kSAT functions of $n$ variables (a kSAT function being a Boolean function representable by a kSAT 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 2SAT 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