When does the K_4-free process stop?

Abstract

The K_4-free process starts with the empty graph on n vertices and at each step adds a new edge chosen uniformly at random from all remaining edges that do not complete a copy of K_4. Let G be the random maximal K_4-free graph obtained at the end of the process. We show that for some positive constant C, with high probability as $n\to \infty$, the maximum degree in G is at most $C{n}^{3/5}\sqrt[5]{\log n}$. This resolves a conjecture of Bohman and Keevash for the K_4-free process and improves on previous bounds obtained by Bollobás and Riordan and by Osthus and Taraz. Combined with results of Bohman and Keevash this shows that with high probability G has $\Theta (n^{8/5}\sqrt[5]{\log n})$ edges and is `nearly regular', i.e., every vertex has degree $\Theta (n^{3/5}\sqrt[5]{\log n})$. This answers a question of Erdős, Suen and Winkler for the K_4-free process. We furthermore deduce an additional structural property: we show that whp the independence number of G is at least $\Omega (n^{2/5}(\log n{)}^{4/5}/\log \log n)$, which matches an upper bound obtained by Bohman up to a factor of $\Theta (\log \log n)$. Our analysis of the K_4-free process also yields a new result in Ramsey theory: for a special case of a well-studied function introduced by Erdős and Rogers we slightly improve the best known upper bound.

39 pages, 3 figures. Minor edits. To appear in Random Structures and Algorithms

Cited by in corpus (8)

• On the method of typical bounded differences
• Upper tails for arithmetic progressions in random subsets
• Large girth approximate Steiner triple systems
• Packing nearly optimal Ramsey R(3,t) graphs
• On the missing log in upper tail estimates
• The jump of the clique chromatic number of random graphs
• On the power of random greedy algorithms
• The $Q_2$-free process in the hypercube