The expander mixing lemma states that, for any two subsets S , T of a d-regular expander graph G with n vertices, the number of edges between S and T is approximately what you would expect in a random d-regular graph, i.e. d | S | | T | / n .
Let G = ( V , E ) be a d-regular graph on n vertices with λ ∈ ( 0 , d ) the second-largest eigenvalue (in absolute value) of the adjacency matrix. For any two subsets S , T ⊆ V , let e ( S , T ) = | { ( x , y ) ∈ S × T : x y ∈ E ( G ) } | be the number of edges between S and T (counting edges contained in the intersection of S and T twice). Then
| e ( S , T ) − d | S | | T | n | ≤ λ | S | | T | . For biregular graphs, we have the following variation.
Let G = ( L , R , E ) be a bipartite graph such that every vertex in L is adjacent to d L vertices of R and every vertex in R is adjacent to d R vertices of L . Let S ⊆ L , T ⊆ R with | S | = α | L | and | T | = β | R | . Let e ( G ) = | E ( G ) | . Then
| e ( S , T ) e ( G ) − α β | ≤ λ d L d R α β ( 1 − α ) ( 1 − β ) ≤ λ d L d R α β . Note that d L d R is the largest absolute value of the eigenvalues of G .
Let A be the adjacency matrix for G . For a vertex subset U ⊆ V , let | U ⟩ = ∑ v ∈ U | v ⟩ ∈ R n . Here | v ⟩ is the standard basis element of R n with a one in the v t h position. Thus in particular A | V ⟩ = d | V ⟩ , and the number of edges between S and T is given by E ( S , T ) = ⟨ S | A | T ⟩ .
Expand each of | S ⟩ and | T ⟩ into a component in the direction of the largest-eigenvalue eigenvector | V ⟩ and an orthogonal component:
| S ⟩ = | S | n | V ⟩ + | S ′ ⟩ | T ⟩ = | T | n | V ⟩ + | T ′ ⟩ ,
where ⟨ S ′ | V ⟩ = ⟨ T ′ | V ⟩ = 0 . Then
⟨ S | A | T ⟩ = | S | | T | n 2 ⟨ V | A | V ⟩ + ⟨ S ′ | A | T ′ ⟩ .
The conclusion follows, since ⟨ V | A | V ⟩ = d ∥ | V ⟩ ∥ 2 = d n , and | ⟨ S ′ | A | T ′ ⟩ | ≤ d λ | | S ′ ⟩ . | T ′ ⟩ | ≤ d λ ∥ | S ′ ⟩ ∥ ∥ | T ′ ⟩ ∥ ≤ d λ ∥ | S ⟩ ∥ ∥ | T ⟩ ∥ = d λ | S | | T | .
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 S , T ⊆ V ,
| E ( S , T ) − d | S | | T | n | ≤ d λ | S | | T | then its second-largest eigenvalue is O ( d λ ( 1 + log ( 1 / λ ) ) ) .
