Great-circle conjecture for uniform sorting networks

From papers

Let ωn\omega_n be an nn-element uniform sorting network, let Sn{\mathbb S}_n denote the permutahedron, and let dd_\infty be the distance from a sorting network to a great circle defined by

d(ω,c):=maxi[1,N]infzcσi1z.d_\infty(\omega,c):=\max_{i\in[1,N]}\inf_{z\in c}\|\sigma_i^{-1}-z\|_\infty.

A sequence is o(n)o(n) in probability if its ratio to nn converges to zero in probability. Great circles. For each nn there exists a random great circle CnSnC_n\subset{\mathbb S}_n such that

d(ωn,Cn)=o(n)in probability asn.d_\infty(\omega_n,C_n)=o(n)\quad\text{in probability as}\quad n\to\infty.

If true, this would explain the conjectured sine trajectories, Archimedes limiting configurations, and semicircle-law swap process through the deterministic great-circle theorem stated nearby. The supplied text does not resolve whether uniform sorting networks lie close to random great circles.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Omer Angel, Alexander E. Holroyd, Dan Romik and Balint Virag, “Random Sorting Networks”, arXiv:math/0609538 (2006).

Solutions 0

No solutions have been posted yet.