Expander mixing lemma – Wikipedia

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[edit]

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[edit]

Let

${displaystyle G=(V,E)}$

be an

${displaystyle (n,d,lambda )}$

-graph. For any two subsets

${displaystyle S,Tsubseteq V}$

, let

${displaystyle e(S,T)=|{(x,y)in Stimes T:xyin 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[edit]

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[edit]

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 Ssubseteq L,Tsubseteq 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}$

.

Proof of First Statement[edit]

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 ntimes 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 Usubseteq V}$

, let

${displaystyle 1_{U}}$

be the column vector with

${displaystyle v^{text{th}}}$

coordinate equal to 1 if

${displaystyle vin 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}}Jright)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 =leftlangle 1_{T},sum _{i=1}^{n}M^{2}langle 1_{T},v_{i}rangle v_{i}rightrangle =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[edit]

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[edit]

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 xin 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[edit]

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,Tsubseteq V}$

with

${displaystyle Scap 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[edit]

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

References[edit]

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