arXiv Analytics

Sign in

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)}$.

Related articles: Most relevant | Search more
arXiv:0911.2519 [math.PR] (Published 2009-11-13, updated 2009-12-18)
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