Let $S_n$ denote the symmetric group on $n$ elements, and $Sigmasubseteq S_{n}$ a symmetric subset of permutations. Aldous spectral gap conjecture, proved by Caputo, Liggett and Richthammer [arXiv:0906.1238], states that if $Sigma$ is a set of transpositions, then the second eigenvalue of the Cayley graph $mathrm{Cay}left(S_{n},Sigmaright)$ is identical to the second eigenvalue of the Schreier graph on $n$ vertices depicting the action of $S_{n}$ on $left{ 1,ldots,nright}$. 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 [2008], we show that for large enough $n$, if $Sigmasubset S_{n}$ is a full conjugacy class, then the second eigenvalue of $mathrm{Cay}left(S_{n},Sigmaright)$ 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,nright}$. 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 $Sigmasubset S_{n}$, which yields surprisingly strong consequences.
Download