Softcover ISBN:  9781470440718 
Product Code:  MEMO/263/1274 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $51.00 
eBook ISBN:  9781470456566 
Product Code:  MEMO/263/1274.E 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $51.00 
Softcover ISBN:  9781470440718 
eBook: ISBN:  9781470456566 
Product Code:  MEMO/263/1274.B 
List Price:  $170.00 $127.50 
MAA Member Price:  $153.00 $114.75 
AMS Member Price:  $102.00 $76.50 
Softcover ISBN:  9781470440718 
Product Code:  MEMO/263/1274 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $51.00 
eBook ISBN:  9781470456566 
Product Code:  MEMO/263/1274.E 
List Price:  $85.00 
MAA Member Price:  $76.50 
AMS Member Price:  $51.00 
Softcover ISBN:  9781470440718 
eBook ISBN:  9781470456566 
Product Code:  MEMO/263/1274.B 
List Price:  $170.00 $127.50 
MAA Member Price:  $153.00 $114.75 
AMS Member Price:  $102.00 $76.50 

Book DetailsMemoirs of the American Mathematical SocietyVolume: 263; 2020; 125 ppMSC: Primary 05; 60
The areas of Ramsey theory and random graphs have been closely linked ever since Erdős's famous proof in 1947 that the “diagonal” Ramsey numbers \(R(k)\) grow exponentially in \(k\). In the early 1990s, the trianglefree process was introduced as a model which might potentially provide good lower bounds for the “offdiagonal” Ramsey numbers \(R(3,k)\). In this model, edges of \(K_n\) are introduced onebyone 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 the authors improve the results of both Bohman and Kim and follow the trianglefree process all the way to its asymptotic end.

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


Additional Material

RequestsReview Copy – for publishers of book reviewsPermission – for use of book, eBook, or Journal contentAccessibility – to request an alternate format of an AMS title
 Book Details
 Table of Contents
 Additional Material
 Requests
The areas of Ramsey theory and random graphs have been closely linked ever since Erdős's famous proof in 1947 that the “diagonal” Ramsey numbers \(R(k)\) grow exponentially in \(k\). In the early 1990s, the trianglefree process was introduced as a model which might potentially provide good lower bounds for the “offdiagonal” Ramsey numbers \(R(3,k)\). In this model, edges of \(K_n\) are introduced onebyone 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 the authors improve the results of both Bohman and Kim and follow the trianglefree process all the way to its asymptotic end.

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