Premium
The number of K s,t ‐free graphs
Author(s) -
Balogh József,
Samotij Wojciech
Publication year - 2011
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/jdq086
Subject(s) - combinatorics , mathematics , bipartite graph , order (exchange) , graph , vertex (graph theory) , discrete mathematics , finance , economics
Denote by f n ( H ) the number of (labeled) H ‐free graphs on a fixed vertex set of size n . Erdős conjectured that, whenever H contains a cycle,f n ( H ) = 2 ( 1 + o ( 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 ( n 2 − 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.