See by year See by month Jump to month

Balogh József: Nearly all k-SAT functions are unate

 Download as iCal file
Friday, 21. July 2023, 10:00 - 11:00
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), Yufei Zhao (MIT).

Back

JEvents v3.1.8 Stable   Copyright © 2006-2013