Expander mixing lemma

Define an $(n,\; d,\; \backslash 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 $\backslash 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 $\backslash mathbf1$ 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 $\backslash lambda$ then $(n,\; d,\; \backslash lambda)$-graphs form a family of expander graphs with a constant spectral gap.

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

:$\backslash left|e(S,\; T)\; -\; \backslash frac\{d\; |S|\; |T|\}\{n\}\backslash right|\; \backslash leq\; \backslash lambda\; \backslash sqrt\{|S|\; |T|\; \}\backslash ,.$

We can in fact show that

:$\backslash left|e(S,\; T)\; -\; \backslash frac\{d\; |S|\; |T|\}\{n\}\backslash right|\; \backslash leq\; \backslash lambda\; \backslash sqrt\{|S|\; |T|\; (1\; -\; |S|/n)(1\; -\; |T|/n)\}\backslash ,$

using similar techniques.{{Cite web|url=https://people.seas.harvard.edu/~salil/cs225/spring09/lecnotes/Chap4.pdf|title=Expander Graphs|last=Vadhan|first=Salil|date=Spring 2009|website=Harvard University|archive-url=|archive-date=|access-date=December 1, 2019}}

For biregular graphs, we have the following variation, where we take $\backslash lambda$ to be the second largest eigenvalue.See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers

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\; \backslash subseteq\; L,\; T\; \backslash subseteq\; R$ with $|S|\; =\; \backslash alpha|L|$ and $|T|\; =\; \backslash beta\; |R|$. Let $e(G)\; =\; |E(G)|$. Then

:$\backslash left|\backslash frac\{e(S,\; T)\}\{e(G)\}\; -\; \backslash alpha\; \backslash beta\backslash right|\; \backslash leq\; \backslash frac\{\backslash lambda\}\{\backslash sqrt\{d\_Ld\_R\}\}\; \backslash sqrt\{\backslash alpha\; \backslash beta\; (1\; -\; \backslash alpha)\; (1\; -\; \backslash beta)\}\; \backslash leq\; \backslash frac\{\backslash lambda\}\{\backslash sqrt\{d\_Ld\_R\}\}\; \backslash sqrt\{\backslash alpha\; \backslash beta\}\backslash ,.$

Note that $\backslash sqrt\{d\_L\; d\_R\}$ is the largest eigenvalue of $G$.

Let $A\_G$ be the adjacency matrix of $G$ and let $\backslash lambda\_1\backslash geq\backslash cdots\backslash geq\backslash lambda\_n$ be the eigenvalues of $A\_G$ (these eigenvalues are real because $A\_G$ is symmetric). We know that $\backslash lambda\_1=d$ with corresponding eigenvector $v\_1=\backslash frac\; 1\{\backslash sqrt\; n\}\backslash mathbf\{1\}$, the normalization of the all-1's vector. Define $\backslash lambda=\backslash sqrt\{\backslash max\backslash \{\backslash lambda\_2^2,\backslash dots,\backslash lambda\_n^2\backslash \}\}$ and note that $\backslash max\backslash \{\backslash lambda\_2^2,\backslash dots,\backslash lambda\_n^2\backslash \}\backslash leq\backslash lambda^2\backslash leq\backslash lambda\_1^2=d^2$. Because $A\_G$ is symmetric, we can pick eigenvectors $v\_2,\backslash ldots,v\_n$ of $A\_G$ corresponding to eigenvalues $\backslash lambda\_2,\backslash ldots,\backslash lambda\_n$ so that $\backslash \{v\_1,\backslash ldots,v\_n\backslash \}$ forms an orthonormal basis of $\backslash mathbf\; R^n$.

Let $J$ be the $n\backslash 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=\backslash mathbf\{1\}$, is an eigenvector of $J$ with eigenvalue 0. For a vertex subset $U\; \backslash subseteq\; V$, let $1\_U$ be the column vector with $v^\backslash text\{th\}$ coordinate equal to 1 if $v\backslash in\; U$ and 0 otherwise. Then,

:$\backslash left|e(S,T)-\backslash frac\; dn|S||T|\backslash right|=\backslash left|1\_S^\backslash operatorname\{T\}\backslash left(A\_G-\backslash frac\; dnJ\backslash right)1\_T\backslash right|$.

Let $M=A\_G-\backslash frac\; dnJ$. Because $A\_G$ and $J$ share eigenvectors, the eigenvalues of $M$ are $0,\backslash lambda\_2,\backslash ldots,\backslash lambda\_n$. By the Cauchy-Schwarz inequality, we have that $|1\_S^\backslash operatorname\{T\}M1\_T|=\backslash langle\; 1\_S,\; M1\_T\backslash rangle\backslash leq\backslash |1\_S\backslash |\backslash |M1\_T\backslash |$. Furthermore, because $M$ is self-adjoint, we can write

:$\backslash |M1\_T\backslash |^2=\backslash langle\; M1\_T,M1\_T\backslash rangle=\backslash langle\; 1\_T,M^21\_T\backslash rangle=\backslash left\backslash langle\; 1\_T,\backslash sum\_\{i=1\}^nM^2\backslash langle\; 1\_T,v\_i\backslash rangle\; v\_i\backslash right\backslash rangle=\backslash sum\_\{i=2\}^n\backslash lambda\_i^2\backslash langle\; 1\_T,v\_i\backslash rangle^2\backslash leq\backslash lambda^2\backslash |1\_T\backslash |^2$.

This implies that $\backslash |M1\_T\backslash |\backslash leq\backslash lambda\backslash |1\_T\backslash |$ and $\backslash left|e(S,T)-\backslash frac\; dn|S||T|\backslash right|\backslash leq\backslash lambda\backslash |1\_S\backslash |\backslash |1\_T\backslash |=\backslash lambda\backslash sqrt$

To show the tighter bound above, we instead consider the vectors $1\_S-\backslash frac$

:$1\_S^\backslash operatorname\{T\}A\_G1\_T=\backslash left(\backslash frac$

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

:$\backslash left|e(S,T)-\backslash frac\; dn|S||T|\backslash right|$

\leq\left|\left(1_S-\frac

We can bound the right hand side by $\backslash lambda\backslash left\backslash |1\_S-\backslash frac$

=\lambda\sqrt

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,\; \backslash lambda)$-graph is at most $\backslash 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,\; \backslash lambda)$-graph, then its chromatic number $\backslash chi(G)$ is at least $d/\backslash 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 $\backslash lambda\; n/d,$ so at least $d/\backslash 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 $\backslash pi$ with a polarity $\backslash perp,$ the polarity graph is a graph where the vertices are the points a of $\backslash pi$, and vertices $x$ and $y$ are connected if and only if $x\backslash in\; y^\{\backslash perp\}.$ In particular, if $\backslash 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.

Bilu and Linial showed[http://www.cs.huji.ac.il/~nati/PAPERS/raman_lift.pdf Expander mixing lemma converse] that a converse holds as well: if a $d$-regular graph $G\; =\; (V,\; E)$ satisfies that for any two subsets $S,\; T\; \backslash subseteq\; V$ with $S\; \backslash cap\; T\; =\; \backslash empty$ we have

:$\backslash left|e(S,\; T)\; -\; \backslash frac\{d\; |S|\; |T|\}\{n\}\backslash right|\; \backslash leq\; \backslash lambda\; \backslash sqrt$

then its second-largest (in absolute value) eigenvalue is bounded by $O(\backslash lambda\; (1+\backslash log(d/\backslash lambda)))$.

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,

:$\backslash left|\; |e(V\_1,...,V\_k)|\; -\; \backslash frac\{k!|E(H)|\}\{n^k\}|V\_1|...|V\_k|\; \backslash right|\; \backslash le\; \backslash lambda\_2(H)\backslash sqrt$

{{Reflist}}

• {{citation

| last1 = Alon | first1 = N.

| last2 = Chung | first2 = F. R. K.

| journal = Discrete Mathematics

| pages = 15–19

| title = Explicit construction of linear sized tolerant networks

| volume = 72

| issue = 1–3

| year = 1988

| doi=10.1016/0012-365X(88)90189-6| doi-access = free

| citeseerx = 10.1.1.300.7495

}}.

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

• {{cite thesis |last= Haemers|first= W. H.|date= 1979|title= Eigenvalue Techniques in Design and Graph Theory|type= Ph.D.|url= http://alexandria.tue.nl/extra3/proefschrift/PRF3A/7909413.pdf}}
• {{citation

| last1 = Haemers | first1 = W. H.

| journal = Linear Algebra Appl.

| pages = 593–616

| title = Interlacing Eigenvalues and Graphs

| volume = 226

| year = 1995

| doi=10.1016/0024-3795(95)00199-2| url = https://research.tilburguniversity.edu/en/publications/8fe72c7b-43cc-455a-a229-1833455b7746

| doi-access = free

}}.

• {{citation

|last1 = Hoory |first1 = S.

|last2 = Linial | first2 = N.

|last3 = Wigderson | first3 = A.

|pages = 439–561

| title = Expander Graphs and their Applications

| journal = Bull. Amer. Math. Soc. (N.S.)

| year = 2006

| url = http://www.cc.gatech.edu/~mihail/LINIALexpsurvey.pdf

| volume = 43

|issue = 4

| doi = 10.1090/S0273-0979-06-01126-8| doi-access = free

}}.

• {{citation

| last1 = Friedman | first1 = J.

| last2 = Widgerson | first2 = A.

| journal = Combinatorica

| pages = 43–65

| title = On the second eigenvalue of hypergraphs

| volume = 15

| issue = 1

| year = 1995

| url = https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/FW95/fw95a.pdf

| doi = 10.1007/BF01294459| s2cid = 17896683

}}.

Category:Theoretical computer science

Category:Lemmas in graph theory

Category:Algebraic graph theory