The C_\ell-free process

Abstract

The C_\ell-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of C_\ell is created. For every $\ell \ge 4$ we show that, with high probability as $n\to \infty$, the maximum degree is $O((n\log n{)}^{1/(\ell -1)})$, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the C_\ell-free process typically terminates with $\Theta (n^{\ell /(\ell -1)}(\log n{)}^{1/(\ell -1)})$ edges, which answers a question of Erdős, Suen and Winkler. This is the first result that determines the final number of edges of the more general H-free process for a non-trivial \emph{class} of graphs H. We also verify a conjecture of Osthus and Taraz concerning the average degree, and obtain a new lower bound on the independence number. Our proof combines the differential equation method with a tool that might be of independent interest: we establish a rigorous way to `transfer' certain decreasing properties from the binomial random graph to the H-free process.

34 pages, 5 figures. Minor revisions and additions

Cited by in corpus (6)

• On the method of typical bounded differences
• Almost all Steiner triple systems have perfect matchings
• Large girth approximate Steiner triple systems
• Packing nearly optimal Ramsey R(3,t) graphs
• On the power of random greedy algorithms
• Prominent examples of flip processes