Benedikt Stufler

RANDOM ENRICHED TREES WITH APPLICATIONS TO RANDOM GRAPHS

We establish limit theorems that describe the asymptotic local and global geometric behaviour of random enriched trees considered up to symmetry. We apply these general results to random unlabelled weighted rooted graphs and uniform random unlabelled k-trees that are rooted at a k-clique of distinguishable vertices. For both models we establish a Gromov-Hausdorff scaling limit, a Benjamini-Schramm limit, and a local weak limit that describes the asymptotic shape near the fixed root.

Introduction

The study of large random discrete structures lies at the intersection of probability theory and combinatorics. A combinatorial approach often involves using the framework of combinatorial classes to express the quantities under consideration in terms of coefficients of power series, and applying analytic tools such as singularity analysis or saddle-point methods to obtain very precise limits and concentration results [START_REF] Drmota | Random trees[END_REF][START_REF] Flajolet | Analytic combinatorics[END_REF][START_REF] Banderier | Random maps, coalescing saddles, singularity analysis, and Airy phenomena[END_REF][START_REF] Chapuy | On the diameter of random planar graphs[END_REF][START_REF] Giménez | Graph classes with given 3-connected components: asymptotic enumeration and random graphs[END_REF][START_REF] Collet | Vertex Degrees in Planar Maps[END_REF]. From a probabilistic viewpoint, the focus is on establishing graph limits describing the asymptotic shape, either locally in so called local weak limits [START_REF] Angel | Uniform infinite planar triangulations[END_REF][START_REF] Stephenson | Local convergence of large critical multi-type Galton-Watson trees and applications to random maps[END_REF][START_REF] Curien | A view from infinity of the uniform infinite planar quadrangulation[END_REF][START_REF] Chassaing | Local limit of labeled trees and expected volume growth in a random quadrangulation[END_REF][START_REF] Benjamini | Recurrence of distributional limits of finite planar graphs[END_REF][START_REF] Ménard | Percolation on uniform infinite planar maps[END_REF][START_REF] Björnberg | Recurrence of bipartite planar maps[END_REF], or globally in Gromov-Hausdorff scaling limits [START_REF] Janson | Scaling limits of random planar maps with a unique large face[END_REF][START_REF] Haas | Scaling limits of k-ary growing trees[END_REF][START_REF] Addario-Berry | Joint convergence of random quadrangulations and their cores[END_REF][START_REF] Gall | The topological structure of scaling limits of large planar maps[END_REF][START_REF] Gall | Scaling limits of random planar maps with large faces[END_REF][START_REF] Gall | Uniqueness and universality of the Brownian map[END_REF][START_REF] Miermont | The Brownian map is the scaling limit of uniform random plane quadrangulations[END_REF], and more recently, also on an intermediate scale in local Gromov-Hausdorff scaling limits [START_REF] Baur | Classification of scaling limits of uniform quadrangulations with a boundary[END_REF][START_REF] Wen | The Brownian plane with minimal neck baby universe[END_REF].

When studying random graphs one usually distinguishes their vertices implicitly, or explicitly using labels. As the labelling does not influence the geometric shape of the graph, it is natural to also consider graphs up to symmetry, that is, unlabelled graphs. However, this poses a particular challenge. Due to the complexity of the involved symmetries, probabilistic approaches in the past focus on models of random unlabelled trees [START_REF] Panagiotou | Scaling limits of random Pólya trees[END_REF][START_REF] Stufler | The continuum random tree is the scaling limit of unlabelled unrooted trees[END_REF][START_REF] Marckert | The CRT is the scaling limit of unordered binary trees[END_REF][START_REF] Haas | Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees[END_REF][START_REF] Wang | Scaling limits for a family of unrooted trees[END_REF], and models of random unlabelled graphs were predominantly studied using analytic methods. In this context we mention the work by Bodirsky, Fusy and Kang [START_REF] Bodirsky | Enumeration and asymptotic properties of unlabeled outerplanar graphs[END_REF] and Kraus [START_REF] Kraus | The degree distribution in unlabelled 2-connected graph families[END_REF] concerning random unlabelled outerplanar graphs. Drmota, Fusy, Kang, Kraus and Rué [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF] took a unified approach to study so called families of subcritical classes of unlabelled graphs, and Drmota and Jin [START_REF] Drmota | An asymptotic analysis of labeled and unlabeled k-trees[END_REF] and Gainer-Dewar, Gessel and Ira [START_REF] Gainer-Dewar | Counting unlabeled k-trees[END_REF] treated unlabelled k-dimensional trees.

In the present work we aim to bring a new probabilistic perspective to the study of random unlabelled graphs by establishing graph limits. The first model considered is that of random unlabelled rooted connected graphs sampled with probability proportional to a product of weights assigned to their 2-connected components. For this model, we obtain a local weak limit that describes the asymptotic vicinity near the fixed root, a Benjamini-Schramm limit that describes the asymptotic shape near a random vertex, and a Gromov-Hausdorff scaling limit. Moreover, we obtain sharp tail bounds for the diameter. In the two local limits, we even obtain total variational convergence of arbitrary o( √ n)-sized neighbourhoods of the fixed root and random root, which is best-possible as the convergence fails for neighbourhoods whose radius is comparable to √ n. The setting we consider explicitly includes uniform random unlabelled rooted graphs from so called subcritical graph classes introduced in [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF], such as series-parallel graphs, outerplanar graphs, and cacti graphs. As for extremal graph parameters, our results also establish the correct order of the diameter. The maximum degree and largest 2-connected component are shown to have typically order O(log n). In [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF] additive parameters of these graphs such as the degree distribution were studied using analytic methods. The two local limits add a probabilistic interpretation to the limit degree distributions obtained in [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF] for the degree of a random vertex and of the fixed

The author is supported by the German Research Foundation DFG, STU 679/1-1.

root. Furthermore, general results by Kurauskas [46,Thm. 2.1] and Lyons [START_REF] Lyons | Asymptotic enumeration of spanning trees[END_REF]Thm. 3.2] for Benjamini-Schramm convergent sequences of random graphs may be applied to deduce laws of large numbers for subgraph count asymptotics and spanning tree count asymptotics in terms of the Benjamini-Schramm limit.

Our general results also apply to random unlabelled k-trees that are rooted at a front of distinguishable vertices. A k-tree consists either of a complete graph with k vertices, or is obtained from a smaller k-tree by adding a vertex and connecting it with k distinct vertices of the smaller k-tree. Such objects are interesting from a combinatorial point of view, as their enumeration problem has a long history, see [START_REF] Moon | The number of labeled k-trees[END_REF][START_REF] Gainer-Dewar | Γ-species and the enumeration of k-trees[END_REF][START_REF] Fowler | The specification of 2-trees[END_REF][START_REF] Foata | Enumerating k-trees[END_REF][START_REF] Darrasse | Limiting distribution for distances in k-trees[END_REF][START_REF] Beineke | The number of labeled k-dimensional trees[END_REF][START_REF] Harary | Graphical enumeration[END_REF]. They are also interesting from an algorithmic point of view, as many NP-hard problems on graphs have polynomial algorithms when restricted to k-trees [START_REF] Arnborg | Linear time algorithms for NP-hard problems restricted to partial k-trees[END_REF][START_REF] Grötschel | Preface. In Building bridges[END_REF]. Employing recent results for limits of random unlabelled Gibbs partitions [START_REF] Stufler | Unlabelled Gibbs partitions[END_REF], we obtain a local weak limit for unlabelled front-rooted k-trees that describes the total variational asymptotic behaviour of arbitrary o( √ n)-neighbourhoods of the root-front. We also obtain a Benjamini-Schramm limit describing the asymptotic shape of o( √ n)-neighbourhoods of a uniformly at random selected vertex. Furthermore, we obtain a Gromov-Hausdorff scaling limit. For all three limits, a concentration result is required that relates the distances of certain points with respect to the k-tree metric and to a tree-metric in the underlying representation by trees endowed with local symmetries. We obtain this intermediate result by locating a hidden Markov chain and applying a large deviation inequality by Lezaud [START_REF] Lezaud | Chernoff-type bound for finite Markov chains[END_REF] for functions on non-reversible Markov processes.

As a third application, our results also yield local weak limits, Benjamini-Schramm limits and scaling limits for a family of random unordered trees drawn according to weights assigned to the vertex degrees. The scaling limit mildly generalizes previous results for uniform vertex degree restricted trees [START_REF] Marckert | The CRT is the scaling limit of unordered binary trees[END_REF][START_REF] Haas | Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees[END_REF][START_REF] Panagiotou | Scaling limits of random Pólya trees[END_REF]. From a probabilistic viewpoint it is natural to consider weights and not only the uniform measure, as this constitutes the unordered analogue of Galton-Watson trees conditioned on having a large number of vertices, or more generally so called simply generated plane trees. As demonstrated by Janson [START_REF] Janson | Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation[END_REF], random weighted plane trees may be classified into various regimes, each exhibiting characteristic asymptotic behaviour. For this reason, it is also natural to work towards a similar classification for random weighted unordered trees.

Due to the length of the present paper one might get the impression that the applications we provide are independent problems that should be treated separately. It is actually one of the main points we are trying to make here, that this is not the case. As for the limits, we are going to use the local weak limits to establish a large deviation result that is crucial for obtaining the scaling limits. Conversely, this result also allows us to establish the local weak limits and Benjamini-Schramm limits in their strong form, featuring total variational convergence of o( √ n)-neighbourhoods. Moreover, rather than treating each model of random graphs individually, we take a unified approach and establish a set of limit theorems that apply to the abstract family of random unlabelled R-enriched trees, with the class R ranging over all combinatorial classes. Roughly speaking, given a class R of combinatorial objects, an R-enriched tree is a rooted tree together with a function that assigns to each vertex an R-structure on its offspring. The model we consider is an unlabelled R-enriched tree with n vertices considered up to symmetry, that we sample with probability proportional to a weight formed by taking the product of weights assigned to its local R-structures. The limits are formed as n becomes large, possibly along a shifted sublattice of the integers. We are going to explain in detail how the mentioned models of random unlabelled graphs fit into this framework. Of course it also makes sense to study a labelled analogue, and this endeavour is undertaken in [START_REF] Stufler | Limits of random tree-like discrete structures[END_REF].

There are various reasons for taking this general approach. First of all, the method of our proofs requires per se that we consider trees enriched with arbitrary structures, not just the structure that corresponds to the graphs under consideration. The limit objects are defined in terms of plane trees enriched with local symmetries, and then interpreted as random graphs according to combinatorial bijections. The benefit of this is that we may really see how classical probabilistic objects such as Kesten's tree or asymptotic fringe distributions [START_REF] Aldous | Asymptotic fringe distributions for general families of random trees[END_REF] are hidden inside. Furthermore, given the immense variety of combinatorial structures [START_REF] Flajolet | Analytic combinatorics[END_REF], it is interesting that a high-level point of view that covers a large class of seemingly unrelated discrete structures is even possible.

Plan of the paper. Section 1 gives an informal description of the topic and main applications. Section 2 fixes notation related to graphs, trees and k-trees, and recalls necessary background on local weak convergence, Gromov-Hausdorff convergence and further properties of large critical Galton-Watson trees. Section 3 is a concise introduction to the combinatorial framework of species of structures and Boltzmann distributions, with a focus on the decomposition of symmetries. Section 4 discusses a limit theorem for unlabelled Gibbs partitions, that we are going to use in our applications. Section 5 explicitly states some probabilistic and combinatorial tools related to random walks and Markov chains. Section 6 presents the contributions of the present paper in detail. Specifically, Subsection 6.1 introduces the model of unlabelled R-enriched trees under consideration, and discusses combinatorial bijections that show how this generalizes various models of random graphs considered up to symmetry, in particular unlabelled blockweighted rooted graphs and unlabelled front-rooted k-trees. Subsection 6.2 builds the framework regarding the local weak limits of unlabelled enriched trees with respect to the fixed root vertex and with respect to a randomly selected point. Subsection 6.3 introduces a general model of random metric spaces based on random unlabelled enriched trees, and establishes a scaling limit and sharp diameter tail-bounds. Subsection 6.4 presents our applications to random weighted unlabelled connected rooted graphs, in particular a scaling limit with respect to the first-passage percolation metric, sharp diameter tail-bounds, a local weak limit and a Benjamini-Schramm limit. Subsection 6.5 discusses applications to random unlabelled front-rooted k-dimensional trees, for which a scaling limit, a local weak limit and a Benjamini-Schramm limit are established. Subsection 6.6 presents further applications to a family of simply generated unlabelled unrooted trees. In Section 7 we collect all proofs. The set of non-negative real numbers is denoted by R ≥0 . We usually assume that all considered random variables are defined on a common probability space whose measure we denote by P, and let L p denote the corresponding space of p-integrable real-valued functions. All unspecified limits are taken as n becomes large, possibly taking only values in a subset of the natural numbers.

We write d -→ and p -→ for convergence in distribution and probability, and

= for equality in distribution. An event holds with high probability, if its probability tends to 1 as n tends to infinity. We let O p (1) denote an unspecified random variable X n of a stochastically bounded sequence (X n ) n , and write o p (1) for a random variable X n with X n p -→ 0. We write L(X) to denote the law of a random variable X. The total variation distance of measures and random variables is denoted by d TV . Given a power series f (z), we let [z n ]f (z) denote the coefficient of z n in f (z).

2.2. Graphs, trees and k-trees. We are going to consider simple graphs, that have no loops or parallel edges. The vertices that are adjacent to a vertex v in a graph G are its neighbourhood. The cardinality of its neighbourhood is called the degree of the vertex v, and denoted by d G (v). We say G is locally finite, if all its vertices have finite degree. A graph is termed connected, if any two vertices may be joined by a path. More generally, for k ≥ 1 we say a graph G is k-connected, if it has at least k + 1 vertices and deleting any k -1 of them does not disconnect the graph. A cutvertex is a vertex whose removal disconnects the graph. Hence 2-connected graphs are graphs without cutvertices and size at least three.

A graph isomorphism between graphs G and H is a bijection between their vertex sets such any two vertices in G are joined by an edge if and only if their images in H are. In this case we say the two graphs are isomorphic. We say a graph is rooted, if one of its vertices is distinguished. Graph isomorphisms between rooted graphs are required to map the roots to each other. More generally, we may consider graphs with an ordered number of distinguishable root-vertices, that must be respected by graph isomorphisms. A graph considered up to isomorphism is an unlabelled graph. That is, any two unlabelled graphs are distinct if they are not isomorphic. Formally, unlabelled graphs are defined as isomorphism classes of graphs. Unlabelled rooted graphs are defined analogously.

A tree is a graph that is connected and does not contain circles. In a rooted tree, we say the vertices lying on the path between a vertex v and the root are the ancestors of v. The vertices that are joined to v by an edge but are not ancestors are its offspring or sons. The collection of the sons of a vertex is its offspring set. The cardinality of the offspring set of a vertex v in a rooted tree A is its outdegree and denoted by d + A (v). Unlabelled rooted trees are also termed Pólya-trees, in honour of George Pólya.

The complete graph with n vertices is denoted by K n . That is, in K n any two distinct vertices are connected. A subgraph of a graph is termed an n-clique, if its isomorphic to K n . A k-tree is a graph that may be constructed by starting with a k-clique, and adding in each step a new vertex that gets connected with k arbitrarily chosen distinct vertices of the previously constructed graph. The k-cliques of a k-tree are also called its fronts, and the k + 1-cliques its hedra. In the present work, we are only considering k-trees that are rooted at a front of distinguishable vertices.

A block B of a graph G is a subgraph that is inclusion maximal with the property of being either an isolated vertex, a 2-clique, or 2-connected. Connected graphs have a tree-like block-structure, whose details are explicitly given for example in Diestel's book [START_REF] Diestel | Graph theory[END_REF]Ch. 3.1]. We mention a few properties, that we are going to use. Any two blocks of G overlap in at most one vertex. The cutvertices of G are precisely the vertices that belong to more than one block.

Any connected graph C is naturally equipped with the graph-metric on its vertex set, that assigns to any two vertices the minimum number of edges required to join them. We usually denote by d C (•, •). Given a vertex v ∈ C and an integer k ≥ 0, the k-neighbourhood V k (C, v) is the subgraph induced by all vertices with distance at most k from v. We regard V k (C, v) as rooted at the vertex v. The diameter D(C) is the supremum of all distances between pairs of vertices. For a rooted graph C • , we may also consider its height H(C • ), which is the supremum of all distances of vertices from the root of C • . Given a vertex v, we let h C • (v) denote its distance from the root.

Another metric on C is the block-metric d block . The block-distance between any two vertices of C is given by the minimum number of blocks required to cover any joining path. By standard properties of the block-structure of connected graphs, the choice of the joining path does not matter. For any vertex v ∈ C and any integer k ≥ 0 we let U k (C, v) denote the k-blockneighbourhood, that is, the subgraph induced by all vertices with block-distance at most k. We regard U k (C, v) as rooted at the vertex v.

Local weak convergence.

Let G • = (G, v G ) and H • = (H, v H ) be two connected, rooted, and locally finite graphs. We may consider the distance

d(G • , H • ) = 2 -sup{k∈N 0 | V k (G • ) V k (H • )} with V k (G • ) V k (H • )
denoting isomorphism of rooted graphs. This defines a premetric on the collection of all rooted locally finite connected graphs. Two such graphs have distance zero, if and only if they are isomorphic. Hence this defines a metric d BS on the collection B of all unlabelled, connected, rooted, locally finite graphs. The space (B, d BS ) is known to be complete and separable, that is, a Polish space.

A random rooted graph G • ∈ B is the the local weak limit of a sequence

G • n = (G n , v n ), n ∈ N of random elements of B, if it is the weak limit with respect to this metric. That is, if lim n→∞ E[f (G • n )] = E[f (G • )] for any bounded continuous function f : B → R. This is equivalent to stating lim n→∞ P(V k (G • n ) G • ) = P(V k (G • ) G • ).
for any rooted graph G • . If the conditional distribution of v n given the graph G n is uniform on the vertex set V (G n ), then the limit G • is often also called the Benjamini-Schramm limit of the sequence (G n ) n . This kind of convergence often yields laws of large numbers for additive graph parameters [START_REF] Lyons | Asymptotic enumeration of spanning trees[END_REF][START_REF] Kurauskas | On local weak limit and subgraph counts for sparse random graphs[END_REF].

2.4. Gromov-Hausdorff convergence. Let X • = (X, d X , x 0 ) and Y • = (Y, d Y , y 0 ) denote pointed compact metric spaces. A correspondence between X • and Y • is a subset R ⊂ X × Y containing (x 0 ,
y 0 ) such that for any x ∈ X there is a point y ∈ Y with (x, y) ∈ R, and conversely for any y ∈ Y there is a point x ∈ X with (x, y) ∈ R. The distortion of the correspondence is defined as the supremum

dis(R) = sup{|d X (x 1 , x 2 ) -d Y (y 1 , y 2 ) | (x 1 , y 1 ), (x 2 , y 2 ) ∈ R}.
The (pointed) Gromov-Hausdorff distance between the pointed spaces X • and Y • may be defined by

d GH (X, Y ) = 1 2 inf R dis(R)
with the index R ranging over all correspondences between X • and Y • . The factor 1/2 is only required in order to stay consistent with an alternative definition of the Gromov-Hausdorff distance via the Hausdorff distance of embeddings of X • and Y • into common metric spaces, see [START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF]Prop. 3.6] and [START_REF] Burago | A course in metric geometry[END_REF]Thm. 7.3.25]. This distance satisfies the axioms of a premetric on the collection of all compact rooted metric spaces. Two such spaces have distance zero from each other, if and only if they are isometric. That is, if there is a distance preserving bijection between the two that also preserves the root vertices. Hence this yields a metric on the collection K • of isometry classes of pointed compact metric spaces. The space (K • , d GH ) is known to be Polish (complete and separable), see [START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF]Thm. 3.5] and [START_REF] Burago | A course in metric geometry[END_REF]Thm. 7.3.30 and 7.4.15].

2.5.

Large critical Galton-Watson trees. In this section we let T n denote a Galton-Watson tree conditioned on having n vertices, such that offspring distribution ξ has average value E[ξ] = 1 and finite non-zero variance σ 2 .

2.5.1.

