2026-07-20T05:45:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26401 2026-07-01T07:16:09Z ddc:004 open_access

Faster Triangulation Mixing via Transport Flows Alev, Vedat Levi Frishberg, Daniel Sarantis, Michail Tetali, Prasad triangulations mixing time log-Sobolev inequality spectral gap Markov chain random walk MCMC transport flow multicommodity flow We prove an Õ(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 Õ(n²). The previous state of the art for the mixing time of this chain due to Eppstein and Frishberg [Eppstein and Frishberg, 2023] was Õ(n³), while the best known lower bound on the mixing time due to Molloy, Reed and Steiger [Molloy et al., 1997] is Ω(n^{3/2}). Our relaxation time bound makes significant progress towards Aldous' [Aldous, 2003] conjectured bound of Θ(n^{3/2}) for the relaxation time. We improve upon the analysis of [Eppstein and Frishberg, 2023] by further developing the framework of transport flows introduced in the work [Xiaoyu Chen et al., 2025] 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vedat Levi Alev and Daniel Frishberg and Michail Sarantis and Prasad Tetali 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.12 urn:nbn:de:0030-drops-264011 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.12 eng https://creativecommons.org/licenses/by/4.0/legalcode