A long-standing problem proposed by David Aldous is that of 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.

In the first talk, we describe various “edge flip” Markov chains, from Aldous’ triangulation walk to edge flips on lattice triangulations and planar maps. We discuss the challenges posed by estimating their mixing time, give an overview of existing results and describe a strategy for proving lower bounds.

In the second talk, we describe a construction of probabilistic canonical paths that yields polynomial upper bounds for the mixing time of several edge flip chains. The method we present relies on the existence of “growth schemes” for the combinatorial objects involved, so we shall in turn discuss the problem of growing uniform random quadrangulations and triangulations “face by face”, presenting some results and implications.