A pattern theorem for random sorting networks

Omer Angel (University of British Columbia)
Vadim Gorin (Massachusetts Institute of Technology and Institute for Information Transmission Problems of Moscow)
Alexander E Holroyd (Microsoft Research Redmond)


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

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-16

Publication Date: November 19, 2012

DOI: 10.1214/EJP.v17-2448


  • Angel, Omer; Holroyd, Alexander E.; Romik, Dan; Virág, Bálint. Random sorting networks. Adv. Math. 215 (2007), no. 2, 839--868. MR2355610
  • Angel, Omer; Holroyd, Alexander E. Random subnetworks of random sorting networks. Electron. J. Combin. 17 (2010), no. 1, Note 23, 7 pp. MR2644860
  • Azuma, Kazuoki. Weighted sums of certain dependent random variables. Tôhoku Math. J. (2) 19 1967 357--367. MR0221571
  • Edelman, Paul; Greene, Curtis. Balanced tableaux. Adv. in Math. 63 (1987), no. 1, 42--99. MR0871081
  • Frame, J. S.; Robinson, G. de B.; Thrall, R. M. The hook graphs of the symmetric groups. Canadian J. Math. 6, (1954). 316--324. MR0062127
  • Goodman, Jacob E.; Pollack, Richard. On the combinatorial classification of nondegenerate configurations in the plane. J. Combin. Theory Ser. A 29 (1980), no. 2, 220--235. MR0583961
  • Handbook of discrete and computational geometry. Second edition. Edited by Jacob E. Goodman and Joseph O'Rourke. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004. xviii+1539 pp. ISBN: 1-58488-301-4 MR2082993
  • Kallenberg, Olav. Foundations of modern probability. Second edition. Probability and its Applications (New York). Springer-Verlag, New York, 2002. xx+638 pp. ISBN: 0-387-95313-2 MR1876169
  • Macdonald, I. G. Symmetric functions and Hall polynomials. Second edition. With contributions by A. Zelevinsky. Oxford Mathematical Monographs. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1995. x+475 pp. ISBN: 0-19-853489-2 MR1354144
  • Sagan, Bruce E. The symmetric group. Representations, combinatorial algorithms, and symmetric functions. Second edition. Graduate Texts in Mathematics, 203. Springer-Verlag, New York, 2001. xvi+238 pp. ISBN: 0-387-95067-2 MR1824028
  • Stanley, Richard P. On the number of reduced decompositions of elements of Coxeter groups. European J. Combin. 5 (1984), no. 4, 359--372. MR0782057
  • Williams, David. Probability with martingales. Cambridge Mathematical Textbooks. Cambridge University Press, Cambridge, 1991. xvi+251 pp. ISBN: 0-521-40455-X; 0-521-40605-6 MR1155402

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.