The notion of the derandomized square of two graphs, denoted as $G \circ H$, was introduced by Rozenman and Vadhan as they rederived Reingold's Theorem, $\mathbf{SL} = \mathbf{L}$. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and other reasons, understanding the spectral expansion $\lambda(G \circ H)$ becomes paramount. Rozenman and Vadhan derived an upper bound for $\lambda(G \circ H)$ in terms of the spectral expansions of the individual graphs, $\lambda(G)$ and $\lambda(H)$. They also proved their bound is optimal if the only information incorporated to the bound is the spectral expansion of the two graphs.

The objective of this work is to gain deeper insights into the behavior of derandomized squaring by taking into account the entire spectrum of $H$, where we focus on a vertex-transitive $H$. Utilizing deep results from analytic combinatorics, we establish a lower bound on $\lambda(G \circ H)$ that applies universally to all graphs $G$. Our work reveals that the key information regarding the bound lies within the largest real solution to the polynomial equation
$$(d-1) \chi_x(H) \chi_x''(H) = (d-2) \chi_x'(H)^2,$$
where $\chi_x(H)$ is the characteristic polynomial of the $d$-vertex graph $H$. Empirical evidence suggests that our lower bound is essentially optimal for every graph $H$ and for a typical graph $G$. We support the tightness of our lower bound by showing that the bound is tight for a class of graphs which exhibit local behavior similar to a derandomized squaring operation with $H$. To this end, we make use of finite free probability theory.

In our second result, we establish a lower bound for the spectral expansion of rotating expanders. These graphs, introduced by Cohen and Maor (STOC 2023), are constructed by taking a random walk with vertex permutations occurring after each step. We prove that Cohen and Maor's construction is essentially optimal. Unlike our results on derandomized squaring, the proof in this instance relies solely on combinatorial methods. The key insight lies in establishing a connection between random walks on graph products and the Fuss-Catalan numbers.