The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘)

Abstract

The areas of Ramsey theory and random graphs have been closely linked ever since Erdős’ famous proof in 1947 that the ‘diagonal’ Ramsey numbers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R left-parenthesis k right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>k</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">R(k)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> grow exponentially in <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 the early 1990s, the triangle-free process was introduced as a model which might potentially provide good lower bounds for the ‘off-diagonal’ Ramsey numbers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R left-parenthesis 3 comma k right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>3</mml:mn> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">R(3,k)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In this model, edges of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K Subscript n"> <mml:semantics> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">K_n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are introduced one-by-one at random and added to the graph if they do not create a triangle; the resulting final (random) graph is denoted <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G Subscript n comma white up pointing triangle"> <mml:semantics> <mml:msub> <mml:mi>G</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi mathvariant="normal"> △ </mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">G_{n,\triangle }</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In 2009, Bohman succeeded in following this process for a positive fraction of its duration, and thus obtained a second proof of Kim’s celebrated result that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper R left-parenthesis 3 comma k right-parenthesis equals normal upper Theta left-parenthesis k squared slash log k right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>3</mml:mn> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi mathvariant="normal"> Θ </mml:mi> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> </mml:mstyle> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>k</mml:mi> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:mstyle> </mml:mrow> <mml:annotation encoding="application/x-tex">R(3,k) = \Theta \big ( k^2 / \log k \big )</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In this paper we improve the results of both Bohman and Kim, and follow the triangle-free process all the way to its asymptotic end. In particular, we shall prove that <disp-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="e left-parenthesis upper G Subscript n comma white up pointing triangle Baseline right-parenthesis equals left-parenthesis StartFraction 1 Over 2 StartRoot 2 EndRoot EndFraction plus o left-parenthesis 1 right-parenthesis right-parenthesis n Superscript 3 slash 2 Baseline StartRoot log n EndRoot comma"> <mml:semantics> <mml:mrow> <mml:mi>e</mml:mi> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">(</mml:mo> </mml:mrow> </mml:mstyle> <mml:msub> <mml:mi>G</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi mathvariant="normal"> △ </mml:mi> </mml:mrow> </mml:msub> <mml:mstyle scriptlevel="0"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo maxsize="1.2em" minsize="1.2em">)</mml:mo> </mml:mrow> </mml:mstyle> <mml:mspace width="thinmathspace"/> <mml:mo>=</mml:mo> <mml:mspace width="thinmathspace"/> <mml:mrow> <mml:mo>(</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mrow> <mml:mn>2</mml:mn> <mml:msqrt> <mml:mn>2</mml:mn> </mml:msqrt> </mml:mrow> </mml:mfrac> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>3</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> <

Topics & Concepts