TIME: 1:30-2:20 pm,  February 12, 2008

PLACE: CSE 503  

SPEAKER: James Lee
         University of Washington

TITLE: The virtue of not conforming

ABSTRACT:
For well over 30 years,  the second eigenvalue of the Laplacian of Riemann
surfaces has been studied in connection with other geometric invariants like
genus, curvature, and diameter.  In 1980, Yang and Yau gave optimal bounds
on the second eigenvalue of the Laplacian for 2-dimensional surfaces of
bounded genus.  Spielman and Teng showed that such a bound holds in the
graph setting for planar graphs, which implies that for bounded degree planar
graphs, Lipton-Tarjan separators will be found by a simple spectral algorithm.
Later, Kelner extended this to all graphs of bounded genus.

All these approaches rely on conformal mappings, or their discrete
analogues (e.g. Koebe's embedding theorem), and it seems difficult to
extend them to families of graphs that don't possess a conformal structure.
For instance, Spielman and Teng conjecture that similar eigenvalue bounds
should be available for arbitrary graphs excluding a fixed minor.

We give a simple intrinsic approach to these spectral bounds which does
not rely on conformal mappings or uniformization; in particular, we are able
to resolve positively the conjecture, showing that spectral partitioning can
recover \sqrt{n}-sized separators in all excluded-minor families.
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 result on separators in non-planar graphs.

Joint work with Punya Biswal and Satish Rao.