Adjacency distribution conjecture for random sorting networks
Adjacency distribution conjecture for random sorting networks
Let and denote the number of adjacencies in a random sorting network and in a random -avoiding sorting network of size , respectively. Here , and let be defined by
Adjacency distribution conjecture. The random sorting-network statistic satisfies in probability for some constant , and the random -avoiding sorting-network statistic satisfies
The claim predicts linear growth of the normalized adjacency count in random sorting networks and a deterministic, piecewise-square-root limiting profile in random -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.