Expander mixing lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, 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. .


Let be a d-regular graph on n vertices with the second-largest eigenvalue (in absolute value) of the normalized 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 .


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


The conclusion follows, since , and .


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 .


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


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