Nearly all k-SAT functions are unate

09/11/2022
by   József Balogh, et al.
0

We prove that 1-o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n →∞. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003. This paper is the second half of a two-part work solving the problem. The first part, by Dong, Mani, and Zhao, reduces the conjecture to a Turán problem on partially directed hypergraphs. In this paper we solve this Turán problem.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset