Markov Chains, CAT(0) Cube Complexes, and Enumeration: Monotone Paths in a Strip Mix Slowly
Abstract
Abstract We prove that two natural Markov chains on the set of monotone paths in a strip mix slowly. To do so, we make novel use of the theory of non-positively curved (CAT(0)) cubical complexes to detect small bottlenecks in many graphs of combinatorial interest. Along the way, we give a formula for the number $c_{m}(n)$ of monotone paths of length $n$ in a strip of height $m$. In particular, we compute the exponential growth constant of $c_{m}(n)$ for arbitrary $m$, generalizing results of Williams for $m=2, 3$.
Fields of Study & Subjects
Advanced Combinatorial Mathematics
Probability and Statistical Research
Stochastic processes and statistical mechanics
Publication details
- Journal / source
- International Mathematics Research Notices
- Volume
- 2026
- Issue
- 4
- Publication date
- 11 January 2026
- Language
- EN