The number of Km,m-free graphs

József Balogh, Wojciech Samotij

Research output: Contribution to journalArticlepeer-review


A graph is called H-free if it contains no copy of H. Denote by fn(H) the number of (labeled) H-free graphs on n vertices. Erdo{double acute}s conjectured that fn(H) ≤ 2(1+o(1))ex(n,H). This was first shown to be true for cliques; then, Erdo{double acute}s, Frankl, and Rödl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log2fn(H) is not known. We prove that fn(Km,m) ≤ 2O(n2-1/m) for every m, extending the result of Kleitman and Winston and answering a question of Erdo{double acute}s. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,Km,m) is conjectured to be Θ(n2-1/m). Our method also yields a bound on the number of Km,m-free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K3,3-free graphs of order n have more than 1/20·ex(n,K3,3) edges.

Original languageEnglish (US)
Pages (from-to)131-150
Number of pages20
Issue number2
StatePublished - Mar 2011

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'The number of K<sub>m,m</sub>-free graphs'. Together they form a unique fingerprint.

Cite this