caa a22 4500 445358742 CHVBK 20180317142908.0 cr unu---uuuuu 170323e20110301xx s 000 0 eng 10.1007/s00493-011-2610-y doi (NATIONALLICENCE)springer-10.1007/s00493-011-2610-y The number of K m,m -free graphs [Elektronische Daten] [József Balogh, Wojciech Samotij] 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. Erdős conjectured that f n (H) ≤ 2(1+o(1))ex(n,H). This was first shown to be true for cliques; then, Erdő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 log2 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 Erdő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. János Bolyai Mathematical Society and Springer Verlag, 2011 Balogh József Department of Mathematics, University of California, San Diego 9500 Gilman Drive, 92093, La Jolla, CA, USA aut Samotij Wojciech Department of Mathematics, University of Illinois, 61801, Urbana, IL, USA aut Combinatorica Springer-Verlag 31/2(2011-03-01), 131-150 0209-9683 31:2<131 2011 31 493 https://doi.org/10.1007/s00493-011-2610-y text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2610-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Balogh József Department of Mathematics, University of California, San Diego 9500 Gilman Drive, 92093, La Jolla, CA, USA aut NATIONALLICENCE 700 1- Samotij Wojciech Department of Mathematics, University of Illinois, 61801, Urbana, IL, USA aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/2(2011-03-01), 131-150 0209-9683 31:2<131 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer