We present a new approach for proving 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 certain kinds of
multi-commodity flows 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 Rayleigh
quotient.
Analyzing the structure of the 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. In the second half of the talk, I will focus
on new results using "subset flows" to bound higher eigenvalues of the
Laplacian.
Copyright. All Rights Reserved.