The early evolution of the H-free process

By Tom Bohman, Peter Keevash. 2009

208 citations recorded by the source corpus.

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least $cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}$. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs Kr,r with r≥5. When H is a complete graph Ks with s≥5 we show that for some C>0, with high probability the independence number of G is at most $Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}$. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.

Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/76528d368e36e43fdcac977e042dfa663f2ec158

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Discrete Mathematics and Combinatorics

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

The asymptotics of r(4,t) (2023, methodology): “The current best lower bounds for r (4 , t ) come from the K 4 -free process in random graphs, studied by Bohman and Keevash [8], improving earlier bounds of Spencer [52].”
Spectral graph theory (2019, methodology): “r(s, t) ≤ cs ts−1 (log t)s−2 The best lower bound so far is shown by Bohman and Keevash [5] (2010) using a natural random Ks-free process: r(s, t) ≥ cs t(s+1)/2 (log t)(s+1)/2−1/(s−2) A recent work by Mubayi and Vertraete [21] (2019) offers a new way to improve this lower bound.”
The triangle-free process and R(3,k) (2013, methodology): “h paper of Bohman [10], who followed the triangle-free process for a constant proportion of its lifespan, and hence proved that e G n; 4 = n 3 = 2 p log n : (2) Shortly afterwards, Bohman and Keevash [13] extended and generalized the method of [10] to the setting of the H -free process, where the tr”
Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, background): “Recently, Bohman and Keevash [18] obtained a small improvement to Ω(n2−2/(r+1)(log n)1/(r 2−1)) from the analysis of the H-free process.”
Random triangle removal (2012, background): “n3/2+o(1), and the correct order of n3/2 √ log n, along with its ramifications on the Ramsey number R(3, t), was recovered in [3] (see also [5] for generalizations).”
A semi-algebraic version of Zarankiewicz's problem (2014, background): “A recent result of Bohman and Keevash [8] on random graph processes gives the best known lower bound for k ≥ 5 and m = n of the form Ω n − 2 /k (log k ) / ( k 2 − 1) .”