The number of graphs without forbidden subgraphs

József Balogh, Béla Bollobás, Miklós Simonovits

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1-24
Number of pages24
JournalJournal of Combinatorial Theory. Series B
Volume91
Issue number1
DOIs
StatePublished - May 2004
Externally publishedYes

Keywords

  • Erdos-Kleitman-Rothschild theory
  • Extremal graphs
  • Speed function

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The number of graphs without forbidden subgraphs'. Together they form a unique fingerprint.

Cite this