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 (1)

• Interlacings for random walks on weighted graphs and the interchange process

Cited by in corpus (33)

• The cutoff profile for the simple exclusion process on the circle
• Interacting particle systems as stochastic social dynamics
• Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
• Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling
• Verification of phased Dicke states
• Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet
• 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
• The second largest eigenvalues of some Cayley graphs on alternating groups
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• 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
• Ferromagnetic Ordering of Energy Levels for $U_q({\mathfrak{sl}}_2)$ Symmetric Spin Chains
• Diffusive scaling of the Kob-Andersen model in ${\mathbb{Z}}^d$
• Mixing of the Averaging process and its discrete dual on finite-dimensional geometries
• Monotonicity properties of exclusion sensitivity
• Spectral gap for random-to-random shuffling on linear extensions
• Free energy asymptotics of the quantum Heisenberg spin chain
• The second largest eigenvalue of normal Cayley graphs on symmetric groups generated by cycles
• Counterexamples to Ferromagnetic Ordering of Energy Levels
• From non-symmetric particle systems to non-linear PDEs on fractals
• Spectral gap of the symmetric inclusion process
• Cutoff for Rewiring Dynamics on Perfect Matchings
• Mixing time for the asymmetric simple exclusion process in a random environment
• On the Aldous-Caputo Spectral Gap Conjecture for Hypergraphs
• The second largest eigenvalue of some nonnormal Cayley graphs on symmetric groups