2023. 07. 21. 10:00 - 2023. 07. 21. 11:00
Szeged, Bolyai Intézet, Aradi vértanúk tere 1, I. emelet, Riesz terem
-
-
-
-
Esemény típusa: szeminárium
Szervezés: Külsős
-
Szegedi Szemináriumok

Leírás

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