UC Irvine

We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n3 log3 n), the first progress since McShine and Tetali’s O(n5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Ω(1/(√nlog n)) and O(1/√n) – asymptotically tight up to an O(log n) factor – for the expansion of the associahedron graph Kn. The upper bound recovers Molloy, Reed, and Steiger’s Ω(n3/2) bound on the mixing time of the walk. To obtain these results, we introduce a framework consisting of a set of sufficient conditions under which a given Markov chain mixes rapidly. This framework is a purely combinatorial analogue that in some circumstances gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda. In particular, in addition to the result for triangulations, we show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k ≥ 4.