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 Virag.

65 pages, 5 figures. More background and connections with other areas have been added in the introduction since previous versions. To appear in J. Amer. Math. Soc

References in corpus (10)

• The oriented swap process
• Schur P-positivity and involution Stanley symmetric functions
• The Local Limit of Random Sorting Networks
• Random sorting networks: local statistics via random matrix laws
• A symplectic refinement of shifted Hecke insertion
• Circular support in random sorting networks
• Geometry of Permutation Limits
• A Markov growth process for Macdonald's distribution on reduced words
• On the expected number of commutations in reduced words
• Stein's method, semicircle distribution, and reduced decompositions of the longest element in the symmetric group

Cited by in corpus (10)

• Random sorting networks: local statistics via random matrix laws
• The skew Brownian permuton: a new universality class for random constrained permutations
• Random Permutations -- A geometric point of view
• 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
• Large deviations for the interchange process on the interval and incompressible flows
• Shift-Invariance of the Colored TASEP and Finishing Times of the Oriented Swap Process
• Random stable type minimal factorizations of the $n$-cycle