Expander mixing lemma
Let be a d-regular graph with normalized second-largest eigenvalue (in absolute value) of the 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
For a proof, see references.
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 .
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|