The Cℓ‐free process. Issue 4 (6th November 2012) - Warnke, Lutz
Abstract The <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fmnj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Cℓ</alternatives>‐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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fmm1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Cℓ</alternatives> is created. For every <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fmsm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ℓ≥4</alternatives> we show that, with high probability as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fmr3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>, the maximum degree is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fmqk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O((nlogn)1/(ℓ−1))</alternatives>, which confirms a conjecture of Bohman and Keevash and improves on bounds of Osthus and Taraz. Combined with previous results this implies that the <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fmp2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Cℓ</alternatives>‐free process typically terminates with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh6c4fmvn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(nℓ/(ℓ−1)(logn)1/(ℓ−1))</alternatives> 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