Convergence toward the CRT. The (Brownian) continuum random tree (CRT) is a random metric space constructed by Aldous in his pioneering papers [START_REF] Aldous | The continuum random tree[END_REF][START_REF] Aldous | The continuum random tree. II. An overview[END_REF][START_REF] Aldous | The continuum random tree[END_REF]. Its construction is as follows.

To any continuous function f :

[0, 1] → [0, ∞[ satisfying f (0) = f (1) = 0 we may associate a premetric d on the unit interval [0, 1] given by d(u, v) = f (u) + f (v) -2 inf u≤s≤v f (s) for u ≤ v. The corresponding quotient space (T f , d T f ) = ([0, 1]/∼, d
), in which points with distance zero from each other are identified, is considered as rooted at the coset 0 of the point zero. This pointed metric space is an R-tree, see [START_REF] Duquesne | Probabilistic and fractal aspects of Lévy trees[END_REF][START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF] for the definition of R-trees and further details. The CRT may be defined as the random pointed metric space (T e , d Te , 0) corresponding to Brownian excursion e = (e t ) 0≤t≤1 of duration one. The famous invariance principle,

(T n , σ 2 n -1/2 d Tn , ∅) d -→ (T e , d Te , 0) (2.1)
in the Gromov-Hausdorff sense, is due to Aldous [START_REF] Aldous | The continuum random tree[END_REF] and there exist various extensions, see for example Duquesne [START_REF] Duquesne | A limit theorem for the contour process of conditioned Galton-Watson trees[END_REF], Duquesne and Le Gall [START_REF] Duquesne | Probabilistic and fractal aspects of Lévy trees[END_REF], Haas and Miermont [START_REF] Haas | Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees[END_REF]. We are going to use a popular shortened notation for rescaled version of metric spaces, writing for example simply

σ 2 n -1/2 T n d -→ T e
for Equation (2.1).

2.5.2. Bounds for the height and level width. Addario-Berry, Devroye and Janson [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF]Thm. 1.2] showed that there are constants C, c > 0 such that for all n and h ≥ 0

P(H(T n ) ≥ h)) ≤ C exp(-ch 2 /n). (2.2)
The first moment of the number L k (T n ) of all vertices v with height h Tn (v) = k admits a bound of the form

E[L k (T n )] ≤ Ck exp(-ck 2 /n). (2.3)
for all n and k ≥ 1. See [1, Thm. 1.5].

Combinatorial species and weighted Boltzmann distributions

In order to study combinatorial objects up to symmetry, it is convenient to use the language of combinatorial species developed by Joyal [START_REF]Une théorie combinatoire des séries formelles[END_REF]. It provides a clean and powerful framework in which complex combinatorial bijection may be stated using simple algebraic terms. In order to make the present work accessible to a large audience, we recall the notions and results required to state and prove our main results. The theory admits an elegant and concise description using the language of category theory, but we will avoid this terminology and assume no knowledge by the reader in this regard. The exposition of the combinatorial and algebraic aspects in the subsequent subsections follows mainly Joyal [START_REF]Une théorie combinatoire des séries formelles[END_REF] and Bergeron, Labelle and Leroux [START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications[END_REF]. The probabilistic aspects in the Boltzmann sampling framework is based on a recent result by Bodirsky, Fusy, Kang and Vigerske [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Prop. 38].

Weighted combinatorial species.

A combinatorial species F is a functor or "rule" that produces for each finite set U a finite set F[U ] of F-objects and for each bijection σ :

U → V a bijective map F[σ] : F[U ] → F[V ]
such that the following properties hold. 1) F preserves identity maps, that is for any finite set U it holds that

F[id U ] = id F [U ] .
2) F preserves composition of maps, that is, for any bijections of finite sets σ : U → V and σ : V → W we require that

F[σ σ] = F[σ ]F[σ].
The idea behind this is that finite combinatorial objects are composed out of atoms, and relabelling these atoms yields structurally equivalent objects.

We say a combinatorial species F maps any finite set U of labels to the finite set F[U ] of F-objects and any bijection σ : U → V to the transport function F[σ]. For any two F-objects

F U ∈ F[U ] and F V ∈ F[V ] that satisfy F[σ](F U ) = F V ,
we say F U and F V are isomorphic and σ is an isomorphism between them. The object F U has size |F U | = |U | and U is its underlying set. An unlabelled F-object or isomorphism type is an isomorphism class of F-objects. That is, a maximal collection of pairwise isomorphic objects. By abuse of notation, we treat unlabelled objects as if they were regular objects.

An R ≥0 -weighted species F ω consists of a species F and a weighting ω that produces for any finite set U a map

ω U : F[U ] → R ≥0 such that ω U = ω V • F[σ] for any bijection σ : U → V . Any object F ∈ F[U ] has weight ω U (F ).
By abuse of notation we will often drop the index and write ω(F ) instead of ω U (F ). Isomorphic structures have the same weight, hence we may define the weight of an unlabelled F-object to be the weight of any representative. The inventory | F[n]| ω is defined as the sum of weights of all unlabelled F-objects of size n. Any species may be considered as a weighted species by assigning weight 1 to each structure, and in this case the inventory counts the number of F-objects. If we do not specify any weighting for a species, then we assume that it is equipped with this canonical weighting.

To any weighted species F ω we may associate its ordinary generating series

Fω (z) = n≥0 | F[n]| ω z n = F unlabelled F -object ω(F )z |F | .
We may form the species Sym(F) of F-symmetries by letting Sym(F)[U ] be the set of all pairs (F, σ) with F ∈ F[U ] an F-structure and σ an automorphism of F , that is, a bijection σ : U → U with F[σ](F ) = F . For any bijection γ : U → V the corresponding transport function Sym(F)[γ] maps to a symmetry (F, σ) ∈ Sym(F)[U ] to the symmetry (F

[γ](F ), γσγ -1 ) in Sym(F)[V ].
There is a canonical weighting on Sym(F) with weights in the power series ring R[[s 1 , s 2 , . . .]]. By abuse of notation, we also denote this weighting by ω. It is given by

ω(F, σ) = ω(F )s σ 1 1 s σ 2 2 • • • with σ i denoting
the number of cycles of length i of the permutation σ. Here we count fixpoints as 1-cycles. The cycle index sum Z F ω of F ω may be defined is defined by

Z F ω = n≥0 (F,σ)∈Sym(F )[n] ω(F, σ)/n! ∈ R[[s 1 , s 2 , . . .]].
The generating series are related by Fω (z) = Z F ω (z, z 2 , z 3 , . . .). (3.1) See for example Chapter 2.3 in the book by Bergeron, Labelle and Leroux [START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications[END_REF]. The main reason for considering symmetries is the following enumerative fact. Lemma 3.1 (Number of symmetries). For each unlabelled F-object t with size n there are precisely n! symmetries (F, σ) ∈ Sym(F) [n] such that the isomorphism type t(F ) of the F-object F is equal to t. This follows from basic properties of group operations, see for example Joyal [START_REF]Une théorie combinatoire des séries formelles[END_REF]Sec. 3]. In particular, if we draw a symmetry (F, σ) from the set Sym(F)[n] at random with probability proportional to the weight of its F-object, then

P(t(F) = t) = ω(t)/ s∈ F [n] ω(s) (3.2)
for any unlabelled F-object t of size n.

We say that two species F and G are isomorphic, denoted by F G, if there is a family (α U ) U of bijections α U : F[U ] → G[U ], with the index U ranging over all finite sets, such that the following diagram commutes for any bijection σ : U → V of finite sets.

F[U ] α U F [σ] / / F[V ] α V G[U ] G[σ] / / G[V ]
The family (α U ) U is then termed a species isomorphism from F to G. Two weighted species F ω and G ν are called isomorphic, if there exists a species isomorphism (α U ) U from F to G that preserves the weights, that is, with ν(α U (F )) = ω(F ) for each finite set U and F-object F ∈ F[U ]. In this case the cycle index sums and hence also the ordinary generating series of F ω and G ν coincide.

There are some natural examples of species that we are going to encounter frequently. The species SET with SET[U ] = {U } has only one structure of each size and its cycle index sum is given by Z SET (s 1 , s 2 , . . .) = exp(

i≥1 s i /i).
The species SEQ of linear orders assigns to each finite set U the set SEQ[U ] of tuples (u 1 , . . . , u t ) of distinct elements with U = {u 1 , . . . , u t }. Its cycle index sum is given by

Z SEQ (s 1 , s 2 , . . .) = 1/(1 -s 1 ).
The species X is given by X

[U ] = ∅ if |U | = 1 and X [U ] = {U } if U is a singleton.
The species 0 is given by 0[U ] = ∅ for all U , and the species 1 by 1[∅] = {∅} and 1[U ] = ∅ for all finite non-empty sets U .

3.2. Operations on species. Species may be combined in several ways to form new species.

3.2.1. Products. The product F • G of two species F and G is the species given by

(F • G)[U ] = (U 1 ,U 2 ) F[U 1 ] × G[U 2 ]
with the index ranging over all ordered 2-partitions of U , that is, ordered pairs of (possibly empty) disjoint sets whose union equals U . The transport of the product along a bijection is defined componentwise. Given weightings ω on F and ν on G, there is a canonical weighting on the product given by

µ(F, G) = ω(F )ν(G).
This defines the product of weighted species

(F • G) µ = F ω • G ν .
The corresponding cycle index sum satisfies

Z (F •G) µ = Z F ω Z G ν .
We also define the powers of a species by

(F ω ) i = F ω • . . . • F ω
with i factors in total, and define (F ω ) 0 = 0 to be the empty species having no objects at all.

3.2.2. Sums. Let (F i ) i∈I be a family of species such that for any finite set U only finitely many indices i with F i [U ] = ∅ exist. Then the sum i∈I F i is a species defined by

i∈I F i [U ] = i∈I F i [U ].
Given weightings ω i on F i , there is a canonical weighting µ on the sum given by

µ(F ) = ω i (F )
for any i and F ∈ F i [U ]. This defines the sum of the weighted species

i∈I F i µ = i∈I F ω i i .
The corresponding cycle index sum is given by

Z i F ω i i = i Z F ω i i .
3.2.3. Derived species. Given a species F, the corresponding derived species F is defined by

F [U ] = F[U ∪ { * U }]
with * U referring to an arbitrary fixed element not contained in the set U . For example, we could set * U = {U }. By abuse of notation, we are often going to drop the index and just refer to the * -atom. Any weighting ω on F may also be viewed as a weighting on F , by letting the weight of a derived object F ∈ F [U ] be given by ω U ∪{ * U } (F ). The transport along a bijection σ : U → V is done by applying the transport F[σ ] of the bijection σ :

U ∪ { * U } → V ∪ { * V } with σ |U = σ.
This defines the weighted derived species (F ) ω . Its cycle index sum is given by

Z (F ) ω = ∂ ∂s 1 Z F ω .
3.2.4. Pointing. For any species F we may form the pointed species F • . It is given by the product of species F • = X • F with X denoting the species consisting of single object of size 1. In other words, an F • -object is a pair (F, v) of an F-object F and a distinguished label v which we call the root of the object. Any weighting ω on F may also be considered as a weighting on F • , by letting the weight of (F, v) be given by ω(F ). This choice of weighting is consistent with the natural weighting given by the product and derivation operation X • F , if we assign weight 1 to the unique object of X . The corresponding cycle index sum is consequently given by

Z (F • ) ω = s 1 ∂ ∂s 1 Z F ω .
3.2.5. Substitution. Given species F and G with G[∅] = ∅, we may form the composition F • G as the species with object sets

(F • G)[U ] = π   {π} × F[π] × Q∈π G[Q]   ,
with the index π ranging over all unordered partitions of the set U . Here the transport (F • G)[σ] along a bijection σ : U → V is done as follows. For any object (π, F, andlet σ : π → π denote the induced bijection between the partitions. Then set

(G Q ) Q∈π ) in (F • G)[U ] define the partition π = {σ(Q) | Q ∈ π},
(F • G)[σ](π, F, (G Q ) Q∈π ) = (π, F[σ](F ), (G[σ| Q ](g Q )) σ(Q)∈π ).
That is, the transport along the induced bijection of partitions gets applied to the F-object and the transports along the restrictions σ| Q , Q ∈ π get applied to the G-objects. Often, we are going to write F(G) instead of F • G. Given a weighting ω on F and a weighting ν on G, there is a canonical weighting µ on the composition given by

µ(π, F, (G Q ) Q∈π ) = ω(F ) Q∈π ν(Q).
This defines the composition of weighted species

(F • G) µ = F ω • G ν .
The corresponding cycle index sum is given by

Z (F •G) µ (s 1 , s 2 , . . .) = Z F ω (Z G ν (s 1 , s 2 , . . .), Z G ν 2 (s 2 , s 4 , . . .), Z G ν 3 (s 3 , s 6 , . . .), . . .). (3.3)
Here ν i denotes the weighting with (ν i )(G) = ν(G) i for all G-structures G.

3.2.6. Restriction. For any subset Ω ⊂ N 0 we may restrict a weighted species F ω to objects whose size lies in Ω and denote the result by F ω Ω . 3.2.7. Relations between the different operations. The interplay of the operations discussed in this section is described by a variety of natural isomorphisms. The two most important are the product rule and the chain rule.

Proposition 3.2 ([44]

). Let F ω and G ν be weighted species.

(1) There is a canonical choice for an isomorphism

(F ω • G ν ) (F ω ) • G ν + F ω • (G ν ) .
(2) Suppose that G[∅] = ∅. Then there is also a canonical isomorphism We may easily verify the product rule, as the * -label in (F ω • G ν ) may either belong the F-structure, accounting for the summand (F ω ) • G ν , or to the G-structure, accounting for the second summand. The chain rule also has an intuitive explanation. The idea is that the partition class or G-structure containing the * -label in an (F ω • G ν ) -structure distinguishes an atom of the F-structure. Hence the (F ω • G ν ) -structure consists of a (F ω ) • G ν ) composite structure, where all atoms of the F-structure receive a regular G-structure, except for a marked * -atom, to which we assign a derived G-structure, which accounts for the extra factor (G ν ) .

(F ω • G ν ) ((F ω ) • G ν ) • (G ν ) .
3.3. Symmetries of the substitution operation. We are going to need detailed information on the structure of the symmetries of the composition F • G. The exposition of this section follows Joyal [START_REF]Une théorie combinatoire des séries formelles[END_REF]Sec. 3.2] and Bergeron, Labelle and Leroux [START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications[END_REF]Sec. 4.3]. We are going to discuss the following result. Lemma 3.3 (Parametrization of the symmetries of the substitution). Up to isomorphism of symmetries, any F • G-symmetry may be constructed as described below from an F-symmetry (F, σ) together with a family of G-symmetries (G τ , σ τ ) τ with the index τ ranging over all cycles of the permutation σ.

There is much more to this result, as it lies at the heart of the proof of Equation (3.3). We refer the inclined reader to the mentioned literature for details. For our purposes, it is sufficient to understand how the symmetry and in particular its cycles get assembled. We are going to use this later in order to define random unlabelled structures based on a tree-like decomposition of symmetries.

The method of construction referred to in Lemma 3.3 is a bit involved, hence let us first recall what an F • G-symmetry is by definition. Let U be a finite set. Any element of Sym(F • G)[U ] consists of the following objects: a partition π of the set U , an F-structure

F ∈ F[π], a family of G-structures (G Q ) Q∈π with G Q ∈ G[Q]
and a permutation σ : U → U . The permutation σ is required to permute the partition classes and induce an automorphism

σ : π → π, Q → σ(Q) of the F-object F . Moreover, for any partition class Q ∈ π the restriction σ| Q : Q → σ(Q) is required to be an isomorphism from G Q to G σ(Q) .
Note that for any cycle τ

= (Q 1 , . . . , Q ) of σ, it follows that σ | Q 1 : Q 1 → Q 1 is an automorphism of G Q 1 . Hence (G τ , σ τ ) := (G Q 1 , σ | Q 1 ) is a G-symmetry.
The symmetry S together with the bijections γ i := σ| Q i for 1 ≤ i ≤ -1 already contain all information about the G-objects

G Q 1 , . . . , G Q and the restriction σ| Q 1 ∪...∪Q . Indeed, it holds that G Q i+1 = G[γ i • • • γ 1 ](G τ ) for all 1 ≤ i ≤ -1,
hence we may reconstruct the G-objects. The bijections γ i contain all information about σ Q 1 ∪...∪Q -1 , and it holds that

σ| Q = γ -1 -1 • • • γ -1 1 σ τ .
In particular, any k-cycle (a 1 , . . . , a k ) of the permutation σ τ corresponds to the k -cycle (a 1 , σ(a 1 ), . . . , σ -1 (a 1 ), a 2 , σ(a 2 ), . . . , σ -1 (a 2 ), . . . , a k , σ(a k ), . . . , σ -1 (a k )) of the permutation σ| Q 1 ∪...∪Q . This implies that any F • G-symmetry is isomorphic to a symmetry ((π, F, (G Q ) Q∈π ), σ) constructed in the following way, which is illustrated in Figure 1. Start with choosing an F-symmetry (m, σ m ). For any cycle τ of the permutation σ m choose a G-symmetry (G τ , σ τ ) and let Q τ denote its set of labels. For every atom e of the cycle τ set Then the product σ of all composed cycles (one for each choice of (c, ν)) is an automorphism of the F • G-structure C. The composed cycles are pairwise disjoint, hence it does not matter in which order we take the product. Note that σ does not depend on the choice of the a's but different choices of the b's result in a different automorphism σ. More precisely, if for a given cycle τ of σ m we choose τ (b) instead of b, then the resulting automorphism is given by the conjugation (id, τ )σ(id, τ ) -1 instead of σ. But (id, τ ) is an automorphism of the F • G-structure C, hence the resulting symmetry (C, (id, τ )σ(id, τ ) -1 ) is isomorphic to (C, σ). This implies that the isomorphism type of (C, σ) does not depend on the choices of the a's and b's. Fixing any canonical way of making these choices yields the construction of Lemma 3.3.

3.4.

Weighted Boltzmann distributions and samplers. Boltzmann distributions crop up in the study of local limit of random discrete structures and in the limit of convergent unlabelled Gibbs partitions. A Boltzmann sampler is a possibly recursive procedure involving random choices that generates a structure according a Boltzmann distribution. For example, a subcritical or critical Galton-Watson tree may be considered as a Boltzmann distributed plane tree. A recursive sampler in this setting is a procedure that draws the offspring of the root and then calls itself for each offspring vertex.

3.4.1. Boltzmann distributions. Let F ω be a weighted species. For any y ≥ 0 satisfying 0 < Fω (y) < ∞, the corresponding Boltzmann distribution for unlabelled F-objects is given by

P F ω ,y ( F ) = Fω (y) -1 ω( F )y | F | , F an unlabelled F-object. (3.4)
Given a sequence y = (y j ) j∈N of non-negative parameters y j satisfying 0 < Z F ω (y) < ∞, the corresponding Pólya-Boltzmann distribution is given by

P Sym(F ) ω ,y (F, σ) = Z F ω (y) -1 ω(F ) y σ 1 1 y σ 2 2 • • • |(F, σ)|! , (F, σ) ∈ m≥0 Sym(F)[m], (3.5)
with σ i denoting the number of i-cycles of a permutation σ. By Lemma 3.1 and Equation (3.1), the Boltzmann distribution for unlabelled objects may be considered as the marginal distribution of the F-object in special cases of the Pólya-Boltzmann distribution. That is, the F-object of a P Sym(F ) ω ,(y,y 2 ,y 3 ,...) -distributed F-symmetry follows a P F ω ,y -distribution.

Boltzmann samplers.

The following lemma allows us to construct Boltzmann distributed random variables in the unlabelled setting for the sum, product and composition of species. The results of this section have been established by Bodirsky, Fusy, Kang and Vigerske [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Prop. 38] for species without weights, and the generalization to the weighted setting is straight-forward.

Lemma 3.4 (Weighted Pólya-Boltzmann samplers).

(1) Let F ω and G ν be weighted species, and let X and Y be independent random variables with distributions L(X) = P Sym(F ) ω ,y and L(Y

) = P Sym(G) ω
L ((F • G)[α](X, Y )) = P Sym(F •G) ω ,y .
(2) Let (F ω i i ) i∈I be a family of weighted species, and (X i ) i∈I a family of independent random variables with distributions

