Next Seminar

Edge flip Markov chains on triangulations and random planar maps

Alexandre Stauffer (Università Roma Tre)

2021-12-02

14:00-14:45 UTC (make sure to keep track of time changes!)

Alessandra Caraceni (Scuola Normale Superiore of Pisa)

2021-12-02

15:00-15:45 UTC (make sure to keep track of time changes!)

Abstracts

A long-standing problem proposed by David Aldous is that of 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 triangulation 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). While it has been shown that the relaxation time for the triangulation 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 reach in spite of the apparent simplicity of the chain.

In the first talk, we describe various “edge flip” Markov chains, from Aldous’ triangulation walk to edge flips on lattice triangulations and planar maps. We discuss the challenges posed by estimating their mixing time, give an overview of existing results and describe a strategy for proving lower bounds.

In the second talk, we describe a construction of probabilistic canonical paths that yields polynomial upper bounds for the mixing time of several edge flip chains. The method we present relies on the existence of “growth schemes” for the combinatorial objects involved, so we shall in turn discuss the problem of growing uniform random quadrangulations and triangulations “face by face”, presenting some results and implications.

Log-in Link

The zoom-link is weekly updated before a seminar session and is given below. If you sign into the mailing list you will receive the link on Wednesdays.

https://us02web.zoom.us/j/84701678257?pwd=UVNNcjFHSXZROUlLbGNqa25pUjMzZz09
Meeting ID: 847 0167 8257
Passcode: 873921

Please turn off your personal videos to reduce the bandwidth used!

If you are having trouble with zoom, or if the capacity of the zoom room gets exceeded, you can also access to the Youtube live stream at the channel of the seminar: https://www.youtube.com/channel/UCiLiEQGTp6bZEhuHDM-WNWQ


Zoom

We use zoom, a simple webinar tool. Zoom is not free, but only the hosts (that's us) need a license. All others can log-in via a link. Before the talk you can find the link on this website. Just click on the link and you will be sent to a webinar. There will be a host with control over the microphones.

Please subscribe to our mailing list for updates about the upcoming seminars and other events.