Graph eigenvalues, spectral partitioning, and flow deformations

James Lee
Department of Computer Science & Engineering
University of Washington, Seattle


Wednesday, Jan 27, 2010
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:


We present a new approach for controlling the spectrum 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. In particular, we are able to resolve a number of conjectures of Spielman and Teng from the 90s, as well as the graph-theoretic version of a conjecture of Yau from the 80s. Our approach has purely combinatorial consequences as well, like a new proof of the Alon-Seymour-Thomas theorem for small separators in non-planar graphs. Our tools involve mathematical programming and the theory of multi-commodity flows, and machinery from metric embeddings, convex geometry, and topological combinatorics. Despite this, the talk will be essentially self-contained.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html