@article{EJP2448,
author = {Omer Angel and Vadim Gorin and Alexander Holroyd},
title = {A pattern theorem for random sorting networks},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {17},
year = {2012},
keywords = {Sorting network; random sorting; reduced word; pattern; Young tableau},
abstract = {A sorting network is a shortest path from $12\cdots n$ to $n\cdots 21$ in the Cayley graph of the symmetric group $S_n$ generated by nearest-neighbor swaps. A pattern is a sequence of swaps that forms an initial segment of some sorting network. We prove that in a uniformly random $n$-element sorting network, any fixed pattern occurs in at least $c n^2$ disjoint space-time locations, with probability tending to $1$ exponentially fast as $n\to\infty$. Here $c$ is a positive constant which depends on the choice of pattern. As a consequence, the probability that the uniformly random sorting network is geometrically realizable tends to $0$.},
pages = {no. 99, 1-16},
issn = {1083-6489},
doi = {10.1214/EJP.v17-2448},
url = {http://ejp.ejpecp.org/article/view/2448}}