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.
ASJC Scopus subject areas