Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-089 | 8th May 2024 21:53

Tight Bounds for the Zig-Zag Product



The Zig-Zag product of two graphs, $Z = G \circ 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 \le \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
\frac{x}{c^2}\cdot\sqrt{1-\frac{d\cdot h(x)}{x\cdot h'(x)}}
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 expansion 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.

ISSN 1433-8092 | Imprint