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 sp(G), if G is ε-far from all disjoint unions of cliques, then |λn|≥ Ωε(n1/4) and sp(G)≥ Ωε(n5/4). Furthermore, we show that when G is n−o(1)-far from all disjoint unions of cliques, we have |λn|≥ n1/4 − o(1) and sp(G)≥ n5/4 − o(1). Finally, we show that the surplus of a Kt-free graph with m edges is at least m0.614 − o(1) as m tends to infinity.
Related
- Bounds on the Minimum Eigenvalue Modulus for Hadamard Products of M- and H-Matrices and Their Inverses
- High-order guaranteed lower bounds for the Schrödinger eigenvalue problem
- Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution
- Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix
- Minimum-Area Enclosing Rectangles and the First Neumann Eigenvalue of Planar Convex Domains
BibTeX
@misc{yip2026lower,
title = {{Lower bounds for the magnitude of the minimum eigenvalue of graphs with applications to MaxCut and Chowla's cosine problem}},
author = {Fredy Yip},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01657},
eprint = {2610.01657},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01657},
}
RIS
TY - UNPB
TI - Lower bounds for the magnitude of the minimum eigenvalue of graphs with applications to MaxCut and Chowla's cosine problem
AU - Fredy Yip
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.01657
UR - https://arxiv.org/abs/2610.01657
AB - 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 sp(G), if G is ε-far from all disjoint unions of cliques, then |λ_n|≥ Ω_ε(n^1/4) and sp(G)≥ Ω_ε(n^5/4). Furthermore, we show that when G is n^−o(1)-far from all disjoint unions of cliques, we have |λ_n|≥ n^1/4 − o(1) and sp(G)≥ 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.
ER -