arXiv Analytics

Sign in

arXiv:1809.05092 [math.PR]AbstractReferencesReviewsResources

Polynomial mixing time of edge flips on quadrangulations

Alessandra Caraceni, Alexandre Stauffer

Published 2018-09-13Version 1

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.

Related articles: Most relevant | Search more
arXiv:1905.03031 [math.PR] (Published 2019-05-08)
New Lower Bounds for Trace Reconstruction
arXiv:1808.02336 [math.PR] (Published 2018-08-04)
Lower bounds for trace reconstruction
arXiv:1609.09637 [math.PR] (Published 2016-09-30)
A large deviation perspective on exponential decay of entropy and lower bounds on the Ricci-curvature