DIMACS - RUTGERS EXPERIMENTAL MATHEMATICS SEMINAR

Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Co-organizers:

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu

Lara Pudwell, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu

Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Random Sorting Networks and the Oriented Swap Process

Speaker: Dan Romik, The Hebrew University of Jerusalem

Date: Thursday, September 25, 2008 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

I will talk about two fascinating random models for sorting a list of N numbers from increasing to decreasing order by applying N(N-1)/2 adjacent transpositions. In one model we simply choose uniformly from the list of possible ways to do this, and in the other model we repeatedly choose adjacent transpositions uniformly from the N-1 possibilities and apply them if they bring the list closer to being sorted. Computer simulations (which I will show) enable guessing the asymptotic behavior of the first model as N goes to infinity. But rigorous mathematical analysis (based on the theory of exclusion processes) enables proving almost everything about the second model, and (so far at least) only very little about the first. Based on joint work with Omer Angel, Alexander Holroyd and Balint Virag.