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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): d. In fact, the all-1's vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \mathbf1} 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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\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

1. Vadhan, Salil (Spring 2009). "Expander Graphs" (PDF). Harvard University. Retrieved December 1, 2019.
2. See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers
3. Expander mixing lemma converse

References

• Alon, N.; Chung, F. R. K. (1988), "Explicit construction of linear sized tolerant networks", Discrete Mathematics, 72 (1–3): 15–19, 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 .