A long-standing problem proposed by David Aldous consists in giving a sharp upper bound for the mixing time of the so-called \u201ctriangulation walk\u201d, 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 \u2013 such as planar maps, quadrangulations of the sphere, lattice triangulations and other geometric graphs \u2013 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 \u201cgrowth scheme\u201d 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 \u201cleaf translations\u201d on plane trees to \u201cedge rotations\u201d on general planar maps. <\/p>\n","protected":false},"excerpt":{"rendered":"
A long-standing problem proposed by David Aldous consists in giving a sharp upper bound for the mixing time of the so-called \u201ctriangulation walk\u201d, a Markov chain defined on the set of all possible triangulations of the regular n-gon. A single step…<\/p>\n