Polynomial mixing time of edge flips on quadrangulations

• 成果类型: Article
• 署名作者: Caraceni, Alessandra; Stauffer, Alexandre
• 署名单位: University of Bath
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-019-00913-5
• 发表日期: 2020
• 页码: 35-76
• 关键词: markov-chain; plane

摘要

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.