Aldous’s spectral gap conjecture for normal sets

Abstract:

Let $S_{n}$ denote the symmetric group on $n$ elements, and let $\Sigma \subseteq S_{n}$ be a symmetric subset of permutations. Aldous’s spectral gap conjecture, proved by Caputo, Liggett, and Richthammer [J. Amer. Math. Soc. 23 (2010), no. 3, 831–851], states that if $\Sigma$ is a set of transpositions, then the second eigenvalue of the Cayley graph $\mathrm {Cay\!}\left (S_{n},\Sigma \right )$ is identical to the second eigenvalue of the Schreier graph on $n$ vertices depicting the action of $S_{n}$ on $\left \{ 1,\ldots ,n\right \}$. Inspired by this seminal result, we study similar questions for other types of sets in $S_{n}$. Specifically, we consider normal sets: sets that are invariant under conjugation. Relying on character bounds due to Larsen and Shalev [Invent. Math. 174 (2008), no. 3, 645–687], we show that for large enough $n$, if $\Sigma \subset S_{n}$ is a full conjugacy class, then the second eigenvalue of $\mathrm {Cay}\!\left (S_{n},\Sigma \right )$ is roughly identical to the second eigenvalue of the Schreier graph depicting the action of $S_{n}$ on ordered $4$-tuples of elements from $\left \{ 1,\ldots ,n\right \}$. We further show that this type of result does not hold when $\Sigma$ is an arbitrary normal set, but a slightly weaker one does hold. We state a conjecture in the same spirit regarding an arbitrary symmetric set $\Sigma \subset S_{n}$, which yields surprisingly strong consequences.