\documentclass[12pt]{amsart}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\bf Z}}
%\usepackage{psfig}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\lecture{24}{December 1, 2004}{Madhu Sudan}{Victor Chen}
\section{Overview}
Today we examine the zig-zag product introduced by Reingold, Vadhan, and Wigderson \cite{RVW} and Capalbo, Reingold, Vadhan, and Wigderson \cite{CRVW}. The product leads to a remarkable constructioon of expander graphs needed in the Spiser-Spielman code. In addition, their works introduce a probabilistic viewpoint of expansion. In previous literature, the spectral techniques are used to analyze the expansion of expanders and often limited to nonbiparite graphs. This randomness notion of expansion enables them to construct a new family of expanders that beat the eigenvalue bound. Warning: this lecture is not self-contained and omits various proofs.
\section{Preliminaries}
\begin{define}
A $D$-regular graph $G=(V,E)$ is a $(K,A)$-expander if for every $S \subset V, |S| \leq K, |\Gamma(S)| \geq A|S|$.
\end{define}
When $D$ is constant and $A>1$, we consider $G$ a good expander. If $A \approx (1-\epsilon)D$, $G$ is considered an excellent expander. Recall that we need a family of expanders with $A > D/2$ in the Sipser-Spielman code. In \cite{CRVW}, a construction of a family of excellent, imbalanced bipartite expanders was given. \\
However, it is difficult to prove that graphs have good expansion using the above definition. Typically spectral techniques are employed.
\begin{define}
The normalized adjacency matrix $P$ of a $D$-regular graph $G$ is $\frac{1}{D}A$, where $A$ is the adjacency matrix of $G$.
\end{define}
%
By normalizing, this allows us to interpret $P$ as the transition matrix of a random walk on $G$. Note that $P$ is a real, symmetric matrix. From linear algebra, we know that it has $N$ eigenvalues, $\lambda_1 \geq \ldots \geq \lambda_N$, and $N$ orthogonal linearly independent eigenvectors $v_1,\ldots,v_N$, such that each eigenvector $v_i$ has eigenvalue $\lambda_i$. It is not hard to see that $v_1=(\frac{1}{N},\ldots,\frac{1}{N})$ and $\lambda_1=1$. \\
Now interpreting graphs in this framework, suppose that a particle starts at vertex $1$ and at each step, jumps to a random neighbor. How fast does the probability distribution converges to the uniform distribution? First, note that in a disconnected graph, it never converges to uniform because some vertices will never be visited. And in a graph with a sparse cut, the distribution also does not converge because some vertices will rarely be visited. So intuitively, we should expect that an expander with weak expansion rate has slow convergence rate whereas an excellent expander has fast convergence. This is formalized as follows.
Suppose all eigenvalues except $\lambda_1$ are less than $1/2$ and that the initial distribution is $\pi=(\pi_1,\ldots,\pi_N)$. Since the eigenvectors form an orthogonal basis, we can write
$\pi=v_1 + \sum_{i=2}^N \gamma_iv_i$. Then $P^t \pi= \lambda_1^t v_1 + \sum_{i=2}^N \lambda_i^t \gamma_i v_i$. Since $\lambda_1=1$, we see that $P^t \pi$ quickly converges to $v_1$, the uniform distribution, if all the other eigenvalues are small.
\section{RVW Result}
Let $G=(N,D)$, where $G$ is a $D$-regular graph on $N$ vertices and $H=(D,d)$, where $H$ is a $d$-regular graph on $D$ vertices. We write $\lambda(G)$ as the second largest eigenvalue of graph $G$. The zig-zag product is an operation that takes graphs $G$ and $H$ and produces a new graph $GzH$. Syntactically, the zig-zag product $GzH=(ND,d^2)$. Moreover, there exists a function $f(\cdot, \cdot)$ such that if
$\lambda(G)=\lambda_1 < 1$ and $\lambda(H)=\lambda_2 < 1$, then $\lambda(GzH) \leq f(\lambda_1, \lambda_2) < 1$. \\
We first describe how to construct a family of expanders from the zig-zag product then define the product itself.
let $H$ be a constant sized expander (which can be found in constant time by brute force). More formally,
there exists a constant $d_0$ such that for all $d \geq d_0$, there exists a constant $D_0$ such that for all $D \geq D_0$, there exists a graph $H=(D,d)$ with $\lambda(H) \leq 1/2$.
From $H$ we can obtain a family of expanders. Before we do so, let's recall the powering operation. If $G$ has transition matrix $P$, then for $t \geq 1$, $G^t$ is a multigraph corresponding to the transition matrix $P^j$. Note also the edges in $G^t$ correspond to walks of length exactly $t$ in $G$. Now, for some appropriate constant $j$, let $G_1=H^{2j}$. Iteratively, define $G_i=(G_{i-1} z H)^j$. Inductively, deg$(G_i)=d^j$ and $\lambda(G_i) \leq 1/2$ (with appropriate $j$). This iterative method provides a construction of good but not excellent expanders from scratch.\\
Now we describe the zig-zag product informally. The vertices of the zig zag product $GzH$ is $V(G) \times V(H)$. So we can imagine placing a copy of $H$ at each vertex $u$ of $G$, and these are the new vertices of the zig-zag graph. Furthermore, each node of $H$ indexes a neighbor of $u$. Pictorially, think of the underlying graph $G$ as colored red and each edge in a copy of $H$ as colored blue. Nodes $(u,i), (v,j)$ are connected in $GzH$ iff there is a path of length $3$ between the two nodes pictorially, where the first edge in the path is blue, second is red, and the third is blue.
Formally, the two nodes are connected iff there exists $i',j'$ such that $(i,i'),(j,j')$ are edges in $H$, such that the $i'$-th neighbor of $u$ is $v$ in $G$ and the $j'$-th neighbor of $v$ is $u$ in $G$.
%
\section{Third Notion of Expansion}
In \cite{CRVW}, a third notion of expansion is introduced. Graphs are viewed as entropy conductors. Recall that extractors, interpreted as a bipartite graph, have $k$ bits of entropy on the left set of vertices, each has $d$ edges (interpreted as $d$ seed bits), and the induced distribution on the right has min$(k+a, m)$ bits of entropy, $a>0$. A bipartite expander is such that for every set of at most $K$ vertices on the left, the set of neighbors on the right is at least $AK$ for some $A>0$. Write $K=2^k$ and $A=2^a$. Then similarly we can interpret expanders as taking a source with $k$ bits of entropy on the left with $d$ additional random bits and producing a distribution with $k+a$ bits of entropy, $a>0$. An excellent expander (the expansion rate is arbitrarily close to the degree) produces almost $k+d$ bits of entropy. This view of expanders as entropy conductors allows Capalbo et. al. to construct a family of excellent expanders, and this will be shown in the next lecture.
%
\begin{thebibliography}{99}
%
\bibitem{CRVW}
Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson.
Randomness conductors and constant-degree lossless expanders.
Proc. of STOC '02.
\bibitem{RVW}
Omer Reingold, Salil Vadhan, and Avi Wigderson.
Entropy Waves, the zig-zag product, and new constant-degree expanders.
\emph{Annals of Mathematics},
155(1), January 2001. Extended Abstract in Proc. of FOCS '00.
\end{thebibliography}
\end{document}