P Sym(F i ) ω i ,y such that i Z F ω i i (y) < ∞. If K ∈ I gets drawn at random with probability proportional to Z F ω K K (y), that is P(K = k) = Z F ω k k (y)/ i Z F ω i i (y), then L(X K ) = P Sym( i F ω i i ),y . (3) Let F ω and G ν be species such that G ν [∅] = ∅ and let y = (y j ) j∈N a family of non- negative parameters with 0 < Z G ν (y) < ∞ and 0 < Z F ω •G ν (y) < ∞. For each k set y k = (y k , y 2k , y 3k , . . .). Let X = (F, σ) be a P Sym(F ω ),(Z G ν 1 (y),Z
G ν 2 (y 2 ),...) -distributed random F-symmetry and let (Y i,k ) i,k∈N an independent family (that is also independent of X) of random G-symmetries such that Y i,k follows a P Sym(G ν ),y k -distribution for all k, i. We may canonically assign to each cycle τ of the random permutation σ a unique element Y τ of the list (Y i,|τ | ) i≥1 . For example, we could do this by ordering for each the cycles of σ having length according to their smallest atom, and assign Y i, to the ith cycle in the ordering. Then (X, (Y τ ) τ ) corresponds according to Lemma 3.3 to an F • G-symmetry over some set M . Draw a bijection α :

M → [|M |] uniformly at random. Then L((F • G)[α](X, (Y τ ) τ )) = P Sym(F ω •G ν ),y .
3.5. Combinatorial specifications and recursive Boltzmann samplers.

Motivation.

A recursive procedure is a list of instructions that are to be followed step by step and may contain references to the procedure itself. For example, a Galton-Watson tree may be described by the procedure that starts with a root vertex and attaches a random number of independent calls of itself.

Often one encounter species admitting a recursive isomorphism such as F ω X + (F ω ) 2 . If this decomposition satisfies a certain property (R), then for any admissible parameter we may apply the rules from Section 3.4.2 for the sum, product and composition of species in order to construct a recursive (Pólya-)Boltzmann sampler for F. That is, a recursive procedure that terminates almost surely and samples objects according to the (Pólya)-Boltzmann distribution.

For the given example F, such a recursive Boltzmann sampler would first, by the sum rule, make a coin flip in order to determine whether it terminates with a single vertex (a Boltzmann sampler for X κ ), or creates, by the product rule, an ordered pair of independent calls of itself. In other words, its a Galton-Watson tree. As property (R) guarantees that this process terminates almost surely, we also know that this Galton-Watson tree must be critical or subcritical. It is clear that not any recursive decomposition can have this desired property. For example, the species 1 which consists of a single object with size zero admits an isomorphism 1 1 • 1, but applying the product rule yields a recursive procedure which never terminates.

Precisely stating property (R) requires us to introduce the complex concepts of weighted multi-sort species and samplers, as well as related operations such as combinatorial composition and partial derivatives in this context.

Combinatorial specifications.

One should think of multi-sort species as species whose atoms have different colours, such as bicoloured graphs. This concept makes sense for arbitrarily many sorts, but for our purposes it will be sufficient to work with only 2 types of atoms.

A 2-sort species H is a functor that maps any pair

U = (U 1 , U 2 ) of finite sets to a finite set H[U ] = H[U 1 , U 2 ] and any pair σ = (σ 1 , σ 2 ) of bijections σ i : U i → V i to a bijection H[σ] : H[U ] → H[V ]
in such a way, that identity maps and composition of maps are preserved. A weighted 2-sort species H ω additionally carries a weighting ω given by family of maps

ω U 1 ,U 2 : H[U 1 , U 2 ] → R ≥0
for all pairs (U 1 , U 2 ). The weighting is required to assign the same weight to isomorphic structures. That is, the diagram

H[U 1 , U 2 ] H[σ 1 ,σ 2 ] ω U 1 ,U 2 / / R ≥0 H[V 1 , V 2 ] ω V 1 ,V 2 : : must commute for all bijections σ 1 : U 1 → V 1 and σ 2 : U 2 → V 2 .
The operations of sum, product and composition extend naturally to the multi-sort-context Let H and K be 2-sort species and U = (U 1 , U 2 ) a pair of finite sets. The sum is defined by

(H + K)[U ] = H[U ] K[U ]. We write U = V + W if U i = V i ∪ W i and V i ∩ W i = ∅ for all i. The product is defined by (H • K)[U ] = V +W =U H[V ] × K[W ].
The partial derivatives are given by

∂ 1 H[U ] = H[U 1 ∪ { * U 1 }, U 2 ] and ∂ 2 H[U ] = H[U 1 , U 2 ∪ { * U 2 }].
In order state Joyal's implicit species theorem we also require the substitution operation for multi-sort species; this will allow us to define species "recursively" up to (canonical) isomorphism. Let F 1 and F 2 be (1-sort) species and M a finite set. A structure of the composition H(F 1 , F 2 ) over the set M is a quadruple (π, χ, α, β) such that:

(1) π is a partition of the set M .

(2) χ : π → {1, 2} is a function assigning to each class a sort.

(3) α a function that assigns to each class

Q ∈ π a F χ(Q) object α(Q) ∈ F χ(Q) [Q]. (4) β a H-structure over the pair (χ -1 (1), χ -1 (2)
). This construction is functorial: any pair of isomorphisms α 1 , α 2 with α i :

F i G i induces an isomorphism H[α 1 , α 2 ] : H(F 1 , F 2 ) H(G 1 , G 2 ).
Let H be a 2-sort species and recall that X denotes the species with a unique object of size one. A solution of the system Y = H(X , Y) is pair (A, α) of a species A with A[0] = 0 and an isomorphism α : A H(X , A). An isomorphism of two solutions (A, α) and (B, β) is an isomorphism of species u : A B such that the following diagram commutes:

A u α / / H(X , A) H(id,u) B β / / H(X , B)
We may now state Joyal's implicit species theorem. Recall that 0 denotes the empty species with 0[U ] = ∅ for all finite sets U .

Theorem 3.5 ([44], Théorème 6). Let H be a 2-sort species satisfying H(0, 0) = 0. If (∂ 2 H)(0, 0) = 0, then the system Y = H(X , Y) has up to isomorphism only one solution.
Moreover, between any two given solutions there is exactly one isomorphism.

We say that an isomorphism F H(X , F) is a combinatorial specification for the species F if the 2-sort species H satisfies the requirements of Theorem 3.5.

3.5.3. Recursive Boltzmann samplers. Given a combinatorial specification F H(X , F) and parameters x ∈ R N ≥0 with 0 < Z F (x) < ∞ we may apply the rules of Lemma 3.4 recursively to construct a recursive procedure that is guaranteed to terminated almost surely and sample according to a Boltzmann distribution P Z F ,x . A justification of this fact is given by Bodirsky, Fusy, Kang and Vigerske [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Thm. 40] for species without weights, and the generalization to the weighted setting is straight-forward.

Let us illustrate this construction of recursive Boltzmann samplers with an example. Let F be the species of binary unordered rooted trees, where each tree receives weight 1. Any such tree is either a single root vertex, or root vertex with two binary trees dangling from it. This yields an isomorphism

F X + X • F 2 = X • (1 + F 2 )
, where the two summands correspond to the two described cases. This may be reformulated by

F X • G(F) = H(X , F) with G = 1 + X 2 . It holds that (∂ 2 H)(0, 0) = 0 • G (0) = 0, hence for each parameter x = (x i ) i ∈ R N ≥0 with 0 < Z F (x)
< ∞ we may apply the rules of Lemma 3.4 to obtain a recursive procedure that terminates almost surely and whose output follows a P Z F ,x -distribution. Briefly described, the procedure starts with a root-vertex and then draws a G-symmetry according to a Boltzmann distribution P Z G ,(Z F (x i )) i≥1 , with x i = (x i , x 2i , . . .). There are two different outcomes. Either the G-symmetry has size 0, in which the sampler stops. Or it has size 2, in which case the sampler calls itself recursively twice to form the subtrees of the root.

Unlabelled Gibbs partitions and subexponential sequences

The term Gibbs partitions was coined by Pitman [START_REF] Pitman | Combinatorial stochastic processes[END_REF] in his comprehensive survey on combinatorial stochastic processes. It describes a model of random partitions of sets, where the collection of classes as well as each individual partition class are endowed with a weighted structure.

Many structures such as classes of graphs may also be viewed up to symmetry. The symmetric group acts in a canonical way on the collection of composite structures over a fixed set, and its orbits may be identified with the unlabelled objects. Sampling such an isomorphism class with probability proportional to its weight is the natural unlabelled version of the Gibbs partition model.

Let F ω and G ν be weighted species such that G[∅] = ∅, and such that the ordinary generating series

F ω • G ν (z) is not a polynomial. An unlabelled Gibbs partitions is a random composite structure S n = (π n , F n , (G Q ) Q∈πn )
sampled from the set of all n-sized unlabelled F • G-objects with probability proportional to its weight. We are going to describe the asymptotic behaviour of the remainder R n obtained by deleting "the" largest component from S n . More specifically, we make a uniform choice of a component Q 0 ∈ π n having maximal size, and let F n denote the F -object obtained from the F-object F n by relabelling the Q 0 atom of F n to a * -placeholder. This yields an unlabelled F • G-object

R n := (π n \ {Q 0 }, F n , (G Q ) Q∈πn\{Q 0 } ).
In the so called convergent case, the remainder R n is stochastically bounded and even converges in total variation toward a limit object.

Theorem 4.1 ([66, Thm. 3.1]). Suppose that the ordinary generating series Gν (z) has positive radius of convergence ρ, and that the coefficients

g i = [z i ] Gν (z) satisfy g n g n+1 ∼ ρ, 1 g n i+j=n g i g j ∼ 2 Gν (ρ) < ∞.
Suppose further that

Z F ω ( Gν (ρ) + , Gν 2 ((ρ + ) 2 ), Gν 3 ((ρ + ) 3 ), . . .) < ∞ for some > 0. Then [z n ] F ω • G ν (z) ∼ (F ) ω • G ν (ρ)[z n ]G ν (z).
and

d TV (R n , R) → 0, n → ∞ with R denoting a random unlabelled F • G-element that follows a P (F ) ω •G ν ,ρ -Boltzmann distri- bution.
Note that the requirements of the theorem are satisfied if g n = f (n)n -β ρ -n for some constant β > 1 and a function f that varies slowly at infinity.

Probabilistic and combinatorial tools

5.1. The lattice case of the multivariate central local limit theorem. We will make frequent use of the classical local limit theorem for random walks. Lemma 5.1 (Central local limit theorem for lattice distributions). Let Y be a random vector in R d whose support is contained in the lattice a + DZ d with D ∈ GL d (R), a ∈ R d , and in no proper sublattice. Suppose that Y has a finite non-zero covariance matrix Σ, and let (Y i ) i≥1 be a family of independent copies of Y. For all n and y we set

p n (y) := P( n i=1 Y i = y),
and as our assumptions imply that Σ is positive-definite, we may also set

pn (y) := | det D| (2πn) d/2 √ det Σ exp - 1 2n (y -nE[Y]) Σ -1 (y -nE[Y]) .
Then sup

y∈a+DZ d |p n (y) -pn (y)| = o(n -d/2 ).
In particular, p n (y) ∼ pn (y) uniformly for (y -nE[Y])/ √ n bounded.

5.2.

A large deviation inequality for functions on finite Markov chains. The following Chernoff-type bound for finite Markov chains was established by Lezaud [START_REF] Lezaud | Chernoff-type bound for finite Markov chains[END_REF] and does not require the chain to be reversible. Then for each initial distribution q = L(X 1 ) and each 0 < δ ≤ 1 and n ≥ 1 it holds that

P(|f (X 1 ) + . . . + f (X n )| ≥ δn) ≤ 2N q exp - nδ 2 (K) 8b 2 (1 + h(5δ/b 2 )
where N q = q/π 2 and

h(x) = 1 2 √ 1 + x -1 + x 2 .

5.3.

A deviation inequality for random walk. The following deviation inequality is found in most textbooks on the subject.

Lemma 5.3 (Medium deviation inequality for one-dimensional random walk). Let (X i ) i∈N be an i.i.d. family of real-valued random variables with E[X 1 ] = 0 and E[e tX 1 ] < ∞ for all t in some interval around zero. Then there are constants δ, c > 0 such that for all n ∈ N, x ≥ 0 and 0 ≤ λ ≤ δ it holds that

P(|X 1 + . . . + X n | ≥ x) ≤ 2 exp(cnλ 2 -λx).
The proof is by observing that E[e λ|X 1 | ] ≤ 1 + cλ 2 for some constant c and sufficiently small λ, and applying Markov's inequality to the random variable exp(λ(|X 1 | + . . . + |X n |)).

The cycle lemma.

The following combinatorial result is given for example in Takács [START_REF] Takács | A generalization of the ballot problem and its application in the theory of queues[END_REF].

Lemma 5.4 (The cycle lemma). For each sequence k 1 , . . . , k n ≥ -1 of integers with i k i = -r ≤ 0 there exist precisely r values of 0 ≤ j ≤ n -1 such that the cyclic shift

(k 1,j , . . . , k n,j ) := (k 1+j , . . . , k n , k 1 , . . . , k j ) satisfies u i=1 k i,j > -r for all 1 ≤ u ≤ n -1.

Random unlabelled weighted enriched trees with applications

We develop a framework for random enriched trees considered up to symmetry and present our main applications to different models of random unlabelled graphs.

Index of notation.

The following list summarizes frequently used terminology.

R κ

κ-weighted species of R-structures, page 17 subspecies of K of k-trees where the root front lies in precisely one hedron, page 18

A ω R ω-
K • n random unlabelled k-tree from the class K • , page 18 d G (•, •) graph-metric on a connected graph G, page 4 d block (•, •) block-metric, page 4 V k (•) graph-distance k-neighbourhood, page 4 U k (•) block-distance k-neighbourhood, page 4 L k (•)
number of vertices at height k in a rooted tree, page 6

f (A, v)
enriched fringe subtree of an enriched tree A at a vertex v, page 19 (T , β)

random Sym(R)-enriched plane tree, page 19 T f fixpoint subtree corresponding to (T , β), page 20 (T n , β n ) the random Sym(R)-enriched plane tree (T n , β n ) conditioned on having n vertices, page 20

T f n fixpoint subtree corresponding to (T n , β n ), page 20 (T ( ) , β ( ) )
size-biased Sym(R)-enriched tree, page 22 (T (∞) , β (∞) ) local weak limit of the Sym(R)-enriched tree (T n , β n ), page 23 τ [k] plane tree trimmed at height k, page 23 (τ, γ) <k> G-enriched tree trimmed at height k, page 23 G random G-object, page 20 Ĝ random G-object with a bias on the number of fixpoints, page 24 Ḡ random G-object with a bias on the number of non-fixpoints, page 24 Ĥ• = ( Ĥ, u * ) the local limit of (T n , β n ) near a random vertex, page 25 6.1. Random weighted R-enriched trees. The concept of R-enriched trees was introduced by Labelle [START_REF] Labelle | Une nouvelle démonstration combinatoire des formules d'inversion de Lagrange[END_REF], and facilitates the unified treatment of a large variety of tree-like combinatorial structures.

Given a species of structures R, the corresponding species of R-enriched trees A R is constructed as follows. For each finite set U let A R [U ] be the set of all pairs (A, α) with A ∈ A[U ] a rooted unordered tree with labels in U , and α a function that assigns to each vertex v of A with offspring set

M v an R-structure α(v) ∈ R[M v ].
The transport along a bijection σ : U → V relabels the vertices of the tree and the R-structures on the offspring sets accordingly. That is, A R [σ] maps the enriched tree (A, α) to the tree (B, β) with

B = A[σ](A) and β(σ(v)) = R[σ| Mv ](α(v)) for
A R X • R(A R ), (6.1)
as any R-enriched tree consists of a root vertex (corresponding to the factor X ) together with an R-structure, in which each atom is identified with the root of a further R-enriched tree. By Theorem 3.5 it holds that given any species F with an isomorphism F X • R(F), there is a natural choice of an isomorphism F A R . Hence a large variety of combinatorial structures have a natural interpretation as enriched trees.

Given a weighting κ on the species R, we obtain a weighting ω on the species A R given by

ω(A, α) = v∈A κ(α(v)). (6.2)
This weighting is consistent with the isomorphism in (6.1), that is,

A ω R X • R κ (A ω R ). (6.3)
We are going to study the random unlabelled enriched tree ÃR n , drawn with probability proportional to its weight among all unlabelled objects with size n. In the following, we illustrate how this model of random enriched trees generalizes various models of random graphs. The list is of course non-exhaustive and a large variety of other special cases of ÃR n may be found in the literature.

6.1.1. Simply generated Pólya trees. For R = SET, the species A R describes rooted unordered trees. The corresponding unlabelled objects are also called Pólya trees. Given a weight sequence w = (ω k ) k , we may assign weight ω k to each k-sized R-structure. Then ÃR n is the random unordered unlabelled tree such that any Pólya tree A with n vertices gets drawn with probability proportional to v∈A ω d + A (v) , with d + A (v) denoting the outdegree of a vertex v. Note that setting weights to zero allows us to impose arbitrary degree restrictions.

Janson [START_REF] Janson | Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation[END_REF] classified weight-sequences for simply generated plane trees into categories, each characterized by a common asymptotic behaviour. It is natural to pursue a similar classification for simply generated Pólya trees. 6.1.2. Random unlabelled connected rooted graphs with weights on the blocks. The species C of connected graphs admits a decomposition in terms of the species B of graphs that are 2-connected or consist of two distinct vertices joined by an edge. The well-known combinatorial specification

C • X • SET(B (C • )) (6.4)
is illustrated in Figure 2. The isomorphism can be found for example in Harary and Palmer [40, 1.3.3, 8.7.1], Robinson [START_REF] Robinson | Enumeration of non-separable graphs[END_REF]Thm. 4], and Labelle [48, 2.10]. The idea is that in any rooted connected graph, the root-vertex is incident to an unordered set of blocks, where each non-root vertex gets identified with the root of a further rooted connected graph. Equation (6.4) allows us to identify the species C • of rooted connected graphs with SET • Benriched trees. That is, rooted trees, in which each offspring set gets partitioned, and each partition class Q carries a B -structure, that has |Q| + 1 vertices, as the * -vertex receives no label.

Let γ be a weighting on the species B. We may consider the weighting ω on C that assigns weight

ω(C) = B γ(B)
to any graph C, with the index B ranging over the blocks of C. The random graph C ω n drawn from the unlabelled n-sized C • -objects with probability proportional to its ω-weight is distributed like the random unlabelled enriched tree ÃR n for the weighted species R κ = (SET • B ) κ , with κ assigning the product of the γ-weights of the individual classes to any assembly of B -structures.

If all γ-weights are equal either to 0 or 1, we obtain random connected graphs from so called block-classes (or block-stable classes), that is, classes of graphs defined by placing constraints on the allowed blocks. For example, any class of graphs Ex(M) that may be defined by excluding a set M of 2-connected minors is also block-stable. Here a minor of a graph G refers to any graph that may be obtained from G by repeated deletion and contraction of edges. Prominent examples are outerplanar graphs (the class Ex(K 4 , K 2,3 )), that may be drawn in the plane such that each vertex lies on the frontier of the infinite face, and series-parallel graphs (the class Ex(K 4 )), that may be constructed similar to electric networks in terms of repeated serial and parallel composition. These two classes fall under the more general setting of random graphs from subcritical block-classes in the sense of Drmota, Fusy, Kang, Kraus and Rué [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF], which also are special cases of the random graph C ω n .

Figure 3. Decomposition of the class K • for k = 2.

6.1.3. Random unlabelled front-rooted k-trees. Let K denote the species of k-dimensional trees that are rooted at a front of distinguishable * -placeholder vertices. We let K n denote the random unlabelled front-rooted k-tree that gets drawn uniformly at random among all unlabelled K-objects with n hedra. We consider the subspecies K • front-rooted k-trees where the root-front is contained in precisely one hedron, and let K • n be sampled uniformly at random from the unlabelled K-objects with n hedra.

