Paper

The second largest eigenvalue of normal Cayley graphs on symmetric groups generated by cycles

Li, Yuxuan, Xia, Binzhou, Zhou, Sanming

2023

Overview

We study the normal Cayley graphs \\(\\mathrm{Cay}(S_n, C(n,I))\\) on the symmetric group \\(S_n\\), where \\(I\\subseteq \\{2,3,\\ldots,n\\}\\) and \\(C(n,I)\\) is the set of all cycles in \\(S_n\\) with length in \\(I\\). We prove that the strictly second largest eigenvalue of \\(\\mathrm{Cay}(S_n,C(n,I))\\) can only be achieved by at most four irreducible representations of \\(S_n\\), and we determine further the multiplicity of this eigenvalue in several special cases. As a corollary, in the case when \\(I\\) contains neither \\(n-1\\) nor \\(n\\) we know exactly when \\(\\mathrm{Cay}(S_n, C(n,I))\\) has the Aldous property, namely the strictly second largest eigenvalue is attained by the standard representation of \\(S_n\\), and we obtain that \\(\\mathrm{Cay}(S_n, C(n,I))\\) does not have the Aldous property whenever \\(n \\in I\\). As another corollary of our main results, we prove a recent conjecture on the second largest eigenvalue of \\(\\mathrm{Cay}(S_n, C(n,\\{k\\}))\\) where \\(2 \\le k \\le n-2\\).

• Publisher: Cornell University Library, arXiv.org
• Subject: Eigenvalues / Graphs / Representations