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 |
| _version_ | 1826200387889135616 |
|---|---|
| author | Angel, Omer Gorin, Vadim Holroyd, Alexander E |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Angel, Omer Gorin, Vadim Holroyd, Alexander E |
| author_sort | Angel, Omer |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:35:37Z |
| format | Article |
| id | mit-1721.1/89523 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:35:37Z |
| publishDate | 2014 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/895232022-09-27T20:33:39Z A pattern theorem for random sorting networks Angel, Omer Gorin, Vadim Holroyd, Alexander E Massachusetts Institute of Technology. Department of Mathematics Gorin, Vadim 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. University of Toronto Natural Sciences and Engineering Research Council of Canada Alfred P. Sloan Foundation Microsoft Research Möbius Contest Foundation for Young Scientists Dynasty Foundation Russian Foundation for Basic Research (RFBR-CNRS grant 10-01-93114) Murmansk State Humanities University (“Development of the scientific potential of the higher school”) Simons Foundation (IUM-Simons Foundation scholarship) Independent University of Moscow (IUM-Simons Foundation scholarship) 2014-09-15T14:57:23Z 2014-09-15T14:57:23Z 2012-11 Article http://purl.org/eprint/type/JournalArticle 1083-6489 http://hdl.handle.net/1721.1/89523 Angel, Omer, Vadim Gorin, and Alexander E Holroyd. “A Pattern Theorem for Random Sorting Networks.” Electronic Journal of Probability 17, no. 0 (January 1, 2012). https://orcid.org/0000-0002-9828-5862 en_US http://dx.doi.org/10.1214/EJP.v17-2448 Electronic Journal of Probability Creative Commons Attribution http://creativecommons.org/licenses/by/2.5/ application/pdf Institute of Mathematical Statistics Institute of Mathematical Statistics |
| spellingShingle | Angel, Omer Gorin, Vadim Holroyd, Alexander E A pattern theorem for random sorting networks |
| title | A pattern theorem for random sorting networks |
| title_full | A pattern theorem for random sorting networks |
| title_fullStr | A pattern theorem for random sorting networks |
| title_full_unstemmed | A pattern theorem for random sorting networks |
| title_short | A pattern theorem for random sorting networks |
| title_sort | pattern theorem for random sorting networks |
| url | http://hdl.handle.net/1721.1/89523 https://orcid.org/0000-0002-9828-5862 |
| work_keys_str_mv | AT angelomer apatterntheoremforrandomsortingnetworks AT gorinvadim apatterntheoremforrandomsortingnetworks AT holroydalexandere apatterntheoremforrandomsortingnetworks AT angelomer patterntheoremforrandomsortingnetworks AT gorinvadim patterntheoremforrandomsortingnetworks AT holroydalexandere patterntheoremforrandomsortingnetworks |