## 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 - Apr 2011 |

## ASJC Scopus subject areas

- Mathematics(all)