Enumerating k-SAT functions

Abstract

How many $k$-SAT functions on $n$ boolean variables are there? What does a typical such function look like? Bollobás, Brightwell, and Leader conjectured that, for each fixed $k\ge 2$, the number of $k$-SAT functions on $n$ variables is $(1+o(1))2^{\left(\genfrac{}{}{0ex}{}{n}{k}\right)+n}$, or equivalently: a $1-o(1)$ fraction of all $k$-SAT functions are unate, i.e., monotone after negating some variables. They proved a weaker version of the conjecture for $k=2$. The conjecture was confirmed for $k=2$ by Allen and $k=3$ by Ilinca and Kahn. We show that the problem of enumerating $k$-SAT functions is equivalent to a Turán density problem for partially directed hypergraphs. Our proof uses the hypergraph container method. Furthermore, we confirm the Bollobás--Brightwell--Leader conjecture for $k=4$ by solving the corresponding Turán density problem. Our solution applies a recent result of Füredi and Maleki on the minimum triangular edge density in a graph of given edge density. In an appendix (by Nitya Mani and Edward Yu), we further confirm the $k=5$ case of the conjecture via a brute force computer search.

50 pages incl. 3 page appendix. Conference version appeared in SODA '22

References in corpus (1)

• On the Number of 2-SAT Functions