Enumerating k-SAT functions

MaRDI QIDQ6373242zbMATH OpenFDO

Authors Nitya Mani, Yufei Zhao

Publication date 19 July 2021

Has companion code repository https://github.com/thingarfield/density-k-pdg

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Hypergraphs (05C65)

Abstract: How many $k$-SAT functions on $n$ boolean variables are there? What does a typical such function look like? Bollob'as, Brightwell, and Leader conjectured that, for each fixed $kge2$, 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'an density problem for partially directed hypergraphs. Our proof uses the hypergraph container method. Furthermore, we confirm the Bollob'as--Brightwell--Leader conjecture for $k=4$ by solving the corresponding Tur'an density problem. Our solution applies a recent result of F"uredi 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.

This page was built for publication: Enumerating k-SAT functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6373242)