

























A sorting network (also known as a reduced decomposition of the reverse permutation), is a shortest path from $12 \cdots n$ to $n \cdots 21$ in the Cayley graph of the symmetric group $S_n$ generated by adjacent transpositions. We prove that in a uniform random $n$-element sorting network $σ^n$, all particle trajectories are close to sine curves with high probability. We also find the weak limit of the time-$t$ permutation matrix measures of $σ^n$. As a corollary of these results, we show that if $S_n$ is embedded into $\mathbb{R}^n$ via the map $τ\mapsto (τ(1), τ(2), \dots τ(n))$, then with high probability, the path $σ^n$ is close to a great circle on a particular $(n-2)$-dimensional sphere in $\mathbb{R}^n$. These results prove conjectures of Angel, Holroyd, Romik, and Virag.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。