Circular support in random sorting networks

Abstract

A sorting network is a shortest path from $12\cdots n$ to $n\cdots 21$ in the Cayley graph of the symmetric group generated by adjacent transpositions. For a uniform random sorting network, we prove that in the global limit, particle trajectories are supported on $\pi$-Lipschitz paths. We show that the weak limit of the permutation matrix of a random sorting network at any fixed time is supported within a particular ellipse. This is conjectured to be an optimal bound on the support. We also show that in the global limit, trajectories of particles that start within distance $\epsilon$ of the edge are within $\sqrt{2\epsilon }$ of a sine curve in uniform norm.

28 pages, 5 figures