When does the K4‐free process stop?. Issue 3 (27th July 2012)

• Record Type: Journal Article
• Authors: Warnke, Lutz
• Is Part Of: Random structures & algorithms. Volume 44:Issue 3(2014)
• Page Start: 355
• Page End: 397
• Publication Date: 2012-07-27
• Subjects: H‐free process -- Random graph process -- Ramsey theory; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20444
• Languages: English
• ISSNs: 1042-9832

Abstract

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 → ∞, the maximum degree in G is at most C n 3 / 5 log n 5 . 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 Θ ( n 8 / 5 log n 5 ) edges and is 'nearly regular', i.e., every vertex has degree Θ ( n 3 / 5 log n 5 ) . 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 Ω ( n 2 / 5 ( log n ) 4 / 5 / log log n ), which matches an upper bound obtained by Bohman up to a factor of Θ ( 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.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 355‐397, 2014