• Random Graphs

To trace back to the origin of the study of planar maps we have to go back to
the ’60’s, when efforts to solve the 4-colour problem led to an increased interest
in embedded planar graphs.
Recently, being natural models for a random “discretised” surface, random pla-
nar maps become relevant to theoretical physics, and in particular theories of
quantum gravity. The question is how planar maps may in fact be interpreted
as approximations of a “continuous” random surface.
The aim of this work is to study the convergence of random graphs in local
topology and scale limits, with a special look to planar maps. The major result
we present, from papers of Le Galle and Miermont, is that scale limit of certain
classes of planar maps is the Brownian Map.
The work is divided in three chapters. In the first chapter we introduce the dis-
crete objects and graph properties. We then introduce a metric in the space of
pointed graph called the local topology and a notion of uniformly pointed graph
through the mass transport principle. We show some examples of local limits
in the topic of uniformly pointed graph with a particular attention to the local
limit of Galton Watson trees. Then we briefly conclude with some connection
to ergodic theory and percolation problems.
In the second chapter we introduce the fundamental tools for the main result
of the work. We start proving the Cori-Vanquelin-Shaeffer bijection between
well labelled trees with n vertices and rooted quadrangulations with n faces.
The proof of the CV S bijection follows the work of Shaeffer in his PhD thesis.
We spend some efforts to study the metric properties preserved by the CV S
bijection. After that we discuss the bijection with a well labelled embedded tree
and his contour process. Inspired by the convergence of scaled random walks
to the Brownian Motion (Donsker Theorem), we briefly introduce the theory
of Brownian excursions and remarking the contour process method we connect
large random plane trees and Brownian excursions.
In the third chapter, we construct the Brownian Continuum Random Tree
(CRT) and we see that with the help of contour process, CRT is the limit
1
of random planar tree. So, starting from the CRT we construct the Brownian
Map. We conclude proving the result of Le Gall-Paulin, stating that the Brow-
nian Map is homeomorphic to the 2-sphere and the result of Le Gall-Miermont,
the Brownian Map is the limit of class of quadrangulations, in the Gromov-
Hausdorff distance.