Faster Triangulation Mixing via Transport Flows

We prove an O^e(n²) bound for the relaxation time and the log-Sobolev time (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex (n + 2)-gon, implying a mixing time of O^e(n²). The previous state of the art for the mixing time of this chain due to Eppstein and Frishberg [20] was O^e(n³), while the best known lower bound on the mixing time due to Molloy, Reed and Steiger [36] is Ω(n³/²). Our relaxation time bound makes significant progress towards Aldous' [3] conjectured bound of Θ(n³/²) for the relaxation time. We improve upon the analysis of [20] by further developing the framework of transport flows introduced in the work [13] 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.