Premium
The typical structure of graphs without given excluded subgraphs
Author(s) -
Balogh József,
Bollobás Béla,
Simonovits Miklós
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20242
Subject(s) - combinatorics , conjecture , mathematics , random graph , graph , discrete mathematics , struct , computer science , programming language
Let $ {\cal L}$ be a finite family of graphs. We describe the typical structure of $ {\cal L}$ ‐free graphs, improving our earlier results (Balogh et al., J Combinat Theory Ser B 91 (2004), 1–24) on the Erdős–Frankl–Rödl theorem (Erdős et al., Graphs Combinat 2 (1986), 113–121), by proving our earlier conjecture that, for $ p = p ({\cal L}) = {\rm min}_L \in {\cal L} \chi (L) - 1 $ , the structure of almost all $ {\cal 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 $ {\cal L}$ .© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009