A Few Remarks on the Octopus Inequality and Aldous’ Spectral Gap Conjecture

DOI10.1080/00927872.2014.975349zbMATH Open1334.05057arXiv1310.6156OpenAlexW2963583262MaRDI QIDQ2802188FDOQ2802188

Filippo Cesi

Publication date: 25 April 2016

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating a random permutation with random transpositions
• Random shuffles and group representations
• Minimal eigenvalue of the Coxeter Laplacian for the symmetric group
• Proof of Aldous’ spectral gap conjecture
• On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of 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
• Exact values of Kazhdan constants for some finite groups
• Kazhdan constants for conjugacy classes of compact groups.
• Interlacings for Random Walks on Weighted Graphs and the Interchange Process

Cited In (10)

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

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)