{"id":"arxiv/2608.27179","url":"https://arxiv.org/abs/2608.27179","tags":["math.CO","cs.DM","math.SP"],"score":0,"title":"On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs","domain":"math.CO","source":"arxiv","authors":["Benedikt Kolbe","Jack Spalding-Jamieson"],"reviews":0,"subject":"math.CO","summary":"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\\ge 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)\\lesssimΔ\\frac g n$. We also obtain an improved eigenvalue bound for $K_h$-minor-free graphs of $λ_2(L_G)\\lesssimΔ\\frac{h^2(\\log h)^2}n$. In fact, our results directly prove much stronger results for reweighted eigenvalues, including…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}