
arXiv: 0911.2519
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.
random sorting network, Combinatorial probability, Polya urn, Probability (math.PR), great circle conjecture, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Searching and sorting, reduced word, Mathematics - Probability, 60C05, 05E10, 68P10
random sorting network, Combinatorial probability, Polya urn, Probability (math.PR), great circle conjecture, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Searching and sorting, reduced word, Mathematics - Probability, 60C05, 05E10, 68P10
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
