When does the K4-free process stop?
The K4-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 K4. Let G be the random maximal K4-free graph obtained at the end of the process. We show that for some positive constant C, with high probability as , the maximum degree in G is at most . This resolves a conjecture of Bohman and Keevash for the K4-free process and improves on previous bounds obtained by Bollobs and Riordan and by Osthus and Taraz. Combined with results of Bohman and Keevash this shows that with high probability G has edges and is nearly regular, i.e., every vertex has degree . This answers a question of Erd?s, Suen and Winkler for the K4-free process. We furthermore deduce an additional structural property: we show that whp the independence number of G is at least , which matches an upper bound obtained by Bohman up to a factor of . Our analysis of the K4-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.Copyright  2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 355-397, 2014
ramsey theory h-free process random graph process