BEGIN:VCALENDAR
VERSION:2.0
PRODID:talks.ox.ac.uk
BEGIN:VEVENT
SUMMARY:Polynomial mixing time for edge flips on quadrangulations - Alessa
ndra Caraceni (University of Bath)
DTSTART;VALUE=DATE-TIME:20181119T120000Z
DTEND;VALUE=DATE-TIME:20181119T130000Z
UID:https://talks.ox.ac.uk/talks/id/46c81587-5db3-4968-9702-2e7f69e098b7/
DESCRIPTION:This talk will revolve around recent joint work with Alexandre
Stauffer in which we give the first polynomial upper bound for the relaxa
tion time of the edge flip Markov chain on rooted quadrangulations. A quad
rangulation 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\, consi
dered up to orientation-preserving homeomorphisms of the sphere itself\; w
e call it rooted when it is endowed with a distinguished oriented edge. Gi
ven a (rooted) quadrangulation of size n\, a step of the Markov chain we a
re 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 c
an 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 whi
ch exploits the well-known bijection by Schaeffer and a specific construct
ion of leaf translations as sequences of edge flips\, we shall estimate th
e relaxation time of the leaf translation chain\, thereby improving on a r
esult by Movassagh and Shor.\nSpeakers:\nAlessandra Caraceni (University o
f Bath)
LOCATION:Mathematical Institute (L4)\, Woodstock Road OX2 6GG
TZID:Europe/London
URL:https://talks.ox.ac.uk/talks/id/46c81587-5db3-4968-9702-2e7f69e098b7/
BEGIN:VALARM
ACTION:display
DESCRIPTION:Talk:Polynomial mixing time for edge flips on quadrangulations
- Alessandra Caraceni (University of Bath)
TRIGGER:-PT1H
END:VALARM
END:VEVENT
END:VCALENDAR