4 Expander graphs and the mixing lemma

This chapter follows Swastik Kopparty, Lecture 2: Expander Graphs, Mixing lemma and Applications to randomness, Topics in Pseudo-randomness and Complexity Theory (Spring 2018), Rutgers University; scribed by Danny Scheinerman and Harsha Tirumala.

Throughout, \(G\) is a \(d\)-regular simple graph on \(n\) vertices.

Definition 42 Normalized adjacency matrix

✓

The normalized adjacency matrix of \(G\) is \(M = \frac{1}{d} A\), where \(A\) is the adjacency matrix. Since \(G\) is \(d\)-regular, \(M\) is the transition matrix of the simple random walk on \(G\).

Lemma 43

✓

\(M\) is symmetric, hence Hermitian, so the spectral theorem provides an orthonormal basis of eigenvectors \(v_1, \dots , v_n\) with real eigenvalues \(\lambda _1, \dots , \lambda _n\).

Lemma 44

✓

Every constant function is an eigenvector of \(M\) with eigenvalue \(1\): each vertex has exactly \(d\) neighbours, so averaging a constant over them returns the same constant.

Theorem 45

✓

Let \(G\) be connected and \(d\)-regular. Then every eigenvector of \(M\) with eigenvalue \(1\) is constant.

Proof ▶

Let \(f\) satisfy \(Mf = f\) and let \(m = f(v_0)\) be the maximum value of \(f\), attained at some vertex \(v_0\) since \(V\) is finite and nonempty. Because \(G\) is \(d\)-regular,

\[ f(v_0) = (Mf)(v_0) = \frac{1}{d} \sum _{u \sim v_0} f(u), \]

so \(\sum _{u \sim v_0} (m - f(u)) = d\, m - d\, f(v_0) = 0\). Each summand is nonnegative, hence every summand vanishes and \(f(u) = m\) for every neighbour \(u\) of \(v_0\). Propagating this along a walk, which exists between any two vertices since \(G\) is connected, gives \(f \equiv m\).

Lemma 46

✓

On a connected \(d\)-regular graph the eigenvalue \(1\) is simple: two distinct basis indices cannot both carry the eigenvalue \(1\), since their eigenvectors would both be nonzero constants and so could not be orthogonal.

Definition 47 Expander

✓

\(G\) is a \(\gamma \)-expander when every eigenvalue of \(M\) other than the top eigenvalue \(1\) is at most \(\gamma \) in absolute value. By 46 this excludes exactly one eigenvalue when \(G\) is connected.

Definition 48

✓

For vertex sets \(A, B \subseteq V\), \(e(A, B) = |\{ (a,b) \in E(G) \; :\; a \in A, b \in B\} |\) is the number of edges joining a vertex in \(A\) to a vertex in \(B\).

Theorem 49 Expander mixing lemma

✓

Let \(G\) be a connected \(d\)-regular \(\gamma \)-expander on \(n\) vertices and let \(A, B \subseteq V\) be two sets of vertices (possibly overlapping). Then

\[ \left| e(A,B) - \frac{d}{n} |A| |B| \right| \le \gamma \, d \sqrt{|A| |B|}. \]

Note that the estimate \(e(A,B) \approx \frac{d}{n}|A||B|\) is what one would expect for a random \(d\)-regular graph on \(n\) vertices.

Proof ▶

Let \(\mathbf{1}_A, \mathbf{1}_B : V \to \mathbf{R}\) be the indicator functions of \(A\) and \(B\), and write their expansions in the orthonormal eigenbasis as \(\alpha _i = \langle v_i, \mathbf{1}_A \rangle \) and \(\beta _i = \langle v_i, \mathbf{1}_B \rangle \). Since \(G\) is \(d\)-regular,

\[ e(A,B) = \sum _{i,j} \mathbf{1}_A(i) \mathbf{1}_B(j) A_{ij} = d \left\langle \mathbf{1}_A, M \mathbf{1}_B \right\rangle = d \sum _i \lambda _i \alpha _i \beta _i . \]

Let \(i_0\) be the index carrying the eigenvalue \(1\), which is unique by 46; its eigenvector is a constant \(c\) with \(n c^2 = 1\). Hence \(\alpha _{i_0} = c |A|\) and \(\beta _{i_0} = c |B|\), so the \(i_0\) term contributes

\[ d\, \lambda _{i_0} \alpha _{i_0} \beta _{i_0} = d\, c^2 |A| |B| = \frac{d}{n} |A| |B|, \]

which is exactly the main term. For the remaining terms, \(|\lambda _i| \le \gamma \) and Cauchy-Schwarz followed by Parseval give

\[ \left| \sum _{i \ne i_0} \lambda _i \alpha _i \beta _i \right| \le \gamma \sum _{i \ne i_0} |\alpha _i| |\beta _i| \le \gamma \Big( \sum _i \alpha _i^2 \Big)^{1/2} \Big( \sum _i \beta _i^2 \Big)^{1/2} = \gamma \sqrt{|A|}\sqrt{|B|} . \]

Multiplying by \(d\) gives the claim.