Expanders and the Mixing Lemma

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$.

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.

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$.

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:

Proof: We kick things off with an important observation:

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

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_i = 1_T^T \frac{\vec{1}}{\sqrt{n}} = \frac{|T|}{\sqrt{n}}$. So:

Which implies, by the triangle inequality, that:

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:

This finishes the proof of the Expander Mixing Lemma. Next, we shall see some applications of it.

Applications of the Expander Mixing Lemma

1. Let $\alpha(G)$ be the size of the largest independent set in a graph $G$. If $G$ is a $d$-regular $\lambda$-expander, then

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:

which gives us the desired relationship.

2. If $G$ is a $d$-regular $\lambda$-expander with $\lambda < 1/3$, then its diameter (the largest distance between any two vertices) satisfies: