Abstract
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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 305-318 |
| Number of pages | 14 |
| Journal | Random Structures and Algorithms |
| Volume | 34 |
| Issue number | 3 |
| DOIs | |
| State | Published - May 2009 |
Keywords
- Extremal graphs
- Graph counting
- Structure of H-free graphs
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics