Enumerating k-SAT functions
Dingding Dong, Nitya Mani, Yufei Zhao · Society for Industrial and Applied Mathematics eBooks · 2022
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 ≥ 2, the number of k-SAT functions on n variables is , 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.