A pattern theorem for random sorting networks
A pattern theorem for random sorting networks
复制标题
DOI：
10.1214/ejp.v17-2448
复制
发表时间：
2011-10
影响因子：
1.4
通讯作者：
Omer Angel;V. Gorin;A. Holroyd
中科院分区：
文献类型：
--
作者：
Omer Angel;V. Gorin;A. Holroyd
排序网络是由最近邻交换生成的对称群$S_n$的Cayley图中从$12点n$到$n点21$的最短路径。模式是形成某个分类网络的初始段的一系列掉期交易。我们证明了在一个一致随机的$n$元排序网络中，任何固定的模式都出现在至少$cn^2$不相交的时空位置上，其概率趋向于$1$与$n\to\inty$指数级地快。这里的$c$是一个正常数，它取决于模式的选择。因此，均匀随机排序网络几何可实现的概率趋向于$0$。
A sorting network is a shortest path from $12\cdots n$ to $n\cdots 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 $n\to\infty$. 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$.