Dense subgraphs in the H-free process

Abstract

The H-free process starts with the empty graph on n vertices and adds edges chosen uniformly at random, one at a time, subject to the condition that no copy of H is created, where H is some fixed graph. When H is strictly 2-balanced, we show that for some c,d>0, with high probability as $n\to \infty$, the final graph of the H-free process contains no subgraphs F on $v_F\le n^d$ vertices with maximum density ${\max }_{J\subseteq F}\{e_J/v_J\}\ge c$. This extends and generalizes results of Gerke and Makai for the C_3-free process.

7 pages, revised version

References in corpus (6)

• The early evolution of the H-free process
• When does the K_4-free process stop?
• The K_4-free process
• Triangle-free Subgraphs at the Triangle-Free Process
• The final size of the C_4-free process
• The diamond-free process

Cited by in corpus (6)

• When does the K_4-free process stop?
• Large girth approximate Steiner triple systems
• The C_\ell-free process
• The final size of the C_4-free process
• The diamond-free process
• The $Q_2$-free process in the hypercube