A pattern theorem for random sorting networks. (English) Zbl 1284.60021

Summary: 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 the pattern. As a consequence, the probability that the uniformly random sorting network is geometrically realizable tends to 0.


60C05 Combinatorial probability
05E10 Combinatorial aspects of representation theory
68P10 Searching and sorting
Full Text: DOI arXiv