Graph Theory & Combinatorics Seminar
- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- Altgeld 241
- Date
- Nov 1, 2022 1:00 pm
- Speaker
- József Balogh
- Views
- 14
József Balogh (UIUC)
Nearly all k-SAT functions are unate
*************************************************************************
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 Bollobás, Brightwell, and Leader. The proof uses among others the container method and the method of (computer-free) flag algebras.The lecture is summarizing results of a paper of Dingding Dong, Nitya Mani, and Yufei Zhao, and a follow-up paper with additional authors Bernard Lidický and the speaker.
The talk is aimed for a general audience, including computer scientists.