Faster Mixing for Triangulations via Transport Flows
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918519812128768 |
|---|---|
| author | Alev, Vedat Levi Frishberg, Daniel Sarantis, Michail Tetali, Prasad |
| author_facet | Alev, Vedat Levi Frishberg, Daniel Sarantis, Michail Tetali, Prasad |
| contents | 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 upon the analysis of Eppstein and Frishberg by further developing the framework of 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_02067 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster Mixing for Triangulations via Transport Flows Alev, Vedat Levi Frishberg, Daniel Sarantis, Michail Tetali, Prasad Combinatorics Computational Geometry Discrete Mathematics Data Structures and Algorithms 05 G.2; G.3; F.2.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 upon the analysis of Eppstein and Frishberg by further developing the framework of 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. |
| title | Faster Mixing for Triangulations via Transport Flows |
| topic | Combinatorics Computational Geometry Discrete Mathematics Data Structures and Algorithms 05 G.2; G.3; F.2.0 |
| url | https://arxiv.org/abs/2605.02067 |