A sorting network is a shortest path from $12cdots n$ to $ncdots 21$ in the Cayley graph of the symmetric group $S_n$ generated by nearest-neighbor swaps. A pattern is a sequence of swaps that forms an initial segment of some sorting network. We prove that in a uniformly random $n$-element sorting network, any fixed pattern occurs in at least $c n^2$ disjoint space-time locations, with probability tending to $1$ exponentially fast as $noinfty$. Here $c$ is a positive constant which depends on the choice of pattern. As a consequence, the probability that the uniformly random sorting network is geometrically realizable tends to $0$.
展开▼
机译：在最近邻交换生成的对称组$ S_n $的Cayley图中，排序网络是从$ 12 cdots n $到$ n cdots 21 $的最短路径。模式是一系列交换的序列，形成某些分类网络的初始部分。我们证明，在均匀随机的$ n $元素排序网络中，任何固定模式至少在$ c n ^ 2 $个不相交的时空位置中发生，概率往往以$ n to infty $指数速度增长。 $ c $是一个正常数，取决于模式的选择。结果，统一随机分类网络在几何上可实现的可能性趋于$ 0 $。
展开▼
