Exponential concentration conjecture for sorting-network permutation measures

About 8 years old · traced to

Let Archt\mathfrak{Arch}_t be the Archimedean path of probability measures on [−1,1]2[-1,1]^2, and let ηtn\eta_t^n be the time-tt permutation-matrix measure of an nn-element uniform random sorting network. Let UU be an open set in the space of probability measures on [−1,1]2[-1,1]^2 with the weak topology, containing every Archt\mathfrak{Arch}_t.

Exponential concentration conjecture. There exist constants c1,c2>0c_1,c_2>0 such that, for every nn,

P(there exists t∈[0,1] such that ηtn∉U)≤c1e−c2n2.\mathbb{P}\left(\text{there exists }t\in[0,1]\text{ such that }\eta_t^n\notin U\right)\le c_1e^{-c_2n^2}.

This strengthens convergence to the Archimedean path from a fixed-time statement to uniform-in-time exponential concentration; the paper presents it as an open problem.

References

Primary source

Duncan Dauvergne and Bálint Virág, “Circular support in random sorting networks”, arXiv:1802.08933 (2018).

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.