UTGD Seminar Schedule - Spring 2021
(for information on how to attend or watch previous talks, click UTGD online seminar on your left)
February 4: Nathanael Berestycki
Introduction to mixing times and the cutoff phenomenon
How many times should you shuffle a deck of cards so that its distribution is approximately uniform? This question can be formalised through the notion of mixing time for a Markov chain. Elementary theory tells us that, given an irreducible and aperiodic Markov chain on a finite state space, its distribution will converge to a unique "equilibrium" distribution. But this theory doesn't say anything about how long one should wait to be close to this distribution. In the early 1980s, Persi Diaconis and David Aldous discovered independently and simultaneously the remarkable fact that many chains undergo a "cutoff phenomenon", where the convergence to equilibrium occurs abruptly (as some parameter n, say the size of the state space, tends to infinity), at a well defined time called the mixing time. I will explain these notions and ideas in a self-contained way; in particular no probabilistic prerequisite will be assumed. I hope to discuss some examples and give a (very rapid) glimpse of the current state of the theory.
February 11: Nathanael Berestycki
Cutoff phenomenon for random walks on random graphs
Let $G = G(n, \lambda / n)$ be an instance of the Erdos-Renyi random graph model on 
vertices, with edges present independently of one another with probability $p = \lambda / n$. When $\lambda1$, it is known that this random graph has a unique giant component with high probability as $n \to \infty$ (where giant means that it contains a positive fraction of all vertices). What can we say about the mixing time of random walk on this giant component? It turns out that the answer depends very much on the starting point of the walk. In this work we show that from a typical starting point the cutoff phenomenon takes place. The limiting order of the mixing time depends on the speed and the entropy of random walk on a Galton-Watson tree which is the Benjamini-Schramm limit of the giant component of a random graph. The result extends to graphs with prescribed degree sequences.
February 25: Gourab Ray
A tale of infinitely many balloons
Consider a Poisson process in R^d . Now start growing balloons at speed 1 from each point in this process, and if two balloons collide, ‘pop’ them (and remove the points in the Poisson process as well) Is the origin going to be visited infinitely many times by a balloon? What if we change R^d to the hyperbolic plane? We answer these questions demonstrating contrasting behaviour in these two cases. Bounding the density of a well separated factor of iid process on a tree comes up in the hyperbolic case, which is of independent interest. Joint work with Omer Angel, Thomas Budzinsky and Yinon Spinka.
March 4: Thomas Budzinksi
Local limits of random maps in high genus
Random maps are natural models of random discrete surfaces. Random planar maps have been known for fifteen years to converge in the Benjamini--Schramm sense to infinite objects with fractal properties such as the UIPT. We will treat the case of random maps with genus proportional to the size, where limiting objects exhibit hyperbolic properties. Based on joint works with Baptiste Louf.
March 11: Tuomas Sahlsten
Benjamini-Schramm convergence and spectral theory of (random) hyperbolic surfaces
We will outline some of our past and ongoing attempts to “translate” ideas from large (random) graphs to the language of large (random) hyperbolic surfaces in the sense of Benjamini and Schramm in order to get new insights on the statistics and behaviour of eigenvalues and eigenfunctions of the Laplacian on such surfaces.