The early evolution of the H-free process

Abstract

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\to \infty$, the minimum degree in G is at least $c{n}^{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 $K_{r,r}$ with $r\ge 5$. When H is a complete graph $K_s$ with $s\ge 5$ we show that for some C>0, with high probability the independence number of G is at most $C{n}^{2/(s+1)}(\log n{)}^{1-1/(e_H-1)}$. This gives new lower bounds for Ramsey numbers R(s,t) for fixed $s\ge 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.

36 pages

References in corpus (2)

• A note on regular Ramsey graphs
• A central limit theorem via differential equations

Cited by in corpus (19)

• On the method of typical bounded differences
• When does the K_4-free process stop?
• Large girth approximate Steiner triple systems
• Separation choosability and dense bipartite induced subgraphs
• On n-dependence
• The C_\ell-free process
• Packing nearly optimal Ramsey R(3,t) graphs
• The Bohman-Frieze Process Near Criticality
• Dense subgraphs in the H-free process
• $\chi$-bounds, operations and chords
• Multicolor Ramsey Numbers for Complete Bipartite Versus Complete Graphs
• Hypergraph Ramsey numbers: tight cycles versus cliques
• Counting extensions revisited
• On the power of random greedy algorithms
• Improved bounds for the Ramsey number of tight cycles versus cliques
• Simple evolving random graphs
• Bounds on Ramsey Games via Alterations
• From flip processes to dynamical systems on graphons
• Prominent examples of flip processes