Angel, Omer; Holroyd, Alexander E. Random subnetworks of random sorting networks. (English) Zbl 1197.60003 Electron. J. Comb. 17, No. 1, Research Paper N23, 7 p. (2010). 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 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. Reviewer: Leonid Petrov (Moscow) Cited in 6 Documents MSC: 60C05 Combinatorial probability 68P10 Searching and sorting Keywords:random sorting network; reduced word; Polya urn; great circle conjecture Citations:Zbl 1132.60008 PDFBibTeX XMLCite \textit{O. Angel} and \textit{A. E. Holroyd}, Electron. J. Comb. 17, No. 1, Research Paper N23, 7 p. (2010; Zbl 1197.60003) Full Text: arXiv EuDML EMIS