View abstract

Session I.3 - Graph Theory and Combinatorics

Tuesday, June 13, 14:00 ~ 15:00

Nearly all k-SAT functions are unate

Jozsef Balogh

University of Illinois, United States   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

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 and as n tends to infinity. This resolves a conjecture by Bollobas, Brightwell, and Leader. The proof uses among others the container method and the method of (computer-free) flag algebras.

Joint work with Dingding Dong (Harvard), Bernard Lidicky (Iowa State University), Nitya Mani (MIT) and Yufei Zhao (MIT).

View abstract PDF