Prefer a chat interface with context about you and your work?
A pattern theorem for random sorting networks
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 …