Any element from K may be obtained in a unique way by glueing an arbitrary unordered collection of K • -objects together at their root-fronts. Hence

K SET(K • ).
As illustrated in Figure 3, any K 1 -object may be constructed in a unique way by starting with a hedron H consisting of the root-front and a vertex v, and then choosing, for each front M of H that contains v, a k-tree from K whose root-front gets identified in a canonical way with M . Hence

K • X • SEQ {k} (K).
Combining the isomorphisms yields

K • X • (SEQ {k} • SET)(K • ).
This identifies the species K • as SEQ {k} • SET-enriched trees, and the species K as unordered forest of enriched trees. In particular, K • n corresponds to the random unlabelled enriched tree Ãω n . 6.2. Local convergence of random unlabelled enriched trees. In the following, we let R κ denote an arbitrary weighted species such that the inventory |R[k]| κ is positive for k = 0 and for at least one k ≥ 2. We let A ω R denote the corresponding species of weighted R-enriched trees. The radius of convergence of the ordinary generating series Ãω R (z) will be denoted by ρ. ) and we may proceed with the construction of β in the same way. For each cycle τ = (v 1 , . . . , v t ) of σ(o) having length t ≥ 2 the situation is more complicated. We know that σ permutes the R-enriched fringe subtrees f (A, v i ) cyclically. Hence they are all structurally equivalent, and in fact, by the discussion in Section 3.3, up to isomorphism composed out of isomorphic symmetries (f (A, v i ), σ i ) with

σ i = σ t | f (A,v i ) .
Hence we may proceed with the construction of β as before, by considering the individual symmetries. This process is illustrated in Figure 4. Note that the Sym(R)-enriched tree (T, β) does not contain all information about the symmetry S, but we may reconstruct S up to relabelling from (T, β).

The fixpoints of the automorphism σ form a subtree T f of T . Each fixpoint v has a possibly empty set f (v) of other fixpoints as offspring, and the remaining offspring correspond to a forest F (v) of Sym(R)-enriched fringe subtrees f ((T, β), v i ), which consist of non-fixpoints of σ. We are going to say the triple G(v) := (β(v), f (v), F (v)) is a G-object on the fixpoints f (v) and define |f (v)| to be its size. Formally, G-objects do not correspond to any species, but the analogy is clear, and we may call (T f , (G(v)) v∈T f ) a G-enriched tree.

Similarly, we may define the concept of a G-enriched plane tree, in which the label set of each occurring R-symmetry is required to belong to the collection {[k] | k ≥ 0}. We are going to use the following recursive procedure illustrated in Figure 5 in order to sample random A R -symmetries according to a weighted Boltzmann-distribution. Lemma 6.1 (A coupling of random unlabelled R-enriched trees with random G-enriched trees). For any parameter x > 0 with Ãω R (x) < ∞ consider the following recursive procedure ΓS(x) which draws a random Sym(R)-enriched plane tree (T , β).

1. Start with a root vertex o and draw a random symmetry

β(o) = (R(o), σ(o))
from the set k≥0 Sym(R)[k] such that β(o) gets drawn with probability proportional to

κ(R(o)) |R(o)|! Ãω R (x) σ 1 (o) Ãω 2 R (x 2 ) σ 2 (o) • • • .
Here σ i (o) denotes the number of i-cycles of the permutation σ(o), with fixpoints counting as 1-cycles. 2. For each cycle τ of the permutation σ(o) draw an independent copy (T τ , β τ ) of the recursively called sampler ΓS(x |τ | ). Here |τ | ≥ 1 denotes the length of the cycle. For each atom a of τ make an identical copy (T a , β a ) of (T τ , β τ ).

3. Let k denote the size of the Sym(R)-structure β(o). For each label a ∈ [k] add an edge between the root vertex o and the root of the plane tree T a . The ordering of the offspring set is given by the order on the label set [k]. This defines a plane tree T with root-vertex o. Moreover, for each a ∈ [k] and each vertex v ∈ T a set β(v) := β a (v). This defines a Sym(R)-enriched plane tree (T , β). This procedure terminates almost surely and the resulting Sym(R)-enriched plane tree (T , β) corresponds to a symmetry on the vertex set of the plane tree T . Let ΓZ A ω R (x) denote the result of relabelling this symmetry uniformly at random with labels from the set [n], with n denoting the number of vertices of the tree T . Then for any symmetry (A, σ) from the set k≥0 Sym(A R )[k] it holds that

P(ΓZ A ω R (x) = (A, σ)) = ω(A) x |A| |A|! Ãω R (x) -1 .
Figure 5. The sampler ΓS(x).

If we condition the sampler ΓZ A ω R (x) on producing a symmetry with size n, then any symmetry from Sym(A R )[n] gets drawn with probability proportional to the ω-weight of its A R -object. By the discussion in Section 3.1 it follows that the isomorphism class of this A R -object is distributed like the random unlabelled R-enriched tree ÃR n . Suppose that the radius of convergence ρ of the ordinary generating series Ãω R (z) is positive. As we state below, it holds that Ãω R (ρ) is finite and hence we may consider the random Sym(R)-enriched (T , β) drawn according to the sampler ΓS(ρ). The vertices of T that correspond to fixpoints of the symmetry ΓZ A ω R (ρ) form a subtree T f ⊂ T containing the root. Note that by the discussion in Section 3.3 the fixpoints correspond precisely to the vertices in which the sampler ΓS calls itself with parameter ρ (as opposed to parameter ρ i for some i ≥ 2).

For each vertex v of

T f let G T f (v) = (β(v), f (v), F (v)) denote the corresponding G-object. Moreover, let (T n , β n ), T f n and G T f n (•) = (β n (•), f n (•), F n (•)
) denote the corresponding random variables conditioned on the event |T | = n. Let G be a random variable that is identically distributed to the G-object G T f (o) corresponding to the root o of T f . Moreover, let ξ denote the number of the fixpoints of G and ζ the size of the enriched forest corresponding to the non-fixpoints. Lemma 6.2 (Properties of the coupling with G-enriched trees). We make the following observations.

(1) The radius of convergence ρ of Ãω R (z) is finite, and the sum Ãω R (ρ) is finite as well.

(2) The size of the tree T satisfies

|T | = v∈T f (1 + |F (v)|).
(3) For any Sym(R)-enriched plane tree (T , β ) corresponding to G-objects G 1 , . . . , G it holds that

P((T , β) = (T , β )) = i=1 P(G = G i ).
(4) An arbitrary sequence of G-objects G i = (S i , f i , F i ), i = 1, . . . , corresponds to a Sym(R)enriched tree if and only if

i=1 |f i | = -1 and m i=1 |f i | ≥ m for all 1 ≤ m ≤ -1. Let G i = (S i , f i , F i ) denote independent identical copies of G. Let L denote depth-first- search ordered list L of the G-objects of T f n and |L| its length. Then (L | |L| = ) is distributed like ((G 1 , . . . , G ) | i=1 (1 + |F i |) = n, i=1 |f i | = -1, m i=1 |f i | ≥ m for all 1 ≤ m ≤ -1).
(5) The plane tree T f is distributed like a Galton-Watson tree with offspring distribution ξ having probability generating function

E[z ξ ] = Z R κ (z Ãω R (ρ), Ãω R (ρ 2 ), . . .)ρ/ Ãω R (ρ). (6
) Given T f , the forests (F (v)) v∈T f are conditionally independent. The conditional distribution of each forest depends only on the outdegree d + T f (v). The distribution of the forest size ζ is given by its probability generating function

E[z ζ ] = Z R κ ( Ãω R (ρ), Ãω R ((ρz) 2 ), Ãω R ((ρz) 3 ), . . .)ρ/ Ãω R (ρ).
In a more specific setting, where the random vector (ξ, ζ) has finite exponential moments, even more can be said. Lemma 6.3 (Further properties of the coupling with R-enriched trees in a specific setting). Suppose that ρ > 0 and that the function

E(z, u) = zZ R κ (u, Ãω R (z 2 ), Ãω R (z 3 ), . . .) satisfies E(ρ + , Ãω R (ρ) + ) < ∞ for some > 0. (1) Then the nth coefficient of Ãω R (z) is asymptotically given by [z n ] Ãω R (z) ∼ span(w) ρE z (ρ, Ãω R (ρ)) 2πE uu (ρ, Ãω R (ρ)) ρ -n n -3/2
as n ≡ 1 mod span(w) tends to infinity.

E[ξ] = E u (ρ, Ãω R (ρ)) = ρ (R ) κ • A ω R (ρ) = 1, V[ξ] = E uu (ρ, Ãω R (ρ)) Ãω R (ρ), and E[ζ] = E z (ρ, Ãω R (ρ))ρ/ Ãω R (ρ) -1. Consequently, P(|T | = n) ∼ span(w)n -3/2 1 + E[ζ] 2πV[ξ]
(4) Suppose that at least one R-structure with positive κ-weight has a non-trivial automorphism. Then the lattice spanned by the support of (ξ, ζ) has a 2-dimensional Z-basis B ∈ Z 2×2 , and the covariance matrix Σ of (ξ, ζ) is positive-definite. Set

µ = 1 1 + E[ζ] , σ 2 = det Σ V[ζ](1 + E[ζ]) 3 , and d = | det B| span(w) .
Then, as n ≡ 1 mod span(w) tends to infinity,

√ nP(|T f n | = ) ∼ d σ √ 2π exp(- x 2 2σ
2 ) uniformly for all bounded x satisfying

:= µn + x √ n ∈ n + dZ.
In particular, Properties (1) and ( 2) are an application of results by Bell, Burris and Yeats [START_REF] Bell | Counting rooted trees: the universal law t(n) ∼ Cρ -n n -3/2[END_REF]. The requirement in (4) that R has at least one structure (with positive κ-weight) with non-trivial symmetries is not really a restriction. If it fails, then almost surely |T f n | = n for all n, which makes the analysis of Ãω n even easier.

|T f n | -nµ √ n d -→ N (0, σ 2 ).
ω R satisfies an isomorphism A ω R X • R κ (A ω R ).
The derivative operator satisfies a product rule similar to the product rule for the derivative of smooth functions, see Proposition 3.2. Hence applying the pointing operator yields a weight-compatible isomorphism

A • R A R + X • R (A R ) • A • R .
We may apply Joyal's implicit species theorem [START_REF]Une théorie combinatoire des séries formelles[END_REF]Th. 6] in order to unwind this recursion and obtain an isomorphism

A • R ∞ =0 A ( ) R , A ( ) R = (X • R (A R )) A R
corresponding to the pointed enriched trees ((A, α), v) in which the outer root v has height in the rooted tree A. The correspondence is illustrated in Figure 6. Again, this isomorphism is compatible with the weightings, and we may use it to construct the following sampler illustrated in Figure 7. Lemma 6.4 (A modified random Sym(R)-enriched tree). For any integer ≥ 0 and parameter x > 0 with ( Ã(1) R ) ω (x) < ∞ consider the following recursive procedure ΓS ( ) (x) that samples a random Sym(R)-enriched plane tree (T ( ) , β ( ) ) together with a distinguished vertex r which we call the outer root.

1. If = 0 then return (an independent copy of ) the random enriched plane tree (T , β) from Lemma 6.1 with the outer root being the root-vertex of T . Otherwise, if ≥ 1, then proceed with the following steps. For each atom a of the cycle τ make an identical copy (T a , β a ) of (T τ , β τ ). 4. Draw an independent copy (T b , β b ) of the sampler ΓS ( -1) (x). 5. For each label a ∈ [k + 1] add an edge between the root vertex o and the root of the plane tree T a . The ordering of the offspring set is given by the order on the label set [k + 1]. This defines a plane tree T with root-vertex v. Moreover, for each a ∈ [k + 1] and each vertex u ∈ T a set β(u) := β a (u). This defines an Sym(R)-enriched plane tree (T ( ) , β ( ) ). This procedure terminates almost surely. As described in Section 6.2.1, the resulting Sym(R)enriched plane tree (T ( ) , β ( ) ) corresponds to a symmetry on the vertex set of the tree T ( ) . Let n denote the number of vertices of the tree T ( ) and let ΓZ A ( ) R (x) denote the result of relabelling this symmetry uniformly at random with labels from the set [n]. Then ΓZ A ( ) R (x) satisfies a weighted Boltzmann distribution, that is, for any symmetry ((A, r), σ) from the set ∞ k=0 Sym(A

Start with a root vertex o and draw a

random R -symmetry (R, σ) from k≥0 Sym(R )[k] with probability proportional to κ(R) |R|! Ãω R (x) σ 1 Ãω 2 R (x 2 ) σ 2 • • • .
( ) R )[k] we have that P(ΓZ A ( ) R (x) = ((A, r), σ)) = ω(A) x |A| |A|! Ã( ) R (x) -1 (6.5)
In particular,

P(ΓZ A ( ) R (x) = ((A, r), σ)) = (x R • A ω R (x)) P(ΓZ A ω R (x) = (A, σ)).
Suppose that ρ > 0 and consider the Sym(R)-enriched tree (T ( ) , β ( ) ) generated by the procedure ΓS ( ) (ρ). The path from the root to the distinguished vertex in T ( ) is its spine. If we set = ∞, the above construction yields an infinite but locally finite Sym(R)-enriched tree (T (∞) , β (∞) ) having an infinite spine. We will show that this object, is the local limit weak limit of the random graph Ãω n , if certain conditions are met. In order to formalize our notion of local convergence, we require the concept of trimmed G-enriched trees. For any G-enriched plane tree (τ, γ) and any non-negative integer k let (τ, γ) <k> denote the result of trimming at height k. That is,

(τ, γ) <k> = (τ [k] , (γ(v)) v∈τ [k-1] ),
with τ [k] denoting the plane tree trimmed hat height k. That is, we delete all vertices from τ with height larger than k. In order to simplify notation, we also set (T , β ) <k> := (τ, γ) <k> for the Sym(R)-enriched plane tree (T , β ) corresponding to (τ, γ). Theorem 6.5 (Local convergence of random unlabelled R-enriched trees). Suppose that the ordinary generating series generating series Ãω R (z) has radius of convergence ρ > 0, and that the series

E(z, u) = zZ R κ (u, Ãω R (z 2 ), Ãω R (z 3 ), . . .) satisfies E(ρ + , Ãω R (ρ) + ) < ∞ for some > 0. Then for any sequence k n = o( √ n) of non-negative integers it holds that d TV ((T n , β n ) <kn> , (T (∞) , β (∞) ) <kn> ) → 0.
as n becomes large.

The limit object (T (∞) , β (∞) ) admits a more accessible description in terms of G-enriched trees, that we are going to use in the proof of Theorem 6.5. Let Ĝ denote a random variable that is distributed like the G-object corresponding to the root of T (∞) . Here we do not explicitly distinguish the vertex corresponding the * -vertex of the R -symmetry. Lemma 6.6. Suppose that ρ > 0, E[ξ] = 1 and that (ξ, ζ) has a finite covariance matrix.

(1) The G-object corresponding to the root of T (∞) together with the fixpoint corresponding to the second spine-vertex is distributed like G with a uniformly at random selected marked fixpoint.

(2) The distribution of the limit enriched tree (T (∞) , β (∞) ) may be described as follows. There are normal fixpoints and mutant fixpoints, and we start with a mutant root. Each normal fixpoint receives as G-object an independent copy of G, and each of the fixpoints of this G-object is declared normal. Ever mutant fixpoint receives an independent copy of Ĝ, and one of the corresponding fixpoints is selected uniformly at random and declared mutant, whereas the remaining fixpoints are declared normal.

(3) Let (τ, γ) denote a G-enriched tree with height at least k. Let G 1 , . . . , G t denote the depth-first-search ordered list of the G-objects of τ [k-1] . Then

P((T (∞) , β (∞) ) <k> = (τ, γ) <k> ) = L k (τ ) t i=1 P(G = G i ).
(4) For any G-enriched tree (τ, γ) with γ(v) = (β τ (v), f τ (v), F τ (v)) and any integer k ≥ 0 we set

L k (τ ) = |{v ∈ τ | h τ (v) = k}|, L G k (τ ) = v∈τ hτ (v)=k |F τ (v)|, H G k (τ ) = k i=0 L G i (τ ).
Let ( ξ, ζ) denote the sizes of the fixpoints and non-fixpoints of Ĝ. When (τ, γ) is the G-enriched tree corresponding to (T (∞) , β (∞) ), it holds for all k ≥ 1 that

E[L k (τ )] = k(E[ ξ] -1) + 1 E[|τ [k] |] = k(k + 1)(E[ ξ] -1)/2 + k + 1 E[L G k (τ )] = k(E[ ξ] -1)E[ζ] + E[ ζ] E[H G k (τ ) -|τ [k] |E[ζ]] = (k + 1)(E[ ζ] -E[ζ]) V[H G k (τ ) -|τ [k] |E[ζ]] = k(k + 1)(E[ ξ] -1)V[ζ]/2 + (k + 1)(V[ ζ] + V[ζ]) 6.2.3.
Local convergence around a random root. Inspired by Aldous' approach [START_REF] Aldous | Asymptotic fringe distributions for general families of random trees[END_REF] on fringe subtrees of random trees, we may also treat local convergence with respect to a uniformly at random drawn root of the random unlabelled enriched tree Ãω n in a similar manner. Let v * be an uniformly at random drawn vertex of the tree T n , and let v 0 denote the unique nearest vertex of

T f n . That is, v 0 = v * if v * ∈ T f n ,
and otherwise v 0 is the unique vertex of the fixpoint tree whose G-object contains v * . For any i ≥ 1, let v i denote the i'th predecessor of v 0 in the fixpoint tree T f n , if this predecessor exists. If not, that is, if v 0 has height greater than i in T f n , then set v i = and f ((T n , β n ), v i ) = for some symbol not contained in the set of G-enriched trees.

(For example, we could use the empty set.) For any k ≥ 0 we consider the vector of increasing fringe subtrees

H n [k] := (H n i ) 0≤i≤k := (f ((T n , β n ), v 0 ), . . . , f ((T n , β n ), v k )
). We are going to establish convergence of these random vectors of enriched trees toward extended enriched fringe subtrees of a limit object, which we introduce in the following lemma. Lemma 6.7. Suppose that ρ > 0, E[ξ] = 1 and that (ξ, ζ) has a finite covariance matrix.

(1) Let Ḡ = ( S, f, F) denote the random G-object with distribution given by

P( Ḡ = (S, f, F )) = (1 + |F |)P(G = (S, f, F ))/(1 + E[ζ]).
We define an infinite random G-enriched tree Ĥ in terms of its sequence ( Ĥk ) k≥0 of increasing extended enriched fringe subtrees. The distribution of the fringe subtree tree Ĥk is given as follows. There are normal fixpoints and special fixpoints, and we start with a special root. Each normal fixpoint receives as G-object an independent copy of G, and all fixpoints of this G-object are declared normal. Every special fixpoint with height less than receives an independent copy of Ĝ, and one of the corresponding fixpoints is selected uniformly at random and declared special, whereas the remaining fixpoints are declared normal. A special fixpoint with height receives Ḡ and all fixpoints of this G-object are declared normal.

Then the special vertices of Ĥ form an infinite spine u 0 , u 1 , . . . that grows backwards, with Ĥk = f ( Ĥ, u k ) for all k. We distinguish a point u * that is drawn uniformly at random from the set {u 0 } ∪ F(u 0 ), with F(u 0 ) denoting the set of non-fixpoints of G-object corresponding to the root of Ĥ0 , and set Ĥ• = ( Ĥ, u * ).

(2) For any two G-enriched trees A and A , let Q(A, A ) denote the number of fixpoint sons v of the root of A with f (A, v) = A . For any increasing fringe subtree representation H = (H i ) 0≤i≤k of a G-enriched tree we set

p(H) = k i=1 Q(H i , H i-1 ).
Then p(H) counts the number of fixpoints v at height k in H k with the property, that the extended enriched fringe subtree representation with respect to v is identical to H. (3) Let u be either the root of H 0 or a non-fixpoint of G-object corresponding to the root of H 0 , and let G 1 , . . . , G t be the G-objects corresponding to H k . Then

