Polynomial mixing time for edge flips on quadrangulations
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, thereby improving on a result by Movassagh and Shor.
Date: 19 November 2018, 12:00 (Monday, 7th week, Michaelmas 2018)
Venue: Mathematical Institute, Woodstock Road OX2 6GG
Venue Details: L4
Speaker: Alessandra Caraceni (University of Bath)
Organising department: Department of Statistics
Organisers: Christina Goldschmidt (Department of Statistics, University of Oxford), James Martin (Department of Statistics, University of Oxford)
Part of: Probability seminar
Booking required?: Not required
Audience: Public
Editor: Christina Goldschmidt