# Lecture 4: Conformal mappings, circle packings, and spectral geometry

In Lecture 2, we used spectral partitioning to rule out the existence of a strong parallel repetition theorem for unique games.  In practice, spectral methods are a very successful heuristic for graph partitioning, and in the present lecture we’ll see how to analyze these partitioning algorithms for some common families of graphs.

### Balanced separators, eigenvalues, and Cheeger’s inequality

Lipton and Tarjan proved that every planar graph has a negligibly small set of nodes whose remval splits the graph into two roughly equal pieces.  More specifically, every n-node planar graph can be partitioned into three disjoint sets $A,B,S$ such that there are no edges from $A$ to $B$, the separator $S$ has at most $O(\sqrt{n})$ nodes, and $|A|,|B| \geq n/3$.  This allows one to do all sorts of things, e.g. a simple divide-and-conquer algorithm gives a linear time $(1+\epsilon)$-approximation for the maximum independent set problem in such graphs, for any $\epsilon > 0$.

So there is a natural question of how well spectral methods do, for example, on planar graphs.  Spielman and Teng showed that for bounded-degree planar graphs, a simple recursive spectral algorithm recovers a partition $V=A \cup B$ of the vertex set so that $|E(A,B)| = O(\sqrt{n})$.  In other words, for bounded-degree planar graphs, spectral methods recover the Lipton-Tarjan separator theorem!  This is proved by combining Cheeger’s inequality with their main theorem.

Theorem [Spielman-Teng]: Every n-node planar graph with maximum degree $d_{\max}$ has $\displaystyle \lambda_2(G) = O\left(\frac{d_{\max}}{n}\right)$, where $\lambda_2(G)$ is the second eigenvalue of the combinatorial Laplacian on $G$.

Recall that we introduced the combinatorial Laplacian in Lecture 2.  If $G=(V,E)$ is an arbitrary finite graph, in this lecture it will make more sense to think about the Laplacian $\Delta$ as an operator on functions $f : V \to \mathbb R$ given by

$\displaystyle \Delta f(x) = \mathrm{deg}(x) f(x) - \sum_{y : xy \in E} f(y).$

If we define the standard inner product $\langle f,g\rangle = \sum_{x \in V} f(x)g(x)$, then one can easily check that for any such $f$, we have $\langle f, \Delta f\rangle = \sum_{xy \in E} |f(x)-f(y)|^2$.  In particular, this implies that $\Delta$ is a positive semi-definite operator.  If we denote its eigenvalues by $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$, then it is also easy to check that $\lambda_1 = 0$, with corresponding eigenfunction $f(x)=1$ for every $x\in V$.

Thus by standard variational principles, we have

$\displaystyle \lambda_2 = \min_{f \neq 0 : \sum_{x \in V} f(x)=0} \frac{\sum_{xy \in E} |f(x)-f(y)|^2}{\sum_{x \in V} f(x)^2}.$

Let us also define the Cheeger constant $h_G$.  For an arbitrary subset $S \subseteq V$, let

$\displaystyle h(S) = \frac{|E(S, \bar S)|}{\min(|S|,|\bar S|)}$,

note that this definition varies from the $h$ we defined in Lecture 2, because we will be discussing eigenfunctions without boundary conditions.  Now one defines $h_G = \min_{S \subseteq V} h(S)$.

Finally, we have the version of Cheeger’s inequality (proved by Alon and Milman in the discrete setting) for graphs without boundary.

Cheeger’s inequality: If $G=(V,E)$ is any graph with maximum degree $d_{\max}$, then

$\displaystyle \lambda_2(G) \geq \frac{h(G)^2}{2d_{\max}}.$

This follows fairly easy from the Dirichlet version of Cheeger’s inequality presented in Lecture 2.  Here’s a sketch:  Let $f : V \to \mathbb R$ satisfy $\Delta f = \lambda_2 f$, and suppose, without loss of generality, that $V_+ = \{ x : f(x) > 0 \}$ has $|V_+| \geq n/2$.  Define $f_+(x)=f(x)$ for $f(x) > 0$ and $f_+(x)=0$ otherwise.  Then $f_+|_B = 0$ for $B = V \setminus V_+$, so we can plug $f_+$ into the Dirichlet version of Cheeger’s inequality with boundary conditions on $B$.  For the full analysis, see this note which essentially follows this approach.  By examining the proof, note that one can find a subset $S \subseteq V$ with $h(S) \leq \sqrt{2 d_{\max} \lambda_2}$ by a simple “sweep” algorithm:  Arrange the vertices $V = \{v_1, v_2, \ldots, v_n\}$ so that $f(v_1) \leq f(v_2) \leq \cdots \leq f(v_n)$, and output the best of the $n-1$ cuts $\{v_1, \ldots, v_i\}, \{v_{i+1}, \ldots, v_n\}$.

So using the eigenvalue theorem of Spielman and Teng, along with Cheeger’s inequality, we can find a set $S \subseteq V$ with $h(S) \lesssim \sqrt{d_{\max}/n}$.  While this cut has the right Cheeger constant, it is not necessarily balanced (i.e. $\min(S, \bar S)$ could be very small).  But one can apply this algorithm recursively, perhaps continually cutting small chunks off of the graph until a balanced cut is collected.  Refer to the Spielman-Teng paper for details.  A great open question is how one might use spectral information about $G$ to recover a balanced cut immediately, without the need for recursion.

### Conformal mappings and circle packings

Now we focus on proving the bound $\lambda_2(G) \lesssim d_{\max}/n$ for any planar graph $G$.  A natural analog is to look at what happens for the Laplace-Beltrami operator for a Riemannian metric on the 2-sphere.  In fact, Hersch considered this problem almost 40 years ago and proved that $\lambda_2(M) \lesssim 1/\mathrm{vol}(M)$, for any such Riemannian manifold $M$.  His approach was to first use the uniformization theorem to get a conformal mapping from $M$ onto $S^2$, and then try to pull-back the standard second eigenfunctions on $S^2 \subseteq \mathbb R^3$ (which are just the three coordinate projections).  Since the Dirichlet energy is conformally invariant in dimension 2, this almost works, except that the pulled-back map might not be orthogonal to the constant function.  To fix this, he has to post-process the initial conformal mapping with an appropriate Möbius transformation.

Unaware of Hersch’s work, Spielman and Teng derived eigenvalue bounds for planar graphs using the discrete analog of this approach:  Circle packings replace conformal mappings, and one still has to show the existence of an appropriate post-processing Möbius transformation.