Abstract

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. This resolves a conjecture by Bollobás, Brightwell, and Leader from 2003. (Joint work with József Balogh, Dingding Dong, Bernard Lidický, and Nitya Mani).

Video Recording