作者：Caraceni, Alessandra; Stauffer, Alexandre
作者单位：University of Bath
摘要：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.
