TY - JOUR

T1 - On the Turán number for the hexagon

AU - Füredi, Zoltan

AU - Naor, Assaf

AU - Verstraëte, Jacques

N1 - Funding Information:
∗ Corresponding author. Fax: +1 425 936 7329. E-mail addresses: [email protected] (Z. Füredi), [email protected] (A. Naor), [email protected] (J. Verstraëte). 1Research supported in part by a Hungarian National Science Foundation Grant OTKA T 032452, and by a National science Foundation Grant DMS 0140692.

PY - 2006/7/10

Y1 - 2006/7/10

N2 - A long-standing conjecture of Erdo{combining double acute accent}s and Simonovits is that ex ( n, C2 k ), the maximum number of edges in an n-vertex graph without a 2 k-gon is asymptotically frac(1, 2) n1 + 1 / k 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{A formula is presented}We also show that ex ( n, C6 ) {less-than or slanted equal to} λ n4 / 3 + O ( n ) < 0.6272 n4 / 3 if n is sufficiently large, where λ is the real root of 16 λ3 - 4 λ2 + λ - 3 = 0. This yields the best-known upper bound for the number of edges in a hexagon-free graph. The same methods are applied to find a tight bound for the maximum size of a hexagon-free 2 n × n bipartite graph.

AB - A long-standing conjecture of Erdo{combining double acute accent}s and Simonovits is that ex ( n, C2 k ), the maximum number of edges in an n-vertex graph without a 2 k-gon is asymptotically frac(1, 2) n1 + 1 / k 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{A formula is presented}We also show that ex ( n, C6 ) {less-than or slanted equal to} λ n4 / 3 + O ( n ) < 0.6272 n4 / 3 if n is sufficiently large, where λ is the real root of 16 λ3 - 4 λ2 + λ - 3 = 0. This yields the best-known upper bound for the number of edges in a hexagon-free graph. The same methods are applied to find a tight bound for the maximum size of a hexagon-free 2 n × n bipartite graph.

KW - Excluded cycles

KW - Extremal graph theory

KW - Turán numbers

UR - http://www.scopus.com/inward/record.url?scp=33747510319&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33747510319&partnerID=8YFLogxK

U2 - 10.1016/j.aim.2005.04.011

DO - 10.1016/j.aim.2005.04.011

M3 - Article

AN - SCOPUS:33747510319

SN - 0001-8708

VL - 203

SP - 476

EP - 496

JO - Advances in Mathematics

JF - Advances in Mathematics

IS - 2

ER -