Random sorting networks
By Omer Angel, Alexander E. Holroyd, Dan Romik, B'alint Vir'ag. 2006
90 citations recorded by the source corpus.
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 → ∞ 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.
Subfields: Discrete Mathematics and Combinatorics, Mathematical Physics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/dcb689d04933664a868641a46b2f0e4858313421
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Discrete Mathematics and Combinatorics
In Mathematical Physics
In Statistics and Probability
Citations in the corpus
- The Surprising Mathematics of Longest Increasing Subsequences (2015, background): “[6]) Let T = (ti,j)1≤i<j≤n be a uniformly random Young tableau of staircase shape n (defined in exercise 3.”