Jump to content

Expander mixing lemma

From Wikipedia, the free encyclopedia

The expander mixing lemma intuitively states that the edges of certain -regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .

d-Regular Expander Graphs

[edit]

Define an -graph to be a -regular graph on vertices such that all of the eigenvalues of its adjacency matrix except one have absolute value at most The -regularity of the graph guarantees that its largest absolute value of an eigenvalue is In fact, the all-1's vector is an eigenvector of with eigenvalue , and the eigenvalues of the adjacency matrix will never exceed the maximum degree of in absolute value.

If we fix and then -graphs form a family of expander graphs with a constant spectral gap.

Statement

[edit]

Let be an -graph. 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

Tighter Bound

[edit]

We can in fact show that

using similar techniques.[1]

Biregular Graphs

[edit]

For biregular graphs, we have the following variation, where we take to be the second largest eigenvalue.[2]

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

Note that is the largest eigenvalue of .

Proofs

[edit]

Proof of First Statement

[edit]

Let be the adjacency matrix of and let be the eigenvalues of (these eigenvalues are real because is symmetric). We know that with corresponding eigenvector , the normalization of the all-1's vector. Define and note that . Because is symmetric, we can pick eigenvectors of corresponding to eigenvalues so that forms an orthonormal basis of .

Let be the matrix of all 1's. Note that is an eigenvector of with eigenvalue and each other , being perpendicular to , is an eigenvector of with eigenvalue 0. For a vertex subset , let be the column vector with coordinate equal to 1 if and 0 otherwise. Then,

.

Let . Because and share eigenvectors, the eigenvalues of are . By the Cauchy-Schwarz inequality, we have that . Furthermore, because is self-adjoint, we can write

.

This implies that and .

Proof Sketch of Tighter Bound

[edit]

To show the tighter bound above, we instead consider the vectors and , which are both perpendicular to . We can expand

because the other two terms of the expansion are zero. The first term is equal to , so we find that

We can bound the right hand side by 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 -graph is at most This is proved by letting in the statement above and using the fact that

An additional consequence is that, if is an -graph, then its chromatic number is at least 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 so at least 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 with a polarity the polarity graph is a graph where the vertices are the points a of , and vertices and are connected if and only if In particular, if has order 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.

Converse

[edit]

Bilu and Linial showed[3] that a converse holds as well: if a -regular graph satisfies that for any two subsets with we have

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

Generalization to hypergraphs

[edit]

Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.

Let be a -uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of vertices. For any choice of subsets of vertices,

Notes

[edit]
  1. ^ Vadhan, Salil (Spring 2009). "Expander Graphs" (PDF). Harvard University. Retrieved December 1, 2019.
  2. ^ See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers
  3. ^ Expander mixing lemma converse

References

[edit]
  • Alon, N.; Chung, F. R. K. (1988), "Explicit construction of linear sized tolerant networks", Discrete Mathematics, 72 (1–3): 15–19, CiteSeerX 10.1.1.300.7495, doi:10.1016/0012-365X(88)90189-6.
  • 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.