On the Laplacian spectral gap of generalized pancake graphs

The generalized pancake graph $P(m,n)$ is the Cayley graph of the group of colored permutations ${\mathbb{Z}}_m\wr S_n=({\mathbb{Z}}_m{)}^n⋊S_n$ generated by generalized prefix reversals. In this paper, we establish that, for all $m,n\ge 2$, the spectral gap $\gamma (P(m,n))$ of the normalized Laplacian satisfies ${\alpha }_m\mathrm{/}n\le \gamma (P(m,n))\le 1\mathrm{/}n$, where ${\alpha }_m$ is a positive constant that depends only on $m$. As a consequence, for every fixed $m\ge 2$, $\gamma (P(m,n))$ is ${\mathrm{\Theta }}_m(1\mathrm{/}n)$ as $n\to \mathrm{\infty }$. The proof combines Cesi’s semi-recursive spectral-gap inequality with a Fourier decomposition of the appropriate operators associated with a coset Schreier graph of color-position pairs. For fixed $n\ge 2$, we also establish that $\gamma (P(m,n))$ is ${\mathrm{\Theta }}_n(m^{-2})$ as $m\to \mathrm{\infty }$. This disproves a conjecture of Blanco and Buehrle asserting that, for fixed $n$, the corresponding undirected generalized pancake graphs form an expander family.