### Abstract

Denote by f_{n} (H) the number of (labeled) H-free graphs on a fixed vertex set of size n. Erdos conjectured that, whenever H contains a cycle, f_{n}(H) = 2^{(1+0(1))ex(n,h)}, yet it is still open for every bipartite graph, and even the order of magnitude of log_{2} f _{n} (H) was known only for C_{4}, C_{6}, and K _{3,3}. We show that, for all s and t satisfying 2≤s≤t, f _{n}(K_{s,t}=2^{O(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, K_{s,t}) is known. Our methods allow us to prove, among other things, that there is a positive constant c such that almost all K_{2,t}-free graphs of order n have at least 1/12 · ex(n, K_{2,t}) and at most (1 - c) ex(n, K_{2,t}) edges. Moreover, our results have some interesting applications to the study of some Ramsey- and Turán-type problems.

Original language | English (US) |
---|---|

Pages (from-to) | 368-388 |

Number of pages | 21 |

Journal | Journal of the London Mathematical Society |

Volume | 83 |

Issue number | 2 |

DOIs | |

State | Published - Jan 1 2011 |

### Fingerprint

### ASJC Scopus subject areas

- Mathematics(all)

### Cite this

_{s,t}-free graphs.

*Journal of the London Mathematical Society*,

*83*(2), 368-388. https://doi.org/10.1112/jlms/jdq086

**The number of K _{s,t}-free graphs.** / Balog, Jozsef; Samotij, Wojciech.

Research output: Contribution to journal › Article

_{s,t}-free graphs'

*Journal of the London Mathematical Society*, vol. 83, no. 2, pp. 368-388. https://doi.org/10.1112/jlms/jdq086

_{s,t}-free graphs. Journal of the London Mathematical Society. 2011 Jan 1;83(2):368-388. https://doi.org/10.1112/jlms/jdq086

}

TY - JOUR

T1 - The number of Ks,t-free graphs

AU - Balog, Jozsef

AU - Samotij, Wojciech

PY - 2011/1/1

Y1 - 2011/1/1

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

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 -