\documentclass[11pt,epsf]{article}
\parindent 0in
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.409 The Behavior of Algorithms in Practice} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe: #4}{Lecture #1}}

\newcommand{\Kappa}{\kappa}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\parskip 1.5ex

\renewcommand{\baselinestretch}{1.25}

\begin{document}

\lecture{8}{March 7, 2002}{Dan Spielman}{Jan Vondr\'ak}

\section*{Eigenvalues of planar graphs}

In this lecture, we prove the following theorem by Spielman and
Shang-Hua Teng.

\begin{theorem}
For any planar graph $G$ on $n$ vertices,
$$ \lambda_2(G) \leq {8 \Delta \over n}.$$
\end{theorem}

Also, we have Mihail's extension of Cheeger's inequality:

\begin{theorem}
Let $G$ be a graph of maximum degree $\Delta$, $L$ its Laplacian matrix,
and $v$ a vector orthogonal to $j = (1,1,\ldots,1)$. Then
$$ \Phi(G) \leq \sqrt{2 \Delta {v^T L v \over v^T v}}.$$
(A cut with this ratio can be found by ordering
the vertices by the components of $v$.)
\end{theorem}

Combined with the bound on $\lambda_2$ for planar graphs, this yields
a cut of ratio
$$ \Phi \leq \sqrt{2 \Delta \lambda_2} \leq {4 \Delta \over \sqrt{n}}$$
for planar graphs.

In the following, we use a generalized characterization of $\lambda_2$.

\begin{lemma}[Embedding lemma.]
For any dimension $d \geq 1$,
$$ \lambda_2(G) = \min\{ {\sum_{(i,j)\in E}{||x_i - x_j||^2} \over
\sum_i{||x_i||^2}}: x_1, \ldots, x_n \in R^d, \sum_{i=1}^{n}{x_i} = 0 \}.$$
\end{lemma}

\begin{proof}
For $d=1$, this is the standard characterization
$$ \lambda_2(G) = \min_{\sum{x_i}=0} {\sum_{(i,j)\in E}{(x_i - x_j)^2}
\over \sum_i{x_i^2}}.$$

For $d \geq 1$, we can obviously achieve the same value by using only
one dimension. However, we don't gain anything either, because
$$ {\sum_{(i,j) \in E}{||x_i - x_j||^2} \over \sum_i{||x_i||^2}} =
{\sum_{k=1}^d \sum_{(i,j) \in E}{(x_{ik} - x_{jk})^2} \over
\sum_{k=1}^d \sum_i{x_{ik}^2}} \geq \min_k{\sum_{(i,j) \in E}
{(x_{ik} - x_{jk})^2} \over \sum_i{x_{ik}^2}}.$$
I.e., the minimum is achieved in one of dimensions as well.
\end{proof}

Now we prove the bound for planar graphs by finding a suitable
embedding of $G$ in $R^3$. Our starting point is Koebe's theorem
about "kissing disks".

\begin{figure}[!ht]
\begin{center}
\scalebox{0.5}{\includegraphics{lect8/koebe.eps}}
\end{center}
\end{figure}

\begin{theorem}
For any planar graph $G$ on $n$ vertices, there is a set of
interior-disjoint disks $\{D_1, D_2, \ldots, D_n\}$ in the plane,
such that
$$ (i,j) \in E \Longleftrightarrow D_i \cap D_j \neq \emptyset.$$
\end{theorem}

Using this representation as is (in $R^2$) wouldn't give a meaningful
bound on $\lambda_2$. Our approach is to lift it to a unit sphere
in $R^3$. If we obtain vectors such that $\sum_i{x_i} = 0$, we can
use the embedding lemma to bound $\lambda_2$. To lift the embedding,
we apply the {\em stereographic projection}.

\begin{definition}[Stereographic projection]
Consider a plane and a unit sphere touching the plane in its origin.
Call this point on the sphere the south pole, and the point on the
sphere farthest away from the plane the north pole.
For a point $x \in R^2$, consider the line passing through $x$ and
the north pole. Define $\pi(x)$ to be the other point $x'$ where this
line intersects the sphere.
\end{definition}

\begin{figure}[!ht]
\begin{center}
\scalebox{0.5}{\includegraphics{lect8/stereo.eps}}
\end{center}
\end{figure}

Note: This mapping is defined uniquely for each point in the plane.
Conversely, each point on the sphere is the image of exactly one
point, except the north pole. We can define the north pole to be
the image of {\em infinity} if we want to have a bijection.

Another property of the stereographic projection is that circles
in the plane are mapped onto circles on the sphere. (However, the
center of a circle is not necessarily mapped onto the center of
the corresponding circle on the sphere.) Thus we can use the projection
to lift our disk embedding $\{D_1, \ldots, D_n\}$ to obtain a disk
embedding $\{\pi(D_1), \ldots, \pi(D_n)\}$ on the sphere.
It still holds that $\pi(D_i) \cap \pi(D_j) \neq \emptyset$ if and
only if $(i,j)$ is an edge.

Let $x_i$ be the center of $\pi(D_i)$ on the sphere. It remains
to ensure that $\sum{x_i}=0$ but assume for now that this is true.
We have
$$ ||x_i|| = 1, \ \ \ \ \sum_{i=1}^{n}{||x_i||^2} = n.$$
Let $r_i$ be the radius of the cap $\pi(D_i)$, measured in a straight
line from $x_i$ to the boundary of $\pi(D_i)$. If $(i,j) \in E$,
the two caps touch, and therefore
$$ ||x_i - x_j||^2 \leq (r_i + r_j)^2 \leq 2(r_i^2 + r_j^2).$$
On the other hand, the caps are interior-disjoint and the sum of their
areas does not exceed the area of the sphere, therefore $\sum{\pi r_i^2}
\leq 4 \pi$.
$$ \sum_{(i,j) \in E}{||x_i-x_j||^2} \leq 2 \sum_{(i,j) \in E}{(r_i^2
+ r_j^2)} \leq 2 \sum_i{d_i r_i^2} \leq 8 \Delta.$$

For the second eigenvalue, we get
$$ \lambda_2(G) \leq {\sum_{(i,j) \in E}{||x_i-x_j||^2} \over
\sum_i{||x_i||^2}} \leq {8 \Delta \over n}.$$

Finally, we show how to satisfy the condition $\sum{x_i} = 0$.
We have some freedom in our choice of the projection $\pi$.
First, we can expand the plane embedding by a constant factor.
We can also choose where the plane touches the unit sphere.

Define $D^{\beta}: R^2 \rightarrow R^2$ as an expansion in the plane
by a factor $\beta > 0$:
$$ D^{\beta}(x) = \beta x.$$

Define $\pi_z: R^2 \rightarrow S^2$ as the stereographic projection
such that the origin of the plane coincides with point $z$ on the sphere.

Our goal is to use Brouwer's fixed point theorem.

\begin{theorem}
Let $B$ be the unit ball in $R^3$ and $\Phi: B \rightarrow B$
any continuous function. Then
$$ \exists x \in B; \ \ \Phi(x) = x.$$
\end{theorem}

\begin{corollary}
If $\Phi: B \rightarrow B$ is continuous and for any $x \in S^2$,
$\Phi(x) = x$, then
$$ \exists x \in B; \ \ \Phi(x) = 0.$$
\end{corollary}

This follows easily from Brouwer's theorem, because if there is
a continuous function $\Phi$ which is identity on $S^2$ and
doesn't map anything to $0$, then
$$ \Psi(x) = -{\Phi(x) \over ||\Phi(x)||} $$
would be a continuous function without any fixed point.

Now we define a mapping $f_\alpha: S^2 \rightarrow S^2$, for any
$\alpha \in B$. For $\alpha = 0$, we define
$$ f_0(z) = z.$$
For $0 < ||\alpha|| < 1$, we define
$$ f_\alpha(z) = \pi_{\alpha/||\alpha||}(D^{1-||\alpha||}
(\pi_{\alpha/||\alpha||}^{-1}(z))). $$
Finally, for $||\alpha|| = 1$,
$$ f_\alpha(-\alpha) = -\alpha $$
and
$$ f_\alpha(z) = \alpha $$
for $z \neq \alpha$.

Let the centers of caps $\pi(D_1), \ldots, \pi(D_n)$
be $x_1, \ldots, x_n$. Note that for a fixed $x_i$,
$f_\alpha(x_i)$ changes continuously depending on $\alpha$,
unless $\alpha$ approaches the antipode $-x_i$ on the boundary
of $B$. To avoid this singularity, we define
$$ \omega_i(\alpha) = \min\{{2 - ||\alpha - x_i|| \over \epsilon},1\}$$
and
$$ \Phi(\alpha) = {\sum_{i=1}^{n}{\omega_i(\alpha) f_{\alpha}(x_i)} \over
\sum_{i=1}^{n}{\omega_i(\alpha)}}.$$
Then $\Phi: B \rightarrow B$ is continuous, because whenever $\alpha$
approaches the antipode of some $x_i$, the factor $\omega_i(\alpha)$
annihilates the influence of $f_\alpha(x_i)$. By the corollary, there
exists $y \in B$ such that $\Phi(y) = 0$. It remains to choose
$\epsilon > 0$ small enough so that $||y - x_i|| < 2 - \epsilon$ for
all $i$. This is possible, because for $y$ very close to the boundary
of $B$, $f_y(x)$ maps everything very close to $y$ and therefore
$\Phi(y)$ cannot be zero unless $y$ is bounded away from the
boundary (by some constant depending on the configuration of the $x_i$'s).
It follows that $\forall i; \omega_i(y) = 1$ and
$$ \Phi(y) = {1 \over n} \sum_{i=1}^{n}{f_y(x_i)} = 0. $$
Therefore $\{f_y(x_1), \ldots, f_y(x_n)\}$ is our "centered"
embedding for which the embedding lemma can be applied.

\end{document}