One of the most basic questions one can ask about a graph $H$ is: how many $H$-free graphs on $n$ vertices are there? For non-bipartite $H$, the answer to this question has been well-understood since 1986, when Erd\H{ o}s, Frankl and R\"odl proved that there are $2^{ (1 + o(1)) ex(n,H)}$ such graphs. For bipartite graphs, however, much less is known: even the weaker bound $2^{ O(ex(n,H))}$ has been proven in only a few special cases: for cycles of length four and six, and for some complete bipartite graphs. For even cycles, Bondy and Simonovits proved in the 1970s that ex$(n,C_{ 2l}) = O( n^{ 1 + 1/l} )$, and this bound is conjectured to be sharp up to the implicit constant. In this paper we prove that the number of $C_{ 2l}$-free graphs on $n$ vertices is at most $2^{ O(n^{ 1 + 1/l})}$, confirming a conjecture of Erd\H{ o}s. Our proof uses the hypergraph container method, which was developed recently (and independently) by Balogh, Morris and Samotij, and by Saxton and Thomason, together with a new 'balanced supersaturation theorem' for even cycles. We moreover show that there are at least $2^{ (1 + c)ex(n,C_6)}$ $C_6$-free graphs on $n$ vertices for some $c > 0$ and infinitely many values of $n$, disproving a well-known and natural conjecture. As a further application of our method, we essentially resolve the so-called Tur\'an problem on the Erd\H{ o}s-R\'enyi random graph $G(n,p)$ for both even cycles and complete bipartite graphs.
Categories: math.CO