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 obtained by Shor and Movassagh.
LanguageEnglish
JournalProbability Theory and Related Fields
Early online date22 Apr 2019
DOIs
StatusE-pub ahead of print - 22 Apr 2019

Keywords

  • math.PR
  • math.CO
  • 60J10

Cite this

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

In: Probability Theory and Related Fields, 22.04.2019.

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 obtained 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",
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 obtained 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 obtained by Shor and Movassagh.

KW - math.PR

KW - math.CO

KW - 60J10

U2 - 10.1007/s00440-019-00913-5

DO - 10.1007/s00440-019-00913-5

M3 - Article

JO - Probability Theory and Related Fields

T2 - Probability Theory and Related Fields

JF - Probability Theory and Related Fields

SN - 0178-8051

ER -