Polynomial mixing time of edge flips on quadrangulations

Alessandra Caraceni, Alexandre Stauffer

Research output: Contribution to journalArticle

Abstract

We establish the first polynomial upper bound for the mixing time of random edge flips on rooted quadrangulations: we show that the spectral gap of the edge flip Markov chain on quadrangulations with n faces admits, up to constants, an upper bound of n - 5 / 4 and a lower bound of n - 11 / 2 . In order to obtain the lower bound, we also consider a very natural Markov chain on plane trees—or, equivalently, on Dyck paths—and improve the previous lower bound for its spectral gap by Shor and Movassagh.

Original languageEnglish
Pages (from-to)35-76
Number of pages42
JournalProbability Theory and Related Fields
Volume176
Issue number1-2
Early online date22 Apr 2019
DOIs
Publication statusPublished - 28 Feb 2020

Keywords

  • math.PR
  • math.CO
  • 60J10

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Projects

Cite this