Alessandra Caraceni (University of Bath, UK)

Titolo: Polynomial mixing time for edge flips on quadrangulations.

Mercoledi' 17 Ottobre 2018 ORE 16:00

Dipartimento di Matematica e Fisica Universita' degli Studi Roma Tre Largo San Leonardo Murialdo,1 - Pal.C - Aula 211

Abstract This talk will revolve around recent joint work with Alexandre Stauffer in which we give the first polynomial upper bound for the relaxation time of the edge flip Markov chain on rooted quadrangulations. A quadrangulation of size n is a connected planar graph endowed with a cellular embedding in the sphere such that all of its n faces have degree 4, considered up to orientation-preserving homeomorphisms of the sphere itself; we call it rooted when it is endowed with a distinguished oriented edge. Given a (rooted) quadrangulation of size n, a step of the Markov chain we are interested in a so-called “edge flip” consists in choosing an edge uniformly at random, deleting it and replacing it with one of the three possible edges (two when the original edge is adjacent to only one face) which, if drawn, recreate a quadrangulation. We will see how one can relate the edge flip chain on quadrangulations to a “leaf translation” chain on plane trees (which has a natural interpretation as a chain on the set of Dyck paths, and on other Catalan structures as well). Having discussed how to set up a successful comparison between the two chains which exploits the well-known bijection by Schaeffer and a specific construction of leaf translations as sequences of edge flips, we shall estimate the relaxation time of the leaf translation chain by improving on a result by Movassagh and Shor.