PreprintCC BY-NC-ND 4.0arXiv
An Improved Upper Bound for the Turán Number of the Hexagon
Abstract
For a graph F, the Turán number 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 C6, 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, ex(n,C6) ≤ λn4/3+O(n)<0.6272 n4/3, where λ is the real root of $ 16λ^3-4λ^2+λ-3=0$. We improve this bound by showing that, for sufficiently large positive integer n, ex(n,C6) ≤ αn4/3+O(n)<0.6144 n4/3, where α is the unique real root of $ 4 α^{3} (3/2)^{1-1/(2α)} =1$ in the interval $(1/2,2/3)$.
Related
- An improved upper bound on the chromatic number of the n-dimensional sphere
- An improved upper bound for the fair domination number of maximal outerplanar graphs
- An improved lower and upper bound of the k-limited domination number
- Improved upper bound on the number of distinct k-decks for any k and alphabet size by counting the independent parameters
- Improved Sidorenko bound for hypergraph Turan densities
BibTeX
@misc{das2026improved,
title = {{An Improved Upper Bound for the Turán Number of the Hexagon}},
author = {Sandip Das and Sk Samim Islam and Aashirwad Mohapatra and Saumya Sen},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10003},
eprint = {2609.10003},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10003},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - An Improved Upper Bound for the Turán Number of the Hexagon
AU - Sandip Das
AU - Sk Samim Islam
AU - Aashirwad Mohapatra
AU - Saumya Sen
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10003
UR - https://arxiv.org/abs/2609.10003
AB - For a graph F, the Turán number 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, ex(n,C_6) ≤ λn^4/3+O(n)<0.6272 n^4/3, where λ is the real root of $ 16λ^3-4λ^2+λ-3=0$. We improve this bound by showing that, for sufficiently large positive integer n, ex(n,C_6) ≤ αn^4/3+O(n)<0.6144 n^4/3, where α is the unique real root of $ 4 α^{3} (3/2)^{1-1/(2α)} =1$ in the interval $(1/2,2/3)$.
ER -