Spectral edge and vertex expansion

For the regular multigraph and spectral conventions in Constant vector is a top eigenvector, 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.