The Local Limit of Random Sorting Networks

Abstract

A sorting network is a geodesic path from $12\cdots n$ to $n\cdots 21$ in the Cayley graph of $S_n$ generated by adjacent transpositions. For a uniformly random sorting network, we establish the existence of a local limit of the process of space-time locations of transpositions in a neighbourhood of $an$ for $a\in [0,1]$ as $n\to \infty$. Here time is scaled by a factor of $1/n$ and space is not scaled. The limit is a swap process $U$ on $\mathbb{Z}$. We show that $U$ is stationary and mixing with respect to the spatial shift and has time-stationary increments. Moreover, the only dependence on $a$ is through time scaling by a factor of $\sqrt{a(1-a)}$. To establish the existence of $U$, we find a local limit for staircase-shaped Young tableaux. These Young tableaux are related to sorting networks through a bijection of Edelman and Greene.

39 pages, 6 figures, The abstract and some exposition in Sections 1-3 has been rewritten. Sections 2 and 3 from the previous version have been merged into one section. Some proofs have been edited for clarity (chiefly the proof of Proposition 5.3, where a figure has been added to help explain the proof)

References in corpus (2)

• The oriented swap process
• Random sorting networks: local statistics via random matrix laws

Cited by in corpus (7)

• The Archimedean limit of random sorting networks
• Random sorting networks: local statistics via random matrix laws
• Sweeps, polytopes, oriented matroids, and allowable graphs of permutations
• Sorting networks, staircase Young tableaux and last passage percolation
• Ungarian Markov Chains
• The oriented swap process and last passage percolation
• Topological invariants of sorting networks