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.