Discrete and Continuous Random Trees

This minicourse provides the background for the proposed open problem on the diameter of random bipartite planar maps with given face degrees. We will first introduce planar maps and some basic bijections, with a focus on bijections between planar maps and "decorated trees" that allow distances in the map to be studied through the tree.

We will begin with the CVS (Cori-Vauquelin-Schaeffer) bijection between pointed quadrangulations and well-labelled plane trees. We will present the bijection in detail and discuss two applications: the enumeration of planar maps, leading to Tutte’s formula, and a typical graph distance scaling of order n^1/4 for uniform random planar quadrangulations with n faces.

We will then move to bipartite maps with general face degrees. We will present a composite bijection arising from combining the BDG (Bouttier-Di Francesco-Guitter) and the JS (Janson-Stefánsson) bijections. This connects pointed bipartite planar maps directly to bridge-labeled plane trees while preserving degree correspondences.

Distances can then be studied using a line-breaking construction for Cayley trees with given vertex degrees, due to Foata and Fuchs. As an application, we will recover the previous bound for typical distances in random planar quadrangulations. The main advantage of this alternative approach is that it also applies to arbitrary sequences of even face degrees, directly leading to our open problem.

How can local information reveal the global structure of a large random graph? The framework of local convergence addresses this question by studying the neighbourhood of a typical vertex as the graph grows. In this mini-course, I will introduce the basic ideas of local convergence and show how local information can be used to understand seemingly global properties, such as the size and structure of the largest component. Our main example will be the sparse Erdős–Rényi random graph, but the framework extends far beyond this example, and applies broadly to random graph models whose typical degrees remain bounded as the network grows.

There are many popular and well-studied models of randomly grown trees, such as binary search trees, preferential attachment trees, and uniform attachment trees. Though different in some ways, many of these tree models share that their depth (also often called the height), the largest distance from the root to a leaf, grows as the logarithm of the number of vertices in the tree.

In this mini-course we will investigate a more recently introduced model of randomly growing trees called depth-weighted trees. In this model, given a function f, vertices are added to the tree one-by-one, where the probability of a new vertex to connect to an existing vertex v is proportional to f(depth of v), where the depth of v is the distance of v to the root. Depending on the choice of the function f, the depth of the tree can grow logarithmically or much slower/faster than logarithmically. We will study some general tools to study depth-weighted trees, and uncover the growth rate of the depth of the tree for different families of functions f.

In this course we aim at providing a small panorama of theory of Bienaymé Galton Watson (BGW) processes with immigration in discrete and continuous time. We will start by the basic theory on discrete time BGW processes without immigration, this will include the extinction probability and time of extinction, as well the connection between BGW and spectrally positive random walks. Then we will include the immigration component and we will review some classical results about the existence of a stationary distribution. We will describe the so-called spine decomposition of the process conditioned to avoid extinction. Then we will move to the continuous time setting, where the BGW process with or without immigration is a continuous time Markov chain. There we will focus in giving some insight about the set of times where the BGW process with immigration is at zero and its excursions from zero. Along the presentation, we will provide some insight on how to modify the theory to include the case where immigration part is being censored by a Markovian agent Y = (Y_t, t ≥ 0) that allows or forbids the entrance in the system. In this case, the BGW process with immigration becomes a process in a Markovian random environment, and hence its beaviour is perturbed according to the behaviour of the Markov agent Y.

Consider a finite connected graph, and pick one of its spanning trees uniformly at random. What are the properties of the resulting random tree, and how do they depend on the underlying graph? These questions have been explored in great detail by probabilists over the last 30 years. The purpose of this mini-course is to give an introduction to uniform spanning trees (USTs), including two beautiful algorithms, both based on random walks, which can be used to generate them. We will investigate what happens in the special case that the underlying graph is the complete graph on n vertices, as n tends to infinity, and then focus in on graphs whose USTs closely resemble that of the complete graph on n vertices, in the sense of having the same scaling limit. These graphs are all, in some sense, high-dimensional. In the final part of the mini-course, we will think about the situation where the underlying graph is the largest component of an Erdos-Renyi random graph, G(n,p), in different ranges of p. Our understanding of the behaviour of the UST here is incomplete (and the subject of my open problem!); I will describe some structural results for the graph which should help to make progress here.

Suppose that on Z² there are zombies at some vertices, with probability λ at each vertex, and one survivor (Mindy). The zombies move randomly, always towards the survivor, and Mindy sees the zombies. How long can Mindy avoid the zombies? With Paweł Prałat and Peter Winkler we give some bounds, and relate this to various random walk problems.

Second-order free probability provides a framework for studying fluctuations of large random matrices beyond their limiting spectral distributions. In this talk, we derive functional equations governing the multiplicative convolution of two second-order free random variables a and b. These relations extend classical first-order descriptions and could allow one to compute fluctuation quantities associated with products of free elements. As applications, we analyze conjugation by a free circular element and investigate connections with finite free probability.

We give an asymptotic estimation in long time for the Laplace transform of the Elephant Random Walk (ERW). The ERW is a generalization of the Simple Random Walk in which the past influences the future evolution of the process according to some memory parameter. Its transition kernel is neither space nor time homogeneous and its transition probability at the nth step can be written as a function of n and the position of the walk at time n − 1. We explore this property to apply classical singularity analysis methods on the generating function of the sequence of Laplace transforms. As an application, we are able to conclude the known result of a Large Deviations Principle for the ERW.

We study the fractal dimensions of various classes of sets defined in terms of the Liouville quantum gravity (LQG) metric. Among other bounds, we prove that the set of 3-star points (i.e., starting points of three disjoint geodesics) has Hausdorff dimension at least two with respect to the LQG metric, which is conjectured to be optimal. Our proofs apply to a general class of planar length metrics including, e.g., Kendall’s Poisson roads metric and other coalescent metrics (i.e., metrics for which geodesics between nearby points tend to merge in the middle). In the particular setting of LQG, we obtain sharper lower bounds for the Hausdorff dimensions of the set of 2-star points and the LQG metric net, with respect to both the Euclidean metric and the LQG metric.

Our proofs are primarily topological. The key idea is to express the sets of interest in terms of non-constancy sets of Lipschitz functions. We will also discuss related work in progress characterizing the coalescent behavior of the critical long-range percolation metric. This is joint work with Manan Bhatia and Ewain Gwynne.

In this talk we will study random matrices whose entries are organized according to the regular representation of a finite group G, giving rise to what we call G-circulant random matrices. By analyzing the spectral distribution of these matrices, we identify conditions under which the empirical spectral distribution can be expressed as the free additive convolution of simpler distributions. This framework establishes a natural connection between random matrices with group symmetries and the concept of free independence. In particular, our main results show that, by decomposing a random matrix X with G-circulant structure and under the assumption that X is freely independent from M_|G|×|G|(ℂ), the transpose X^t can be represented as a sum of freely independent matrices.