\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\newcommand{\handout}[5]{
\noindent
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in { {\bf Lectures on Expanders} \hfill Course Instructor: #2 }
\vspace{4mm}
\hbox to 5.78in { {\Large \hfill #5 \hfill} }
\vspace{2mm}
\hbox to 5.78in { {\em #3 \hfill #4} }
}
}
\end{center}
\vspace*{4mm}
}
\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe:
#4}{Lecture#1}}
\newtheorem{theorem}{Theorem}
\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}
%my custom commands
\newcommand{\norm}[1]{\left\Vert #1 \right\Vert}
\newcommand{\ltwo}[1]{\left\Vert #1 \right\Vert_2}
\newcommand{\lone}[1]{\left| #1 \right|_1}
\newcommand{\linf}[1]{\left| #1 \right|_{\infty}}
\newcommand{\innerp}[1]{\langle #1 \rangle}
\newcommand{\blah}{x\perp u,\norm{x}=1}
\newtheorem{subclaim}[theorem]{Subclaim}
\newcommand{\z}{\textcircled{z}}
\newcommand{\parn}[1]{\left( #1 \right)}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\f}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\parl}{\parallel}
\newcommand{\md}[1]{\left|#1\right|}
\newcommand{\ldju[2]}{\bigcup_{#1}^{#2}\hspace{-9mm\cdot}\hspace{7mm}}
\begin{document}
\lecture{ $1$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Introduction}
\subsection{Motivation}
We would like to build a family of graphs that are ``sparse'' but
``highly'' connected. Some conditions that we would want our graphs
have are
\begin{enumerate}
\item The graph should be computable in time polynomial in the number
of vertices
\item The graph should be edge-checkable in time poly logarithmic in
the number of vertices.
\item In the context of $d-$regular graphs, $A(x,i) = y$ if $y$ is the
$i^{th}$ neighbour of $x$, and this $A$ should be polynomial time in
its input length.
\end{enumerate}
\subsection{Graph Parameters}
{\bf Sparseness:}
As for the graphs being sparse, the graphs we are looking for
shall be $d$ regular, for ``small'' $d$, and thus property $3$ would
be applicable.
\bigskip
\noindent
{\bf Connectivity:}
A possible connectivity measure is the measure how much the graph
``expands''.
\begin{definition}\label{vertex_exp_defn}
A graph $G_n$ is said be a $(k,\alpha)$ vertex expander if for
all subsets $S$ of vertices such that $|S|\leq k$, the neighbourhood
of $S$, denotes by $\Gamma(S) \geq \alpha|S|$.
\end{definition}
This is a natural notion of connectivity or expansion that we would
want ($\alpha$ ``large'' $implies$ ``expands well''), but
unfortunately, checking if a graph is a $(k,\alpha)$ is $coNP$
complete! Hence we need a different notion of expansion.
\section{Spectral Expansion}
\subsection{Associated Eigenvalues}
Let $G(V,E)$ be a $d$-regular multigraph, where there could be more
than $1$ edge between vertices. This could be thought of as a graph
with non-negative integral weights, where the weight of edge $ij$
denotes the number of edges between $i,j$.
Let $A$ be the {\em normalised adjacency matrix} of $G$
$$
A_{ij} = \frac{\text{number of edges between }i,j}{d}
$$
$A$ is a real, symmetric, doubly stochastic matrix\footnote{rows and
columns entries are non-negative and add up to $1$}. And by the spectral
theorem, the eigenvalues of this matrix are real, and there exists an
eigenbasis. Let the eigenvalues be $\lambda_1, \lambda_2, \cdots,
\lambda_n$ such that $|\lambda_1|\geq |\lambda_2| \geq \cdots \geq
|\lambda_n|$
Suppose $\lambda$ is any eigenvalue of $A$ and $v$ an associated
eigenvector.
Let $|v_i| = \max_{1\leq j\leq n}|v_j|$
\begin{eqnarray*}
|\sum_{j=1}^n A_{ij}v_j| & = & |\lambda||v_i|\\
& \leq & \sum_{j=1}^n |A_{ij}||v_j| \\
& \leq & |v_i|\sum_{j=1}^n |A_{ij}| \\
& = & |v_i|
\end{eqnarray*}
Hence $|\lambda| \leq 1$
And since $A$ is a stochastic matrix, clearly $(1,1,\cdots, 1)$ is an
eigenvector whose eigenvalue is $1$. Speaking in terms of probability
distributions, it makes more sense to say that the uniform
distribution $u=\left(\frac{1}{n},\frac{1}{n},\cdots,
\frac{1}{n}\right)$ is an eigenvector with eigenvalue $1$.
Thus $\lambda_1 = 1$.
\subsection{Other Eigenvalues}
$\lambda_1 = 1$ for all graphs, we have to inspect the other
eigenvalues to see if they tell us anything about the graph's
expansion properties. Firstly, we need to see if any other
$|\lambda_i| = 1$.
\noindent
First let's examine if any $\lambda_i = 1$.
\begin{lemma}The dimension of the eigenspace of $1$ $=$ number of
connected components of $G$
\end{lemma}
\begin{proof}
Let $x\perp u$ and $Ax = x$. Let $x_i = \max x_j$, $X = \{k|x_k =
x_i\}$.
$$
\sum_{j=1}^{n}A_{ij}x_j = x_i = \sum_{j,A_{ij}\neq 0} A_{ij}x_j
$$
which is a convex combination of $x_j$'s. Thus $A_{ij}\neq 0
\implies x_i = x_j$, which implies no edges go out of the set
$X$. Thus $X$ is a component of $G$.
And if there are $k$ connected components, dimension of eigenspace of
$1$ is atleast $k$ (uniform distribution over that component is an
eigenvector). And since every connected component has only $u$ as its
eigenvector, the dimension of the eigenspace of $1$ is exactly $k$.
\end{proof}
Now for the case when $\lambda_i = -1$
\begin{lemma}
For a connected $d-$regular graph $G$,
$$
G \text{ is bipartite } \iff -1 \text{ is an eigenvalue}
$$
\end{lemma}
\begin{proof}
Look at the graph $G^2$, whose edge relation correspond to paths of
length $2$ in $G$. Note that the adjacency matrix of this graph has
to be $A^2$ and hence the eigenvalues of $G^2$ has to be
$\{\lambda_i^2\}_{i=1}^n$
If $G$ is connected and bipartite, $G^2$ has $2$ component, and thus
$G^2$ has an eigenvalue $1$ with multiplicity $2$. And since $G$ is
connected, the eigenvalue $1$ of $G$ has multiplicity $1$, which
implies $-1$ is an eigenvalue of $G$.
\medskip
Conversely. let $-1$ be an eigenvalue of $G$ and $x$ the eigenvector
chosen such that $\max x_j = \max |x_j| = x_i$(say).
And repeating the argument in the earlier lemma,
$$
\sum_{j=1}^n A_{ij}x_j = -x_i = \sum_{j,A_{ij}\neq 0}A_{ij}x_j
$$
which is a convex combination of $x_j$. And hence, $A_{ij}\neq 0
\implies x_j = -x_i$.
Now let $X =\{ k | x_k = x_i\}$. Since $x_j = x_i \implies A_{ij} =
0$, the induced subgraph on $X$ is empty.
Since the graph is connected, let $x_l$ be a vertex in $V \\ X$ that
is connected to some $x_m$ in $X$. And since it is connected to some
vertex in $X$, $A_{ml} \neq 0 \implies x_m = -x_i$
$$
\sum_j A_{lj}x_j = -x_l = x_i
$$
And this is possible only when $x_j = x_i$ wherever $A_{lj}\neq 0$,
which means all the neighbours of $x_m$ are in $X$ - the graph is
bipartite.
\end{proof}
Hence, if $G$ is connected, and not bipartite, $|\lambda_2|<1$. This
$|\lambda_2|$ is called the spectral expansion of $G$.
\begin{definition}
For $G$, a connected $d-$regular non-bipartite graph, the spectral
expansion of $G$ is $|\lambda_2| = \lambda_2(G)$
\end{definition}
We shall soon see that $1 - \lambda_2(G)$ is large $\implies$ good
vertex expansion.
\begin{theorem}
$$
\lambda_2(G) = \max_{x\perp u} \frac{\norm{Ax}_2}{\norm{x}_2} =
\max_{x\perp u} \frac{|\langle Ax,x \rangle|}{|\langle x,x \rangle|}
$$
\end{theorem}
\begin{proof}
Let $u=v_1, v_2, \cdots, v_n$ be an eigenbasis. For any $x\perp
u$,
\begin{eqnarray*}
x & = &\alpha_2 v_2 + \alpha_3 v_3 + \cdots \alpha_n v_n\\
\langle Ax , Ax \rangle & = &\sum_{i=2}^n \alpha_i^2 \lambda_i^2
\leq \alpha_2^2 \norm{x}_2
\end{eqnarray*}
and the equality is attained when $x$ is the eigenvector of $\lambda_2$
The proof of the other equality is exactly the same.
\end{proof}
\begin{fact}
$\linf{v} \leq \ltwo{v} \leq \lone{v} \leq \sqrt{n}\ltwo{v}$
\end{fact}
\section{Random Walks on Expanders}
\subsection{Mixing Time and Spectral Expansion}
Let $\pi$ be a probability distribution over the vertices. Since $A$
is a stochastic matrix, $A\pi$ is also a probabilistic
distribution\footnote{this is the probabilistic distribution over the
vertices after $1$ step is taken according to $\pi$}.
\begin{definition}
$G$ has mixing time $t(n)$ if for all probability distributions
$\pi$
$$
\linf{A^{t(n)}\pi - u} \leq \frac{1}{2n}
$$
\end{definition}
\noindent
\begin{theorem}
``Good Expanders have small mixing time''
\end{theorem}
\begin{proof}
Let $\lambda_2(G) = \lambda$ and $\pi$ be any probability
distribution.
$$
\pi = \alpha_1 u + \alpha_2 v_2 + \cdots \alpha_n v_n
$$
Note that $\innerp{\pi,u} = \frac{1}{n}$ and hence $\alpha_1 =
1$. Hence
\begin{eqnarray*}
A^l\pi - u &= &\alpha_2 \lambda_2^l v_2 + \cdots + \alpha_n
\lambda_n^l v_n\\
\therefore \ltwo{A^l \pi - u}^2 & = &\alpha_2^2 \lambda_2^{2l} + \cdots +
\alpha_n^2 \lambda_n^{2l}\\
& \leq & \lambda_2^{2l}\left(\alpha_2^2 + \cdots + \alpha_n^2\right)\\
& \leq & \lambda_2^{2l} \ltwo{\pi - u}^2
\end{eqnarray*}
And since $\ltwo{pi}^2 = \ltwo{u}^2 + \ltwo{u^{\perp}}^2$, we have
$\ltwo{pi}^2 \geq \ltwo{\pi - u}^2$.
Hence we now have,
$$
\linf{A^l\pi - u} \leq \ltwo{A^l\pi - u} \leq \lambda_2^l \ltwo{\pi}
\leq \lambda_2^l \leq \frac{1}{2n}
$$
Hence $l = \log_{\frac{1}{\lambda_2}}2n$
Thus for small $\lambda_2$, mixing time is small.
\end{proof}
\section{Undirected Graph Connectivity is in $RL$}
$$
UGAP = \{(G,s,t)| \exists s-t \text{ path in }G\}
$$
\begin{definition}
$RL$ is the class of languages $L$ that are accepted by a polytime
randomized logspace turing machine with onesided error.
\end{definition}
Note that the polynomial running time requirement is critical, since
we have a stream of random bits, the machine could run for much
longer. Randomized logspace machines running for more than polynomial
time arguably have more computational power than $RL$ machines.
\begin{theorem}\label{UGAP}
$UGAP\in RL$
\end{theorem}
We need some bounds before we get into the proof.
\subsection{Bounds on $\lambda_2(G)$}
Let $G$ be any arbitrary connected, non-bipartite regular
graph. Assuming that there are self loops on all the nodes of $G$,
$G^2$ will now be a regular, non-bipartite connected graph with all
its eigenvalues non-negative. Let the normalized adjacency matrix of
$G^2$ be $A$ and let $E$ be the multiset of edges.
\begin{eqnarray*}
\lambda_2(G^2) &= &\max_{\blah}\left|\innerp{Ax,x}\right|\\
&= &\max_{\blah}\left|\sum_{i,j}A_{ij}x_ix_j\right|\\
&= &\max_{\blah}\left|\sum_{(i,j)\in E} \frac{2}{d}x_ix_j\right|\\
&= &\max_{\blah}\left|\frac{1}{d}\sum (x_i^2 + x_j^2) -
\frac{1}{d}\sum (x_i - x_j)^2\right|\\
&= &\max_{\blah}\left|\frac{1}{d} d\norm{x}^2 - \frac{1}{d}\sum
(x_i - x_j)^2\right|\\
\therefore 1 - \lambda_2 &= &\min_{\blah}\left|\frac{1}{d}\sum_{(i,j)\in
E}(x_i - x_j)^2\right|
\end{eqnarray*}
Let $x$ be the optimal vector for the above equation. Since $x\perp
u$, let $00$, $G$ is an $\left(\alpha n,\frac{1}{(1-\alpha)\lambda^2 +
\alpha}\right)$ vertex expander.
\end{theorem}
\begin{proof}
Let $S\subseteq V$ such that $|S|\leq \alpha n$. Suppose $\pi$ is any
distribution over the vertices, it can be written as $u + u^\perp$.
$$
\innerp{\pi, \pi} = \frac{1}{n} + \ltwo{\pi -u}^2
$$
Also,
\begin{eqnarray*}
\innerp{\pi, \pi}& = & \sum_{i\in supp(\pi)}\pi_i^2 \\
& \geq &\frac{\left(\sum \pi\right)^2}{|supp(\pi)|}\ \ \ \ \ \ \ \text{ (Cauchy Schwarz)}\\
& = & \frac{1}{|supp(\pi)|}
\end{eqnarray*}
Suppose $\pi$ was the uniform distribution on $S$, then note that
$\innerp{\pi, \pi} = \frac{1}{|S|}$.
Hence,
$$
\ltwo{\pi -u}^2 = \frac{1}{|S|} - \frac{1}{n}
$$
Since $supp(A\pi) = \Gamma(S)$,
\begin{eqnarray*}
\frac{1}{|\Gamma(S)|} &\leq &\innerp{A\pi, A\pi} = \frac{1}{n} +
\ltwo{A\pi - u}^2\\
& \leq & \frac{1}{n} + \lambda^2 \ltwo{\pi - u}^2\\
& = & \frac{1}{n} + \lambda^2\left(\frac{1}{|S|} -
\frac{1}{n}\right)\\
\implies \frac{|S|}{|\Gamma(S)|} & \leq & \frac{|S|}{n} +
\lambda^2\left(1 - \frac{|S|}{n}\right)\\
& = & \frac{|S|}{n}\left(1 - \lambda^2\right) + \lambda^2\\
& \leq & \alpha\left(1 - \lambda^2\right) + \lambda^2
\end{eqnarray*}
Therefore,
$$
\frac{|\Gamma(S)|}{|S|} \geq \frac{1}{\alpha\left(1 - \lambda^2\right)
+ \lambda^2} = \frac{1}{\lambda^2\left(1 - \alpha\right) + \alpha}
$$
\end{proof}
\subsection{Lower Bounds on $\lambda$}
Theorem \ref{spec_vert} tells much more than an implication.
For any $d$ regular graph, the vertex expansion of this graph is
atmost $d$.
\begin{eqnarray*}
\implies \frac{1}{\alpha + \left(1-\alpha\right)\lambda^2} & \leq & d\\
\implies \lambda^2\left(1 - \alpha\right) & \geq & \frac{1}{d} - \alpha
\end{eqnarray*}
Taking $\alpha$ close to $0$, we see that $\lambda =
\Omega(\frac{1}{\sqrt{d}})$.
\noindent
Infact there are better bounds known, Alon and Bopanna show that
$$\lambda \geq \frac{2\sqrt{d-1}}{d} - o(1)$$
Ramanujam graphs get very close to this optimal\footnote{they have
$\lambda = \frac{2}{\sqrt{d-1}} - o(1)$}.
\section{Random Graphs as Expanders}
Instead of looking at general random graphs, we shall restrict
ourselves to bipartite graphs and show that a random bipartite graph
is a ``good'' {\em left expander}.
\begin{definition}
A bipartite multigraph $G(L\cup R,E)$ is a $(d,k,\alpha)$
left expander if every vertex on $L$ has degree $d$, and for all
subsets $S$ of vertices in $L$ such that $|S| \leq k$, $|\Gamma(S)|
\geq \alpha|S|$
\end{definition}
Random bipartite graphs are chosen in the following sense, for every
vertex $v\in L$ randomly pick $d$ vertices from $R$ with
repitition. For simplicity of notation, let us call the set of
possible multigraphs $\mathcal{G}_{n,d}$.
\begin{theorem}
For every $n$ and $d\leq n$, there exists an $\alpha > 0$ such that
random $G\in \mathcal{G}_{n,d}$ is a $(d,\alpha n, d-2)$ left
expander with probability greater than $\frac{1}{2}$
\end{theorem}
\begin{proof}
Let $S\subseteq L$, such that $|S|=k<\alpha n$, we shall estimate the
$\Pr_{G}[|\Gamma(S)|< (d-2)|S|]$.
For every vertex $v\in L$, we chose $d$ neighbours, which is $kd$
elements picked from $L$. Thus, we want to estimate the probability
that there are atleast $2k$ repititions. There are $\binom{kd}{2k}$
places where the collisions can occur and each collision with
probability $\frac{kd}{n}$.
$$
\therefore Pr_{G}[|\Gamma(S)|<(d-2)|S|] \leq \binom{kd}{2k}\left(\frac{kd}{n}\right)^{2k}
$$
Summing over all $S$,
\begin{eqnarray*}
\sum_{k=1}^{\alpha n} \binom{n}{k} \binom{kd}{2k}
\left(\frac{kd}{n}\right)^2k & \leq & \sum_{k=1}^{\alpha
n}\left(\frac{ne}{k}\right)^k
\left(\frac{kde}{2k}\right)^{2k}\left(\frac{kd}{n}\right)^{2k}\\
& = & \sum_{k=1}^{\alpha n}\left(\frac{kd^2e^3}{4n}\right)^k \\
& \leq & \sum_{k=1}^{\alpha n}\left(\frac{\alpha d^2 e^3}{4}\right)^k
\end{eqnarray*}
And clearly for $\alpha<\frac{1}{d^2e^3}$ this probability can be
bounded by half.
\end{proof}
\section{Explicit Constructions}
The earliest explicit constructions of expander graphs were given by
[Margulis,Gabber-Galil], [Lubotzky,Sarnak] but the contructions are
fairly complex, looks at certain subsets of matrix groups.
[Reingold,Vadhan,Wigderson] used ``zig-zag products'' to construct
expanders, we shall be looking at them in the next lecture. Gramov had
used this zig-zag products earlier, though the novelty is attibuted to
[RVW].
Zig-zag products seem to mimic the semi-definite over groups.
Alon et al gave another ``not-so-difficult'' construction for
expanders, infact he said something more.
\begin{theorem}[Alon/Roichman]
There exists a constant $c$ such that for every finite group $G$, a
random set of $c\log n$ elements define a ``good'' expander in the
Cayley graph on the vertices.
\end{theorem}
\newpage
\lecture{ $3$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
In this lecture we shall be discussing the paper ``'Entropy Waves',
the zig-zag produt and new constant degree expanders'' by Reingold,
Vadhan and Wigderson, which appeared in the Annals of Mathematics
$'02$.
\section{The Rotation Map}
Let $G$ be an $N$ vertex $D$ regular graph. The rotation map is a map
$Rot_G:[N]\times [D] \rightarrow [N]\times [D]$, defined as follows.
If $i^{th}$ edge of vertex $v$ is $w$, as a $j^{th}$ neighbour, then
$$
Rot_G(v,i) = (w,j)
$$
Note that this map is also an involution. This map defines the graph,
and we would want this to be efficient ($poly(\log N,\log D)$
computable, in this lecture).
\section{Graph Products}
We shall now inspect various graphs products possible and the
parameters of the graph.
\subsection{Powering}
Let $G$ be a $(N,D,\lambda)$ expander, given by the rotation map
$Rot_G$. Then its $i^{th}$ power, $G^t$ is given by the following
rotation map:
$$
Rot_{G^t}(v_0,(k_1, k_2,\cdots, k_t)) = (v_t,(l_t, \cdots, l_1))
$$
{\em if and only if} there exists $v_1,\ldots, v_{t-1}$ such that
\begin{eqnarray*}
Rot_G(v_0,k_1) & = &(v_1, l_1)\\
Rot_G(v_1,k_2) & = &(v_2, l_2)\\
&\vdots & \\
Rot_G(v_{t-1},k_t) &= &(v_t, l_t)
\end{eqnarray*}
\medskip
And easy to see that $Rot_{G^t}$ is efficiently computable, and infact
the adjacency matrix of $G^t$ is $A^t$. Hence, $G^t$ is a $(N,D^t,
\lambda^t)$ expander.
\subsection{Tensoring}
$G_1$ is a $(N_1, D_1, \lambda_1)$ expander, and $G_2$ is a $(N_2,
D_2, \lambda_2)$ expander and let $Rot_{G_1}$ and $Rot_{G_2}$ be the
corresponding rotation maps.
The rotation map of $G_1\otimes G_2$ is defined by moving parallel on
$G_1$ and $G_2$.
$$
Rot_{G_1\otimes G_2} \parn{(v,w),(i,j)} = \parn{(v',w'),(i',j')}
$$
{\em if and only if}
$Rot_{G_1}(v,i) = (v',i')$ and $Rot_{G_2}(w,j) = (w',j')$.
Now, it is easy to see that the normalized adjacency matrix of this
graph, $A_{G_1\otimes G_2} = A_{G_1} \otimes A_{G_2}$, the tensor
product of the corresponding matrices\footnote{each $i,j$-th entry of
$A_1$ is replaced by the block $(A_1)_{i,j} \cdot A_2$}
The eigenbasis will also be the tensor products of the eigenbases of
the two matrices, and hence the eigenvalues will be the products of
the eigen values. And since $1$ is an eigen value for both $A_1$ and
$A_2$, the second largest eigenvalues is $\max(\lambda_1, \lambda_2)$.
\medskip
Thus, $G_1\otimes G_2$ is a $\parn{N_1N_2, D_1D_2, \max(\lambda_1,
\lambda_2)}$ expander.
\bigskip
Both the products blows up the degree of the final graph, which is not
desired. We want a family of graphs with constant degree and good
spectral gap\footnote{$1 - \lambda(G)$}.
\section{The Zig-Zag Product}
Let $G_1$ be a $(N,D,\lambda_1)$ expander and $G_2$ be a
$(D,d,\lambda_2)$ expander, with rotation maps $Rot_{G_1}$ and
$Rot_{G_2}$
Define the the graph $G_1 \z G_2$ as follows:
\begin{itemize}
{\item $V(G_1\z G_2) = [N]\times [D]$, replace every vertex in $G_1$
by a cloud of vertices in $G_2$, since the degree of $G_1$ matches
with vertex size of $G_2$, this can be done.}
{\item An edge in $G_1\z G_2$ is defined by a three step walk, $1$
move in the $G_2$ cloud, take and edge of $G_1$ and move to another
cloud, $1$ move in the new cloud. More formally,
$$
\parn{(v,k),(w,l)} \in E[\parn{G_1\z G_2}]
$$
if, there exists numbers $k',l'$ such that
\begin{eqnarray*}
(k,k')&\in& E(G_2)\\
(l,l')&\in& E(G_2)\\
Rot_{G_1}(v,k')& = &(w,l')
\end{eqnarray*}
}
\end{itemize}
So $G_1\z G_2$ is a $\parn{ND,d^2,\lambda_3}$ expander.
\begin{theorem}[Zig-Zag Theorem]\label{zigzagthm}
For $G_1$ and $G_2$ considered above, $G_1\z G_2$ is a $\parn{ND, d^2,
\lambda_3}$ expander where,
\begin{enumerate}
\item $\lambda_3 \leq \lambda_1+\lambda_2 + \lambda_2^2$
\item If $\lambda_1 <1$ and $\lambda < 1$, then $\lambda_3 < 1$
\end{enumerate}
\end{theorem}
We shall prove this later.
\subsection{Intuition Behind this}
To be filled up soon
\section{A Constant Degree Expander Family}
Our base graph $H$ would be a $\parn{D^8, D, \lambda}$ expander for a
constant $D$, which we shall explicitly construct later.
The family $\{G_t\}$ is defined as follows:
\begin{eqnarray*}
G_1 & = & H^2\\
G_2 & = & H\otimes H\\
\forall t>2,\ \ \ G_t & = & \parn{G_{\ceil{\frac{t-1}{2}}} \otimes
G_{\floor{\frac{t-1}{2}}}}^2 \z H
\end{eqnarray*}
\begin{claim}
$G_t$ is a $\parn{D^{8t},D,\lambda_t}$ expander, where $\lambda_t =
\lambda + O(\lambda^2)$, and whose rotation map is computable in time
polynomial in $\parn{t,\log N,\log D}$ with $poly(t)$ queries to the
rotation maps in the recursion.
\end{claim}
\begin{proof}
The ambiguity is only in $\lambda$ of $G_2$, it's clear that the
vertex size of $G^t$ is $D^{8t}$ and that the parameters match for
zig-zag.
\medskip
$\lambda_1 = \lambda^2 \leq \lambda + c\lambda^2$, and $\lambda_2 =
\lambda \leq \lambda + c\lambda^2$, we shall now proceed by
induction.
Let $\mu_t = \max_{i} \lambda_i = \max(\lambda_t,\mu_{t-1})$. We know
that $\mu_1$ and $\mu_2$ are upper bounded by $\lambda +
c\lambda^2$. Assume by induction that $\mu_{t-1} \leq \lambda +
c\lambda^2$.
Now, $G_t = K \z H$, where $K$ is the chunk in the definition. Note
that $\lambda_k \leq \mu_{t-1}^2 $.
Hence by the Zig-Zag theorem, we know that
\begin{eqnarray*}
\lambda_t & \leq & \mu_{t-1}^2 + \lambda + \lambda^2\\
& \leq & (\lambda+c\lambda^2)^2 + \lambda + \lambda^2
\end{eqnarray*}
We want this to be less than $\lambda + c\lambda^2$ for some $c$. It's
easy to see that if $\lambda \leq \frac{1}{5}$, then $c=5$ is good
enough.
Thus we have a uniform family of constant degree expanders, with good
spectral gap.
\end{proof}
Also note that in the earlier lecture we showd that $\lambda \leq
\frac{2}{\sqrt{D}}$, and hence
$$
\lambda_t \leq \lambda + c\lambda^2 \leq \frac{2}{\sqrt{D}} +
\frac{4c}{D} \leq \frac{c}{\sqrt{D}}
$$
And thus $\lambda_t = O\parn{\frac{1}{(deg(G))^{1/4}}}$.
\subsection{An explicit construction for $H$}
Let $q = p^t$, some prime power, and $\f_q$ be the associated
field. Our graph $AP_q$ is going to have the vertex set $V = \f_q \times
\f_q$.
As for the edge set of the graph, for every vertex $(a,b)\in \f_q
\times \f_q$, define the set of vertices adjacent to $(a,b)$ as
$L_{a,b}$ where
$$
L_{a,b} = \{ (x,y) | y = ax - b\}
$$
And since $|L_{a,b}| = q$, we have a $q$ regular graph.
\begin{claim}
$AP_q$ is a $\parn{q^2, q, \frac{1}{\sqrt{q}}}$ expander.
\end{claim}
\begin{proof}
Let $M$ eb the normalized adjacency matrix of $AP_q$. $M^2$ is a $q^2
\times q^2$ matrix. And note that
\begin{eqnarray}
M^2_{(a,b),(c,d)} = \frac{1}{q^2}\left| L_{a,b} \bigcap L_{c,d}\right| \label{eqn1}
\end{eqnarray}
If $(x,y)$ is a common point, then
$$
\left(\begin{array}{cc}
a & -1 \\
c & -1
\end{array}\right) = \parn{\begin{array}{c} x \\ y\end{array}}
$$
When $a\neq c$, the matrix is of rank $1$ and hence by equation
\ref{eqn1} $$M^2_{(a,b),(c,d)} = \frac{1}{q^2}$$.
\noindent
Suppose $a=c$, if $b\neq d$, there are no solutions and hence
$M^2_{(a,b),(c,d)} = 0$.
\noindent If $a=c$ and $b=d$, there are $q$ points in
common and hence $M^2_{(a,b),(c,d)} = \frac{1}{q}$
Thus the $M' = q^2M^2$ has the following form
$$
M' = \parn{\begin{array}{cccc}
qI_q & J_q & \cdots & J_q\\
J_q & qI_q& \cdots & J_q\\
\vdots& & \ddots & \\
J_q & \cdots & J_q & q_Iq
\end{array}}
$$
or in other words,
$$
M' = \parn{I_q\otimes qI_q + (J_q - I_q)\otimes J_q}
$$
where $J_q$ is the $q\times q$ matrix with every entry being a $1$.
The only eigenvalue of $I_q\otimes qI_q$ is $q$.
As for the other sum, $J_q - I_q$ has eigenvalue $q-1$ with
multiplicity $1$ and $-1$ with multiplicity $q-1$.
And $J_q$ has eigenvalue $q$ with multiplicity $1$ and $-1$ with
multiplicity $q-1$. Hence $(J_q - I_q)\otimes J_q$ has eigen value
$q(q-1)$ with multiplicity $1$, $0$ with multiplicity $q(q-1)$ and
$-q$ with multiplicity $q-1$.
Hence $M'$ has eigenvalue $q^2$ with multiplicity $1$, $q$ with
multiplicity $q(q-1)$ and $0$ with multiplicity $q-1$.
Hence, clearly, the second largest eigenvalue of $M'$ is atmost $q$,
and hence the second largest eigenvalue of $M$ is atmost $\frac{1}{\sqrt{q}}$
\end{proof}
Now let $AP_q^1 = AP_q \otimes AP_q$, which gives a $\parn{q^4, q^2,
\frac{1}{\sqrt{q}}}$ expander.
Define
$$
AP_q^i = AP_q^{i-1}\z AP_q
$$
And then we have the following claim, which is easy to prove.
\begin{claim}
$AP_q^i$ is a $\parn{q^{2(i+1)},q^2, \frac{2i}{\sqrt{q}}}$ expander.
\end{claim}
And with this, if we were to choose $i=7$, and $q>70^2$, we have a
$H=AP_{5000}^7$ as our $(D^8,D,\frac{1}{5})$ expander.
\newpage
\lecture{ $4$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Overview}
We saw that the zig-zag product gave us a uniform family of
expanders. In the next two lectures we shall prove Reingold's
Theorem.
First let us look at the rotation map of the zig-zag product as an
algorithm.
\medskip
\noindent
$
Rot_{G_1 \z G_2}:
$
Input: $\parn{(v,k),(i,j)}$
\begin{eqnarray*}
(k',i')&:= &Rot_{G_2}(k,i)\\
(w,l')& := & Rot_{G_1}(v,k')\\
(l,j')& := & Rot_{G_2}(l',j)
\end{eqnarray*}
\indent
Output: $\parn{(w,l),(j',i')}$
\medskip
\noindent
Notice that this is a logspace algorithm and requires just $O(1)$
extra space apart from storing the $4$ vertices in consideration; this
would crucial in Reingold's proof.
\section{Proof of the Zig-Zag Theorem (\ref{zigzagthm})}
We shall prove only one of the results stated in the previous
lecture.
We have to study the second largest eigenvalue of $G_1\z G_2 = G$, for
which we need to look at the normalized adjacency matrix of $G$. Let
the normalised adjacency matrix of $G_2$ be $A$, and let $P$ be a
permutation matrix defining the rotation map of $G_1$.
Every edge of $G$ consists of a three step walk, the first one being a
walk in one of the $v$ clouds that are expanded to a $G_2$. Thus that
step can be represented by the matrix $B = I_N \otimes A$.
Thus the transition matrix of $G$ is simply $Z = BPB$.
In order to analyse the spectral gap of $Z$, let $f\in \R^{ND},
\ltwo{f} = 1,f\perp 1_{ND}$. We want to show that
$$
\md{\innerp{f,Zf}} \leq \lambda_1 + \lambda_2 + \lambda_2^2
$$
Let $f = f^\parl + f^\perp$, where $f^\parl$ is a vector such that
$$
f^\parl_{(v,i)} = \frac{1}{D}\sum_{j=1}^D f(v,j) = \alpha_v
$$
which makes it locally uniform in each cloud $G_2$, hence $Bf^\parl =
f^\parl$. And, it also ensures that
$$
\sum_{v,i}f^\parl_{(v,i)} = \sum_{v,j} f_{(v,i)} = 0
$$
and hence $f^\parl$ and $f^\perp$ are orthogonal to $1_{ND}$.
Note that since $BPB$ is symmetric, $\innerp{f^\perp,BPBf^\parl} =
\innerp{f^\parl,BPBf^\perp}$. We then have,
\begin{eqnarray*}
\md{\innerp{f,BPBf}} & = &\md{\innerp{f^\parl,BPBf^\parl} +
2\innerp{f^\parl,BPBf^\perp} + \innerp{f^\perp, BPBf^\perp}}\\
& \leq & \md{\innerp{f^\parl,BPBf^\parl}} +
2\md{\innerp{f^\parl,BPBf^\perp}} + \md{\innerp{f^\perp,
BPBf^\perp}}\\
& = & (1) + (2) + (3)
\end{eqnarray*}
where $(1) = \md{\innerp{f^\parl,BPBf^\perp}}, (2) =
2\md{\innerp{f^\parl,BPBf^\perp}},(3) = \md{\innerp{f^\perp, BPBf^\perp}} $
\subsection*{Bounding $(1)$}
\begin{eqnarray*}
(1) & = & \md{\innerp{f^\parl, BPBf^\parl}}\\
& = & \md{\innerp{Bf^\parl, PBf^\parl}}\\
& = & \md{\innerp{f^\parl, Pf^\parl}}
\end{eqnarray*}
Now
\begin{eqnarray*}
\innerp{f^\parl,Pf^\parl} & = &
\sum_{(v,i)}\sum_{(w,j)}P_{(v,i),(w,j)}f^\parl_{(v,i)}f^\perp_{(w,j)}\\
& = & \sum_{(v,i)}\sum_{(w,j)}P_{(v,i),(w,j)}\alpha_v \alpha_w\\
& = & \sum_{(v,w)\in E} D\alpha_v \alpha_w
\end{eqnarray*}
And if we were to choose $g =
\parn{\sqrt{D}\alpha_{v_1},\sqrt{D}\alpha_2,\cdots,\sqrt{D}
\alpha_{v_N}}$, the above sum is just $\innerp{g,Ag}$. Now $g \perp
1_N$ and $\ltwo{g} = \ltwo{f^\parl}$. Hence
$$
(1) = \md{\innerp{g,Ag}} \leq \lambda_1 \ltwo{g} = \lambda_1
\ltwo{f^\parl} \leq \lambda_1
$$
\subsection*{Bounding $(2)$}
Since $\sum_i f^\parl_{(v,i)} = \sum_i f_{(v,i)}$ for all $v$, it
forces that $\sum_i f^\perp_{(v,i)} = 0$, or $f^\perp_v \perp 1_D$,
the projection of $f^\perp$ on $v$.
And hence
\begin{eqnarray*}
\ltwo{Af^\perp_v} &\leq& \lambda_2 \ltwo{f^\perp_v}\\
\implies \ltwo{Bf^\perp} &\leq& \lambda_2 \ltwo{f^\perp}\\
\end{eqnarray*}
Thus,
\begin{eqnarray*}
(2) & = & 2\md{\innerp{f^\parl,BPBf^\perp}}\\
& = & 2\md{\innerp{Bf^\parl,PBf^\perp}}\\
& = & 2\md{\innerp{f^\parl,PBf^\perp}}\\
& \leq & 2\ltwo{f^\parl} \ltwo{PBf^\perp}\\
& = & 2\ltwo{f^\parl} \ltwo{Bf^\perp}\\
& \leq & 2\lambda_2 \ltwo{f^\parl} \ltwo{f^\perp}
\end{eqnarray*}
\footnote{we used some other method in class first, but this seemed to
be an easier proof}By the AM-GM inequality,
$2\ltwo{f^\parl}\ltwo{f^\perp} \leq \ltwo{f^\parl}^2 +
\ltwo{f^\perp}^2 = \ltwo{f}^2$
And hence,
$$
(2) \leq \lambda_2 \ltwo{f} \leq \lambda_2
$$
\subsection*{Bounding $(3)$}
\begin{eqnarray*}
(3) & = & \md{\innerp{f^\perp,BPBf^\perp}}\\
& = & \md{\innerp{Bf^\perp, PBf^\perp}}\\
& \leq & \ltwo{Bf^\perp}\cdot\ltwo{PBf^\perp}\\
& = & \ltwo{Bf^\perp}^2\\
& \leq & \lambda_2^2 \ltwo{f}^2\\
& \leq & \lambda_2^2
\end{eqnarray*}
Thus, $\lambda(G_1\z G_2) \leq \lambda_1 + \lambda_2 + \lambda_2^2$ \qed
\section{Towards Reingold's Theorem}
\begin{theorem}[Reingold]\label{reingold}
$UGAP \in L$
\end{theorem}
Instead of looking at $s-t$ connectivity over general graphs, we shall
see that if the connected component containing $s$ was a
$\lambda$-spectral expander for some constant $\lambda<1$, then we can
check connectivity in $L$
First, we shall expand every vertex to a cycle, so that we get a $D$
regular graph.
Let $A$ be the adjacency matrix of $G$. We know that the mixing time
of $l = O(\log_{\frac{1}{\lambda}}N) = O(\log N)$. Thus for any
distribution over the connected component of $s$,
$$
\linf{A^le_s - u_s} \leq \frac{1}{2N}
$$
and in particular, $(A^le_s)_t \geq {1}{2N}$ if it is inside the
connected component. Hence, if there exists a path from $s$ to $t$,
the path is of length atmost $O(\log N)$.
But how does one enumerate all paths of length $O(\log N)$? The naive
method of remembering all vertices in the path would cost you
$O(\log^2 N)$ space. But since the graph is $D$ regular for some
constant $D$, it suffices to remember the out-edge number! Thus, the
space you need to try out all paths of length $O(\log N)$ would be
$O(\log D, \log N) = O(\log N)$, and this gives us the logspace
algorithm.
\bigskip
Reingold's theorem basically forces every graph $G$ to be transformed
of one of the above category.
For any $G = (N,D,\_)$ graph,
\begin{enumerate}
\item Pick $H$, a small $\parn{D^{16},D,\frac{1}{2}}$ expander.
\item $G_0 = G, G_i = \parn{G_{i-1}\z H}^8$
\item Thus, $G_i$ is a $\parn{ND^{16i},D^{16},\_}$ graph.
\end{enumerate}
Looking at the connected component containing $s$, turns out that
$$
\lambda(G_i) \leq \max[\lambda(G_{i-1})^2 ,\frac{1}{2}]
$$
And now, choosing $i=l=5\log N$ or so, we have
$$
\lambda \leq \parn{1 - \frac{1}{N^4}}^{2^l} \leq \frac{1}{2}
$$
and this reduces to the earlier case which is solvable in logspace.
The heart of the proof is to show that the rotation maps of $G_i$'s
can be computed in logspace.\footnote{though it seems like we need to
make $O(\log N)$ recursive calls, the amortized cost of computing
the rotation map is still $O(\log N)$}
\newpage
\lecture{ $5$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Overview}
We are on our way to showing that $UGAP$ or undirected graph
connectivity can be computed in logspace. Last class we saw that if
the connected component containing $s$ was an expander with some
constant positive spectral gap, then we can check connectivity it in
logspace.
We shall now see how we can ``expanderize'' graphs in logspace, and
thus solve $UGAP$ in logspace.
\section{Reingold's Algorithm}
\begin{enumerate}
\item Choose a graph $H$ that's a $\parn{D^{16},D,\frac{1}{2}}$
expander for some constant $D$.
\item Convert $G$ into a $D^{16}$ regular graph $G'$ with $N'=N^2$
many vertices. We shall elaborate on how to do this shortly.
\item Let $G_0 = G'$, and for all $i\geq 1$,
$$
G_i = \parn{G_{i-1}\z H}^8 = T_i(G',H)
$$
Thus, $G_i$ would be a $\parn{N^2D^{16i},D^{16},\_}$ expander.
\end{enumerate}
Now we have the following claims
\begin{claim}\label{rein_resp_conn}
If $S$ is a connected component of $G$,
$$
T_i(G'|_S,H) = T_i(G',H)|_{S\times [D^{16}]^i}
$$
\end{claim}
This basically tells us that the products respect connected
components, and hence connectivity.
\begin{claim}\label{rein_lambda_bound}
For all $i\geq 1$, if $\lambda_i$ is the second largest eigenvalue of
the connected component of $G_i$ containing $s$, then
$$
\lambda_i \leq \max\parn{\lambda_{i-1}^2,\frac{1}{2}}
$$
\end{claim}
With this claim, if we choose $i=O(\log N)=l$, we have
$$
\lambda_i = \parn{1 - \frac{1}{poly(N)}}^{2^i} < \frac{1}{2}
$$
And then our problem would reduce to the case we discussed last
lecture.
\medskip
\noindent
But we need one more crucial claim, that allow us to take the
products.
\begin{claim}\label{rein_rotmap}
$Rot_{G_l}$ can be computed in logspace from $Rot_{G'}$ and $Rot_H$
\end{claim}
\medskip
\noindent
So with the three claims, the algorithm is complete and we are done by
just applying the algorithm discussed last class for constant spectral
gap!
\subsection{Converting $G$ to a $D^{16}$-regular graph $G'$}
Let the vertex set of $G'$ be $[N]\times [N]$.
$$
Rot_{G'}: \parn{[N]\times [N]}\times [D^{16}] \rightarrow
\parn{[N]\times [N]}\times [D^{16}]
$$
is defined as follows
\begin{itemize}
{\item For all $(v,w)\in [N]\times [N]$,
$$
((v,w),1)\mapsto ((v,w'),2)
$$
where $w' = w+1$ if $w1$ and $w'=N$ when $w=1$,
}
{\item
If $(v,w)\in E$, then
$$
((v,w),3)\mapsto ((w,v),3)
$$
else
$$
((v,w),3)\mapsto ((v,w),3)
$$
}
{\item For all $3* 0$, if $k \geq 2\log|G| +
2\log\parn{\frac{1}{\epsilon}} + \log\parn{\frac{1}{\delta}}$,
$$
\Pr_x\left[\linf{Q_x - U} > \frac{\epsilon}{|G|}\right] \leq \delta
$$
\end{theorem}
\begin{proof} As usual, we shall work with the $L_2$ norm instead of
the $L_{\infty}$ norm.
\begin{eqnarray*}
\linf{Q_x - U}^2 & \leq & \ltwo{Q_x - U}^2\\
& = & \sum_g \parn{Q_x(g) - \frac{1}{|G|}}^2\\
\therefore E_x\linf{Q_x - U}^2 & \leq & E_x\ltwo{Q_x - U}^2\\
& = & \sum_g E_x\parn{Q_x(g)^2 + \frac{1}{|G|^2} -
2Q_x(g)\frac{1}{|G|}}\\
& = & E_x\parn{\sum_g Q_x(g)^2} - \frac{1}{|G|}
\end{eqnarray*}
Note that the first term in the last line is the collision
probability. Hence, define $\chi_x(\bar{e},\bar{e'})$ as the indicator
random variable to check for collision, i.e,
$$
\chi_x(\bar{e},\bar{e'}) =
\begin{cases}
1 & \text{if }x_1^{e_1}\cdots x_k^{e_k} = x_1^{e'_1}\cdots x_k^{e'_k}\\
0 & \text{otherwise}
\end{cases}
$$
Hence,
\begin{eqnarray*}
E_x\parn{\sum_g Q_x(g)^2} & = & E_x\frac{1}{2^{2k}}
\sum_{e,e'}\chi(e,e')\\
& = & \frac{1}{2^{2k}} \sum_{e,e'}E_x[\chi_x(e,e')]\\
& = & \frac{1}{2^{2k}} \sum_{e,e'}\Pr_x[\chi_x(e,e')=1]
\end{eqnarray*}
Now, when $e=e'$, then $\Pr_x[\chi_x(e,e')=1]=1$. As for the other
case when $e\neq e'$, taking all the $e_i$ to one side we have
$\Pr_x[\chi_x(e,e')=1] = \frac{1}{|G|}$. And hence,
\begin{eqnarray*}
E_x\parn{\sum_g Q_x(g)^2} & = & \frac{1}{2^{2k}}\parn{\sum_{e=e'}1} +
\frac{1}{2^{2k}}\parn{\sum_{e\neq e'}\frac{1}{|G|}}\\
& = & \frac{1}{2^k} + \frac{2^{2k} - 2^k}{2^{2k}}\frac{1}{|G|}\\
& = & \frac{1}{|G|} + \frac{1}{2^k}\parn{1 - \frac{1}{|G|}}\\
\therefore E_x\parn{\linf{Q_x - U}^2} & \leq & \frac{1}{2^k}\parn{1 -
\frac{1}{|G|}}
\end{eqnarray*}
And now to estimate $\Pr_x[\linf{Q_x - U} > \frac{\epsilon}{|G|}]$, we
can use Markov's inequality and the result follows.
\end{proof}
\subsection{Towards Babai's Sampling Algorithm: The Cayley Graph}
Let $G = \innerp{S}$. The cayley graph $X(G,T)$ where $T = S \cup
S^{-1}\cup \{1\}$ has the vertex set as $G$. And $(x,y)$ is an edge in
the $X(G,T)$ if there exists a $g\in T$ such that $xg=y$.
Earlier we say the following eigenvalue bound
$$
\lambda_2 \leq 1 - \frac{1}{O(diam^2|G|^2)}
$$
In arbitrary graphs, one could have a very small diameter but the size
of the graph could be large (two complete graphs connected by a cut
edge, diameter is $3$ but size is large). But for Cayley graphs, the
additional structure ensure the following eigenvalue bound.
$$
\lambda_2 \leq 1 - \frac{1}{O(diam^2)}
$$
Babai achieves the random sampling by looking at the Cayley Graph as
an expander and taking a random walk on it. Cayley graphs aren't
really expander but they have a property that Babai called the {\em
Local Expansion Property}.
\begin{lemma}[Local Expansion Lemma]\label{lel_lemma}
Define $T^t$ to be the $t-$neighbourhood of $T$, the set of all
vertices reachable from $T$ by a path of length atmost $t$. Let $0<
\alpha < \frac{1}{2t+1}$, and $D\subseteq T^t$ such that $|D|\leq (1 -
2t\alpha)|G|$. Then there exists a $g \in S$ such that $|D\backslash
Dg| \geq \alpha|D|$
\end{lemma}
Note that if $t$ was the diameter of $X(G,T)$, then $T^t = G$. Taking
$\alpha = \frac{1}{4t}$, we then have for all $D\subseteq G, |D|\leq
\frac{|G|}{2}$, $|\Gamma(D)| \geq \parn{1+\frac{1}{4t}}|D|$, and this
actually gives us that $\lambda_2 \leq 1 - \frac{1}{diam^2}$.
We shall see the proof of this lemma and the sampling algorithm in the
next lecture.
\newpage
\lecture{ $7$}{V. Arvind}{V. Arvind}{Ramprasad Saptharishi}
\section{Recap}
Last class we wanted to show that the membership testing problem in
the blackbox group model is in $NP\cap coAM$, and showing it was in
$NP$ was done by construction of small circuits (by expanding
``cubes'') acting as a witness. To show that it is in $coAM$, we
needed to sample from the group; that was the focus of Babai's paper.
The result of Erd\"{o}s and R\'{e}nyi tells us that given a random set
of size $O(\log |G|)$ can be used to sample almost uniformly at random
from the group $G$. But this would first require to pick the set of
$O(\log|G|)$ elements, which is too costly.
When we noted that Babai then describes the Cayley graph and Lemma
\ref{lel_lemma} tells us that the Cayley Graph has decent expansion
properties, and we shall be exploiting this. As seen in some of our
earlier lecture, we shall analyse random walks on these Cayley
Graphs to help us achieve almost uniform sampling from $G$.
\section{Proof of Lemma \ref{lel_lemma}}
Suppose the lemma is not true, then for all $g\in S$, $|D\backslash
Dg| < \alpha|D|$.
\noindent
Now for $x,y\in G$,
\begin{eqnarray*}
D\setminus D_{xy} & \subseteq & (D\setminus D_y)\cup (D_y \setminus
D_{xy})\\
& = & (D \setminus D_y)\cup(D \setminus D_x)\cdot y\\
\therefore |D\setminus D_{xy}| &\leq &|D\setminus D_x| + |D\setminus
D_y|
\end{eqnarray*}
\noindent
Hence, for all $k$, $u\in T^k$,
$$
|D\setminus D_u| < k\alpha|D|
$$
Thus for $k=2t+1$,
$$
|D\setminus D_u|<|D|
$$
but this is possible only when $D_u$ contains some elements of $D$,
i.e $D\cap D_u \neq \phi \implies u \in D^{-1}D\subseteq
T^{2t}$ for all $u$, and hence $G = T^{2t}$.
Now lets count the number of pairs $(x,u)$ such that $x\in D, u\in G,
xu \in D$. For every $u\in G$, there exists an $x$ such that $xu\in D$
since $D\cap D_u \neq \phi$. Hence for $k=2t$,
\begin{eqnarray*}
|D \setminus D_u| &< &2\alpha t|D|\\
\implies |D\cap D_u| &> &(1 - 2\alpha t)|D|
\end{eqnarray*}
And since $|D\cap D_u|$ many $x$'s are possible for each $u$, the total number of
pairs is atleast $(1 - 2\alpha t)|D|\cdot|G|$.
And also clearly the number of pairs is less than $|D|^2$, which then
forces the contradiction on the size of $D$. \qed
\section{Local Expanders}
In order to study more on the ``local expanders'' we have the
following definition.
\begin{definition}
Let $X = (V,E)$ any undirected graph and let $Y$ be a vertex induced
subgraph of $X$. We say $Y$ is $\epsilon$ expanding subgraph of $X$
if for all $W \subseteq V(Y)$, $|\Gamma_X(W)| \geq (1+\epsilon)|W|$
\end{definition}
\begin{theorem}
If $G = \innerp{S}$ and $X = X(G,T), T = S\cup S^{-1}\cup\{1\}$ then
if $|T^t|\leq \frac{|G|}{2} \implies T^t$ is a $\frac{1}{4t}$
expanding subgraph of $X$, i.e
$$
\forall D\subseteq T^t, |\Gamma(D)| \geq \parn{1+\frac{1}{4t}}|D|
$$
\end{theorem}
\begin{proof}
Put $\alpha = \frac{1}{4t}$ in the earlier lemma and the theorem is done.
\end{proof}
Earlier we had shown that spectral expansion implied vertex
expansion. Here is a result in the other direction, we won't prove it
though.
\begin{theorem}[Alon's Eigenvalue Bound] Let $G$ be a $d-$regular
connected non-bipartite undirected graph such that for all
$U\subseteq V, |U|\leq \frac{|V|}{2}$, $|\Gamma(U)| \geq
(1+\epsilon)|U|$. Then
$$
\lambda_2(G) \leq \parn{d - \frac{\epsilon^2}{4+2\epsilon^2}}\frac{1}{d}
$$
\end{theorem}
And in the context of locally expanding subgraphs:
\begin{theorem}[Babai's Eigenvalue Bound]
If $Y$ is an $\epsilon-$expanding subgraph of $X$, then we have the
following bound for the largest eigenvalue of the adjacency matrix
(the non-normalized adjacency matrix) of $Y$
$$
\lambda_1(Y) \leq d - \frac{\epsilon^2}{4+2\epsilon^2}
$$
\end{theorem}
Now for random walks on these local expanders.
\begin{theorem}
Suppose we start at a random walk on $X$ from any vertex $v_0\in Y$,
then
$$
\Pr[\text{the random walk is confined to $Y$ for $l$ steps}] \leq
|V(Y)|e^{-\frac{\epsilon^2 l}{4 + 2\epsilon^2}\frac{1}{d}}
$$
\end{theorem}
\begin{proof}
Let $A$ be the adjacency matrix of $Y$, and $e_0 \in \R^{|V(Y)|}$,
the standard basis vector with $1$ at $v_0$ and $0$ everywhere
else. Assuming that the walk is completely confined in $Y$, the
transition matrix of the walk is $\frac{1}{d}A$.
Now, the probability that you are confined in $Y$ for $l$ steps is
precisely
$$
(1,1,\cdots, 1)^T\parn{\frac{1}{d}A}^le_0
$$
Since $A$ is a real symmetric matrix, we know by the spectral
theorem that there exists a real eigenbasis. Hence $A = C^TDC$ where
$C$ is an orthogonal matrix and $D$ is the diagonal matrix of
eigenvalues. Hence the probability of staying inside $Y$ for $l$
steps (let me call that value as $P(l)$)
\begin{eqnarray*}
P(l) & = & \frac{1}{d^l}\parn{CJ}^T\cdot D^l\cdot \parn{Ce_0}\\
& \leq & \ltwo{CJ}\cdot \lambda_1^l\ltwo{J}\\
& = & \parn{\frac{\lambda_1}{d}}^l|V(Y)|
\end{eqnarray*}
And now using Babai's eigenvalue bound, the theorem follows.
\end{proof}
The only other property we need the Cayley graph to satisfy is the
small diameter criteria. Then our random walk would sample almost
uniformly from $G$.
\begin{claim}
If $diam(G)>2t$, then $|T^t| \leq \frac{|G|}{2}$
\end{claim}
\begin{proof}
If $diam(G)>2t$, then we know that
\begin{eqnarray*}
G & \nsubseteq & \parn{T^t}^{-1}T^t\\
\implies \exists g & : & T^tg\cap T^t = \phi\\
\implies |T^t| & \leq & \frac{|G|}{2}
\end{eqnarray*}
\end{proof}
Now, suppose $diam(G)>2t$, we know that $|T^t|\leq \frac{|G|}{2}$ and
then, by our earlier theorem, $T^t$ is a $\frac{1}{4t}$ expanding
subgraph of $X(G,T)$. And then, the probability of the random walk
being confined to $T^t$ is upper bounded as follows
$$
P(l) \leq |G| e^{\frac{l}{(64t^2 + 2)|T|}}
$$
And when $l = (64t^2 + 2)|T|\parn{\log|G|}^2$, then $P(l)
\frac{1}{|G|}$ and this $l$ is polynomially bounded in $\log |G|$, so
we are in good shape to emulate the reachability lemma.
Define $R_1 = T$ and for inductive procedures, $C_i = R_1\cdots
R_i$. Suppose $G\subseteq T^{4i}$, we already have small diameter and
hence we are done.
Suppose $G\nsubseteq T^{4i}$, then $T^{2i}\leq \frac{|G|}{2}$. Do a
random walk for $l$ steps (for the suitable $l$ for $2i$) and add all
the elements visited to $R_{i+1}$.
With good probability, we have an $x \notin C_i^{-1}C_i$ and hence
$|C_{i+1}|\geq 2|C_i|$, the size doubles with each time. Hence with
little error, we would be reaching small diameter in $\log|G|$
steps.
The accumulated error, by the union bound, is upper bounded by
$\frac{poly(\log|G|)}{|G|}$ and we are in good shape. We can now use
Erd\"os and R\'enyi and we would be able to sample almost uniformly
from $G$.
\section{$MembershipTest \in coAM$}
Needs to be filled out, not sure of it myself.
\end{document}*