Aldous' spectral gap property for normal Cayley graphs on symmetric groups
arXiv:2203.06789 · doi:10.1016/j.ejc.2022.103657
Abstract
Aldous' spectral gap conjecture states that the second largest eigenvalue of any connected Cayley graph on the symmetric group Sn with respect to a set of transpositions is achieved by the standard representation of Sn. This celebrated conjecture, which was proved in its general form in 2010, has inspired much interest in searching for other families of Cayley graphs on Sn with the property that the largest eigenvalue strictly smaller than the degree is attained by the standard representation of Sn. In this paper, we prove three results on normal Cayley graphs on Sn possessing this property for sufficiently large n, one of which can be viewed as a generalization of the "normal" case of Aldous' spectral gap conjecture.
arXiv commentFinal version published in European Journal of Combinatorics
References in corpus (8)
- Proof of Aldous' spectral gap conjecture
- Eigenvalues of Cayley graphs
- On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
- Interlacings for random walks on weighted graphs and the interchange process
- The second largest eigenvalues of some Cayley graphs on alternating groups
- Aldous' Spectral Gap Conjecture for Normal Sets
- A direct comparison between the mixing time of the interchange process with "few" particles and independent random walks
- Entropy inequalities for random walks and permutations