Analysis reveals the relationship between eigenvalues and odd girth in graphs, suggesting tighter bounds for bipartiteness metrics.
The sum λ₁ + λₙ of the maximum and minimum eigenvalues, and the odd girth of a graph both measure bipartiteness. We seek to relate these measures. In particular, for an odd integer k≥ 3, let γₖ denote the supremum of λ₁ + λₙ/n over graphs without odd cycles of length less than k. The example of the k-cycle Cₖ shows that γₖ≥ Ω(k⁻³). In their recent work, Abiad, Taranchuk, and van Veluw showed that γₖ≤ O(k⁻¹) and asked to determine the asymptotics of γₖ. Using approximation theory, we show that γₖ≤ O(k⁻³log³ k), giving a tight upper bound up to a poly-logarithmic factor.
No takes yet. Share an insight, caveat, or question.
Fredy Yip (2025) studied this question.