In the previous lecture, we gave an upper bound on the second eigenvalue of the Laplacian of (bounded degree) planar graphs in order to analyze a simple spectral partitioning algorithm. A natural question is whether these bounds extend to more general families of graphs. Well-known generalizations of planar graphs are those which can be embedded on a surface of fixed genus, and, more generally, families of graphs that arise by forbidding minors. In fact, Spielman and Teng conjectured that for any graph excluding as a minor, one should have . Of course planar graphs have genus 0, and by Wagner’s theorem, are precisely the graphs which exclude and as minors. In this lecture, we will follow an intrinsic approach of Biswal, myself, and Rao which, in particular, is able to resolve the conjecture of Spielman and Teng. First, we see why even pushing the conformal approach to bounded genus graphs is difficult.
Bounded genus graphs
For graphs of bounded genus, there is hope to use an approach based on conformal mappings. In 1980, Yang and Yau proved that
for any compact Riemannian surface of genus . (Note that for the Laplace-Beltrami operator, one usually writes as the first non-zero eigenvalue, rather than .) In analog with Hersch’s proof of the genus 0 case, they use Riemann-Roch to obtain a degree- conformal mapping to the Riemann sphere, then try to pull back a second eigenfunction. A factor of the degree is lost in the Rayleigh quotient (hence the factor in the preceding bound), and Hersch’s Möbius trick is still required.
An analogous proof for graphs of bounded genus would proceed by constructing a circle packing of on the sphere , but instead of the circles having disjoint interiors, we would be assured that every point of is contained in at most circles. Unfortunately, such a result is impossible (this has to do with the handling of branch points in the discrete setting). Kelner has to take a different approach in his proof that for graphs of genus at most .
He starts with a circle packing of on a compact surface of genus (whose existence follows from results of Beardon and Stephenon and He and Schramm). Then Kelner randomly subdivides repeatedly, and these subdivisions give progressively better approximations to some sequence of surfaces . Once the approximation is of high enough quality, one applies Riemann-Roch to , and infers something about a subdivision of . The final element is to track how the second eigenvalue of changes (in expectation) under random subdivision.
Needless to say, this approach is already quite delicate, and for graphs that can’t be equipped with some kind of conformal structure, we seem to have reached a dead end. In this lecture, we’ll see how to use intrinsic deformations of the geometry of in order to bound its eigenvalues. Eventually, this will reduce to the study of certain kinds of multi-commodity flows.
Metrics on graphs
Let be an arbitrary n-vertex graph with maximum degree . Recall that we can write
where . (Also recall that we can replace by any Hilbert space, and the same formula holds.) The first step is to prepare this equality for “non-linearization” by getting rid of the linear condition and the sum . (This is a popular sort of passage in the non-linear geometry of Banach spaces, which also plays a rather important role in applications to the theoretical CS.) The goal is to get only terms that look like . Fortunately, there is a well-known way to do this:
which follows easily from the equality when .
Thus if we want to bound , we need to find an for which the latter ratio (without the ) is . Now, for someone who works a lot with linear programming relaxations, it’s very natural to consider a “relaxation”
where the minimization is over all pseudo-metrics d, i.e. symmetric non-negative functions which satisfy the triangle inequality, but might have even for . Certainly , but Bourgain’s embedding theorem (which states that every n-point metric space embeds into a Hilbert space with distortion at most ) also assures us that . Since we are trying to show that , this term is morally negligible. One can see the paper for a more advanced embedding argument that doesn’t lose this factor, but for now we concentrate on proving that . The embedding theorems allow us to concentrate on finding an intrinsic metric on the graph with small “Rayleigh quotient,” without having to worry about an eventual geometric representation.
As a brief preview… we are going to find a good metric by taking a certain kind of all-pairs multi-commodity flow at optimality, and weighting the edges by their congestion in the optimal flow. Thus as the flow spreads out on the graph, it has the effect of “uniformizing” its geometry.
Discrete Riemannian metrics, convexification, and duality
Let’s now assume that is planar. We want to show that . First, let’s restrict ourselves to vertex weighted metrics on . Given any non-negative weight function , we can define the length of a path in by summing the weights of vertices along it: . Then we can define a vertex-weighted shortest-path pseudo-metric on in the natural way
where is the set of all u-v paths in . We also have the nice relationship
So if we define
then by (1), we have .
Examples. Let’s try to exhibit weights for two well-known examples: the grid, and the complete binary tree.
For the grid, we can simply take for all . Clearly . On the other hand, a random pair of points in the grid is apart, hence . It follows that , as desired.
For the complete binary tree with root , we can simply put and for . (Astute readers will guess the geometrically decreasing weights are actually the optimal choice.) In this case, , while all the pairs on opposite sides of the root have . It again follows that . Our goal is to provide such a weight for any planar graph.