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.

How could one define a “uniform random continuous path” in d dimensions? A natural answer is given by Brownian motion, a stochastic process that arises as a limit of discrete random walks in R^d, appropriately rescaled in space and time. This will be our first example of a “scaling limit”.

Planar maps are planar graphs “drawn” on the surface of the sphere. What does a large random planar map look like? A first step will be to study plane trees, maps with a single face: what does a large plane tree look like? The procedure of taking scaling limits is an amazingly fruitful tool in this context; it highlights a connection to Brownian motion and sparks a beautiful theory of “continuous” random geometries, with far-reaching implications in several fields of Mathematics and Physics.

Programma

The local limit of random quadrangulations (UIPQ) and the local limit of quadrangulations with a simple boundary (the simple boundary UIHPQ) are two very well studied objects. We shall see how the simple boundary UIHPQ relates to an annealed model of self-avoiding walk on random quadrangulations, and how metric information obtained for the UIHPQ can be used to study quantities such as the displacement of the self-avoiding walk from the origin, as well as to ultimately investigate how the biasing of random quadrangulations by the number of their self-avoiding walks affects their local limit.

If you're ever in Lyon on a Wednesday, make sure not to miss the Séminaire de la détente at the MMI! Cake, tidbits of mathematical fun, plus even a great apéro afterwords: what's there not to love?!
Was so happy to give a talk there in September: thanks to Olga and Marie for the invitation and delicious cake! Here's the abstract and slides (as usual, a version in a better format, possibly with some added explanations – some essential bits were done on the blackboard – may or may not be on the way):

For an English version of the following abstract, click here.

Nous sommes en 1944 ; le mathématicien Pál Turán, qui se trouve dans un camp de travail près de Budapest, est chargé de transporter des briques des fours aux aires de stockage via des chariots sur rails. Chaque four est relié par des rails à chacune des aires de stockage ; pousser les chariots ne demande pas trop d’effort, sauf aux croisements de deux rails, où ils ont tendance à capoter, de sorte que la plupart des briques tombent dehors. Pourquoi – s’interroge Pál – construire ce réseau de manière aussi inefficace, avec tellement de croisements exaspérants ?! Comment pourrait-on minimiser le nombre de croisements, tout en reliant chaque four à chaque aire de stockage ?
C’est peut-être la première question (qui est encore essentiellement ouverte !) portant sur le ’nombre de croisements’, une notion importante en théorie des graphes. En l’étudiant, on va ’croiser’ des artistes constructivistes, des informaticiens, des matheux sceptiques, et on va finalement tomber sur l’une des parties les plus précieuses de l’héritage de Pál Erdős : la méthode que l’on appelle ’probabiliste’.

Third take on a talk about outerplanar maps, and perhaps the most complete account I ever gave of this paper; the slides are the same those of the Journée YSP, with an extra section that describes the core algorithm. Sorry about the annoying video format; an incredibly heavy pdf file is available here.

A planar map is outerplanar if all of its vertices belong to a single (outer)face. The scaling limit for various classes of large planar maps has been shown to be the so-called “Brownian Map”; under certain conditions, however, different asymptotic behaviours may emerge, and some classes of planar maps with a macroscopic face admit Aldous’ CRT, or a scalar multiple thereof, as the scaling limit. We shall see that this is the case for outerplanar maps as well: using a bijection by Bonichon, Gavoille and Hanusse one can show that uniform outerplanar maps with n vertices, suitably rescaled by a factor $1/\sqrt{n}$, converge to $7\sqrt{2}/9$ times the CRT.

Voici le programme de la journée.