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

DOI10.1007/S10801-009-0208-XzbMATH Open1221.05196arXiv0902.0727OpenAlexW2069626659MaRDI QIDQ610447FDOQ610447

Authors: Filippo Cesi 

Publication date: 8 December 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating a random permutation with random transpositions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random shuffles and group representations
• Some Characters of the Symmetric Group
• Proof of Aldous' spectral gap conjecture
• On Cayley graphs on the symmetric group generated by transpositions
• The spectral gap of the ferromagnetic \(XXZ\) chain
• Spectral gap for the interchange process in a box
• Rate of convergence for shuffling cards by transpositions

Cited In (15)

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

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)