---
tag: ES427AJ8B6
kind: proof
name: Proof of Expander mixing lemma
proves: 7235FH8REJ
sources:
  - wikipedia: en:6230931@r1354782268
    locator: Expander mixing lemma, section Proofs > Proof Sketch of Tighter Bound
    note: adopted
    mention: wikipedia://en/6230931#YA6W
    sections: [Proof]
---

## 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.