Title: The Continuous Limit of Large Random Planar Graphs, I
Speaker: Professor Jean-Francois Le Gall
Speaker Info: University of Paris
Planar maps are graphs embedded in the plane, considered up to continuous deformation. They have been studied extensively in combinatorics, and they also have significantgeometrical applications. Random planar maps have been used in theoretical physics, where they serve as models of random geometry. Our goal is to discuss the convergence in distribution of rescaled random planar maps viewed as random metric spaces. More precisely, we consider a random planar map M(n) which is uniformly distributed over the set of all planar maps with n vertices in a certain class. We equip the set of vertices of M(n) with the graph distance rescaled by the factor n to the power -1/4. We then discuss the convergence in distribution of the resulting random metric spaces as n tends to infinity, in the sense of the Gromov-Hausdorff distance between compact metric spaces. This problem was stated by Oded Schramm in his 2006 ICM paper, in the special case of triangulations. In the case of bipartite planar maps, we first establish a compactness result showing that a limit exists along a suitable subsequence. We then prove that this limit can be written as a quotient space of the so-called Continuum Random Tree (CRT) for an equivalence relation which has a simple definition in terms of Brownian labels attached to the vertices of the CRT. This limiting random metric space, which is called the Brownian map, can be viewed as a "Brownian surface" in the same sense as Brownian motion is the limit of rescaled discrete paths. We show that the Brownian map is almost surely homeomorphic to the two-dimensional sphere, although it has Hausdorff dimension 4. Furthermore, we are able to give a complete description of the geodesics from a distinguished point (the root) of the Brownian map, and in particular of those points which are connected by more than one geodesic to the root. Asa key tool, we use bijections between planar maps and various classes of labeled trees.Date: Friday, October 24, 2008
References (available on http://www.dma.ens.fr/users/legall/ )
J.F. Le Gall. The topological structure of scaling limits of large planar maps. Invent. Math. 169, 621-670 (2007).
J.F. Le Gall, F. Paulin. Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere. Geometr. Funct. Analysis, to appear.
J.F. Le Gall. Geodesics in large random planar maps. Preprint (2008)