P( Ĥ[k] = H) = p(H)(1 + E[ζ]) -1 t i=1 P(G = G i ).
(4) For any G-enriched tree (τ, γ) with γ(v) = (β τ (v), f τ (v), F τ (v)) let # f (τ, γ) = |τ | denote its number of fixpoints, and #(τ, γ) = v∈τ (1 + F τ (v)) its total size. Then for any sequence k n = √ nt n of non-negative integers with t n = o(1) it holds with probability tending to one that

# f Ĥkn ≤ nt n and |# Ĥkn -E[ζ]# f Ĥkn | ≤ √ nt n .
We may now establish convergence of the extended enriched fringe subtrees, that will help us to apply our main theorems to specific examples of random discrete structures, in particular random graphs. Theorem 6.8 (Local convergence of random unlabelled R-enriched trees around a random root). Suppose that the ordinary generating series generating series Ãω R (z) has radius of convergence ρ > 0, and that the series

E(z, u) = zZ R κ (u, Ãω R (z 2 ), Ãω R (z 3 ), . . .) satisfies E(ρ + , Ãω R (ρ) + ) < ∞ for some > 0.
Then for any sequence k n = o( √ n) of non-negative integers the increasing fringe subtree sequence H n

[kn] of length k n , corresponding to the uniformly at random drawn vertex v * of (T n , β n ), converges in total variation to the fringe subtree sequence of Ĥ with the same length. That is,

d TV ((H n [kn] , v * ), ( Ĥ[kn] , u * )) → 0. (6.6)
Here u * denotes a random vertex of Ĥ that we defined in Lemma 6.7.

6.3.1.

Patching together discrete metric spaces. We study metric spaces patched together from metrics associated to the vertices of a tree. Let A be a rooted tree. For each vertex v ∈ A let M v denote its offspring set. Let δ be a map that assigns to each vertex v of A a metric δ(v) on the set U v := M v ∪ {v}. This induces a metric d on the vertex vertex set V (A) that extends the metrics δ(v) by patching together as illustrated in Figure 8. Formally, we define this metric as follows. Consider the graph G on the vertex set of A obtained by connecting any two vertices x = y if and only if there is some vertex v of the tree A with x, y ∈ U v and assigning the weight δ(v)(x, y) to the edge. The resulting graph is connected and the distance of any two vertices a and b is defined by the minimum of all sums of edge-weights along paths joining a and b in the graph G.

Suppose that for each finite set U and each R-structure R ∈ R[U ] we are given a random metric δ R on the set U ∪ { * U } with * U denoting an arbitrary fixed element not contained in U . For example, we could set * U := {U }. Let ÃR n = ( Ãn , α n ) denote the random n-sized R-enriched tree drawn with probability proportional to its ω-weight. We construct a random n-element metric space Y n as follows. For each vertex v of ÃR n with offspring set M v let δ n (v) be the metric on the set M v ∪ {v} obtained by taking an independent copy of δ αn(v) and identifying * Mv with v. Let d Yn denote the metric patched together from the family (δ n (v)) v as described in the preceding paragraph.

In order for this to be a sensible model of a random tree-like structure we require the following two assumptions.

(1) We assume that there is a real-valued random variable χ ≥ 0 such that for any R-structure R the diameter of the metric δ R is stochastically bounded by the sum of |R| independent copies χ R 1 , . . . , χ R |R| of χ. (2) For any bijection σ : U → V of finite sets and for any R-structure R ∈ R[U ] we require that the metric δ R[σ](R) is identically distributed to the push-forward of the metric δ R by the bijection σ :

U ∪ { * U } → V ∪ { * V } with σ| U = σ.
Recall that by Lemma 6.3 the radius of convergence ρ of Ãω R (z) is finite, and the sum Ãω R (ρ) is finite as well. Theorem 6.9 (Scaling limits of spaces based on unlabelled enriched trees). Suppose that the ordinary generating series generating series Ãω R (z) has radius of convergence ρ > 0 and that the series

E(z, u) = zZ R κ (u, Ãω R (z 2 ), Ãω R (z 3 ), . . .) satisfies E(ρ + , Ãω R (ρ) + ) < ∞ for some > 0.
Then the rescaled space (Y n , n -1/2 d Yn ) converges weakly to a constant multiple of the (Brownian) continuum random tree T e with respect to the Gromov-Hausdorff metric as n ≡ 1 mod span(w) tends to infinity.

An explicit expression of the scaling constant in Theorem 6.9 is given in the corresponding proof in Section 7.2. It is interesting to note that the local weak limit (T (∞) , β (∞) ) contains some information on the scaling limit, as it is responsible for one of the factors in the scaling factor. We also provide the following sharp tail-bound for the diameter. Theorem 6.10 (Tail bounds for the diameter). Under the same assumptions of Theorem 6.9 there are constants C, c > 0 such that for all n and x ≥ 0 it holds that

P(D(Y n ) ≥ x) ≤ C(exp(-cx 2 /n) + exp(-cx)).
Again it holds that if χ is bounded, then we have the tail-bound

P(D(Y n ) ≥ x) ≤ C exp(-cx 2 /n) for some constants C, c > 0.
The main idea of the proofs of Theorems 6.9 and Theorem 6.10 is that we may use the random Sym(R)-enriched tree (T ( ) , β ( ) ) of Lemma 6.4 to relate for any two vertices x, y ∈ T f n distances d Yn (x, y) and d T f n (x, y) by constant factor. The following basic observation then takes care of the rest. Lemma 6.11. Suppose that ρ > 0 and that the function

E(z, u) = zZ R κ (u, Ãω R (z 2 ), Ãω R (z 3 ), . . .) satisfies E(ρ + , Ãω R (ρ) + ) < ∞ for some > 0.
Then the following assertions hold: (1) There are constants C, c > 0 such that for all n and x ≥ 0

P(max v∈T f n (|f n (v)| + |F n (v)|) ≥ x) ≤ Cn 5/2 exp(-cx).
(2) For any vertex v let D v denote the d Yn -diameter of the subspace {v} ∪ F n (v) ⊂ Y n . Then there are constants C, c > 0 such that for all h ≥ 0 P(max

v∈T f n D v ≥ h) ≤ Cn 5/2 exp(-ch).
(3) We have that

(1 + E[ζ])V[ξ] 2 √ n T f n d -→ T e
in the Gromov-Hausdorff sense as n ≡ 1 mod span(w) tends to infinity.

A result similar to Lemma 6.11 was used in [START_REF] Panagiotou | Scaling limits of random Pólya trees[END_REF] to provide a combinatorial proof for the scaling limit of uniform random Pólya trees (with possible degree restrictions). Theorem 6.9 is more general, as it applies for example to scaling limits of models of random graphs with respect to the first-passage-percolation metric, and its proof is deeper and more involved, as it requires the interplay with the Sym(R)-enriched tree (T ( ) , β ( ) ) of Lemma 6.4 that is related to the local weak limit.

6.4. Applications to random unlabelled rooted connected graphs. Let C denote the class of connected graphs and B its subclass of graphs that are two-connected or a single edge with its ends. Recall that the rooted class C • may be identified with the class of SET•B -enriched trees as discussed in Section 6.1.2. Suppose that we have a weighting γ on the class B, that is, for each B-graph B we are given a weight γ(B) ≥ 0 such that the weights of isomorphic graphs agree. This induces a weighting κ on the species SET • B by setting the weight of a set of graphs to the product of the individual weights. Hence we also have a weighting ω on C given by

ω(C) = B γ B
for all C-objects C, with the index B ranging over all blocks of the graph C. In the following, we study random unlabelled rooted graph C ω n drawn from the unlabelled C • -objects of size n with probability proportional to its ω-weight. This corresponds to the model of random unlabelled enriched trees ÃR n in Section 6.1 for the special case R κ = (SET • B ) κ . Under the premise that the cycle index sums related to the random graph C ω n satisfy Equation (6.7), we establish a local weak limit for the vicinity of the fixed root in Theorem 6.12 and a Benjamini-Schramm limit in Theorem 6. [START_REF] Benjamini | Recurrence of distributional limits of finite planar graphs[END_REF]. In both cases we actually establish total variational convergence of arbitrary o( √ n)-neighbourhoods, which is best-possible in this setting. We also consider the first-passage-percolation metric on the graph C ω n , which is more general than the graph-metric, and establish sharp exponential tail-bounds for the diameter and a Gromov-Hausdorff scaling limit in Theorem 6.14. As a byproduct, we also obtain a bound for the size of the largest 2-connected component.

As an important special case, these Theorems apply to uniform random unlabelled rooted graph from a subcritical block class. This model was studied by Drmota, Fusy, Kang, Kraus and Rué in [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF]Def. 10], and includes uniform random rooted unlabelled cacti graphs, outerplanar graphs, and series-parallel graphs [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF]Thm. 15]. The scaling limit Theorem 6.14 is a strong result in this context and also establishes the correct order of the diameter of this type random graphs.

6.4.1. Local weak limit. The infinite Sym(SET • B )-enriched tree (T (∞) , β (∞) ) from Section 6.2.2 is naturally also a SET • B -enriched tree, and may hence be interpreted as an infinite locally finite random graph Ĉ according to the bijection in Section 6.1.2. Theorem 6.5 yields local weak convergence of the random graph C ω n with respect to neighbourhoods around its fixed root vertex. Theorem 6.12 (Local convergence of random unlabelled graphs). Suppose that the weighted ordinary generating series ( C• ) ω (z) has radius of convergence ρ > 0, and that

E(z, u) = zZ (SET•B ) κ (u, ( C• ) ω (z 2 ), ( C• ) ω (z 3 ), . . .) (6.7) satisfies E(ρ + , ( C• ) ω (ρ) + ) < ∞ for some > 0. Then for any sequence k n = o( √ n) of non-negative integers it holds that d TV (U kn (C ω n ), U kn ( Ĉ)) → 0, (6.8)
and likewise for the graph-metric neighbourhoods V kn (•). Thus, the infinite random graph Ĉ is the local weak limit of the random graph C ω n as n becomes large. Note that this form of convergence is best-possible, as the diameter of C ω n has order √ n by Theorem 6.14, and hence (6.8) fails if the order of k n is comparable to √ n.

6.4.2. Benjamini-Schramm limit and subgraph count asymptotics. The infinite G-enriched tree Ĥ• from Section 6.2.2 may be interpreted as an infinite locally finite random graph Ĉ• according to the bijection in Section 6.1.2. Theorem 6.8 yields Benjamini-Schramm convergence of the random graph C ω n . Theorem 6.13 (Benjamini-Schramm convergence of random unlabelled graphs). Suppose that the weighted ordinary generating series ( C• ) ω (z) has radius of convergence ρ > 0, and that

E(z, u) = zZ (SET•B ) κ (u, ( C• ) ω (z 2 ), ( C• ) ω (z 3 ), . . .)
satisfies E(ρ + , ( C• ) ω (ρ) + ) < ∞ for some > 0. Let v * be a uniformly at random drawn vertex of the random graph C ω n . Then for any sequence

k n = o( √ n) of non-negative integers it holds that d TV (U kn (C ω n , v * ), U kn ( Ĉ•
)) → 0, and likewise for the graph-metric neighbourhoods V kn (•). Thus, the infinite random graph Ĉ• is the Benjamini-Schramm limit of the random graph C ω n as n tends to infinity. Again this form of convergence is best-possible, as the diameter of C ω n has order √ n by Theorem 6.14. Benjamini-Schramm convergent sequences have many nice properties, for example we may apply general results by Kurauskas [46,Thm. 2.1]) and Lyons [START_REF] Lyons | Asymptotic enumeration of spanning trees[END_REF]Thm. 3.2] to deduce laws of large numbers for subgraph count statistics and spanning tree count statistics. 6.4.3. Scaling limit and diameter tail-bounds. We apply our results to first-passage percolation on graphs. Let ι > 0 denote a random variable which has finite exponential moments. Given a connected graph G we may consider the first-passage percolation metric d FPP on G by assigning an independent copy of ι to each edge of G, letting for any two vertices x, y the distance d FPP (x, y) be given by the minimum of all sums of weights along paths joining x and y. We let D FPP (•) and H FPP (•) denote the diameter and height with respect to the d FPP -distance Theorems 6.9 and 6.10 and the fact, that the diameter and height of the CRT are related by

E[D(T e )] = 4 3 E[H(T e )] = 4 3 π 2 ,
readily yield the following result.

Theorem 6.14 (First passage percolation random unlabelled rooted graphs). Suppose that the weighted ordinary generating series has radius of convergence ρ > 0, and that the series

E(z, u) = zZ (SET•B ) κ (u, C•ω (z 2 ), C•ω (z 3 ), . . .)
is finite at the point (ρ + , C•ω (ρ) + ) for some > 0. Then there exists a constant a > 0 such that

(C ω n , an -1/2 d FPP ) d -→ (T e , d Te )
in the Gromov-Hausdorff sense as n ≡ 1 mod span(w) becomes large. Furthermore, there are constants C, c > 0 with

P(D(C ω n , d FPP ) ≥ x) ≤ C exp(-cx 2 /n
) for all n and x ≥ 0. In particular, the rescaled height and diameter converge in the space L p for all p ≥ 1. We have asymptotically

E[D FPP (C ω n )] ∼ 4 3 E[H FPP (C ω n )] ∼ 4 3a πn 2 .
Lemma 6.11 also yields the following result for the size of the largest 2-connected component of the random graph C ω n . Corollary 6.15. There is a constant C > 0 such that the largest block in the random graph C ω n has size at most C log n with probability tending to 1 as n becomes large. Likewise, the maximum degree admits an O(log(n)) bound with high probability.

6.5. Applications to random unlabelled front-rooted k-dimensional trees. We consider the species K of front-rooted k-trees and the subclass K • where the root-front is required to lie in a single hedron. Let K n denote a uniform random unlabelled K-object with n hedra and likewise K • n a uniform random K • -object with n hedra. As discussed in Section 6.1.3, the two species are related by the equations

K SET • K • , K • X • (SEQ {k} • SET)(K • ).
This identifies the random k-tree K • n with the random enriched tree A R n for the special case R = SEQ {k} • SET. The random front-rooted k-tree K n may be interpreted as a random unordered forest of R-enriched trees. We let ρ denote the radius of convergence of K

• (z) = Ãω R (z). Note that Z R (z 1 , z 2 , . . .) = exp(k i=1 ∞z i /i).
Lemmas 6.2 and 6.3 readily yield 0 < ρ < 1 and K

• (ρ) < ∞. Hence Z R ( K• (ρ) + , K• ((ρ + ) 2 ), K• ((ρ + ) 3 )) < ∞
for some > 0. This parallels some arguments from Drmota and Jin [START_REF] Drmota | An asymptotic analysis of labeled and unlabeled k-trees[END_REF], where among other enumerative results the asymptotic number of unlabelled unrooted and rooted k-trees was determined.

6.5.1. Local weak limit. Theorem 6.5 readily yields a local weak limit of the random graph K • n with respect to neighbourhoods of the root-front, or any fixed vertex of the root-front. The limit object is the infinite random k-tree K• that corresponds to the limit Sym(R)-enriched tree (T (∞) , β (∞) ) according to the bijection in Section 6.1.3. The random unlabelled front-rooted k-tree K n may be viewed as a random unlabelled Gibbspartition. By Theorem 4.1 it follows that K n exhibits a giant component of size n + O p (1), and the small fragments converge in total variation toward a Boltzmann limit R that follows a P SET•K • ,ρ distribution. We let K denote the infinite random k-tree obtained by identifying the root-front of K• with the root-front of the front-rooted k-tree corresponding to R according to the bijection in Section 6.1.3. Theorem 6.16 (Local convergence of random unlabelled front-rooted k-trees). For any sequence

k n = o( √ n) it holds that d TV (V kn (K n ), V kn ( K)) → 0.
Thus the infinite random graph K is the local weak limit of the random front-rooted k-tree K n as n becomes large. Here we may interpret V kn (•) as the neighbourhood of the root-front, or of any fixed vertex of the root-front. By exchangeability, it does not matter which we choose.

Note that Theorem 6.16 does not follow directly from the above discussion, as we still need to relate the height of vertices in the G-enriched tree representation with the height in the corresponding k-tree. We provide a detailed justification in Section 7.3. 6.5.2. Benjamini-Schramm limit. The infinite G-enriched tree Ĥ• from Section 6.2.2 may be interpreted as an infinite k-tree K• according to the bijection in Section 6.1.3.

As we are going to argue in detail in Section 7.3, a random vertex in K n lies with high probability in the largest K • -component. Theorem 6.8 together with a large deviation estimate yield Benjamini-Schramm convergence of the random k-tree K • n toward the random graph K• , and hence also Benjamini-Schramm convergence for the largest K • -component of K n . Moreover, within this component, a random vertex is unlikely to lie anywhere near the root. Thus K is also the Benjamini-Schramm limit of the random front-rooted k-tree K n . Theorem 6.17 (Benjamini-Schramm convergence of random unlabelled front-rooted k-trees). Let v * denote a uniformly at random selected vertex of the random unlabelled front-rooted k-tree K n . Then for any sequence of positive integers

k n = o( √ n) it holds that d TV (V kn (K n , v * ), V kn ( K• )) → 0.
Thus K• is the Benjamini-Schramm limit of K n as n becomes large.

6.5.3. Scaling limit. By Theorem 4.1 we know that K n exhibits a giant K • -component of size n + O p [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF]. Hence in order to establish a scaling limit for K n it suffices to study the random k-tree K • n where the root-front lies in a single hedron. In order to establish a scaling limit for K • n we may not apply Theorem 6.9 directly, as the metric of K • n does not fit in the general scheme of random metric spaces considered in Section 6.3. Rather than that, we make direct use of the size-biased G-enriched tree of Lemma 6.4 and the results of Lemma 6.11. Theorem 6.18. There is a constant a k > 0 such that

(K n , a k n -1/2 d Kn ) d -→ (T e , d Te )
in the Gromov-Hausdorff sense as n becomes large.

As a byproduct, we obtain the following properties of the random k-tree K • n . Lemma 6.19. It holds that

(K • n , a k n -1/2 d Kn ) d -→ (T e , d Te ).
Moreover, there are constants C, c > 0 such that for all x ≥ 0 and n ≥ 1

P(D(K • n ) ≥ x) ≤ C exp(-cx 2 /n). 6.6.
Applications to simply generated Pólya trees. Let (κ i ) i∈N be a sequence of nonnegative weights with κ 0 > 0 and κ i > 0 for some i ≥ 2. Hence κ can be seen as a weighting on the species SET. Let d denote the greatest common divisor of the set of all indices i with κ i > 0. For n ≡ 1 mod d large enough we may draw a random Pólya tree τ n having n vertices with probability P(τ n = τ ) proportional to v∈τ κ d + τ (v) for any unlabelled unordered tree τ with size n. This corresponds to the random unlabelled enriched tree ÃR n for R κ = SET κ . We let ρ denote the radius of convergence of the corresponding generating series Ã(z) := Ãω R (z). In the following, we only consider the case where ρ > 0 and Z SET κ ( Ã(ρ) + , Ã((ρ + ) 2 ), . . .) < ∞ (6.9) for some > 0. 6.6.1. Local weak limit. Let τ denote the tree T (∞) for the special case R κ = SET κ . Theorem 6.5 readily yields the following result. Theorem 6.20. If Condition (6.9) is satisfied, then for any sequence

k n = o( √ n) of positive integers it holds that d TV (V kn (τ n ), V kn (τ )) → 0.
Thus, τ is the local weak limit of τ n as n becomes large.

6.6.2. Benjamini-Schramm limit. Let τ • denote the pointed plane tree corresponding to the tree Ĥ• for the case R κ = SET κ . Theorem 6.8 applies directly and yields a Benjamini-Schramm limit for the simply generated Pólya tree τ n .

Theorem 6.21. Suppose that Condition (6.9) holds. Let v * denote a uniformly at random selected vertex of the tree τ n . Then for any sequence

k n = o( √ n) of positive integers it holds that d TV (V kn (τ n , v * ), V kn (τ • )) → 0.
In particular, τ • is the Benjamini-Schramm limit of τ n as n becomes large.

6.6.3. Scaling limit and diameter tail-bound. Another application of Theorems 6.9 and 6.10 is the following scaling limit with a sharp tail-bound for the diameter.

Theorem 6.22 (Scaling limits of simply generated Pólya trees). If Condition (6.9) is satisfied, then there is a constant a > 0 such that

