Random subnetworks of random sorting networks
A sorting network is a shortest path from the permutation \((12...n)\) to the permutation \((n...21)\) in the Cayley graph of the symmetric group \(S_n\) generated by the nearest-neighbor swaps. For \(m<=n\), consider the random m-particle sorting network obtained by choosing an n-particle sorting network uniformly at random and then observing only the relative order of \(m\) particles chosen uniformly at random. The authors find an exact formula for the expected number of swaps in location j in the subnetwork. It turns out that this expectation does not depend on n. The proof of this fact is probabilistic and is based on a Polya urn construction with non-integer (more precisely, proper half-integer) numbers of balls. The result of the article is closely related to known conjectures about random sorting networks. First, the case \(m=4\) leads to a proof of a conjecture of Warrington (2009). On the other hand, authors show that their result is consistent with the conjectural limiting law of a subnetwork (as \(n\) goes to infinity) implied by the great circle conjecture \textit{O. Angel, A. E. Holroyd, D. Romik, B. Virág} [Adv. Math. 215, No. 2, 839--868 (2007; Zbl 1132.60008)]. In the end of the paper the authors state two more open questions about random sorting networks.
- Circular support in random sorting networks
- Random sorting networks
- A pattern theorem for random sorting networks
- The Archimedean limit of random sorting networks
- The local limit of random sorting networks
- Random permutation graphs and related Markov chains
- Emergence of a giant component in a random permutation with given number of cycles
- Random sorting networks: local statistics via random matrix laws
- A rearrangement inequality for the longest run, with an application to network reliability
- The local limit of random sorting networks
- Absorbing time asymptotics in the oriented swap process
- Milnor invariants of sorting networks
- Sorting networks, staircase Young tableaux, and last passage percolation
- Random sorting networks: local statistics via random matrix laws
- Geometry of permutation limits
- Random sorting networks
- A pattern theorem for random sorting networks
- Relating Edelman-Greene insertion to the Little map
- The Archimedean limit of random sorting networks
- Circular support in random sorting networks
- A combinatorial version of Sylvester's four-point problem
This page was built for publication: Random subnetworks of random sorting networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976676)
