Faster Mixing for Triangulations via Transport Flows

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

arXivarxiv/2605.02067May 3, 2026math.COscore 0

We prove an $\widetilde O(n^2)$ 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 $\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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.02067
curl -X POST /api/v1/records/arxiv/2605.02067/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.02067/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'