The diamond‐free process. Issue 3 (11th October 2013) - Picollelli, Michael E.
Abstract Let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9bmjr" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />K4−</alternatives> denote the diamond graph, formed by removing an edge from the complete graph K4. We consider the following random graph process: starting with n isolated vertices, add edges uniformly at random provided no such edge creates a copy of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9bmk9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />K4−</alternatives>. We show that, with probability tending to 1 as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9bm3k" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>, the final size of the graph produced is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9bm7s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Θ(log⁡n·n3/2)</alternatives>. Our analysis also suggests that the graph produced after i edges are added resembles the uniform random graph, with the additional condition that the edges which do not lie on triangles form a random‐looking subgraph. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 513–551, 2014