UW-PIMS Colloquia: Random Sorting Networks

Sorting a list of items is perhaps the most familiar problem of computer science. If one must do this by swapping neighbouring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps which achieves this. We consider a uniformly random n-item sorting network. Exact simulations and heuristic arguments have led to a wealth of astonishing conjectures about the n→infinity limit. For instance, the half-time permutation matrix is believed to be circularly symmetric, while the trajectories of items appear to converge to random sine curves; the best known bounds on the permutation matrices and trajectories are much weaker (but still non-trivial). The conjectures fit together into a remarkable geometric picture. I'll also report on some recent progress on local sub-networks and random sub-networks, both of which shed some new light on this picture.

Based on joint works with Omer Angel, Vadim Gorin, Dan Romik and Balint Virag.