An Improved Upper Bound for the Turán Number of the Hexagon

Abstract

For a graph $F$, the Turán number $\mathrm{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Turán numbers of even cycles is a central problem in extremal graph theory and remains open in general. For $C_6$, the best previous upper bound was due to Füredi, Naor, and Verstraëte [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$\mathrm{ex}(n,C_6)\le \lambda n^{4/3}+O(n)<0.6272n^{4/3},$$ where $\lambda$ is the real root of $16{\lambda }^3-4{\lambda }^2+\lambda -3=0$. We improve this bound by showing that, for sufficiently large positive integer $n$, $$\mathrm{ex}(n,C_6)\le \alpha n^{4/3}+O(n)<0.6144n^{4/3},$$ where $\alpha$ is the unique real root of $4{\alpha }^3(3/2{)}^{1-1/(2\alpha )}=1$ in the interval $(1/2,2/3)$.

9 pages