Colloquium
3:00 p.m., Friday (March 9)
Math Annex 1100
Ander Holroyd
UBC
Random Sorting Networks
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 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 nitem sorting network as n>infinity. We prove a law of large numbers for the spacetime process of swaps. Exact simulations and heuristic arguments have led us to astonishing conjectures. For example, the halftime 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 Holder1/2. A key tool is a connection with Young tableaux.
Refreshments will be served at 2:45 p.m. in the Faculty Lounge,
Math Annex (Room 1115).
