# Random cubic planar graphs converge to
the Brownian sphere

Marie Albenque111LIX/CNRS, UMR7161, École Polytechnique,
<EMAIL_ADDRESS>Éric Fusy222LIGM/CNRS, UMR8049, Université
Gustave Eiffel<EMAIL_ADDRESS>Thomas Lehéricy333Institut für Mathematik,
Universität Zürich<EMAIL_ADDRESS>
###### Abstract

In this paper, the scaling limit of random connected cubic planar graphs
(respectively multigraphs) is shown to be the Brownian sphere.

The proof consists in essentially two main steps. First, thanks to the known
decomposition of cubic planar graphs into their 3-connected components, the
metric structure of a random cubic planar graph is shown to be well
approximated by its unique 3-connected component of linear size, with modified
distances.

Then, Whitney’s theorem ensures that a 3-connected cubic planar graph is the
dual of a simple triangulation, for which it is known that the scaling limit
is the Brownian sphere. Curien and Le Gall have recently developed a framework
to study the modification of distances in general triangulations and in their
dual. By extending this framework to simple triangulations, it is shown that
3-connected cubic planar graphs with modified distances converge jointly with
their dual triangulation to the Brownian sphere.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Definitions on graphs and maps
    2. 2.2 Gromov–Hausdorff–Prokhorov topology
  3. 3 The 3-connected core of cubic planar graphs
    1. 3.1 Decomposition into 3-connected components
    2. 3.2 Largest 3-connected component
    3. 3.3 Cubic planar graphs with a marked $3$-connected component
    4. 3.4 Extension of the results to cubic planar multigraphs
  4. 4 First results about the metric properties of random cubic planar graphs
    1. 4.1 Pole-distance in cubic networks under the critical Boltzmann distribution
    2. 4.2 A first bound on the diameter
  5. 5 Skeleton decomposition for quasi-simple triangulations
    1. 5.1 Simple triangulations
    2. 5.2 Quasi-simple triangulations: definition and enumeration
    3. 5.3 Decomposition of quasi-simple triangulations of the 1-gon into simple components
    4. 5.4 Quasi-simple triangulations of the cylinder and their skeleton decomposition
    5. 5.5 Hulls and encoding via a branching process
    6. 5.6 Local limits: quasi-simple UIPT and half-plane models
  6. 6 Modification of distances in simple triangulations
    1. 6.1 Upper bounds in the infinite models
    2. 6.2 Upper bound in finite simple triangulations
    3. 6.3 Two-point function
    4. 6.4 Coupling between $\mu_{n}$ and $\mu_{n}^{\dagger}$ and proof of Theorem 2
  7. 7 Scaling limit of the 3-connected core with distances induced by the connected graph
    1. 7.1 Definition of the coupling between $\widehat{\mathfrak{K}}_{q}$ and $\widetilde{\mathfrak{K}}_{q}$
    2. 7.2 First properties of the coupling
    3. 7.3 Truncation of edge-lengths
    4. 7.4 Lengths of truncated geodesic paths in both models
    5. 7.5 Proof of Proposition 37
    6. 7.6 Proof of Theorem 36
  8. 8 Gromov–Hausdorff–Prokhorov distance between a random connected cubic planar graph and its 3-connected core

##  1 Introduction

In recent years, a lot of progress has been achieved in the understanding of
the scaling limit of random planar maps (planar graphs embedded in the
sphere). Miermont [28] and Le Gall [24] established the first results of
convergence of random planar maps towards the Brownian sphere. Since these
major results, many other families of maps have also been proved to admit the
Brownian sphere as their scaling limit. Moreover, the properties of the
Brownian sphere have been thoroughly investigated, we refer to the following
surveys and references therein [25, 29, 30] for nice entry points to this
field.

However, much less is known about the scaling limit of random planar _graphs_
, which are graphs that can be embedded in the sphere but for which the
embedding is not fixed. In this article, we obtain the first result of
convergence of a family of random planar graphs towards the Brownian sphere.
Our main result is the following (a graph or multigraph is called _cubic_ if
all its vertices have degree $3$):

######  Theorem 1.

Let $\mathfrak{C}_{n}$ (resp. $\mathfrak{M}_{n}$) be a uniformly random
connected cubic labeled planar graph (resp. multigraph) with $2n$ vertices.
Let $\mu_{\mathfrak{C}_{n}}$ and $\mu_{\mathfrak{M}_{n}}$ denote respectively
the uniform distribution on $V(\mathfrak{C}_{n})$ and $V(\mathfrak{M}_{n})$.
Let $\mathrm{d}_{\mathrm{gr}}$ denote the graph distance. Then, there exist
constants $\mathrm{c},\mathrm{c}_{m}\in(0,\infty)$ such that the following
convergence holds:

$\left(V(\mathfrak{C}_{n}),\frac{1}{\mathrm{c}\cdot
n^{1/4}}\mathrm{d}_{\mathrm{gr}},\mu_{\mathfrak{C}_{n}}\right)\xrightarrow[n\to\infty]{}\mathrm{m}_{\infty},$
(1)

and

$\left(V(\mathfrak{M}_{n}),\frac{1}{\mathrm{c}_{m}\cdot
n^{1/4}}\mathrm{d}_{\mathrm{gr}},\mu_{\mathfrak{M}_{n}}\right)\xrightarrow[n\to\infty]{}\mathrm{m}_{\infty},$
(2)

where the convergence holds in distribution for the Gromov–Hausdorff–Prokhorov
topology for measured metric spaces, and $\mathrm{m}_{\infty}$ denotes the
Brownian sphere.

While finishing this project, we became aware that Benedikt Stufler obtained
simultaneously and independently the scaling limit of random connected cubic
planar graphs [38, 39], using the same general strategy but with different
techniques to resolve the main difficulties.

Our motivation to consider not only cubic planar graphs but also cubic planar
multigraphs comes from the fact that they appear naturally as the kernel of
random connected planar graphs in the sparse regime (i.e. when the excess of
the graph is $o(n)$). The scaling limit of random planar _maps_ in the sparse
regime has recently been investigated in [12], via the study of the scaling
limit of their cubic kernel. To extend this result to the case of random
sparse planar graphs, the scaling limit of random connected cubic planar
multigraphs is thus a decisive step444A simpler problem involving kernel
extraction would be to obtain the scaling limit of random connected planar
multigraphs that are _precubic_ , i.e., with vertex-degrees in $\\{1,3\\}$..

Before giving the main ideas behind the proof of this result, let us place it
in the context of the existing literature on the enumeration of planar graphs
and on the study of their random properties. Unlike planar maps, for which
closed enumerative formulas are often available [41], the enumeration of
planar graphs is more involved. Building on a canonical decomposition of
graphs into their 3-connected components [42], a (differential) system of
equations for their generating series can be obtained. Major achievements have
consisted in deriving precise asymptotic estimates from these equations. A
non-exhaustive list of contributions includes the case of 2-connected planar
graphs [6], the case of cubic planar graphs [7] and cubic planar multigraphs
[22] and the case of planar graphs [18]. We also refer to the survey [32] and
references therein.

These enumerative results have made possible the study of random properties of
planar graphs, and to establish limit laws for various parameters, such as the
maximum degree [14]. They have also been a key ingredient in the recent proofs
of the convergence of random cubic planar graphs [40] and random planar graphs
[37] for the local topology.

However, only few results are available about the metric properties of random
planar graphs. It has only been shown that the order of magnitude of the
diameter of random planar graphs with $n$ vertices is concentrated around
$n^{1/4}$ [11]. Let us also mention that the scaling limit of some families of
planar graphs have been previously established. However, such results only
hold for so-called _subcritical_ families of graphs (which include in
particular outerplanar graphs and series-parallel graphs) and their scaling
limit is Aldous’ Brownian Continuum Tree [34, 36].

### General strategy of the proof and organization of the paper

##### Decomposition of cubic planar graphs along their 3-connected components.

The first ingredient in the proof of Theorem 1 is the known decomposition of
cubic planar graphs into 3-connected components. This decomposition allows us
to use techniques similar to the ones developed in [5, 17] and to prove that a
random cubic planar graph (resp. cubic planar multigraph) admits a unique
giant 3-connected component called its _3-connected core_. This is presented
in Section 3. A key feature is that the metric properties of the original
graph can be very precisely approximated by the metric properties of its
3-connected core with random edge-lengths. More precisely, the length of a
given edge follows asymptotically a distribution denoted $\nu_{\star}$. To
study this model, a first step is to consider the case where the edge-lengths
are i.i.d random variables distributed according to $\nu_{\star}$.

Dealing with a 3-connected planar graph allows us to enter the world of planar
maps. Indeed, by Whitney’s theorem [43], a 3-connected planar graph is known
to admit a unique embedding (up to mirror). Hence, 3-connected planar graphs
and 3-connected planar maps are the same objects. By duality, 3-connected
cubic planar graphs correspond to simple triangulations (i.e. triangulations
with no loops nor multiple edges).

##### Modification of distances in simple triangulations.

In [13], Curien and Le Gall studied modifications of distances in
triangulations. Their techniques have also been adapted to quadrangulations
and general maps by the third author [26], and to Eulerian triangulations
[10]. To establish the scaling limit of random 3-connected cubic planar maps
with random i.i.d edge-lengths, we extend their framework in two directions.
We deal with simple triangulations rather than general triangulations, and we
consider the first-passage percolation distance on the edges of the dual map
rather than the dual graph distance or the Eden model (corresponding to
exponential random variables on the edges of the dual map). To be able to
state our result precisely, we first introduce a couple of definitions and
notations.

Fix $\mathrm{m}$ a planar map, and write $\mathrm{m}^{\dagger}$ for its dual.
Let $\nu$ be a probability distribution on $\mathbb{R}_{>0}$. We define a
(random) metric on $\mathrm{m}^{\dagger}$ as follows. Let $(w_{e})_{e\in
E(\mathrm{m}^{\dagger})}$ be a collection of random weights indexed by the set
of edges of $\mathrm{m}^{\dagger}$, such that $(w_{e})$ are i.i.d random
variables sampled from $\nu$. We define the first-passage percolation distance
$\mathrm{d}^{\star}_{\nu}$ on $\mathrm{m}^{\dagger}$ by setting, for any
$u,v\in V(\mathrm{m}^{\dagger})$:

$\mathrm{d}^{\star}_{\nu}(u,v)=\inf_{\gamma:u\rightarrow
v}\sum_{e\in\gamma}w_{e},$ (3)

where the infimum runs over all paths $\gamma$ going from $u$ to $v$ in
$\mathrm{m}^{\dagger}$.

Our second main result is the following theorem:

######  Theorem 2.

Let $\mathfrak{t}_{n}$ be a uniformly random simple triangulation with $n+2$
vertices. Let $\mu_{\mathfrak{t}_{n}}$ and $\mu_{\mathfrak{t}_{n}^{\dagger}}$
denote respectively the uniform distribution on $V(\mathfrak{t}_{n})$ and on
$V(\mathfrak{t}^{\dagger}_{n})$. Assume that the support of $\nu$ is included
in $[\eta_{0},\infty)$ for $\eta_{0}>0$, and that $\nu$ has exponential tails.

Then, there exists a constant $c_{\nu}>0$ such that the following convergence
holds jointly in distribution for the Gromov–Hausdorff–Prokhorov topology:

$\left(\left(V(\mathfrak{t}_{n}),\Big{(}\frac{3}{4n}\Big{)}^{1/4}\mathrm{d}_{\mathrm{gr}},\mu_{\mathfrak{t}_{n}}\right),\left(V(\mathfrak{t}^{\dagger}_{n}),\Big{(}\frac{3}{4n}\Big{)}^{1/4}\frac{1}{c_{\nu}}\cdot\mathrm{d}^{\star}_{\nu},\mu_{\mathfrak{t}_{n}^{\dagger}}\right)\right)\xrightarrow[n\rightarrow\infty]{(d)}(\mathrm{m}_{\infty},\mathrm{m}_{\infty}),$
(4)

where $\mathrm{m}_{\infty}$ is the Brownian sphere.

Note that the convergence of the first component was established by Addario-
Berry and the first author in [1]. By applying this theorem to the case where
$\nu=\delta_{1}$ is the Dirac measure on $\\{1\\}$, and by applying Whitney’s
theorem, we obtain as an immediate corollary:

######  Theorem 3.

Let $\mathfrak{K}_{n}$ be a uniformly random 3-connected cubic planar graphs
with $2n$ vertices. Denote by $\mu_{\mathfrak{K}_{n}}$ the uniform
distribution on $V(\mathfrak{K}_{n})$. Then, there exists a constant $c_{3}>0$
such that the following convergence holds in distribution for the
Gromov–Hausdorff–Prokhorov topology:

$\left(V(\mathfrak{K}_{n}),\frac{1}{c_{3}n^{1/4}}\mathrm{d}_{\mathrm{gr}},\mu_{\mathfrak{K}_{n}}\right)\xrightarrow[n\rightarrow\infty]{(d)}\mathrm{m}_{\infty},$
(5)

where $\mathrm{m}_{\infty}$ is the Brownian sphere.

When adapting the framework of Curien and Le Gall to our setting, the main
difficulty comes from the fact that we consider simple triangulations rather
than (unconstrained) triangulations. The article [13] relies extensively on
the so-called _skeleton decomposition_ of triangulations, introduced by Krikun
in [23]. However, the skeleton decomposition does not behave as nicely on
simple triangulations as on general triangulations. To circumvent this issue,
we apply the skeleton decomposition to the model of quasi-simple
triangulations (defined in Section 5). The very nice property of quasi-simple
triangulations is that their skeleton decomposition can be encoded via exactly
the same branching process as general triangulations. Therefore, many results
of [13] extend to our setting effortlessly. This comes at the price that
quasi-simple triangulations are not invariant under re-rooting (its root plays
indeed a special role), so that some arguments need to be adapted. This is the
purpose of Section 6. On the other hand, in his independent preprint [38],
Benedikt Stufler deals directly with a skeleton decomposition for simple
triangulations, where some forbidden configurations have to be handled.

##### From i.i.d edge weights to the scaling limit of random cubic planar
graphs.

Given Theorem 2, there remain two last steps to prove Theorem 1. The first one
deals with the metric property: indeed, we need to relax the hypothesis that
the edge lengths are independent. The second one deals with the measure on the
vertices. Roughly speaking, we have to prove that the uniform measure on the
vertices of a random connected cubic planar graph on one hand, and on the
vertices of its 3-connected core on the other hand, do not differ
asymptotically.

More precisely, to prove Theorem 1, we establish in fact the following joint
convergence result:

######  Theorem 4.

Let $\mathfrak{C}_{n}$ be a uniformly random connected cubic labeled planar
graph (resp. multigraph) with $2n$ vertices. Write $K(\mathfrak{C}_{n})$ for
its 3-connected core and $\Delta(\mathfrak{C}_{n})$ for the (unlabeled,
rooted) dual of $K(\mathfrak{C}_{n})$. We denote respectively by
$\mu_{\mathfrak{C}_{n}}$, $\mu_{K(\mathfrak{C}_{n})}$ and
$\mu_{\Delta(\mathfrak{C}_{n})}$ the uniform measures on
$V(\mathfrak{C}_{n})$, $V(K(\mathfrak{C}_{n}))$ and
$V(\Delta(\mathfrak{C}_{n}))$. Moreover, we write
$\mathrm{dist}_{\mathfrak{C}_{n}}$ for the distance on $K(\mathfrak{C}_{n})$
induced by the graph distance on $\mathfrak{C}_{n}$.

Then, there exist two positive constants $c_{1}$ and $c_{2}$ (with $c_{2}$
explicit) such that:

$\left(\left(\mathfrak{C}_{n},\frac{1}{c_{1}n^{1/4}}\mathrm{d}_{\mathrm{gr}},\mu_{\mathfrak{C}_{n}}\right),\left(K(\mathfrak{C}_{n}),\frac{1}{c_{1}n^{1/4}}\mathrm{dist}_{\mathfrak{C}_{n}},\mu_{K(\mathfrak{C}_{n})}\right),\left(\Delta(\mathfrak{C}_{n}),\frac{1}{c_{2}n^{1/4}}\mathrm{d}_{\mathrm{gr}},\mu_{\Delta(\mathfrak{C}_{n})}\right)\right)\\\
\xrightarrow[n\rightarrow\infty]{(d)}(\mathrm{m}_{\infty},\mathrm{m}_{\infty},\mathrm{m}_{\infty}),$
(6)

where $\mathrm{m}_{\infty}$ is the Brownian sphere. Moreover, a similar result
holds when replacing $\mathfrak{C}_{n}$ by a random connected cubic planar
multigraph $\mathfrak{M}_{n}$.

To establish the joint convergence of the last two coordinates, we construct
in Section 7 an explicit coupling between the models with independent edge-
lengths (sampled from $\nu_{\star}$) and
$\left(K(\mathfrak{C}_{n}),\mathrm{dist}_{\mathfrak{C}_{n}}\right)$. With this
coupling, we prove in Theorem 36 that the Gromov–Hausdorff distance between
both models tends to 0 in probability.

Finally, in Section 8, to establish the joint convergence of the first two
coordinates, we rely on the methodology developed by Addario-Berry and Wen in
[2]. It involves an explicit projection from the vertices of
$\mathfrak{C}_{n}$ to the vertices of its $3$-connected core
$K(\mathfrak{C}_{n})$. The key points are the property that each vertex is
projected to a vertex at distance $o(n^{1/4})$ with high probability, and the
property that the projection of $\mu_{\mathfrak{C}_{n}}$ is asymptotically
close to $\mu_{K(\mathfrak{C}_{n})}$ (in the sense of the Lévy-Prokhorov
distance).

### Acknowledgments

M.A.’s research was supported by the ANR grant GATO (ANR-16-CE40-0009-01) and
the ANR grant IsOMa (ANR-21-CE48-0007). E.F. acknowledges the support of the
ANR grant GATO (ANR-16-CE40-0009-01) and the ANR grant Combine
(ANR-19-CE48-0011).

##  2 Preliminaries

###  2.1 Definitions on graphs and maps

In this article, we consider both multigraphs, and graphs (i.e., multigraphs
with no loop nor multiple edges). A multigraph is called _vertex-labeled_ if
its $n$ vertices carry distinct labels in $[1..n]$, and is called _half-edge-
labeled_ if its $2m$ half-edges carry distinct labels in $[1..2m]$. When
dealing with random cubic planar multigraphs (resp. graphs) we will usually
consider that they are half-edge-labeled (resp. vertex-labeled). A connected
multigraph is _rooted_ if it comes with a distinguished oriented edge called
its _root edge_. The tail vertex of the root edge is called the _root vertex_.

Note that a connected graph or multigraph can be seen as a discrete metric
space, where the distance between two vertices is the minimal length over the
paths connecting them. More generally, we will consider so-called _metric
graphs_ , i.e., graphs where every edge $e$ carries a length
$\ell(e)\in\mathbb{R}_{+}^{*}$. In such a graph seen as a metric space, the
length of a path $\gamma=(e_{1},\ldots,e_{m})$ is defined as
$L(\gamma)=\ell(e_{1})+\cdots+\ell(e_{m})$, and the distance between two
vertices is the length of a shortest path connecting them (on the other hand,
in the context of metric graphs, we will use the notation $|\gamma|$ for the
number of edges in $\gamma$).

