Abstract
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 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 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.