## 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.

### MSC:

 60C05 Combinatorial probability 05E10 Combinatorial aspects of representation theory 68P10 Searching and sorting

### Keywords:

sorting network; random sorting; reduced word; pattern; Young tableau
Full Text: