TY - JOUR
T1 - The number of graphs without forbidden subgraphs
AU - Balogh, József
AU - Bollobás, Béla
AU - Simonovits, Miklós
N1 - Funding Information:
E-mail addresses: [email protected] (J. Balogh), [email protected] (B. Bollobás), [email protected] (M. Simonovits). 1Partially supported by NSF Grant DMS-9971788, ITR Grant 0225610, and DARPA Grant F33615-01-C-1900. 2Partially supported by OTKA Grants T026069, T038210.
PY - 2004/5
Y1 - 2004/5
N2 - Given a family ℒ of graphs, set p =p(ℒ) = minℒ∈ℒ χ(L) - 1 and, for n≥ 1, denote by P(n,ℒ) the set of graphs with vertex set [n] containing no member of ℒ as a subgraph,and write ex(n,ℒ) for the maximal size of a member of P(n, ℒ). Extending a result of Erdos, Frankl and Rödl (Graphs Combin. 2 (1986) 113), we prove that A figure is presented. For some constant γ = γ(ℒ) > 0, and characterize γ in terms of some related extremal graph problems. In fact, if ex(n,ℒ) = O(n2-δ), then any γ<δ will do. Our proof is based on Szemerédi's Regularity Lemma and the stability theorem of Erdos and Simonovits. The bound above is essentially best possible.
AB - Given a family ℒ of graphs, set p =p(ℒ) = minℒ∈ℒ χ(L) - 1 and, for n≥ 1, denote by P(n,ℒ) the set of graphs with vertex set [n] containing no member of ℒ as a subgraph,and write ex(n,ℒ) for the maximal size of a member of P(n, ℒ). Extending a result of Erdos, Frankl and Rödl (Graphs Combin. 2 (1986) 113), we prove that A figure is presented. For some constant γ = γ(ℒ) > 0, and characterize γ in terms of some related extremal graph problems. In fact, if ex(n,ℒ) = O(n2-δ), then any γ<δ will do. Our proof is based on Szemerédi's Regularity Lemma and the stability theorem of Erdos and Simonovits. The bound above is essentially best possible.
KW - Erdos-Kleitman-Rothschild theory
KW - Extremal graphs
KW - Speed function
UR - http://www.scopus.com/inward/record.url?scp=2342449349&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=2342449349&partnerID=8YFLogxK
U2 - 10.1016/j.jctb.2003.08.001
DO - 10.1016/j.jctb.2003.08.001
M3 - Article
AN - SCOPUS:2342449349
SN - 0095-8956
VL - 91
SP - 1
EP - 24
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 1
ER -