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

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 which permits a proof by induction, and a quite hard estimate named the octopus inequality. In this article 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.

Key Words:

• Aldous’ conjecture
• Cayley graph
• Kazhdam constant
• Spectral group
• Symmetric group

2010 Mathematics Subject Classification:

• 05C25
• 05C50
• 20C30
• 60K35

Notes

¹Some of these articles even predate the “official” formulation of the conjecture, as it is often the case.

²Even if it is not explicitly mentioned.

³Representations are finite-dimensional throughout this article, with the exception of Section 5.

⁴This happens when R is a multiple of I. In this case, 0 is the only eigenvalue, and it is trivial.

⁵If n < 5, one or more of the following terms are missing, which is all right.

⁶This means that the Young diagram of α′ is obtained from the Young diagram of α by interchanging rows and columns.

⁷Or, even more quickly, one can look them up on the internet.

⁸Partitions α = (2, 1, 1) and α = (1⁴), absent in this table, are conjugate to (3, 1) and (4), respectively.

Communicated by D. Macpherson.