Improved upper bound found for graphs avoiding six-node cycles
An Improved Upper Bound for the Turán Number of the Hexagon
Discrete Mathematics
Summary
The paper deals with a problem in graph theory about how many connections a large network can have without including a specific loop of six nodes. This problem has been studied for many years. The authors improved the best known mathematical limit for how large such a network can be while still avoiding these six-node loops. Their new limit is a bit smaller than the previously known one, giving a tighter understanding of the problem.
What this means in practice
- •For network designers: Use tighter theoretical limits when designing networks that must exclude certain cyclical substructures to improve reliability and avoid failure modes.
- •For algorithm developers: Incorporate improved bounds to optimize algorithms that detect or avoid six-node cycles in large graphs.
A theory result. No direct application yet.
Authors
Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
Abstract
For a graph $F$, the Turán number $\operatorname{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$, $$ \operatorname{ex}(n,C_6) \leq λ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$, $$ \operatorname{ex}(n,C_6) \leq α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)$.