The number of C₂ₗ-free graphs

Original · EN

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ős, Frankl and Rödl 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 2O(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₂ₗ) = O(n¹ ⁺ ¹/ˡ), and this bound is conjectured to be sharp up to the implicit constant. In this paper we prove that the number of C₂ₗ-free graphs on n vertices is at most 2ᵒ⁽ⁿ¹ ⁺ ¹/ˡ⁾, confirming a conjecture of Erdő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₆) C₆-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án problem on the Erdős-Rényi random graph G(n,p) for both even cycles and complete bipartite graphs.