(τ n , an -1/2 d τn ) d -→ (T e , d Te )
with respect to the Gromov-Hausdorff metric as becomes large. Moreover, there are constants c, C > 0 such that for all x ≥ 0 and n it holds that

P(D(τ n ) ≥ x) ≤ C exp(-cx 2 /n).
This is a mild extension of results for uniformly drawn Pólya trees with n vertices and vertex degree restrictions, whose scaling limits were studied in [START_REF] Marckert | The CRT is the scaling limit of unordered binary trees[END_REF][START_REF] Haas | Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees[END_REF][START_REF] Panagiotou | Scaling limits of random Pólya trees[END_REF]].

Proofs of the main results

7.1. Proof of the local convergence of unlabelled enriched trees in Section 6.2.

Proof of Lemma 6.1. As discussed in Section 3.5.3, the rules of Lemma 3.4 concerning the interplay of Boltzmann distributions and operations on species may be used to construct recursive samplers, if the concerning isomorphism satisfies the conditions of Theorem 3.5. This is the case for isomorphism

A ω R X • R κ (A ω R ), which corresponds to the combinatorial specification Y = H(X , Y) with H(X , Y) = X • R κ (Y). Indeed, it holds that H(0, 0) = 0 • R κ (0) = 0 and ∂ 2 H(0, 0) = 0 • (R ) κ (0) = 0.
Thus we may apply the product rule and substitution rule of Lemma 3.4 to construct a recursive procedure that samples according to the P Sym(A ω R ),(x i ) i -Boltzmann distribution. The result is the procedure described in Lemma 6.1, with one important difference. According to Lemma 3.4 we would have to apply Lemma 3.3 for each recursive call to construct an A Rsymmetry out of the R-symmetry and the attached A R -symmetries, and then relabel uniformly at random. Instead of doing this for each recursive call, we skip this step and keep track of all the R-symmetries, yielding the Sym(R)-enriched tree (T , β). As discussed at the beginning of the Section 6.2.1, we may construct the symmetry that corresponds to (T , β) in one step by applying Lemma 3.3 for each of its vertices, starting with the leaves and working our way upwards. Thus (T , β) corresponds to a symmetry on the vertex set of the plane tree T . Moreover, instead of relabelling uniformly at random after each application of Lemma 3.3, we may postpone this step and just relabel the symmetry corresponding to (T , β) once uniformly at random. The result ΓZ A ω R (x) then follows P Sym(A ω R ),(x i ) i -Boltzmann distribution, meaning that for each n ≥ 0 and each symmetry (A, σ) ∈ Sym(A R )[n] it holds that

P(ΓZ A ω R (x) = (A, σ)) = ω(A) x n n! Z A ω R (x, x 2 , . . .) -1 .

By Equation (3.1) we know that

Z A ω R (x, x 2 , . . .) = Ãω R (x)
. This completes the proof.

Proof of Lemma 6.2. As for claim (1), note that the isomorphism Ãω

R X • R κ ( Ãω R ) implies that Ãω R (z) = zZ R κ ( Ãω R (z), Ãω R (z 2 ), . . .).
By assumption, there is an R-structure with size zero and one with size at least two such that both have a positive κ-weight. It follows that there are constants a, b > 0 and k ≥ 2 with the property that for all 0 ≤ x < ρ it holds that

Ãω R (x) ≥ x(a + b Ãω R (x) k
). This implies that lim x↑ρ Ãω R (x) < ∞ and hence, by non-negativity of coefficients, Ãω R (ρ) < ∞. Claims (2) -(6) all follow after a moments consideration from the explicit description of the sampler in Lemma 6.1.

Proof of Lemma 6.3. Claims (1) and (2) follow from a general enumeration theorem by Bell, Burris and Yeats [START_REF] Bell | Counting rooted trees: the universal law t(n) ∼ Cρ -n n -3/2[END_REF]Thm. 28] which implies the asymptotic behaviour of the coefficients of the power series Ãω R (z). Claim (3): The expressions for the moments of ξ and ζ follow from the equations describing the corresponding probability generating functions in Lemma 6.2. In order to verify that E[ξ] = 1, note that by Pringsheim's theorem the function Ãω R (z) cannot be analytically continued in a neighbourhood of ρ, and hence by the implicit function theorem it must hold that the function

H(z, u) := u -E(z, u) satisfies H u (ρ, Ãω R (ρ)) = 0. In other words, E[ξ] = E u (ρ, Ãω R (ρ)) = 1.
(Compare with the proof of [START_REF] Bell | Counting rooted trees: the universal law t(n) ∼ Cρ -n n -3/2[END_REF]Cor. 12].) Claim (4): Let Λ denote the lattice spanned by all differences x-y of vectors that (ξ, ζ) assumes with positive probability. We assumed that there is an R-structure with size zero and positive κ-weight. Its automorphism is the empty map with no cycles at all. Hence P((ξ, ζ) = (0, 0)) > 0, and Λ is actually generated by the support of (ξ, ζ).

We assumed further that at least one R-structure R with positive κ-weight has a non-trivial automorphism group. Hence there are positive numbers a * , b * and c * such that (ξ, ζ) assumes (a * , 0) and (b * , c * ) with positive probability, as these points correspond the trivial and a non-trivial automorphism of R. Hence the lattice Λ contains three points that do not lie on any straight line. Consequently, it has rank 2, that is, Λ Z 2 as abelian group.

Let B ∈ Z 2×2 be a basis of the lattice Λ. As the support of (ξ, ζ) is not contained on a straight line, it follows that the covariance matrix Σ is positive-definite. Let (ξ i , ζ i ) i∈N denote a family of independent copies of (ξ, ζ). By Lemma 6.2 it holds for any positive integer n and that

P(|T | = n, |T f | = ) = P( i=1 (ξ i , ζ i ) = ( -1, n -), m i=1 ξ i ≥ m for all m < ).
Using rotational symmetry and the cycle lemma 5.4, it follows that

P(|T | = n, |T f | = ) = 1 P( i=1 (ξ i , ζ i ) = ( -1, n -)). (7.1)
We know by Claim (1) that if n is larger than some fixed constant, then P(|T | = n) > 0 if and only if n -1 is divisible by span(w). We shall check below that for each such n

{ ∈ Z | ( -1, n -) ∈ Λ} = n + Zd (7.2)
with d = | det B|/span(w). For now, let us assume that (7.2) holds. Let M > 0 be a fixed constant. Then it holds uniformly for all = (1 + E

[ζ])n + x √ n with |x| ≤ M that ∼ n/ 1 + E[ζ] and -1/2 (( -1, n -) -E[(ξ, ζ)]) ∼ (0, -x(1 + E[ζ]) 3/2 ).
The central local limit theorem given in Lemma 5.1 yields that

1 P( i=1 (ξ i , ζ i ) = ( -1, n -)) ∼ (1 + E[ζ])| det B| n 2 √ 2π det Σ exp(- x 2 2σ 2 ). (7.3) with σ 2 = det Σ/(V[ζ](1 + E[ζ]) 3
). By Claim (3) we know that

P(|T | = n) ∼ span(w)n -3/2 1 + E[ζ] 2πV[ξ] .
Using Equation (7.1) it follows that

P(|T f n | = ) ∼ d σ √ 2πn exp(- x 2 2σ
2 ).

The central limit theorem now follows from Equation (7.2), as for any fixed a < b

P(a ≤ |T f n | -n/(1 + E[ζ]) √ n ≤ b) ∼ d √ n x 1 σ √ 2π exp(- x 2 2σ 2 ) ∼ b a 1 σ √ 2π exp(- x 2 2σ 2 ) dx, with the sum index x ranging over [a, b] ∩ ((1 -µ) √ n + Zd/ √ n).
It remains to verify Equation (7.2), which requires careful reasoning, as we have to relate span(w) with the involved lattice. In order to simplify our calculations, we would like to pick a "nice" basis B of Λ. Note that it does not matter for (7.2) which basis of Λ we choose, as for any two bases B 1 and B 2 there is a matrix M ∈ GL 2 (Z) with B 1 = MB 2 , and as det M ∈ {1, -1} it follows that | det B 1 | = | det B 2 |. The inconvenient part is that, contrary to vector spaces, not every linear independent subset of a lattice may be extended to a basis. However, a classical algebraic result states that for any free Z-module M with rank r(M ) and for any submodule N ⊂ M with rank r(N ) there is a Z-basis v 1 , . . . , v r(M ) of M and integers λ 1 , . . . , λ r(N ) such that λ 1 v 1 , . . . , λ k v k is a basis of N . See for example Roman's book [START_REF] Roman | Advanced linear algebra[END_REF]Thm. 6.7], which states this in the more general context of modules over principal ideal domains. If B = (b 1 , b 2 ) is such a basis of Λ for the submodule N := Z(a * , 0) ⊂ Λ (recall that we defined a * at the beginning of the proof, when we showed that Λ has rank 2), then there is an integer λ with λb 1 ∈ Z(a * , 0) . But this implies that the second coordinate of b 1 must be zero, and hence Since det(B) = ac, it remains to check that span(w) = gcd(a, b + c). That is, we show that span(w) is the span of the projection of Λ on the y-axis. The support S of (|T f | -1, |T | -1) is a subset of the lattice Λ . Hence span(w), which is the span of the projection of S to the y-axis, is a multiple of gcd(a, b + c). In order to show equality we need to verify that indeed two successive multiples of gcd(a, b + c) exist that |T | -1 assumes with positive probability. We may do this probabilistically. Let C > 0 be a given constant. By Equation 7.1 and the central local limit theorem given in Lemma 5.1 it follows that there is a positive integer L such that for all ≥ L and all n with (l -1, n -1) ∈ Λ and

B = a b 0 c (7.
-1/2 (( -1, n -) -E[(ξ, ζ)]) ≤ C (7.5) it holds that P(|T | = n, |T f | = ) > 0.
There is a constant c > 0 such that for every n at least c √ n consecutive integers ≥ L exist that satisfy Inequality (7.5). If n -1 is additionally a constant multiple of gcd(a, b + c), then the intersection Γ n of the lattice Λ and the affine space (0, n -1) + Z(1, 0) is non-empty, and hence an affine subspace of rank one, whose span does not depend on n. In particular, Γ n hits the cone (7.5) about a constant fraction of √ n many times. This proves that span(w) = gcd(a, b + c) and concludes the proof of Claim (4).

Proof of Lemma 6.4. The task is to provide a sampler for the species A ( )

R using the isomorphism A ( ) R (X • (R ) κ (A ω R )) A ω R .
Note that for = 0 we have

A (0) R = A ω R and for ≥ 1 it holds that A ( ) R X • (R ) κ (A ω R ) • A ( -1) R
.

Thus for ≥ 1 we may apply the product rule and substitution rule of Lemma 3.4 to construct a procedure that samples according to the P Sym(A ( ) R ),(x i ) i -Boltzmann distribution, employing a

P Sym(A ( -1)

R

),(x i ) i -distributed symmetry, which we may sample by a recursive call to the sampler for -1.

The result is essentially the procedure described in Lemma 6.4, but we make some modifications. According to Lemma 3.4 we would have to apply Lemma 3.3 to construct an A R -symmetry out of the R -symmetry, the attached A R -symmetries, and the A ( -1) R -symmetry, and relabel uniformly at random afterwards. Instead of doing this for each call, we skip this step and keep track of all the R -symmetries. Also, instead of taking A R -symmetries directly, we use the Sym(R)-enriched tree (T , β) from Lemma 6.4. This yields the Sym(R)-enriched tree (T ( ) , β ( ) ).

As discussed at the beginning of the Section 6.2.1, we may construct the symmetry that corresponds to (T ( ) , β ( ) ) in one step by applying Lemma 3.3 for each of its vertices, starting with the leaves and working our way upwards. If we additionally relabel uniformly at random, the resulting symmetry ΓZ A ( )

R follows a P Sym(A ( ) R ,(x i ) i -distribution.
We defined A ( ) R as a subspecies of the species of pointed R-enriched trees. In particular, for all n ≥ 0 and any symmetry ((A, r), σ) ∈ Sym(A ( ) R ) we have that (A, σ) is an A ω R -symmetry and r is a fixpoint of the automorphism σ. It follows from the definition of the Boltzmann distributions and Ã( )

R (x) = (x (R ) κ • A ω R (x)) Ãω R (x) that P(ΓZ A ( ) R (x) = ((A, r), σ)) = ω(A) x |A| |A|! Ã( ) R (x) -1 = (x (R ) κ • A ω R (x)) -P(ΓZ A ω R (x) = (A, σ)).
Proof of Lemma 6.6. Claim (1): By Lemma 6.4, the R-symmetry ( R, σ) of Ĝ follows, up to relabeling, a weighted Pólya-Boltzmann distribution for the species (R ) κ with parameter Ãω R (ρ).

It makes no difference whether we distinguish the vertex corresponding to the * -fixpoint, or a uniformly at random drawn fixpoint, as the results are identically distributed. By the discussion in Section 3.2 it holds that

Z (R ) κ (s 1 , s 2 , . . .) = ∂ ∂s 1 Z R κ (s 1 , s 2 , . . .).
Hence, for any R-symmetry (R, σ) with a marked fixpoint u, the probability that ( R, σ) = (R, σ) and that precisely the fixpoint u gets marked, is simply given by the probability that a Pólya-Boltzmann distributed R-symmetry with parameter Ãω R (ρ) equals (R, σ). Consequently, for any G-object G with a marked fixpoint u the probability that Ĝ assumes G and that precisely the vertex u is marked is given by P(G = G).

Claim (2): This is a reformulation of Lemma 6.4 in terms of G-enriched trees. Claim (3): The event (T (∞) , β (∞) ) <k> = (τ, γ) <k> corresponds to precisely L τ (k) different outcomes of the first k -1 levels, depending on which leaf of τ [k] the spine of the fixpoint tree (T (∞) ) f is supposed to pass through. By Claim (1), each of these events is equally likely with probability t i=1 P(G = G i ). Claim (4): The k + 1-th level of (T (∞) , β (∞) ) interpreted as G-enriched tree is obtained by taking for each fixpoint of the k-th level an independent copy of G, except for the unique distinguished fixpoint, which receives an independent copy of Ĝ. This yields

E[L k (τ )] = (E[L k-1 (τ )] -1)E[ξ] + E[ ξ] = . . . = k(E[ ξ] -1) + 1, E[|τ [k] |] = E[L 0 (τ ) + . . . + L k (τ )] = k(k + 1)(E[ ξ] -1)/2 + k + 1, E[L G k (τ )] = (E[L k ] -1)E[ζ] + E[ ζ] = . . . = k(E[ ξ] -1)E[ζ] + E[ ζ], E[H G k (τ ) -|τ [k] |E[ζ]] = k i=0 (E[L G i (τ )] -E[L i (τ )]E[ζ]) = (k + 1)(E[ ζ] -E[ζ]).
For the variance, note that

V[H G k (τ ) -|τ [k] |E[ζ]] = E[(D 0 + . . . D k ) 2 )] with D i := L G i (τ ) -L i (τ )E[ζ] -E[ ζ] + E[ζ] satisfying E[D i | L i (τ ) = ] =
0 for all . In particular, for all i < j,

E[D i D j | (τ [k] , (γ(v)) v∈τ [k-1] )] = D i E[D j | L j (τ )] = 0.
It also holds that

E[D 2 i | L i (τ )] = L i (τ )V[ζ] + V[ ζ], and consequently V[H G k (τ ) -|τ [k] |E[ζ]] = k i=0 E[D 2 i ] = k i=0 (E[L i (τ )]V[ζ] + V[ ζ]) = k(k + 1)(E[ ξ] -1)V[ζ]/2 + (k + 1)(V[ ζ] + V[ζ]).
Proof of Theorem 6.5. Let E denote the countably infinite set of all G-enriched plane trees and set

E k = {A <k> | A ∈ E}.
We have to show that lim n→∞ sup

H⊂E kn |P((T n , β n ) <kn> ∈ H) -P((T (∞) , β (∞) ) <kn> ∈ H)| = 0. (7.6)
Recall that for any G-enriched tree (τ, (G τ (v)) v ) with G τ (v) = (β τ (v), f τ (v), F τ (v)) and any integer k ≥ 0 we set

L k (τ ) = |{v ∈ τ | h τ (v) = k}|, L G k (τ ) = v∈τ hτ (v)=k |F τ (v)|, and H G k (τ ) = k i=0 L G i (τ ).
By assumption, there is a sequence t n → 0 with k n = √ nt n . We may without loss of generality assume that k n tends to infinity. For any C > 0 and all k and n we define with foresight the set E C,k,n of all (τ, γ) ∈ E k satisfying P((T (∞) , β (∞) ) <k> = (τ, γ)) > 0 and

1 ≤ L k (τ ) ≤ C(nt n ) 1/2 , |H G k-1 (τ ) -|τ [k-1] |E[ζ]| ≤ C(nt n ) 1/2 , |τ [k-1]
| ≤ nt n . Using Markov's and Chebyshev's inequalities and the expressions of the moments in Lemma 6.6, it follows that there is a constant C such that

lim n→∞ P((T (∞) , β (∞) ) <kn> ∈ E C,kn,n ) = 1. (7.7)
Hence, if we verify (7.6) with the index H ranging only over all subsets of E C,kn,n , then (7.7) implies that

lim n→∞ P((T n , β n ) <kn> / ∈ E C,kn,n ) = 1 (7.8)
and consequently (7.6) already holds with the index ranging over all subsets of E kn . So the only thing that is left to show is that (7.6) holds for H ⊂ E C,kn,n . That is, we have to verify that for any > 0 it holds for large enough n that sup

H⊂E C,kn,n |P((T n , β n ) <kn> ∈ H) -P((T (∞) , β (∞) ) <kn> ∈ H)| ≤ . (7.9)
Let B, Σ, µ, σ and d = | det B|/span(w) be as in Lemma 6.3. We have shown in this Lemma that, as n ≡ 1 mod span(w) tends to infinity,

√ nP(|T f n | = ) ∼ d σ √ 2π exp(- x 2 2σ
2 ) (7.10) uniformly for all bounded x with

:= µn + x √ n ∈ n + dZ. Moreover, |T f n | -nµ √ n d -→ N (0, σ 2 )
and for any 1 > 0 there is a constant M > 0 such that for all n

P(|T f n | / ∈ I n ) ≤ 1 with I n := (n + dZ) ∩ [n/(1 + E[ζ]) -M √ n, n/(1 + E[ζ]) + M √ n].
Hence the expression in (7.9) may be bounded by

1 + sup (τ,γ)∈E C,kn,n P((T n , β n ) <kn> = (τ, γ), |T f n | ∈ I n ) P((T (∞) , β (∞) ) <kn> = (τ, γ)) -1 . (7.11) Let (τ, γ) ∈ E C,kn,n and let G i = (R i , f i , F i ), 1 ≤ i ≤ t be the depth-first-search ordered list of its G-objects. We set (h, H) := t i=1 (|f i |, |F i |). Moreover, let G i = (R i , f i , F i
) denote a family of independent copies of the random G-enriched tree G. For each G-enriched plane tree G set π G = P(G = G). By Lemma 6.2 it follows that for all the probability P((T , β) <kn> = (τ, γ),

|T f | = ) is given by π G 1 • • • π Gt P( i=t+1 (|f i |, |F i |) = ( -1 -h, n --H), m i=t+1 f i ≥ m -h for all 1 ≤ m < ).
Using rotational symmetry and the Cycle Lemma 5.4, this may be simplified further to

π G 1 • • • π Gt h -t + 1 -t P( i=t+1 (|f i |, |F i |) = ( -1 -h, n --H)).
The tree τ has precisely h -t + 1 many leaves with height k and thus Lemma 6.6 implies that

P((T (∞) , β (∞) ) <kn> = (τ, γ)) = π G 1 • • • π Gt (h -t + 1). It holds uniformly for (τ, γ) ∈ E C,kn,n and = µn + x √ n ∈ I n that -1/2 |( -1 -h, n --H) -( -t)E[(ξ, ζ)]| ∼ (0, -x (1 + E[ζ]) 3/2 )
as n becomes large. Hence, as -t ∼ , we may apply the bivariate Central Local Limit Theorem 5.1 to obtain

1 -t P( i=t+1 (|f i |, |F i |) = ( -1 -h, n --H)) ∼ (1 + E[ζ])| det B| n 2 √ 2π det Σ exp(- x 2 2σ 2 ).
By Lemma 6.3 we know that

P(|T | = n) ∼ span(w)n -3/2 1 + E[ζ] 2πV[ξ] .
It follows that uniformly for all (τ, γ) ∈ E C,kn,n

P((T n , β n ) <kn> = (τ, γ), |T f n | ∈ I n ) P((T (∞) , β (∞) ) <kn> = (τ, γ)) ∼ d √ n ∈In 1 σ √ 2π exp(- x 2 2σ 2 ) ∼ M -M 1 σ √ 2π exp(- x 2 2σ 2 ) dx.
Taking 1 = /2 and M sufficiently large it follows that the bound (7.11) is smaller than for sufficiently large n. This completes the proof.

Proof of Lemma 6.7. Claims (1) and (2) are straight-forward. For Claim (3), note that the event Ĥ[k] = H [k] means that Ĥk = H k , and that u 0 lies at one of the p(H) many locations, and that u * lies in precisely the location in {u 0 } ∪ F (u 0 ) that corresponds to u, with F (u 0 ) denoting the forest of non-fixpoints of the G-object corresponding to u 0 . Let G 1 , . . . , G t denote the depth-first-search ordered list of the G-objects G i = (S i , f i , F i ) of H k and let G 1 , . . . , G 2 be the segment that corresponds to H 0 . For any G-object G = (S, f, F ) with a marked fixpoint v from f , the probability for Ĝ = ( Ŝ, f , F ) to assume G and that a uniformly at random drawn fixpoint of f equals v is given by

P( Ĝ = G)|f | -1 = P(G = G).
Likewise, if we distinguish a vertex v from { * } F , then the probability for Ḡ = ( S, f, F) to assume G and that a uniformly at random drawn vertex from { * } F equals v is given by

P( Ḡ = G)(1 + |F |) -1 = P(G = G)(1 + E[ζ]) -1 . Thus P(( Ĥ[k] , u * ) = (H, u)) = p(H)P(G = G 1 )(1 + E[ζ]) -1 i = 1 P(G i = G i ).
For Claim (4), let us start with the fixpoints. By assumption, there is a sequence t n → 0 such that k n = t n √ n → ∞. For any integer m ≥ 0 let S m denote the sum of m independent copies of the size of the ξ-Galton-Watson tree T f . The number of fixpoints # f Ĥk is given by the sum of

# f Ĥ0 (d) = 1 + S | f| .
and the independent differences

# f Ĥi -# f Ĥi-1 (d) = S | f|-1 . Consequently, # f Ĥk (d) = 1 + S M k with M k = | f| + k i=1 ( ξi -1
) and ( ξi ) i≥1 denoting a family of independent copies of | f|. By a general result for the size of Galton-Watson forests, there is a constant C > 0 such that

