The number of C_2ℓ-free graphs

详细信息    查看全文

• 作者：Robert Morris ; ^{rob@impa.br" class="auth_mail" title="E-mail the corresponding author} ; David Saxton ^{saxton@impa.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Extremal graph theory ; Hypergraph containers ; Balanced supersaturation
• 刊名：Advances in Mathematics
• 出版年：2016
• 出版时间：6 August 2016
• 年：2016
• 卷：298
• 期：Complete
• 页码：534-580
• 全文大小：795 K

文摘

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)}$2^{(1+o(1))\mathrm{ex}(n,H)}$ such graphs. For bipartite graphs, however, much less is known: even the weaker bound 2^O(ex(n,H))$2^{O(\mathrm{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_2ℓ)=O(n^1+1/ℓ)$\mathrm{ex}(n,C_{2\ell })=O\left(n^{1+1/\ell }\right)$, and this bound is conjectured to be sharp up to the implicit constant. In this paper we prove that the number of C_2ℓ$C_{2\ell }$-free graphs on n   vertices is at most 2^O(n1+1/ℓ)$2^{O(n^{1+1/\ell })}$, 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₆)}$2^{(1+c)\mathrm{ex}(n,C_6)}$C₆$C_6$-free graphs with n   vertices for some c>0$c>0$ and infinitely many values of n∈N$n\in \mathbb{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)$G(n,p)$ for both even cycles and complete bipartite graphs.