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 -