A _planar map_ (shortly, a map) $\mathrm{m}$ is a connected multigraph
embedded on the sphere, up to orientation-preserving homeomorphism. A _face_
of $\mathrm{m}$ is a connected component of the sphere cut by the embedding, a
_corner_ of $\mathrm{m}$ is a sector between two consecutive edges around a
vertex (a corner thus lies in a unique face of $\mathrm{m}$). The _degree_ of
a vertex (resp. face) of $\mathrm{m}$ is the number of corners that are
incident to it. A _rooted map_ is a map that comes with a distinguished
oriented edge called its _root edge_ , i.e., the underlying multigraph is
rooted. The face on the right of the root edge is called the _root face_ (also
called the _outer face_ , since it is usually taken as the unbounded face when
the embedding of the map is represented on the plane), and the corner incident
to the root vertex just after the root edge in clockwise order is called the
_root corner_. In general, maps are considered as unlabeled (whether on
vertices or on half-edges). Indeed, in contrast to the situation for
multigraphs, the rooting operation is sufficient to suppress the possibility
of having non-trivial automorphisms. A map is _simple_ if the underlying
multigraph is a graph, i.e. if there is no double edge and no loop.

For $\mathrm{m}$ a map, the _dual map_ $\mathrm{m}^{\dagger}$ is constructed
as follows (see Figure 1): we add a “type F” vertex in every face of
$\mathrm{m}$. Then for every edge $e$ of $\mathrm{m}$, we draw an edge
$e^{\dagger}$ (the _dual edge_ of $e$) between the type F vertices of the two
faces that are incident to $e$, in such a way that $e^{\dagger}$ crosses $e$
and no other edge (including the new ones) — if both sides of $e$ are incident
to the same face, then $e^{\dagger}$ is a loop. Then $\mathrm{m}^{\dagger}$
has vertex set the set of type F vertices, and edge set the set of dual edges.
If $\mathrm{m}$ is rooted, the root edge of $\mathrm{m}^{\dagger}$ is taken as
the dual of the root edge $e$ of $\mathrm{m}$, oriented in such a way that it
crosses $e$ in the counterclockwise direction around the root vertex.

Figure 1: Two examples of triangulations superimposed with their dual. The one
on the left is non-simple while the one on the right is simple. The dual cubic
map is $3$-connected only for the example on the right.

One can see from the definition that $(\mathrm{m}^{\dagger})^{\dagger}$ is the
map obtained from $\mathrm{m}$ by reversing the direction of its root edge.
Furthermore, the one-to-one correspondence between the faces of $\mathrm{m}$
and the vertices of $\mathrm{m}^{\dagger}$ preserves the degree: if $f$ is a
face of $\mathrm{m}$, and $f^{\dagger}$ is the associated vertex of
$\mathrm{m}^{\dagger}$, then
$\deg_{\mathrm{m}}(f)=\deg_{\mathrm{m}^{\dagger}}(f^{\dagger})$. The same
holds for vertices of $\mathrm{m}$: every face of $\mathrm{m}^{\dagger}$
contains a unique vertex of $\mathrm{m}$, and if $v$ is a vertex of
$\mathrm{m}$ and $v^{\dagger}$ is the face of $\mathrm{m}^{\dagger}$ that
contains it, then
$\deg_{\mathrm{m}}(v)=\deg_{\mathrm{m}^{\dagger}}(v^{\dagger})$.

A multigraph or map is called _cubic_ if every vertex has degree $3$. The
_size_ of such a multigraph or map is the integer $n\geqslant 1$ such that the
number of vertices is $2n$ and the number of edges is $3n$. By Euler’s
formula, a cubic map of size $n$ has $n+2$ faces. On the other hand, a
_triangulation_ is a map where all faces have degree $3$. Since taking the
dual of a map sends vertices of the primal to faces of the dual and vice-
versa, it follows that the dual of triangulations are cubic maps; and
conversely, the dual of cubic maps are triangulations. A triangulation with
$n+2$ vertices thus has $2n$ faces and $3n$ edges.

A multigraph is called _$3$ -connected_ it is simple, has at least $4$
vertices, and at least $3$ vertices need to be deleted to disconnect it. By
Whitney’s theorem [43], such a graph has exactly two embeddings on the sphere,
which differ by a mirror. A _$3$ -connected map_ is a map whose underlying
graph is $3$-connected. It is known that duality preserves $3$-connectivity
[31], and that a triangulation is $3$-connected if and only if it is simple.

######  Remark 1.

For a 3-connected graph $\mathrm{k}$ that is vertex-labeled and rooted, we can
canonically choose one of the two embeddings $R,R^{\prime}$ (which differ by a
mirror) as follows. In $R$ we let $f_{1},f_{2}$ be the two faces incident to
the root edge $e$. Let $v_{0}$ be the root-vertex, and let $v_{1}$ (resp.
$v_{2}$) be the unique vertex of $f_{1}$ (resp. $f_{2}$) adjacent to $v_{0}$
and not incident to the root edge. By 3-connectivity, we have $v_{1}\neq
v_{2}$. If the label of $v_{1}$ is smaller than the label of $v_{2}$, then we
take $R$ as the embedding associated to $\mathrm{k}$, otherwise we take
$R^{\prime}$. The _outer edges_ of $\mathrm{k}$ are those incident to the
outer face in the canonical embedding. Note that each $3$-connected
(unlabeled) rooted map with $n$ vertices has $n!/2$ preimages under this
correspondence.

###  2.2 Gromov–Hausdorff–Prokhorov topology

We now define the Gromov–Hausdorff–Prokhorov distance. For details and proofs,
we refer to [9] and [27, Section 6].

Let $(\mathcal{X},\mathrm{d})$ be a metric space. For every
$K\subset\mathcal{X}$ and every $\varepsilon>0$ let
$K^{\varepsilon}=\\{x\in\mathcal{X}:\mathrm{d}(x,K)<\varepsilon\\}$. The
Hausdorff distance between two compact sets $K_{1}$ and $K_{2}$ of
$\mathcal{X}$ is

$\mathrm{d}^{\mathcal{X}}_{\mathrm{H}}(K_{1},K_{2})\overset{\hbox{\tiny{def}}}{=}\inf\\{\varepsilon>0\
:\ K_{1}\subset K_{2}^{\varepsilon}\text{ and }K_{2}\subset
K_{1}^{\varepsilon}\\}.$

The Gromov–Hausdorff distance allows us to compare two compact metric spaces
by isometrically embedding them in a common, larger metric space, and
comparing the Hausdorff distance of their embedding. More formally for every
pair of compact metric spaces $(\mathcal{X},\mathrm{d}^{\mathcal{X}})$ and
$(\mathcal{Y},\mathrm{d}^{\mathcal{Y}})$, we define their Gromov–Hausdorff
distance as:

$\mathrm{d}_{\mathrm{GH}}((\mathcal{X},\mathrm{d}^{\mathcal{X}}),(\mathcal{Y},\mathrm{d}^{\mathcal{Y}}))\overset{\hbox{\tiny{def}}}{=}\inf\\{\mathrm{d}^{\mathcal{Z}}_{\mathrm{H}}(\Phi^{\mathcal{X}}(\mathcal{X}),\Phi^{\mathcal{Y}}(\mathcal{Y}))\\},$

where the infimum is over every metric space $\mathcal{Z}$ and isometries
$\Phi^{\mathcal{X}}:\mathcal{X}\to\mathcal{Z}$ and
$\Phi^{\mathcal{Y}}:\mathcal{Y}\to\mathcal{Z}$. Since isometric spaces are at
Gromov–Hausdorff “distance” zero, $\mathrm{d}_{\mathrm{GH}}$ only defines a
pseudo-distance on compact metric spaces, but it becomes a true distance when
considered on $\mathbb{M}$ the set of compact metric spaces seen up to
isometry. Furthermore, $(\mathbb{M},\mathrm{d}_{\mathrm{GH}})$ is a Polish
space.

If $(\mathcal{Z},\mathrm{d})$ is a metric space with Borel $\sigma$-algebra
$\mathcal{B}(\mathcal{Z})$, we define the Lévy–Prokhorov distance between two
Borel probability measures $\mu,\mu^{\prime}$ on $\mathcal{Z}$ as follows:

$\mathrm{d}_{\mathrm{LP}}^{\mathcal{Z}}(\mu,\mu^{\prime})\overset{\hbox{\tiny{def}}}{=}\inf\\{\varepsilon>0\
:\ \forall
A\in\mathcal{B}(\mathcal{Z}),\mu(A)\leqslant\nu(A^{\varepsilon})+\varepsilon\text{
and }\nu(A)\leqslant\mu(A^{\varepsilon})+\varepsilon\\}.$

If $\mathcal{Z}$ is a Polish space then the Lévy–Prokhorov distance makes the
set of probability measures on $\mathcal{Z}$ a Polish space, and
$\mathrm{d}_{\mathrm{LP}}$ metrizes the weak convergence of measures. There is
also a characterization of
$\mathrm{d}_{\mathrm{LP}}^{\mathcal{Z}}(\mu,\mu^{\prime})$ in terms of
coupling, see for instance [20]. A _coupling_ between $\mu$ and $\mu^{\prime}$
is a probability measure $\nu$ on $\mathcal{Z}\times\mathcal{Z}$ such that
$\pi^{1}_{*}\nu=\mu$ and $\pi^{2}_{*}\nu=\mu^{\prime}$ (where $\pi^{1}$ and
$\pi^{2}$ denote the canonical projections with respect to the first and
second coordinate respectively). We denote by $\mathcal{M}(\mu,\mu^{\prime})$
the set of couplings between $\mu$ and $\mu^{\prime}$. Then, if
$(\mathcal{Z}\times\mathcal{Z})_{\epsilon}$ denotes the set
$\\{(z,z^{\prime})\in\mathcal{Z}\times\mathcal{Z}\,,\,\mathrm{d}(z,z^{\prime})\leqslant\epsilon\\}$,
we have
$\mathrm{d}_{\mathrm{LP}}^{\mathcal{Z}}(\mu,\mu^{\prime})\leqslant\epsilon$ if
and only if there exists a coupling $\nu\in\mathcal{M}(\mu,\mu^{\prime})$ such
that $\nu((\mathcal{Z}\times\mathcal{Z})_{\epsilon})\geqslant 1-\epsilon$.

A weighted metric space is a metric space equipped with a probability Borel
measure. The Gromov–Hausdorff–Prokhorov distance $\mathrm{d}_{\mathrm{GHP}}$
is a metric on isometry classes of compact weighted metric spaces, defined as
follows. For any measured spaces $\mathcal{X},\mathcal{Z}$, measurable
function $\Phi:\mathcal{X}\to\mathcal{Z}$ and measure $\mu$ on $\mathcal{X}$,
write $\Phi_{*}\mu=\mu(\Phi^{-1}(\cdot))$ for the pushforward of $\mu$ under
$\Phi$. Let $(\mathcal{X},\mathrm{d}^{\mathcal{X}})$ and
$(\mathcal{Y},\mathrm{d}^{\mathcal{Y}})$ be two compact metric spaces equipped
respectively with the finite measures $\mu^{\mathcal{X}}$ and
$\mu^{\mathcal{Y}}$; define

$\mathrm{d}_{\mathrm{GHP}}((\mathcal{X},\mathrm{d}^{\mathcal{X}},\mu^{\mathcal{X}})\,,\,(\mathcal{Y},\mathrm{d}^{\mathcal{Y}},\mu^{\mathcal{Y}}))\overset{\hbox{\tiny{def}}}{=}\inf\left\\{\mathrm{d}^{\mathcal{Z}}_{\mathrm{H}}(\Phi^{\mathcal{X}}(\mathcal{X}),\Phi^{\mathcal{Y}}(\mathcal{Y}))\
+\
\mathrm{d}_{\mathrm{LP}}^{\mathcal{Z}}(\Phi^{\mathcal{X}}_{*}\mu^{\mathcal{X}},\Phi^{\mathcal{Y}}_{*}\mu^{\mathcal{Y}})\right\\},$

where (as in the definition of $\mathrm{d}_{\mathrm{GH}}$) the infimum is over
every metric space $(\mathcal{Z},\mathrm{d}^{\mathcal{Z}})$ and isometries
$\Phi^{\mathcal{X}}:\mathcal{X}\to\mathcal{Z}$ and
$\Phi^{\mathcal{Y}}:\mathcal{Y}\to\mathcal{Z}$. Because isometric weighted
metric spaces are at Gromov–Hausdorff–Prokhorov “distance” zero, the function
$\mathrm{d}_{\mathrm{GHP}}$ only defines a pseudo-metric; to make it a true
metric, we consider $\mathbb{K}$ the set of isometry classes of compact
weighted metric spaces. Then $\mathrm{d}_{\mathrm{GHP}}$ defines a true metric
on $\mathbb{K}$, and $(\mathbb{K},\mathrm{d}_{\mathrm{GHP}})$ is a Polish
space.

There exists also an equivalent description of $\mathrm{d}_{\mathrm{GHP}}$
based on couplings which is better suited for our purposes. Let us introduce
the concept of correspondence. A _correspondence_ between two sets
$\mathcal{X},\mathcal{X}^{\prime}$ is a subset
$\mathcal{R}\subset\mathcal{X}\times\mathcal{X}^{\prime}$ such that
$\pi^{\mathcal{X}}(\mathcal{R})=\mathcal{X}$ and
$\pi^{\mathcal{X}^{\prime}}(\mathcal{R})=\mathcal{X}^{\prime}$, where
$\pi^{\mathcal{X}}$, resp. $\pi^{\mathcal{X}^{\prime}}$ is the canonical
projection on $\mathcal{X}$, resp. $\mathcal{X}^{\prime}$. We write
$\mathcal{C}(\mathcal{X},\mathcal{X}^{\prime})$ for the set of correspondences
between $\mathcal{X}$ and $\mathcal{X}^{\prime}$. Given a correspondence,
define its _distortion_

$\operatorname{dis}(\mathcal{R})\overset{\hbox{\tiny{def}}}{=}\sup\left\\{\left|\mathrm{d}^{\mathcal{X}}(x,y)-\mathrm{d}^{\mathcal{X}^{\prime}}(x^{\prime},y^{\prime})\right|\
:\ (x,y),(x^{\prime},y^{\prime})\in\mathcal{R}\right\\}.$

The Gromov–Hausdorff distance can be expressed in terms of distortion:

$\mathrm{d}_{\mathrm{GH}}((\mathcal{X},\mathrm{d}^{\mathcal{X}}),(\mathcal{Y},\mathrm{d}^{\mathcal{Y}}))=\frac{1}{2}\inf\\{\operatorname{dis}(\mathcal{R}):\mathcal{R}\in\mathcal{C}(\mathcal{X},\mathcal{Y})\\},$

and this infimum is attained.

Let $\mathbf{X}=(\mathcal{X},\mathrm{d}^{\mathcal{X}},\mu^{\mathcal{X}})$ and
$\mathbf{Y}=(\mathcal{Y},\mathrm{d}^{\mathcal{Y}},\mu^{\mathcal{Y}})$ be two
weighted metric spaces. Recall the notation
$\mathcal{M}(\mu^{\mathcal{X}},\mu^{\mathcal{Y}})$ for the set of couplings
between $\mu^{\mathcal{X}}$ and $\mu^{\mathcal{Y}}$, then we have the
following alternate characterization of the Gromov–Hausdorff–Prokhorov
distance:

$\mathrm{d}_{\mathrm{GHP}}(\mathbf{X},\mathbf{Y})=\inf\\{\varepsilon>0\ :\
\exists\mathcal{R}\in\mathcal{C}(\mathcal{X},\mathcal{Y}),\exists\nu\in\mathcal{M}(\mu^{\mathcal{X}},\mu^{\mathcal{Y}}),\operatorname{dis}(\mathcal{R})\leqslant
2\varepsilon,\nu(\mathcal{R})\geqslant 1-\varepsilon\\}.$

##  3 The 3-connected core of cubic planar graphs

###  3.1 Decomposition into 3-connected components

We recall here a decomposition [7, 22, 33] of so-called cubic networks
(closely related to rooted cubic planar graphs) and of cubic planar
(multi-)graphs into 3-connected components.

A _cubic network_ is a connected planar multigraph $\mathrm{N}$ with two
marked vertices $v_{-},v_{+}$ called the _poles_ , such that the poles have
degree $1$ and the other vertices have degree $3$. Note that the number of
non-pole vertices has to be a positive even number $2n$, then $n\geqslant 0$
is called the _size_ of $\mathrm{N}$. The two edges adjacent to the poles are
called the _legs_ of $\mathrm{N}$, and the other edges are called _plain_. The
_trivial network_ is the one of size $0$, with a single edge connecting the
two poles. Note that a cubic network $\mathrm{N}$ of positive size identifies
to a rooted cubic planar multigraph $\overline{\mathrm{N}}$, which is obtained
by merging the two poles, smoothing out the merged vertex, and orienting the
resulting edge from the neighbor of $v_{-}$ to the neighbor of $v_{+}$. Then
$\mathrm{N}$ is called _polyhedral_ if $\overline{\mathrm{N}}$ is 3-connected,
in which case the _outer edges_ of $\mathrm{N}$ are the (plain) edges of
$\mathrm{N}$ corresponding to the outer edges (without including the root
edge) of $\overline{\mathrm{N}}$. We also define the _double-edge network_ as
the cubic network of size $1$ where the neighbors of the poles are connected
by a double edge.

Given two non-trivial cubic networks $\mathrm{N}_{1},\mathrm{N}_{2}$, we let
$\mathrm{N}:=\mathrm{N}_{1}+\mathrm{N}_{2}$ be the cubic network obtained by
merging the plus-pole of $\mathrm{N}_{1}$ with the minus-pole of
$\mathrm{N}_{2}$ and smoothing out the merged vertex, so that the plus-pole of
$\mathrm{N}$ is the plus-pole of $\mathrm{N}_{2}$, and the minus-pole of
$\mathrm{N}$ is the minus-pole of $\mathrm{N}_{1}$. A cubic network
$\mathrm{N}$ that can be obtained as
$\mathrm{N}=\mathrm{N}_{1}+\mathrm{N}_{2}$ is called an _$S$ -network_, in
which case $\mathrm{N}$ has a unique decomposition as
$\mathrm{N}=\mathrm{N}_{1}+\mathrm{N}_{2}$ where $\mathrm{N}_{1}$ is a (non-
trivial) non-$S$-network, and by unfolding it also has a unique decomposition
as $\mathrm{N}=\mathrm{N}_{1}+\cdots+\mathrm{N}_{k}$ where each component
$\mathrm{N}_{i}$ is a non-trivial non-$S$-network.

In this article, _edge-substitution_ in a graph $G$ is the operation
consisting, for each edge $e=(u_{-},u_{+})$ of $G$ (canonically endowed with a
minus-extremity and a plus-extremity), of substituting it by a cubic network
$\mathrm{N}_{e}$, so that the plus-pole and minus-pole of $\mathrm{N}_{e}$ are
identified respectively with $u_{-}$ and $u_{+}$ (note that substitution by
the trivial network leaves the edge unchanged). If $G$ is itself a cubic
network, only the plain edges are substituted. A cubic network obtained by
edge-substitution from the double-edge network (resp. from a polyhedral
network) is called an _$P$ -network_ (resp. a _$H$ -network_).

