MIXING TIMES FOR RANDOM k-CYCLES AND COALESCENCE-FRAGMENTATION CHAINS

Let S(n) be the permutation group on n elements, and consider a random walk on S(n) whose step distribution is uniform on k-cycles. We prove a well-known conjecture that the mixing time of this process is (1/k)n log n, with threshold of width linear in n. Our proofs are elementary and purely probabilistic, and do not appeal to the representation theory of S(n).