Random Sorting Networks
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 neighboring 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.
Speaker Details
Alexander Holroyd has been at UBC since 2003. Previously he was at UC Berkeley for 1 year and UCLA for 3 years. He received his Ph.D. in Cambridge (UK) in 2000.
- Date:
- Speakers:
- Alexander E. Holroyd
- Affiliation:
- University of British Columbia
-
-
Alexander E. Holroyd
Senior Researcher
-
Jeff Running
-