Note that $S$-networks, $P$-networks and $H$-networks are such that the two
poles are at distance greater than $2$. An _$L$ -network_ is a cubic network
$\mathrm{N}$ whose poles are at distance $2$. In an $L$-network, let $u$ be
the common neighbor of the poles, and let $v$ be its other neighbor (note that
the edge $\\{u,v\\}$ is an isthmus). Let $\mathrm{l}_{1}$ be the $L$-network
of size $1$ where $v$ carries a loop. And let $\mathrm{l}_{2}$ be the
$L$-network of size $2$ where $v$ has two neighbors (apart from $u$) each
carrying a loop. As shown in [7, 22], an $L$-network $\mathrm{N}$ is either
obtained from $\mathrm{l}_{1}$ where only the loop-edge is allowed to be
substituted, or is obtained from $\mathrm{l}_{2}$ where only the two loop-
edges are allowed to be substituted (the first and second case correspond
respectively to $N\backslash v$ having two or three connected components). The
two cases are called type 1 and type 2, respectively.

We have the following decomposition result for cubic networks [7, 22]:

######  Lemma 5.

Any non-trivial cubic network is in exactly one of the following classes:
$\\{$$L$-network, $S$-network, $P$-network, $H$-network $\\}$.

Figure 2: Left: a connected (simple) cubic graph $\mathrm{g}$, realized as a
cubic network upon rooting at a (non-isthmus) edge. Right: the associated
decomposition-tree.
The tree is considered as unrooted: it is intrinsic to $\mathrm{g}$ (i.e., it
does not depend on the root-choice), which is also reflected by the difference
in the choice of letters (a series-decomposition in the rooted setting
corresponds to a “ring” of components in the unrooted setting, giving a node
of type $R$). The left part also shows the partition of the vertices of
$\mathrm{g}$ by components (tree-nodes) of type in $\\{L,M,T\\}$.

As detailed in [33] and illustrated in Figure 2, Lemma 5 yields a _tree-
decomposition_ of cubic networks, i.e., a rooted (unembedded) tree
$\tau(\mathrm{N})$ can be associated to a non-trivial cubic network
$\mathrm{N}$, whose inner nodes have labels in $\\{L,R,M,T\\}$. Precisely, if
$\mathrm{N}$ is an $S$-network, of the form
$\mathrm{N}_{1}+\cdots+\mathrm{N}_{k}$, then the root node of
$\tau(\mathrm{N})$ is labeled $R$ and the hanging subtrees are
$\tau(\mathrm{N}_{1}),\ldots,\tau(\mathrm{N}_{k})$ (these are not $S$-network
hence do not have root label $R$). If $\mathrm{N}$ is an $P$-network or
$H$-network, then the root node is labeled $M$ (resp. $T$) and the hanging
subtrees are the trees associated to the substituted networks. Finally, for
$L$-networks, the root node has label $L$. In type 1, it has one child also
labeled $L$ and of arity in $\\{0,1\\}$, depending on whether the loop-edge of
$\mathrm{l}_{1}$ is unchanged or substituted by a non-trivial network
$\mathrm{N}^{\prime}$ (in which case the hanging subtree at the child
corresponds to $\tau(\mathrm{N}^{\prime})$). In type $2$, it has two children
labeled $L$, each corresponding to one of the two loops of $\mathrm{l}_{2}$.
Each child again has arity in $\\{0,1\\}$, depending on whether the
corresponding loop is left unchanged or substituted by a non-trivial network.

Each $T$-node of the tree $\tau(\mathrm{N})$ corresponds to a certain rooted
3-connected planar graph $\mathrm{k}$ whose vertex-set is a subset of the
vertex-set of $\mathrm{N}$. Then $\mathrm{k}$ is called a _3-connected
component_ of $\mathrm{N}$. The hanging subtrees of the node correspond to the
(non-trivial) cubic networks substituted at its edges. As detailed in [33],
the tree-decomposition and 3-connected components are intrinsic to the
underlying unrooted cubic planar graph (essentially it means that rerooting
the cubic multigraph at another non-isthmus edge amounts to rerooting the same
underlying unrooted tree, a fact established by Tutte [42] for the
decomposition of graphs into 3-connected components, which can then be
specialized to the cubic case). Accordingly, to any connected cubic planar
graph $\mathrm{g}$, one can associate an unrooted decomposition tree, denoted
$\tau(\mathrm{g})$. Let us mention the following subtlety: when building the
tree in the rooted case, every $R$-node has arity at least $2$, hence degree
at least $3$ if not at the root and degree at least $2$ if at the root. In
case the root node is of type $R$ of arity $2$, then when unrooting the tree
the corresponding node of degree $2$ is smoothed out, so that all $R$-nodes in
the unrooted tree are of degree at least $3$. The (unrooted) decomposition-
tree satisfies the following properties, which can be visualized in Figure 2:

######  Claim 6.

For $\mathrm{g}$ a connected cubic planar multigraph and $\tau(\mathrm{g})$
the associated decomposition-tree, the vertices of $\mathrm{g}$ are
partitioned among the $L$-components, the $M$-components, and the
$T$-components (3-connected components) of $\tau(\mathrm{g})$ (the
$R$-components have no contribution).

The $L$-components are in one-to-one correspondence with the separating
vertices of $\mathrm{g}$, the $M$-components are in one-to-one correspondence
with vertex-pairs $\\{u,v\\}$ such that $\mathrm{g}$ is obtained by edge-
substitution in the triple-bond connecting $u$ and $v$.

The other vertices belong to the 3-connected components. Precisely, for
$V^{\prime}$ a vertex-subset of $\mathrm{g}$ with $|V^{\prime}|\geqslant 4$,
and $\mathrm{k}$ a 3-connected planar graph (unrooted) with vertex-set
$V^{\prime}$, $\mathrm{k}$ is a 3-connected component of $\mathrm{g}$ if and
only if $\mathrm{g}$ is $\mathrm{k}$ with networks substituted at the edges.

We focus our study first on _simple_ cubic planar graphs; accordingly the
cubic networks are also simple (extension of the arguments to multigraphs will
be given in Section 3.4). In the network-decomposition, this yields the
constraint that loops (when dealing with an $L$-network at the current node)
are to be substituted by non-trivial non-$L$-networks, whereas when
substituting in the double-edge network (when dealing with a $P$-network at
the current node), at least one of the two edges is to be substituted by a
non-trivial network. On the decomposition-tree for unrooted graphs, being
simple is equivalent to the fact that every leaf has label $T$, every $L$-node
of degree $2$ has exactly one neighbor of type $L$, and every $M$-node has
degree in $\\{2,3\\}$; for networks the same constraints hold at non-root
nodes, while the root node is allowed to be a leaf (i.e., to have arity $1$)
of type $L$ or type $M$.

We define families $\mathcal{F}=\cup_{n}\mathcal{F}_{n}$ of cubic simple
networks (with $n$ the size-parameter), where $\mathcal{F}$ is replaced by
$\mathcal{L},\mathcal{S},\mathcal{P},\mathcal{H}$ according to the type; we
also define $\mathcal{D}$ as the family of all simple cubic networks and
$\mathcal{K}$ as the family of polyhedral networks. Each of these families is
vertex-labeled, in the sense that the $2n$ non-pole vertices have distinct
labels in $[1..2n]$ (on the other hand the two poles are unlabeled). We denote
by $F(z)=\sum_{n}\frac{1}{(2n)!}|\mathcal{F}_{n}|z^{n}$ the associated
generating function, replacing $F$ by the corresponding letter for each
family.

We can express $K$ in the following way. Let $\mathcal{T}_{n}$ be the set of
rooted simple planar triangulations with $n+2$ (unlabeled) vertices (and $2n$
faces), and $T(x)=\sum_{n\geqslant 2}|\mathcal{T}_{n}|x^{n}$ the corresponding
ordinary generating function, which is known [41] to have the following exact
expression:

$T(x)=\sum_{n\geqslant
2}\frac{2}{n(n-1)}\binom{4n-3}{n-2}x^{n}=\xi^{2}(1-3\xi+\xi^{2}),$ (7)

where $\xi$ is the unique formal power series in $x$ with constant term equal
to 0 and defined by $x=\xi(1-\xi)^{3}$.

By duality, _simple_ planar triangulations correspond to _3-connected_ cubic
planar maps. Thus, applying Whitney’s theorem and taking vertex-labeling into
account, we have $(2n)!|\mathcal{T}_{n}|=2|\mathcal{K}_{n}|$, hence
$K(x)=T(x)/2$.

Then a decomposition at the root of the decomposition tree of cubic networks
yields the following system (from which the coefficients can be extracted):

