arXiv:1702.08368 [math.PR]AbstractReferencesReviewsResources
The Local Limit of Random Sorting Networks
Omer Angel, Duncan Dauvergne, Alexander E. Holroyd, Bálint Virág
Published 2017-02-27Version 1
A sorting network is a shortest path from $12 \dots n$ to $n \dots 21$ in the Cayley graph of $S_n$ generated by adjacent transpositions. We establish existence of a local limit of sorting networks in a neighbourhood of $an$ for $a\in[0,1]$ as $n\to\infty$, with time scaled by a factor of $n$. 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)}$.
Comments: 35 pages, 5 figures
Related articles: Most relevant | Search more
Random Subnetworks of Random Sorting Networks
arXiv:1802.08934 [math.PR] (Published 2018-02-25)
The Archimedean limit of random sorting networks
arXiv:1802.08933 [math.PR] (Published 2018-02-25)
Circular support in random sorting networks