# Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract

Konstantinos Panagiotou, Benedikt Stufler, Kerstin Weller

► To cite this version:

Konstantinos Panagiotou, Benedikt Stufler, Kerstin Weller. Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.745-756, 10.46298/dmtcs.2461 . hal-01337777

HAL Id: hal-01337777

https://hal.science/hal-01337777

Submitted on 27 Jun 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract

Konstantinos Panagiotou$^{1†}$ and Benedikt Stufler$^{1‡}$ and Kerstin Weller$^{2§}$

$^{1}$Ludwig Maximilian University, Munich, Germany

$^{2}$Eidgenössische Technische Hochschule, Zurich, Switzerland

**Abstract.** We study the uniform random graph $C_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $C_n/\sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_e$ multiplied by a constant scaling factor that depends on the class under consideration. In addition, we provide subgaussian tail bounds for the diameter $D(C_n)$ and height $H(C_n)$ of the rooted random graph $C_n$. We give analytic expressions for the scaling factor of several classes, including for example the prominent class of outerplanar graphs. Our methods also enable us to study first passage percolation on $C_n$, where we show the convergence to $\mathcal{T}_e$ under an appropriate rescaling.

**Résumé.** On s’intéresse au comportement asymptotique du graphe aleatoire $C_n$ sur $n$ sommets pris uniformement d’une classe sous-critique des graphes sur $n$ sommets. Dans cette contribution nous montrons que le graph normalisé $C_n/\sqrt{n}$ converge vers un arbre aleatoire brownien continue $\mathcal{T}_e$ multiplie par une constante qui depends de la classe de graphes considérée. Nous calculons l’expression analytique pour cette constante dans plusieurs cas parmi la classe fameuse des graphes planaire exterieure. En plus, on montre que le diamètre $D(C_n)$ et l’hauteur $H(C_n)$ de l’équivalent racine de $C_n$ sont bornes par des bornes sousgaussiens. Notres méthodes nous permettons aussi de l’étudier la percolation du premier passage sur $C_n$. Nous montrons que $\mathcal{T}_e$ suit a une changement d’échelle appropriée.

**Keywords:** Scaling Limits, Random Graphs, Continuum Random Trees

## 1 Introduction

Let $G$ be a connected graph with vertex set $V(G)$ and edge set $E(G)$. We can associate in a natural way a metric space $(V(G), d_G)$ with $G$, where $d_G(u, v)$ is the number of edges on a shortest path that contains $u$ and $v$ in $G$. In this work we study the case where $G$ is a random graph, and we consider several properties of the associated metric space as the number of vertices of $G$ becomes large.

In the series of seminal papers [3, 4, 5] Aldous studied the fundamental case of $G$ being a critical Galton-Watson random tree with $n$ vertices, where the offspring distribution has finite nonzero variance. Among other results, he showed that the asymptotic properties of the associated metric space admit an

<footnote>†Email: kpanagio@math.lmu.de</footnote>

<footnote>‡Email: stufler@math.lmu.de</footnote>

<footnote>§Email: kerstin.weller@inf.ethz.ch</footnote>
universal description: they can be depicted, up to an appropriate rescaling, in terms of "continuous trees" whose archetyp e is the so-called Brownian Continuum Random Tree (CRT for short). Since Aldous's pioneering work, the CRT has been identified as the limiting object of many different classes of discrete structures, in particular trees, see e.g. Haas and Miermont [16] and references therein, and planar maps, see e.g. Albenque and Marckert [2], Bettinelli [8], Caraceni [9], Curien, Haas and Kortchemski [10] and Janson and Stefansson [19].

Although the aforementioned papers identify the CRT as the universal limiting object in various set-
tings, much less is known about the scaling limit of random graphs from complex graph classes. In this
paper we study in a unified way the asymptotic distribution of distances in random graphs from so-called
subcritical classes, where, informally, a class is called subcritical if for a typical graph with $n$ vertices the
largest block (i.e. inclusion maximal 2-connected subgraph) has $O(\log n)$ vertices. Random graphs from
such classes have been the object of intense research in the last years, see e.g. [14, 7, 13, 24], especially
because of their close connection to the class of planar graphs. Prominent examples of classes that are
subcritical are outerplanar and series-parallel graphs. However, with the notable exception of [14], most
research on such random graphs has focused on additive parameters, like the number of vertices of a
given degree; the fine study of global properties, like the distribution of the distances, poses a significant
challenge.

In the present paper we study the random graph $C_n$ drawn uniformly from the set of connected graphs with $n$ vertices of a subcritical class $C$. Our first main result is Theorem 4.1, which shows that, up to an appropriate rescaling, the associated metric space converges in distribution to a multiple of the CRT. Postponing the introduction of the appropriate notation to later sections (see the outline), our main result asserts that there is a constant $s = s(C) > 0$ such that

$$
(V(C_n), s n^{-1/2} d_{C_n}) \xrightarrow{(d)} \mathcal{T}_e,
$$

where $\mathcal{T}_e$ is the CRT and convergence is with respect to the Gromov-Hausdorff metric. In particular, this establishes that the CRT is the universal scaling limit for random graphs from subcritical classes, and it proves (in a strong form) a conjecture by Drmota and Noy [14], who conjectured distributional convergence for the rescaled diameter $D(C_n)n^{-1/2}$. We also show exponential tail bounds, see Theorem 4.4. In particular, we show that there are constants $C, c > 0$ such that for all $n$ and $x \ge 0$

$$
\mathbb{P}(D(C_n) \ge x) \le C \exp(-cx^2/n)
$$

A similar result was shown for critical Galton-Watson random trees by Addario-Berry, Devroye and Jan-
son [1], and our proof of these bounds builds on the methods in that paper. From this we deduce that all
moments of the rescaled height and diameter converge as well. In particular, we obtain the universal and
remarkable asymptotic behaviour