$\left\\{\begin{array}[]{rcl}D(z)&=&1+L(z)+S(z)+P(z)+H(z),\\\\[2.84544pt]
L(z)&=&\frac{1}{2}L(z)^{2}+\frac{1}{2}z(D(z)-1-L(z)),\\\\[2.84544pt]
S(z)&=&(D(z)-1-S(z))(D(z)-1),\\\\[2.84544pt]
P(z)&=&\frac{1}{2}z(D(z)^{2}-1),\\\\[2.84544pt]
H(z)&=&\frac{1}{D(z)}K\big{(}zD(z)^{3}\big{)}=\frac{1}{2D(z)}T\big{(}zD(z)^{3}\big{)}.\end{array}\right.$
(8)

In the second line the two terms correspond respectively to the root $L$-node
having arity $2$ or $1$. The last line (with $T(x)$ given in (7)) relies on
the fact that a cubic network of size $n$ has $3n-1$ plain edges.

Let $\mathcal{C}=\cup_{n}\mathcal{C}_{n}$ be the family of vertex-labeled
connected cubic planar graphs of size $n$, i.e., the $2n$ vertices carry
distinct labels in $[1..2n]$. Let $C(z)=\sum_{n\geqslant
1}\frac{1}{(2n)!}|\mathcal{C}_{n}|z^{n}$ be the associated exponential
generating function. Using Claim 6, one obtains the following expression for
the exponential generating function $C^{\bullet}(z)=2zC^{\prime}(z)$ of
pointed (i.e., with a marked vertex) cubic planar graphs [33]:

$C^{\bullet}(z)=\Big{(}\frac{1}{2}\big{(}D(z)-1-L(z)\big{)}L(z)+\frac{1}{6z}L(z)^{3}\Big{)}+\frac{z}{6}(D(z)^{3}-3D(z)+2)+\frac{1}{3}G(z),$
(9)

where we define $G(z):=K(zD(z)^{3})$. The three groups correspond to the
marked vertex being involved in an $L$-component (with the two terms
corresponding to the marked vertex yielding two or three connected components
upon its removal), an $M$-component, and a $T$-component respectively (the
factor $1/3$ in front of $G(z)$ is due to having a marked vertex instead of a
marked directed edge).

###  3.2 Largest 3-connected component

We now use singularity analysis of the involved generating functions, in order
to show (in this subsection and the next one) that a random cubic connected
planar graph almost surely has a unique giant 3-connected component (of linear
size), and to establish related properties. This analysis follows from a well-
established methodology [5, 17]. Similar results appear in the recent preprint
[40] (in particular Theorem 1.2). We provide here our own analysis (thereby
explaining the mild differences with the statements and proof of [40]) for the
sake of completeness, and since we will extend these results to cubic planar
multigraphs in Section 3.4.

If follows from [7, 33, 15] that the generating functions $F(z)$ with
$F\in\\{L,D,G,C^{\bullet}\\}$ have the same radius of convergence $\rho\approx
0.101905$ and these series have singular expansion (in a slit neighborhood) of
the form

$F(z)=F_{0}-F_{2}Z^{2}+F_{3}Z^{3}+O(Z^{4}),\ \ \ \mathrm{where}\
Z=\sqrt{1-z/\rho}.$ (10)

Moreover, these series are analytically continuable to a domain
$\\{|z|\leqslant\rho+\eta,\ z-\rho\notin\mathbb{R}_{+}\\}$ for some $\eta>0$.
By transfer theorems of analytic combinatorics [16, VI.3], we have
$[z^{n}]F(z)\sim\kappa\rho^{-n}n^{-5/2}$, where
$\kappa=\frac{3F_{3}}{4\sqrt{\pi}}$.

We say that a pointed connected cubic planar graph is of type $T$ if the
marked vertex is incident to a $T$-component. According to (9), this occurs
with probability

$[z^{n}]\frac{1}{3}G(z)/[z^{n}]C^{\bullet}(z)\sim\frac{1}{3}G_{3}/C^{\bullet}_{3}.$
(11)

Let $E(z)=zD(z)^{3}$ (note that $E(z)$ also has a singular expansion of the
form $E(z)=E_{0}-E_{2}Z^{2}+E_{3}Z^{3}+O(Z^{4})$), so that the generating
function of cubic connected planar graphs of type $T$ is

$\frac{1}{3}G(z)=\frac{1}{3}K(E(z)).$

As shown in [33], this composition scheme is critical, in the sense that the
radius of convergence of $y\to K(y)$ is $y_{0}=\rho D_{0}^{3}$, and $K(y)$ has
a singular expansion of the form $K(y)=K_{0}-K_{2}Y^{2}+K_{3}Y^{3}+O(Y^{4})$,
with $Y=\sqrt{1-y/y_{0}}$. We can now use the results from [5]. Let $A(x)$ be
the density function defined by

$A(x)=\frac{1}{\pi}\sum_{k\geqslant
1}(-1)^{k-1}x^{k}\frac{\Gamma(1+2k/3)}{\Gamma(1+k)}\mathrm{sin}(2\pi k/3).$

For $c>0$, the probability distribution of density $cA(cx)$ is called _Airy-
map_ distribution of parameter $c$.

######  Proposition 7 (Apply Theorem 5 in [5]).

Define the constants

$p^{\prime}_{\ell}=1-\frac{E_{3}G_{2}}{E_{2}G_{3}},\ \
\alpha=\frac{E(\rho)}{\rho E^{\prime}(\rho)}=\frac{E_{0}}{E_{2}},\ \
c=\frac{1}{\alpha}\left(\frac{E_{2}}{3E_{3}}\right)^{2/3}.$

For $\mathfrak{C}_{n}^{\bullet}$ the random pointed cubic 3-connected planar
graph of type $T$, let $X_{n}$ be the size of the 3-connected component
incident to the marked vertex. Then, for any $x\in\mathbb{R}$ (and uniformly
in any compact set of $\mathbb{R}$)

$P(X_{n}=\lfloor\alpha n+xn^{2/3}\rfloor)=p^{\prime}_{\ell}\ \\!n^{-2/3}\
\\!cA(cx)\cdot(1+o(1)).$

######  Remark 2.

The quantities $\alpha,c$ are explicitly computable, $\alpha\approx 0.8509$ is
root of the polynomial

$\begin{array}[]{c}13026164315213824\,x^{6}-10328139725010432\,x^{4}-1810655504690048\,x^{3}\\\
+1409382842895504\,x^{2}+591702923494104\,x+62103840598801,\end{array}$

and $c\approx 1.5190$ is root of the polynomial

$\begin{array}[]{c}225719792049828011973129\,{x}^{18}-25997088298647780811521072\,{x}^{15}+1072598816640412427380432704\,{x}^{12}\\\
-29427138982726419066720150528\,{x}^{9}+347939923194525847286624477184\,{x}^{6}\\\
-1656815421544715458705316511744\,{x}^{3}+2651264949483594255344169385984.\end{array}$

Compared to [40, Theo 1.2] the constant $c$ differs by a factor $2^{1/3}$;
this is due to the size $n$ being the number of vertices in [40] whereas it is
half the number of vertices here.

The _3-connected core_ of a cubic connected planar multigraph is its largest
$3$-connected component (if there is a tie, we break the tie by choosing the
one whose minimal label is smaller). We now obtain:

######  Theorem 8.

For $\mathfrak{C}_{n}$ the random connected cubic planar graph with $2n$
vertices, let $X_{n}^{*}$ be the size of the 3-connected core of
$\mathfrak{C}_{n}$. Then, for any $x\in\mathbb{R}$ (and uniformly in any
compact set of $\mathbb{R}$), we have, with the constants $\alpha,c$ defined
in Proposition 7:

$P(X_{n}^{*}=\lfloor\alpha n+xn^{2/3}\rfloor)=n^{-2/3}\
\\!cA(cx)\cdot(1+o(1)).$ (12)

Note that Theorem 8 ensures that $X_{n}^{*}$ is concentrated around $\alpha n$
with fluctuations of order $n^{2/3}$, and that $(X_{n}^{*}-\alpha n)/n^{2/3}$
converges in law to the Airy-map distribution of parameter $c$.

###### Proof.

Let $\mathcal{C}_{n}^{\bullet}$ be the set of pointed connected cubic planar
graphs with $2n$ vertices, and let $\mathfrak{C}_{n}^{\bullet}$ be uniformly
random in $\mathcal{C}_{n}^{\bullet}$. In view of (11), if we define

$p_{\ell}:=\frac{G_{3}}{3C^{\bullet}_{3}}p_{\ell}^{\prime}\ =\
\frac{1}{3C^{\bullet}_{3}}\left(G_{3}-\frac{E_{3}G_{2}}{E_{2}}\right),$ (13)

and define $X_{n}$ to be $0$ if $\mathfrak{C}_{n}^{\bullet}$ is not of type
$T$, and $X_{n}$ to be the size of the 3-connected core otherwise, then by
(11) and Proposition 7, we have for any $x\in\mathbb{R}$ (and uniformly in any
compact set of $\mathbb{R}$),

$P(X_{n}=\lfloor\alpha n+xn^{2/3}\rfloor)=n^{-2/3}\ \\!p_{\ell}\
\\!cA(cx)\cdot(1+o(1)).$

To show (12) we rely on a re-rooting argument given in [5, Appendix D]. The
graphs with a giant 3-connected component of size $\approx\alpha n$ incident
to the marked vertex are in proportion $\sim p_{\ell}$ among
$\mathcal{C}_{n}^{\bullet}$, and they admit $\sim 1/\alpha$ re-rootings at an
arbitrary vertex. In addition, they produce different objects in
$\mathcal{C}_{n}^{\bullet}$, because, as observed in [40], the fact that
$\alpha>1/2$ ensures that there is at most one such component within the
graph, for $n$ large enough.

Thus $p_{\ell}/\alpha\leqslant 1$, and to conclude that almost all graphs in
$\mathcal{C}_{n}^{\bullet}$ are of that form it remains to show that
$p_{\ell}=\alpha$. Here we proceed a bit differently from [40]. Rather than
computing the precise evaluations of $\alpha$ and $p_{\ell}$, we will show
that each of $\alpha,p_{\ell}$ has a rational expression in terms of
$\rho,L_{0},L_{2}$ and that these expressions are the same. Thereby our
calculations do not require any evaluations of the involved quantities,
treated as formal symbols, nor the exact expression of $K(x)=T(x)/2$ given in
(7); we just use the fact that the series in $z$ have a singular expansion of
the form (10). (Thus the coincidence of $p_{\ell}$ and $\alpha$ can be seen as
a “generic” property of the decomposition grammar.)

The second line of (8) yields for each $i\in\\{0,2,3\\}$ a rational expression
for $D_{i}$ in terms of $\\{\rho,L_{0},L_{i}\\}$, precisely

$D_{0}=1+\frac{L_{0}(2+\rho-L_{0})}{\rho},\ \
D_{2}=\frac{L_{0}^{2}-2L_{0}L_{2}+L_{2}\rho-2L_{0}+2L_{2}}{\rho},\ \
D_{3}=\frac{L_{3}(2+\rho-2L_{0})}{\rho}.$

Since $E(z)=zD(z)^{3}$, this directly yields for each $i\in\\{0,2,3\\}$ a
rational expression for $E_{i}$ in terms of $\\{\rho,L_{0},L_{i}\\}$, e.g.
$E_{3}=3L_{3}(2+\rho-2L_{0})(L_{0}^{2}-L_{0}\rho-2L_{0}-\rho)^{2}/\rho^{2}$.
We can then inject the expressions of $E_{0}$ and $E_{2}$ into
$\alpha=\frac{E_{0}}{E_{2}}$, and find

$\alpha=\frac{\rho+L_{0}\rho+2L_{0}-L_{0}^{2}}{2L_{0}^{2}-6L_{0}L_{2}+L_{0}\rho+3L_{2}\rho-4L_{0}+6L_{2}+\rho}.$

It remains to find a similar rational expression for
$p_{\ell}=\frac{1}{3C^{\bullet}_{3}}\left(G_{3}-\frac{E_{3}G_{2}}{E_{2}}\right)$.
From (8) we extract the equation (noting that the 3rd line yields
$S(z)=(D(z)-1)^{2}/D(z)$)

$D(z)=\displaystyle
1+L(z)+\frac{(D(z)-1)^{2}}{D(z)}+\frac{1}{2}z(D(z)^{2}-1)+\frac{1}{D(z)}G(z),$

from which we extract for each $i\in\\{0,2,3\\}$ a (quite larger) rational
expression for $G_{i}$ in terms of $\\{\rho,L_{0},L_{i}\\}$. From (9) we can
then extract a rational expression for $C^{\bullet}_{3}$ in terms of
$\\{L_{0},L_{3},\rho\\}$. From the expressions of $E_{2},E_{3},G_{2},G_{3}$,
we obtain a rational expression of $p_{\ell}$ that exactly matches the one of
$\alpha$ given above. Thus $p_{\ell}=\alpha$. ∎

###  3.3 Cubic planar graphs with a marked $3$-connected component

For two integers $n,q$, let $\mathcal{C}_{n}^{(q)}$ be the set of connected
cubic planar graphs of size $n$ having a marked 3-connected component of size
$q$, and denote by $\mathfrak{C}_{n}^{(q)}$ a uniformly random element in
$\mathcal{C}_{n}^{(q)}$. It will also prove convenient for us to see
$\mathfrak{C}_{n}^{(q)}$ as closely related to a model with more independence.
The _critical Boltzmann distribution_ on $\mathcal{D}$ is the probability
distribution $\mu^{(\mathcal{D})}$ defined as

$\mu^{(\mathcal{D})}(\mathrm{d})=\frac{\rho^{|\mathrm{d}|}}{(2|\mathrm{d}|)!D(\rho)}\
\ \ \forall\ \mathrm{d}\in\mathcal{D},$ (14)

where we recall that $\rho$ is the radius of convergence of $D(z)$.

Let $\mathfrak{C}^{(q)}$ be a random connected cubic planar graph with a
marked 3-connected component of size $q$ constructed in the following way.
Letting $\mathrm{K}$ be a uniformly random 3-connected graph of size $q$, we
replace (independently) each edge of $\mathrm{K}$ by a cubic network sampled
from $\mu^{(\mathcal{D})}$. The resulting graph is $\mathfrak{C}^{(q)}$. Note
that, for any $n,q\geqslant 1$, $\mathfrak{C}_{n}^{(q)}$ is distributed as
$\mathfrak{C}^{(q)}$ conditioned to have size $n$.

As stated next, the conditioning probability is polynomial when $q=\alpha
n+O(n^{2/3})$:

######  Lemma 9.

For every $C>0$, we can find $0<c_{-}<c_{+}<\infty$ such that for every $q$
with $|q-\alpha n|\leqslant Cn^{2/3}$, we have
$n^{2/3}\mathbb{P}(|\mathfrak{C}^{(q)}|=n)\in(c_{-},c_{+})$.

Informally, this local limit theorem-type result ensures that when $q,n$ are
related by $q=\alpha n+O(n^{2/3})$, then
$\mathbb{P}(|\mathfrak{C}^{(q)}|=n)=\Theta(n^{-2/3})$. We will often use such
an informal notation thereafter.

###### Proof.

Let $n^{(q)}$ be the size of $\mathfrak{C}^{(q)}$. With $E(z)=zD(z)^{3}$, we
have

$\mathbb{P}(n^{(q)}=n)=[u^{n}]p(u)^{q},\ \ \mathrm{where}\ p(u):=\frac{E(\rho
u)}{E(\rho)}.$

With the notation (10), we have

$p(u)=1+\frac{1}{\alpha}(u-1)+\frac{E_{3}}{E_{0}}(1-u)^{3/2}+O((u-1)^{2}).$

A local limit theorem (for a stable law of parameter $3/2$) holds [5,
Theo.11(ii)]: for $n=\frac{1}{\alpha}q-xq^{2/3}$, uniformly in $x$ on any
compact interval, we have

$\mathbb{P}(n^{(q)}=n)\sim\frac{\tilde{c}A(\tilde{c}x)}{q^{2/3}},$

with $\tilde{c}=(E_{0}/E_{3})^{2/3}$, and $\tilde{c}A(\tilde{c}x)$ the Airy-
map distribution of parameter $\tilde{c}$. ∎

Let $\mathrm{C}$ be a connected cubic planar graph with a marked 3-connected
component $\mathrm{K}$. Note that $\mathrm{C}$ is obtained from $\mathrm{K}$
by substituting every edge of $\mathrm{K}$ by a cubic network; such a network
is called an _attached network of $\mathrm{C}$_.

######  Lemma 10.

Let $\epsilon>0$. When $q,n$ are related by $q=\alpha n+O(n^{2/3})$, then
a.a.s. all attached networks of $\mathfrak{C}_{n}^{(q)}$ have size at most
$n^{2/3+\epsilon}$.

###### Proof.

Let $\epsilon^{\prime}=\epsilon/2$. We argue via $\mathfrak{C}^{(q)}$ and
conditioning on the size. The $3q$ edges of the marked 3-connected component
can be canonically ordered (e.g. lexicographic ordering on the pair of labels
of the incident vertices), which yields a canonical ordering
$M_{1},\ldots,M_{3q}$ of the $3q$ attached networks. In $\mathfrak{C}^{(q)}$
these are independently drawn under $\mu^{(\mathcal{D})}$, and the size of
$\mathfrak{C}^{(q)}$ is $|\mathfrak{C}^{(q)}|=|M_{1}|+\cdots+|M_{3q}|$. Using
[17, Theo.1(iii)-(b)], it follows that

$\mathbb{P}\left(|\mathfrak{C}^{(q)}|<\frac{1}{\alpha}q-q^{2/3+\epsilon^{\prime}}\right)=O(\exp(-q^{\epsilon^{\prime}})).$

(a large deviation result, obtained by a saddle-point estimate).

Similarly, for any $i\in[1..3q]$, we have
$\mathbb{P}(|\mathfrak{C}^{(q)}|-|M_{i}|<\frac{1}{\alpha}q-q^{2/3+\epsilon^{\prime}})=O(\exp(-q^{\epsilon^{\prime}}))$
(we apply the same argument to $(3q-1)$ attached networks instead of $3q$). By
the union bound, the probability that
$|\mathfrak{C}^{(q)}|-|M_{i}|<\frac{1}{\alpha}q-q^{2/3+\epsilon^{\prime}}$ for
some $i\in[1..3q]$ is $O(q\exp(-q^{\epsilon^{\prime}}))$. When conditioning on
$\mathfrak{C}^{(q)}$ to have size $n$, the event that
$|\mathfrak{C}^{(q)}|-|M_{i}|<\frac{1}{\alpha}q-q^{2/3+\epsilon^{\prime}}$ for
some $i\in[1..3q]$ is the same as
$|M_{i}|>n-\frac{1}{\alpha}q+q^{2/3+\epsilon^{\prime}}$ for some
$i\in[1..3q]$. Hence, when $q,n$ are related by $q=\alpha n+O(n^{2/3})$, Lemma
9 ensures that the probability that
$|M_{i}|>n-\frac{1}{\alpha}q+q^{2/3+\epsilon^{\prime}}$ for some $i\in[1..3q]$
is $O(n^{2/3}q\exp(-q^{\epsilon^{\prime}}))=o(1)$. Moreover, for $n$ large
enough, this event is implied by the event that $|M_{i}|>n^{2/3+\epsilon}$ for
some $i\in[1..3q]$. ∎

######  Remark 3.

For $q=\alpha n+O(n^{2/3})$, as already observed in [40] the fact that
$\alpha>1/2$ ensures that for $n$ large enough $\mathfrak{C}_{n}^{(q)}$
coincides with the random connected cubic planar graph $\mathfrak{C}_{n}$
conditioned to have its $3$-connected core of size $q$.

###  3.4 Extension of the results to cubic planar multigraphs

In the context of multigraphs, it is somehow more natural (e.g. for kernel
extraction relations) to consider that the half-edges are labeled instead of
the vertices555This is equivalent to considering vertex-labeled multigraphs
with a certain compensation-factor [21], which for cubic graphs with more than
$2$ vertices is $2^{-\\#\mathrm{loops}-\\#\mathrm{double\ edges}}$.. Thus, let
$\mathcal{M}_{n}$ denote the set of half-edge-labeled connected cubic planar
multigraphs of size $n$ (i.e., with $2n$ vertices), and $\mathfrak{M}_{n}$
denotes an element of $\mathcal{M}_{n}$ taken uniformly at random. Regarding
cubic networks (allowing for loops and multiedges), we consider that, in size
$n$ (i.e., with $2n$ non-pole vertices), the $6n-2$ half-edges on plain edges
carry distinct labels in $[1..6n-2]$. For each family $\mathcal{F}$ of cubic
networks, with
$\mathcal{F}\in\\{\mathcal{D},\mathcal{L},\mathcal{S},\mathcal{P},\mathcal{H}\\}$,
we let $F(z)=\sum_{n}\frac{1}{(6n-2)!}|\mathcal{F}_{n}|z^{n}$ be the
associated generating function. In this context, the equation-system (8)
(again obtained from a decomposition at the root of the associated tree)
becomes

$\left\\{\begin{array}[]{rcl}D(z)&=&1+L(z)+S(z)+P(z)+H(z),\\\\[2.84544pt]
L(z)&=&\frac{1}{2}L(z)^{2}+\frac{1}{2}z\,D(z),\\\\[2.84544pt]
S(z)&=&(D(z)-1-S(z))(D(z)-1),\\\\[2.84544pt]
P(z)&=&\frac{1}{2}z\,D(z)^{2},\\\\[2.84544pt]
H(z)&=&\frac{1}{D(z)}K\big{(}zD(z)^{3}\big{)}=\frac{1}{2D(z)}T\big{(}zD(z)^{3}\big{)}.\end{array}\right.$
(15)

We warn the reader of our abuse of notations, as $D,L,S,P$ and $H$ all denote
different objects in the context of graphs and multigraphs; we do so because
of the extreme similarity of the proofs and results. Which object we consider
should be clear from context. Now, with $M(z)=\sum_{n\geqslant
1}\frac{1}{(6n)!}|\mathcal{M}_{n}|z^{n}$ and
$M^{\bullet}(z)=2z\frac{\mathrm{d}}{\mathrm{d}z}M(z)$, the analogue of (9) is

$M^{\bullet}(z)=\frac{1}{2}D(z)\,L(z)+\frac{1}{6z}L(z)^{3}+\frac{z}{6}D(z)^{3}+\frac{1}{3}G(z),$
(16)

where $G(z)=K(E(z))$, with $E(z)=zD(z)^{3}$ (the series $K(x)$ is the same as
before, since $3$-connected graphs are simple).

We can now rely on the singularity analysis performed in [15, 22] to obtain
the analogue of Theorem 8. The generating functions $F(z)$ with
$F\in\\{L,D,E,G,M^{\bullet}\\}$ have the same radius of convergence
$\rho=54/(79)^{3/2}$ (we still use the letter $\rho$ even if the radius of
convergence for multigraphs is different than for simple graphs), and these
series have singular expansion (in a slit neighborhood) of the form

$F(z)=F_{0}-F_{2}Z^{2}+F_{3}Z^{3}+O(Z^{4}),\ \ \ \mathrm{where}\
Z=\sqrt{1-z/\rho}.$ (17)

As in the case of graphs, the composition scheme in (15) is critical, so that
we can apply Theorem 5 from [5], exactly in the same way as in Proposition 7.
Defining the constants

$p^{\prime}_{\ell}=1-\frac{E_{3}G_{2}}{E_{2}G_{3}},\ \
\alpha=\frac{E(\rho)}{\rho E^{\prime}(\rho)}=\frac{E_{0}}{E_{2}},\ \
c=\frac{1}{\alpha}\left(\frac{E_{2}}{E_{3}}\right)^{2/3},$

we obtain that, for $\mathfrak{M}_{n}^{\bullet}$ the random pointed connected
cubic planar multigraph of size $n$, conditioned to have the marked vertex on
a 3-connected component, the size $X_{n}$ of the 3-connected component at the
marked vertex satisfies for any $x\in\mathbb{R}$ (and uniformly in any compact
set of $\mathbb{R}$)

$P(X_{n}=\lfloor\alpha n+xn^{2/3}\rfloor)=p^{\prime}_{\ell}\ \\!n^{-2/3}\
\\!cA(cx)\cdot(1+o(1)).$

The constants $\alpha,c$ are again explicitly computable, and we find the
following values, much simpler than in the case of graphs:

$\alpha=\frac{199}{316}\approx 0.6297,\ \ \
c=\frac{2}{3}\left(\frac{79}{17}\right)^{2/3}\approx 1.8565.$ (18)

We can now obtain the analogue of Theorem 8.

######  Theorem 11.

For $\mathfrak{M}_{n}$ a uniformly random connected cubic planar multigraph of
size $n$, let $X_{n}^{*}$ be the size of its $3$-connected core. Then, for any
$x\in\mathbb{R}$, and uniformly in any compact set of $\mathbb{R}$,

$P(X_{n}^{*}=\lfloor\alpha n+xn^{2/3}\rfloor)=n^{-2/3}\
\\!cA(cx)\cdot(1+o(1)),$ (19)

where $\alpha,c$ are given in (18).

Again, this implies that $X_{n}^{*}$ is concentrated around $\alpha\,n$, and
$(X_{n}^{*}-\alpha\,n)/n^{2/3}$ converges to the Airy-map distribution of
parameter $c$.

###### Proof.

Similarly as in Theorem 8, we have to check that the constant
$p_{\ell}:=\frac{G_{3}}{3M^{\bullet}_{3}}p_{\ell}^{\prime}$ is equal to
$\alpha$ (again we do not need the precise algebraic equations of the involved
series, the proof is “generic” and does not require the expression of $K(x)$).
The second line of (15) yields, for each $i\in\\{0,2,3\\}$, a rational
expression of $D_{i}$ in terms of $\\{\rho,L_{0},L_{i}\\}$:

$D_{0}=\frac{L_{0}(2-L_{0})}{\rho},\ \
D_{2}=\frac{L_{0}^{2}-2L_{0}L_{2}-2L_{0}+2L_{2}}{\rho},\ \
D_{3}=\frac{2L_{3}(1-L_{0})}{\rho}.$

Using $E(z)=zD(z)^{3}$, this yields, for each $i\in\\{0,2,3\\}$, a rational
expression for $E_{i}$ in terms of $\\{\rho,L_{0},L_{i}\\}$, which gives a
rational expression for $\alpha=\frac{E_{0}}{E_{2}}$. We find

$\alpha=\frac{L_{0}(2-L_{0})}{2(L_{0}^{2}-3L_{0}L_{2}-2L_{0}+3L_{2})}.$

It remains to find a similar rational expression for
$p_{\ell}=\frac{1}{3M^{\bullet}_{3}}\Big{(}G_{3}-\frac{E_{3}G_{2}}{E_{2}}\Big{)}$.
From (15) (note that the third line yields $S(z)=(D(z)-1)^{2}/D(z)$), we
extract the equation

$D(z)=1+L(z)+\frac{(D(z)-1)^{2}}{D(z)}+\frac{1}{2}zD(z)^{2}+\frac{1}{D(z)}G(z),$

which yields, for $i\in\\{0,2,3\\}$, a rational expression for $G_{i}$ in
terms of $\\{\rho,L_{0},L_{i}\\}$. Finally, we can extract from (16) a
rational expression for $M^{\bullet}_{3}$ in terms of
$\\{\rho,L_{0},L_{3}\\}$. Injecting the expressions of
$M^{\bullet}_{3},G_{2},G_{3},E_{2},E_{3}$ into $p_{\ell}$, we obtain a
rational expression for $p_{\ell}$ that exactly matches the one of $\alpha$
given above. Hence $p_{\ell}=\alpha$. ∎

Similarly as for cubic graphs, for two integers $n,q$, we let
$\mathcal{M}_{n}^{(q)}$ be the set of connected cubic planar multigraphs of
size $n$ having a marked 3-connected component of size $q$, and let
$\mathfrak{M}_{n}^{(q)}$ be a uniformly random element in
$\mathcal{M}_{n}^{(q)}$. And we denote by $\mathfrak{M}^{(q)}$ the random
connected cubic planar multigraph with a marked 3-connected component
$\mathrm{K}$ of size $q$, each edge of $\mathrm{K}$ being independently
replaced by a cubic network drawn under the _critical Boltzmann distribution_
on $\mathcal{D}$, i.e., the probability distribution $\mu^{(\mathcal{D})}$
($\mathcal{D}$ denoting here the family of cubic networks allowing for double
edges and loops) defined as

$\mu^{(\mathcal{D})}(\mathrm{d})=\frac{\rho^{|\mathrm{d}|}}{(2|\mathrm{d}|)!D(\rho)}\
\ \ \forall\ \mathrm{d}\in\mathcal{D},$ (20)

where $\rho$ is the radius of convergence of $D(z)$. As before,
$\mathfrak{M}_{n}^{(q)}$ is $\mathfrak{M}^{(q)}$ conditioned to have size $n$.
By a very similar analysis as in Section 3.3, when $n,q$ are related by
$q=\alpha n+O(n^{2/3})$, the probability that $\mathfrak{M}^{(q)}$ has size
$n$ is $\Theta(n^{-2/3})$; and for $\epsilon>0$, a.a.s. every cubic network
attached at the marked 3-connected component has size smaller than
$n^{2/3+\epsilon}$. Moreover, since $\alpha>1/2$, for $q=\alpha n+O(n^{2/3})$
and $n$ large enough, $\mathfrak{M}_{n}^{(q)}$ coincides with the random cubic
connected planar multigraph of size $n$ conditioned to have its $3$-connected
core of size $q$.

##  4 First results about the metric properties of random cubic planar graphs

###  4.1 Pole-distance in cubic networks under the critical Boltzmann
distribution

For $\mathrm{N}$ a cubic network, the _pole-distance_ of $\mathrm{N}$ is the
distance between its two poles, it is denoted $\delta(N)$. We use the notation
$\mathcal{D}$ for the class of networks in both contexts (simple cubic
networks, labeled at non-pole vertices, or cubic networks allowing for loops
and multiedges, labeled at half-edges on plain edges). Let $\nu_{\star}$ be
the distribution of $\delta(N)$, where $\mathrm{N}$ is drawn under
$\mu^{(\mathcal{D})}$ (critical Boltzmann distribution on $\mathcal{D}$). Our
aim here is to show that $\nu_{\star}$ has an exponential tail, both in the
case of graphs and multigraphs (the reason to show this is that $\nu_{\star}$
will be the law of edge-lengths to be considered on the $3$-connected core,
and our subsequent analysis of modified distances in $3$-connected cores
assumes the law of edge-lengths to have exponential tails).

######  Lemma 12.

There exist constants $a_{\star},b_{\star}>0$ such that, for $X$ drawn under
$\nu_{\star}$,

$\mathbb{P}(X>k)\leqslant a_{\star}\exp(-b_{\star}\,k)\ \ \mathrm{for\ all\
}k\geqslant 0.$

###### Proof.

Similarly as in [11, Lem.5.6], the approach is to define another parameter
$\chi$ on cubic networks that dominates $\delta$ and is easier to track along
the network decomposition, and to show via generating functions that $\chi$
has an exponential tail. For $N\in\mathcal{D}$, $\chi(N)$ is defined as
follows:

  * •

if $\mathrm{N}$ is the trivial network then $\chi(N)=1$,

  * •

if $\mathrm{N}$ is of type $L$ then $\chi(N)=2$,

  * •

if $\mathrm{N}$ is of type $R$, of the form $\mathrm{N}_{1}+\mathrm{N}_{2}$
(with $\mathrm{N}_{1}$ a not-$R$ network), then
$\chi(N)=\chi(\mathrm{N}_{1})+\chi(\mathrm{N}_{2})$,

  * •

if $\mathrm{N}$ is of type $M$, with $\mathrm{N}_{1}$ and $\mathrm{N}_{2}$ the
two networks substituted at each edge, then
$\chi(N)=\chi(\mathrm{N}_{1})+\chi(\mathrm{N}_{2})+2$,

  * •

if $\mathrm{N}$ has a 3-connected core $K$, and if
$\mathrm{N}_{1},\ldots,\mathrm{N}_{k}$ are the cubic networks substituted at
the outer edges of $K$, then
$\chi(N)=2+\chi(\mathrm{N}_{1})+\cdots+\chi(\mathrm{N}_{k})$.

It is easy to check recursively along the decomposition that
$\chi(N)\geqslant\delta(N)$ for any $N\in\mathcal{D}$.

For each family $\mathcal{F}$ of networks, we let $F(z,u)$ be the bivariate
generating function (with $z$ for the size and $u$ for the parameter $\chi$).
We also write $T(z,v)$ for the bivariate generating function of rooted simple
triangulations, with $v$ for the root degree minus $1$. By Remark 1,
$T(z,v)/2$ is the bivariate (exponential) generating function of 3-connected
edge-rooted cubic planar graphs, with $v$ conjugate to the number of outer
edges minus $1$. For the case of graphs, the network decomposition gives

$\left\\{\begin{array}[]{rcl}D(z,u)&=&u+L(z,u)+S(z,u)+P(z,u)+H(z,u),\\\
L(z,u)&=&u^{2}L(z),\\\ S(z,u)&=&(D(z,u)-u-S(z,u))(D(z,u)-u),\\\
P(z,u)&=&\frac{1}{2}u^{2}(D(z,u)^{2}-1),\\\
H(z,u)&=&u^{2}\frac{1}{2D(z)}T(zD(z)^{3},D(z,u)/D(z)),\end{array}\right.$ (21)

Hence, noting that $S(z,u)=\frac{(D(z,u)-u)^{2}}{D(z,u)-u+1}$, the series
$D(z,u)$ is solution of the equation in $y$

$A(z,u,y)=0,$ (22)

where

$A(z,u,y)=-y+u+u^{2}L(z)+\frac{(y-u)^{2}}{y-u+1}+\frac{1}{2}u^{2}(y^{2}-1)+\frac{u^{2}}{2D(z)}T(zD(z)^{3},\frac{y}{D(z)}).$

We are now going to prove the property that there exists $u_{0}>1$ such that
$D(\rho,u_{0})$ converges; this will prove the lemma, since for $\mathrm{N}$
drawn under $\mu^{(\mathcal{D})}$ one has

$\mathbb{P}(\delta(N)\geqslant k)\leqslant\mathbb{P}(\chi(N)\geqslant
k)=\sum_{r\geqslant
k}\frac{[u^{r}]D(\rho,u)}{D(\rho)}\leqslant\frac{D(\rho,u_{0})}{D(\rho)}u_{0}^{-k}.$

What we will obtain more precisely is that, in a complex neighborhood of
$(\rho,1)$ (with $\rho$ the radius of convergence of $D(z)$), we have a
singular expansion for $D(z,u)$ of the form

$D(z,u)=\widetilde{D}(Z,U),\ \ \mathrm{with}\ Z=\sqrt{1-z/\rho}\ \mathrm{and}\
U=u-1,$

where $\widetilde{D}(Z,U)$ is analytic around $(0,0)$ and satisfies
$[Z^{1}]\widetilde{D}(Z,U)=0$, and $[Z^{2}]\widetilde{D}(Z,0)\neq 0$; and
moreover we will check that $\rho$ is the radius of convergence of $z\to
D(z,u)$ for $u\in\mathbb{R}$ around $1$.

To prove that, we first obtain a similar singular expansion for $T(x,v)$. An
explicit expression is given in [8]:

$T(x,v)=\frac{1}{2vx}\Big{(}-2v^{2}x^{2}+vx\eta(1+2(1-\eta))-(1-\eta)\eta^{3}-(\eta
vx-(1-\eta)\eta^{3})\sqrt{1-4vx/\eta^{2}}\Big{)},$

where $\eta\equiv\eta(x)$ is the algebraic series given by
$x=\eta^{3}(1-\eta)$, which has an expansion of the form
$\eta(x)=\widetilde{a}(x)+\widetilde{b}(x)\cdot(1-x/x_{\mathrm{c}})^{3/2}$,
where $x_{\mathrm{c}}=27/256$, and $\widetilde{a}(x)$ and $\widetilde{b}(x)$
are analytic around $x_{\mathrm{c}}$, and
$\eta(x_{\mathrm{c}})=\widetilde{A}(x_{\mathrm{c}})=3/4$. Plugging this
expansion into the expression of $T(x,v)$, one obtains an expansion of
$T(x,v)$ around $(x_{\mathrm{c}},1)$ of the form

$T(x,v)=\widetilde{T}(X,V),\ \ \mathrm{with}\ X=\sqrt{1-x/x_{\mathrm{c}}}\
\mathrm{and}\ V=v-1,$

where $\widetilde{T}(X,V)$ is analytic around $(0,0)$ and satisfies
$[X^{1}]\widetilde{T}(X,V)=0$, and $[X^{2}]\widetilde{T}(X,0)\neq 0$. Next, we
have (from [7, 33]) that $L(z)$ and $D(z)$ are of the form
$f(z)=\widetilde{f}(Z)$ with $\widetilde{f}(Z)$ analytic around $0$ and
satisfying $\widetilde{f}^{\prime}(0)=0$ and
$\widetilde{f}^{\prime\prime}(0)\neq 0$; and moreover $\rho
D(\rho)^{3}=x_{\mathrm{c}}$. Plugging these expansions into (22) (see [14,
Sec.2.6] for a similar extraction) we can extract an expansion for $D(z,u)$ of
the form $D(z,u)=\widetilde{D}(Z,U)$, where $\widetilde{D}(Z,U)$ is analytic
around $(0,0)$ and satisfies $[Z^{1}]\widetilde{D}(Z,U)=0$, and
$[Z^{2}]\widetilde{D}(Z,0)\neq 0$.

It remains to check that $\rho$ is the radius of convergence of $z\to D(z,u)$
for $u\in\mathbb{R}$ around $1$. At $u=1$ we know that $\rho$ is the radius of
convergence of $D(z)=D(z,1)$, and thus there is no branch point in (22), i.e.,
$\frac{\partial}{\partial y}A(z,1,D(z))\neq 0$ for every $z\in(0,\rho]$. By
compactness and continuity we thus have $\frac{\partial}{\partial
y}A(z,u,D(z,u))\neq 0$ for $z\in[0,\rho]$ and $u\in\mathbb{R}$ around $1$.
Hence $D(z,u)$ is analytic at $z\in[0,\rho)$ for $u\in\mathbb{R}$ around $1$,
so that (by Pringsheim’s theorem) $\rho$ is the radius of convergence of $z\to
D(z,u)$. Moreover, for any $u>0$, the generating function $z\to D(z,u)$
converges at its radius of convergence $\rho(u)$ (indeed it is solution of a
non-linear positive equation-system). Since $\rho(u)=\rho$ for $u$ close to
$1$, we conclude that there exists $u_{0}>1$ such that $D(\rho,u_{0})$
converges.

The proof for the case of multigraphs is completely similar (the equation-
system is the same, except for $P(z,u)=\frac{1}{2}u^{2}D(z,u)^{2}$). ∎

###  4.2 A first bound on the diameter

For later purpose, we need to establish a first bound on the diameter of
random connected cubic planar graphs (resp. multigraphs), which is the
analogue of the one for random planar graphs obtained in [11]. We say that a
property $A_{n,\epsilon}$ related to a random object of size $n$, and also
formulated in terms of a real parameter $\epsilon>0$, holds _a.a.s. with
exponential rate_ if there are positive constants $a,b,c$ such that
$P(\mathrm{not}\ A_{n,\epsilon})\leqslant a\,\exp(-b\,n^{c\epsilon})$ for all
$n\geqslant 0$ and $\epsilon>0$ small enough. The _diameter_ of a graph
$\mathrm{g}$, denoted $\mathrm{Diam}(\mathrm{g})$, is the maximum of the
pairwise distances between vertices in $\mathrm{g}$.

The purpose of this section is to prove the following result:

######  Proposition 13.

Let $\mathfrak{C}_{n}$ (resp. $\mathfrak{M}_{n}$) be the random connected
cubic planar graph (resp. multigraph) on $2n$ vertices. Then
$\mathrm{Diam}(\mathfrak{C}_{n})\leqslant n^{1/4+\epsilon}$ (resp.
$\mathrm{Diam}(\mathfrak{M}_{n})\leqslant n^{1/4+\epsilon}$) a.a.s. with
exponential rate.

As a first step, we establish the bound in the 3-connected case (starting in
the dual setting of random simple triangulations).

######  Lemma 14.

Let $\mathfrak{t}_{n}$ be the random rooted simple triangulation with $n+2$
vertices. Then $\mathrm{Diam}(\mathfrak{t}_{n})\leqslant n^{1/4+\epsilon}$
a.a.s. with exponential rate.

###### Proof.

Let $\mathcal{T}_{n}^{\prime}$ be the set of rooted triangulations with a
marked vertex (distinct from the root vertex), having $n+2$ vertices. We use
the fact (to be detailed in Section 5.2, and illustrated in Figure 4) that
$\mathcal{T}_{n-1}^{\prime}$ injects into the set $\mathcal{Q}_{n,1}$ of so-
called quasi-simple triangulations of the 1-gon having $n$ inner vertices, in
such a way that the underlying metric space is preserved; and that both
$|\mathcal{Q}_{n,1}|$ and $|\mathcal{T}_{n}^{\prime}|$ are
$\Theta((256/27)^{n}n^{-3/2})$. Let $G(x)$ be the counting series of quasi-
simple triangulations of the 1-gon with respect to the number of vertices
minus $2$. For $i\geqslant 1$, let $G^{(i)}(x)$ be the counting series of
quasi-simple triangulations of the 1-gon where the root vertex and the marked
vertex are at distance $i$, counted with respect to the number of vertices
minus $2$. Let $\mathfrak{q}_{n}$ be the random map in $\mathcal{Q}_{n,1}$.
Denoting by $L_{n}$ the distance between the root vertex and the marked vertex
in $\mathfrak{q}_{n-1}$, we have

$\mathbb{P}(L_{n}=i)=\frac{[x^{n}]G^{(i)}(x)}{[x^{n}]G(x)}.$

An explicit expression666The expression is given for symmetric simple
triangular $k$-dissections of order $k\geqslant 3$ such that the central
vertex is at distance $i$ from the outer boundary; the quotient of these
dissections by the rotation of order $k$ is precisely a quasi-simple
triangulation whose root-vertex is at distance $i$ from the marked vertex. for
$G^{(i)}(x)$ is given in [3, Prop.5.3]. Precisely, there exists an (algebraic)
counting series $Y(x)$, with a quartic dominant singularity at $27/256$,

$Y(x)\sim 1-24^{1/4}(1-256\,x/27)^{1/4},$

such that $G^{(i)}(x)$ is expressed as

$G^{(i)}(x)=Y^{i}(x)\cdot R(Y^{i}(x),Y(x),S(x)),$

where $S(x)=\sqrt{Y(x)^{2}+10Y(x)+1}$, and where $R(z_{1},z_{2},z_{3})$ is an
explicit rational expression that is continuous and positive at
$(z_{1}=0,z_{2}=1,z_{3}=\sqrt{12})$. Let $x_{n}=27/256\cdot(1-1/n)$. Then
$Y(x_{n})=1-(24/n)^{1/4}+o(n^{-1/4})$. Hence, for $\epsilon>0$ and $i\geqslant
n^{1/4+\epsilon}$, we have $Y^{i}(x_{n})=O(\exp(-b\,n^{\epsilon}))$, where $b$
is any positive constant smaller than $24^{1/4}$ (e.g. $b=24^{1/4}/2$). Given
the expression of $G^{(i)}(x)$, we also have
$G^{(i)}(x_{n})=O(\exp(-b\,n^{\epsilon}))$. Hence, for $i\geqslant
n^{1/4+\epsilon}$, we have

$[x^{n}]G^{(i)}(x)\leqslant
G^{(i)}(x_{n})x_{n}^{-n}=O\big{(}\exp(-b\,n^{\epsilon})(256/27)^{n}\big{)}.$

Since $[x^{n}]G(x)=|\mathcal{Q}_{n,1}|=\Theta((256/27)^{n}n^{-3/2})$, we
conclude that $\mathbb{P}(L_{n}=i)=O(n^{3/2}\exp(-b\,n^{\epsilon}))$ uniformly
over $i\geqslant n^{1/4}$, and thus

$\mathbb{P}(L_{n}\geqslant
n^{1/4+\epsilon})=O\big{(}n^{5/2}\exp(-b\,n^{\epsilon})\big{)}=O\big{(}\exp(-n^{\epsilon/2})\big{)},$

so that $L_{n}\leqslant n^{1/4+\epsilon}$ a.a.s. with exponential rate. Let
$\mathfrak{t}_{n}$ be the uniform random rooted simple triangulation with
$n+2$ vertices. Let $\tilde{L}_{n}$ be the distance between the root vertex
and a random vertex (distinct from the root vertex) in $\mathfrak{t}_{n}$.
Note that $\tilde{L}_{n}$ is distributed as $L_{n}$ conditioned on the event
that the triangulation associated with $\mathfrak{q}_{n-1}$ is simple (via the
mapping described in Section 5.2). Since that event has probability
$\Theta(1)$, we conclude that $\tilde{L}_{n}\leqslant n^{1/4+\epsilon}$ a.a.s.
with exponential rate. Since the number of choices for a root and a marked
vertex is $O(n^{2})$, the union-bound ensures that
$\mathrm{Diam}(\mathfrak{t}_{n})\leqslant n^{1/4+\epsilon}$ a.a.s. with
exponential rate. ∎

######  Lemma 15.

Let $\mathfrak{K}_{n}$ be the random 3-connected cubic planar graph on $2n$
vertices. Then $\mathrm{Diam}(\mathfrak{K}_{n})\leqslant n^{1/4+\epsilon}$
a.a.s. with exponential rate.

###### Proof.

Up to choosing one of the two embeddings, and choosing a root edge,
$\mathrm{Diam}(\mathfrak{K}_{n})$ is distributed as the diameter of the random
rooted 3-connected cubic planar map with $2n$ vertices. Let $\mathrm{m}$ be a
planar map, and let $\mathrm{m}^{\dagger}$ be its dual. Let $v,v^{\prime}$ be
vertices in $\mathrm{m}$, let $f$ (resp. $f^{\prime}$) be a face incident to
$v$ (resp. to $v^{\prime}$), and let $v_{f}$ (resp. $v_{f^{\prime}}$) be the
vertex of $\mathrm{m}^{\dagger}$ corresponding to $f$ (resp. to $v^{\prime}$).
From any path $\gamma=(v_{0}=v,\ldots,v_{r}=v^{\prime})$ connecting $v$ to
$v^{\prime}$, it is easy to derive a path $\gamma^{\dagger}$ on
$\mathrm{m}^{\dagger}$ between $v_{f}$ and $v_{f^{\prime}}$ of length at most
$\mathrm{deg}(v_{0})+\cdots+\mathrm{deg}(v_{r})$. Hence, if
$\mathrm{maxDeg}(\mathrm{m})$ denotes the maximal vertex-degree in
$\mathrm{m}$, then we have

$\mathrm{Diam}(\mathrm{m}^{\dagger})\leqslant(1+\mathrm{Diam}(\mathrm{m}))\cdot\mathrm{maxDeg}(\mathrm{m}).$

Hence, $\mathrm{Diam}(\mathfrak{K}_{n})$ is stochastically dominated by
$(1+\mathrm{Diam}(\mathfrak{t}_{n}))\cdot\mathrm{maxDeg}(\mathfrak{t}_{n})$.
Given Lemma 14, it remains to prove that
$\mathrm{maxDeg}(\mathfrak{t}_{n})\leqslant n^{\epsilon}$ a.a.s. with
exponential rate. Letting $\mathrm{rootDeg}(\mathfrak{t}_{n})$ be the root
degree in $\mathfrak{t}_{n}$, we have (with $T(x,v)$ defined in Section 4.1)

$\mathbb{P}(\mathrm{rootDeg}(\mathfrak{t}_{n})=k)=\frac{[x^{n}v^{k}]T(x,v)}{[x^{n}]T(x,1)}.$

The explicit expression [8] of $T(x,v)$ (recalled in Section 4.1) guarantees,
that there exists $v_{0}>1$ such that $C:=T(27/256,v_{0})$ converges as a sum
(any $v_{0}\in(1,4/3)$ fits). We thus have $[x^{n}v^{k}]T(x,v)\leqslant
C\,(256/27)^{n}v_{0}^{-k}$, so that

$\mathbb{P}(\mathrm{rootDeg}(\mathfrak{t}_{n})=k)=O(n^{5/2}v_{0}^{-k}),$

On the other hand, a standard re-rooting argument ensures that

$\mathbb{P}(\mathrm{maxDeg}(\mathfrak{t}_{n})=k)\leqslant
6n\cdot\mathbb{P}(\mathrm{rootDeg}(\mathfrak{t}_{n})=k)=O(n^{7/2}v_{0}^{-k}),$

which is $O(v_{0}^{-n^{\epsilon}/2})$ for $k\geqslant n^{\epsilon}$. Hence,
$\mathrm{maxDeg}(\mathfrak{t}_{n})\leqslant n^{\epsilon}$ a.a.s. with
exponential rate. ∎

Let $\mathrm{g}$ be a (non-rooted) cubic connected planar multigraph, and let
$\tau(\mathrm{g})$ be the associated decomposition-tree. We call _$R$
-attached network within $\mathrm{g}$_ one of the cubic networks assembled
around an $R$-cycle of components (node of label $R$ in $\tau(\mathrm{g})$).
Note that such a component must be a non-trivial non-$S$-network. It
corresponds to an edge $e$ with a $R$ extremity in $\tau(\mathrm{g})$,
precisely it is the network associated to the subtree hanging from the non-$R$
side of $e$. We let $\delta_{R}(\mathrm{g})$ be the maximal value of
$\delta(N)$ over all $R$-attached networks within $\mathrm{g}$. And we let
$\xi_{R}(\mathrm{g})$ be the maximal degree over all $R$-nodes of
$\tau(\mathrm{g})$. Similarly, we define a _$T$ -attached network_ as a
network substituted at one of the edges of a $T$-component of $\mathrm{g}$. It
corresponds to an edge $e$ with a $T$ extremity in $\tau(\mathrm{g})$,
precisely it is the network associated to the subtree hanging from the other
side of $e$. We let $\delta_{T}(\mathrm{g})$ be the maximal value of
$\delta(N)$ over all $T$-attached networks within $\mathrm{g}$. And we let
$\xi_{T}(\mathrm{g})$ be the maximal diameter over all 3-connected components
of $\mathrm{g}$.

Similarly as in [11, Eq.(6)], the following bound on the diameter of
$\mathrm{g}$ holds:

######  Claim 16.

We have

$\mathrm{Diam}(\mathrm{g})\leqslant(1+\mathrm{Diam}(\tau(\mathrm{g})))\cdot(2+\xi_{R}(\mathrm{g})\delta_{R}(\mathrm{g})+\xi_{T}(\mathrm{g})\delta_{T}(\mathrm{g})).$

###### Proof.

A diametral path $\gamma$ in $\mathrm{g}$ induces a path $\gamma^{\prime}$ in
$\tau(\mathrm{g})$. Some edges on $\gamma$ correspond to edges of
$\gamma^{\prime}$ (where $\gamma$ leaves a component and enters another
component). The other edges of $\gamma$ are “consumed” within the nodes on
$\gamma^{\prime}$. For a $T$-node $w$ visited by $\gamma$, corresponding to a
$3$-connected component $\mathrm{K}$, the length of $\gamma$ consumed within
$w$ is bounded by
$\mathrm{Diam}(\mathrm{K})\cdot\mathrm{max}_{N\in\mathrm{att}_{w}}\delta(N)$,
where $\mathrm{att}_{w}$ is the set of $T$-attached networks at $\mathrm{K}$.
Similarly, for an $R$-node $w$, of degree $k$, visited by $\gamma$, the length
of $\gamma$ consumed within $w$ is bounded by
$k\cdot\mathrm{max}_{N\in\mathrm{att}_{w}}\delta(N)$, where $\mathrm{att}_{w}$
is the set of $R$-attached networks at $w$. Finally, for an $M$-node $w$, at
most one edge of $\gamma$ is consumed by $w$ (this happens if one of the three
edges of the $M$-component for $w$ is not substituted, and this edge is
traversed by $\gamma$). ∎

In view of Claim 16, in order to conclude the proof of Proposition 13, it just
remains to show the following.

######  Lemma 17.

For $\mathfrak{C}_{n}$ the random connected cubic planar graph with $2n$
vertices, we have

$\mathrm{Diam}(\tau(\mathfrak{C}_{n}))\leqslant n^{\epsilon},\ \
\delta_{R}(\mathfrak{C}_{n})\leqslant n^{\epsilon},\ \
\delta_{T}(\mathfrak{C}_{n})\leqslant n^{\epsilon},\ \
\xi_{R}(\mathfrak{C}_{n})\leqslant n^{\epsilon},\ \
\xi_{T}(\mathfrak{C}_{n})\leqslant n^{1/4+\epsilon}$

a.a.s. with exponential rate.

The same holds when replacing $\mathfrak{C}_{n}$ by $\mathfrak{M}_{n}$.

###### Proof.

We give the proof details for graphs (the arguments for multigraphs are
completely similar). We start with $\xi_{T}(\mathfrak{C}_{n})$. Consider a
3-connected component $\mathrm{K}$ in $\mathfrak{C}_{n}$, and let
$n^{\prime}\leqslant n$ be its size. Then $\mathrm{K}$ is uniformly
distributed over cubic 3-connected planar graphs with $2n^{\prime}$ vertices.
If $n^{\prime}\leqslant n^{1/4}/2$, then obviously
$\mathrm{Diam}(\mathrm{K})\leqslant n^{1/4+\epsilon}$. If
$n^{\prime}\in[n^{1/4}/2,n]$, then by Lemma 15 there are positive constants
$a,b,c$ such that, for $\epsilon>0$ small enough, we have (where Lemma 15
yields the middle inequality):

$\mathbb{P}(\mathrm{Diam}(\mathrm{K})\geqslant
n^{1/4+\epsilon})\leqslant\mathbb{P}(\mathrm{Diam}(\mathrm{K})\geqslant
n^{\prime}\,{}^{1/4+\epsilon})\leqslant
a\,\exp\big{(}-b\,n^{\prime}\,{}^{c\epsilon})\leqslant
a\,\exp\big{(}-b\,n^{c\epsilon/4}/2^{c\epsilon}\big{)}.$

Hence, uniformly over $n^{\prime}\in[0,n]$, the diameter of a random
$3$-connected cubic planar graph of size $n^{\prime}$ is smaller than
$n^{1/4+\epsilon}$ a.a.s. with exponential rate. Since the number of
$3$-connected components in $\mathfrak{C}_{n}$ is $O(n)$, by the union-bound
we conclude that $\xi_{T}(\mathfrak{C}_{n})\leqslant n^{1/4+\epsilon}$ a.a.s.
with exponential rate.

We now deal with $\xi_{R}(\mathfrak{C}_{n})$. Let $\bar{S}(z):=L(z)+P(z)+H(z)$
be the generating function for cubic networks that are eligible to be
$R$-attached (i.e., non-trivial non-$R$ cubic networks). From the 1st and 3rd
line in (8) (or directly, from the decomposition of $S$-networks), we get
$S(z)=\frac{\bar{S}^{2}}{1-\bar{S}(z))}$. Since $S(z)$ converges at $\rho$, we
must have $\bar{S}(\rho)\in(0,1)$. For $k\geqslant 3$, the generating function
of connected cubic planar graphs with a marked $R$-component of degree $k$ is
equal to $\bar{S}(z)^{k}/k$. Hence, for $k\geqslant 3$, the number of
connected cubic planar graphs of size $n$ having a marked $R$-component of
degree $k$ is bounded by $(2n)![z^{n}]\bar{S}(z)^{k}$, which itself is bounded
by $(2n)!\beta^{k}\rho^{-n}$, where $\beta=\bar{S}(\rho)\in(0,1)$. The number
of connected cubic planar graphs of size $n$ having a marked $R$-component of
degree larger than $k$ is thus bounded by
$(2n)!\frac{\beta^{k}}{1-\beta}\rho^{-n}$. Since the number of $R$-component
is $O(n)$, the number of connected cubic planar graphs of size $n$ having at
least one $R$-component of degree larger than $k$ is
$O((2n)!n\frac{\beta^{k}}{1-\beta}\rho^{-n})$ On the other hand, the number of
connected cubic planar graphs of size $n$ is $\Theta((2n)!\rho^{-n}n^{-7/2})$.
Hence, the probability that $\mathfrak{C}_{n}$ has an $R$-component of degree
larger than $k$ is $O(n^{9/2}\beta^{k})$, which is $O(\beta^{n^{\epsilon}/2})$
for $k\geqslant n^{\epsilon}$, ensuring that
$\xi_{R}(\mathfrak{C}_{n})\leqslant n^{\epsilon}$ a.a.s. with exponential
rate.

We now consider the parameter $\delta_{T}(\mathfrak{C}_{n})$. Again, we use
the fact that a $T$-attached network of size $n^{\prime}$ in
$\mathfrak{C}_{n}$ is uniformly distributed over cubic networks of size
$n^{\prime}$. This distribution is also $\mu^{(\mathcal{D})}$ conditioned to
have size $n^{\prime}$, an event that occurs with probability
$\Theta(n^{\prime}\,{}^{-5/2})$ (as follows from the asymptotic form of the
counting coefficients for cubic networks). Hence, letting
$\mathrm{D}_{n^{\prime}}$ be the random cubic network of size $n^{\prime}$,
Lemma 12 ensures that there are positive constants $a_{\star},b_{\star}$ such
that

$\mathbb{P}(\delta(\mathrm{D}_{n})>k)\leqslant a\,n^{5/2}\exp(-b\,k).$

Hence, $\delta(\mathrm{D}_{n^{\prime}})\leqslant n^{\epsilon}$ a.a.s. with
exponential rate, uniformly over $n^{\prime}\leqslant n$. Since the number of
$T$-attached networks in $\mathfrak{C}_{n}$ is $O(n)$, the union bound ensures
that $\delta_{T}(\mathfrak{C}_{n})\leqslant n^{\epsilon}$ a.a.s. with
exponential rate. The same argument is easily adapted to
$\delta_{R}(\mathfrak{C}_{n})$ as well (an $R$-attached network of size
$n^{\prime}$ is a network drawn under $\mu^{(\mathcal{D})}$ conditioned to
have size $n^{\prime}$ and to be a non-trival non-$S$-network, an event that
holds with probability $\Theta(n^{\prime}\,{}^{-5/2})$).

We now consider $\mathrm{Diam}(\tau(\mathfrak{C}_{n}))$. We first rewrite the
system (8) in a positive form, where $t_{n}$ is the number of rooted simple
triangulations with $2n$ faces.

$\left\\{\begin{array}[]{ll}L(z)&=\frac{1}{2}L(z)^{2}+\frac{1}{2}z(S(z)+P(z)+H(z)),\\\
S(z)&=\frac{(L(z)+P(z)+H(z))^{2}}{1-(L(z)+P(z)+H(z))}\\\
P(z)&=\frac{1}{2}z\big{(}(L(z)+S(z)+P(z)+H(z))\cdot(2+L(z)+S(z)+P(z)+H(z))\big{)}\\\
H(z)&=\frac{1}{2}\sum_{n\geqslant
2}t_{n}z^{n}\big{(}1+L(z)+S(z)+P(z)+H(z)\big{)}^{3n-1}.\end{array}\right.$

This system, of the form $\mathbf{y}=\mathbf{F}(z,\mathbf{y})$, is
irreducible. It is also critical in the sense of [11, Sec.5], as the
quantities $L^{\prime}(z),S^{\prime}(z),P^{\prime}(z),H^{\prime}(z)$ converge
when $z\in(0,\rho)$ tend to $\rho$. For $h\geqslant 0$, let
$L_{h}(z),S_{h}(z),P_{h}(z),H_{h}(z)$ be the counting series gathering the
contributions of $L(z),S(z),P(z),H(z)$ where the associated decomposition-tree
has height at most $h$, and let
$\mathbf{y}_{h}=(L_{h}(z),S_{h}(z),P_{h}(z),H_{h}(z))$. We clearly have
$\mathbf{y}_{h+1}=\mathbf{F}(z,\mathbf{y}_{h})$ for $h\geqslant 0$. Thus, the
height of the decomposition-tree is a height-parameter for the system, with
the terminology of [11, Sec.5]. We can then rely on [11, Lem.5.3.], which
ensures that for a random cubic network in each type $\in\\{L,S,P,H\\}$, the
height of the decomposition-tree is bounded by $n^{\epsilon}$ a.a.s. with
exponential rate. Since the diameter of a rooted tree is at most twice its
height, we easily conclude (via the decomposition (9) for pointed cubic
connected planar graphs in terms of cubic networks) that
$\mathrm{Diam}(\tau(\mathfrak{C}_{n}))\leqslant n^{\epsilon}$ a.a.s. with
exponential rate. ∎

##  5 Skeleton decomposition for quasi-simple triangulations

We introduce in this section a modification of simple triangulations, which
will prove to be more convenient to deal with, when studying Krikun’s skeleton
decomposition. We will indeed prove in Sections 5.4 and 5.5 that the skeleton
of these so-called _quasi-simple triangulations_ admit exactly the same
encoding by a branching process as general triangulations.

###  5.1 Simple triangulations

For every $n\geqslant 1$, we write $\mathcal{T}_{n}$ be the set of rooted
simple triangulations with $n+2$ vertices. Then, for every $p\geqslant 3$ and
$n\geqslant 0$, let $\mathcal{T}_{n,p}$ be the set of simple triangulations of
the $p$-gon with $n$ inner vertices (that is, simple triangulations whose root
face is a simple cycle of degree $p$, with $n$ vertices that are not incident
to the root face). Observe in particular that
$\mathcal{T}_{n}=\mathcal{T}_{n-1,3}$. Enumerative formulas for
$\mathcal{T}_{n,p}$ have been obtained by Brown in [8] and read:

$|\mathcal{T}_{n,p}|=\frac{2(2p-3)!}{(p-1)!(p-3)!}\frac{(4n+2p-5)!}{n!(3n+2p-3)!}\quad\text{for}\quad
n\geqslant 0,\,p\geqslant 3.$ (23)

We deduce from this expression and from Stirling’s formula that:

$|\mathcal{T}_{n,p}|\stackrel{{\scriptstyle[}}{{n}}\rightarrow\infty]{}{\sim}C^{\star}(p)\left(\frac{256}{27}\right)^{n}n^{-5/2},$
(24)

with

$C^{\star}(p)=\frac{\sqrt{3}}{64\sqrt{2\pi}}(p-2)\binom{2(p-1)}{p-1}\left(\frac{16}{9}\right)^{p-1}\stackrel{{\scriptstyle[}}{{p}}\rightarrow\infty]{}{\sim}\frac{\sqrt{6}}{64\pi}\sqrt{p}\left(\frac{64}{9}\right)^{p-1}=\frac{9\sqrt{6}}{4096\pi}\sqrt{p}\left(\frac{64}{9}\right)^{p}.$
(25)

Because of the polynomial correction in $n^{-5/2}$ (usual for planar maps),
the generating series $T_{p}(x):=\sum_{n\geqslant 0}|\mathcal{T}_{n,p}|x^{n}$
evaluated at $x=27/256$ converge for every value of $p$. Following [8, (4.5)],
we get:

$Z(p):=T_{p}\left(\frac{27}{256}\right)=\frac{1}{p(2p-3)}\left(\frac{16}{9}\right)^{p-2}\binom{2(p-1)}{p-1}.$
(26)

From which we deduce:

$Z(p)\stackrel{{\scriptstyle[}}{{p}}\rightarrow\infty]{}{\sim}\frac{2}{\sqrt{\pi}}\left(\frac{64}{9}\right)^{p-2}p^{-5/2}=\frac{18}{64\sqrt{\pi}}\left(\frac{64}{9}\right)^{p-1}p^{-5/2}.$
(27)

The _critical Boltzmann distribution_ on simple triangulations of the $p$-gon
is the one assigning probability $(27/256)^{n}/Z(p)$ to the elements in
$\mathcal{T}_{n,p}$, for $n\geqslant 0$.

###  5.2 Quasi-simple triangulations: definition and enumeration

Figure 3: A quasi-simple triangulation of the 4-gon. Separating 1- and
2-cycles are represented in dashed blue edges.
The pointed vertex is encircled.

Figure 4: Mapping $\Psi$ that turns a quasi-simple triangulation of the 1-gon
into a quasi-simple triangulation of the sphere.
The pointed vertex is encircled.

######  Definition 18.

For $p\geqslant 1$, let $\mathrm{q}$ be a triangulation of the $p$-gon with a
marked inner vertex $v^{\star}$. We call $(\mathrm{q},v^{\star})$ a _quasi-
simple triangulation_ if all its 1-cycles and 2-cycles separate the $p$-gon
and the pointed vertex, see Figure 4.

######  Remark 4.

Observe that in a quasi-simple triangulation, each vertex can carry at most
one loop, otherwise the two loops would form a 2-cycle that does not contain
the pointed vertex.

Therefore, we can turn a quasi-simple triangulation of the 1-gon into a
triangulation of the sphere by merging the two edges that form a triangular
face with the root edge, rooting the modified map at the merged edge so that
the tail vertex is the one incident to the deleted loop, see Figure 4. This
mapping is denoted $\Psi$. Note that $\Psi$ preserves the underlying metric
space.

Reciprocally, the set of pointed and rooted simple triangulations of the
sphere can be seen as a (strict) subset of quasi-simple triangulations of the
1-gon by opening the root edge and inserting a loop incident to the root
vertex inside the 2-gon created.

For every $p\geqslant 1$ and $n\geqslant 0$, let $\mathcal{Q}_{n,p}$ be the
set of quasi-simple triangulations of the $p$-gon with $n$ inner vertices.
Enumerative formulas for $\mathcal{Q}_{n,p}$ have been obtained by Brown in
[8] and we list them here for future reference. Precisely (up to a change of
variable), Brown gives in [8, (8.12)] a formula for the number of simple
triangulations of a $pr$-gon with a rotational symmetry of order $r\geqslant
3$ and $rs+1$ inner vertices, which are in bijection with quasi-simple
triangulations of the $p$-gon with $s+1$ inner vertices, up to marking the
center of rotation and quotienting. For $p\geqslant 1$ and $n\geqslant 1$,
this formula rewrites as:

$|\mathcal{Q}_{n,p}|=\frac{(2p)!(4n+2p-5)!}{(p-1)!p!(n-1)!(3n+2p-3)!}.$ (28)

The asymptotic behavior of $|\mathcal{Q}_{n,p}|$ as $n$ goes to infinity can
be deduced directly from this expression. It is given in [8, (9.1)] and reads:

$|\mathcal{Q}_{n,p}|\stackrel{{\scriptstyle[}}{{n}}\rightarrow\infty]{}{\sim}C(p)\left(\frac{256}{27}\right)^{n}n^{-3/2},$
(29)

with

$C(p)=\frac{\sqrt{3}}{32\sqrt{2\pi}}p\binom{2p}{p}\left(\frac{16}{9}\right)^{p-1}\stackrel{{\scriptstyle[}}{{p}}\rightarrow\infty]{}{\sim}\frac{\sqrt{3}}{8\sqrt{2}\pi}\sqrt{p}\left(\frac{64}{9}\right)^{p-1}=\frac{9\sqrt{3}}{512\sqrt{2}\pi}\sqrt{p}\left(\frac{64}{9}\right)^{p}.$
(30)

Note the unusual polynomial correction in $n^{-3/2}$, which comes from the
fact that quasi-simple triangulations are inherently rooted _and_ pointed. We
hence retrieve the classical behavior of (non-pointed) planar maps with a
polynomial correction in $n^{-5/2}$.

Following the same approach as in the proof of [13, Lemma 1], we obtain from
(28) the following bounds for $|\mathcal{Q}_{n,p}|$:

######  Lemma 19.

There exists a constant $c>0$ (independent of $p$ and $n$) such that, for
every $n\geqslant 1$ and $p\geqslant 1$, we have:

$|\mathcal{Q}_{n,p}|\leqslant c\cdot
C(p)n^{-3/2}\left(\frac{256}{27}\right)^{n}.$

###  5.3 Decomposition of quasi-simple triangulations of the 1-gon into simple
components

Let $\mathcal{Q}_{(1)}$ be the family of quasi-simple triangulations of the
1-gon, where the size-parameter is the number of inner vertices. Let
$\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}$, $\mathcal{T}^{-}$,
$\mathcal{T}^{\bullet\\!\\!-}$, $\mathcal{T}^{\circ\\!-\\!\circ}$ be the
families of rooted simple triangulations with respectively a marked inner
vertex, a marked inner edge, and a marked inner edge incident (resp. not
incident) to the root vertex, where the size-parameter is the number of
vertices minus 2 (which is also half the number of faces). We use a
decomposition of $\mathcal{Q}_{(1)}$ described in [3, Sec.3.2] (decomposition
along the nested sequence of 1-cycles and 2-cycles) that yields
$\mathcal{Q}_{(1)}=\mathcal{X}\cdot\mathcal{U}$, where the families
$\mathcal{U},\mathcal{V}$ admit the following decomposition-grammar:

$\left\\{\begin{array}[]{rl}\mathcal{U}&=\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}+\mathcal{X}\cdot(1+\mathcal{U})+\mathcal{T}^{\bullet\\!\\!-}\cdot\mathcal{U}+\mathcal{T}^{\circ\\!-\\!\circ}\cdot\mathcal{V},\\\
\mathcal{V}&=\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}+2\cdot\mathcal{X}\cdot(1+\mathcal{U})+\mathcal{T}^{-}\cdot\mathcal{V},\end{array}\right.$

with $\mathcal{X}$ an atom that accounts for $1$ in the size.

This system can easily be turned into a regular expression for
$\mathcal{U}=\mathcal{Q}_{(1)}$ involving only the “terminal families”
$\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}$, $\mathcal{T}^{-}$,
$\mathcal{T}^{\bullet\\!\\!-}$, $\mathcal{T}^{\circ\\!-\\!\circ}$ (as well as
the atom-family $\mathcal{X}$). Note that the second line gives

$\mathcal{V}=\big{(}\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}+2\cdot\mathcal{X}+2\cdot\mathcal{X}\cdot\mathcal{U}\big{)}\cdot\mathrm{Seq}(\mathcal{T}^{-}).$

