Faster Mixing for Triangulations via Transport Flows
For researchers in Markov chain mixing and combinatorial enumeration, this work provides a tighter analysis of a fundamental chain, making progress on a long-standing conjecture.
The paper proves an $\\widetilde O(n^2)$ bound for the relaxation time and log-Sobolev time of the triangulation flip chain on a convex $(n+2)$-gon, improving the previous $\\widetilde O(n^3)$ bound and narrowing the gap to the conjectured $\\Theta(n^{3/2})$.
We prove an $\widetilde O(n^2)$ bound for the \emph{relaxation time} and the \emph{log-Sobolev time} (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex $(n+2)$-gon, implying a mixing time of $\widetilde O(n^2)$. The previous state of the art for the mixing time of this chain, due to Eppstein and Frishberg, was $\widetilde O(n^3)$, while the best known lower bound on the mixing time, due to Molloy, Reed, and Steiger, is $Ω(n^{3/2})$. Our relaxation time bound makes significant progress towards Aldous' conjectured bound of $Θ(n^{3/2})$ for the relaxation time. We improve upon the analysis of Eppstein and Frishberg by further developing the framework of \emph{transport flows} introduced in the work of Chen et al. In this light, our results can be seen as a more efficient way of using combinatorial decompositions to obtain functional inequalities for Markov chains. We hope our ideas will find other applications in the future.