On the Turán number for the hexagon |
| |
Authors: | Zoltan Fü redi,Assaf Naor,Jacques Verstraë te |
| |
Affiliation: | 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 等数据库收录! |
|