The areas of Ramsey theory and random graphs have been closely linked ever since Erdos'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 the authors improve the results of both Bohman and Kim and follow the triangle-free process all the way to its asymptotic end.
|
|
|
1 | (6) |
|
1.1 Random graph processes |
|
|
2 | (1) |
|
1.2 The triangle-free process |
|
|
2 | (5) |
|
Chapter 2 An overview of the proof |
|
|
7 | (8) |
|
Chapter 3 Martingale bounds: The line of peril and the line of death |
|
|
15 | (12) |
|
3.1 The line of peril and the line of death |
|
|
16 | (2) |
|
|
|
18 | (3) |
|
3.3 The events X(m), Y(m), Z(m) and Q(m) |
|
|
21 | (2) |
|
|
|
23 | (4) |
|
Chapter 4 Tracking everything else |
|
|
27 | (40) |
|
|
|
30 | (5) |
|
|
|
35 | (5) |
|
4.3 Creating and destroying copies of F |
|
|
40 | (5) |
|
4.4 Balanced non-tracking graph structures |
|
|
45 | (11) |
|
4.5 Bounding the maximum change in Nφ(F) |
|
|
56 | (4) |
|
4.6 The land before time t = ω |
|
|
60 | (3) |
|
|
|
63 | (4) |
|
Chapter 5 Tracking Ye, and mixing in the Y-graph |
|
|
67 | (22) |
|
5.1 Mixing inside open neighbourhoods |
|
|
69 | (4) |
|
5.2 Mixing in the whole Y-graph |
|
|
73 | (2) |
|
5.3 Creating and destroying σ-walks |
|
|
75 | (2) |
|
|
|
77 | (9) |
|
5.5 The Lines of Peril and Death |
|
|
86 | (3) |
|
Chapter 6 Whirlpools and Lyapunov functions |
|
|
89 | (6) |
|
|
|
89 | (2) |
|
|
|
91 | (3) |
|
6.3 The proof of Theorems 2.1, 2.4, 2.5, 2.7 and 2.11 |
|
|
94 | (1) |
|
Chapter 7 Independent sets and maximum degrees in Gn,Δ |
|
|
95 | (26) |
|
7.1 A sketch of the proof |
|
|
95 | (1) |
|
7.2 Partitioning the bad events |
|
|
96 | (2) |
|
7.3 The events A(S, δ) and A'(S, δ) |
|
|
98 | (2) |
|
7.4 The events B(S, δ) ∩ D(S, δ)c and B'(S, δ) ∩ D(S, δ)c |
|
|
100 | (5) |
|
7.5 The events C(S, δ) and C'(S, δ) |
|
|
105 | (8) |
|
|
|
113 | (6) |
|
7.7 The proof of Propositions 7.1 and 7.2 |
|
|
119 | (2) |
| Acknowledgements |
|
121 | (2) |
| Bibliography |
|
123 | |
Gonzalo Fiz Pontiveros, Instituto Nacional de Matematica Pura e Aplicada (IMPA), Rio de Janeiro, Brasil
Simon Griffiths, Instituto Nacional de Matematica Pura e Aplicada (IMPA), Rio de Janeiro, Brasil
Robert Morris, Instituto Nacional de Matematica Pura e Aplicada (IMPA), Rio de Janeiro, Brasil
Lisainfo e-raamatute kohta