Tight Bounds for the Zig-Zag Product

The Zig-Zag product of two graphs, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$Z= G\bigcirc{\!\!\!\!\!\! \mathrm{z}}\ H$</tex>, 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, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\omega z\leq\omega_{H}+\omega_{G}$</tex>. In this work we derive, for every (vertex-transitive) c-regular graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$H$</tex> on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d$</tex> vertices, a tight bound for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\omega z$</tex> by taking into account the entire spectrum of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$H$</tex>. Our work reveals that the bound, which holds for every graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex>, 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(c^{2},\ \infty)$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$h(x)$</tex> is the characteristic polynomial of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$H^{2}$</tex>. 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.