Polynomial mixing time of edge flips on quadrangulations

2018/09/13 by Caraceni, Alessandra, Stauffer, Alexandre
#60J10 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1809.05092

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.

Related

• A polynomial upper bound for the mixing time of edge rotations on planar maps
• Mixing time bounds for edge flipping on regular graphs
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic\n tilings
• Mixing time bounds for edge flipping on regular graphs
• Faster Mixing of the Jerrum-Sinclair Chain