= Expander mixing lemma
{title2=$|e(S,T)-d|S||T|/n|\leq d\rho\sqrt{|S|(1-|S|/n)|T|(1-|T|/n)}$}
{wiki}
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)=\mathbf1_S^TA\mathbf1_T$ counts oriented incidences, so an <edge> within $S\cap T$ is counted twice.
Back to article page
