Polynomial mixing time of edge flips on quadrangulations

Alessandra Caraceni, Alexandre Stauffer

Research output: Contribution to journalArticlepeer-review

4 Citations (SciVal)


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
Issue number1-2
Early online date22 Apr 2019
Publication statusPublished - 1 Feb 2020


  • math.PR
  • math.CO
  • 60J10

ASJC Scopus subject areas

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


Dive into the research topics of 'Polynomial mixing time of edge flips on quadrangulations'. Together they form a unique fingerprint.

Cite this