Mixing of branch rotation and triangulation chains

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Consider the following two discrete-time finite reversible Markov chains. In the triangulation chain, a state is a triangulation of a convex regular $n$-gon. At each step choose one of its $n-3$ interior diagonals uniformly, remove it to expose a quadrilateral, and insert the other diagonal of that quadrilateral. In the cladogram chain, states are rooted binary trees with $n$ leaves labeled $1,\ldots,n$, unlabeled internal vertices and no ordering of left and right subtrees; a stem edge above the root is included, giving $2n-1$ edges. Choose uniformly an edge other than that stem edge. Detach its descendant subtree at its upper endpoint and suppress the resulting degree-two vertex, producing an edge $e$. For each of the at most four edges adjacent to $e$, reattach the detached subtree at that edge's midpoint with probability $1/4$; any remaining probability makes no change. Both chains have uniform stationary law. If $1=\lambda_1>\lambda_2$ are their largest two transition eigenvalues, define relaxation time by $t_{\rm rel}=(1-\lambda_2)^{-1}$.

Statement recorded in the supplied source.

For each of these two chains, prove that $t_{\rm rel}\le Cn^{3/2}$ for some constant $C$ independent of $n$, matching the order-$n^{3/2}$ lower bound. [S2]

Short English statement

Prove sharp relaxation-time bounds for polygon diagonal flips and local branch rotations of labeled cladograms.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 9700012 (AMR-096-0012). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 David J. Aldous, Mixing Times for the Branch-Rotation Chain on Cladograms (or the Triangulation Walk), State-space and transition definitions, pp. 1--2, and PROBLEM, p. 2. https://www.stat.berkeley.edu/~aldous/Research/OP/clad-mix.pdf.