The Cℓ‐free process. Issue 4 (6th November 2012)

• Record Type: Journal Article
• Authors: Warnke, Lutz
• Is Part Of: Random structures & algorithms. Volume 44:Issue 4(2014)
• Page Start: 490
• Page End: 526
• Publication Date: 2012-11-06
• Subjects: H‐free process -- random graph process -- differential equation method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20468
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The C ℓ ‐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 ℓ is created. For every ℓ ≥ 4 we show that, with high probability as n → ∞, the maximum degree is O ( ( n log n ) 1 / ( ℓ − 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 ℓ ‐free process typically terminates with Θ ( n ℓ / ( ℓ − 1 ) ( log n ) 1 / ( ℓ − 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 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. © 2014 Wiley Periodicals, Inc. Random Struct. Alg. 44, 490–526, 2014