The expander mixing lemma intuitively states that the edges of certain
In particular, the number of edges between two vertex subsets
is always close to the expected number of edges between them in a random
vertices such that all of the eigenvalues of its adjacency matrix
-regularity of the graph guarantees that its largest absolute value of an eigenvalue is
, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of
-graphs form a family of expander graphs with a constant spectral gap.
Then We can in fact show that using similar techniques.
[1] For biregular graphs, we have the following variation, where we take
be a bipartite graph such that every vertex in
is symmetric, we can pick eigenvectors
forms an orthonormal basis of
share eigenvectors, the eigenvalues of
is self-adjoint, we can write This implies that
To show the tighter bound above, we instead consider the vectors
We can expand because the other two terms of the expansion are zero.
, so we find that We can bound the right hand side by
using the same methods as in the earlier proof.
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
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
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
then the expander mixing lemma can show that an independent set in the polarity graph can have size at most
a bound proved by Hobart and Williford.
Bilu and Linial showed[3] that a converse holds as well: if a
we have then its second-largest (in absolute value) eigenvalue is bounded by
Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.