On the second largest eigenvalue of some Cayley graphs of the symmetric group

摘要

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 - 2)!(n - r k - r)1/n - r ((k - 1)(n - k) - (k - r - 1)(k - r)/n - r - 1. We prove that this bound is attained 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 6.