Seminar: December 1, 2008

James Lee, University of Washington

Eigenvalue Bounds, Spectral Partitioning, and Flow Deformations

We present a new approach to upper bounds on the eigenvalues of the Laplacian on finite graphs. Such bounds are used to analyze the efficacy of popular spectral partitioning heuristics. Whereas previous methods, e.g. those of Spielman and Teng in the setting of graphs, and Hersch in the setting of surfaces, relied on conformal mappings into a model space, our approach is intrinsic.

We use a certain kind of multi-commodity flow at optimality to deform the geometry of the graph. As the flow spreads out, the graph becomes more uniform. We then embed this geometry into Euclidean space to recover a bound on the eigenvalues. Analyzing the structure of the optimal flow requires arguments from geometric combinatorics.

In particular, we are able to resolve a conjecture of Spielman and Teng that gives optimal eigenvalue bounds for graphs which exclude any fixed minor. Unlike previous spectral approaches, we can obtain separators without a bounded degree assumption; although the second eigenvector may perform poorly in this setting, we show that our test vector still gives a \sqrt{n}-sized separator, yielding an alternate proof of the Alon-Seymour-Thomas theorem on separators in non-planar graphs.