When does the K4‐free process stop?. Issue 3 (27th July 2012) - Warnke, Lutz
Abstract 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1f1d" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>, the maximum degree in G is at most <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1ff1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Cn3/5logn5</alternatives>. This resolves a conjecture of Bohman and Keevash for the K4‐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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1fdg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(n8/5logn5)</alternatives> edges and is 'nearly regular', i.e., every vertex has degree <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1fms" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(n3/5logn5)</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1fh4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Ω(n2/5(logn)4/5/loglogn)</alternatives>, which matches an upper bound obtained by Bohman up to a factor of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg4x9s1fqf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(loglogn)</alternatives>. 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