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)1-42
Number of pages42
JournalProbability Theory and Related Fields
Early online date22 Apr 2019
DOIs
Publication statusE-pub ahead of print - 22 Apr 2019

Keywords

  • math.PR
  • math.CO
  • 60J10

ASJC Scopus subject areas

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

Cite this

Polynomial mixing time of edge flips on quadrangulations. / Caraceni, Alessandra; Stauffer, Alexandre.

In: Probability Theory and Related Fields, 22.04.2019, p. 1-42.

Research output: Contribution to journalArticle

@article{8ee8bd49ab1847f7b594ff39ef6610c7,
title = "Polynomial mixing time of edge flips on quadrangulations",
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.",
keywords = "math.PR, math.CO, 60J10",
author = "Alessandra Caraceni and Alexandre Stauffer",
year = "2019",
month = "4",
day = "22",
doi = "10.1007/s00440-019-00913-5",
language = "English",
pages = "1--42",
journal = "Probability Theory and Related Fields",
issn = "0178-8051",
publisher = "Springer New York",

}

TY - JOUR

T1 - Polynomial mixing time of edge flips on quadrangulations

AU - Caraceni, Alessandra

AU - Stauffer, Alexandre

PY - 2019/4/22

Y1 - 2019/4/22

N2 - 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.

AB - 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.

KW - math.PR

KW - math.CO

KW - 60J10

UR - http://www.scopus.com/inward/record.url?scp=85064620293&partnerID=8YFLogxK

U2 - 10.1007/s00440-019-00913-5

DO - 10.1007/s00440-019-00913-5

M3 - Article

SP - 1

EP - 42

JO - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

SN - 0178-8051

ER -