UC Irvine

We prove that the well-studied triangulation flip walk on a convex point set mixes in time O(n^3 log^3 n), the first progress since McShine and Tetali’s O(n^5 log n) bound in 1997. In the process we give lower and upper bounds of respectively Omega(1/(sqrt(n) log n)) and O(1/sqrt(n))---asymptotically tight up to an O(log n) factor---for the expansion of the associahedron graph K_n---the first o(1) expansion result for this graph. We show quasipolynomial mixing for the k-angulation flip walk on a convex point set, for fixed k >= 4, and a treewidth result for the flip graph on n x n lattice triangulations.

We show that the hardcore Glauber dynamics---a random walk on the independent sets of an input graph---mixes rapidly in graphs of bounded treewdith for all fixed values of the standard parameter lambda > 0, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets and b-edge covers (for fixed b >= 1 and lambda > 0) in bounded-treewidth graphs, and for Markov chains on the b-matchings (for fixed b >= 1 and lambda > 0), the maximal independent sets, and the maximal b-matchings of a graph (for fixed b >= 1), in graphs of bounded carving width.

To obtain these results, we introduce a decomposition framework for showing rapid Markov chain mixing. This framework is a purely combinatorial analogue that in some settings gives better results than the projection-restriction technique of Jerrum, Son, Tetali, and Vigoda.