Expander mixing lemma
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 vertices with the second-largest eigenvalue (in absolute value) of the normalized adjacency matrix. Then for any two subsets , let denote the number of edges between S and T. If the two sets are not disjoint, edges in their intersection are counted twice, that is, . We have
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 .
Recently, Bilu and Linial showed 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 .
- Expander mixing lemma converse. 
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|