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}|=|1_{S}\cdot M1_{T}|\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}|}}.$

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.