Random subnetworks of random sorting networks

Omer Angel ; Alexander E. Holroyd

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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.

Détail

DOI : 10.37236/472

Classification : 60C05, 68P10
Mots-clés : random sorting network, reduced word, Polya urn, great circle conjecture