Every monotone graph property has a sharp threshold 论文

摘要

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>