= Zig-zag product
{wiki}
For a port-labeled $D$-regular <graph> $G$ and a $d$-regular <graph> $H$ on its $D$ port labels, replace every <vertex> by a copy of $H$. An <edge> makes a step in $H$, crosses the corresponding <edge> of $G$, then makes another step in $H$. The result has $|G|D$ <vertices> and degree $d^2$. Its normalized operator is $BRB$, where $B=I\otimes P_H$ and $R$ is the involutive <edge> rotation of $G$. Decomposing a mean-zero vector into cloud-constant and cloud-orthogonal parts proves the bound $\rho(G\mathbin{\mathrm{zigzag}}H)\leq\rho(G)+2\rho(H)+\rho(H)^2$.
Back to article page
