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