Trigonometry in Galois fields

The expander mixing lemma states that, for any two subsets $S,T$ of a d-regular expander graph $G$, the number of edges between $S$ and $T$ is approximately what you would expect in a random d-regular graph, i.e. $d\cdot |S|\cdot |T|/n$.

Statement

Let $G=(V,E)$ be a d-regular graph with normalized second-largest eigenvalue $\lambda$ (in absolute value) of the adjacency matrix. Then for any two subsets $S,T\subseteq V$, let $E(S,T)$ 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, $E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S)$. We have

$|E(S,T)-\frac{d\cdot |S|\cdot |T|}{n}|\le d\lambda \sqrt{|S|\cdot |T|}.$

For a proof, see references.

Converse

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 $S,T\subseteq V$,

$|E(S,T)-\frac{d\cdot |S|\cdot |T|}{n}|\le d\lambda \sqrt{|S|\cdot |T|}$

then its second-largest eigenvalue is $O(d\lambda \cdot (1+\log (1/\lambda )))$.

References

• Notes proving the expander mixing lemma. [1]
• Expander mixing lemma converse. [2]