Injecting it into the first line, we obtain

$\mathcal{U}=\mathcal{F}+\mathcal{G}\cdot\mathcal{U},\ \
\mathrm{equivalently}\ \
\mathcal{U}=\mathcal{F}\cdot\mathrm{Seq}(\mathcal{G}),$ (31)

where
$\mathcal{F}=\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}+\mathcal{X}+\mathcal{T}^{\circ\\!-\\!\circ}\cdot(\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}+2\cdot\mathcal{X})\cdot\mathrm{Seq}(\mathcal{T}^{-})$
and
$\mathcal{G}=\mathcal{X}+\mathcal{T}^{\bullet\\!\\!-}+2\cdot\mathcal{X}\cdot\mathcal{T}^{\circ\\!-\\!\circ}\cdot\mathrm{Seq}(\mathcal{T}^{-})$.

######  Lemma 20.

Let $\mathfrak{q}_{n}$ be a uniformly random element of size $n$ in
$\mathcal{Q}_{(1)}$. Let $T(\mathfrak{q}_{n})$ be the largest simple component
of $\mathfrak{q}_{n}$ along the decomposition (31), and let $X_{n}$ be its
half number of faces. Then a.a.s. $T(\mathfrak{q}_{n})$ is in
$\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}},\mathcal{T}^{-}$, or
$\mathcal{T}^{\circ\\!-\\!\circ}$ (not $\mathcal{T}^{\bullet\\!\\!-}$) and
follows the uniform distribution for that family, conditioned on its size. In
addition, the random variable $n-X_{n}$ converges in law, hence is $O(1)$ in
probability.

