1. A proof of the Kahn--Kalai conjecture.
- Author
-
Park, Jinyoung and Pham, Huy Tuan
- Subjects
- *
LOGICAL prediction - Abstract
Proving the "expectation-threshold" conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing property \mathcal {F} on a finite set X, \[ p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})), \] where p_c(\mathcal {F}) and q(\mathcal {F}) are the threshold and "expectation threshold" of \mathcal {F}, and \ell (\mathcal {F}) is the maximum of 2 and the maximum size of a minimal member of \mathcal {F}. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF