2015/05/25 by Emma Cohen, Cohen, Emma, Prasad Tetali +3
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1505.06710
openalex publication_date 2015/05/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. While our main result is in deriving an O(n2 log n) bound on the mixing time in L2 (and hence total variation) distance for the random transposition chain on 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 lattice path matroids, including the so-called Catalan matroid which can be defined using Dyck paths.