# Expander mixing lemma

The expander mixing lemma intuitively states that the edges of certain $d$-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets $S$ and $T$ is always close to the expected number of edges between them in a random $d$-regular graph, namely ${\frac {d}{n}}|S||T|$.

## d-Regular Expander Graphs

Define an $(n,d,\lambda )$-graph to be a $d$-regular graph $G$ on $n$ vertices such that all of the eigenvalues of its adjacency matrix $A_{G}$ except one have absolute value at most $\lambda .$ The $d$-regularity of the graph guarantees that its largest absolute value of an eigenvalue is $d.$ In fact, the all-1's vector $\mathbf {1}$ is an eigenvector of $A_{G}$ with eigenvalue $d$, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of $G$ in absolute value.
If we fix $d$ and $\lambda$ then $(n,d,\lambda )$-graphs form a family of expander graphs with a constant spectral gap.

## Statement

Let $G=(V,E)$ be an $(n,d,\lambda )$-graph. For any two subsets $S,T\subseteq V$, let $e(S,T)=|\{(x,y)\in S\times T:xy\in E(G)\}|$ be the number of edges between S and T (counting edges contained in the intersection of S and T twice). Then
    $\left|e(S,T)-{\frac {d|S||T|}{n}}\right|\leq \lambda {\sqrt {|S||T|}}\,.$

### Tighter Bound

We can in fact show that
    $\left|e(S,T)-{\frac {d|S||T|}{n}}\right|\leq \lambda {\sqrt {|S||T|(1-|S|/n)(1-|T|/n)}}\,$
using similar techniques.

### Biregular Graphs

For biregular graphs, we have the following variation, where we take $\lambda$ to be the second largest eigenvalue.
Let $G=(L,R,E)$ be a bipartite graph such that every vertex in $L$ is adjacent to $d_{L}$ vertices of $R$ and every vertex in $R$ is adjacent to $d_{R}$ vertices of $L$. Let $S\subseteq L,T\subseteq R$ with $|S|=\alpha |L|$ and $|T|=\beta |R|$. Let $e(G)=|E(G)|$. Then
    $\left|{\frac {e(S,T)}{e(G)}}-\alpha \beta \right|\leq {\frac {\lambda }{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta (1-\alpha )(1-\beta )}}\leq {\frac {\lambda }{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta }}\,.$
Note that ${\sqrt {d_{L}d_{R}}}$ is the largest eigenvalue of $G$.

## Proofs
### Proof of First Statement

Let $A_{G}$ be the adjacency matrix of $G$ and let $\lambda _{1}\geq \cdots \geq \lambda _{n}$ be the eigenvalues of $A_{G}$ (these eigenvalues are real because $A_{G}$ is symmetric). We know that $\lambda _{1}=d$ with corresponding eigenvector $v_{1}={\frac {1}{\sqrt {n}}}\mathbf {1}$, the normalization of the all-1's vector. Define $\lambda ={\sqrt {\max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}}}$ and note that $\max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}\leq \lambda ^{2}\leq \lambda _{1}^{2}=d^{2}$. Because $A_{G}$ is symmetric, we can pick eigenvectors $v_{2},\ldots ,v_{n}$ of $A_{G}$ corresponding to eigenvalues $\lambda _{2},\ldots ,\lambda _{n}$ so that $\{v_{1},\ldots ,v_{n}\}$ forms an orthonormal basis of $\mathbf {R} ^{n}$.
Let $J$ be the $n\times n$ matrix of all 1's. Note that $v_{1}$ is an eigenvector of $J$ with eigenvalue $n$ and each other $v_{i}$, being perpendicular to $v_{1}=\mathbf {1}$, is an eigenvector of $J$ with eigenvalue 0. For a vertex subset $U\subseteq V$, let $1_{U}$ be the column vector with $v^{\text{th}}$ coordinate equal to 1 if $v\in U$ and 0 otherwise. Then,
    $\left|e(S,T)-{\frac {d}{n}}|S||T|\right|=\left|1_{S}^{\operatorname {T} }\left(A_{G}-{\frac {d}{n}}J\right)1_{T}\right|$.
