On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions

DOI10.1007/S10801-009-0208-XMaRDI QIDQ610447zbMATH OpenOpenAlexFDO

Authors Filippo Cesi

Publication date 8 December 2010

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.0727

zbMATH Keywords

Cayley graphsLaplacianspectral gapsymmetric groupLittlewood-Richardson ruleinterchange process

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Random walks on graphs (05C81)

Abstract: 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.

Recommendations

• On Cayley graphs on the symmetric group generated by transpositions
• Aldous' spectral gap property for normal Cayley graphs on symmetric groups
• Aldous's spectral gap conjecture for normal sets
• On the spectral gap of some Cayley graphs on the Weyl group \(W(B_n)\)
• Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 3771876 (Why is no real title available?)
• scientific article; zbMATH DE number 3212917 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Generating a random permutation with random transpositions
• On Cayley graphs on the symmetric group generated by transpositions
• Proof of Aldous' spectral gap conjecture
• Random shuffles and group representations
• Rate of convergence for shuffling cards by transpositions
• Some Characters of the Symmetric Group
• Spectral gap for the interchange process in a box
• The spectral gap of the ferromagnetic \(XXZ\) chain

Cited in

(15)

• A few remarks on the octopus inequality and Aldous' spectral gap conjecture
• Minimal eigenvalue of the Coxeter Laplacian for the symmetric group
• The second eigenvalue of some normal Cayley graphs of highly transitive groups
• Ordering the representations of \(S_n\) using the interchange process
• Spectrum of Cayley graphs on the symmetric group generated by transpositions
• Interlacings for random walks on weighted graphs and the interchange process
• Aldous's spectral gap conjecture for normal sets
• On the spectral gap of some Cayley graphs on the Weyl group \(W(B_n)\)
• On Cayley graphs on the symmetric group generated by transpositions
• Aldous' spectral gap property for normal Cayley graphs on symmetric groups
• The second largest eigenvalues of some Cayley graphs on alternating groups
• Proof of Aldous' spectral gap conjecture
• Coxeter factorizations with generalized Jucys–Murphy weights and Matrix‐Tree theorems for reflection groups
• Fourier analysis of subgroup conjugacy invariant functions on finite groups
• Eigenvalues of Cayley graphs

This page was built for publication: On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q610447)