Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles. (English) Zbl 1228.60079
Summary: Consider the random walk on the permutation group obtained when the step distribution is uniform on a given conjugacy class. It is shown that there is a critical time at which two phase transitions occur simultaneously. On the one hand, the random walk slows down abruptly: the acceleration (i.e., the second time derivative of the distance) drops from 0 to \(-\infty\) at this time as \(n\to\infty\). On the other hand, the largest cycle size changes from microscopic to giant. The proof of this last result is considerably simpler and holds more generally than in a previous result of O. Schramm [Isr. J. Math. 147, 221–243 (2005; Zbl 1130.60302)] for random transpositions. It turns out that in the case of random \(k\)-cycles, this critical time is proportional to \(1/[k(k-1)]\), whereas the mixing time is known to be proportional to \(1/k\).
MSC:
60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
60K35 | Interacting random processes; statistical mechanics type models; percolation theory |
60B15 | Probability measures on groups or semigroups, Fourier transforms, factorization |
05C80 | Random graphs (graph-theoretic aspects) |
05C12 | Distance in graphs |
05C65 | Hypergraphs |