On the Laplacian spectral gap of generalized pancake graphs

Abstract

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/n\le \gamma (P(m,n))\le 1/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 ${\Theta }_m(1/n)$ as $n\to \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 ${\Theta }_n(m^{-2})$ as $m\to \infty$. This disproves a conjecture of Blanco and Buehrle asserting that, for fixed $n$, the corresponding undirected generalized pancake graphs form an expander family. Additionally, we present a counterexample to a recent conjecture of Greaves and Zhu concerning equality between the spectral gaps of the full Cayley graph and the associated coset Schreier graph.

Fixed typos, included a new conjecture