Expander mixing lemma
The expander mixing lemma intuitively states that the edges of certain formula_1-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets formula_2 and formula_3 is always close to the expected number of edges between them in a random formula_1-regular graph, namely formula_5. Section::::"d"-Regular Expander Graphs. Define an formula_6-graph to be a formula_1-regular graph formula_8 on formula_9 vertices such that all of the eigenvalues of its adjacency matrix formula_10 except one have absolute value at most formula_11 The formula_1-regularity of the graph guarantees that its  largest absolute value of an eigenvalue is formula_13 In fact, the all-1's vector formula_14 is an eigenvector of formula_10 with eigenvalue formula_1, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of formula_8 in absolute value. If we fix formula_1 and formula_19 then formula_6-graphs form a family of expander graphs with a constant spectral gap. Statement. Let formula_21 be an formula_6-graph. For any two subsets formula_23, let formula_24 be the number of edges between "S" and "T" (counting edges contained in the intersection of "S" and "T" twice). Then Expander mixing lemma The