کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6425246 | 1633790 | 2016 | 47 صفحه PDF | دانلود رایگان |

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,C2â)=O(n1+1/â), and this bound is conjectured to be sharp up to the implicit constant. In this paper we prove that the number of C2â-free graphs on n vertices is at most 2O(n1+1/â), 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,C6)C6-free graphs with n vertices for some c>0 and infinitely many values of nâ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.
Journal: Advances in Mathematics - Volume 298, 6 August 2016, Pages 534-580