 Expander mixing lemma

For a $d$-regular undirected graph whose normalized adjacency eigenvalues other than the constant eigenvalue have absolute value at most $\rho$, center the indicator vectors of $S,T$. Their constant parts give the expected term $d|S||T|/n$, and the operator norm on the mean-zero subspace bounds the remaining inner product. Here $e(S,T)=1_S^{T}A{1}_T$ counts oriented incidences, so an edge within $S\cap T$ is counted twice.

The Expander Mixing Lemma is a result from the field of graph theory, particularly in the study of expander graphs. Expander graphs are sparse graphs that have strong connectivity properties, which makes them useful in various applications, including computer science, combinatorics, and information theory. The Expander Mixing Lemma provides a quantitative measure of how well an expander graph mixes the vertices when performing random walks on the graph.