Source-linked AI summary
On Eigenvalue Bounds for Bounded Genus Graphs and Minor-Free Graphs
Benedikt Kolbe, Jack Spalding-Jamieson
TL;DR
The paper asks whether spectral partitioning admits sharp eigenvalue guarantees on bounded-genus and minor-free graphs. It proves stronger reweighted eigenvalue bounds using class-wide bootstrapping and a Lovász Local Lemma-based congestion argument. The results resolve the bounded-genus conjecture, substantially improve the minor-free case, and transfer to other eigenvalue notions and separators.
Problem
The paper addresses open questions about proving the bounded-genus eigenvalue conjecture in full generality and improving the minor-free bound toward its best-possible constant.
Method
The proof bootstraps bounded-degree bounds class-wide for bounded-genus graphs and extends a Korhonen–Lokshtanov Lovász Local Lemma argument for minor-free graphs.
Results
The paper proves optimal-up-to-constants bounded-genus bounds and minor-free bounds optimal up to O(log^2 h) and O(log^3 h) factors, including stronger reweighted eigenvalue results.
Takeaways & Limitations
The bounds transfer to normalized Laplacian and Steklov eigenvalues and yield improved guarantees for existing partitioning algorithms.
Takeaways & Limitations
A previously claimed bounded-genus extension to non-triangulated graphs contained a proof issue, and one cited bound holds only in restricted cases.
Abstract
from arXiv · showhide
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$. 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 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.
1 Introduction
The paper resolves the bounded-genus conjecture and advances the minor-free case through stronger reweighted eigenvalue bounds, with consequences for several eigenvalue notions and vertex separators.
- Motivation: Spectral partitioning’s performance is certified through upper bounds on Laplacian eigenvalues, especially λ2(L_G), whose smaller values imply better partitions.The paper studies special graph classes to explain why spectral partitioning is effective.
- Open questions: The paper addresses two open questions: proving the bounded-genus conjecture in full generality and improving the minor-free constant toward its best-possible value two.Earlier work left both questions unresolved.
- Main results: Theorem 1.7 gives reweighted eigenvalue bounds for every positive distribution on n-vertex graphs of orientable genus at most g, resolving the first question.The bounded-genus result is optimal up to constant factors.
- Main results: Theorem 1.8 gives reweighted eigenvalue bounds for K_h-minor-free graphs, with optimality gaps of O(log^2 h) and O(log^3 h) for the two minor-free bounds.These results constitute significant progress toward the second conjecture.
- Consequences: A polynomial-time algorithm computes balanced vertex separators of size ≲min{√log Δ, log g} · √gn for genus at most g and ≲min{√log Δ, log h} · h log h · √n for K_h-minor-free graphs.The separator guarantees combine the eigenvalue theorems with existing algorithmic results.
- Consequences: The results transfer to normalized Laplacian and Steklov eigenvalues, and improvements in these bounds imply improved guarantees for existing graph-partitioning algorithms.They also yield bounds for higher eigenvalues and related separator results.
- Techniques: For bounded genus, the proof bootstraps bounded-degree eigenvalue bounds class-wide to unbounded-degree reweighted bounds; for minor-free graphs, it extends a Lovász Local Lemma argument for congestion.The two proof strategies differ, while their extensions to other eigenvalue notions are unified.
2 Bounded-Genus Graphs
The bounded-genus argument reduces arbitrary-degree graphs to bounded-degree embedded graphs through tree gadgets, then transfers eigenvalue bounds back using reweighted Rayleigh quotients.
- Degree reduction: The proof uses a degree-reduction proposition relating reweighted eigenvalues of an embedded graph to Laplacian eigenvalues of bounded-degree graphs in the same surface.The reduction applies to every positive vertex distribution and higher eigenvalue index k.
- Tree gadgets: Each original vertex is replaced by an ordered binary tree whose leaves preserve the cyclic order of incident edges while keeping maximum degree at most three.The tree has 2s−1 vertices and supports a bound on deviations from averages.
- Tree gadgets: The inserted trees and edge bundles preserve the embedding, and the resulting graph is simple, connected, and of maximum degree at most three.Edge bundles match consecutive leaf blocks around the replaced vertices without crossings.
- Rayleigh-quotient transfer: Averages over the replacement trees define a linear map from eigenvectors of the reduced graph back to the original vertices.The map is shown to be injective on the relevant k-dimensional eigenspace, enabling Courant–Fischer comparison.
- Rayleigh-quotient transfer: The resulting inequalities control both numerator and denominator of the Rayleigh quotient, first for positive rational pairs and then for general weights by continuity.The proof finally maximizes over all admissible edge weightings.
3 Minor-Free Graphs
The minor-free proof combines multicommodity-flow congestion bounds, metric-embedding infrastructure, and a transfer from arbitrary vertex weights to uniform weights.
- Proof framework: The method reduces the minor-free eigenvalue problem to an L2-congestion multicommodity-flow bound within an established sequence of graph-metric reductions.The framework builds on work by Biswal, Lee, Rao, Kelner, Lee, Price, Teng, Tung, and Spalding-Jamieson.
- Arbitrary weights: Arbitrary vertex distributions are handled by transforming each vertex into a cluster with attached leaves, reducing the problem to the uniform-weight case.The construction preserves K_h-minor-freeness and directly applies to reweighted eigenvalues.
- Uniform weights: The uniform-weight case follows from bounds connecting minor-free graph spread, padded decompositions, and extremal L2-congestion.The paper states the intermediate spread and congestion estimates before deriving the uniform eigenvalue bound.
- Congestion bound: A graph H with at most 3h^2 edges is used as a minor-detection gadget: any graph almost-embedding H contains K_h as a minor.The Lovász local lemma constructs such an almost-embedding probabilistically in the contradiction argument.
4 Eigenvalue Relationships
The paper transfers reweighted eigenvalue bounds to ordinary Laplacian, normalized Laplacian, and Steklov eigenvalues using leaf-attachment closure and variational comparisons.
- Laplacian relationships: Bounds on reweighted eigenvalues are sufficient to control several other eigenvalue notions, including ordinary Laplacian and normalized Laplacian eigenvalues.The ordinary Laplacian comparison uses the uniform vertex distribution and an admissible uniform edge weighting.
- Laplacian relationships: The normalized Laplacian comparison follows by applying Courant–Fischer after substituting degree-weighted coordinates.The change of variables is explicitly x := D^−1/2z.
- Leaf attachment: Attaching leaves preserves both bounded-genus graph families and H-minor-free families when H has minimum degree at least two.For minor-free graphs, deleting attached leaves from a minor model recovers a model in the original graph.
- Steklov eigenvalues: The transfer theorem attaches many leaves to vertices in a boundary set B, assigns feasible weights, and compares the resulting graph's eigenvalues with Steklov eigenvalues.The construction uses r = Δn^2 leaves per boundary vertex.
- Steklov eigenvalues: The comparison relies on harmonic extension outside B, maximum-principle bounds, paths from interior vertices to B, and Courant–Fischer.The harmonic values outside B remain bounded by the maximum boundary value.
A Lower Bounds
The lower-bound section establishes that the bounded-genus results are tight up to constants, while the minor-free results are tight up to polylogarithmic factors in h.
- Tightness: The paper states that all bounded-genus eigenvalue bounds are optimal up to constant factors.This includes the higher-eigenvalue result cited as Theorem 1.7.
- Tightness: For minor-free graphs, the corresponding bounds are optimal up to O(polylog(h)) factors.The claimed comparison applies to all minor-free eigenvalue bounds discussed in the paper.
- Genus lower bounds: A bounded-degree genus-g construction supplies lower bounds for every eigenvalue index k with 2 ≤ k ≤ n.The proposition applies for sufficiently large n and g.
- Minor-free lower bounds: A new construction gives a K_h-minor-free graph with n = Θ(h^2k) vertices and maximum degree at most four for every k ≥ 2.The paper describes this lower bound as new to the authors' knowledge.
- Comparison: The minor-free construction has intrinsically worse dependence on k than the bounded-genus construction.The paper explicitly highlights this difference between the two lower bounds.