Random sorting networks (Q2383011): Difference between revisions

From the authors' abstract: A sorting network is a shortest path from \(12\dots n\) to \(n\dots21\) in the Cayley graph of \(S_n\) generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as \(n\to\infty\) the space-time process of swaps converges to the product of semicircle law and Lebesgue measure. We conjecture that the trajectories of individual particles converge to random sine curves, while the permutation matrix at halftime converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Hölder-1/2 continuous, while the support of the permutation matrix lies within a certain octagon. A key tool is a connection with random Young tableaux.