Every monotone graph property has a sharp threshold

Abstract

In their seminal work which initiated random graph theory Erdös and Rényi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This follows from the following theorem. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V Subscript n Baseline left-parenthesis p right-parenthesis equals left-brace 0 comma 1 right-brace Superscript n"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>p</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">V_n(p)= \{0,1\}^n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> denote the Hamming space endowed with the probability measure <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu Subscript p"> <mml:semantics> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\mu _p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> defined by <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu Subscript p Baseline left-parenthesis epsilon 1 comma epsilon 2 comma ellipsis comma epsilon Subscript n Baseline right-parenthesis equals p Superscript k Baseline dot left-parenthesis 1 minus p right-parenthesis Superscript n minus k"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:msup> <mml:mi>p</mml:mi> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>⋅</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>p</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>−</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">\mu _p (\epsilon _1, \epsilon _2, \dots , \epsilon _n)= p^k \cdot (1-p)^{n-k}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k equals epsilon 1 plus epsilon 2 plus midline-horizontal-ellipsis plus epsilon Subscript n"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>+</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">k=\epsilon _1 +\epsilon _2 +\cdots +\epsilon _n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be a monotone subset of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper V Subscript n"> <mml:semantics> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">V_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We say that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is symmetric if there is a transitive permutation group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ</mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula> on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartSet 1 comma 2 comma ellipsis comma n EndSet"> <mml:semantics> <mml:mrow> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>2</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo fence="false" stretchy="false">}</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\{1,2,\dots , n\}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is invariant under <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Gamma"> <mml:semantics> <mml:mi mathvariant="normal">Γ</mml:mi> <mml:annotation encoding="application/x-tex">\Gamma</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. <bold>Theorem.</bold> For every symmetric monotone <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu Subscript p Baseline left-parenthesis upper A right-parenthesis greater-than epsilon"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>A</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>&gt;</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mu _p(A)&gt;\epsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="mu Subscript q Baseline left-parenthesis upper A right-parenthesis greater-than 1 minus epsilon"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>q</mml:mi> </mml:msub> <mml:mo stretchy="false">(</mml:mo> <mml:mi>A</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−</mml:mo> <mml:mi>ϵ</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mu _q(A)&gt;1-\epsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q equals p plus c 1 log left-parenthesis 1 slash 2 epsilon right-parenthesis slash log n"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mi>ϵ</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo>⁡</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">q=p+ c_1 \log (1/2\epsilon )/\log n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. (<inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c 1"> <mml:semantics> <mml:msub> <mml:mi>c</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:annotation encoding="application/x-tex">c_1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is an absolute constant.)