Description
The random walk on the permutations of $[N]$ generated by the transpositions was shown by Diaconis and Shahshahani to mix with sharp cutoff around $N \log N /2$ steps. However, Schramm showed that the distribution of the sizes of the largest cycles concentrates (after rescaling) on the Poisson-Dirichlet distribution $PD(0,1)$ considerably earlier, after $(1+\epsilon)N/2$ steps. We show that this behaviour truly emerges precisely during the critical window of $(1+\lambda N^{-1/3}) N/2$ steps, as $\lambda \rightarrow\infty$. Our methods are rather different, and involve an analogy with the classical Erdos-Renyi random graph process, the metric scaling limits of a uniformly-chosen connected graph with a fixed finite number of surplus edges, and analysing the directed cycle structure of large 3-regular graphs. Joint work with Christina Goldschmidt.