This website uses features that are not well-supported by your browser. Please consider upgrading to a browser and version that fully supports CSS Grid and the CSS Flexible Box Layout Module.
Sidebar image
NB: A PDF version of this announcement (suitable for posting) is also available.

Random sorting networks

Alexander E. Holroyd
Microsoft Research

Thursday, October 18, 2012
007 Kemeny Hall, 4 pm
Tea 3:30 pm, 300 Kemeny Hall

Abstract: Sorting a list of items is one of the most familiar algorithmic problems. If one must do it 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 that achieves this. We address the question: what does a typical (i.e. uniformly random) n-item sorting network look like? Exact simulations and heuristic arguments have led to a wealth of astonishing conjectures about the n -> infinity limit. For instance, the half-time permutation matrix is believed to be circularly symmetric, while the trajectories of items appear to converge to random sine curves; the best known bounds on the permutation matrices and trajectories are much weaker (but still non-trivial), and arise from a connection with Young tableaux. The conjectures fit together into a remarkable geometric picture. I'll also report on some recent progress on local sub-networks and random sub-networks, both of which shed some new light on this picture. Based on joint works with Omer Angel, Vadim Gorin, Dan Romik and Balint Virag. See for pictures.

This talk will be accessible to graduate students.