Expander mixing lemma

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

d-Regular Expander Graphs

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

If we fix ${\displaystyle d}$ and ${\displaystyle \lambda }$ then ${\displaystyle (n,d,\lambda )}$-graphs form a family of expander graphs with a constant spectral gap.

Statement

Let ${\displaystyle G=(V,E)}$ be an ${\displaystyle (n,d,\lambda )}$-graph. For any two subsets ${\displaystyle S,T\subseteq V}$, let ${\displaystyle 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

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

Tighter Bound

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]

Biregular Graphs

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

Proofs

Proof of First Statement

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

Proof Sketch of Tighter Bound

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.

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 ${\displaystyle (n,d,\lambda )}$-graph is at most ${\displaystyle \lambda n/d.}$ This is proved by letting ${\displaystyle T=S}$ in the statement above and using the fact that ${\displaystyle e(S,S)=0.}$

An additional consequence is that, if ${\displaystyle G}$ is an ${\displaystyle (n,d,\lambda )}$-graph, then its chromatic number ${\displaystyle \chi (G)}$ is at least ${\displaystyle 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 ${\displaystyle \lambda n/d,}$ so at least ${\displaystyle 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 ${\displaystyle \pi }$ with a polarity ${\displaystyle \perp ,}$ the polarity graph is a graph where the vertices are the points a of ${\displaystyle \pi }$, and vertices ${\displaystyle x}$ and ${\displaystyle y}$ are connected if and only if ${\displaystyle x\in y^{\perp }.}$ In particular, if ${\displaystyle \pi }$ has order ${\displaystyle q,}$ then the expander mixing lemma can show that an independent set in the polarity graph can have size at most ${\displaystyle q^{3/2}-q+2q^{1/2}-1,}$ a bound proved by Hobart and Williford.

Converse

Bilu and Linial showed^[3] that a converse holds as well: if a ${\displaystyle d}$-regular graph ${\displaystyle G=(V,E)}$ satisfies that for any two subsets ${\displaystyle S,T\subseteq V}$ with ${\displaystyle S\cap T=\emptyset }$ we have

${\displaystyle \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 ${\displaystyle O(\lambda (1+\log(d/\lambda )))}$.

Generalization to hypergraphs

Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.

Let ${\displaystyle H}$ be a ${\displaystyle k}$-uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of ${\displaystyle k}$ vertices. For any choice of subsets ${\displaystyle V_{1},...,V_{k}}$ of vertices,

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

Notes

References

• Alon, N.; Chung, F. R. K. (1988), "Explicit construction of linear sized tolerant networks", Discrete Mathematics, 72 (1–3): 15–19, CiteSeerX 10.1.1.300.7495, doi:10.1016/0012-365X(88)90189-6.
• F.C. Bussemaker, D.M. Cvetković, J.J. Seidel. Graphs related to exceptional root systems, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), volume 18 of Colloq. Math. Soc. János Bolyai (1978), 185-191.

• Haemers, W. H. (1979). Eigenvalue Techniques in Design and Graph Theory (PDF) (Ph.D.).
• Haemers, W. H. (1995), "Interlacing Eigenvalues and Graphs", Linear Algebra Appl., 226: 593–616, doi:10.1016/0024-3795(95)00199-2.

• Hoory, S.; Linial, N.; Wigderson, A. (2006), "Expander Graphs and their Applications" (PDF), Bull. Amer. Math. Soc. (N.S.), 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8.

• Friedman, J.; Widgerson, A. (1995), "On the second eigenvalue of hypergraphs" (PDF), Combinatorica, 15 (1): 43–65, doi:10.1007/BF01294459, S2CID 17896683.