The diamond‐free process. Issue 3 (11th October 2013) - Picollelli, Michael E.
Abstract Let K4− 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 K4−. We show that, with probability tending to 1 as n→∞, the final size of the graph produced is Θ(log⁡n·n3/2). 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