Expander mixing lemma

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

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

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

Note that is the largest absolute value of the eigenvalues of .

Proof[edit]

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:

,

where . This orthogonality implies that and . Moreover

.

The conclusion follows, since , and .

Converse[edit]

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 ,

then its second-largest eigenvalue is .

Notes[edit]

  1. ^ See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers
  2. ^ Expander mixing lemma converse

References[edit]

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