On the sum of the largest and smallest eigenvalues of graphs with high odd girth

Abstract

The sum ${\lambda }_1+{\lambda }_n$ 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\ge 3$, let ${\gamma }_k$ denote the supremum of $\frac{{\lambda }_1+{\lambda }_n}{n}$ over graphs without odd cycles of length less than $k$. The example of the $k$-cycle $C_k$ shows that ${\gamma }_k\ge \Omega (k^{-3})$. In their recent work, Abiad, Taranchuk, and Van Veluw showed that ${\gamma }_k\le O(k^{-1})$ and asked to determine the asymptotics of ${\gamma }_k$. Using approximation theory, we show that ${\gamma }_k\le O(k^{-3}(\log k{)}^3)$, giving a tight upper bound up to a poly-logarithmic factor.

9 pages (6 pages excluding appendix)

References in corpus (1)

• The Spectrum of Triangle-free Graphs