A long-standing problem proposed by David Aldous consists in giving a sharp upper bound for the mixing time of the so-called “triangulation walk”, a Markov chain defined on the set of all possible triangulations of the regular n-gon. A single step of the chain consists in performing a random edge flip, i.e. in choosing an (internal) edge of the triangulation uniformly at random and, with probability 1/2, replacing it with the other diagonal of the quadrilateral formed by the two triangles adjacent to the edge in question (with probability 1/2, the triangulation is left unchanged).
While it has been shown that the relaxation time for the triangulation walk is polynomial in n and bounded below by a multiple of n^{3/2}, the conjectured sharpness of the lower bound remains firmly out of reach in spite of the apparent simplicity of the chain. For edge flip chains on different models -- such as planar maps, quadrangulations of the sphere, lattice triangulations and other geometric graphs -- even less is known.
We shall discuss results concerning the mixing time of random edge flips on rooted quadrangulations of the sphere, partly obtained in joint work with Alexandre Stauffer. A “growth scheme” for quadrangulations which generates a uniform quadrangulation of the sphere by adding faces one at a time at appropriate random locations can be combined with careful combinatorial constructions to build probabilistic canonical paths in a relatively novel way. This method has immediate implications for a range of interesting edge-manipulating Markov chains on so-called Catalan structures, from “leaf translations” on plane trees to “edge rotations” on general planar maps. Moreover, we are able to apply it to flips on 2p-angulations and simple triangulation of the sphere, via newly developed “growth schemes”.
Guillaume Blanc (LMO) & Alice Contat (LMO)
