Proof of Expander mixing lemma

Proof

To show the tighter bound above, we instead consider the vectors $1_S-\frac{|S|}n\mathbf 1$ and $1_T-\frac{|T|}n\mathbf 1$, which are both perpendicular to $v_1$. We can expand

1_S^\operatorname{T}A_G1_T=\left(\frac{|S|}n\mathbf 1\right)^\operatorname{T}A_G\left(\frac{|T|}n\mathbf 1\right)+\left(1_S-\frac{|S|}n\mathbf 1\right)^\operatorname{T}A_G\left(1_T-\frac{|T|}n\mathbf 1\right)

because the other two terms of the expansion are zero. The first term is equal to \frac{|S||T|}{n^2}\mathbf 1^\operatorname{T}A_G\mathbf 1=\frac dn|S||T|, so we find that

\left|e(S,T)-\frac dn|S||T|\right| \leq\left|\left(1_S-\frac{|S|}n\mathbf 1\right)^\operatorname{T}A_G\left(1_T-\frac{|T|}n\mathbf 1\right)\right|

We can bound the right hand side by $\lambda\left\|1_S-\frac{|S|}{|n|}\mathbf 1\right\|\left\|1_T-\frac{|T|}{|n|}\mathbf 1\right\| =\lambda\sqrt{|S||T|\left(1-\frac{|S|}n\right)\left(1-\frac{|T|}n\right)}$ using the same methods as in the earlier proof.