Great-circle conjecture for uniform sorting networks

About 20 years old · traced to

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

d∞(ω,c):=max⁡i∈[1,N]inf⁡z∈c∥σi−1−z∥∞.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 Cn⊂SnC_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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.