TY - JOUR

T1 - The number of Km,m-free graphs

AU - Balogh, József

AU - Samotij, Wojciech

N1 - Funding Information:
* This material is based upon work supported by NSF CAREER Grant DMS-0745185, UIUC Campus Research Board Grant 09072, and OTKA Grant K76099. †Research supported in part by the Trijtzinsky Fellowship and the James D. Hogan Memorial Scholarship Fund.

PY - 2011/3

Y1 - 2011/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80051502286&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80051502286&partnerID=8YFLogxK

U2 - 10.1007/s00493-011-2610-y

DO - 10.1007/s00493-011-2610-y

M3 - Article

AN - SCOPUS:80051502286

VL - 31

SP - 131

EP - 150

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 2

ER -