The local limit of random sorting networks

Omer Angel, Duncan Dauvergne, Alexander E. Holroyd, Bálint Virág

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

A sorting network is a geodesic path from 12 · · · n to n · · · 21 in the Cayley graph of Sn generated by adjacent transpositions. For a uniformly random sorting network, we establish the existence of a local limit of the process of space–time locations of transpositions in a neighbourhood of an for a ∈ [0, 1] as n → ∞. Here time is scaled by a factor of 1/n and space is not scaled. The limit is a swap process U on 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 a(1 − a). To establish the existence of U, we find a local limit for staircase-shaped Young tableaux. These Young tableaux are related to sorting networks through a bijection of Edelman and Greene.

Original languageEnglish (US)
Pages (from-to)412-440
Number of pages29
JournalAnnales de l'institut Henri Poincare (B) Probability and Statistics
Volume55
Issue number1
DOIs
StatePublished - Feb 2019
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Keywords

  • Local limit
  • Random sorting network
  • Reduced decomposition
  • Sorting network
  • Young tableau

Fingerprint Dive into the research topics of 'The local limit of random sorting networks'. Together they form a unique fingerprint.

Cite this