TY - JOUR
T1 - The number of Km,m-free graphs
AU - Balogh, József
AU - Samotij, Wojciech
N1 - * 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
SN - 0209-9683
VL - 31
SP - 131
EP - 150
JO - Combinatorica
JF - Combinatorica
IS - 2
ER -