Expander mixing lemma

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

d-Regular Expander Graphs

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

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

Statement

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

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

Tighter Bound

We can in fact show that

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

using similar techniques.

Biregular Graphs

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

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

[math]\displaystyle{ \left|\frac{e(S, T)}{e(G)} - \alpha \beta\right| \leq \frac{\lambda}{\sqrt{d_Ld_R}} \sqrt{\alpha \beta (1 - \alpha) (1 - \beta)} \leq \frac{\lambda}{\sqrt{d_Ld_R}} \sqrt{\alpha \beta}\,. }[/math]

Note that [math]\displaystyle{ \sqrt{d_L d_R} }[/math] is the largest eigenvalue of [math]\displaystyle{ G }[/math].

Proofs

Proof of First Statement

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

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

[math]\displaystyle{ \left|e(S,T)-\frac dn|S||T|\right|=\left|1_S^\operatorname{T}\left(A_G-\frac dnJ\right)1_T\right| }[/math].

Let [math]\displaystyle{ M=A_G-\frac dnJ }[/math]. Because [math]\displaystyle{ A_G }[/math] and [math]\displaystyle{ J }[/math] share eigenvectors, the eigenvalues of [math]\displaystyle{ M }[/math] are [math]\displaystyle{ 0,\lambda_2,\ldots,\lambda_n }[/math]. By the Cauchy-Schwarz inequality, we have that [math]\displaystyle{ |1_S^\operatorname{T}M1_T|=|1_S\cdot M1_T|\leq\|1_S\|\|M1_T\| }[/math]. Furthermore, because [math]\displaystyle{ M }[/math] is self-adjoint, we can write

[math]\displaystyle{ \|M1_T\|^2=\langle M1_T,M1_T\rangle=\langle 1_T,M^21_T\rangle=\left\langle 1_T,\sum_{i=1}^nM^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 }[/math].

This implies that [math]\displaystyle{ \|M1_T\|\leq\lambda\|1_T\| }[/math] and [math]\displaystyle{ \left|e(S,T)-\frac dn|S||T|\right|\leq\lambda\|1_S\|\|1_T\|=\lambda\sqrt{|S||T|} }[/math].

Proof Sketch of Tighter Bound

To show the tighter bound above, we instead consider the vectors [math]\displaystyle{ 1_S-\frac{|S|}n\mathbf 1 }[/math] and [math]\displaystyle{ 1_T-\frac{|T|}n\mathbf 1 }[/math], which are both perpendicular to [math]\displaystyle{ v_1 }[/math]. We can expand

[math]\displaystyle{ 1_S^\operatorname{T}A_G1_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) }[/math]

because the other two terms of the expansion are zero. The first term is equal to [math]\displaystyle{ \frac{|S||T|}{n^2}\mathbf 1^\operatorname{T}A_G\mathbf 1=\frac dn|S||T| }[/math], so we find that

[math]\displaystyle{ \left|e(S,T)-\frac dn|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| }[/math]

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

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

Converse

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

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

then its second-largest (in absolute value) eigenvalue is bounded by [math]\displaystyle{ O(\lambda (1+\log(d/\lambda))) }[/math].

Generalization to hypergraphs

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

Let [math]\displaystyle{ H }[/math] be a [math]\displaystyle{ k }[/math]-uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of [math]\displaystyle{ k }[/math] vertices. For any choice of subsets [math]\displaystyle{ V_1, ..., V_k }[/math] of vertices,

[math]\displaystyle{ \left| |e(V_1,...,V_k)| - \frac{k!|E(H)|}{n^k}|V_1|...|V_k| \right| \le \lambda_2(H)\sqrt{|V_1|...|V_k|}. }[/math]

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, https://research.tilburguniversity.edu/en/publications/8fe72c7b-43cc-455a-a229-1833455b7746 .

• Hoory, S.; Linial, N.; Wigderson, A. (2006), "Expander Graphs and their Applications", Bull. Amer. Math. Soc. (N.S.) 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8, http://www.cc.gatech.edu/~mihail/LINIALexpsurvey.pdf .

• Friedman, J.; Widgerson, A. (1995), "On the second eigenvalue of hypergraphs", Combinatorica 15 (1): 43–65, doi:10.1007/BF01294459, https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/FW95/fw95a.pdf .