Dense subgraphs in the H-free process

AbstractThe 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→∞, the final graph of the H-free process contains no subgraphs F on vF≤nd vertices with maximum density maxJ⊆F{eJ/vJ}≥c. This extends and generalizes results of Gerke and Makai for the C3-free process