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).