Proof of Aldous’ spectral gap conjecture

DOI10.1090/S0894-0347-10-00659-4zbMATH Open1203.60145arXiv0906.1238WikidataQ122984871 ScholiaQ122984871MaRDI QIDQ3584366FDOQ3584366

Thomas Richthammer, Thomas M. Liggett, Pietro Caputo

Publication date: 27 August 2010

Published in: Journal of the American Mathematical Society (Search for Journal in Brave)

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.

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

zbMATH Keywords

random walkspectral gapweighted graphinterchange processsymmetric exclusion process

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Continuous-time Markov processes on discrete state spaces (60J27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating a random permutation with random transpositions
• Probability on trees and networks
• Strong stationary times via a new form of duality
• Random shuffles and group representations
• Comparison theorems for reversible Markov chains
• Random walks on trees and matchings
• 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
• Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap
• Interlacings for Random Walks on Weighted Graphs and the Interchange Process

Cited In (57)

• On the spectra and spectral radii of token graphs
• Universality of cutoff for exclusion with reservoirs
• On the algebraic connectivity of some token graphs
• Garland's method for token graphs
• On the diameters of friends-and-strangers graphs
• Spectral gap of the symmetric inclusion process
• A general method to find the spectrum and eigenspaces of the \(k\)-token graph of a cycle, and 2-token through continuous fractions
• Typical and extremal aspects of friends-and-strangers graphs
• Title not available (Why is that?)
• A Few Remarks on the Octopus Inequality and Aldous’ Spectral Gap Conjecture
• Counterexamples to ferromagnetic ordering of energy levels
• Spectral gap for multi-species exclusion processes
• Free energy asymptotics of the quantum Heisenberg spin chain
• Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
• Sharp phase transition in the random stirring model on trees
• 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)\)
• Friends and strangers walking on graphs
• Eigenvalues of Cayley graphs
• On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
• The second largest eigenvalues of some Cayley graphs on alternating groups
• Stochastic models for large interacting systems and related correlation inequalities
• Diffusive scaling of the Kob-Andersen model in \({\mathbb{Z}}^d \)
• A proof of alon's second eigenvalue conjecture
• Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling
• Comparing with octopi
• On the dynamical behavior of the ABC model
• Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet
• Rates of convergence to equilibrium for potlatch and smoothing processes
• The full spectrum of random walks on complete finite \(d\)-ary trees
• A version of Aldous' spectral-gap conjecture for the zero range process
• Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
• Interacting particle systems as stochastic social dynamics
• The exclusion process mixes (almost) faster than independent particles
• Ferromagnetic ordering of energy levels for \(\mathrm{U}_q(\mathfrak{sl}_2)\) symmetric spin chains
• Coxeter factorizations with generalized Jucys–Murphy weights and Matrix‐Tree theorems for reflection groups
• Proof of the fundamental gap conjecture
• The probability of long cycles in interchange processes
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Spectral analysis of random-to-random Markov chains
• Spectral Gap for Random-to-Random Shuffling on Linear Extensions
• Mixing of the averaging process and its discrete dual on finite-dimensional geometries
• Optimizing the convergence rate of the quantum consensus: a discrete-time model
• Cutoff for rewiring dynamics on perfect matchings
• A sharp log-Sobolev inequality for the multislice
• Convergence to equilibrium for a directed \((1+d)\)-dimensional polymer
• Comparison inequalities and fastest-mixing Markov chains
• On meteors, earthworms and wimps
• Aldous' spectral gap property for normal Cayley graphs on symmetric groups
• The interchange process on high-dimensional products
• Mixing times for exclusion processes on hypergraphs
• Mixing time and cutoff for one-dimensional particle systems
• Spectral properties of token graphs
• Aldous’s spectral gap conjecture for normal sets
• Density fluctuations for exclusion processes with long jumps
• Mixing time for the asymmetric simple exclusion process in a random environment

This page was built for publication: Proof of Aldous’ spectral gap conjecture

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