TY - JOUR

T1 - The number of Ks,t-free graphs

AU - Balogh, József

AU - Samotij, Wojciech

N1 - Funding Information:
The first author was supported by NSF CAREER Grant DMS-0745185 and DMS-0600303, UIUC Campus Research Board Grants 09072 and 08086, and OTKA Grant K76099. The second author was supported in part by Trijtzinsky Fellowship and James D. Hogan Memorial Scholarship Fund.

PY - 2011/4

Y1 - 2011/4

N2 - Denote by fn (H) the number of (labeled) H-free graphs on a fixed vertex set of size n. Erdos conjectured that, whenever H contains a cycle, fn(H) = 2(1+0(1))ex(n,h), yet it is still open for every bipartite graph, and even the order of magnitude of log2 f n (H) was known only for C4, C6, and K 3,3. We show that, for all s and t satisfying 2≤s≤t, f n(Ks,t=2O(n2-1/s), which is asymptotically sharp for those values of s and t for which the order of magnitude of the Turán number ex(n, Ks,t) is known. Our methods allow us to prove, among other things, that there is a positive constant c such that almost all K2,t-free graphs of order n have at least 1/12 · ex(n, K2,t) and at most (1 - c) ex(n, K2,t) edges. Moreover, our results have some interesting applications to the study of some Ramsey- and Turán-type problems.

AB - Denote by fn (H) the number of (labeled) H-free graphs on a fixed vertex set of size n. Erdos conjectured that, whenever H contains a cycle, fn(H) = 2(1+0(1))ex(n,h), yet it is still open for every bipartite graph, and even the order of magnitude of log2 f n (H) was known only for C4, C6, and K 3,3. We show that, for all s and t satisfying 2≤s≤t, f n(Ks,t=2O(n2-1/s), which is asymptotically sharp for those values of s and t for which the order of magnitude of the Turán number ex(n, Ks,t) is known. Our methods allow us to prove, among other things, that there is a positive constant c such that almost all K2,t-free graphs of order n have at least 1/12 · ex(n, K2,t) and at most (1 - c) ex(n, K2,t) edges. Moreover, our results have some interesting applications to the study of some Ramsey- and Turán-type problems.

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

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

U2 - 10.1112/jlms/jdq086

DO - 10.1112/jlms/jdq086

M3 - Article

AN - SCOPUS:79952942283

VL - 83

SP - 368

EP - 388

JO - Journal of the London Mathematical Society

JF - Journal of the London Mathematical Society

SN - 0024-6107

IS - 2

ER -