Expander mixing lemma

Given: the objects and hypotheses in the statement above.

For the regular multigraph and spectral conventions in the stated convention, put $\alpha =\mathrm{\parallel }M{\mathrm{\mid }}_{{\mathbf{1}}^{\perp }}\mathrm{\parallel }$. For $n\ge 2$ order the eigenvalues $1={\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_n$, counting multiplicity, and put $\gamma =1-{\mu }_2$. Thus $\alpha ={\max }_{j\ge 2}\mathrm{\mid }{\mu }_j\mathrm{\mid }$, which also controls negative eigenvalues. Write $\mathrm{cut}(S)={\sum }_{u\in S,v\mathrm{\notin }S}{A}_{uv}$ and ${\mathrm{\partial }}_{V}S=\{v\mathrm{\notin }S:A_{uv}>0\text{ for some }u\in S\}$. Normalized edge expansion and external vertex expansion are $h={\min }_{0<\mathrm{\mid }S\mathrm{\mid }\le n\mathrm{/}2}\frac{\mathrm{cut}(S)}{d\mathrm{\mid }S\mathrm{\mid }},h_V={\min }_{0<\mathrm{\mid }S\mathrm{\mid }\le n\mathrm{/}2}\frac{\mathrm{\mid }{\mathrm{\partial }}_{V}S\mathrm{\mid }}{\mathrm{\mid }S\mathrm{\mid }}\mathrm{.}$ For $n=1$, put $\alpha =0$ and leave ${\mu }_2,\gamma ,h,h_V$ undefined; cut-expansion assertions are vacuous. A bounded-degree family is an expander family when its normalized edge expansion has a positive uniform lower bound for $n\ge 2$. Polynomial-time constructibility means a uniform algorithm outputs the adjacency list in time polynomial in $n$; neighbor computation in time polynomial in $\log n$ is a stronger requirement. (Spectral edge and vertex expansion).

For vectors $u,v$ in a real or complex inner product space, $\mathrm{\mid }⟨u,v⟩\mathrm{\mid }\le \parallel u\parallel \parallel v\parallel \mathrm{.}$ Equality holds if and only if $u$ and $v$ are linearly dependent, including the case in which either vector is zero. (Cauchy–Schwarz: $\mathrm{\mid }⟨u,v⟩\mathrm{\mid }\le \parallel u\parallel \parallel v\parallel$, with equality exactly for linearly dependent vectors).