Return to Colloquia & Seminar listing
Random Sorting NetworksMathematical Physics & Probability
|Speaker: ||Andrew Holroyd, University of British Columbia|
|Location: ||1147 MSB|
|Start time: ||Wed, Apr 30 2008, 4:10PM|
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 behavior 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.