Catalan Shuffles

Combinatorics Seminar
Tuesday, January 13, 2015 - 12:05pm
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech
Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. We consider natural local moves on some realizations of the Catalan sequence and derive estimates of the mixing time of the corresponding Markov chains. We present a new O(n^2 log n) bound on the mixing time for the random transposition chain on Dyck paths, and raise several open problems, including the optimality of the above bound.  (Joint work with Prasad Tetali and Damir Yelliusizov.)