P(S m ≥ x) ≤ Cmx -1/2
P(S M k ≥ x) ≤ CE[M k ]x -1/2 = C(E[| f|] + k(E[ ξ] -1))x -1/2 .
Setting x = nt n -1 and k = k n , it follows that # f Ĥkn ≤ nt n with probability tending to one as n becomes large.

For the second statement, let R m denote the sum of m independent copies of

|T |-(1+E[ζ])|T f |. The difference # Ĥk -(1 + E[ζ])# f Ĥk is given by the sum of # Ĥ0 -(1 + E[ζ])# f Ĥ0 (d) = | F| -E[ζ] + R | f| and the independent differences # Ĥi -# Ĥi-1 -(1 + E[ζ])(# f Ĥi -# f Ĥi-1 ) (d) = | F| -E[ζ] + R | f|-1 , i = 1 . . . k. Consequently, # Ĥk -(1 + E[ζ])# f Ĥk (d) = | F| -E[ζ] + k i=1 ( ζi -E[ζ]) + R M k (7.12) with ζi denoting independent copies of | F|. Markov's inequality implies that for k = k n || F| -E[ζ] + kn i=1 ( ζi -E[ζ])| ≤ √ nt n /2 (7.13)
with probability tending to one as n becomes large.

It remains to show that |R M kn | ≤ √ nt n /2 with probability tending to one. If ξ and ζ were independent, then this would be rather simple. But, as this is not necessarily the case, it requires a bit of effort. We may write

|T | -(1 + E[ζ])|T f | = ∞ i=0 D i with D i = L G i (T f ) -L i (T f )E[ζ]. (7.14)
The sum is finite, as D i = 0 for i > H(T f ). Since

P(H(T f ) ≥ h) ∼ 2/(V[ξ]h)
as h becomes large, it follows that the probability for the maximum height of m independent copies of T f to be less than k n / √ t n is given by 1

- (1 + o(1))2 √ t n V[ξ]k n m , (7.15) with the o(1) term not depending on m. As E[M kn ] ∼ k n (E[ ξ] -1) and V[M kn ] = k n V[ ξ], it follows by Chebyshev's inequality that |M kn -k n | ≤ k 3/4 n
with probability tending to one. Hence Expression (7.15) implies that the probability for the maximum height of M kn independent copies of T f to be smaller than k n / √ t n tends to one as n becomes large. Equation (7.14) hence implies for all x that

P(|R M kn | ≥ x) ≤ o(1) + P(|U 1 + . . . + U kn | ≥ x) (7.16)
with the U j denoting independent copies of kn/ √ tn i=0 D i . We aim to apply Chebyshev's inequality again, and hence compute the expected value and variance of the U j . It holds for all i and that

E[D i | L i (T f ) = ] = E[ j=1 ζ j -E[ζ]] = 0, with (ζ j ) j denoting a family of independent copies of ζ. Consequently, for all k E[ k i=0 D i ] = 0 and V[ k i=0 D i ] = k i=0 E[D 2 i ] + 2 0≤i<j≤k E[D i D j ].
For all 0 ≤ i < j it holds that

E[D i D j | ((T f ) [j] , (β(v)) v∈(T f ) [j-1] ] = D i E[D j | L j (T f )] = 0, because for all E[D j | L j (T f ) = ] = E[ r=1 ζ i -E[ζ]] = 0.
Clearly it also holds that

E[D 2 j | L j (T f ) = ] = V[ζ]. Hence, V[ k i=0 D i ] = V[ζ]E[ k i=0 L i (T f )] = (k + 1)V[ζ]. Setting k = k n / √
t n , we may thus apply Chebyshev's inequality to (7.16) and obtain

P(|R M kn ≥ √ nt n /2) ≤ o(1) + k n (k n / √ t n + 1)V[ζ] nt n /4 = o(1).
Together with (7.12) and (7.13) this implies that

|# Ĥkn -(1 + E[ζ])# f Ĥkn | ≤ √ nt n
with probability tending to one as n becomes large.

Proof of Theorem 6.8. For any k, let E k denote the set of pairs (H, u) where H = (H i ) 0≤i≤k is a representation of a G-enriched tree as sequence of increasing enriched fringe subtrees, and u is either the root of H 0 or an element of the non-fixpoints of the G-object corresponding to the root of H 0 . We need to show that lim n→∞ sup

H⊂E kn |P((H n [kn] , v * ) ∈ H) -P(( Ĥ[kn] , u * ) ∈ H)| = 0. (7.17)
By assumption, there is a sequence t n → 0 such that k n = √ nt n . We define the subset In order to show this, we first exert some control over the number of fixpoints in (T n , β n ). Let B, Σ, µ and σ be as in Lemma 6.3. If follows from this Lemma that, as n ≡ 1 mod span(w) tends to infinity,

E k,n = {((H i ) 0≤i≤k , u) ∈ E k | # f H k ≤ nt n , |#H k -(1 + E[ζ])# f H k | ≤ √ nt n }. Lemma
√ nP(|T f n | = ) ∼ d σ √ 2π exp(- x 2 2σ
2 )

The sum j 1 J j is invariant under cyclic permutations of the list (G 1 , . . . , G ). Hence the Cycle Lemma 5.4 yields

E[ j=1 J n j , |T f n | = ] = P(|T f n | = )E[ j=1 J j | i=1 (|f i |, |F i |) = ( -1, n -)].
Conditioned on this simpler event, the J j are all identically distributed. Hence

E[ j=1 J n j , |T f n | = ] = P(|T f n | = )E[J 1 | i=1 (|f i |, |F i |) = ( -1, n -)].
Setting π G = P(G = G) for all G-objects G, it follows that

E[J 1 , i=1 (|f i |, |F i |) = ( -1, n -)] = π G 1 • • • π Gt P( i=t+1 (|f i |, |F i |) = ( -1 -t, n -#H k )).
It holds uniformly for (H, u) ∈ E kn,n and = µn

+ x √ n ∈ I n that -1/2 |( -1 -t, n -#H k ) -( -t)E[(ξ, ζ)]| ∼ (0, -x (1 + E[ζ]) 3/2 )
as n becomes large. Hence, as -t ∼ , we may apply the multivariate central local limit theorem 5.1 to obtain

P( i=t+1 (|f i |, |F i |) = ( -1 -t, n -#H k )) ∼ | det B| n √ 2π det Σ exp(- x 2 2σ 2 ).
Likewise, the probability P( i=1

(|f i |, |F i |) = ( -n -))
has precisely the same asymptotic order. It follows from Equation (7.22) that

P(H n [k] = H, |T f n | ∈ I n ) ∼ p(H)π G 1 • • • π Gt ∈In n P(|T f n | = ). Since /n ∼ (1 + E[ζ]) -1 and P(|T f n | / ∈ I n ) ≤ 1 it follows that uniformly for (H, u) ∈ E kn,n P(H n [k] = H, |T f n | ∈ I n ) p(H)(1 + E[ζ]) -1 π G 1 • • • π Gt -1 ≤ 1 (7.23)
for n large enough. Setting 1 = /2, Inequality (7.23) and Lemma 6.7 imply that the bound in (7.19) is smaller than for large enough n. This verifies (7.18) and hence the proof is complete. 7.2. Proofs of the scaling limits and diameter tail bounds in Section 6.3.

Proof of Lemma 6.11. Claim (1): Let x ≥ 0 be arbitrary and let E denote the event that there is a vertex

v ∈ T f with |f (v)| + |F (v)| ≥ x. It follows from Claim (1) that P(|T | = n) = [z n ] Ãω R (ρz)/ Ãω R (ρ) = Θ(n -3/2 ) and hence P(E | |T | = n) = O(n 3/2 )P(E, |T | = n). By Lemma 6.2, the probability P(E, |T | = n) is given by P(∃ ≤ n : max(ξ 1 + ζ 1 , . . . , ξ + ζ ) ≥ x, i=1 ξ i = -1, i=1 (1 + ζ i ) = n, ∀m < : m i=1 ξ i ≥ m),
with (ξ i , ζ i ) i∈N denoting a list of independent copies of (ξ, ζ). We are not interested in precise asymptotics here and hence bound this very roughly by

P(E, |T | = n) ≤ P(max(ξ 1 + ζ 1 , . . . , ξ n + ζ n ) ≥ x) ≤ nP(ξ + ζ ≥ x).
As (ξ, ζ) has finite exponential moments, it follows that P(E, |T | = n) ≤ Cn 5/2 exp(-cn) for some constants C, c > 0 that do not depend on n.

Claim (2):

We may form a random metric space Y by constructing a metric d Y on the vertex set of ΓS(ρ) by patching together independent copies of the metrics δ R just as in the construction of the metric space Y n . Hence Y n is distributed like the space Y conditioned on having size n. For any vertex v of the fixpoint tree T f let D v denote the d Y -diameter of the subspace {v} ∪ F (v) ⊂ Y. Given h ≥ 0 let E denote the event that D v ≥ h for at least one vertex v ∈ T f . Using Claim (1) it follows that ( * )

P(E | |Y| = n) = O(n 3/2 )P(E , |Y| = n) = O(n 5/2 )P(D o ≥ h)
with o denoting the root of the fixpoint tree T f . By assumption, for any vertex u ∈ F (o), the distance d Y (o, u) is bounded by the sum of e d + T (e) many independent copies of a real-valued random variable χ ≥ 0 having finite exponential moments, with the sum index e ranging over all ancestors of the vertex u in the tree T . Clearly we have that

P(D o ≥ h) ≤ ∞ k=0 P(|F (o)| = k)kP(χ 1 + . . . + χ k ≥ h/2)
with (χ i ) i∈N a family independent copies of χ. Moreover,

P(|F (o)| = k) = P(ζ = k) = O(γ k 1 )
for some constant 0 < γ 1 < 1. By the deviation inequality given in Lemma 5.3 it follows that there are constants a, b > 0 such that γ k 1 P(χ 1 + . . . + χ k ≥ h/2) ≤ 2e -ak-bh for all k and h. Hence

P(D o ≥ h) = O(γ h
2 ) for some constant 0 < γ 2 < 1. Hence Equality ( * ) implies that

P(E | |Y| = n) = O(n 5/2 )γ h 2 and we are done. Claim (3): Set t := (1 + E[ζ])σ/2 with σ 2 = V[ξ]. Let g : K • → R denote a
Lipschitzcontinuous, bounded function defined on the space of isometry classes of pointed compact metric spaces. Note that T f n conditioned on having size is distributed like T f conditioned on having size . Hence it is distributed like a ξ-Galton-Watson tree conditioned on having vertices, which we denote by T . It follows from claim ii) that

E[g(tT f n / √ n)] = o(1) + E[g(tT / √ n)]P(|T f | = )
with the sum index ranging over all integers ≡ 1 mod span(w) contained in the interval

(1 ± n -s ) n 1+E[ζ] . Since g is Lipschitz-continuous, we have that |E[g(tT / √ n)] -E[g(σT /(2 √ ))]| ≤ a n, E[D(T )/ √ ]
for some constants a n, with sup (a n, ) → 0 as n ≡ 1 mod span(w) tends to infinity. and we are done. Let s > 1 and t > 0 be arbitrary constants and set s n = log(n) s and t n = n t . Let > 0 be given and let E 1 denote the event that there exists a fixpoint v ∈ T f n and an ancestor u of v with the property that holds with high probability. Since we may choose arbitrarily small, and D(T f n )/ √ n converges in distribution (to a multiple of the diameter of the CRT), it follows that d GH (Y n , E[η]T f n ) → 0 in probability and we are done.

For each finite subset U ∈ N and each R-structure R ∈ R[U ] let (δ i R ) i∈N 0 be a family of independent copies of the metric δ R . Given a A R -symmetry S = ((T, α), σ) with label set [k] for some k ≥ 0 we may form the family (δ S (v)) v∈T of random metrics by traversing bijectively the vertices of T in ascending order 1, 2, . . . k and assigning to each vertex v the "leftmost" unused copy from the list (δ 1 α(v) , δ 2 α(v) , . . .). The metrics can be patched together to a metric d S on the vertex set [k] of the tree T just as described in Section 6.3.

We may assume that all random variables considered so far are defined on the same probability space and that the metric d Yn of Y n coincides with the metric d Zn with Z n denoting the sampler ΓZ A ω R (ρ) conditioned on having size n. Given the family (δ i R ) R,i let H ⊂ ∞ k=0 Sym(A R )[k] denote the finite set symmetries of size n such that the event E 1 takes place if and only if Z n ∈ H. By the definition of the event E 1 for any symmetry S = ((T, α), σ) ∈ H we may choose a fixpoint v S of σ having the property that there exists an ancestor u in the tree T with d T (u, v S ) ≥ s n and d S (u, v S ) /

∈ (1 ± )E[η]d T (u, v).

Let S denote the height h T (v S ). Note that since v S is a fixpoint, the tupel (T, α, v S , σ) is a A

( S )
R -symmetry. By Lemma 6.3 the probability for the sampler ΓZ A ω R (ρ) to have size n is Θ(n -3/2 ) and we have that ρ R • A ω R (ρ) = 1. Hence Equation (6.5) implies that the conditional distribution of the event E 1 given (δ i R ) R,i equals -distance between spine vertices v i and v j is distributed like the sum η 1 + . . . + η |i-j| of independent copies (η i ) i of η. We know that η has finite exponential moments and hence by the deviation inequality in Lemma 5.3 the bound ( * ) converges to zero as n ≡ 1 mod span(w) tends to infinity. Thus with high probability E 1 does not hold. By the same arguments we may bound the probability for the event E 2 by Θ(n 3/2 ) n =1 min(sn, ) k=1 P(η 1 + . . . + η k ≥ t n ) which also converges to zero. This concludes the proof.

Proof of Theorem 6.10. It suffices to show that there are constants C, c, N > 0 such that for all n ≥ N and h ≥ √ n we have that P(H(X n ) ≥ h) ≤ C(exp(-ch 2 /n) + exp(-ch)).

For any fixpoint v ∈ T f n set (v) = u d + Tn (u) with the sum index u ranging over all ancestors of the vertex v in the plane tree T f n . Note that we are summing up the outdegrees in the tree T n and not in the tree T f n . Moreover, for any vertex y ∈ T n let v y denote its closest fixpoint, that is, v y = y if y is a fixpoint and otherwise v y is the unique vertex with y ∈ F n (v y ). If y has height If s is sufficiently small, then it follows that there are constants C 3 , c 3 > 0 such that P(E h 3 ) ≤ C 3 exp(-c 3 h) for all n and h ≥ √ n. Thus there exist constants C, c > 0 with

P(E 2h ) ≤ i P(E h i ) ≤ C(exp(-ch 2 /n) + exp(-ch))
for all n and h ≥ √ n. This concludes the proof.

7.3. Proofs concerning the applications.

7.3.1. Random weighted graphs. As argued in Section 6.4, Theorems 6.12, 6.13 and 6.14 are special cases of the more general results we established in Sections 6.2 and 6.3.

7.3.2.

Random front-rooted k-dimensional trees. We start with global geometric properties, as some intermediate results in there will also be useful in the study of the local properties.

Proof of Theorem 6.18. By Theorem 4.1 it follows that the largest K • -component of the random front-rooted k-tree K n has size n + O p (1). Hence Lemma 6.19 readily implies that K n converges toward the CRT after rescaling by the same factor as for K • n . Proof of Lemma 6.19. The random front-rooted k-tree K • n corresponds to the random enriched tree ÃR n for R = SEQ {k} • SET. Hence our framework applies. We first show a tail-bound for the diameter. By the bijection discussed in Section 6.1.3, we know that the distance between any vertex in (T n , β n ) and its offspring is always 1, as the two vertices are also joined by an edge in the corresponding k-tree. Let √ n ≤ x ≤ n be given. If H(K • n ) ≥ x, then it follows that H(T n ≥ x). (Here we define the height with respect to the vertex that corresponds to the root of T n .) Hence H(T f n ) ≥ x/2 or |F (v)| ≥ x/2 for some v ∈ T f n . Let us denote these events by E 1 and E 2 . Lemma 6.11 states that there are constants C 1 , c 1 > 0 such that uniformly for all n and non-negative x P(max Thus, there are constants C 4 , c 4 > 0 such that P(H(K • n ) ≥ x) ≤ P(E 1 ) + P(E 2 ) ≤ C 4 exp(-c 4 x 2 /n) for all n and all √ n ≤ x ≤ n. It is clear that, by possibly adjusting the constants involved, such an inequality also holds for all x ≥ 0. This verifies the exponential tail-bound for the diameter of the k-tree K • n . It remains to establish the scaling limit. Inequality (7.24) implies that with high probability all vertices v ∈ T f n have the property that the number of vertices in the forest F (v) is at most O(log(n)). This implies that the (pointed) Gromov-Hausdorff distance between the k-tree K • n and the subspace corresponding to the vertices of the fixpoint tree T f n is with high probability at most O(log n). Consequently, it suffices to show that there is a constant a k > 0 such that this subspace rescaled by a k / √ n converges toward the continuum random tree.

We are going to bound the p to show that the bound in (7.31) converges to zero. In order to simplify the calculations, let u denote any fixed vertex of the * -place-holder root-front of the k-tree corresponding to ΓZ for all and it suffices to study the deviation of d from b k . We are going to exploit properties of the bijection in Section 6.1.3 to take a Markov chain approach. Consider the set M 0 consisting of all k unlabelled vertices. The vertex v 1 is incident to v 0 and to a k -1-element subset S 0 ⊂ M 0 . By the construction in Lemma 6.4 each (k -1)-element subset of M 0 is equally likely. The distance of v 1 to u is given by

d 1 = 1 + min v∈S 0 d(u, v)
with d(•, •) denoting the k-tree distance. This follows from the fact that M 0 ∪{v 0 } is a (k+1)-clique.

Setting M 1 = {v 0 } ∪ S 0 , the distance of v 2 to u is again given by

d 2 = 1 + min v∈S 1 d(u, v)
with S 1 ⊂ M 1 denoting the (k -1)-element subset of M 1 that is incident with v 2 . Here each (k -1)-element subset of M 1 is (conditionally) equally likely. We may continue this construction, yielding sequences S 0 , . . . , S -1 and M 0 , . . . , M , such that for all 0 ≤ i ≤ -1 it holds that (7.32) and such that, conditioned on M i , the subset S i gets drawn uniformly at random among the (k -1)-element subsets of M i . Note that for all v ∈ M i it holds that d(u, v) = d i or d(u, v) = d i -1. For all 0 ≤ i ≤ we let 1 ≤ X i ≤ k denote the number of vertices in M i with d(u, v) = d i -1. Equation (7.32) implies that for all 0 ≤ i ≤ -1

d i+1 = 1 + min v∈S i d(u, v) and M i+1 = {v i } ∪ S i ,
d i+1 = d i , X i+1 < k d i + 1, X i+1 = k .
As d 0 = 1 and X 0 = 1, it holds that

d = 1 + i=1 1 X i =k .
(7.33)

Recall that given M i , the set S i gets drawn uniformly at random from the (k -1)-element subsets of M i . Thus, (X i ) i is Markov chain with the transition probabilities p ij = P(X n+1 = j | X n = i) given by the matrix

P = (p ij ) i,j =          k-1 k 1 k 2 k k-2 k 3 k k-3 k . . . . . . k-1 k 1 k 1          ∈ R k×k .
Here we use the convention, that empty spaces in a matrix denote zero entries. The stationary distribution is given by

π = (π i ) 1≤i≤k = 1 k i=1 1 i 1, 1 2 , . . . , 1 k .
This chain is clearly irreducible. However, unless k = 2, it is not reversible. As the multiplicative symmetrization P P is irreducible, we may apply Lemma 5.2 to obtain that there are constants a, b > 0 such that for all sufficiently small > 0 and all ≥ 1 it holds that

P(|d -1 -π k | ≥ ) ≤ a exp(-b 2 ).

2 . Preliminaries 2 . 1 .

 221 Notation. Throughout, we set N = {1, 2, . . .}, N 0 = {0} ∪ N, [n] = {1, 2, . . . , n}, n ∈ N 0 .

Figure 1 .

 1 Figure 1. Composition of cycles.

  Q e := Q τ × {e} and (G Qe , σ Qe ) := Sym(G)[f e ](G τ , σ τ ) with f e : Q τ → Q e the canonical bijection. For any label e of the F-structure m set f (e) := Q e and let π denote the set of all sets Q e . Thus F := F[f ](m) is an F-structure with label set π and C := (π, F, (G Q ) Q∈π ) is an F • G-structure. Let τ be a cycle of σ m and ν a cycle of σ τ . Fix an atom b = b(τ ) of τ and an atom a = a(ν) of ν. Let denote the length of τ and k the length of ν. Form the composed cycle c by ((a, b), . . . , (a, τ -1 (b)), (ν(a), b), . . . , (ν(a), τ -1 (b)), . . . , (ν k-1 (a), b), . . . , (ν k-1 (a), τ -1 (b))).

  ,y . Then (X, Y ) may be interpreted as an (F • G)-symmetry over the set [|X|] [|Y |]. If α denotes a uniformly at random drawn bijection from this set to [|X| + |Y |], then

Lemma 5 . 2 (

 52 [START_REF] Lezaud | Chernoff-type bound for finite Markov chains[END_REF] Thm. 3.3]). Let (X n ) n≥1 denote an irreducible Markov chain on a finite state space S with transition matrix P and stationary distribution π. Suppose that the multiplicative symmetrization K = P P is irreducible, and let (K) denote its spectral gap. Let f : S → [-1, 1] denote a function whose expected value with respect to the distribution π equals E π [f ] = 0. Let b > 0 be a constant such that 0 < f 2 ≤ b.

Figure 2 .

 2 Figure 2. Correspondence of rooted connected graphs and enriched trees.

Figure 4 .

 4 Figure 4. The encoding of A R -symmetries as Sym(R)-enriched trees.

( 2 )

 2 The series Ãω R (z) has square root singularities at the points s k = ρ exp(2πik/span(w)), k = 0, . . . , span(w) -1, with local expansions as analytic functions of 1 -z/s k .(3) The offspring distribution ξ of the Galton-Watson tree T f and the random variable ζ have finite exponential moments. Moreover,

Figure 6 .

 6 Figure 6. The decomposition of A ( ) R .

Figure 7 . 6 . 2 . 2 .

 7622 Figure 7. The sampler ΓS ( ) (x).

  Set k := |R| and make a uniformly at random choice of a bijection f from the set [k] ∪ { * k } of labels of the R-structure R to the set of integers [k + 1]. Relabel the symmetry via the transport function: β(o) := (R(o), σ(o)) := Sym(R)[f ](R, σ). Let b := f ( * k ) denote the vertex corresponding to * k . 3. Note that b is a fixpoint of the permutation σ(o). For each cycle τ = (b) of σ(o) draw an independent copy (T τ , β τ ) of the sampler ΓS(x |τ | ) with |τ | ≥ 1 denoting the length of the cycle.

Figure 8 . 6 . 3 .

 863 Figure 8. Patching together discrete metric spaces.

4 )

 4 with a, b, c > 0 is an upper-triangular matrix. For any , n it holds that ( -1, (n-1)-( -1)) ∈ Λ if and only if ( -1, n -1) ∈ Λ := CZ 2 with We may easily calculate that( -1, n -1) ∈ CZ 2 if and only if n -1 ∈ Z gcd(a, b + c), ∈ n + Zac/ gcd(a, b + c).Indeed, it necessarily holds that n -1 ∈ Za + Z(b + c) = Z gcd(a, b + c). Conversely, if n -1 = λ 0 a + µ 0 b, then any pair (λ, µ) ∈ Z 2 satisfies λa + µb = n -1 precisely if there is an arbitrary integer t with λ -λ 0 = t(b + c)/ gcd(a, b + c) and µ -µ 0 = ta/ gcd(a, b + c). Hence ( -1, n -1) = C(λ, µ) reduces to = n + act/ gcd(a, b + c) with t ∈ Z.

  ) ≤ |F (o)| for all u ∈ F (o). Since D o ≤ 2 sup u∈F (o) d Y (o, u), it follows that

  v) ≥ s n and d Yn (u, v) / ∈ (1 ± )E[η]d Tn (u, v).Likewise, let E 2 denote the event that there exists a vertex v and an ancestor u of v with d Tn (u, v) ≤ s n and d Yn (u, v) ≥ t n .We are going to show that with high probability none of the events E 1 and E 2 takes place This suffices to show the claim: Take s = 2 and t = 1/4 and suppose that the complementary events E c1 and E c 2 hold. Given vertices a = b in the tree T f n let x denote their lowest common ancestor. If x ∈ {a, b} then we haved Yn (a, b) = d Yn (a, x) + d Yn (b, x).If x = a, b, then let a denote the offspring of x that lies on the T f n -path joining a and x and likewise b the offspring of x lying on the path joining x and b. Hence we have thatd Yn (a, b) = d Yn (a, x) + d Yn (b, x) + R with R = d Yn (a, a ) -d Yn (a , x) -d Yn (b , x).By property E c2 and the triangle inequality it follows that |R| = -R ≤ 2n 1/4 . Thus, regardless whether x ∈ {a, b}, it holds thatd Yn (a, b) = d Yn (a, x) + d Yn (b, x) + O(n 1/4 ). Moreover, if d T f n (a, x) ≥ log(n) 2 , then it follows by property E c 1 that d Yn (a, x) ∈ (1 ± )E[η]d T f n (a, x). Otherwise, if d T f n (a, x) < log(n)2 then it follows by property E c 2 that d Yn (a, x) ≤ n 1/4 and thus |d Yn (a, x) -E[η]d T f n (a, x)| ≤ Cn 1/4 for a fixed constant C that does not depend on n or the points a and x. It follows that |d Yn (a, b)/ √ n -E[η]d T f n (a, b)/ √ n| ≤ D(T f n )/ √ n + o(1), with D(T f n ) denoting the diameter. Thus d GH (Y n , E[η]T f n ) ≤ D(T f n )/ √ n + o(1)

S∈HP

  (Z n = S | (δ i R ) R,i ) = Θ(n 3/2 ) = (S, v S ) | (δ i R ) R,i ).Let v 0 , . . . , v denote the spine of ΓZ A ( ) R (ρ), that is, v is the outer root, v 0 is the inner root, and (v 0 , . . . , v ) is the directed path connecting the roots. It follows that the probability for the eventE 1 , v ) / ∈ (1 ± )E[η]( -k))

