ALMOST ALL C-4-FREE GRAPHS HAVE FEWER THAN (1-epsilon) ex(n, C-4) EDGES

作者：Balogh Jozsef^*; Samotij Wojciech

来源：SIAM Journal on Discrete Mathematics, 2010, 24(3): 1011-1018.

DOI：10.1137/09074989X

• asymptotic graph structure
• asymptotic graph enumeration
• C-4-free
• Turan's problem
• extremal graphs

A graph is called H-free if it contains no copy of H. Let ex(n, H) denote the Turan number for H, i.e., the maximum number of edges that an n-vertex H-free graph may have. An old result of Kleitman and Winston states that there are 2(O(ex(n, C4))) C-4-free graphs on n vertices. Furedi showed that almost all C-4-free graphs of order n have at least c ex(n, C-4) edges for some positive constant c. We prove that there is a positive constant epsilon such that almost all C-4-free graphs have at most (1-epsilon) ex(n, C-4) edges. This resolves a conjecture of Balogh, Bollobas, and Simonovits for the 4-cycle.

• 出版日期2010