A polynomial upper bound for the mixing time of edge rotations on planar maps
A polynomial upper bound for the mixing time of edge rotations on planar maps
复制标题
DOI：
10.1214/20-ejp519
复制
发表时间：
2020-01
影响因子：
1.4
通讯作者：
Alessandra Caraceni
中科院分区：
文献类型：
--
作者：
Alessandra Caraceni
我们考虑具有$n$边的所有有根平面映射的集合上的一个自然局部动态，它在某种意义上类似于以前在各种组合结构($n$-边的三角剖分和球面的四边形剖分等)上已被考虑的“边翻转”马尔可夫链。我们给出了平面映射上“边旋转”链混合时间的第一个多项式上界：我们证明了边旋转链的谱间隙在一个适当的常数倍$n^-11/2}下有界.通过这样做，我们提供了一个部分新的证明，证明了同样的界限也适用于四边形上的边翻转的谱间隙，这使得作者和Stauffer最近的一个结果可以推广到通过Tutte双射与边旋转有关的链。
We consider a natural local dynamic on the set of all rooted planar maps with $n$ edges that is in some sense analogous to "edge flip" Markov chains, which have been considered before on a variety of combinatorial structures (triangulations of the $n$-gon and quadrangulations of the sphere, among others). We provide the first polynomial upper bound for the mixing time of this "edge rotation" chain on planar maps: we show that the spectral gap of the edge rotation chain is bounded below by an appropriate constant times $n^{-11/2}$. In doing so, we provide a partially new proof of the fact that the same bound applies to the spectral gap of edge flips on quadrangulations, which makes it possible to generalise a recent result of the author and Stauffer to a chain that relates to edge rotations via Tutte's bijection.