On Certain Integral Schreier Graphs of the Symmetric Group

Abstract

We compute the spectrum of the Schreier graph of the symmetric group $S_n$ corresponding to the Young subgroup $S_2\times S_{n-2}$ and the generating set consisting of initial reversals. In particular, we show that this spectrum is integral and for $n\geq 8$ consists precisely of the integers $\{0,1,\ldots,n\}$. A consequence is that the first positive eigenvalue of the Laplacian is always $1$ for this family of graphs.