On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
arXiv:0902.0727 · doi:10.1007/s10801-009-0208-x
Abstract
Given a finite simple graph $\cG$ with vertices, we can construct the Cayley graph on the symmetric group generated by the edges of $\cG$, interpreted as transpositions. We show that, if $\cG$ is complete multipartite, the eigenvalues of the Laplacian of $\Cay(\cG)$ have a simple expression in terms of the irreducible characters of transpositions, and of the Littlewood-Richardson coefficients. As a consequence we can prove that the Laplacians of $\cG$ and of $\Cay(\cG)$ have the same first nontrivial eigenvalue. This is equivalent to saying that Aldous's conjecture, asserting that the random walk and the interchange process have the same spectral gap, holds for complete multipartite graphs.
29 pages. Includes modification which appear on the published version in J. Algebraic Combin
References in corpus (2)
Cited by in corpus (12)
- Proof of Aldous' spectral gap conjecture
- Eigenvalues of Cayley graphs
- Interlacings for random walks on weighted graphs and the interchange process
- The second largest eigenvalues of some Cayley graphs on alternating groups
- Coxeter factorizations with generalized Jucys-Murphy weights and Matrix Tree theorems for reflection groups
- Exact eigenspectrum of the symmetric simple exclusion process on the complete, complete bipartite, and related graphs
- Aldous' spectral gap property for normal Cayley graphs on symmetric groups
- Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap
- Ordering the representations of S_n using the interchange process
- Asymptotic Ferromagnetic Ordering of Energy Levels for the Heisenberg Model on Large Boxes
- On the spectral gap of some Cayley graphs on the Weyl group
- Restricted permutations for the simple exclusion process in discrete time over graphs