BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Alessandra Caraceni (University of Oxford) DTSTART:20210511T150000Z DTEND:20210511T160000Z DTSTAMP:20260423T021256Z UID:POSemP/5 DESCRIPTION:Title: P olynomial mixing time for edge flips on planar maps\nby Alessandra Car aceni (University of Oxford) as part of Pisa Online Seminar in Probability \n\n\nAbstract\nA long-standing problem proposed by David Aldous consists in giving a sharp upper bound for the mixing time of the so-called “tria ngulation walk”\, a Markov chain defined on the set of all possible tria ngulations of the regular n-gon. A single step of the chain consists in pe rforming a random edge flip\, i.e. in choosing an (internal) edge of the t riangulation uniformly at random and\, with probability 1/2\, replacing it with the other diagonal of the quadrilateral formed by the two triangles adjacent to the edge in question (with probability 1/2\, the triangulation is left unchanged).\n\nWhile it has been shown that the relaxation time f or the triangulation walk is polynomial in n and bounded below by a multip le of $n^{3/2}$\, the conjectured sharpness of the lower bound remains fir mly out of reach in spite of the apparent simplicity of the chain. For edg e flip chains on different models – such as planar maps\, quadrangulatio ns of the sphere\, lattice triangulations and other geometric graphs – e ven less is known.\n\nWe shall discuss results concerning the mixing time of random edge flips on rooted quadrangulations of the sphere obtained in joint work with Alexandre Stauffer. A “growth scheme” for quadrangulat ions\, which generates a uniform quadrangulation of the sphere by adding f aces one at a time at appropriate random locations\, can be combined with careful combinatorial constructions to build probabilistic canonical paths in a relatively novel way. This method has implications for a range of in teresting edge-manipulating Markov chains on so-called Catalan structures\ , from “leaf translations” on plane trees to “edge rotations” on g eneral planar maps.\n LOCATION:https://researchseminars.org/talk/POSemP/5/ END:VEVENT END:VCALENDAR