Random Subnetworks of Random Sorting Networks

A sorting network is a shortest path from 12 · · · n to n · · · 21 in the Cayley graph of Sn generated by 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. 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 Polya urn with noninteger 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 → ∞ implied by the great circle conjecture Angel, Holroyd, Romik and Virag.