A few remarks on the octopus inequality and Aldous' spectral gap conjecture

DOI10.1080/00927872.2014.975349MaRDI QIDQ2802188zbMATH OpenOpenAlexFDO

Authors Filippo Cesi

Publication date 25 April 2016

Published in Communications in Algebra (Search for Journal in Brave)

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

zbMATH Keywords

Cayley graphsymmetric groupAldous' conjectureKazhdam constantspectral group

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Representations of finite symmetric groups (20C30)

Abstract: A conjecture by D. Aldous, which can be formulated as a statement about the first nontrivial eigenvalue of the Laplacian of certain Cayley graphs on the symmetric group generated by transpositions, has been recently proven by Caputo, Liggett and Richthammer. Their proof is a subtle combination of two ingredients: a nonlinear mapping in the group algebra of the symmetric groups which permits a proof by induction, and a quite hard estimate named the octopus inequality. In this paper we present a simpler and more transparent proof of the octopus inequality, which emerges naturally when looking at the Aldous' conjecture from an algebraic perspective. We also show that the analogous of the Aldous' conjecture, where the spectral gap is replaced by the Kazhdan constant, does not hold in general.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 47926 (Why is no real title available?)
• scientific article; zbMATH DE number 1827712 (Why is no real title available?)
• Exact values of Kazhdan constants for some finite groups
• Generating a random permutation with random transpositions
• Interlacings for random walks on weighted graphs and the interchange process
• Kazhdan constants for conjugacy classes of compact groups.
• Minimal eigenvalue of the Coxeter Laplacian for the symmetric group
• On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
• Proof of Aldous' spectral gap conjecture
• Random shuffles and group representations
• Rate of convergence for shuffling cards by transpositions
• Spectral gap for the interchange process in a box
• The spectral gap of the ferromagnetic \(XXZ\) chain

Cited in

(11)

• The second eigenvalue of some normal Cayley graphs of highly transitive groups
• On the algebraic connectivity of some token graphs
• Comparing with octopi
• A general method to find the spectrum and eigenspaces of the \(k\)-token graph of a cycle, and 2-token through continuous fractions
• Aldous's spectral gap conjecture for normal sets
• On the spectral gap of some Cayley graphs on the Weyl group \(W(B_n)\)
• Aldous' spectral gap property for normal Cayley graphs on symmetric groups
• Proof of Aldous' spectral gap conjecture
• Coxeter factorizations with generalized Jucys–Murphy weights and Matrix‐Tree theorems for reflection groups
• On the spectra of token graphs of cycles and other graphs
• Eigenvalues of Cayley graphs

This page was built for publication: A few remarks on the octopus inequality and Aldous' spectral gap conjecture

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