Threshold functions for Ramsey properties

Abstract

Probabilistic methods have been used to approach many problems of Ramsey theory. In this paper we study Ramsey type questions from the point of view of random structures. Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K left-parenthesis n comma upper N right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">K(n,N)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be the random graph chosen uniformly from among all graphs with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N"> <mml:semantics> <mml:mi>N</mml:mi> <mml:annotation encoding="application/x-tex">N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edges. For a fixed graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and an integer <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula> we address the question what is the minimum <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals upper N left-parenthesis upper G comma r comma n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>,</mml:mo> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">N = N(G,r,n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that the random graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K left-parenthesis n comma upper N right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">K(n,N)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contains, almost surely, a monochromatic copy of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-coloring of its edges ( <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K left-parenthesis n comma upper N right-parenthesis right-arrow left-parenthesis upper G right-parenthesis Subscript r"> <mml:semantics> <mml:mrow> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>r</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">K(n,N) \to {(G)_r}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, in short). We find a graph parameter <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="gamma equals gamma left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>γ<!-- γ --></mml:mi> <mml:mo>=</mml:mo> <mml:mi>γ<!-- γ --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\gamma = \gamma (G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> yielding <disp-formula content-type="math/mathml"> \[ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="limit Underscript n right-arrow normal infinity Endscripts upper P r o b left-parenthesis upper K left-parenthesis n comma upper N right-parenthesis right-arrow left-parenthesis upper G right-parenthesis Subscript r Baseline right-parenthesis equals StartLayout Enlarged left-brace 1st Row 0 if upper N greater-than c n Superscript y Baseline comma 2nd Row 1 if upper N greater-than upper C n Superscript y Baseline comma EndLayout"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mo form="prefix">lim</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mi mathvariant="normal">∞<!-- ∞ --></mml:mi> </mml:mrow> </mml:munder> <mml:mi>Prob</mml:mi> <mml:mo>⁡<!-- ⁡ --></mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>r</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtable rowspacing="4pt" columnspacing="1em"> <mml:mtr> <mml:mtd> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>0</mml:mn> <mml:mspace width="1em" /> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>if </mml:mtext> </mml:mrow> <mml:mspace width="thickmathspace" /> <mml:mi>N</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>c</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>y</mml:mi> </mml:msup> </mml:mrow> <mml:mo>,</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> <mml:mtr> <mml:mtd> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mspace width="1em" /> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mtext>if</mml:mtext> </mml:mrow> <mml:mspace width="thickmathspace" /> <mml:mi>N</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>C</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mi>y</mml:mi> </mml:msup> </mml:mrow> <mml:mo>,</mml:mo> </mml:mrow> </mml:mtd> </mml:mtr> </mml:mtable> </mml:mrow> <mml:mo fence="true" stretchy="true" symmetric="true" /> </mml:mrow> <mml:mspace width="1em" /> </mml:mrow> <mml:annotation encoding="application/x-tex">\lim \limits _{n \to \infty } \operatorname {Prob}(K(n,N) \to {(G)_r}) = \left \{ {\begin {array}{*{20}{c}} {0\quad {\text {if }}\;N &gt; c{n^y},} \\ {1\quad {\text {if}}\;N &gt; C{n^y},} \\ \end {array} } \right .\quad</mml:annotation> </mml:semantics> </mml:math> \] </disp-formula> for some <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c"> <mml:semantics> <mml:mi>c</mml:mi> <mml:annotation encoding="application/x-tex">c</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="upper C greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">C &gt; 0</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We use this to derive a number of consequences that deal with the existence of sparse Ramsey graphs. For example we show that for all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r greater-than-or-equal-to 2"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>≥<!-- ≥ --></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">r \geq 2</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="k greater-than-or-equal-to 3"> <mml:semantics> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥<!-- ≥ --></mml:mo> <mml:mn>3</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">k \geq 3</mml:annotation> </mml:semantics> </mml:math> </inline-formula> there exists <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C greater-than 0"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">C &gt; 0</mml:annotation> </mml:semantics> </mml:math> </inline-formula> such that almost all graphs <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H"> <mml:semantics> <mml:mi>H</mml:mi> <mml:annotation encoding="application/x-tex">H</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper C n Superscript StartFraction 2 k Over k plus 1 EndFraction"> <mml:semantics> <mml:mrow> <mml:mi>C</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mfrac> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">C{n^{\frac {{2k}}{{k + 1}}}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> edges which are <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K Subscript k plus 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{K_{k + 1}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-free, satisfy <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H right-arrow left-parenthesis upper K Subscript k Baseline right-parenthesis Subscript r"> <mml:semantics> <mml:mrow> <mml:mi>H</mml:mi> <mml:mo stretchy="false">→<!-- → --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:mrow> <mml:msub> <mml:mo stretchy="false">)</mml:mo> <mml:mi>r</mml:mi> </mml:msub> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">H \to {({K_k})_r}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We also apply our method to the problem of finding the smallest <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals upper N left-parenthesis k comma r comma n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mi>N</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>,</mml:mo> <mml:mi>r</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">N = N(k,r,n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> guaranteeing that almost all sequences <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1 less-than-or-equal-to a 1 greater-than a 2 greater-than midline-horizontal-ellipsis greater-than a Subscript upper N Baseline less-than-or-equal-to n"> <mml:semantics> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mo>⋯<!-- ⋯ --></mml:mo> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>N</mml:mi> </mml:msub> </mml:mrow> <mml:mo>≤<!-- ≤ --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">1 \leq {a_1} &gt; {a_2} &gt; \cdots &gt; {a_N} \leq n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contain an arithmetic progression of length <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-coloring, and show that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper N equals normal upper Theta left-parenthesis n Superscript StartFraction k minus 2 Over k minus 1 EndFraction Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>N</mml:mi> <mml:mo>=</mml:mo> <mml:mi mathvariant="normal">Θ<!-- Θ --></mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mfrac> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>k</mml:mi> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">N = \Theta ({n^{\frac {{k - 2}}{{k - 1}}}})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the threshold.

Locations

• Journal of the American Mathematical Society - View - PDF