This write-up will be about expander graphs, an indispensable tool in computer science. Expanders are widely used in error-correcting codes, complexity theory, hashing and computer networks.
Definitions
Let $G=(V,E)$ be a graph. Let $S,T \subseteq V$. We define $E(S,T) := \{(u,v)\mid \{u,v\} \in E, u\in S, v\in T\}$: this is the edges $u\to v$ from $S$ to $T$. Let $e(S,T) = |E(S,T)|$. Note that if $S$ and $T$ have a non-empty intersection then we count the edges between $S$ and $T$ twice.
We define the edge boundary of a set $S \subseteq V$ as $\partial S := E(S,V\setminus S)$. The vertex boundary is the number of neighbors of $S$ that are not in $S$.
A graph is a $\varepsilon$-edge expander if all subsets $S \subset V$ such that $|S| \leq |V|/2$ satisfy:
$$ h(S) = \frac{|\partial S|}{|E(S,V)|} \geq \varepsilon $$
Intuitively, we can think of it as follows: a social network is a $1/2$ expander if for all groups of people, the number of friends outside of the group is at least $1/2$ the total number of friends of the group. We have a name for the largest $\varepsilon$ this definition works for: the isoperimetric number, or Cheeger constant.
$$ h(G) := \text{inf}_{S}[h(S)] $$
An adjacent definition, an $\varepsilon$-vertex expander is a graph where all $S \subset V$ with $|S|\leq |V|/2$ have $N(S) \geq \varepsilon |S|$. These two notions of expansion are combinatorial and well-motivated. Let's see an example.
Examples
Consider $K_n$. We can prove that it is a $1$-vertex expander (which is actually optimal) and a $\frac{1}{2} + O(1/n)$ edge expander. This is a good exercise that we will leave for the end.
Cycle graphs and Cayley graphs are interesting constructions of expanders.
Spectral Expansion
Beyond the combinatorial definitions, we can also talk about spectral expansion. Let $G$ be $d$-regular, and consider its normalized adjacency matrix: $A_G = A/d$. Let $\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_n$ be the spectrum of $A_G$. By the Perron-Frobenius Theorem we can show that:
- $\vec{1}$ is an eigenvector of $A_G$ with eigenvalue 1. This eigenvector is also called a Perron vector, because all its coordinates are strictly positive.
- $1 = \lambda_1 \geq \cdots \geq \lambda_n \geq -1$.
$G$ is a $\lambda$-spectral expander if:
$$ \lambda(G) := \max\{|\lambda_2|,|\lambda_n|\} \leq \lambda $$
We define the spectral gap of a graph as $1-\lambda_2$.
What does the spectrum of a graph have anything to do with its expansion properties? The answer is that they are closely related, as we will see in the following theorem:
Let $G$ be a $d$-regular graph with normalized adjacency matrix $A_G$ whose spectrum is $\lambda_1 \geq \cdots \geq \lambda_n$. Then, for all $S,T \subseteq V$, we have:
$$ \left|e(S,T)-\frac{d|S||T|}{n}\right|\leq \lambda(G)\cdot d\sqrt{|S|\cdot |T|} $$
Proof: We kick things off with an important observation:
$$ 1_S^T (d A_G) 1_T = e(S,T) $$
This is because $(d A_G) 1_T$ gives for every $v \in V$ the number of neighbors in $T$, and subsequently multiplying by $1_S$ only keeps $v \in S$.
Now, let us consider an orthonormal eigenbasis $\{v_1,...,v_n\}$ for $A_G$. We can write $1_S = \sum \alpha_i v_i$ and $1_T = \sum \beta_i v_i$ and then:
$$ 1_S^T (A_G) 1_T = \sum\limits_{i=1}^n\alpha_i v_i^T\left(\sum\limits_{i=1}^n \lambda_i v_i v_i^T\right)\sum\limits_{i=1}^n\beta_i v_i = \sum\limits_{i=1}^n \lambda_i \alpha_i \beta_i $$
because of orthonormality. Now, note that $\lambda_1 = 1$ and so $\alpha_1 = 1_S^T \frac{\vec{1}}{\sqrt{n}} = \frac{|S|}{\sqrt{n}}$. Similarly, $\beta_1 = 1_T^T \frac{\vec{1}}{\sqrt{n}} = \frac{|T|}{\sqrt{n}}$. So:
$$ 1_S^T (A_G)1_T = \frac{|S|\cdot |T|}{n} + \sum\limits_{i=2}^n \lambda_i \alpha_i\beta_i $$
Which implies, by the triangle inequality, that:
$$ \left|\frac{e(S,T)}{d}-\frac{|S|\cdot |T|}{n}\right| = \left|\sum\limits_{i=2}^n \lambda_i \alpha_i \beta_i\right| \leq \lambda(G)\sum\limits_{i=2}^n\left|\alpha_i\beta_i\right|\leq \lambda(G)\sqrt{|S|\cdot |T|} $$
which finally gives us the desired result. Note that $|S| = \sum\alpha_i^2$ and $|T| = \sum\beta_i^2$ and so by Cauchy-Schwarz we have:
$$ \left(\sum\alpha_i\beta_i\right)^2 \leq \left(\sum \alpha_i^2\right)\cdot\left(\sum\beta_i^2\right) = |S|\cdot |T| $$
This finishes the proof of the Expander Mixing Lemma. Next, we shall see some applications of it.
Applications of the Expander Mixing Lemma
To see why, consider any independent set $S$ and apply the expander mixing lemma with $T = S$. We have that $e(S,T) = 0$, so:
$$ \frac{|S|^2}{n} \leq \lambda |S| $$
which gives us the desired relationship.
If $G$ is a $d$-regular $\lambda$-expander with $\lambda < 1/3$, then its diameter (the largest distance between any two vertices) satisfies:
$$ \Omega(\log n/\log d) \leq \text{diam}(G) \leq O(\log n) $$