Expander mixing lemma explained

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 (dn|S||T|)/() .

d-Regular Expander Graphs

Define an

(n, d, λ ) -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 λ . The d -regularity of the graph guarantees that its largest absolute value of an eigenvalue is d. In fact, the all-1's vector 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 λ then (n, d, λ ) -graphs form a family of expander graphs with a constant spectral gap.

Statement

Let

G = (V, E) be an (n, d, λ ) -graph. For any two subsets S, T \subseteq V , let e(S, T) = |\{(x,y) \in S x 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) - (d |S| |T|)/(n) \right| \leq λ \sqrt{|S| |T| }.

Tighter Bound

We can in fact show that

\left|e(S, T) - (d |S| |T|)/(n) \right| \leq λ \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

λ to be the second largest eigenvalue.^[2]

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| (e(S, T))/(e(G)) - \alpha \beta\right| \leq (λ)/(\sqrt{d _{Ld} _{R}) } \sqrt \leq \frac \sqrt\,.

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 λ _{1\geq … \geqλ} _{n} be the eigenvalues of A _{G} (these eigenvalues are real because A _{G} is symmetric). We know that λ _{1=d} with corresponding eigenvector v _{1= (1 {\sqrt)/(n} 1)} , the normalization of the all-1's vector. Define λ= \sqrt{ max \{ λ ^{2 \}}} _{n} and note that max \{ λ ^{2 \}\leq λ} _{n} ^{2= d} ^{1} ^{2} . Because A _{G} is symmetric, we can pick eigenvectors v _{2,\ldots,v} _{n} of A _{G} corresponding to eigenvalues λ _{2,\ldots,λ} _{n} so that \{v _{1,\ldots,v} _{n\}} forms an orthonormal basis of R ^{n} .

Let

J be the n x 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=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 ^{th} coordinate equal to 1 if v\in U and 0 otherwise. Then,\left|e(S,T) - (dn|S||T|\right| = \left| 1)/(_{S}) ^{\operatorname{T}\left(A} ^{G - (dnJ\right) 1)/(_{T\right|})} .

Let

M = A _{G - (dnJ)/()} . Because A _{G} and J share eigenvectors, the eigenvalues of M are 0 , λ _{2,\ldots,λ} _{n} . By the Cauchy-Schwarz inequality, we have that | 1 ^{\operatorname{T}M 1} _{T| = | 1} _{S ⋅} M 1 _{T|\leq\|1} _{S\|\|M1} _{T\|} . Furthermore, because M is self-adjoint, we can write\|M 1 ^{2= \langle} _{T\|} M 1 _{T,M1} _{T\rangle=\langle} 1 ^{21} _{T\rangle = \left\langle} 1 _{T,\sum} ^{nM} ^{i =1} ^{2\langle} 1 _{T,v} _{i\rangle} v _{i\right\rangle=\sum} ^{2 \langle} ^{i} 1 _{T,v} ^{2 \leq λ} ^{i\rangle} ^{2} ^{T\|} .

This implies that

\|M 1 _{T\|\leqλ\|1} _{T\|} and \left|e(S,T) - (dn|S||T|\right|\leq λ \| 1)/(_{S\|\|1}) _{T\|=λ\sqrt{|S||T|}} .

Proof Sketch of Tighter Bound

To show the tighter bound above, we instead consider the vectors

1 _{S - (|S|)/(n 1)} and 1 _{T - (|T|)/(n 1)} , which are both perpendicular to v _{1} . We can expand1 ^{\operatorname{T}A} _{G 1} ^{\operatorname{T}A} ^{G\left( (|T|)/(n 1\right)+\left(1)} ^{\operatorname{T}A} ^{G\left( 1} ^{T - (|T|)/(n 1\right))}

because the other two terms of the expansion are zero. The first term is equal to

(|S||T|)/(n ^{2}) 1 ^{\operatorname{T}A} _{G 1= (dn|S||T|)/()} , so we find that\left|e(S,T) - (dn|S||T|\right| \leq\left|\left( 1)/(^{S - (|S|)/(n 1\right))}) ^{\operatorname{T}A} ^{G\left( 1} ^{T - (|T|)/(n 1\right)\right|)}

We can bound the right hand side by

λ \left\| 1 _{S - (|S|)/(|n|)} 1\right\|\left\|1 _{T - (|T|)/(|n|)} 1\right\| =λ\sqrt{|S||T|\left(1- (|S|)/(n\right)\left(1- (|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, λ ) -graph is at most λ 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, λ ) -graph, then its chromatic number \chi(G) is at least d/ λ . 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 λ n/d, so at least d/ λ such sets are needed to cover all of the vertices.\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 + 2 q ^{1/2} - 1 , a bound proved by Hobart and Williford.

Converse

Bilu and Linial showed^[3] 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 = \empty we have\left|e(S, T) - (d |S| |T|)/(n) \right| \leq λ \sqrt{|S| |T|},

then its second-largest (in absolute value) eigenvalue is bounded by

O( λ ( 1+log (d/ λ ))) .

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)|} - (k!|E(H)|)/(n ^{k}) |V _{1|...|V} _{k|} \right| \le λ _{2(H)\sqrt{|V} _{1|...|V} _{k|}.}

References

• .
• 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. Ph.D..
• .
• .
• .

Notes and References

1. Web site: Expander Graphs. Vadhan. Salil. Spring 2009. Harvard University. December 1, 2019.
2. See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers
3. http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf Expander mixing lemma converse