Catalan Shuffles

Catalan numbers arise in many enumerative contexts as the counting sequence of combinatorial structures. In this work, we consider natural Markov chains on some of the realizations of the Catalan sequence, and derive estimates on the mixing time of the corresponding Markov chains. While our main result is an $O(n^2 log n)$ bound on the mixing time for the random transposition chain on the so-called Dyck paths, we raise several open questions, including the optimality of the above bound. The novelty in our proof is in establishing a certain negative correlation property among random bases of the Catalan matroid, for which the Dyck paths form the bases. This is joint work with Damir Yeliussizov (Kazakhstan) and Emma Cohen (Georgia Tech).