A proof of the Kahn–Kalai conjecture

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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> on a finite set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript c Baseline left-parenthesis script upper F right-parenthesis equals upper O left-parenthesis q left-parenthesis script upper F right-parenthesis log script l left-parenthesis script upper F right-parenthesis right-parenthesis comma"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>c</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>q</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi> ℓ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mo>,</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})),</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p Subscript c Baseline left-parenthesis script upper F right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>p</mml:mi> <mml:mi>c</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">p_c(\mathcal {F})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q left-parenthesis script upper F right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">q(\mathcal {F})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are the threshold and “expectation threshold” of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l left-parenthesis script upper F right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi> ℓ </mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\ell (\mathcal {F})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the maximum of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2"> <mml:semantics> <mml:mn>2</mml:mn> <mml:annotation encoding="application/x-tex">2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and the maximum size of a minimal member of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper F"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">F</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {F}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> .

Topics & Concepts