The Archimedean limit of random sorting networks

Abstract:

A sorting network (also known as a reduced decomposition of the reverse permutation) is a shortest path from $12 \cdots n$ to $n \cdots 21$ in the Cayley graph of the symmetric group $S_n$ generated by adjacent transpositions. We prove that in a uniform random $n$-element sorting network $\sigma ^n$, all particle trajectories are close to sine curves with high probability. We also find the weak limit of the time-$t$ permutation matrix measures of $\sigma ^n$. As a corollary of these results, we show that if $S_n$ is embedded into $\mathbb {R}^n$ via the map $\tau \mapsto (\tau (1), \tau (2), \dots \tau (n))$, then with high probability, the path $\sigma ^n$ is close to a great circle on a particular $(n-2)$-dimensional sphere in $\mathbb {R}^n$. These results prove conjectures of Angel, Holroyd, Romik, and Virág.