9 The zig-zag product
\(G^k\) has an edge for every length-\(k\) walk of \(G\); if \(G\) is an \((n,d,\alpha )\)-graph then \(G^k\) is an \((n,d^k,\alpha ^k)\)-graph.
For an \((n,m,\alpha )\)-graph \(G\) and an \((m,d,\beta )\)-graph \(H\), \(G\, \textcircled rH\) has vertex set \(V(G)\times [m]\) (each \(G\)-vertex a cloud of \(m\) vertices), with the \(G\)-edges between clouds and \(n\) copies of \(H\) within clouds.
\(G\textcircled {z}H=(V(G)\times [m],E')\) where \(((v,i),(u,j))\in E'\) iff there are \(k,l\) with \((i,k),(l,j)\in E(H)\) and \(e_v^k=e_u^l\) (dashed–wiggly–dashed walks in \(G\, \textcircled rH\)).
\(\varphi (\alpha ,\beta )\le \alpha +\beta +\beta ^2\) for \(G\textcircled {z}H\).
Write the walk matrix \(Z=\tilde{\mathbf B}P\tilde{\mathbf B}\) with \(\tilde{\mathbf B}=\hat B\otimes I\) and \(P\) the matching involution. Decompose \(f=f^\parallel +f^\perp \) (cloud averages and remainders); then \(\tilde{\mathbf B}f^\parallel =f^\parallel \), \(\| \tilde{\mathbf B}f^\perp \| \le \beta \| f^\perp \| \), and \(f^\parallel Pf^\parallel =g\hat A_Gg\le \alpha \| f^\parallel \| ^2\). Hence \(|fZf|\le \alpha \| f^\parallel \| ^2+2\beta \| f^\parallel \| \| f^\perp \| + \beta ^2\| f^\perp \| ^2\), whose maximum is the top eigenvalue of \(\left(\begin{smallmatrix} \alpha & \beta \\ \beta & \beta ^2 \end{smallmatrix}\right) \le \alpha +\beta +\beta ^2\).
If \(G\) is an \((n,m,\alpha )\)-graph and \(H\) an \((m,d,\beta )\)-graph, then \(G\textcircled {z}H\) is an \((nm,d^2,\varphi (\alpha ,\beta ))\)-graph with: (1) \(\varphi {\lt}1\) if \(\alpha ,\beta {\lt}1\); (2) \(\varphi \le \alpha +\beta \); (3) \(\varphi \le 1-(1-\beta ^2)(1-\alpha )/2\).
Lemma 165 gives \(\varphi \le \alpha +\beta +\beta ^2\) and bound (1). The sharper bounds (2),(3) are the harder analysis of [RVW02]/[RTV05].
Fix a \((d^4,d,1/4)\)-graph \(H\) (it exists by a probabilistic argument and, \(d\) being constant, is found by brute force).
\(G_1=H^2\), \(G_{n+1}=(G_n)^2\textcircled {z}H\).
\(G_n\) is a \((d^{4n},d^2,1/2)\)-graph for all \(n\).
Base: \(H^2\) is \((d^4,d^2,1/16)\). Inductively \((G_n)^2\) is \((d^{4n},d^4,1/4)\); zig-zagging with \(H\) (degree match \(d^4\)) gives via bound (2) \(\varphi \le 1/4+1/4=1/2\), so \(G_{n+1}\) is \((d^{4(n+1)},d^2,1/2)\).
For input \(D=d^{16}\)-regular connected \(G\) (so an \((n,D,\alpha )\)-graph with \(\alpha {\lt}1-\Omega (1/n^2)\)) and a \((d^{16},d,1/2)\)-graph \(H\), set \(G_1=G\), \(G_{i+1}=(G_i\textcircled {z}H)^8\), run for \(k=O(\log n)\) steps.
Undirected \(s\)-\(t\) connectivity is solvable by a polynomial-length random walk in randomized logspace (\(SL\subseteq RL\)).
\(G_k\) is an \((nd^{16k},d^{16},3/4)\)-graph.
By bound (3), \(1-\mu _i\ge \tfrac 38(1-\lambda _i)\), so \(\lambda _{i+1}=\mu _i^8\le \max (\lambda _i^2,1/2)\); after \(k=O(\log n)\) steps \(\lambda _k\le 3/4\). The size multiplies by \(d^{16}\) each step.
Neighbour queries to \(G_k\) are answerable in logspace.
Undirected \(s\)-\(t\) connectivity is in deterministic logspace, so \(SL=L\).