$$
\mathbb{E}[D(C_n)] \sim \frac{2^{3/2}}{3s} \sqrt{\pi n} \sim \frac{4}{3} \mathbb{E}[H(C_n^*)].
$$

with $C_n^*$ denoting the graph $C_n$ together with a uniformly at random drawn root. This improves the previously best known bounds $c_1\sqrt{n} \le \mathbb{E}[D(C_n)] \le c_2\sqrt{n\log n}$ given in [14]. The higher moments can also be determined. We apply our main theorem to the specific class of outerplanar graphs and give analytic expression and numerical approximation of the scaling constant.
In addition to the previous results, we demonstrate that our proof strategy is powerful enough to enable us to study the far more general setting of first passage percolation: suppose that the edges of $C_n$ are equipped with independent random “lengths”, drawn from a distribution that has exponential moments, and let the distance of two vertices $u, v$ be the minimum sum of those lengths along a path that contains both $u$ and $v$. We show that again, up to an appropriate rescaling, the associated metric space converges to a multiple of the CRT.

The present paper is an extended abstract of [25] where further results, detailed proofs and several examples are given, in particular an extension to disconnected graphs and applications to more specific examples of minor-closed graph classes.

# 2 Combinatorial species, $\mathcal{R}$-enriched trees and subcritical graph classes

## 2.1 Combinatorial species and classes

We make use of the frameworks of combinatorial species and combinatorial classes. The reader is referred to the excellent sources Joyal [20], Bergeron, Labelle and Leroux [6] and Flajolet and Sedgewick [15] for an introduction to the framework of combinatorial classes and generating functions.

## 2.2 Block-stable graph classes

Any graph may be decomposed into its *connected components*, i.e. its maximal connected subgraphs. These connected components allow a *block-decomposition* which we recall in the following. Let $C$ be a connected graph. If removing a vertex $v$ (and deleting all adjacent edges) disconnects the graph, we say that $v$ is a *cutvertex* of $C$. The graph $C$ is *2-connected*, if it has size at least three and no cutvertices.

A *block* of an arbitrary graph $G$ is a maximal connected subgraph $B \subset G$ that does not have a cutvertex (of itself). It is well-known, see for example [12], that any block is either 2-connected or an edge or a single isolated point. Moreover, the intersection of two blocks is either empty or a cutvertex of a connected component of $G$. If $G$ is connected, then the bipartite graph whose vertices are the blocks and the cutvertices of $G$ and whose edges are pairs $\{v, B\}$ with $v \in B$ is a tree and called the *block-tree* of $G$.

Let $\mathcal{G}$ denote a subspecies of the species of graphs, $C \subset \mathcal{G}$ the subspecies of connected graphs in $\mathcal{G}$ and $B \subset C$ the subspecies of all graphs in $C$, that are 2-connected or consist of only two vertices joined by an edge. We say that $\mathcal{G}$ or $C$ is a *block-stable* class of graphs, if $B \neq 0$ and $G \in \mathcal{G}$ if and only if every block of $G$ belongs to $B$ or is a single isolated vertex. The block-tree construction allows for the following combinatorial specifications that can be found for example in Joyal [20], Bergeron, Labelle and Leroux [6] and Harary and Palmer [17]:

