The diamond-free process

2010/10/25 by Michael E. Picollelli, Picollelli, Michael E. · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1010.5207

25 pages

arxiv created 2010/10/25 · arxiv updated 2010/10/26

Abstract

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 Θ(√(log(n)) ⋅ 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.

Cited by

• The Sunflower-Free Process

Related

• The triangle-free process
• The final size of the C₄-free process
• The K₄-free process
• The random k-matching-free process
• Triangle-free Subgraphs at the Triangle-Free Process