# Expanders and the Mixing Lemma

Themistoklis Haris

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

Definition

A graph is a

$\varepsilon$-edge expanderif 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**.

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

Definition

$G$ is a $\lambda$-spectral expander if

$\lambda(G) := \max\{|\lambda_2|,|\lambda_n|\} \leq \lambda$We define the

spectral gapof 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:

Theorem

Expander Mixing Lemma

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:

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

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

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

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