(

  |f n (v)| + |F n (v)|) ≥ x) ≤ C 1 n 5/2 exp(-c 1 x). (7.24)As we assumed that √ n ≤ x ≤ n, it follows thatP(E 2 ) ≤ C 1 n 5/2 exp(-c 1 x/2) ≤ C 2 exp(-c 2 x 2 /n) with the constants C 2 ,c 2 > 0 not depending on n or x. As for the event E 1 , Lemma 2.2 implies that there are constants C 3 , c 3 > 0 that do not depend on n or x such thatP(E 1 ) = n =1 P(|T f n | = )P(H(T f n ) ≥ x/2 | |T f n | = ) f n | = ) exp(-c 3 x 2 / ) ≤ C 3 exp(-c 3 x 2 / ).

  . Let d denote the k-tree distance from u to v . Thus |d -d | ≤ 1

  for all m and x > 0. See Devroye and Janson [24, Lem. 2.3] and Janson [41, Lem. 2.1]. As ξ and | f| have finite first moments, it follows that

  6.7 implies that ( Ĥ[kn] , u * ) lies in E kn,n with probability tending to one as n becomes large. Hence, if we verify Equation (7.17) with the index H only ranging over the subsets of E kn,n , then it follows that (H n[kn] , v * ) also lies with probability tending to one in E kn,n . But this already verifies (7.17) when H ranges over all subsets of E kn , and we are done.

	So it remains to show that for any > 0 it holds for sufficiently large n that
	(7.18)	sup H⊂E kn,n	|P((H n [kn] , v * ) ∈ H) -P(( Ĥ[kn] , u * ) ∈ H)| ≤ .

  Proof of Theorem 6.9. By Lemma 6.11 it follows that with high probability all vertices v ∈ T f n have the property that the d Yn -diameter of the subspace {v} ∪ F (v) is at most O(log(n)). This implies that the Gromov-Hausdorff distance between the metric spaces (Y n , d Yn / Ãω R (ρ 2 ) σ 2 • • •and let η denote the δ R -distance of the two distinct * -labels. Note that by our assumptions on the cycle index sum Z R κ we have that |R| has finite exponential moments. Moreover, the diameter of the metric δ R is bounded by |R| many independent copies of a real-valued random variable χ ≥ 0 with finite exponential moments. Hence η has finite exponential moments. We are going to show that the Gromov-Hausdorff distance of (T f n , d Yn /

	√ n) converges in probability to zero. Moreover, by Lemma 6.11 we know that n) n) with c = (1 + E[ζ])V[ξ]/2 converges weakly to the CRT T e . It remains to show n , d Yn / and (T f √ (T f n , cd T f n / √ that there is a constant c such that the Gromov-Hausdorff distance between (T f n , d Yn / √ n) and (T f n , c d T f n / √ n) converges in probability to zero.
	We define the random number η as follows. Choose a random R -symmetry (R, σ) from
	k≥0 Sym(R )[k] with probability proportional to the weight
	κ(R) |R|! converges in probability to zero. By the discussion in the preceding paragraph this implies that Ãω R (ρ) σ 1 √ n) and (T f n , E[η]d T f / √ n) n
	(1 + E[ζ])V[ξ] 2E[η] √ n	Y n	d -→ T e

Moreover, the average rescaled diameter E[D(T )/ √ ] converges as becomes large to a multiple of the expected diameter of the CRT T e . In particular, it is a bounded sequence. Since E[g( σT 2 √ )] converges to E[g(T e )] as becomes large, it follows that E[g( tT f n √ n )] converges to E[g(T e )] as n becomes large. This concludes the proof.

Acknowledgement

I thank Jetlir Duraj, Markus Heydenreich, Grégory Miermont, and Vitali Wachtel for related discussions.

uniformly for all bounded x ∈ R with := µn + x √ n ∈ n + dZ.

Furthermore,

and for any 1 > 0 there is a constant M > 0 such that for all n

Hence we may bound the expression in (7.18) by

Throughout the rest of the proof, we set k = k n . Let (H, u) ∈ E k,n with H = (H i ) 0≤i≤k be given. We set L = L k (H k ) + L G k (H k ) and let F 0 denote the size of the forest of the G-object corresponding to the root of H 0 . Let A denote a G-enriched tree with a total number of vertices #A = n. Given (T n , β n ) = A, the vertex v * is drawn uniformly at random from A. Given (T n , β n ) = A and H n k = H k , the vertex v * is drawn uniformly at random from L possible locations. Out of these, exactly p(H)(1 + F 0 ) many correspond to the event H n

[k] = H, since the number p(H) defined in Lemma 6.7 counts the number of fixpoints v at height k in H k with the property, that the extended enriched fringe subtree representation with respect to v is identical to H.

Moreover, given additionally H n

[k] = H, there is precisely one out of 1 + F 0 possible locations such that v * = u. Hence

There is a 1 to L correspondence between the fixpoints v of A with f (A, v) = H k , and the possible locations for v * such that H n k = H k . Hence

Let (G 1 , . . . , G t ) and G n i , i = 1, . . . , |T f n | denote the depth-first-search ordered lists of G-objects of the enriched trees H k and T f n . The occurrences of (G 1 , . . . , G t ) as substrings of (G n i ) i correspond precisely to the vertices of T f n where the fringe-subtree equals H k . As Equations (7.20) and (7.21) hold uniformly for all G-enriched trees with n vertices, it follows that

with J n j denoting the indicator variable for the event (G n j , . . . , G n j+t-1 ) = (G 1 , . . . , G t ). Here we set G n i := G n i-whenever i > . Note that J j = 0 whenever j + t -1 > , as then the sequence (G n i ) j≤i≤j+t-1 does not correspond to any G-enriched tree at all. Hence the sum of the J j really counts the number of occurrences of (G i ) 1≤i≤t in (G i ) 1≤i≤ . Recall that by Lemma 6.2 there is a natural coupling of the unconditioned G-enriched tree (T , β) with a family (G i ) i∈N of independent copies G i = (S i , f i , F i ) of the random G-object G, conditioned on the event that there is an initial segment of (G i ) i∈N that corresponds to an G-enriched tree. Let (J j ) j=1,..., denote the unconditioned pendants of J n j for the sequence (G i ) 1≤i≤ . Lemma 6.2 implies that

We are going to show that if we choose r and s sufficiently small, then each of these events is sufficiently unlikely. By Lemma 6.11 we have that

In order to bound the probability for the event E h 1 note that the tree T f n conditioned on having size is distributed like T f conditioned on having size . That is, it is identically distributed to a ξ-Galton-Watson tree conditioned on having size which we denote by T . Hence

By Inequality (2.2) there exist constants C 1 , c 1 > 0 that do not depend on n or h such that for all 1 ≤ ≤ n we have the tail bound

In particular, it holds that P(E h 1 ) ≤ C 1 exp(-c 1 r 2 h 2 /n) for all n and h. We proceed to bound the probability for the event E h 2 . Let Z n denote the sampler ΓZ A ω R (ρ) conditioned on having size n and let H ⊂ ∞ k=0 Sym(A R )[k] denote the set of A R -symmetries S = ((T, α), σ) having the property that there exists a fixpoint vertex v S in T with the property that S := h T (v S ) ≤ rh and u d + T (u) ≥ sh with the sum-index u ranging over all ancestors of the vertex v in the tree T . By Equation 6.5 we may bound the probability for the event E h 2 by

Let η denote the outdegree of the root in the sampler ΓZ A (1) R (ρ). By the assumptions on the cycle index sum Z A ω R it follows that η has finite exponential moments. Note that the outdegrees along the spine of ΓZ A ( ) R are distributed like independent copies of η. It follows that

By the deviation inequality in Lemma 5.3 it follows that there are constants c, λ > 0 such that the above quantity is bounded by a constant multiple of exp(5/2 log(n) + crh -λsh). We assumed that h ≥ √ n, hence if we choose r sufficiently small depending only on s, c and λ, it follows that there are constants C 2 , c 2 > 0 such that P(E h 2 ) ≤ C 2 exp(-c 2 h). It remains to treat the event E h 3 . By assumption, for any fixpoint v ∈ T f n we have that the height h Yn (v) is bounded by (v) many independent copies of a random variable χ having finite exponential moments. Thus

P(E h

3 ) ≤ nP(χ 1 + . . . + χ sh ≥ h) with (χ i ) i∈N a family of independent copies of χ. By the deviation inequality in Lemma 5.3 there are constants c, λ > 0 such that this quantity is bounded by a constant multiple of exp(log(n) + sh c -λh). We assumed that h ≥ √ n, hence we may bound this by exp(h(log(n

We are going to show that there are exponents t > 0 and 1/2 < s < 1 such that with high probability

for all u, v ∈ T f n . This suffices to complete the proof. Indeed, it follows that with high probability

By Lemma 6.11 we know that

-→ (T e , d Te ). (7.28) in the (pointed) Gromov-Hausdorff sense. In particular, D(

), and hence it follows from Equation (7.27) that

p -→ 0. (7.29) Equations (7.28) and (7.29) then readily imply that the subspace of the k-tree K • n , that corresponds to T f n , converges toward the CRT after rescaling the metric by c k / √ n with n -distance at most 1 from x. Thus the expression

| is bounded by a fixed constant that does not depend on u, v or x. Thus, in order to show Inequality (7.26), it suffices to show that for a sufficiently small but fixed constant c > 0 and it holds with high probability that

) having the property that the there exists a fixpoint vertex v S in T with the property that S := h T (v S ) ≥ log t (n) but the corresponding distance h * (v S ) in the k-tree corresponding to (T, α) satisfies

. By Lemma 6.3 the probability for the sampler ΓZ A ω R (ρ) to have size n is Θ(n -3/2 ). It follows from Equation 6.5 that

log t n≤ ≤n p , (7.31) with p denoting the probability that the k-tree distance d between the root vertex v 0 and the tip v of the spine v 0 , . . . , v in ΓZ

As π k = b k , follows that for any 1/2 < s < 1 we may choose t > 0 large enough such that the bound in (7.31) tends to zero as n becomes large.

Thus, it holds with high probability that all vertices v ∈ T (7.34) This readily verifies Equation (7.30) and hence completes the proof.

Proof of Theorem 6.16. Let k n = o( √ n) be a given sequence. The random front-rooted unlabelled k-tree K n may be viewed as a Gibbs partition. Theorem 4.1 ensures that K n exhibits a giant component, and that the small fragments converge in total variation toward a Boltzmann limit. Thus, it suffices to show that

as n becomes large. By Equation (7.34) we know that with high probability the trimmed tree (T n , β n ) <hn> already contains all information required to determine the k n -neighbourhood V kn (K • n ). This verifies Equation (7.35) and hence completes the proof. Proof of Theorem 6.17. Let k n = o( √ n) be a given sequence. Theorem 4.1 ensures that K n exhibits a giant component, which is distributed like K ( r n ) • for some random size r n = n + O p [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF]. A uniformly at random selected vertex of K n lies with high probability in this giant component and outside of its root-front. Conditioned on this event, the random vertex is uniformly distributed among the non-root vertices of the large component. Note that every path from a vertex of the giant component to a vertex of a smaller component must pass through the root-front. Thus, it suffices to show that if v * is a random vertex of (T n , β n ), then d TV (V kn (K • n , v * ), V kn ( K• )) → 0, and with high probability V kn (K