BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Polynomial Mixing Time for Edge Flips via Growing  Random Planar M
 aps
DTSTART:20220412T083000Z
DTEND:20220412T093000Z
DTSTAMP:20260312T162500Z
UID:indico-event-7733@indico.math.cnrs.fr
CONTACT:cecile@ihes.fr
DESCRIPTION:Speakers: Alessandra Caraceni (Scuola Normale Superiore of Pis
 a)\n\nA long-standing problem proposed by David Aldous consists in 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 triangulati
 on uniformly at random and\, with probability 1/2\, replacing it with the 
 other diagonal of the quadrilateral formed by the two triangles adjacent t
 o the edge in question (with probability 1/2\, the triangulation is left u
 nchanged).\nWhile it has been shown that the relaxation time for the trian
 gulation walk is polynomial in n and bounded below by a multiple of n^{3/2
 }\, the conjectured sharpness of the lower bound remains firmly out of rea
 ch in spite of the apparent simplicity of the chain. For edge flip chains 
 on different models -- such as planar maps\, quadrangulations of the spher
 e\, lattice triangulations and other geometric graphs -- even less is know
 n.\nWe shall discuss results concerning the mixing time of random edge fli
 ps on rooted quadrangulations of the sphere\, partly obtained in joint wor
 k with Alexandre Stauffer. A “growth scheme” for quadrangulations whic
 h generates a uniform quadrangulation of the sphere by adding faces one at
  a time at appropriate random locations can be combined with careful combi
 natorial constructions to build probabilistic canonical paths in a relativ
 ely novel way. This method has immediate implications for a range of inter
 esting edge-manipulating Markov chains on so-called Catalan structures\, f
 rom “leaf translations” on plane trees to “edge rotations” on gene
 ral planar maps. Moreover\, we are able to apply it to flips on 2p-angulat
 ions and simple triangulation of the sphere\, via newly developed “growt
 h schemes”.\n\nhttps://indico.math.cnrs.fr/event/7733/
LOCATION:Centre de conférences Marilyn et James Simons (I.H.E.S.)
URL:https://indico.math.cnrs.fr/event/7733/
END:VEVENT
END:VCALENDAR