Lower bounds for the magnitude of the minimum eigenvalue of graphs with applications to MaxCut and Chowla's cosine problem
Abstract
Jin, MilojeviÄ, Tomon and Zhang established a powerful recursive estimate relating the positive eigenvalues of a graph whose least eigenvalue is small in absolute value. We establish a refinement of this result, yielding improved estimates across spectral graph theory and discrepancy theory, and for Chowla's cosine problem. Recent results of Janzer, Tomon and Yip allow us to directly transfer least eigenvalue estimates to the corresponding surplus estimates.
Using these tools, we fully resolve a conjecture of Räty, Sudakov and Tomon. We show that, for an $n$-vertex graph $G$ with least eigenvalue $λ_n$ and surplus $\operatorname{sp}(G)$, if $G$ is $ε$-far from all disjoint unions of cliques, then $|λ_n|\geq Ω_ε(n^{1/4})$ and $\operatorname{sp}(G)\geq Ω_ε(n^{5/4})$. Furthermore, we show that when $G$ is $n^{-o(1)}$-far from all disjoint unions of cliques, we have $|λ_n|\geq n^{1/4 - o(1)}$ and $\operatorname{sp}(G)\geq n^{5/4 - o(1)}$. Finally, we show that the surplus of a $K_t$-free graph with $m$ edges is at least $m^{0.614 - o(1)}$ as $m$ tends to infinity.引用本文复制引用
Fredy Yip.Lower bounds for the magnitude of the minimum eigenvalue of graphs with applications to MaxCut and Chowla's cosine problem[EB/OL].(2026-10-01)[2026-10-03].https://arxiv.org/abs/2610.01657.学科分类
数学
