Emergence of giant cycles and slowdown transition in random transpositions and k-cycles

2010/04/20 by Nathanael Berestycki, Berestycki, Nathanael
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1004.3530

arxiv created 2010/04/20 · arxiv updated 2010/04/21

Abstract

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 (i.e., the acceleration drops from 0 to -∞ at this time as n tends to ∞). On the other hand, the largest cycle size changes from microscopic to giant. The proof of this last result is both considerably simpler and more general than in a previous result of Oded Schramm (2005) 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.

Related

• A phase transition in the random transposition random walk
• Cutoff for conjugacy-invariant random walks on the permutation group
• Cycle structure of the interchange process and representation theory
• The Evolution of the Mixing Rate
• Three steps mixing for general random walks on the hypercube at criticality