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.
Recommendations
- Interlacings for random walks on weighted graphs and the interchange process
- Spectral gap for the interchange process in a box
- A version of Aldous' spectral-gap conjecture for the zero range process
- A few remarks on the octopus inequality and Aldous' spectral gap conjecture
- The spectrum and convergence rates of exclusion and interchange processes on the complete graph
Cites work
- Cayley graphs on the symmetric group generated by initial reversals have unit spectral gap
- Comparison theorems for reversible Markov chains
- Generating a random permutation with random transpositions
- scientific article; zbMATH DE number 3934150 (Why is no real title available?)
- scientific article; zbMATH DE number 3771876 (Why is no real title available?)
- Interlacings for random walks on weighted graphs and the interchange process
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
- Probability on trees and networks
- Random shuffles and group representations
- Random walks on trees and matchings
- Rate of convergence for shuffling cards by transpositions
- Spectral gap for the interchange process in a box
- Strong stationary times via a new form of duality
- The spectral gap of the ferromagnetic \(XXZ\) chain
Cited in
(79)- Spectral gap for the interchange process in a box
- Rate of convergence for shuffling cards by transpositions
- Spectral analysis of random-to-random Markov chains
- Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk
- The second eigenvalue of some normal Cayley graphs of highly transitive groups
- Convergence to equilibrium for a directed (1+d)-dimensional polymer
- Comparing with octopi
- Rates of convergence to equilibrium for potlatch and smoothing processes
- The full spectrum of random walks on complete finite \(d\)-ary trees
- A sharp log-Sobolev inequality for the multislice
- Typical and extremal aspects of friends-and-strangers graphs
- Eigenvalues of Cayley graphs
- The exclusion process mixes (almost) faster than independent particles
- Diffusive scaling of the Kob-Andersen model in \({\mathbb{Z}}^d \)
- The interchange process on high-dimensional products
- On the spectral gap of some Cayley graphs on the Weyl group \(W(B_n)\)
- The second largest eigenvalues of some Cayley graphs on alternating groups
- Mixing times for exclusion processes on hypergraphs
- A version of Aldous' spectral-gap conjecture for the zero range process
- Sharp phase transition in the random stirring model on trees
- On meteors, earthworms and wimps
- Validity of the spin-wave approximation for the free energy of the Heisenberg ferromagnet
- The spectrum and convergence rates of exclusion and interchange processes on the complete graph
- Optimizing the convergence rate of the quantum consensus: a discrete-time model
- The moving particle lemma for the exclusion process on a weighted graph
- Cutoff phenomenon for the asymmetric simple exclusion process and the biased card shuffling
- Friends and strangers walking on graphs
- Aldous' spectral gap property for normal Cayley graphs on symmetric groups
- A few remarks on the octopus inequality and Aldous' spectral gap conjecture
- Counterexamples to ferromagnetic ordering of energy levels
- Spectral gap for random-to-random shuffling on linear extensions
- Proof of the fundamental gap conjecture
- Interlacings for random walks on weighted graphs and the interchange process
- The probability of long cycles in interchange processes
- A proof of alon's second eigenvalue conjecture
- Interacting particle systems as stochastic social dynamics
- Comparison inequalities and fastest-mixing Markov chains
- Approach to equilibrium for random walks on graphs and for stochastic infinite particle processes
- Ferromagnetic ordering of energy levels for \(\mathrm{U}_q(\mathfrak{sl}_2)\) symmetric spin chains
- Stochastic models for large interacting systems and related correlation inequalities
- Ordering the representations of S_n using the interchange process
- Aldous's spectral gap conjecture for normal sets
- Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations
- Spectral gap for multi-species exclusion processes
- scientific article; zbMATH DE number 7662445 (Why is no real title available?)
- Coxeter factorizations with generalized Jucys–Murphy weights and Matrix‐Tree theorems for reflection groups
- On the spectra of token graphs of cycles and other graphs
- Quartic graphs with minimum spectral gap
- Cutoff for rewiring dynamics on perfect matchings
- Mixing of the averaging process and its discrete dual on finite-dimensional geometries
- On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions
- Mixing time and cutoff for one-dimensional particle systems
- Spectral properties of token graphs
- Mixing time for the asymmetric simple exclusion process in a random environment
- Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
- On the spectra and spectral radii of token graphs
- Universality of cutoff for exclusion with reservoirs
- On the dynamical behavior of the ABC model
- 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
- Density fluctuations for exclusion processes with long jumps
- Laplacian spectral radius and integrality of token graphs
- On the treewidth of token and Johnson graphs
- The analogue of Aldous’ spectral gap conjecture for the generalized exclusion process
- The second largest eigenvalue of some nonnormal Cayley graphs on symmetric groups
- Mixing time and cutoff for the k-SPEP
- On the algebraic connectivity of token graphs and graphs under perturbations
- On the Aldous-Caputo spectral gap conjecture for hypergraphs
- Essentially tight bounds for rainbow cycles in proper edge-colourings
- Entropy and curvature: beyond the Peres-Tetali conjecture
- Dynamics of pseudoentanglement
- Some bounds on the Laplacian eigenvalues of token graphs
- Violation of ferromagnetic ordering of energy levels in spin rings for the singlet
- Spectrum for some quantum Markov semigroups describing N-particle systems evolving under a binary collision mechanism
- Varadhan's decomposition of shift-invariant closed L^2-forms for large scale interacting systems on Euclidean lattices
- Free energy asymptotics of the quantum Heisenberg spin chain
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)
