Random Sorting Networks

Abstract

A sorting network is a shortest path from 12...n to n...21 in the Cayley graph of S_n generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n->infinity 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 half-time converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Holder-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.

38 pages, 12 figures

Cited by in corpus (28)

• Asymptotic domino statistics in the Aztec diamond
• The oriented swap process
• Jeu de taquin dynamics on infinite Young tableaux and second class particles
• The Archimedean limit of random sorting networks
• The Local Limit of Random Sorting Networks
• Random sorting networks: local statistics via random matrix laws
• A symplectic refinement of shifted Hecke insertion
• Geometry of Permutation Limits
• Primitive factorizations, Jucys-Murphy elements, and matrix models
• A Markov growth process for Macdonald's distribution on reduced words
• Sorting networks, staircase Young tableaux and last passage percolation
• Sweeps, polytopes, oriented matroids, and allowable graphs of permutations
• Periodic Pólya Urns, the Density Method, and Asymptotics of Young Tableaux
• A combinatorial version of Sylvester's four-point problem
• Stein's method, semicircle distribution, and reduced decompositions of the longest element in the symmetric group
• On the expected number of commutations in reduced words
• Ungarian Markov Chains
• A pattern theorem for random sorting networks
• Drawing Permutations with Few Corners
• The oriented swap process and last passage percolation
• Large deviations for the interchange process on the interval and incompressible flows
• Random Subnetworks of Random Sorting Networks
• Topological invariants of sorting networks
• A generalization of balanced tableaux and marriage problems with unique solutions
• A determinantal point process approach to scaling and local limits of random Young tableaux
• On collisions times of self-sorting interacting particles in one-dimension with random initial positions and velocities
• Random stable type minimal factorizations of the $n$-cycle
• Limiting behavior of the distance of a random walk