A pattern theorem for random sorting networks

DOI10.1214/EJP.V17-2448MaRDI QIDQ392684zbMATH OpenOpenAlexFDO

Authors Omer Angel, Vadim Gorin, A. E. Holroyd

Publication date 15 January 2014

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0160

zbMATH Keywords

patternrandom sortingreduced wordsorting networkYoung tableau

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10) Combinatorial probability (60C05) Searching and sorting (68P10)

Abstract: A sorting network is a shortest path from 12..n to n..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 cn^2 disjoint space-time locations, with probability tending to 1 exponentially fast as n tends to infinity. 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.

Recommendations

• Random sorting networks
• Random subnetworks of random sorting networks
• The local limit of random sorting networks
• The Archimedean limit of random sorting networks
• Random sorting networks: local statistics via random matrix laws
• Sorting networks on restricted topologies
• Sorting and counting networks of arbitrary width and small depth
• RANDOMIZED SORTING ON THE POPS NETWORK
• Sorting networks, staircase Young tableaux, and last passage percolation
• scientific article; zbMATH DE number 1263220

Cited in

(13)

• The local limit of random sorting networks
• On collisions times of `self-sorting' interacting particles in one-dimension with random initial positions and velocities
• Absorbing time asymptotics in the oriented swap process
• Sorting networks, staircase Young tableaux, and last passage percolation
• Random sorting networks: local statistics via random matrix laws
• Geometry of permutation limits
• Shift-invariance of the colored TASEP and finishing times of the oriented swap process
• Relating Edelman-Greene insertion to the Little map
• The Archimedean limit of random sorting networks
• Circular support in random sorting networks
• Random sorting networks: edge limit
• Underlying flag polymatroids
• Random subnetworks of random sorting networks

This page was built for publication: A pattern theorem for random sorting networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392684)