On the second largest eigenvalue of some Cayley graphs of the Symmetric Group

Abstract

Let $S_n$ and $A_n$ denote the symmetric and alternating group on the set $\{1,..,n\},$ respectively. In this paper we are interested in the second largest eigenvalue ${\lambda }_2(\Gamma )$ of the Cayley graph $\Gamma =Cay(G,H)$ over $G=S_n$ or $A_n$ for certain connecting sets $H.$ Let $1<k\le n$ and denote the set of all $k$-cycles in $S_n$ by $C(n,k).$ For $H=C(n,n)$ we prove that ${\lambda }_2(\Gamma )=(n-2)!$ (when $n$ is even) and ${\lambda }_2(\Gamma )=2(n-3)!$ (when $n$ is odd). Further, for $H=C(n,n-1)$ we have ${\lambda }_2(\Gamma )=3(n-3)(n-5)!$ (when $n$ is even) and ${\lambda }_2(\Gamma )=2(n-2)(n-5)!$ (when $n$ is odd). The case $H=C(n,3)$ has been considered in X. Huang and Q. Huang, The second largest eigenvalue of some Cayley graphs on alternating groups, J. Algebraic Combinatorics} 50(2019), $99-111$. Let $1\le r<k<n$ and let $C(n,k;r)\subseteq C(n,k)$ be set of all $k$-cycles in $S_n$ which move all the points in the set $\{1,2,...,r\}.$ That is to say, $g=(i_1,i_2...i_k)(i_{k+1})\dots (i_n)\in C(n,k;r)$ if and only if $\{1,2,...,r\}\subset \{i_1,i_2,...,i_k\}.$ Our main result concerns ${\lambda }_2(\Gamma )$, where $\Gamma =Cay(G,H)$ with $H=C(n,k;r)$ with $1\le r<k<n$ when $G=S_n$ if $k$ is even and $G=A_n$ if $k$ is odd. Here we observe that $${\lambda }_2(\Gamma )\ge (k-2)!(\genfrac{}{}{0ex}{}{n-r}{k-r}\left)\frac{1}{n-r}\right((k-1)(n-k)-\frac{(k-r-1)(k-r)}{n-r-1}).$$ We show that this bound is sharp in the special case $k=r+1$ , giving ${\lambda }_2(\Gamma )=r!(n-r-1)$. The cases with $H=C(n,3;1)$ and $H=C(n,3;2)$ were considered earlier in the same paper of X. Huang and Q. Huang.

14 pages