Expander mixing lemma

We can in fact show that

${\displaystyle \left|e(S,T)-{\frac {d|S||T|}{n}}\right|\leq \lambda {\sqrt {|S||T|(1-|S|/n)(1-|T|/n)}}\,}$

using similar techniques.[1]

For biregular graphs, we have the following variation, where we take ${\displaystyle \lambda }$ to be the second largest eigenvalue.[2]

Let ${\displaystyle G=(L,R,E)}$ be a bipartite graph such that every vertex in ${\displaystyle L}$ is adjacent to ${\displaystyle d_{L}}$ vertices of ${\displaystyle R}$ and every vertex in ${\displaystyle R}$ is adjacent to ${\displaystyle d_{R}}$ vertices of ${\displaystyle L}$. Let ${\displaystyle S\subseteq L,T\subseteq R}$ with ${\displaystyle |S|=\alpha |L|}$ and ${\displaystyle |T|=\beta |R|}$. Let ${\displaystyle e(G)=|E(G)|}$. Then

${\displaystyle \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 ${\displaystyle {\sqrt {d_{L}d_{R}}}}$ is the largest eigenvalue of ${\displaystyle G}$.

Let ${\displaystyle A_{G}}$ be the adjacency matrix of ${\displaystyle G}$ and let ${\displaystyle \lambda _{1}\geq \cdots \geq \lambda _{n}}$ be the eigenvalues of ${\displaystyle A_{G}}$ (these eigenvalues are real because ${\displaystyle A_{G}}$ is symmetric). We know that ${\displaystyle \lambda _{1}=d}$ with corresponding eigenvector ${\displaystyle v_{1}={\frac {1}{\sqrt {n}}}\mathbf {1} }$, the normalization of the all-1's vector. Define ${\displaystyle \lambda ={\sqrt {\max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}}}}$ and note that ${\displaystyle \max\{\lambda _{2}^{2},\dots ,\lambda _{n}^{2}\}\leq \lambda ^{2}\leq \lambda _{1}^{2}=d^{2}}$. Because ${\displaystyle A_{G}}$ is symmetric, we can pick eigenvectors ${\displaystyle v_{2},\ldots ,v_{n}}$ of ${\displaystyle A_{G}}$ corresponding to eigenvalues ${\displaystyle \lambda _{2},\ldots ,\lambda _{n}}$ so that ${\displaystyle \{v_{1},\ldots ,v_{n}\}}$ forms an orthonormal basis of ${\displaystyle \mathbf {R} ^{n}}$.

Let ${\displaystyle J}$ be the ${\displaystyle n\times n}$ matrix of all 1's. Note that ${\displaystyle v_{1}}$ is an eigenvector of ${\displaystyle J}$ with eigenvalue ${\displaystyle n}$ and each other ${\displaystyle v_{i}}$, being perpendicular to ${\displaystyle v_{1}=\mathbf {1} }$, is an eigenvector of ${\displaystyle J}$ with eigenvalue 0. For a vertex subset ${\displaystyle U\subseteq V}$, let ${\displaystyle 1_{U}}$ be the column vector with ${\displaystyle v^{\text{th}}}$ coordinate equal to 1 if ${\displaystyle v\in U}$ and 0 otherwise. Then,

${\displaystyle \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 ${\displaystyle M=A_{G}-{\frac {d}{n}}J}$. Because ${\displaystyle A_{G}}$ and ${\displaystyle J}$ share eigenvectors, the eigenvalues of ${\displaystyle M}$ are ${\displaystyle 0,\lambda _{2},\ldots ,\lambda _{n}}$. By the Cauchy-Schwarz inequality, we have that ${\displaystyle |1_{S}^{\operatorname {T} }M1_{T}|=|1_{S}\cdot M1_{T}|\leq \|1_{S}\|\|M1_{T}\|}$. Furthermore, because ${\displaystyle M}$ is self-adjoint, we can write

${\displaystyle \|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 ${\displaystyle \|M1_{T}\|\leq \lambda \|1_{T}\|}$ and ${\displaystyle \left|e(S,T)-{\frac {d}{n}}|S||T|\right|\leq \lambda \|1_{S}\|\|1_{T}\|=\lambda {\sqrt {|S||T|}}}$.

To show the tighter bound above, we instead consider the vectors ${\displaystyle 1_{S}-{\frac {|S|}{n}}\mathbf {1} }$ and ${\displaystyle 1_{T}-{\frac {|T|}{n}}\mathbf {1} }$, which are both perpendicular to ${\displaystyle v_{1}}$. We can expand

${\displaystyle 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 ${\displaystyle {\frac {|S||T|}{n^{2}}}\mathbf {1} ^{\operatorname {T} }A_{G}\mathbf {1} ={\frac {d}{n}}|S||T|}$, so we find that

${\displaystyle \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 ${\displaystyle \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.