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.

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.

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.