|
|||||
|
|
On the Turán number for the hexagon |
|
| Authors: | Zoltan Füredi Assaf Naor Jacques Verstraëte |
| Institution: | a Department of Mathematics, University of Illinois at Urbana-Champaign 1409 W. Green Street Urbana, Illinois 61801-2975, USA b Theory Group, Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA c Department of Combinatorics and Optimization, Math Faculty, University of Waterloo, 200 University Avenue West, Waterloo, Ont., Canada N2L 3G1 |
| Abstract: | A long-standing conjecture of Erd?s and Simonovits is that ex(n,C2k), the maximum number of edges in an n-vertex graph without a 2k-gon is asymptotically  as n tends to infinity. This was known almost 40 years ago in the case of quadrilaterals. In this paper, we construct a counterexample to the conjecture in the case of hexagons. For infinitely many n, we prove that |
| Keywords: | 05C35 05C38 |
| 本文献已被 ScienceDirect 等数据库收录！ | |