The diamond-free process

الأصل · EN

Let K₄- denote the diamond graph, formed by removing an edge from the complete graph K₄. 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 K₄-. We show that, with probability tending to 1 as n → ∞, the final size of the graph produced is Θ(√(n) · n³/²). Our analysis also suggests that the graph produced after i edges are added resembles the random graph, with the additional condition that the edges which do not lie on triangles form a random-looking subgraph.