FOCS Conference 2024 Conference Paper
Tight Bounds for the Zig-Zag Product
- Gil Cohen
- Itay Cohen 0003
- Gal Maor
The Zig-Zag product of two graphs, $Z= G\bigcirc{\! \! \! \! \! \! \mathrm{z}}\ H$, was introduced in the seminal work of Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound, which is used throughout, states that the spectral expansion of the Zig-Zag product can be bounded roughly by the sum of the spectral expansions of the individual graphs, $\omega z\leq\omega_{H}+\omega_{G}$. In this work we derive, for every (vertex-transitive) c-regular graph $H$ on $d$ vertices, a tight bound for $\omega z$ by taking into account the entire spectrum of $H$. Our work reveals that the bound, which holds for every graph $G$, is precisely the minimum value of the function \begin{equation*}\frac{x}{c^2} \cdot \sqrt{1-\frac{d \cdot h(x)}{x \cdot h^{\prime}(x)}}\end{equation*} in the domain $(c^{2}, \ \infty)$, where $h(x)$ is the characteristic polynomial of $H^{2}$. As a consequence, we establish that Zig-Zag products are indeed intrinsically quadratic away from being Ramanujan. We further prove tight bounds for the spectral ex-pansion of the more fundamental replacement product. Our lower bounds are based on results from analytic combinatorics, and we make use of finite free probability to prove their tightness. In a broader context, our work uncovers intriguing links between the two fields and these well-studied graph operators.