Proof of Aldous' spectral gap conjecture

Abstract

Aldous' spectral gap conjecture asserts that on any graph the random walk process and the random transposition (or interchange) process have the same spectral gap. We prove the conjecture using a recursive strategy. The approach is a natural extension of the method already used to prove the validity of the conjecture on trees. The novelty is an idea based on electric network reduction, which reduces the problem to the proof of an explicit inequality for a random transposition operator involving both positive and negative rates. The proof of the latter inequality uses suitable coset decompositions of the associated matrices on permutations.

23 pages, 7 figures. Revised version, minor changes

References in corpus (2)

• On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
• Interlacings for random walks on weighted graphs and the interchange process

Cited by in corpus (34)

• The cutoff profile for the simple exclusion process on the circle
• Interacting particle systems as stochastic social dynamics
• Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling
• Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
• Verification of phased Dicke states
• Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet
• On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
• Comparison inequalities and fastest-mixing Markov chains
• The probability of long cycles in interchange processes
• A version of Aldous' spectral-gap conjecture for the zero range process
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• The second largest eigenvalues of some Cayley graphs on alternating groups
• On meteors, earthworms and WIMPs
• Dynamics of Pseudoentanglement
• On the dynamical behavior of the ABC model
• Coxeter factorizations with generalized Jucys-Murphy weights and Matrix Tree theorems for reflection groups
• Aldous' Spectral Gap Conjecture for Normal Sets
• Exact eigenspectrum of the symmetric simple exclusion process on the complete, complete bipartite, and related graphs
• Lifted TASEP: a Bethe ansatz integrable paradigm for non-reversible Markov chains
• Aldous' spectral gap property for normal Cayley graphs on symmetric groups
• Diffusive scaling of the Kob-Andersen model in ${\mathbb{Z}}^d$
• Ferromagnetic Ordering of Energy Levels for $U_q({\mathfrak{sl}}_2)$ Symmetric Spin Chains
• Spectral gap for random-to-random shuffling on linear extensions
• Mixing of the Averaging process and its discrete dual on finite-dimensional geometries
• Monotonicity properties of exclusion sensitivity
• Counterexamples to Ferromagnetic Ordering of Energy Levels
• The second largest eigenvalue of normal Cayley graphs on symmetric groups generated by cycles
• Free energy asymptotics of the quantum Heisenberg spin chain
• From non-symmetric particle systems to non-linear PDEs on fractals
• Cutoff for Rewiring Dynamics on Perfect Matchings
• Spectral gap of the symmetric inclusion process
• The second largest eigenvalue of some nonnormal Cayley graphs on symmetric groups
• On the Aldous-Caputo Spectral Gap Conjecture for Hypergraphs
• Mixing time for the asymmetric simple exclusion process in a random environment