Adjacency distribution conjecture for random sorting networks

Let Yn(α)Y_n(\alpha) and Xn(α)X_n(\alpha) denote the number of adjacencies 1k<α(n2)1\leq k<\alpha\binom{n}{2} in a random sorting network and in a random 132132-avoiding sorting network of size nn, respectively. Here α[0,1]\alpha\in[0,1], and let g:[0,1]Rg:[0,1]\to\mathbb{R} be defined by

g(α)={α2if α[0,12],11α2if α[12,1].g(\alpha)= \begin{cases} \sqrt{\frac{\alpha}{2}}&\quad\text{if }\alpha\in[0,\frac{1}{2}],\\ 1-\sqrt{\frac{1-\alpha}{2}}&\quad\text{if }\alpha\in[\frac{1}{2},1]. \end{cases}

Adjacency distribution conjecture. The random sorting-network statistic satisfies Yn(α)/E[Yn(1)]cαY_n(\alpha)/\mathbb{E}[Y_n(1)]\to c\alpha in probability for some constant cc, and the random 132132-avoiding sorting-network statistic satisfies

limnP(max0α1Xn(α)2(n2)g(α)>ϵ)=0.\lim_{n\to\infty}\mathbb{P}\left(\max_{0\leq\alpha\leq 1}\left|\frac{X_n(\alpha)}{2(n-2)}-g(\alpha)\right|>\epsilon\right)=0.

The claim predicts linear growth of the normalized adjacency count in random sorting networks and a deterministic, piecewise-square-root limiting profile in random 132132-avoiding sorting networks. The surrounding discussion says that these behaviors are suggested by experiments; no resolution is given here.

Sources & referencesView supporting material

Primary source

Svante Linusson, Samu Potka and Robin Sulzgruber, “On random shifted standard Young tableaux and 132-avoiding sorting networks”, arXiv:1804.01795 (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.