###### Proof.

We rely on classical results of analytic combinatorics regarding the size of
the largest component in combinatorial decompositions [19]. For
$\alpha\in\mathbb{R}\backslash\mathbb{N}$, a combinatorial class $\mathcal{C}$
is said to be of singularity-type $\alpha$ if the radius of convergence $\rho$
of the counting series $C(z)=\sum_{n}|\mathcal{C}_{n}|z^{n}$ is positive, and
$C(z)$ can be analytically continued to a domain
$\\{|z|\leqslant\rho+\eta,z-\rho\notin\mathbb{R}_{+}\\}$ (for some $\eta>0$),
where it admits a singular expansion around $\rho$ of the form

$C(z)=P(z)+d\,(1-z/\rho)^{\alpha}\,(1+o(1)),$

for some polynomial $P(z)$ of degree smaller than $\alpha$, and some non-zero
constant $d$. Transfer theorems of analytic combinatorics [16, VI.3] then
guarantee that
$|\mathcal{C}_{n}|\sim\frac{d}{\Gamma(-\alpha)}\rho^{-n}n^{-\alpha-1}$. The
following dictionary can then be obtained regarding the size of the greatest
component (we also include a sum-rule to track which families along the
decomposition have asymptotically non-zero probability of having the largest
component):

Sum rule. Let $\mathcal{C}=\mathcal{A}+\mathcal{B}$, where
$\mathcal{A},\mathcal{B}$ have the same radius of convergence $\rho$, and have
respective singularity types $\alpha,\alpha^{\prime}\notin\mathbb{N}$, both
positive. Let $\mathfrak{C}_{n}$ be the random structure in $\mathcal{C}_{n}$.
Then $\mathfrak{C}_{n}$ is almost surely in $\mathcal{A}$ (resp.
$\mathcal{B}$) if $\alpha<\alpha^{\prime}$ (resp. $\alpha^{\prime}<\alpha$).

