Random Subnetworks of Random Sorting Networks

Abstract

A sorting network is a shortest path from $12\cdots n$ to $n\cdots21$ in the Cayley graph of $S_n$ generated by nearest-neighbor swaps. For $m\leq 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. We prove that the expected number of swaps in location $j$ in the subnetwork does not depend on $n$, and we provide a formula for it. Our proof is probabilistic, and involves a Pólya urn with non-integer numbers of balls. From the case $m=4$ we obtain a proof of a conjecture of Warrington. Our result is consistent with a conjectural limiting law of the subnetwork as $n\to\infty$ implied by the great circle conjecture of Angel, Holroyd, Romik and Virág.