Source-linked AI summary
An Improved Upper Bound for the Tur\'an Number of the Hexagon
Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
TL;DR
Exact Turán numbers for even cycles remain unknown in general, including for C6. The paper improves the C6 upper bound using a contradiction argument with a maximizing induced subgraph. It proves an upper bound with leading coefficient 0.614314... .
Problem
Exact Turán numbers for even cycles are unknown in general, including for C4 and C6.
Source: §1 · p. 1Method
The proof argues by contradiction using an induced subgraph that maximizes Ψα,c.
Source: §3 · pp. 7–8Results
0.614314... n^4/3 + O(n) is an upper bound for ex(n, C6) for sufficiently large n.
Source: §4 · p. 8Takeaways & Limitations
The result gives a tighter upper bound but does not determine the exact leading constant for ex(n, C6).
Source: §4 · p. 8A gap remains between the best-known lower and upper bounds for the leading constant of ex(n, C6).
Source: §4 · p. 8
Abstract
from arXiv · showhide
For a graph $F$, the Tur\'an number $\operatorname{ex}(n,F)$ is the maximum number of edges in an $n$-vertex graph containing no copy of $F$. Determining the Tur\'an 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\"uredi, Naor, and Verstra\"ete [Advances in Mathematics, 2006], who proved that, for sufficiently large positive integer $n$, $$ \operatorname{ex}(n,C_6) \leq \lambda n^{4/3}+O(n)<0.6272 n^{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$, $$ \operatorname{ex}(n,C_6) \leq \alpha n^{4/3}+O(n)<0.6144 n^{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)$.
1 Introduction
The Turán numbers of even cycles remain difficult to determine, with exact values unknown even for C4 and C6. This paper improves the upper bound for C6 to a leading coefficient below 0.6144.
1 Introduction
- Turán-type problems for non-bipartite forbidden graphs are comparatively well understood, and Füredi and Gunderson described extremal graphs for odd cycles.Their work built on earlier results by Bondy, Woodall, and Bollobás.Source: §1 · p. 1
- Exact Turán numbers for even cycles are unknown in general, including for C4 and C6.The C4 case is understood asymptotically, but the exact value is not known.Source: §1 · pp. 1–2
- For every fixed k ≥ 2, an upper-bound exponent 1+1/k is established; matching lower bounds of order n^(1+1/k) are known only for k ∈ {2, 3, 5}, via finite-geometry constructions.Source: §1 · p. 2
- The C4 asymptotic formula motivated Erdős and Simonovits to conjecture its leading constant for every fixed even cycle, but Lazebnik, Ustimenko, and Woldar disproved this for C10.Their C10-free construction applies along an infinite sequence of n.Source: §1 · p. 2
- The earlier construction of Füredi, Naor, and Verstraëte gives ex(n, C6) > 0.5338n^4/3 for infinitely many n, while their previous upper bound was below 0.6272n^4/3.The earlier upper bound had remained the best known.Source: §1 · p. 2
- The parameter α is the unique solution in (1/2, 2/3) to 4α^3(3/2)^(1−1/(2α)) = 1.Source: §1 · p. 2
2 Preliminaries
The preliminaries classify vertex pairs by their length-three paths and collect earlier bounds on degrees, path counts, and the bipartite hexagon problem.
2 Preliminaries
- Pairs joined by multiple length-three paths are classified as degenerate or non-degenerate, while an oriented path is forward if it contains a directed length-two path starting at an endpoint.The text also defines C(π) as the number of length-three paths between the pair’s endpoints.Source: §2 · p. 3
- Füredi, Naor, and Verstraëte provide bounds on degrees and path contributions, including an orientation that controls forward paths for pairs in Π2.Source: §2 · p. 3
- The bipartite C6-free extremal bound is relevant because a maximum cut of an arbitrary graph yields a large bipartite subgraph.Source: §2 · p. 3
3 Proof of Theorem 1
The proof combines length-three path counts and orientations with a maximum-cut bound, then applies these inequalities to a suitable induced subgraph to establish the improved upper bound.
3 Proof of Theorem 1
- For C6-free graphs, path-counting lemmas bound p3(G) and the number of forward paths, yielding an upper bound on s for a suitable orientation.The proof also relates these counts to n(n−1) and the maximum degree times the edge count.Source: §3 · p. 4
- A lower bound on s for graphs of minimum degree at least two is expressed using the edge count and maximum-cut size, allowing comparison with the C6-free upper bound.Source: §3 · pp. 5–6
- The proof assumes a counterexample and selects an induced subgraph maximizing Ψα,c, whose minimum degree grows with its order.The maximizing-subgraph lemma also ensures its order tends to infinity when Ψα,c diverges.Source: §3 · pp. 6–7
- Degree control and a Taylor expansion yield F_nh(x) > n_h^2, contradicting the assumed counterexample and completing the bound.Source: §3 · pp. 7–8
- ex(n, C6) ≤ αn^4/3 + 2cn for all sufficiently large n, where α is the unique root in (1/2, 2/3) of 4α^3(3/2)^(1−1/(2α)) = 1.Source: §3 · pp. 7–8
4 Conclusions
The paper improves the upper bound for the C6 Turán number, while a gap from the best known lower bound remains.
4 Conclusions
- ex(n, C6) ≤ (0.614314...) n^4/3 + O(n).Source: §4 · p. 8
- The construction of Füredi, Naor, and Verstraëte leaves a gap between the best known lower and upper bounds for the leading constant.Source: §4 · p. 8
- Further work could determine whether ex(n, C6)/n^4/3 has a limit and its value, or strengthen or adapt the path-counting and orientation arguments for C10 and other even cycles.Source: §4 · p. 8