The triangle-free process and the Ramsey number $R(3,k)$

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,△}$. 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 (k^2/\log k)$. 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 $$e\left(G_{n,△}\right)=\left(\frac{1}{2\sqrt{2}}+o(1)\right)n^{3/2}\sqrt{\log n},$$ with high probability as $n\to \infty$. We also obtain several pseudorandom properties of $G_{n,△}$, and use them to bound its independence number, which gives as an immediate corollary $$R(3,k)\ge \left(\frac{1}{4}-o(1)\right)\frac{k^2}{\log k}.$$ 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.

118 pages + 36-page Appendix, 6 figures

Cited by in corpus (8)

• Simple evolving random graphs
• On the power of random greedy algorithms
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• The $Q_2$-free process in the hypercube
• Prominent examples of flip processes
• Counting independent sets in structured graphs
• The early evolution of the random graph process in planar graphs and related classes
• Paley-like graphs for the Ramsey number $r(C_4,K_t)$