go-v.orgdoi

Random Subnetworks of Random Sorting Networks

Omer Angel, Alexander E. Holroyd · The Electronic Journal of Combinatorics · 2010

  • DOI 10.37236/472
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2010

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2010

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.

Open the resolved locator · 10.37236/472

Metadata licence: OpenAlex metadata (CC0)