ECCC-Report TR24-089https://eccc.weizmann.ac.il/report/2024/089Comments and Revisions published for TR24-089en-usWed, 08 May 2024 23:03:01 +0300
Paper TR24-089
| Tight Bounds for the Zig-Zag Product |
Gil Cohen,
Gal Maor,
Itay Cohen
https://eccc.weizmann.ac.il/report/2024/089The 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.Wed, 08 May 2024 23:03:01 +0300https://eccc.weizmann.ac.il/report/2024/089