Expander mixing lemma

The expander mixing lemma states that, for any two subsets S , T {displaystyle S,T} of a d-regular expander graph G {displaystyle G} with n {displaystyle n} vertices, the number of edges between S {displaystyle S} and T {displaystyle T} is approximately what you would expect in a random d-regular graph, i.e. d | S | | T | / n {displaystyle d|S||T|/n} . The expander mixing lemma states that, for any two subsets S , T {displaystyle S,T} of a d-regular expander graph G {displaystyle G} with n {displaystyle n} vertices, the number of edges between S {displaystyle S} and T {displaystyle T} is approximately what you would expect in a random d-regular graph, i.e. d | S | | T | / n {displaystyle d|S||T|/n} . Let G = ( V , E ) {displaystyle G=(V,E)} be a d-regular graph on n vertices with λ ∈ ( 0 , d ) {displaystyle lambda in (0,d)} the second-largest eigenvalue (in absolute value) of the adjacency matrix. For any two subsets S , T ⊆ V {displaystyle S,Tsubseteq V} , let e ( S , T ) = | { ( x , y ) ∈ S × T : x y ∈ E ( G ) } | {displaystyle e(S,T)=|{(x,y)in S imes T:xyin E(G)}|} 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. Let G = ( L , R , E ) {displaystyle G=(L,R,E)} be a bipartite graph such that every vertex in L {displaystyle L} is adjacent to d L {displaystyle d_{L}} vertices of R {displaystyle R} and every vertex in R {displaystyle R} is adjacent to d R {displaystyle d_{R}} vertices of L {displaystyle L} . Let S ⊆ L , T ⊆ R {displaystyle Ssubseteq L,Tsubseteq R} with | S | = α | L | {displaystyle |S|=alpha |L|} and | T | = β | R | {displaystyle |T|=eta |R|} . Let e ( G ) = | E ( G ) | {displaystyle e(G)=|E(G)|} . Then Note that d L d R {displaystyle {sqrt {d_{L}d_{R}}}} is the largest absolute value of the eigenvalues of G {displaystyle G} . Let A {displaystyle A} be the adjacency matrix for G {displaystyle G} . For a vertex subset U ⊆ V {displaystyle Usubseteq V} , let | U ⟩ = ∑ v ∈ U | v ⟩ ∈ R n {displaystyle |U angle =sum _{vin U}|v angle in mathbf {R} ^{n}} . Here | v ⟩ {displaystyle |v angle } is the standard basis element of R n {displaystyle mathbf {R} ^{n}} with a one in the v t h {displaystyle v^{th}} position. Thus in particular A | V ⟩ = d | V ⟩ {displaystyle A|V angle =d|V angle } , and the number of edges between S {displaystyle S} and T {displaystyle T} is given by E ( S , T ) = ⟨ S | A | T ⟩ {displaystyle E(S,T)=langle S|A|T angle } . Expand each of | S ⟩ {displaystyle |S angle } and | T ⟩ {displaystyle |T angle } into a component in the direction of the largest-eigenvalue eigenvector | V ⟩ {displaystyle |V angle } and an orthogonal component: where ⟨ S ′ | V ⟩ = ⟨ T ′ | V ⟩ = 0 {displaystyle langle S'|V angle =langle T'|V angle =0} . This orthogonality implies that ‖ | S ⟩ ‖ 2 = ‖ | S | n | V ⟩ ‖ 2 + ‖ | S ′ ⟩ ‖ 2 {displaystyle ||S angle |^{2}=|{frac {|S|}{n}}|V angle |^{2}+||S' angle |^{2}} and ‖ | T ⟩ ‖ 2 = ‖ | T | n | V ⟩ ‖ 2 + ‖ | T ′ ⟩ ‖ 2 {displaystyle ||T angle |^{2}=|{frac {|T|}{n}}|V angle |^{2}+||T' angle |^{2}} . Moreover The conclusion follows, since ⟨ V | A | V ⟩ = d ‖ | V ⟩ ‖ 2 = d n {displaystyle langle V|A|V angle =d||V angle |^{2}=dn} , and | ⟨ S ′ | A | T ′ ⟩ | ≤ ‖ | S ′ ⟩ ‖ ⋅ ‖ A | T ′ ⟩ ‖ ≤ λ ‖ | S ′ ⟩ ‖ ‖ | T ′ ⟩ ‖ = λ ‖ | S ⟩ ‖ 2 − ‖ | S | n | V ⟩ ‖ 2 ‖ | T ⟩ ‖ 2 − ‖ | T | n | V ⟩ ‖ 2 = λ | S | ( 1 − | S | / n ) | T | ( 1 − | T | / n ) {displaystyle |langle S'|A|T' angle |leq ||S' angle |cdot |A|T' angle |leq lambda ||S' angle |||T' angle |=lambda {sqrt {||S angle |^{2}-|{frac {|S|}{n}}|V angle |^{2}}}{sqrt {||T angle |^{2}-|{frac {|T|}{n}}|V angle |^{2}}}=lambda {sqrt {|S|(1-|S|/n)|T|(1-|T|/n)}}} .