On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.27179
curl -X POST /api/v1/records/arxiv/2608.27179/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.27179/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'