\usepackage{palatino} %my favourite font

        \hbox to \textwidth { {\bf #2}\hfill {\bf Computational Complexity }
        \hbox to \textwidth { {\Large \hfill #5  \hfill} }
        \hbox to \textwidth { {\em #3 \hfill #4} }

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


% my custom commands
\newcommand{\inparen}[1]{\left(#1\right)}             %\inparen{x+y}  is (x+y)
\newcommand{\inbrace}[1]{\left\{#1\right\}}           %\inbrace{x+y}  is {x+y}
\newcommand{\insquar}[1]{\left[#1\right]}             %\insquar{x+y}  is [x+y]
\newcommand{\inangle}[1]{\left\langle#1\right\rangle} %\inangle{A}    is <A>
\newcommand{\abs}[1]{\left|#1\right|}                 %\abs{x}        is |x|
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}        %\norm{x}       is ||x||
\newcommand{\super}[2]{#1^{\inparen{#2}}}             %\super{G}{i-1} is G^{(i-1)}
\newcommand{\setdef}[2]{\inbrace{{#1}\ : \ {#2}}}
\newcommand{\inrpdt}[2]{\left\langle{#1},{#2}\right\rangle}%\inrpdt{x}{y} is <x,y>.
\newcommand{\pderiv}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\bea}[1]{\begin{eqnarray*} #1 \end{eqnarray*}}

% Commands specific to this file
% TODO: Find the right way to typeset group index
\newcommand{\gpidx}[2]{\insquar{#1 : #2}}             %\gpidx{H}{K}   is [H : K]
\newcommand{\gpigs}[2]{\gpidx{\super{G}{#1}}{\super{G}{#2}}} %Group index of g super ...
\newcommand{\roundoff}[1]{\left\lfloor #1 \right\rceil}

% \newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

%for expected value
\newcommand{\Ex}{{\bf E}}

%for algorithms

%Dirac's notation

%ZigZag Product

\lecture{Expanders: Vertex and Spectral Expansion}{CS640}{Manindra Agrawal}{Ramprasad Saptharishi}

Last class we saw three very powerful and useful combinatorial
objects: extractors, expanders and pseudo-random generators. With the
promise that we shall get back to extractors and PRGs in a while, let
us go into expander graphs. 

\section{Two Notions of Expansion}

\subsection{Vertex Expansion}

Last class we defined a notion of expansion. The definition we saw
last time is called {\em vertex expansion}.\\

\index{expanders!vertex expansion}
A $d$-regular graph $G$ on $n$ vertices is called an
$(n,d,\epsilon)$-vertex expander  if for every subset $S$ of size less than
$n/2$, the number of edges going out of $S$ is atleast $\epsilon
d|S|.$ That is, $E(S,V\setminus S)\geq \epsilon d|S|.$\\

Another definition is what is known as the {\em spectral expansion}.

\subsection{Spectral Expansion}

Let $G$ be a $n$-vertex $d$-regular graph. Let $A$ be the normalized
adjacency matrix, which is $A_{ij} = \frac{1}{d}$ if $(i,j)$ is an
edge and $0$ otherwise; the usual adjacency matrix divided by $d$.

The reason we do this is that since $G$ is $d$-regular, each row has
exactly $d$ non-zero entries of value $\frac{1}{d}$ and so does each
column. Therefore, each row and column sum up to $1.$ And further,
this is a symmetric matrix. 

There is a theorem in linear algebra that states the following:
\begin{theorem}\index{linear algebra!spectral theorem}
Let $A$ be a symmetric matrix with real entries. Then there exists a
basis $\inbrace{v_1, v_2, \cdots, v_n}$ such that each $v_i$ is an
eigenvector with eigenvalue $\lambda_i$ which is real. And further,
the basis is orthonormal, that is $v_i\cdot v_j = 0$ if $i\neq j$ and
$v_i\cdot v_i = 1.$

And therefore, our normalized adjacency matrix has a set of
orthonormal eigenvectors as a basis. Without loss of generality, we
can assume that the eigenvalues are decreasing :
$\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_n.$

$\lambda_1 = 1.$
Firstly, we need to show that $1$ is infact an eigenvalue. That is
pretty straightforward to see. Consider the vector of all $1$s, which
is sometimes referred to as $\bar{1}.$ 

Note that $A\bar{1} = \bar{1}$ since each row of $A$ adds up to $1.$
Therefore $\bar{1}$ is an eigenvector corresponding to the eigenvalue
$1.$ We now need to show that all eigenvalues have to be at most
$1.$ \\

Let $\lambda$ be any eigenvalue and $x$ be the eigenvector
corresponding to $\lambda.$ Look at the product $Ax.$ Without loss of
generality, assume that the first coordinate of $x$ is the largest
entry in $x.$ Then we have
Ax & = & \lambda x\\
\implies (Ax)_1 & = & \lambda x_1
Now note that the LHS will merely be the average of some $d$
coordinates of $x$ and the average of $d$ coordinates can never be
larger than the maximum value. And hence, $\lambda \leq 1.$ Infact one
can slightly tweak the argument to show that $|\lambda| \leq 1.$

Therefore all eigenvalues lie between $1$ and $-1$; and $1$ is the
largest eigenvalue. 

The second largest eigenvalue of a graph $G$ is the second largest
eigenvalue in magnitude of the normalized adjacency matrix $A$ of $G.$
\lambda_2(G) = \max\inbrace{|\lambda_2|,|\lambda_n|}

With this, we can define our spectral expansion. 
\begin{definition}\index{expanders!spectral expansion}
A $n$-vertex $d$-regular graph $G$ is called a $(n,d,\lambda)$-spectral
expander if $\lambda = \lambda_2(G).$

The use of this notion of expansion is that it allows us to use linear
algebra to analyse such graphs and their properties. We shall soon see
that the two notions of expansion are essentially equivalent. To easy
the notation used there, we shall used {\em Dirac's Notations} for
vectors; it is more intuitive to understand in that setting. 

\section{Dirac's Notation}

Dirac's notation of representing vectors, inner products, outer
products is widely used in Physics and expecially in the setting of
quantum mechanics where equations start looking messy with ordinary
vectors and transpose etc. Dirac's notation cleans them up and it
makes it a lot easier to understand. 

\item A normal vector $v$ is written $\ket{v}$, pronounced as ``ket
$v$'', which is the column vector. And the row vector $v^T$ is written
as $\bra{v}$ and pronounced as ``bra $v$.'' \index{Dirac's notation!
bra,ket vectors}
\item In this setting, note that the usual inner product is just the
vector product $v^Tv$ which translates to $\bra{v}\ket{v}$ which is
``bra-ket (bracket) $v$.''\index{Dirac's notation!inner and outer products}
\item The outer-product $vv^t$ which gives an $n\times n$ matrix is
written as $\ket{v}\bra{v}.$ This is used less often than the inner
product but is very useful. For example, the adjacency matrix $E$ can
be expressed as 
E = \sum_{(u,v)\in \text{Edges}}\ket{u}\bra{v}
where $\bra{v}$ is the characteristic vector of $v$ that has $1$ in
the $v$-th position and $0$ everywhere else. 

This notation really cleans up a whole mess of arrow, or transposes or
dot-products etc. We shall see the power of this notation by using it
to prove the connection between vertex and spectral expansion. 

\section{Vertex Expansion $\Leftrightarrow$ Spectral Expansion}

The following theorem shows that the two notions of expansion are
essentially the same.

Vertex expansion $\Leftrightarrow$ Spectral Expansion
\item If $G$ was a $(n,d,\epsilon)$ vertex expander, then $G$ is also
a $(n,d,\lambda)$ spectral expander where $\lambda \leq 1 - (\epsilon^2/4).$
\item If $G$ was a $(n,d,\lambda)$ spectral expander, then $G$ is also
a $(n,d,\epsilon)$ vertex expander where  $\epsilon \geq (1 - \lambda)/2.$
If $\epsilon$ was large, then $\lambda$ will be small and vice-versa

We shall prove just the second part of the theorem. 
Let $G$ be a $(n,d,\lambda)$ expander. Let $S$ be any subset of
vertices such that $|S| \leq n/2.$ We want to estimate the number of
edges going out of $S.$ Let $T$ be the set of vertices that are not in
$S.$ We need to estimate $E(S,T).$

The first step is to write $E(S,T)$ as a product of
vectors/matrices. Let $u_S$ be the characteristic vector of $S$, the
vector which has a $1$ on exactly those coordinates that belong to
$S.$ In Dirac's notation, $\ket{u_S} = \sum_{i\in S}\ket{i}$ and
similarly $\ket{u_T}.$ Now look at the term $u_S^TAu_T$:
u_S^TAu_T  = \bra{u_S}A\ket{u_T}& = & \inparen{\sum_{i\in S}\bra{i}}A\inparen{\sum_{j\in
& = & \frac{1}{d}\inparen{\sum_{i\in S}\bra{i}}\inparen{\sum_{(u,v)\in
E}\ket{u}\bra{v}}\inparen{\sum_{j\in T}\ket{j}}\\
& = & \frac{1}{d}\sum_{(i,j)\in
E(S,T)}\bra{i}\ket{i}\bra{j}\ket{j} \qquad\text{(all other terms
become $0$)}\\
& = & \frac{1}{d}|E(S,T)|
Suppose $\inbrace{v_1, v_2, \cdots, v_k}$ is the orthonormal
eigenbasis of $A$, let 
\ket{u_S} & = &\sum_{i=1}^n \alpha_i \ket{v_i}\\
\ket{u_T} & = &\sum_{i=1}^n \beta_i \ket{v_i}
And therefore, we can calculate $\bra{u_T}A\ket{u_S}$ as
\bra{u_T}A\ket{u_S} & = & \inparen{\sum_{i=1}^n\alpha_i\bra{v_i}}\inparen{A(\sum_{j=1}^n\beta_j\ket{v_j})}\\
& =
& \inparen{\sum_{i=1}^n\alpha_i\bra{v_i}}\inparen{\sum_{j=1}^n\lambda_j\beta_j\ket{v_j}}\\
& = & \sum_{i=1}^n\alpha_i\beta_i\lambda_i\bra{v_i}\ket{v_i} \qquad \text{(since $i\neq
j \implies \bra{v_i}\ket{v_j} = 0$)}

We know that $\lambda_1 = 1$ and that $v_1 = \frac{1}{\sqrt{n}}\bar{1}
= \frac{1}{\sqrt{n}}\sum_{i=1}^n\ket{i}.$ And further, 
\bra{u_S}\ket{v_1} & = & \sum_{i=1}^n\alpha_i\bra{v_i}\ket{v_1}\\
                   & = & \alpha_1\\
\implies \frac{1}{\sqrt{n}}\sum_{i=1}^n\bra{u_S}\ket{i} & =
& \frac{|S|}{\sqrt{n}} = \alpha_1\\
\text{Similarly, }\frac{|T|}{\sqrt{n}} & = & \beta_1

\bra{u_S}A\ket{u_T} - \frac{|S||T|}{n} & =
&\sum_{i=2}^n \alpha_i\beta_i\lambda_i\\
\abs{\bra{u_S}A\ket{u_T} - \frac{|S||T|}{n}}
& \leq &\abs{\sum_{i=2}^n\alpha_i\beta_i\lambda_i}\\
  & \leq & \sum_{i=2}^n|\alpha_i||\beta_i||\lambda_i|\\
& \leq & \lambda \sum_{i=2}^n|\alpha_i||\beta_i|\\
& \leq & \lambda \sqrt{\sum_{i=2}\alpha_i^2}\sqrt{\sum_{i=2}\beta_i^2}

Now let us go back to the definition of $\ket{u_S}.$ We know that
$\norm{u_S}^2 = |S| = \bra{u_S}\ket{u_S}.$ Evaluating this as a linear
combination of eigenvectors, we have
|S| = \bra{u_S}\ket{u_S} & =
&\inparen{\sum_{i=1}^n\alpha_i\bra{v_i}}\inparen{\sum_{i=1}^n\alpha_i\ket{v_i}} =  \sum_{i=1}^n\alpha_i^2\\
\implies |S| - \alpha_1^2 &= &\sum_{i=2}^n\alpha_i^2\\
\implies \sum_{i=2}^n\alpha_i^2 & = & |S| - \frac{|S|^2}{n} =
|S|\inparen{\frac{n - |S|}{n}} = \frac{|S||T|}{n}\\
\text{Similarly }\sum_{i=2}^n\beta_i^2 & = & \frac{|S||T|}{n}

Hence the above equation becomes
\abs{\bra{u_S}A\ket{u_T} - \frac{|S||T|}{n}} &\leq& \lambda\frac{|S||T|}{n}\\
\implies \abs{E(S,T) - \frac{d|S||T|}{n}} & \leq &
\implies E(S,T) & \geq & \frac{d|S||T|}{n} - d\lambda\frac{|S||T|}{n}

From the definition of vertex expansion, we have
\frac{E(S,T)}{d|S|} = \epsilon & \geq & \frac{|T|}{n}\inparen{1 -\lambda}\\
& \geq & \frac{1}{2}\inparen{1 - \lambda} \qquad\text{( since $|S|\leq n/2$ and
therefore $|T|\geq n/2$)}

Therefore, any graph with spectral expansion $\lambda$ has vertex
expansion of $\frac{1}{2}\inparen{1 - \lambda}.$

In essence, both notions of expansion are equivalent. It is easier to
work with the spectral definition since it allows us to use a lot of
linear algebra techniques to analyze.