Random Sorting Networks

  • Date: 12/04/2006

Alexander Holroyd (University of British Columbia)


University of British Columbia


See http://www.math.ubc.ca/~holroyd/sort for pictures.

Joint work with Omer Angel, Dan Romik and Balint Virag.

Sorting a list of items is perhaps the most celebrated problem in
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 investigate the behaviour of a uniformly random n-item sorting
network as n->infinity. We prove a law of large numbers for the
space-time process of swaps. Exact simulations and heuristic arguments
have led us to astonishing conjectures. For example, the half-time
permutation matrix appears to be circularly symmetric, while the
trajectories of individual items appear to converge to a famous family
of smooth curves. We prove the more modest results that,
asymptotically, the support of the matrix lies within a certain
octagon, while the trajectories are Holder-1/2. A key tool is a
connection with Young tableaux.

Other Information: 

Probability Seminar 2006