= Squaring and zig-zag iteration yields bounded-degree expanders
Choose $D=d^2$ and a fixed $d$-regular <graph> $H$ on $D^2$ <vertices> with absolute nonconstant <eigenvalues> at most $1/10$. Start with the loop-inclusive <complete graph> $G_0$ on $D$ <vertices> and iterate $G_{t+1}=G_t^2\mathbin{\mathrm{zigzag}}H$. The degree stays $D$, <vertex> counts are $D^{2t+1}$, and $\rho_{t+1}\leq\rho_t^2+21/100$. Since $\rho_0=0$, all $\rho_t\leq1/2$. The spectral cut bound gives multiplicity-counted <edge> expansion at least $D/4$. Removing loops and merging parallel <edges> loses at most a factor $D$, producing simple <expander graphs> with maximum degree $D$ and <edge> expansion at least $1/4$.
Back to article page
