The diamond-free process

Abstract

Let K_4^- denote the diamond graph, formed by removing an edge from the complete graph K_4. 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_4^-. We show that, with probability tending to 1 as $n\to \infty$, the final size of the graph produced is $\Theta (\sqrt{\log (n)}\cdot n^{3/2})$. 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.

25 pages

References in corpus (2)

• The K_4-free process
• Triangle-free Subgraphs at the Triangle-Free Process