Tight Bounds for the Zig-Zag Product

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 equationxc^2 1-d h(x)x h^(x)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.