The Second Eigenvalue of some Normal Cayley Graphs of Highly Transitive Groups

Abstract

Let $G$ be a finite group acting transitively on $[n]=\{1,2,\ldots,n\}$, and  let $\Gamma=\mathrm{Cay}(G,T)$ be a Cayley graph of $G$. The graph $\Gamma$ is called  normal if $T$ is closed under conjugation. In this paper, we obtain an upper bound for the second (largest) eigenvalue of the adjacency matrix of the graph $\Gamma$ in terms of the second eigenvalues of certain subgraphs of $\Gamma$. Using this result, we develop a recursive method to  determine the second eigenvalues of certain  Cayley graphs of $S_n$, and we determine the second eigenvalues  of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $S_n$  with  $\max_{\tau\in T}|\mathrm{supp}(\tau)|\leqslant 5$, where $\mathrm{supp}(\tau)$ is the set of points in $[n]$ non-fixed by $\tau$.