Mathematics – Combinatorics
Scientific paper
2009-02-04
J. Algebraic Combin. 32, no. 2, 155-185 (2010)
Mathematics
Combinatorics
29 pages. Includes modification which appear on the published version in J. Algebraic Combin
Scientific paper
10.1007/s10801-009-0208-x
Given a finite simple graph $\cG$ with $n$ vertices, we can construct the Cayley graph on the symmetric group $S_n$ 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.
No associations
LandOfFree
On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-553570