On the Turán number for the hexagon

Zoltan Füredi, Assaf Naor, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)476-496
Number of pages21
JournalAdvances in Mathematics
Volume203
Issue number2
DOIs
StatePublished - Jul 10 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Excluded cycles
  • Extremal graph theory
  • Turán numbers

Fingerprint

Dive into the research topics of 'On the Turán number for the hexagon'. Together they form a unique fingerprint.

Cite this