Robi Krauthgamer and I will give a series of lectures entitled “The strange geometries of computer science,” essentially every Monday of the trimester starting on Jan 24. Details of the first lecture follow.
We will begin with a simple spectral partitioning algorithm for graphs, based on the Cheeger-Alon-Milman inequality. Analysis of this algorithm rests on proving upper bounds for the smallest non-zero eigenvalue of the associated graph Laplace operator. Such bounds were obtained for compact surfaces by Hersch, and by Yang and Yau using conformal uniformization, and later for graphs by Spielman and Teng using a combinatorial analog (the Koebe-Andreev-Thurston circle packing theorems). This latter result yields a spectral approach to the classical Lipton-Tarjan separator theorem for planar graphs.
But what can be done when we are given a graph which has no conformal structure (e.g. cannot be drawn on a surface)? This leads to questions of Gromov and of Spielman and Teng on whether the conformal/spectral approach can be extended to more combinatorial settings. We will answer these questions using a form of “metric uniformization,” whereby we optimize some convex functional over all shortest-path metrics on a given graph (by varying the weights on the edges). Such optimizations will be an important reoccurring theme throughout the course.
Analysis of this optimization (via duality) will lead us to examine “area-minimizing” multi-flows in graphs, which we will study using some beautiful results of Leighton and Ajtai, Chvatal, Newborn, and Szemeredi on crossing numbers of graphs. Once the optimal metric is understood, we can use results from metric embedding theory to recover tight bounds on the smallest non-zero eigenvalue.
Finally, we will discuss how this technique extends to bounding the entire spectrum of the Laplacian (not just the smallest non-zero eigenvalue). We will end the lecture with a related question about controlling the spectrum of a graph by disjointly supported test functions; this question will be intimately related to an attempted resolution of the Unique Games Conjecture from approximation algorithms.
I will assume essentially no background beyond basic finite-dimensional linear algebra. See the lecture notes below for an idea of the level of the presentation.
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
Metric uniformization and spectral bounds for graphs