The number of K_m,m-free graphs

A graph is called H-free if it contains no copy of H. Denote by f_n(H) the number of (labeled) H-free graphs on n vertices. Erdo{double acute}s conjectured that f_n(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 log₂f_n(H) is not known. We prove that f_n(K_m,m) ≤ 2^O(n^2-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,K_m,m) is conjectured to be Θ(n^2-1/m). Our method also yields a bound on the number of K_m,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 K_3,3-free graphs of order n have more than 1/20·ex(n,K_3,3) edges.