科研之友
微信
新浪微博
Facebook
分享链接
摘要
A sorting network is a shortest path from 1 2 ... n to n ... 2 1 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 cn(2) disjoint space-time locations, with probability tending to 1 exponentially fast as n -> infinity. 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
- 出版日期2012-11-19
- 单位Microsoft
