On the mixing time of the flip walk on triangulations of the sphere

Abstract

A simple way to sample a uniform triangulation of the sphere with a fixed number $n$ of vertices is a Monte-Carlo method: we start from an arbitrary triangulation and flip repeatedly a uniformly chosen edge. We give a lower bound in $n^{5/4}$ on the mixing time of this Markov chain.

arXiv comment10 pages, 2 figures. Published version