The interchange process on dumbbell graphs has a sharp cutoff exactly when the smaller clique size tends to infinity, with the mixing time scaling crossing at m ~ sqrt(n).
Cutoff for conjugacy-invariant random walks on the permutation group
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation processes and control the Kantorovitch distance by using a variant of a coupling due to Oded Schramm. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time $cn/2$, the curvature is asymptotically zero for $c\le 1$ and is strictly positive for $c>1$.
fields
math.PR 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Mixing time and cutoff phenomenon for the interchange process on dumbbell graphs and the labelled exclusion process on the complete graph
The interchange process on dumbbell graphs has a sharp cutoff exactly when the smaller clique size tends to infinity, with the mixing time scaling crossing at m ~ sqrt(n).