$$ \mathcal{G} \simeq \text{SET} \circ C \quad \text{and} \quad C^{\bullet} \simeq \mathcal{X} \cdot (\text{SET} \circ B' \circ C^{\bullet}). \qquad (1) $$

The first correspondence expresses the fact that we may form any graph on a given vertex set $U$ by partitioning $U$ and constructing a connected graph on each partition class. The specification for rooted connected graphs, illustrated in Figure 1, is based on the construction of the block-tree. By the rules for computing the generating series of species we obtain the equations

$$ G(z) = \exp(C(z)) \quad \text{and} \quad C^{\bullet}(z) = z \exp(B'(C^{\bullet}(z))). \qquad (2) $$
<figure><img src="image_2.png" /><figcaption>Fig. 1: Decomposition of a rooted graph from $C^*$ into a $\mathcal{X} \cdot (\text{SET} \circ \mathcal{B}' \circ C^*)$ structure. Labels are omitted and the roots are marked with squares.</figcaption></figure>

## 2.3 $\mathcal{R}$-enriched trees

The class $\mathcal{A}$ of rooted trees$^{(i)}$ is known to satisfy the decomposition $\mathcal{A} \simeq \mathcal{X} \cdot \text{SET}(\mathcal{A})$. More generally, given a species $\mathcal{R}$ the class $\mathcal{A}_{\mathcal{R}}$ of $\mathcal{R}$-enriched trees is defined by the combinatorial specification

$$ \mathcal{A}_{\mathcal{R}} \simeq \mathcal{X} \cdot \mathcal{R}(\mathcal{A}_{\mathcal{R}}). $$

In other words, an $\mathcal{R}$-enriched tree is a rooted tree such that the offspring set of any vertex is endowed with an $\mathcal{R}$-structure. Natural examples are labeled ordered trees, which are SEQ-enriched trees, and plane trees, which are unlabeled ordered trees. Ordered and unordered tree families defined by restrictions on the allowed outdegree of internal vertices also fit in this framework. $\mathcal{R}$-enriched trees were introduced by Labelle [21] in order to provide a combinatorial proof of Lagrange Inversion. They have applications in various fields of mathematics, see for example [23, 11, 22].

The combinatorial specification (1) together with Joyal’s Implicit Species Theorem allows us to identify a block-stable graph class $C^*$ with the class $\mathcal{R}$-enriched trees where $\mathcal{R} = \text{SET}(\mathcal{B}')$, that is, rooted trees from $\mathcal{A}$ where the offspring set of each vertex is partitioned into nonempty sets and each of these sets carries a $\mathcal{B}'$-structure. Compare with Figure 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Correspondence of the classes $C^*$ and $\text{SET}(\mathcal{B}')$-enriched trees.</figcaption></figure>

**Corollary 2.1** Let $\mathcal{C}$ be a block-stable class of connected graphs, $\mathcal{B} \neq \emptyset$ its subclass of all graphs that are 2-connected or a single edge. Then there is a unique isomorphism between $C^*$ and the class $\mathcal{A}_{\text{SET} \circ \mathcal{B}'}$ of pairs $(T, \alpha)$ with $T \in \mathcal{A}$ and $\alpha$ a function that assigns to each $v \in V(T)$ a (possibly empty) set $\alpha(v) \in (\text{SET} \circ \mathcal{B}')[M_v]$ of derived blocks whose vertex sets partition the offspring set $M_v$ of $v$.

<footnote>(i) Arborescence is the French word for rooted tree, hence the notation $\mathcal{A}$.</footnote>
## 2.4 Subcritical graph classes

Let $\mathcal{C}$ be a block-stable class of connected graphs and $B \neq 0$ its subclass of all graphs that are 2-connected or a single edge with its ends. We assume in the following that $\mathcal{B}$ and $\mathcal{C}$ are analytic and denote by $\rho$ and $R$ the radii of convergence of the corresponding exponential generating series $C(z)$ and $B(z)$. Note that any graph of the class $\mathcal{B}$ has at least 2 vertices, hence the generating series $B'(z)$ has the form $\sum_{k \ge 1} b_k z^k$ with $b_k \neq 0$ for at least one integer $k \ge 1$. Since $C^\bullet(z) = z \exp(B'(C^\bullet(z)))$ the nonnegativity of all coefficients implies that $\rho, y = C^\bullet(\rho)$ and $\lambda = B'(y)$ are finite quantities. The following proposition provides a coupling of a Boltzmann-distributed random graph drawn from the class $\mathcal{C}$ with a Galton-Watson tree, that is based on the decomposition developed in the previous section. This sampler is in some sense one of the main contributions of the present paper, as it allows us to build on results for branching processes in order to study random graphs from the classes under consideration.

**Proposition 2.2** Let $\mathcal{C}^\bullet$ denote a random rooted graph drawn from the set $\cup_n C_n^\bullet$ according to a Boltzmann distribution with parameter $\rho$, i.e. the distribution of $\mathcal{C}$ is given by $\mathbb{P}(\mathcal{C} = \mathcal{C}^\bullet) = \rho^n/(yn!)$ for any rooted graph $\mathcal{C}^\bullet \in C_n^\bullet$. Let $(T, \alpha)$ denote the SET $\circ B^�$-enriched tree corresponding to $\mathcal{C}$. Then the rooted labeled unordered tree $T$ is distributed like the outcome of the following process:

1. Draw a Galton-Watson tree with offspring distribution $\xi$ given by the probability generating function $\varphi(z) = \exp(B'(yz) - \lambda)$.

2. Distribute labels uniformly at random.

3. Discard the ordering on the offspring sets.

Let $\xi$ denote the offspring distribution given in Proposition 2.2. Its average value is given by $\mathbb{E}[\xi] = \varphi'(1) = yB''(y) = B'^{\bullet}(y)$.

The following definition of subcritical classes is slightly more general as the traditional one given in [13], as we do not require aperiodicity of the series $B'(z)$. This requirement is usually made, as it simplifies the application of analytic methods such as singularity analysis of generating functions and most interesting classes such as series-parallel graphs and outerplanar graphs satisfy this condition anyway. However, with the branching-processes methods employed in the present paper there is no need to make this extra requirement, as it does not simplify the arguments used in the following.

**Definition 2.3** The block-stable class of connected graphs $\mathcal{C}$ is termed subcritical, if the series $B'(z)$ is analytic at the point $y$ and $yB''(y) = 1$.

In our framework, this is equivalent to the offspring distribution $\xi$ having average value 1 and exponential moments, i.e. if the probability generating function $\mathbb{E}[z^\xi]$ has radius of convergence greater than 1.

Prominent examples of subcritical graph classes are trees, outerplanar graphs and series-parallel graphs; the class of planar graphs is block-stable but not subcritical [13, 7]. Thus, if the offspring distribution $\xi$ has average value 1, then its variance is given by $\sigma^2 = 1 + B'''(y)y^2$.

The span of the random variable $\xi$ is the smallest positive integer $d$ such the support $\{k \mid \mathbb{P}(\xi = k) > 0\}$ is a subset of $x + d\mathbb{Z}$ for some $x \in \mathbb{Z}$. Proposition 2.2 allows us to apply standard results for conditioned Galton-Watson trees to obtain the following corollary, which was shown in [13] under stronger assumptions.
**Corollary 2.4** Let $\mathcal{C}$ be an analytic block-stable class, and let $\xi$ be the distribution from Proposition 2.2. Suppose that $B'^{\bullet}(y) = 1$ and $B'''(y) < \infty$, i.e. $\xi$ has finite variance. Then, as $n \equiv 1 \mod \operatorname{span}(\xi)$ tends to infinity,

$$|C_n| \sim \frac{y \operatorname{span}(\xi)}{\sqrt{2\pi E[|\Gamma B'^{\bullet}(y)|]}} n^{-5/2} \rho^{-n} n!.$$

### 3 A size-biased random $\mathcal{R}$-enriched tree

Let $\mathcal{C}$ be an analytic block-stable class of connected graphs and $\mathcal{B} \neq 0$ its subclass of graphs that are 2-connected or a single edge. As before we let $\rho$ denote the radius of convergence of the exponential generating series $C(z)$ and set $y = C^{\bullet}(\rho)$. Recall that by Corollary 2.1 the class $\mathcal{C}^{\bullet}$ may be identified with the class of $\mathcal{R}$-enriched trees with $\mathcal{R} := \text{SET} \circ \mathcal{B}'$, i.e. pairs $(T, \alpha)$ with $T \in \mathcal{A}$ a rooted labeled unordered tree and $\alpha$ a function that assigns to each $v \in V(T)$ a (possibly empty) set $\alpha(v)$ of derived blocks whose vertex sets partition the offspring set of the vertex $v$.

An important ingredient in our forthcoming arguments will be an accurate description of the distribution of the blocks on sufficiently long paths in random graphs from $\mathcal{C}$. In order to study this distribution we will make use of a special case of a size-biased random $\mathcal{R}$-enriched tree. This construction is based on the size-biased Galton Watson tree introduced in [1] and has several other applications and implications.

Recall that $\mathcal{A}_{\mathcal{R}}$ has the decomposition $\mathcal{A}_{\mathcal{R}} \simeq \mathcal{X} \cdot \mathcal{R}(\mathcal{A}_{\mathcal{R}})$. By the rules governing operations on species we obtain algebraically

$$ \begin{aligned} \mathcal{A}_{\mathcal{R}}^{\bullet} &\simeq \mathcal{A}_{\mathcal{R}} + \mathcal{X} \cdot \mathcal{R}'(\mathcal{A}_{\mathcal{R}}) \cdot \mathcal{A}_{\mathcal{R}}^{\bullet} \\ &\simeq \mathcal{A}_{\mathcal{R}} + \mathcal{X} \cdot \mathcal{R}'(\mathcal{A}_{\mathcal{R}}) \cdot \mathcal{A}_{\mathcal{R}} + (\mathcal{X} \cdot \mathcal{R}'(\mathcal{A}_{\mathcal{R}}))^2 \cdot \mathcal{A}_{\mathcal{R}}^{\bullet} \\ &\dots \\ &\simeq \sum_{\ell \ge 0} (\mathcal{X} \cdot \mathcal{R}'(\mathcal{A}_{\mathcal{R}}))^{\ell} \mathcal{A}_{\mathcal{R}}. \end{aligned} $$

The above calculation corresponds to taking a direct limit in the category of species, either directly or alternatively by application of Joyal's Implicit Species Theorem. Here $\mathcal{A}_{\mathcal{R}}^{(\ell)} := (\mathcal{X} \cdot \mathcal{R}'(\mathcal{A}_{\mathcal{R}}))^{\ell} \mathcal{A}_{\mathcal{R}}$ corresponds to the subspecies of all enriched trees $(T, \alpha)$ with a distinguished vertex $r$ such that $r$ has height $\ell$ in $T$. It follows from the definition of the Boltzmann distribution that for any pointed enriched tree $(A, r) \in \mathcal{A}_{\mathcal{R}}^{(\ell)}$ we have that

$$ \mathbb{P} \left( \Gamma A_{\mathcal{R}}^{(\ell)}(\rho) = (A, r) \right) = (\rho R'(y))^{-\ell} \mathbb{P} \left( \Gamma A_{\mathcal{R}}(\rho) = A \right). \quad (3) $$

Translating the combinatorial specification for $\mathcal{A}_{\mathcal{R}}^{(\ell)}$ into a Boltzmann sampler $\Gamma A_{\mathcal{R}}^{(\ell)}(\rho)$ yields the following procedure which we call the size-biased $\mathcal{R}$-enriched tree (see also Figure 3). Any vertex is either normal or mutant, and we start with a single mutant root. Normal vertices have an independent copy of $\Gamma R(y)$ as offspring. Mutant nodes have an independent copy of $\Gamma R^{\bullet}(y)$ as offspring and the root in the $\mathcal{R}^{\bullet}$ object is declared mutant, unless it is the $\ell$th copy of $\Gamma R^{\bullet}(y)$. By the theory of recursive Boltzmann samplers obtained from combinatorial specifications this procedure terminates almost surely. The sampler $\Gamma A_{\mathcal{R}}^{(\ell)}(\rho)$ is obtained by additionally distributing labels uniformly at random.
<figure><img src="image_4.png" /><figcaption>Fig. 3: Illustration of the sampler for the size-biased $\mathcal{R}$-enriched tree.</figcaption></figure>

We call the path connecting the inner root with the outer root in an $\mathcal{A}_{\mathcal{R}}^{\bullet}$-object the spine. Note that the $\mathcal{R}$-objects along the spine of the random enriched tree $\Gamma A_{\mathcal{R}}^{(\ell)}(\rho)$ are drawn according to $\ell$ independent copies of $\Gamma R^{\bullet}(y)$.

In our setting we have that $\mathcal{R} = \text{SET} \circ \mathcal{B}'$, where $\mathcal{B} \neq 0$ denotes the subclass of blocks of the block-stable class $\mathcal{C}$. It follows that

$$ \mathcal{R}^{\bullet} \approx (\text{SET} \circ \mathcal{B}') \cdot \mathcal{B}'^{\bullet} $$

and the sampler $\Gamma R^{\bullet}(y)$ is given by independent calls of $\Gamma(\text{SET} \circ \mathcal{B}')(y)$ and $\Gamma \mathcal{B}'^{\bullet}(y)$. Hence the blocks along the spine are drawn according to $\ell$ independent copies of $\Gamma \mathcal{B}'^{\bullet}(y)$.

Equation (3) allows us to relate properties of $\Gamma A_{\mathcal{R}}^{(\ell)}(\rho)$ to properties of a uniformly random chosen enriched tree of a given size. We are going to apply the following general lemma in Section 4 in order to show that the blocks along sufficiently long paths in random graphs behave asymptotically like the spine of $\Gamma A_{\mathcal{R}}^{(\ell)}(\rho)$ for a corresponding $\ell$.

**Lemma 3.1** Let $\mathcal{E}$ be a property of pointed $\mathcal{R}$-enriched trees (i.e. a subset of $\mathcal{A}_{\mathcal{R}}^{\bullet}$) and let $n \in \mathbb{N}$ be such that $\mathcal{A}_{\mathcal{R}}[n]$ is nonempty. Consider the function

$$ f: \mathcal{A}_{\mathcal{R}}[n] \to \mathbb{R}, \quad A \mapsto \sum_{v \in [n]} 1_{(A,v) \in \mathcal{E}} $$

counting the number of “admissible” outer roots with respect to $\mathcal{E}$. Let $A_n \in \mathcal{A}_{\mathcal{R}}[n]$ be drawn uniformly at random. Then

$$ \mathbb{E}[f(A_n)] = \mathbb{P}(|\Gamma A_R(\rho)| = n)^{-1} \sum_{\ell=0}^{n-1} (\rho R'(y))^{\ell} \mathbb{P}(\Gamma A_R^{(\ell)}(\rho) \text{ has size } n \text{ and satisfies } \mathcal{E}). $$

**Proof:** First, observe that

$$ \sum_{v=1}^{n} \mathbb{P}((A_n, v) \in \mathcal{E}) = \sum_{\ell=0}^{n-1} \sum_{(A,r) \in \mathcal{E} \cap \mathcal{A}_{\mathcal{R}}^{(\ell)}[n]} \mathbb{P}(A_n = A). $$

By (3) we have for all $(A, r) \in \mathcal{E} \cap \mathcal{A}_{\mathcal{R}}^{(\ell)}[n]$ that

$$ \mathbb{P}(\Gamma A_R(\rho) = A | |\Gamma A_R(\rho)| = n) = (\rho R'(y))^{\ell} \mathbb{P}(\Gamma A_R^{(\ell)}(\rho) = (A, r)) \mathbb{P}(|\Gamma A_R(\rho)| = n)^{-1}. $$

This proves the claim.

□
# 4 Convergence Towards the CRT

Let $\mathcal{C}$ be an analytic block-stable class of connected graphs and $\mathcal{B} \neq 0$ its subclass of all graphs that are 2-connected or a single edge. We let $\rho > 0$ denote the radius of convergence of the exponential generating series $C(z)$ and set $y = C^{\bullet}(\rho)$. As before we identify $\mathcal{C}^{\bullet}$ with the class $\mathcal{A}_{\mathcal{R}}$ of $\mathcal{R}$-enriched trees with $\mathcal{R} = \text{SET} \circ \mathcal{B}'$. By Proposition 2.2 we know that if we draw an $\mathcal{R}$-enriched tree $(T, \alpha)$ according to the Boltzmann distribution with parameter $\rho$, then $T$ is distributed like a $\xi$-Galton-Watson tree with $\xi := |\Gamma(\text{SET} \circ \mathcal{B}')(y)|$, relabeling uniformly at random and discarding the ordering on the offspring sets.

Throughout this section let $n \equiv 1 \mod \text{span}(\xi)$ denote a large enough integer such that the probability of a $\xi$-GWT having size $n$ is positive. Let $C_n \in C_n$ be drawn uniformly at random and generate $C_n^{\bullet} \in C_n^{\bullet}$ by uniformly choosing a root from $[n]$. We let $(T_n, \alpha_n)$ be the corresponding enriched tree.

For any pointed derived block $B \in \mathcal{B}'^{\bullet}$ we let $\text{sp}(B) := d_B(*, \text{root})$ denote the length of a shortest path connecting the $*$-vertex with the root. In this section we prove our main result:

**Theorem 4.1** Let $\mathcal{C}$ be a subcritical class of connected graphs. Then

$$ \frac{\sigma}{2\kappa\sqrt{n}} C_n^{\bullet} \xrightarrow{(d)} \mathcal{T}_e \quad \text{and} \quad \frac{\sigma}{2\kappa\sqrt{n}} C_n \xrightarrow{(d)} \mathcal{T}_e $$

with respect to the (pointed) Gromov-Hausdorff metric. The constants are given by $\sigma^2 = \mathbb{E}[|B|]$ and $\kappa = \mathbb{E}[\text{sp}(B)]$ with $B \in \mathcal{B}'^{\bullet}$ a random block drawn according to the Boltzmann distribution with parameter $y = C^{\bullet}(\rho)$, and in particular $\sigma^2 = 1 + B'''(y)y^2$.

As an example, we apply our main theorem to the class of connected outerplanar graphs and obtain the following numeric approximations and analytic expressions for the relevant constants:

**Proposition 4.2** For the class of outerplanar graphs the constant $y$ is the unique positive solution to $zB''(z) = 1$, where $B'(z) = (z + D(z))/2$ with $D(z) = \frac{1}{4}(1 + z - \sqrt{z^2 - 6z + 1})$. Moreover,

$$ \kappa = \frac{y}{2} + \left(1 - \frac{y}{2}\right) \frac{8w^4 - 16w^3 + 4w - 1}{(4w^3 - 6w^2 - 2w + 1)(2w - 1)} \approx 5.0841 \text{ with } w = D(y) $$

and $\sigma^2 = 1 + B'''(y)y^2 \approx 95.3658$.

As a consequence of Theorem 4.1 we obtain the limit distributions for the height and diameter of $C_n^{\bullet}$.

**Corollary 4.3** Let $\mathcal{C}$ be a subcritical class of connected graphs. Then the rescaled height $\frac{\sigma}{2\kappa\sqrt{n}}H(C_n^{\bullet})$ and diameter $\frac{\sigma}{2\kappa\sqrt{n}}D(C_n)$ converge in distribution to $H(\mathcal{T}_e)$ and $D(\mathcal{T}_e)$, i.e. for all $x > 0$, as $n$ tends to infinity

$$ \mathbb{P} \left( H(C_n^{\bullet}) > \frac{2\kappa\sqrt{n}}{\sigma} x \right) \rightarrow 2 \sum_{k=1}^{\infty} (4k^2 x^2 - 1) \exp(-2k^2 x^2), $$

$$ \mathbb{P} \left( D(C_n) > \frac{2\kappa\sqrt{n}}{\sigma} x \right) \rightarrow \sum_{k=1}^{\infty} (k^2 - 1) \left( \frac{2}{3} k^4 x^4 - 4k^2 x^2 + 2 \right) \exp(-k^2 x^2 / 2). $$

Moreover, all moments converge as well. In particular

$$ \mathbb{E}[D(C_n)] \sim \frac{2^{5/2}\kappa}{3\sigma\sqrt{\pi n}} \sim \frac{4}{3}\mathbb{E}[H(C_n^{\bullet})]. $$
Of course, in order to obtain converge of higher moments of the rescaled diameter we need to check uniform integrability, which is why we provide the following tail-bounds.

**Theorem 4.4** Let $\mathcal{C}$ be a block-stable class of connected graphs. Suppose that $\mathcal{C}$ satisfies $B'^*(y) = 1$ and the offspring distribution $\xi$ has finite variance, i.e. $B'''(y) < 1$. Then there are $C, c > 0$ such that for all $n, x \ge 0$

$$ \mathbb{P}(D(C_n) \ge x) \le C \exp(-cx^2/n) \quad \text{and} \quad \mathbb{P}(H(C_n^\bullet) \ge x) \le C \exp(-cx^2/n). $$

Proofs of Theorem 4.4 and Proposition 4.2 are not part of this extended abstract but given in [25]. We do outline in the following a proof of our main result Theorem 4.1. The idea is to show that the pointed Gromov-Hausdorff distance of $C_n^\bullet$ and $\kappa T_n$ is small with high probability and use the convergence of $T_n$ towards a multiple of the CRT $\mathcal{T}_e$.

**Definition 4.5** Let $C \in \mathcal{C}$. For any $x, y \in V(C)$ set $\bar{d}_C(x, y) := d_T(x, y)$ with $(T, \alpha)$ the enriched tree corresponding to $(C, x)$, i.e. $C$ rooted at the vertex $x$.

Less formally speaking, $\bar{d}_C(x, y)$ denotes the minimum number of blocks required to cover the edges of a shortest path linking $x$ and $y$. It takes a moment to see that if $(T, \alpha)$ corresponds to the rooted graph $(C, z)$, then $\bar{d}_C(x, y) \le d_T(x, y) \le \bar{d}_C(x, y) + 1$ for all $x, y \in V(C)$. In particular, $\bar{d}_C$ is a metric: the triangle inequality holds since $d_T$ is a metric and

$$ \bar{d}_C(x, y) \le d_T(x, y) \le d_T(x, z) + d_T(y, z) = \bar{d}_C(x, z) + \bar{d}_C(y, z). $$

In the following lemma we apply the results on pointed enriched trees of Section 3.

**Lemma 4.6** Let $\mathcal{C}$ be a subcritical class of connected graphs and set $\kappa = \mathbb{E}[\text{sp}(\Gamma B'^*(y))]$. Then for all $s > 1$ and $0 < \epsilon < 1/2$ with $2\epsilon s > 1$ we have with high probability that all $x, y \in V(C_n)$ with $\bar{d}_{C_n}(x, y) \ge \log^s(n)$ satisfy $|d_{C_n}(x, y) - \kappa \bar{d}_{C_n}(x, y)| \le \bar{d}_{C_n}(x, y)^{1/2+\epsilon}$.

**Proof:** We denote $L_n = \log^s(n)$ and $t_\ell = \ell^{1/2+\epsilon}$. Let $\mathcal{E} \subset A_R^\bullet \simeq C^{\bullet\bullet}$ with $\mathcal{R} = \text{SET} \circ \mathcal{B}'$ denote the set of all bipointed graphs or pointed enriched trees $((C, x), y) \simeq ((T, \alpha), y)$, where we call $x$ the inner root and $y$ the outer root, such that

$$ d_T(x, y) \ge L_{|T|} \quad \text{and} \quad |d_C(x, y) - \kappa d_T(x, y)| > t_{d_T(x, y)}. $$

We will bound the probability that there exist vertices $x$ and $y$ with $((C_n, x), y) \in \mathcal{E}$. First observe that

$$ \sum_{x,y \in [n]} \mathbb{P}(((C_n, x), y) \in \mathcal{E}) = \sum_{((C,x),y) \in \mathcal{E}} \mathbb{P}(C_n = C) = n \sum_{y=1}^{n} \mathbb{P}((C_n^\bullet, y) \in \mathcal{E}). $$

By assumption we may apply Corollary 2.4 to obtain $\mathbb{P}(|\Gamma C^\bullet(\rho)| = n) = \Theta(n^{-3/2})$. Moreover, $B'^*(y) = 1$ since $\mathcal{C}$ is subcritical and thus

$$ \rho R'(y) = \rho B''(y) e^{B'(y)} = y B''(y) = 1. $$

Hence, by applying Lemma 3.1 we obtain that

$$ \mathbb{P}(((C_n, x), y) \in \mathcal{E} \text{ for some } x, y) \le O(n^{5/2}) \sum_{\ell=L_n}^{n-1} \mathbb{P}(\Gamma A_R^{(\ell)}(\rho) \text{ has size } n \text{ and satisfies } \mathcal{E}). $$
The height of the outer root in the bipointed graph corresponding to $\Gamma A_R^{(\ell)}(\rho)$ is distributed like the sum of $\ell$ independent random variables, each distributed like the distance of the $*$-vertex and the root in the corresponding derived block of $\Gamma(\text{SET} \circ \mathcal{B}')^*(y)$. Since $(\text{SET} \circ \mathcal{B}')^* \simeq (\text{SET} \circ \mathcal{B}') \cdot \mathcal{B}'^*$, these variables are actually $\text{sp}(\Gamma \mathcal{B}'^*(y))$-distributed. Hence

$$ \mathbb{P}(\Gamma A_R^{(\ell)}(\rho) \in \mathcal{E}, |\Gamma A_R^{(\ell)}(\rho)| = n) \le \mathbb{P}(|\eta_1 + \dots + \eta_\ell - \ell \mathbb{E}[\eta_1]| > t_\ell) $$

with $(\eta_i)_i$ i.i.d. copies of $\eta := \text{sp}(\Gamma \mathcal{B}'^*(y))$. Clearly we have that $\eta \le |\Gamma \mathcal{B}'^*(y)|$. Since $\mathcal{C}$ is subcritical it follows that there is a constant $\delta > 0$ such that $\mathbb{E}[e^{\eta\theta}] < \infty$ for all $\theta$ with $|\theta| \le \delta$. Hence we may apply a moderate deviation inequality for one-dimensional random walk to obtain for some constant $c > 0$

$$ \mathbb{P}((C_n, x), y) \in \mathcal{E} \text{ for some } x, y) \le O(n^{7/2}) \exp(-c(\log n)^{2s\epsilon}) = o(1). $$

□

It remains to clarify what happens if $\bar{d}_{C_n}$ is small. We prove the following statement for random graphs from block-stable classes that are not necessarily subcritical.

**Proposition 4.7** Let $\mathcal{C}$ be a block-stable class of connected graphs. Suppose that $\mathcal{B}'^*(y) = 1$ and the offspring distribution $\xi$ has finite second moment, i.e. $\mathcal{B}'''(y) < \infty$. Let $\text{lb}(C_n)$ denote the size of the largest block in $C_n$,

1. For any $x, y \in C_n$ we have $d_{C_n}(x, y) \le \bar{d}_{C_n}(x, y)\text{lb}(C_n)$.

2. If the offspring distribution $\xi$ is bounded, then so is $\text{lb}(C_n)$. Otherwise, for any sequence $K_n$ we have $\mathbb{P}(\text{lb}(C_n) \ge K_n) = O(n)\mathbb{P}(\xi \ge K_n)$.

**Proof:** We have that $d_{C_n} \le \bar{d}_{C_n}(\text{lb}(C_n) - 1)$ and $\text{lb}(C_n) = \text{lb}(C_n^*) \le \Delta(\Gamma_n) + 1$ with $\Delta(\Gamma_n)$ denoting the largest outdegree. Recall that $\Delta(\Gamma_n)$ is distributed like the maximum degree of a $\xi$-Galton-Watson tree conditioned to have $n$ vertices. By assumption, the offspring distribution $\xi$ has expected value $\mathbb{E}[\xi] = \mathcal{B}'^*(y) = 1$ and finite variance.

If $\xi$ is bounded then so is the largest outdegree of $\Gamma_n$. Otherwise, as argued in the proof of [18, Eq. (19.20)], for any sequence $K_n$

$$ \mathbb{P}(\Delta(\Gamma_n) \ge K_n) \le (1 + o(1))n\mathbb{P}(\xi \ge K_n). \quad (4) $$

Applying (4) yields $\mathbb{P}(\Delta(\Gamma_n) \ge K_n) \le (1 + o(1))n\mathbb{P}(\xi \ge K_n)$ for any sequence $K_n$. □

Note that if $\mathcal{C}$ is subcritical then this implies that $\text{lb}(C_n) = O(\log n)$ with high probability: the definition of the Boltzmann model and the fact that $y$ is smaller than the radius of convergence of $\mathcal{B}(z)$ guarantee that there is a constant $\beta < 1$ such that

$$ \mathbb{P}(\xi = k) = \mathbb{P}(|\Gamma(\text{SET} \circ \mathcal{B}')(y)| = k) = O(\beta^k). $$

Combined with the bounds of Lemma 4.6 this yields the following concentration result.

**Corollary 4.8** Let $\mathcal{C}$ be a subcritical class of connected graphs. Then for all $s > 1$ and $0 < \epsilon < 1/2$ with $2\epsilon s > 1$ we have with high probability that for all vertices $x, y \in V(C_n)$

$$ |d_{C_n}(x, y) - \kappa \bar{d}_{C_n}(x, y)| \le \bar{d}_{C_n}(x, y)^{1/2+\epsilon} + O(\log^{s+1}(n)). $$
We may now prove the main theorem.

**Proof of Theorem 4.1:** Recall that $\bar{d}_{C_n} \le d_{T_n} \le \bar{d}_{C_n} + 1$. By Corollary 4.8, it follows that with high probability we have the following bound for the Gromov-Hausdorff distance

$$d_{GH}(C_n^\bullet/(\kappa\sqrt{n}), T_n/\sqrt{n}) \le D(T_n)^{3/4}/\sqrt{n} + o(1).$$

Using the tail bounds [1] for the diameter $D(T_n)$ we obtain that $d_{GH}(C_n^\bullet/(\kappa\sqrt{n}), T_n/\sqrt{n})$ converges in probability to zero. Recall that the variance of the offspring distribution $\xi$ is given by $\sigma^2 = \mathbb{E}[|\Gamma B'^\bullet(y)|]$. By [5] we have that $\frac{\sigma}{2\sqrt{n}}T_n \xrightarrow{\binom{d}{2\sqrt{n}}} \mathcal{T}_e$ and thus $\frac{\sigma}{2\kappa\sqrt{n}}C_n^\bullet \xrightarrow{\binom{d}{2\kappa\sqrt{n}}} \mathcal{T}_e$. $\square$

# 5 First Passage Percolation

Let $\omega > 0$ be a given random variable such that there is a $\delta > 0$ with $\mathbb{E}[e^{\theta\omega}] < \infty$ for all $\theta$ with $|\theta| \le \delta$. For any graph $G$ we may consider the random graph $\hat{G}$ obtained by assigning to each edge $e \in E(G)$ a weight $\omega_e$ that is an independent copy of $\omega$. The $d_{\hat{G}}$-distance of two vertices $a$ and $b$ is then given by

$$d_{\hat{G}}(a, b) = \inf \left\{ \sum_{e \in E(P)} \omega_e \mid P \text{ a path connecting } a \text{ and } b \text{ in } G \right\}.$$

Let $\hat{\kappa} := \mathbb{E}[\text{sp}(\hat{B})]$ with $B$ drawn according to the Boltzmann sampler $\Gamma B'^\bullet(y)$ and $\text{sp}(\hat{B})$ denoting the $d_{\hat{B}}$-distance from the $*$-vertex to the root vertex. Our main result may be extended as follows.

**Theorem 5.1** Let $C$ be a subcritical class of connected graphs. We have that

$$\frac{\sigma}{2\hat{\kappa}\sqrt{n}} \hat{C}_n \xrightarrow{\binom{d}{2\hat{\kappa}\sqrt{n}}} \mathcal{T}_e \quad \text{and} \quad \frac{\sigma}{2\hat{\kappa}\sqrt{n}} \hat{C}_n \xrightarrow{\binom{d}{2\hat{\kappa}\sqrt{n}}} \mathcal{T}_e$$

with respect to the (pointed) Gromov-Hausdorff metric.

# References

[1] L. Addario-Berry, L. Devroye, and S. Janson. Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees. *Ann. Probab.*, 41(2):1072–1087, 2013.

[2] M. Albenque and J.-F. Marckert. Some families of increasing planar maps. *Electron. J. Probab.*, 13:no. 56, 1624–1671, 2008.

[3] D. Aldous. The continuum random tree. I. *Ann. Probab.*, 19(1):1–28, 1991.

[4] D. Aldous. The continuum random tree. II. An overview. In *Stochastic analysis (Durham, 1990)*, volume 167 of *London Math. Soc. Lecture Note Ser.*, pages 23–70. Cambridge Univ. Press, Cambridge, 1991.

[5] D. Aldous. The continuum random tree. III. *Ann. Probab.*, 21(1):248–289, 1993.

[6] F. Bergeron, G. Labelle, and P. Leroux. *Combinatorial species and tree-like structures*, volume 67 of *Encyclopaedia of Math. and its Applications*. Cambridge University Press, Cambridge, 1998. Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota.

[7] N. Bernasconi, K. Panagiotou, and A. Steger. The degree sequence of random graphs from subcritical classes. *Combin. Probab. Comput.*, 18(5):647–681, 2009.
[8] J. Bettinelli. Scaling limit of random planar quadrangulations with a boundary. *To appear in Annales de l'Institut Henri Poincaré.*

[9] A. Caraceni. The scaling limit of random outerplanar maps. *Submitted*, 2014.

[10] N. Curien, B. Haas, and I. Kortchemski. The CRT is the scaling limit of random dissections. *To appear in Random Struct. Alg.*

[11] H. Décoste, G. Labelle, and P. Leroux. Une approche combinatoire pour l'itération de Newton-Raphson. *Adv. in Appl. Math.*, 3(4):407–416, 1982.

[12] R. Diestel. *Graph theory*, volume 173 of *Graduate Texts in Math*. Springer, 2010.

[13] M. Drmota, É. Fusy, M. Kang, V. Kraus, and J. Rué. Asymptotic study of subcritical graph classes. *SIAM J. Discrete Math.*, 25(4):1615–1651, 2011.

[14] M. Drmota and M. Noy. Extremal parameters in sub-critical graph classes. In *ANALCO13—Meeting on Analytic Algorithmics and Combinatorics*, pages 1–7. SIAM, Philadelphia, PA, 2013.

[15] P. Flajolet and R. Sedgewick. *Analytic combinatorics*. Cambridge University Press, Cambridge, 2009.

[16] B. Haas and G. Miermont. Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. *Ann. Probab.*, 40(6):2589–2666, 2012.

[17] F. Harary and E. M. Palmer. *Graphical enumeration*. Academic Press, New York-London, 1973.

[18] S. Janson. Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. *Probab. Surv.*, 9:103–252, 2012.

[19] S. Janson and S. Ö. Stefánsson. Scaling limits of random planar maps with a unique large face. *To appear in Ann. Probab.*

[20] A. Joyal. Une théorie combinatoire des séries formelles. *Adv. in Math.*, 42(1):1–82, 1981.

[21] G. Labelle. Une nouvelle démonstration combinatoire des formules d'inversion de Lagrange. *Adv. in Math.*, 42(3):217–247, 1981.

[22] G. Labelle. On extensions of the Newton-Raphson iterative scheme to arbitrary orders. In *22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)*, Discrete Math. Theor. Comput. Sci. Proc., AN, pages 845–856. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2010.

[23] M. A. Méndez and J. C. Liendo. An antipode formula for the natural Hopf algebra of a set operad. *Adv. in Appl. Math.*, 53:112–140, 2014.

[24] K. Panagiotou and A. Steger. Maximal biconnected subgraphs of random planar graphs. *ACM Trans. Algorithms*, 6(2):Art. 31, 21, 2010.

[25] K. Panagiotou, B. Stufler, and K. Weller. Scaling Limits of Random Graphs from Subcritical Classes. *ArXiv e-prints*, Nov. 2014.