The expander mixing lemma states that, for any two subsets
of a d-regular expander graph
with
vertices, the number of edges between
and
is approximately what you would expect in a random d-regular graph, i.e.
.
Statement
Let
be a d-regular graph on n vertices with
the second-largest eigenvalue (in absolute value) of the adjacency matrix. For any two subsets
, let
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|}}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/569129f510ae0c774795021fd1019ab513376757)
For biregular graphs, we have the following variation.[1]
Let
be a bipartite graph such that every vertex in
is adjacent to
vertices of
and every vertex in
is adjacent to
vertices of
. Let
with
and
. Let
. 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 }}\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14de44079b2a32fb756f72a2a8885d37676d33b5)
Note that
is the largest absolute value of the eigenvalues of
.
Proof
Let
be the adjacency matrix for
. For a vertex subset
, let
. Here
is the standard basis element of
with a one in the
position. Thus in particular
, and the number of edges between
and
is given by
.
Expand each of
and
into a component in the direction of the largest-eigenvalue eigenvector
and an orthogonal component:
![{\displaystyle |S\rangle ={\frac {|S|}{n}}|V\rangle +|S'\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/a61a89ca17cc2dd3cf9f5307e456ae0ff7b263b0)
,
where
. Then
.
The conclusion follows, since
, and
.
Converse
Bilu and Linial showed[2] that the converse holds as well: if a graph satisfies the conclusion of the expander mixing lemma, that is, for any two subsets
,
![{\displaystyle |E(S,T)-{\frac {d|S||T|}{n}}|\leq d\lambda {\sqrt {|S||T|}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a428f6a9024992519f49883ce7e270619c822754)
then its second-largest eigenvalue is
.
Notes
- ^ See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers
- ^ Expander mixing lemma converse. [1]
References
- Alon, N.; Chung, F. R. K. (1988), "Explicit construction of linear sized tolerant networks", Discrete Mathematics, 72: 15–19, doi:10.1016/0012-365X(88)90189-6.