License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.56
URN: urn:nbn:de:0030-drops-181081
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18108/
Go to the corresponding LIPIcs Volume Portal

Eppstein, David ; Frishberg, Daniel

Improved Mixing for the Convex Polygon Triangulation Flip Walk

pdf-format:
LIPIcs-ICALP-2023-56.pdf (1 MB)

Abstract

We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n³ log³ n), the first progress since McShine and Tetali’s O(n⁵ log n) bound in 1997. In the process we give lower and upper bounds of respectively Ω(1/(√n log n)) and O(1/√n) - asymptotically tight up to an O(log n) factor - for the expansion of the associahedron graph K_n. The upper bound recovers Molloy, Reed, and Steiger’s Ω(n^(3/2)) bound on the mixing time of the walk. To obtain these results, we introduce a framework consisting of a set of sufficient conditions under which a given Markov chain mixes rapidly. This framework is a purely combinatorial analogue that in some circumstances gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda. In particular, in addition to the result for triangulations, we show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k ≥ 4.

BibTeX - Entry

@InProceedings{eppstein_et_al:LIPIcs.ICALP.2023.56,
  author =	{Eppstein, David and Frishberg, Daniel},
  title =	{{Improved Mixing for the Convex Polygon Triangulation Flip Walk}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18108},
  URN =		{urn:nbn:de:0030-drops-181081},
  doi =		{10.4230/LIPIcs.ICALP.2023.56},
  annote =	{Keywords: associahedron, mixing time, mcmc, Markov chains, triangulations, quadrangulations, k-angulations, multicommodity flow, projection-restriction}
}

Keywords: associahedron, mixing time, mcmc, Markov chains, triangulations, quadrangulations, k-angulations, multicommodity flow, projection-restriction
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI