Probability on Trees and Planar Graphs (14w5159)

Arriving in Banff, Alberta Sunday, September 14 and departing Friday September 19, 2014


(McGill University, Canada)

(University of British Columbia)

(University of Oxford)

(University of Washington, USA)


``There are methods and formulae in science, which serve as master-keys to many apparently different problems. The resources of such things have to be refilled from time to time. In my opinion at the present time we have to develop an art of handling sums over random surfaces. These sums replace the old-fashioned (and extremely useful) sums over random paths. The replacement is necessary, because today gauge invariance plays the central role in physics. Elementary excitations in gauge theories are formed by the flux lines (closed in the absence of charges) and the time development of these lines forms the world surfaces. All transition amplitude[s] are given by the sums over all possible surfaces with fixed boundary.'' [Polyakov (1981)]

Statistical physics in two dimensions

Statistical physics in two dimensions has been one of the hottest areas of probability in recent years. The introduction of Schramm's SLE and further developments by Lawler, Schramm and Werner on the one hand, and the application of discrete complex analysis, as pioneered by Smirnov, on the other, have led to several breakthroughs and to the resolution of a number of long-standing conjectures. These include the conformally invariant scaling limits of critical percolation and Ising models, and the determination of critical exponents and dimensions of sets associated with planar Brownian motion (such as the frontier and the set of cut points). It is manifest that much progress will follow, possibly including the treatment of self-avoiding walks, the $O(n)$ loop model and the Potts model. While the bulk of this body of work applies to specific lattices, there are many fascinating problems in extending results to arbitrary planar graphs.

One natural next step is to study the classical models of statistical physics in the context of random planar maps. There are deep conjectured connections between the behaviour of the models in the random setting versus the Euclidean setting, most significantly the KPZ formula of Knizhnik, Polyakov and Zamolodchikov from conformal field theory. This formula relates the dimensions of certain sets in Euclidean geometry to the dimensions of corresponding sets in the random geometry. It may provide a systematic way to analyze models on the two dimensional Euclidean lattice: first study the model in the random geometry setting, where the Markovian properties of the underlying space make the model tractable; then use the KPZ formula to translate the critical exponents from the random setting to the Euclidean one. As mentioned before, much of this picture is conjectural. However, with our rapidly growing understanding of the structure of random planar maps and discrete complex analysis, there is hope of making progress in this direction.

{\sc Random maps}

Random planar maps is a widely studied topic at the intersection of probability, combinatorics and statistical physics. There are many natural classes of finite planar maps from which one can draw a random element: triangulations or $p$-angulations, maps of more general face size or of higher genus, and even the set of all planar graphs on $n$ vertices. As in the case of random walks, where the large scale behavior is invariant to the microscopic properties of the walk (it converges to Brownian motion), it is expected that random planar maps exhibit a similar universality (with the exception of random trees, which lie in a different universality class: see the last section of this proposal).

Let us consider a concrete example. Let $T_n$ be a random $p$-angulation ($p\geq 3$) of the sphere $\mathbb{S}^2$, chosen uniformly among such all $p$-angulations with $n$ vertices (considered up to orientation-preserving homeomorphism). In the recent culmination of a series of papers, Le Gall and (independently) Miermont show that when $p=3$ or when $p \geq 4$ is even, the random graph metric of $T_n$ scaled by $n^{-1/4}$ converges (in the Gromov--Hausdorff sense) to a random compact metric space homeomorphic to the sphere. This limiting metric has been termed the {\em Brownian Map}.

A second approach to the investigation of random maps is to study the unrescaled or ``infinite volume'' limit of random maps. One such limit, known as the uniform infinite planar triangulation (UIPT), was shown to exist by Angel and Schramm, and is obtained by taking the local limit of uniform random finite triangulations; other models of maps possess similar limits. The research in this area is focused on almost sure geometric properties of the limiting object: it is an invariant, planar, recurrent, and polynomially growing graph (the volume growth exponent is $4$), with a very fractal geometry. In particular, the random walk on it exhibits anomalous diffusion. Many questions about the UIPT and its (unfortunately named) counterpart, the stochastic hyperbolic infinite triangulation, remain; for example, the speed of the random walk on the UIPT is conjectured to be $n^{1/4}$.

