On the sum of the largest and smallest eigenvalues of graphs with high odd girth
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911472599171072 |
|---|---|
| author | Yip, Fredy |
| author_facet | Yip, Fredy |
| contents | The sum $λ_1 + λ_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\geq 3$, let $γ_k$ denote the supremum of $\frac{λ_1 + λ_n}{n}$ over graphs without odd cycles of length less than $k$. The example of the $k$-cycle $C_k$ shows that $γ_k\geq Ω(k^{-3})$. In their recent work, Abiad, Taranchuk, and Van Veluw showed that $γ_k\leq O(k^{-1})$ and asked to determine the asymptotics of $γ_k$. Using approximation theory, we show that $γ_k\leq O(k^{-3}(\log k)^3)$, giving a tight upper bound up to a poly-logarithmic factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06611 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the sum of the largest and smallest eigenvalues of graphs with high odd girth Yip, Fredy Combinatorics 05C38, 15A18 The sum $λ_1 + λ_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\geq 3$, let $γ_k$ denote the supremum of $\frac{λ_1 + λ_n}{n}$ over graphs without odd cycles of length less than $k$. The example of the $k$-cycle $C_k$ shows that $γ_k\geq Ω(k^{-3})$. In their recent work, Abiad, Taranchuk, and Van Veluw showed that $γ_k\leq O(k^{-1})$ and asked to determine the asymptotics of $γ_k$. Using approximation theory, we show that $γ_k\leq O(k^{-3}(\log k)^3)$, giving a tight upper bound up to a poly-logarithmic factor. |
| title | On the sum of the largest and smallest eigenvalues of graphs with high odd girth |
| topic | Combinatorics 05C38, 15A18 |
| url | https://arxiv.org/abs/2509.06611 |