Product rule. Let $\mathcal{C}=\mathcal{A}\cdot\mathcal{B}$, where
$\mathcal{A},\mathcal{B}$ have the same radius of convergence $\rho$, and have
respective singularity types $\alpha,\alpha^{\prime}\notin\mathbb{N}$, both
positive. Let $\mathfrak{C}_{n}$ be the random structure in $\mathcal{C}_{n}$.
Let $X_{n}$ be the size of its largest component (either in $\mathcal{A}$ or
in $\mathcal{B}$, in $\mathcal{A}$ if there is a tie). Then $n-X_{n}$
converges in law. In addition, the largest component is a.a.s. in
$\mathcal{A}$ (resp. in $\mathcal{B}$) if $\alpha<\alpha^{\prime}$ (resp.
$\alpha^{\prime}<\alpha$).

Sequence rule. Let $\mathcal{C}=\mathrm{Seq}(\mathcal{A})$ (with no object of
size $0$ in $\mathcal{A}$), where $\mathcal{C},\mathcal{A}$ have same radius
of convergence and same positive singularity type $\alpha\notin\mathbb{N}$
(non-critical case in [19]). Let $\mathfrak{C}_{n}$ be the random structure in
$\mathcal{C}_{n}$, and let $X_{n}$ be the size of the largest component (in
$\mathcal{A}$, if there is a tie the leftmost component of largest size is
chosen). Then $n-X_{n}$ converges in law (the limit law having exponential
tail).

We can then use these rules repeatedly in the regular expression (31) to prove
the statement, using also the fact [3] that the counting series of
$\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}$, $\mathcal{T}^{-}$,
$\mathcal{T}^{\bullet\\!\\!-}$, $\mathcal{T}^{\circ\\!-\\!\circ}$ all have
radius of convergence $27/256$, with singularity type $1/2$ for
$\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}$, $\mathcal{T}^{-}$,
$\mathcal{T}^{\circ\\!-\\!\circ}$, and singularity type $3/2$ for
$\mathcal{T}^{\bullet\\!\\!-}$ (the fact that the largest component is a.a.s.
not in $\mathcal{T}^{\bullet\\!\\!-}$ is due to the larger singularity type
for this family). ∎

We will also need the following statement, ensuring that, for the
decomposition (31), the largest simple component of $\mathfrak{q}_{n}$ is
asymptotically distributed as a uniform random rooted simple triangulation
(conditioned on its size):

######  Lemma 21.

Recall the definition of $\mathcal{T}_{n}$. Then, the distribution induced
(upon unmarking) by the uniform distribution on
$\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}_{n}$ (resp.
$\mathcal{T}^{-}_{n}$) is the uniform distribution on $\mathcal{T}_{n}$. And
the distribution induced (upon unmarking) by the uniform distribution on
$\mathcal{T}^{\circ\\!-\\!\circ}_{n}$ is at total-variation distance $o(1)$
from the uniform distribution on $\mathcal{T}_{n}$.

###### Proof.

The statement for $\mathcal{T}^{\scalebox{0.4}{$\blacksquare$}}_{n}$ (resp.
$\mathcal{T}^{-}_{n}$) is obvious, since the number of allowed markings on an
object in $\mathcal{T}_{n}$ is $n-1$ (resp. $3n-3$). For
$\mathcal{T}^{\circ\\!-\\!\circ}_{n}$, the number of allowed markings of an
object in $\mathcal{T}_{n}$, with root degree $d$, is $3n-1-d$. As we have
seen in the proof of Lemma 15, the root degree of the random triangulation in
$\mathcal{T}_{n}$ is a.a.s. at most $n^{\epsilon}$ for any $\epsilon>0$ (even
more is true, it converges in law), hence the number of allowed markings is
concentrated around $3n$, ensuring that the distribution induced by
$\mathcal{T}^{\circ\\!-\\!\circ}_{n}$ on $\mathcal{T}_{n}$ is at total-
variation distance $o(1)$ from the uniform distribution on $\mathcal{T}_{n}$.
∎

###  5.4 Quasi-simple triangulations of the cylinder and their skeleton
decomposition

In this section, we describe the structure of the neighborhood of the root in
a quasi-simple triangulation, and how it can be encoded via the so-called
_skeleton decomposition_ introduced by Krikun in [23]. We follow here the
presentation given by Curien and Le Gall in [13, Section 2.2] for _general_
triangulations, and we emphasize the necessary adjustments to deal with quasi-
simple triangulations. We first introduce quasi-simple triangulations of the
cylinder, which will appear naturally as the hulls of quasi-simple
triangulations.

######  Definition 22.

Fix $r\in\mathbb{Z}_{>0}$. A _quasi-simple triangulation_ of the cylinder of
height $r$ is a rooted planar map such that:

  1. 1.

All its faces are triangles except for two distinguished faces: its root face
(also called the bottom face) and the top face.

  2. 2.

The boundaries of the bottom and of the top face are disjoint simple cycles.

  3. 3.

Every vertex incident to the top face is at graph distance exactly $r$ from
the boundary of the bottom face, and every edge incident to the top face is
also incident to a triangle whose third vertex is at distance $r-1$ from the
bottom face.

  4. 4.

Cycles of length 1 and 2 necessarily separate the bottom face and the top
face.

If $\Delta$ is a quasi-simple triangulation of the cylinder of height $r$, the
boundary of its root face (bottom cycle) is denoted by $\partial\Delta$ and
its top cycle (boundary of the top face) is denoted by $\partial^{*}\Delta$.
We call $\Delta$ a quasi-simple triangulation of the
$(|\partial\Delta|,|\partial^{*}\Delta|)$-cylinder.

Moreover, we denote by $\mathcal{Z}_{p,r}$ the set of quasi-simple
triangulations of the cylinder of height $r$ with a root face of degree $p$.

Note that this is the same definition as [13, Definition 1], except for item
$4$. To describe the encoding of a triangulation of the cylinder via the
skeleton decomposition, we need additional definitions.

######  Definition 23.

Let $\Delta$ be a fixed quasi-simple triangulation of the cylinder of height
$r$. For $1\leqslant j\leqslant r$, the _ball of radius $j$_ of $\Delta$ –
denoted $B_{j}(\Delta)$ – is the submap of $\Delta$, which is spanned by its
faces which are incident to at least one vertex at distance strictly smaller
than $j$ from $\partial\Delta$.

Figure 5: Illustration of the skeleton decomposition of a quasi-simple
triangulation of the $(4,6)$-cylinder of height 2. Downward triangles are
represented by blue shaded triangles. Trees of the forest are represented by
fat red edges and are labeled from $\tau_{1}$ to $\tau_{6}$.

Moreover, the _hull of radius $j$_ of $\Delta$ – denoted
$B^{\bullet}_{j}(\Delta)$ – is defined as the reunion of $B_{j}(\Delta)$ with
the connected components of $\Delta\backslash B_{j}(\Delta)$ that do not
contain $\partial^{*}\Delta$.

Note that for any $j\in\\{1,\ldots,r\\}$, $B^{\bullet}_{j}(\Delta)$ is itself
a quasi-triangulation of the cylinder (of height $j$), and we set
$\partial_{j}(\Delta):=\partial^{*}(B^{\bullet}_{j}(\Delta))$. We extend this
notation to $j=0$ and set $\partial_{0}(\Delta):=\partial\Delta$. Every edge
of $\partial_{j}(\Delta)$ is incident to exactly one triangle whose third
vertex belongs to $\partial_{j-1}(\Delta)$. Such triangles are called the
_downward triangles at height $j$_, and we write $\mathrm{F}_{j}(\Delta)$ for
the set of all downward triangles at height $j$. Let $\bar{E}(\Delta)$ be the
collection of all edges that belong to one of the cycles
$\partial_{j}(\Delta)$, for $0\leqslant j\leqslant r$. The planar embedding of
$\Delta$ enables to encode the edges of $\bar{E}(\Delta)$ as the vertices of a
forest $\mathrm{f}$, with $q$ trees where $q:=|\partial^{\star}|$. This
encoding is depicted in Figure 5 and we refer to [13, page 9] for its formal
definition.

Given the forest $\mathrm{f}:=(\tau_{1},\ldots,\tau_{q})$, to reconstruct the
full quasi-triangulation $\Delta$, we need to fill the “slots” that lie
between successive downward triangles. More precisely, for
$e\in\partial_{j}(\Delta)$ with $1\leqslant j\leqslant r$, we associate to $e$
a (possibly empty) slot in the following way: the slot is included in
$B^{\bullet}_{j}(\Delta)\backslash B^{\bullet}_{j-1}(\Delta)$, and is bounded
by the edges of $\partial_{j-1}(\Delta)$ that correspond to children of $e$
and by the two “vertical” edges that connect the initial vertex of $e$ (when
$\partial_{j}(\Delta)$ is oriented so that $B^{\bullet}_{j}(\Delta)$ lies on
its left) with vertices of $\partial_{j-1}(\Delta)$. The definition should be
clear from Figure 5.

Writing $k_{\mathrm{f}}(e)$ for the number of children of $e$ in the forest
$\mathrm{f}$, the slot associated to $e$ has to be filled with a _simple_
triangulation of the $k_{\mathrm{f}}(e)+2$-gon. Note that, when
$k_{\mathrm{f}}(e)=0$, the slot is filled by the edge-triangulation, or in
other words the two vertical edges defining the slot are identified (whereas
in the setting of [13] of general triangulations, non-trivial slots with a
boundary of length 2 may occur).

To characterize the forests that can appear via the encoding, we need the
following definition:

######  Definition 24.

A forest $\mathrm{f}$ with a marked vertex is said to be $(p,q,r)$-admissible
if:

  1. 1.

The forest $\mathrm{f}:=(\tau_{1},\ldots,\tau_{q})$ is made of $q$ rooted
plane trees,

  2. 2.

The maximal height of these trees is $r$.

  3. 3.

The total number of vertices of the forest at generation $r$ is $p$,

  4. 4.

The distinguished vertex has height $r$,

  5. 5.

The distinguished vertex is in $\tau_{1}$.

We write $\mathrm{f}^{\star}$ for the set of vertices of $\mathrm{f}$ with
height strictly smaller than $r$.

Moreover, the set of $(p,q,r)$-admissible forests is denoted
$\mathcal{F}_{p,q,r}$ and we define $\mathcal{F}_{p,r}:=\cup_{q\geqslant
1}\mathcal{F}_{p,q,r}$.

(a) A separating loop.

(b) A separating pair of edges.

Figure 6: (Top) Two examples of how a loop or a pair of multiple edges can
appear when grafting simple triangulations in the slots of a skeleton. Both
the loop and the multiple edges separate the root face (in grey) from the
pointed vertex (not represented in the figures). (Bottom) The same maps,
represented on the universal cover, are now simple triangulations.

######  Proposition 25.

The skeleton decomposition described above is a bijection between, quasi-
simple triangulations $\Delta$ of the $(p,q)$-cylinder of height $r$, and
pairs $(\mathrm{f},(\mathrm{t}_{v})_{v\in\mathrm{f}^{\star}})$, where
$\mathrm{f}$ is a $(p,q,r)$-admissible forest and for any
$v\in\mathrm{f}^{\star}$, with $e\in\bar{E}(\Delta)$ the corresponding edge,
$\mathrm{t}_{v}$ is a _simple_ triangulation of the
$(k_{\mathrm{f}}(e)+2)$-gon.

We write
$(\mathfrak{F}(\Delta),(\mathrm{t}_{v})_{v\in\mathfrak{F}(\Delta)^{\star}})$
for the image of $\Delta$ via this bijection.

###### Proof.

This proposition is very similar to the skeleton decomposition introduced
originally by Krikun in [23]. However, in this paper, he dealt with _loopless_
triangulations rather than quasi-simple triangulations. In other words, loops
were always forbidden (whereas they are allowed in our setting if they
separate $\partial\Delta$ and $\partial\Delta^{\star}$) and multiple edges
were always authorized (whereas we allow them only if they separate
$\partial\Delta$ and $\partial\Delta^{\star}$). This is the only differences
between his decomposition and ours. Hence, we only need to prove that we
indeed obtain a quasi-simple triangulation. In other words, we only need to
check that 1-cycle and 2-cycle separate $\partial\Delta$ and
$\partial\Delta^{\star}$.

One can argue via the universal cover of the cylinder, which is the periodic
plane $(\mathbb{R}/\mathbb{Z})\times\mathbb{R}$. Indeed, the constraint of
being quasi-simple on the cylinder is equivalent to being simple in the
universal cover representation. Thus, one just has to check that, on
$(\mathbb{R}/\mathbb{Z})\times\mathbb{R}$, the obtained (periodic)
triangulation is simple. Since, in the universal cover representation, each
boundary $\partial_{j}(\Delta)$ can conveniently be drawn as the horizontal
line $\\{y=j\\}$, with the next added layer in the horizontal band
$\\{j\leqslant y\leqslant j+1\\}$, the result follows directly.

For sake of illustration, some configurations in which a loop or a pair of
multiple edges can appear are represented on Figure 6 (note that it is only
possible to have a loop or a pair of edges if $\mathfrak{F}(\Delta)$ has only
one or two vertices at some generation $j$ with $0<j<r$). ∎

###  5.5 Hulls and encoding via a branching process

In this section, we show how the probability to have a fixed neighborhood of
the root can be expressed in terms of a branching process via the skeleton
decomposition.

(a) Balls of radius 1 and 2.

(b) Hulls of radius 1 and 2.

Figure 7: The balls and the hulls in a quasi simple triangulation of the 1-gon
are represented in various shades of blue. The pointed vertex is the encircled
vertex.

