Faster Mixing for Triangulations via Transport Flows

Vedat Levi Alev, Daniel Frishberg, Michail Sarantis, Prasad Tetali · 2026

Read Faster Mixing for Triangulations via Transport Flows by Vedat Levi Alev, Daniel Frishberg, Michail Sarantis, Prasad Tetali (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-02067.txt.

Description

Vedat Levi Alev, Daniel Frishberg, Michail Sarantis, and Prasad Tetali bound how fast random flips mix among triangulations of a convex polygon. The flip chain moves between ways to cut a polygon into triangles. Past work gave a mixing time near the cube of the size, while the best lower bound sits near size to the power three halves.

The authors prove a relaxation and log-Sobolev time near size squared, up to log factors, which gives the same order for mixing. That moves toward Aldous's conjectured order. Their advance develops transport flow methods further, using combinatorial decompositions to get functional inequalities for Markov chains more efficiently. They suggest the ideas may serve other chains.

Catalog record

CREATORVedat Levi Alev, Daniel Frishberg, Michail Sarantis, Prasad Tetali
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE119 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.02067

Browse the full library · About the Tower of Babel