A pattern theorem for random sorting networks
A sorting network is a shortest path from 12⋯n to n⋯21 in the Cayley graph of the symmetric group S[subscript 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,...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Mathematical Statistics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89523 https://orcid.org/0000-0002-9828-5862 |
| Summary: | A sorting network is a shortest path from 12⋯n to n⋯21 in the Cayley graph of the symmetric group S[subscript 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[superscript 2] disjoint space-time locations, with probability tending to 1 exponentially fast as n→∞. 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. |
|---|