######  Definition 26.

Let $(\mathrm{q},v^{*})$ be a quasi-simple triangulation of the $p$-gon. For
$R\geqslant 1$, the _ball of radius $R$_ of $\mathrm{q}$ – denoted
$B_{R}(\mathrm{q})$ – is the submap of $\mathrm{q}$, which is spanned by its
faces which are incident to at least one vertex at distance strictly smaller
than $R$ from its root face, see Figure 7.

Moreover, the _hull of radius $R$_ of $(\mathrm{q},v^{*})$ – denoted
$B^{\bullet}_{R}(\mathrm{q},v^{\star})$ – is defined from $B_{R}(\mathrm{q})$
in the following way. If $\operatorname{dist}(v_{\rho},v^{\star})\leqslant R$,
then $B^{\bullet}_{R}(\mathrm{q},v^{\star})=\mathrm{q}$. Otherwise,
$B^{\bullet}_{R}(\mathrm{q},v^{\star})$ is the submap of $\mathrm{q}$, that
consists of the reunion of $B_{R}(\mathrm{q})$ with the connected components
of $\mathrm{q}\backslash B_{R}(\mathrm{q})$ that do not contain $v^{\star}$.

It follows directly from the definition of the hull, that
$B^{\bullet}_{R}(\mathrm{q},v^{\star})$ is either a quasi-simple triangulation
(with a marked vertex) if
$B^{\bullet}_{R}(\mathrm{q},v^{\star})=(\mathrm{q},v^{\star})$, or a quasi-
simple triangulation of the cylinder $\Delta$, with $|\partial\Delta|=p$,
otherwise.

######  Proposition 27.

Let $p,q,r$ be positive integers. Let $\Delta$ be a quasi-simple triangulation
of the $(p,q)$-cylinder with height $r$. Then, for $\mathfrak{q}_{n}^{(p)}$ a
uniformly random element of $\mathcal{Q}_{n,p}$, we have:

$\mathbb{P}\left({B_{r}^{\bullet}(\mathfrak{q}_{n}^{(p)})}=\Delta\right)\xrightarrow[n\to\infty]{}\frac{\kappa(q)}{\kappa(p)}\prod_{v\in\mathfrak{F}(\Delta)^{\star}}\theta(k_{v})\frac{\rho^{\text{Inn}(\mathfrak{s}_{v})}}{Z(k_{v}+2)},$
(32)

where $\kappa$ and $\theta$ are defined by:

$\kappa(p)=\frac{p}{4^{p}}\binom{2p}{p}\text{ for }p\geqslant
1,\quad\text{and}\quad\theta(k)=\frac{3}{2}\frac{1}{4^{k}}\frac{(2k)!}{k!(k+2)!}\text{
for }k\geqslant 0.$ (33)

######  Remark 5.

It follows from the definition of $\theta$ that:

$\sum_{k\geqslant
0}\theta(k)x^{k}=1-\left(1+\frac{1}{\sqrt{1-x}}\right)^{-2}.$

Hence our definition of $\theta$ matches the definition given in [23, (22)]
and in [13, (15)]. This is not surprising and can be explained via classical
substitution relations between general, loopless and simple triangulations.

Note that Proposition 27 is fully analogous to [13, Lemma 2], except that here
$Z$ and $\rho$ denote respectively the generating series and the radius of
convergence associated to _simple_ triangulations, whereas in [13], they
correspond to _general_ (a.k.a allowing loops and multiple edges)
triangulations.

###### Proof.

We set $\rho=27/256$ to be the radius of convergence of the generating series
of quasi-simple triangulations and $\beta=9/64$ to be inverse of the growth
rate of $Z(p)$ defined in (26). We denote by $|\Delta|$ the total number of
vertices of $\Delta$. Recall that $\mathcal{Q}_{n,p}$ is the set of quasi-
simple triangulations of the $p$-gon with $n$ _inner_ vertices. Then:

$\mathbb{P}\left({B_{r}^{\bullet}(\mathfrak{q}_{n}^{(p)})}=\Delta\right)=\frac{|\mathcal{Q}_{n-|\Delta|+p,q}|}{|\mathcal{Q}_{n,p}|}\stackrel{{\scriptstyle[}}{{n}}\rightarrow\infty]{}{\sim}\frac{C(q)}{C(p)}\rho^{|\Delta|-p},$
(34)

where the asymptotic equivalent is obtained from (29).

To lighten notation, in this proof we set $\mathrm{f}:=\mathfrak{F}(\Delta)$,
and recall that $\mathrm{f}^{*}$ is the set of its vertices with height
strictly smaller than $r$. According to the skeleton decomposition, the
vertices of $\Delta$ can be partitioned into two sets. They either belong to
one of the cycles $\delta_{j}\Delta$, for $0\leqslant j\leqslant r$, or they
are inner vertices of the simple triangulations that are inserted in the
slots. Hence
$|\Delta|=|f^{\star}|+\sum_{v\in\mathrm{f}^{\star}}\text{Inn}(S_{v})$. Since
$|\mathrm{f}^{\star}|=q+\sum_{v\in\mathrm{f}^{\star}}k_{v}$, we get from (34)
that:

$\mathbb{P}\left({B_{r}^{\bullet}(\mathfrak{q}_{n}^{(p)})}=\Delta\right)\stackrel{{\scriptstyle[}}{{n}}\rightarrow\infty]{}{\sim}\frac{C(q)}{C(p)}\rho^{q-p}\prod_{v\in\mathrm{f}^{\star}}\rho^{\text{Inn}(S_{v})+k_{v}}.$

Following similar computations performed in [23] and [13], and in order to
interpret this quantity in terms of a branching process, we perform a change
of variables. Since $\sum_{v\in\mathrm{f}^{\star}}(k_{v}-1)=p-q$, we can
multiply the former expression by
$(\rho/\beta)^{p-q-\sum_{v\in\mathrm{f}^{\star}}(k_{v}-1)}$ to get:

$\mathbb{P}\left({B_{r}^{\bullet}(\mathfrak{q}_{n}^{(p)})}=\Delta\right)\stackrel{{\scriptstyle[}}{{n}}\rightarrow\infty]{}{\sim}\frac{\beta^{q}C(q)}{\beta^{p}C(p)}\prod_{v\in\mathrm{f}^{\star}}\rho^{\text{Inn}(S_{v})+1}\beta^{k_{v}-1}.$

Now, informally, we would like to decompose each term of the product into two
contributions. On the one hand, a term representing the probability for a
vertex to have $k$ children in the skeleton decomposition and, on the other
hand, a term for the probability (under the critical Boltzmann distribution)
that a given simple triangulation of the $(k+2)$-gon appears in the
corresponding slot. To do so, we set $\theta(k):=\rho\beta^{k-1}Z(k+2)$, which
yields:

$\mathbb{P}\left({B_{r}^{\bullet}(\mathfrak{q}_{n}^{(p)})}=\Delta\right)\stackrel{{\scriptstyle[}}{{n}}\rightarrow\infty]{}{\sim}\frac{\beta^{q}C(q)}{\beta^{p}C(p)}\prod_{v\in\mathrm{f}^{\star}}\theta(k_{v})\frac{\rho^{\text{Inn}(S_{v})}}{Z(k_{v}+2)}.$

In view of the definition of $\beta$ and $\rho$ and the expression of $Z(k)$
given in (26), this concludes the proof. ∎

###  5.6 Local limits: quasi-simple UIPT and half-plane models

####  5.6.1 Quasi-simple UIPT

In exactly the same manner as in Section 2.4 of [13], we can define a
probability measure $\mathbf{P}_{p,r}$ on $\mathcal{F}_{p,r}$ by setting for
every forest $\mathrm{f}\in\mathcal{F}_{p,q,r}$:

$\mathbf{P}_{p,r}(\mathrm{f}):=\frac{\kappa(q)}{\kappa(p)}\prod_{v\in\mathrm{f}^{\star}}\theta(k_{v}).$
(35)

We then define a probability measure $\mathbb{P}_{p,r}$ on the set
$\mathcal{Z}_{p,r}$, by saying that under $\mathbb{P}_{p,r}$ the law of the
skeleton on the triangulation is given by $\mathbf{P}_{p,r}$ and,
conditionally given the skeleton, the triangulations filling the slots are
independent critical Boltzmann simple triangulations with a simple boundary
(whose boundary lengths are determined by the skeleton). Proposition 27 can
then be restated as:

$\mathbb{P}\left({B_{r}^{\bullet}(\mathfrak{q}_{n}^{(p)})}=\Delta\right)\xrightarrow[n\to\infty]{}\mathbb{P}_{p,r}(\Delta),$
(36)

for any $\Delta\in\mathcal{Z}_{p,r}$.

It follows from the preceding convergence, that we can define a random
infinite _quasi-simple_ triangulation of the plane with a simple boundary of
length $p$ – denoted $\mathfrak{q}_{\infty}^{(p)}$ – such that the
distribution of $B_{r}^{\bullet}(\mathfrak{q}_{\infty}^{(p)})$ is given by
$\mathbb{P}_{p,r}$, for every integer $r\geqslant 1$. The map
$\mathfrak{q}_{\infty}^{(p)}$ is called the _uniform infinite quasi simple
triangulation_ of the $p$-gon and it follows directly from (36) that
$\mathfrak{q}_{\infty}^{(p)}$ is the local limit of $\mathfrak{q}_{n}^{(p)}$
as $n\rightarrow\infty$.

By the correspondence $\Psi$ (illustrated in Figure 4) between quasi-simple
triangulations of the 1-gon and quasi-simple triangulations of the sphere,
from $\mathfrak{q}_{\infty}^{(1)}$ we can define the so-called _quasi-simple
triangulation of the sphere_ , denoted $\mathfrak{q}_{\infty}$.

####  5.6.2 Half-plane simple models

Recall from Remark 5 that the branching process encoding the skeleton
decomposition of quasi-simple triangulations has exactly the same offspring
distribution as the one obtained in [13] for general triangulations.

In this work, two half-plane models of random geometry are introduced, the
upper half-plane triangulation and the lower half-plane triangulation and we
refer to [13, Section 3] for their construction. This allows us to define
readily the upper half-plane _simple_ triangulation $\mathfrak{U}^{s}$ and the
lower half-plane _simple_ triangulation $\mathfrak{L}^{s}$, by only requiring
that in their construction, the slots are filled with _simple_ triangulations
rather than general triangulations.

All results stated in Sections 3 and 4 of [13] can be extended verbatim to our
setting. Indeed, in most of the proofs they do not need to know how the slots
are filled in, and only study the distribution of the skeleton, which is the
same in our setting and in [13]; the only part that we need to change is in
[13, Lemma 10], where (to reflect the different constants in the enumeration
of simple triangulations) $\rho=12\sqrt{3}$ should be replaced by
$\rho=256/27$ and $\alpha=12$ by $\alpha=64/9$. Notice that triangulations of
the half-plane that we obtain are simple triangulations and not quasi-simple
triangulations, as can be directly observed from the construction of
$\mathfrak{U}^{s}$ and $\mathfrak{L}^{s}$.

####  5.6.3 Coupling between simple and general models

It follows from the preceding section that $\mathfrak{q}^{(1)}_{\infty}$ and
$\mathfrak{L}^{s}$ can be constructed via exactly the same branching process
as the (general) UIPT of the 1-gon and $\mathfrak{L}$ respectively. The only
modification between these pairs of models is that the slots are filled in the
first case by _simple_ critical Boltzmann triangulations with a simple
boundary and in the second case by _general_ critical Boltzmann triangulations
with a simple boundary.

The simple core of a critical Boltzmann general triangulation with a simple
boundary of length $\geqslant 3$ (obtained by collapsing all 2-cycles into
edges) is itself a critical Boltzmann simple triangulation with a boundary. So
that, by taking the simple core of each triangulation grafted in the slots,
this induces a coupling between the (general) UIPT of the $1$-gon and
$\mathfrak{q}^{(1)}_{\infty}$ on one hand and between $\mathfrak{L}$ and
$\mathfrak{L}^{s}$ on the other hand. This remark will be useful to derive
bounds in our model directly from the bounds obtained in [13].

##  6 Modification of distances in simple triangulations

The goal of this section is to give the proof of Theorem 2. To do that, we
follow closely the work of Curien and Le Gall [13] and rely heavily on the
skeleton decomposition of quasi-simple triangulations presented in the
previous section.

Throughout this section, we assume that $\nu$ is a probability distribution
with support included in $[\eta_{0},\infty)$ for a given $\eta_{0}>0$, and
that there exist constants $A,\lambda>0$ such that, for $X$ a random variable
with law $\nu$:

$\mathbb{P}\left(X\geqslant K\right)\leqslant A\exp(-\lambda K),\quad\text{
for any }K\in\mathbb{R}_{+}.$

Moreover, we assume that any planar map $\mathrm{m}$ (random or not)
considered in this section is equipped with a collection $(w_{e})_{e\in
E(\mathrm{m}^{\dagger})}$ of random weights, such that $(w_{e})$ are i.i.d
random variables sampled from $\nu$. Recall from the introduction that we
defined the first-passage percolation distance $\mathrm{d}^{\star}$ on
$\mathrm{m}^{\dagger}$ by setting:

$\mathrm{d}^{\star}_{\nu}(u,v)=\mathrm{d}^{\star}(u,v):=\inf_{\gamma:u\rightarrow
v}\sum_{e\in\gamma}w_{e},\quad\text{ for }u,v\in V(\mathrm{m}^{\dagger})$ (37)

where the infimum runs over all paths $\gamma$ going from $u$ to $v$ in
$\mathrm{m}^{\dagger}$. For the sake of simplicity, we write
$\mathrm{d}^{\star}$ without emphasizing its dependency in $\nu$, it should
not bear any confusion.

Since the skeleton decomposition of quasi-simple triangulations gives the
exact same branching process as the skeleton decomposition of general
triangulations, many results of [13] can be applied verbatim to our setting.
When this is the case, we do not duplicate the proofs. Rather, we only state
the results for which the proofs need to be adapted. Note also that in [13],
the authors focus first on the case of modifications of distances in
triangulations (and not on their dual). They then treat the dual case without
giving as many details as for the primal case.

######  Remark 6.

Theorem 2 and its proof could be extended verbatim to deal with modification
of distances on simple triangulations rather than on their dual as was
initially done in [13]. However, for sake of conciseness, we only give the
proof of this result in the dual setting.

###  6.1 Upper bounds in the infinite models

The purpose of this section is to derive statements similar to Lemma 24 and
Proposition 25 of [13] for the lower half-plane simple triangulation
$\mathfrak{L}^{s}$. For every $j\leqslant 0$, let $\mathfrak{L}_{j}^{s}$ for
the vertices of $\mathfrak{L}^{s}$ that are the vertices of depth $-j$ of its
skeleton; or rather, $\mathfrak{L}_{j}^{s}$ is the set (forming an infinite
simple path) of all edges of $\mathfrak{L}^{s}$ that connect these vertices —
it is the analogue of $\partial_{r+j}(\Delta)$ when $\Delta$ is a quasi-simple
triangulation of the cylinder of height $r$. We also denote by
$\mathrm{F}_{j}(\mathfrak{L}^{s})$ the set of all downward triangles incident
to an edge of $\mathfrak{L}^{s}_{j}$, and by $f_{0,0}$ the face in
$\mathrm{F}_{0}(\mathfrak{L}^{s})$ that is incident to the root edge of
$\mathfrak{L}^{s}$.

Figure 8: Representation of the first 4 layers of $\mathfrak{L}^{s}$. The
downward path started from $f_{0,0}$ is represented in fat red edges.

For every downward triangle $f$ in $\mathrm{F}_{j}(\mathfrak{L}^{s})$, the
downward path from $f$ is an infinite path in the dual map, defined as follows
(see [13, Section 7.2] for a precise definition): starting from $f$, and if
$v$ is the vertex of $f$ that is not an endpoint of an edge of
$\mathfrak{L}^{s}_{j}$, turn around $v$ in counterclockwise order until
crossing an edge of $\mathfrak{L}_{j-1}^{s}$. The face we reach is itself in
$\mathrm{F}_{j-1}(\mathfrak{L}^{s})$: we continue inductively with the
downward path starting from this latter face.

######  Lemma 28.

For $r\geqslant 1$, let $w_{r}$ be the downward path in $\mathfrak{L}^{s}$
connecting $f_{0,0}$ to a downward triangle incident to
$\mathfrak{L}^{s}_{-r}$, and write $|w_{r}|$ for the length of $w_{r}$. There
exist two constants $\mu>0$ and $K<\infty$ such that for every integer
$r\geqslant 1$:

$\mathbf{E}[\exp(\mu\,|w_{r}|)]\leqslant K^{r}.$

###### Proof.

The result follows from Lemma 24 of [13], and from the coupling described in
Section 5.6.3, under which the length of the downward path can only decrease.
∎

For every $j\leqslant 0$, let $\mathfrak{L}^{s,\dagger}_{j}$ be the set of
downward triangles incident to an edge of $\mathfrak{L}^{s}_{j}$ in the lower
half-plane model. We assume that $\mathfrak{L}^{s}$ is equipped with the f.p.p
distance $\mathrm{d}^{\star}$ defined above (the dual map is infinite here,
its vertices corresponding to the triangular faces of $\mathfrak{L}^{s}$, and
its edges corresponding to the edges in $\mathfrak{L}^{s}$ with a triangular
face on each side). Then, Proposition 25 of [13] can be readily adapted into
the following result:

######  Proposition 29.

Recall that the support of $\nu$ is included in $[\eta_{0},\infty)$. There
exists a constant $c_{\nu}\geqslant 2\eta_{0}$ such that:

$r^{-1}\mathrm{d}^{\star}(f_{0,0},\mathfrak{L}^{s,\dagger}_{-r})\xrightarrow[r\rightarrow\infty]{a.s.}c_{\nu}.$

As in the original article, the result follows directly from a subadditive
argument together with the fact that
$\mathbb{E}[\mathrm{d}^{\star}(f_{0,0},\mathfrak{L}^{s,\dagger}_{-r})]<\infty$
by Lemma 28 and
$\mathrm{d}^{\star}(f_{0,0},\mathfrak{L}^{s,\dagger}_{-r})\geqslant
2\eta_{0}r$ by construction.

Thanks to Lemma 28, the proof of Lemma 26 and Corollary 27 of [13] can
directly be extended to our setting. We obtain:

######  Lemma 30.

Consider the quasi-simple UIPT of the 1-gon $\mathfrak{q}_{\infty}^{(1)}$,
with i.i.d weights on its edges sampled from $\nu$. There exist positive
constants $K\textquoteright,\alpha_{0},\beta_{0}$ such that, for any integer
$0\leqslant r<s$:

$\mathbb{P}\left(\mathrm{d}^{\star}(f_{s},B_{r}^{\bullet}(\mathfrak{q}_{\infty}^{(1)}))>\alpha_{0}(s-r)\right)\leqslant
K\textquoteright\exp(-\beta_{0}(s-r)),$ (38)

where $f_{s}$ is a downward triangle at height $s$ chosen uniformly at random,
and where $B_{0}^{\bullet}(\mathfrak{q}_{\infty}^{(1)})$ should be interpreted
as the bottom face.

Moreover, for any fixed $\delta>0$, define $A_{R}(\delta)$ to be the event
where the bound