AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

The Triangle-Free Process and the Ramsey Number $R(3,k)$

About this Title

Gonzalo Fiz Pontiveros, IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, 22460-320, Brasil, Simon Griffiths, IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, 22460-320, Brasil and Robert Morris, IMPA, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, 22460-320, Brasil

Publication: Memoirs of the American Mathematical Society
Publication Year: 2020; Volume 263, Number 1274
ISBNs: 978-1-4704-4071-8 (print); 978-1-4704-5656-6 (online)
DOI: https://doi.org/10.1090/memo/1274
Published electronically: March 10, 2020
MSC: Primary 05D10, 05D40, 60C05

View full volume PDF

Table of Contents

Chapters

• 1. Introduction
• 2. An overview of the proof
• 3. Martingale bounds: The line of peril and the line of death
• 4. Tracking everything else
• 5. Tracking $Y_e$, and mixing in the $Y$-graph
• 6. Whirlpools and Lyapunov functions
• 7. Independent sets and maximum degrees in $G_{n,\triangle }$
• Acknowledgements

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 $R(k)$ grow exponentially in $k$. 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 $R(3,k)$. In this model, edges of $K_n$ 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 $G_{n,\triangle }$. 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 $R(3,k) = \Theta \big ( k^2 / \log k \big )$.

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 \begin{equation*} e\big ( G_{n,\triangle } \big ) \,=\, \left ( \frac {1}{2\sqrt {2}} + o(1) \right ) n^{3/2} \sqrt {\log n }, \end{equation*} with high probability as $n \to \infty$. We also obtain several pseudorandom properties of $G_{n,\triangle }$, and use them to bound its independence number, which gives as an immediate corollary \begin{equation*} R(3,k) \, \geqslant \, \left ( \frac {1}{4} - o(1) \right ) \frac {k^2}{\log k}. \end{equation*} This significantly improves Kim’s lower bound, and is within a factor of $4 + o(1)$ of the best known upper bound, proved by Shearer over 25 years ago.