Let $M=A_{G}-{\frac {d}{n}}J$. Because $A_{G}$ and $J$ share eigenvectors, the eigenvalues of $M$ are $0,\lambda _{2},\ldots ,\lambda _{n}$. By the Cauchy-Schwarz inequality, we have that $|1_{S}^{\operatorname {T} }M1_{T}|=\langle 1_{S},M1_{T}\rangle \leq \|1_{S}\|\|M1_{T}\|$. Furthermore, because $M$ is self-adjoint, we can write
    $\|M1_{T}\|^{2}=\langle M1_{T},M1_{T}\rangle =\langle 1_{T},M^{2}1_{T}\rangle =\left\langle 1_{T},\sum _{i=1}^{n}M^{2}\langle 1_{T},v_{i}\rangle v_{i}\right\rangle =\sum _{i=2}^{n}\lambda _{i}^{2}\langle 1_{T},v_{i}\rangle ^{2}\leq \lambda ^{2}\|1_{T}\|^{2}$.
This implies that $\|M1_{T}\|\leq \lambda \|1_{T}\|$ and $\left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \lambda \|1_{S}\|\|1_{T}\|=\lambda {\sqrt {|S||T|}}$.

### Proof Sketch of Tighter Bound

To show the tighter bound above, we instead consider the vectors $1_{S}-{\frac {|S|}{n}}\mathbf {1}$ and $1_{T}-{\frac {|T|}{n}}\mathbf {1}$, which are both perpendicular to $v_{1}$. We can expand
    $1_{S}^{\operatorname {T} }A_{G}1_{T}=\left({\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left({\frac {|T|}{n}}\mathbf {1} \right)+\left(1_{S}-{\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left(1_{T}-{\frac {|T|}{n}}\mathbf {1} \right)$
because the other two terms of the expansion are zero. The first term is equal to ${\frac {|S||T|}{n^{2}}}\mathbf {1} ^{\operatorname {T} }A_{G}\mathbf {1} ={\frac {d}{n}}|S||T|$, so we find that
    $\left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \left|\left(1_{S}-{\frac {|S|}{n}}\mathbf {1} \right)^{\operatorname {T} }A_{G}\left(1_{T}-{\frac {|T|}{n}}\mathbf {1} \right)\right|$
We can bound the right hand side by $\lambda \left\|1_{S}-{\frac {|S|}{|n|}}\mathbf {1} \right\|\left\|1_{T}-{\frac {|T|}{|n|}}\mathbf {1} \right\|=\lambda {\sqrt {|S||T|\left(1-{\frac {|S|}{n}}\right)\left(1-{\frac {|T|}{n}}\right)}}$ using the same methods as in the earlier proof.

## Applications

The expander mixing lemma can be used to upper bound the size of an independent set within a graph. In particular, the size of an independent set in an $(n,d,\lambda )$-graph is at most $\lambda n/d.$ This is proved by letting $T=S$ in the statement above and using the fact that $e(S,S)=0.$
An additional consequence is that, if $G$ is an $(n,d,\lambda )$-graph, then its chromatic number $\chi (G)$ is at least $d/\lambda .$ This is because, in a valid graph coloring, the set of vertices of a given color is an independent set. By the above fact, each independent set has size at most $\lambda n/d,$ so at least $d/\lambda$ such sets are needed to cover all of the vertices.
A second application of the expander mixing lemma is to provide an upper bound on the maximum possible size of an independent set within a polarity graph. Given a finite projective plane $\pi$ with a polarity $\perp ,$ the polarity graph is a graph where the vertices are the points a of $\pi$, and vertices $x$ and $y$ are connected if and only if $x\in y^{\perp }.$ In particular, if $\pi$ has order $q,$ then the expander mixing lemma can show that an independent set in the polarity graph can have size at most $q^{3/2}-q+2q^{1/2}-1,$ a bound proved by Hobart and Williford.

## Converse

Bilu and Linial showed that a converse holds as well: if a $d$-regular graph $G=(V,E)$ satisfies that for any two subsets $S,T\subseteq V$ with $S\cap T=\emptyset$ we have
    $\left|e(S,T)-{\frac {d|S||T|}{n}}\right|\leq \lambda {\sqrt {|S||T|}},$
then its second-largest (in absolute value) eigenvalue is bounded by $O(\lambda (1+\log(d/\lambda )))$.

## Generalization to hypergraphs

Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.
Let $H$ be a $k$-uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of $k$ vertices. For any choice of subsets $V_{1},...,V_{k}$ of vertices,
    $\left||e(V_{1},...,V_{k})|-{\frac {k!|E(H)|}{n^{k}}}|V_{1}|...|V_{k}|\right|\leq \lambda _{2}(H){\sqrt {|V_{1}|...|V_{k}|}}.$