The second eigenvalue of some normal Cayley graphs of highly transitive groups (Q2001976)

Summary: Let \(G\) be a finite group acting transitively on \([n]=\{1,2,\ldots,n\}\), and let \(\Gamma=\text{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}|\text{supp}(\tau)|\leqslant 5\), where \(\text{supp}(\tau)\) is the set of points in \([n]\) non-fixed by \(\tau\).