On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs
Abstract
In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an orientable surface of genus g≥ 1. In particular, for such a graph G with n vertices and maximum degree Δ, we show that the second-smallest eigenvalue of its Laplacian matrix satisfies λ2(LG)≲Δg/n. We also obtain an improved eigenvalue bound for Kh-minor-free graphs of λ2(LG)≲Δ(h2(log h)2)/n. In fact, our results directly prove much stronger results for reweighted eigenvalues, including higher reweighted eigenvalues. As a consequence, we obtain bounds not just on Laplacian eigenvalues, but also on normalized Laplacian eigenvalues and Steklov eigenvalues. Our results for genus-g graphs are optimal for all of these kinds of eigenvalues, while our results for Kh-minor-free graphs are optimal up to log(h) factors. Our techniques for genus-g graphs bootstrap bounded-degree bounds of normalized eigenvalues for entire classes to bounds for reweighted eigenvalues for the same classes without the bounded-degree limitation, while our techniques for Kh-minor-free graphs generalize an argument of Korhonen and Lokshtanov, making use of the Lovász local lemma.
Related
- Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
- Lower bounds for the magnitude of the minimum eigenvalue of graphs with applications to MaxCut and Chowla's cosine problem
- Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
- Sharp lower bounds for bisections of graphs with bounded maximum degree
- Eigenvalue comparison theorems for the Witten-Laplacian and the weighted p-Laplacian on complete manifolds with a modified Ricci curvature bounded from below
BibTeX
@misc{kolbe2026eigenvalue,
title = {{On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs}},
author = {Benedikt Kolbe and Jack Spalding-Jamieson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.27179},
eprint = {2608.27179},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27179},
}
RIS
TY - UNPB
TI - On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs
AU - Benedikt Kolbe
AU - Jack Spalding-Jamieson
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2608.27179
UR - https://arxiv.org/abs/2608.27179
AB - In this paper, we resolve a 30-year-old conjecture of Spielman and Teng concerning the performance of the spectral partitioning method on graphs embeddable on an orientable surface of genus g≥ 1. In particular, for such a graph G with n vertices and maximum degree Δ, we show that the second-smallest eigenvalue of its Laplacian matrix satisfies λ_2(L_G)≲Δg/n. We also obtain an improved eigenvalue bound for K_h-minor-free graphs of λ_2(L_G)≲Δ(h^2(log h)^2)/n. In fact, our results directly prove much stronger results for reweighted eigenvalues, including higher reweighted eigenvalues. As a consequence, we obtain bounds not just on Laplacian eigenvalues, but also on normalized Laplacian eigenvalues and Steklov eigenvalues. Our results for genus-g graphs are optimal for all of these kinds of eigenvalues, while our results for K_h-minor-free graphs are optimal up to log(h) factors. Our techniques for genus-g graphs bootstrap bounded-degree bounds of normalized eigenvalues for entire classes to bounds for reweighted eigenvalues for the same classes without the bounded-degree limitation, while our techniques for K_h-minor-free graphs generalize an argument of Korhonen and Lokshtanov, making use of the Lovász local lemma.
ER -