The typical structure of graphs without given excluded subgraphs

Let L be a finite family of graphs. We describe the typical structure of L-free graphs, improving our earlier results (Balogh et al., J Combinat Theory Ser B 91 (2004), 1-24) on the Erdo{double acute}s- Frankl-Rödl theorem (Erdo{double acute}s et al., Graphs Combinat 2 (1986), 113-121), by proving our earlier conjecture that, for p = p(L) = min L∈L X(L) - 1, the structure of almost all L-free graphs is very similar to that of a random subgraph of the Turán graph T n,p. The similarity is measured in terms of graph theoretical parameters of L. © 2008 Wiley Periodicals, Inc