Exponential concentration conjecture for sorting-network permutation measures

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 ηtnU)c1ec2n2.\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.

Sources & referencesView supporting material

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.