The second largest eigenvalue of Cayley graphs on symmetric groups

Abstract

The spectral gap of a regular graph is defined as the difference between the two largest eigenvalues of its adjacency matrix. It is a significant algebraic parameter reflecting the geometric properties of the graph, such as connectivity and expansion properties. The spectral gap is also a key index indicating the convergence rates of random processes on the graph. Cayley graphs are ideal candidates for constructing expanders due to their regularity and excellent symmetry. Thus, investigating the second largest eigenvalue of Cayley graphs is of great importance. One of the most famous results on this topic is Aldous' spectral gap conjecture, proposed by Aldous in 1992 and completely confir..