Local trajectory reconstruction conjecture for sorting networks

Let σn\sigma^n be an nn-element uniform random sorting network, let JnJ_n be uniform on 1,,n{1,\mathellipsis,n}, and let Stn(Jn,)S_t^n(J_n,\cdot) be the unique curve of the form Asin(πs+Θ)A\sin(\pi s+\Theta) satisfying

Stn(Jn,0)=σGn(Jn,0),Stn(Jn,t)=σGn(Jn,t).S_t^n(J_n,0)=\sigma_G^n(J_n,0),\qquad S_t^n(J_n,t)=\sigma_G^n(J_n,t).

Local trajectory reconstruction conjecture. For every ϵ>0\epsilon>0, there exists C>0C>0 such that

lim infnP(σGn(Jn,)SC/nn(Jn,)u<ϵ)1ϵ.\liminf_{n\to\infty}\mathbb{P}\left(\|\sigma_G^n(J_n,\cdot)-S_{C/n}^n(J_n,\cdot)\|_u<\epsilon\right)\ge1-\epsilon.

This predicts that observing a randomly chosen particle after only order nn steps determines its full trajectory with high probability; 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.