Random subnetworks of random sorting networks (Q976676)

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.