Journée "Cartes Aléatoires"

Polynomial Mixing Time for Edge Flips via Growing Random Planar Maps

by Alessandra Caraceni (Scuola Normale Superiore of Pisa)

Centre de conférences Marilyn et James Simons (I.H.E.S.)

Centre de conférences Marilyn et James Simons


Le Bois-Marie 35, route de Chartres 91440 Bures-sur-Yvette

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

Organized by

Guillaume Blanc (LMO) & Alice Contat (LMO)