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.
Edge flips are a simple dynamic that can be considered on a range of different models, such as planar maps, p-angulations of the sphere, lattice triangulations, and other geometric graphs; iterating random edge flips will eventually yield an almost uniform random structure of a given size — but how many iterations does it take to come reasonably near to stationarity? This proves to be an elusive question even in the (deceptively) simple case of the triangulation walk, for which it remains mostly open.
We will take this problem as a starting point to discuss the mixing and relaxation time of reversible Markov chains. At the same time, we will explore the rich world of planar maps, from surprising combinatorial features to their role as universal models for random surfaces.
Finally, we will present some new results obtained in joint work with Alexandre Stauffer, briefly describing some tools we have developed in order to provide polynomial upper and lower bounds for the mixing time of edge flips on a range of Catalan structures.
My personal website