Geodesic
On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
Journal of Algebraic Combinatorics, Tome 32 (2010) no. 2, pp. 155-185.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Given a finite simple graph $G$ with $n$ vertices, we can construct the Cayley graph on the symmetric group $S _{ n }$ generated by the edges of $G$, interpreted as transpositions. We show that, if $G$ is complete multipartite, the eigenvalues of the Laplacian of Cay $( G)$ 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 $G$ and of Cay $( G)$ 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.
Keywords: Cayley graphs, Laplacian, symmetric group, Littlewood-Richardson rule, spectral gap, interchange process 
@article{JAC_2010__32_2_a6,
     author = {Cesi, Filippo},
     title = {On the eigenvalues of {Cayley} graphs on the symmetric group generated by a complete multipartite set of transpositions},
     journal = {Journal of Algebraic Combinatorics},
     pages = {155--185},
     publisher = {mathdoc},
     volume = {32},
     number = {2},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2010__32_2_a6/}
}
TY  - JOUR
AU  - Cesi, Filippo
TI  - On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
JO  - Journal of Algebraic Combinatorics
PY  - 2010
SP  - 155
EP  - 185
VL  - 32
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2010__32_2_a6/
LA  - en
ID  - JAC_2010__32_2_a6
ER  - 
%0 Journal Article
%A Cesi, Filippo
%T On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
%J Journal of Algebraic Combinatorics
%D 2010
%P 155-185
%V 32
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2010__32_2_a6/
%G en
%F JAC_2010__32_2_a6
Cesi, Filippo. On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions. Journal of Algebraic Combinatorics, Tome 32 (2010) no. 2, pp. 155-185. http://geodesic.mathdoc.fr/item/JAC_2010__32_2_a6/