The number of 3-SAT functions
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