All the research described above is concerned with the graph distance of random maps. However, planar maps can also be viewed as manifolds and, as such, are endowed with a conformal structure. In particular, there are natural embeddings of these maps in the sphere or the plane, given by the Riemann uniformization of the conformal structure. There are also discrete analogues of this embedding based on tools from discrete conformal geometry, and we can find embeddings using circle packings (see next section), rubber bands or square tilings. Understanding how these embeddings behave can shed light on many models of statistical physics on random planar maps. For instance, a concrete conjecture states that the empirical mass measure of the circle packing of a random triangulation on $n$ vertices (that is, the measure giving each circle mass $1/n$) converges to {\em Liouville quantum gravity}, a continuous model of random surfaces developed by Duplantier and Sheffield. Proving this conjecture will advance us considerably towards the goals presented in the previous section.

Circle packing and random walks on planar graphs

An important tool in the study of planar maps is the theory of circle packing, which provides a canonical and conformally natural way to embed a planar graph into the plane. A circle packing is a collection of circles in the plane with disjoint interiors. The tangency graph of a circle packing is a planar graph in which the vertex set is the set of circles and two circles are neighbours if they are tangent in the packing. It is clear that the tangency graph is planar and, in the other direction, the celebrated Koebe--Andreev--Thurston Circle Packing Theorem states that any finite planar graph can be realized as a tangency graph of a circle packing. Many extensions and generalizations of this theorem are known.

This beautiful theory has a wide range of applications, in combinatorics, computer science, differential geometry, geometric analysis, and complex analysis as well as discrete probability. In particular, circle packings have been indispensable for the analysis of random walks on planar graphs.

An example that highlights the connection to probability is a seminal theorem of He and Schramm which states that a bounded degree triangulation is transient if and only if it can be circle packed in a bounded domain. This bounded circle packing gives rise to a natural definition of the geometric ``boundary" of a transient planar graph. A natural question is the relation between this and other notions of boundary, such as the Poisson and Martin boundaries. A deep result in this area is that the Poisson boundary contains the geometric boundary. In the context of (continuous) manifolds, these questions have been central in geometric analysis, since the work of Yau, and are very difficult. The additional assumption of planarity provides us with a rich set of ideas and tools.

{\sc Random Trees and Critical Percolation}

Random trees have a long and illustrious history in the combinatorics literature. However, work on their scaling limits is a much more recent development which was initiated in a sequence of seminal papers by Aldous. The prototypical result is that the random graph metric obtained from drawing a random uniform tree from the set of $n^{n-1}$ rooted trees on $n$ labelled vertices converges (again, in the Gromov--Hausdorff sense), when rescaled by $n^{-1/2}$, to a random compact metric space. This is the so-called {\em Brownian continuum random tree} (BCRT).

This topic is more mature than the topic of random planar maps and the universality phenomenon for random trees is much better understood. In particular, the BCRT is known to be the limit for a large class of random trees: critical Galton--Watson trees whose offspring distributions have finite variance, unordered binary trees, uniform unordered trees, critical multitype Galton--Watson trees and many others. Moreover, the techniques used to prove convergence to the BCRT have also been adapted to give new limits each having its own domain of attraction: the stable trees (the scaling limits of critical Galton--Watson trees whose offspring distribution are in the domain of attraction of a stable law of index in $(1,2)$), L\'evy trees, fragmentation trees (which are the scaling limits of the so-called Markov branching trees) and the minimum spanning tree of the complete graph.

The BCRT is now recognized as a central to the scaling limits of many discrete and highly varied objects. For example, the scaling limit of critical Erd\H{o}s--R\'enyi random graphs, has been shown by Addario-Berry, Broutin and Goldschmidt to be composed of a number of rescaled BCRT's glued together. Excitingly, there is evidence that this limiting object is a universal limit for a wide variety of models including random graphs with a fixed degree sequence, percolation on random regular graphs, critical percolation on high-dimensional tori and on the hypercube, the critical vacant set left by random walk on a random regular graph, and the SIR epidemic model. The Brownian map discussed above is also defined as a certain quotient of the BCRT. This fruitful and expanding area of study should yield interesting developments for many years to come.