**Title:** Random Sorting

**Speaker:** Professor Alexander Holroyd

**Speaker Info:** University of British Columbia

**Brief Description:**

**Special Note**:

**Abstract:**

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

Copyright © 1997-2024 Department of Mathematics, Northwestern University.