Benedikt Stufler
email: benedikt.stufler@ens-lyon.fr

The continuum random tree is the scaling limit of unlabelled unrooted trees

Keywords: combinatorial trees, continuum random tree, scaling limits

. We also establish Benjamini-Schramm convergence of this model of random trees and provide a general approximation result, that allows for a transfer of a wide range of asymptotic properties of extremal and additive graph parameters from Pólya trees to unrooted trees.

Introduction and main results

Combinatorial trees are classical mathematical objects and crop up in a variety of fields [START_REF] Otter | The number of trees[END_REF][START_REF] Drmota | Random trees[END_REF][START_REF] Drmota | The shape of unlabeled rooted random trees[END_REF]. In the present work we take a probabilistic approach to study unordered trees without labels. Here one distinguishes between Pólya trees, which have a root, and unlabelled (unrooted) trees. It has been a long-standing conjecture by Aldous [4, p. 55] that the continuum random tree (CRT) arises as scaling limit of these models of random trees. Marckert and Miermont [START_REF] Marckert | The CRT is the scaling limit of unordered binary trees[END_REF] treated the case of binary unordered rooted trees. The convergence of random (unrestricted) Pólya trees was confirmed by Haas and Miermont [START_REF] Haas | Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees[END_REF] using new methods, and an alternative proof has been given later by Panagiotou and Stufler [START_REF] Panagiotou | Scaling limits of random Pólya trees[END_REF]. As was also mentioned in [24, p. 18], this does not settle the question regarding the convergence of random unlabelled unrooted trees. The main challenge for these structures is the complexity of their symmetries. Rooted trees have a simpler structure, as any automorphism is required to fix the root vertex. Our first main result confirms the CRT as scaling limit of unlabelled unrooted trees as their number of vertices becomes large, confirming Aldous' conjecture for these structures. We take a unified approach to cover all (sensible) cases of vertex degree restrictions.

Throughout, we let Ω denote a fixed set of positive integers containing 1 and at least one integer equal or larger than 3, and set Ω * = Ω -1. Let T n be drawn uniformly at random from the unlabelled trees with n vertices and vertex-degrees in Ω, and let A n-1 denote the random Pólya tree selected uniformly among all such trees with n -1 vertices and outdegrees in the shifted set Ω * . See Figure 1 and 2 for illustrations of these structures. in the Gromov-Hausdorff sense, as n ≡ 2 mod gcd(Ω * ) becomes large. Moreover, there are constants C, c > 0 such that the diameter D(T n ) satisfies the tail bound

P (D(T n ) ≥ x) ≤ C exp(-cx 2 /n) (1.2)
for all n and x ≥ 0. The CRT (T e , d Te ) plays a central role in the study of the geometric shape of large discrete structures. It crops up as scaling limit for a variety of models [START_REF] Albenque | Some families of increasing planar maps[END_REF][START_REF] Bettinelli | Scaling limit of random planar quadrangulations with a boundary[END_REF][START_REF] Caraceni | The scaling limit of random outerplanar maps[END_REF][START_REF] Curien | The CRT is the scaling limit of random dissections[END_REF][START_REF] Janson | Scaling limits of random planar maps with a unique large face[END_REF][START_REF] Panagiotou | Scaling limits of random graphs from subcritical classes[END_REF] and incited research in further directions [START_REF] Abraham | Excursion theory for Brownian motion indexed by the Brownian tree[END_REF][START_REF] Albenque | The Brownian continuum random tree as the unique solution to a fixed point equation[END_REF]. Although scaling limits describe asymptotic global properties, they do not contain information on local properties, such as the limiting degree distribution of a randomly chosen vertex in a graph. Such asymptotic local properties of random rooted structures are described by Benjamini-Schramm limits [START_REF] Angel | Uniform infinite planar triangulations[END_REF][START_REF] Gurel-Gurevich | Recurrence of planar graph limits[END_REF][START_REF] Benjamini | Recurrence of distributional limits of finite planar graphs[END_REF]. Our second main result establishes Benjamini-Schramm convergence for random unlabelled unrooted trees toward an infinite limit tree.

INTRODUCTION AND MAIN RESULTS

Theorem 1.2. The random unrooted tree T n converges in the Benjamini-Schramm sense toward an infinite rooted tree A Ω * , as n ≡ 2 mod gcd(Ω * ) becomes large. Even stronger, if v n denotes a uniformly at random selected vertex of the tree T n , then for each sequence

k n = o( √ n) the radius k n graph neighbourhood V kn (•) satisfies d TV (V kn (T n , v n ), V kn (A Ω * )) → 0. (1.3)
Here d TV denotes the total variation distance. Note that this form of convergence is best possible, as (1.3) fails if the order of k n is comparable to √ n. In the case Ω = N, Benjamini-Schramm convergence for T n was independently obtained by Georgakopoulos and Wagner [START_REF] Georgakopoulos | Limits of subcritical random graphs and random graphs with excluded minors[END_REF] using different techniques. Our methods for the proof of Theorems 1.1 and 1.2 are based on the cycle pointing decomposition established recently by Bodirsky, Fusy, Kang and Vigerske [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]. This novel and effective centering method differs fundamentally from classical approaches, such as the geometric center, and applies to arbitrary classes of combinatorial structures. We use it to approximate the random unlabelled unrooted tree T n with n vertices and vertex outdegrees in a set Ω, by random Pólya trees with vertex outdegrees in the shifted set Ω * = Ω -1, whose random sizes concentrate around n. The approximation works not only for graph limits, but actually for a large range of additive and extremal graph parameters.

Theorem 1.3. There are constants C, c > 0, a random number K n = n + O p (1) ≤ n, and a coupling of the randomly sized Pólya tree A Kn with a tree B n having stochastically bounded size n -K n + 1, such that the random tree Tn obtained by identifying the root vertices of A Kn and B n satisfies d TV (T n , Tn ) ≤ C exp(-cn) for all n.

Theorem 1.3 establishes in full generality how a random unrooted tree may be approximated by a single large random rooted tree having the property, that when conditioned on having a fixed size, it is uniformly distributed among all Pólya trees with this size and the given vertex outdegree restrictions. This has far reaching consequences and underlines the advantages of this approach. It implies that for a very large set of graph theoretic properties (maximum degree, degree distribution, subtree counts, . . . ) everything known (present and future) about random Pólya trees also applies to random unlabelled unrooted trees, erasing the need to study uniform unrooted unordered trees directly. For example, Haas and Miermont [24, Thm. 9, Cor. 10] established Gromov-Hausdorff-Prokhorov scaling limits for uniform unordered rooted trees endowed with the uniform measure on their leaves or on all their vertices, if the vertex out-degrees are restricted to a set of the form Ω * = N 0 , Ω * = {0, d} or Ω * = {0, . . . , d} for some d ≥ 2. Using this result, it follows easily from Theorem 1.3 that the uniform vertex degree restricted unrooted tree T n with vertex degrees in Ω = Ω * + 1 also converges in the Gromov-Hausdorff-Prokhorov sense, thus strengthening the convergence of Theorem 1.1 for these cases. But again, it is not about for which cases of vertex-degree restrictions we may deduce convergence at the moment. The contribution of Theorem 1.3 is that "practically all" properties of random unordered rooted trees get transferred automatically to the unrooted case, regardless of the extend to which they are understood at present. Thus, Theorem 1.3 provides a rigorous justification of the empirically backed and widely believed fact that rooted and unrooted trees behave asymptotically similarly. Note that this does not imply that almost all unrooted trees are asymmetric (meaning the absence of non-trivial symmetries) or possess as much possible root locations as vertices. Some discrete structures such as planar maps with half-edges as atoms have such properties, and hence a purely enumerative argument suffices to show that the asymptotic study of these objects is equivalent to the study of half-edge rooted planar maps. The case of unordered trees is different, as the probability for the random tree T n to be asymmetric is bounded away from 1, as is the probability for the event that rooting it at each of its n vertices yields n distinct trees. Moreover, the approximation argument of Theorem 1.3 does not appear to work as well in the other direction. For example, the convergence of T n (in the local sense, or in the sense of scaling limits) may be used to obtain convergence of a random Pólya-tree having a random number of vertices (depending on n), but, although this number concentrates, this is not sufficient to deduce convergence of a random Pólya tree with a deterministic size that becomes large. Hence the most economic approach is really to study Pólya trees and then transfer the results to random unlabelled unrooted trees. Furthermore, in [START_REF] Panagiotou | Scaling limits of random Pólya trees[END_REF] it was shown how asymptotic properties of conditioned Galton-Watson trees may be transferred to random Pólya trees, which by the results of the present work hence also apply to the unrooted model. As Galton-Watson trees are without doubt the best understood model of random trees in probability theory, it is natural to pave the way for building on this knowledge.

In [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF] the cycle pointing method was developed for the enumeration and efficient sampling of discrete structures. The present work demonstrates for the important classical example of unlabelled trees how a combination with a probabilistic approach allows us to answer a large number of questions related to the study of asymptotic properties of random discrete structures. Due to the generality of the involved methods this will likely stimulate probabilistic applications to further classes of discrete structures, such as models of random unlabelled graphs.

Combinatorial applications of the scaling limit

A direct consequence of the scaling limit in Theorem 1.1 is that the rescaled diameter e Ω n -1/2 D(T n ) converges weakly and in arbitrarily high moments toward the diameter D(T e ) of the CRT. That is, and (e(t 1 ) + e(t 2 ) -2 inf

E [D(T n ) p ] ∼ e -p Ω n p/2 E [D(T e ) p ]
t 1 ≤t≤t 2 e(t)), (1.4)
with e = (e t ) 0≤t≤1 denoting Brownian excursion of length 1, and

P (D(T e ) > x) = ∞ k=1 (k 2 -1) 2 3 k 4 x 4 -4k 2 x 2 + 2 exp(-k 2 x 2 /2). (1.5)
Equations (1.4) and (1.5) have been established by Aldous [4,Ch. 3.4] using convergence of random discrete trees. Expression (1.5) was recently recovered directly in the continuous setting by Wang [START_REF] Wang | Height and diameter of Brownian tree[END_REF].

The moments of the diameter are given by:

E [D(T e )] = 4 3 π/2, E D(T e ) 2 = 2 3 1 + π 2 3 , E D(T e ) 3 = 2 √ 2π, (1.6)
E D(T e ) k = 2 k/2 3 k(k -1)(k -3)Γ(k/2)(ζ(k -2) -ζ(k)) for k ≥ 4. (1.7)
The expression E [D(T e )] = 4 3 π/2 may be obtained as shown by Aldous [4,Sec. 3.4] using results of Szekeres [START_REF] Szekeres | Distribution of labelled trees by diameter[END_REF], who proved the existence of a limit distribution for the diameter of rescaled random unordered labelled trees. The higher moments can be obtained in the same way by elaborated calculations, but it is more economic to deduce them by combining Theorem 1.1 with results by Broutin and Flajolet [START_REF] Broutin | The distribution of height and diameter in random non-plane binary trees[END_REF] as follows:

Consider the random tree τ n drawn uniformly at random among all unlabelled trees with n leaves in which each inner vertex is required to have degree 3. In [START_REF] Broutin | The distribution of height and diameter in random non-plane binary trees[END_REF]Thm. 8] asymptotics of the form

E [D(τ n ) r ] ∼ c r λ -r n r/2
were established by analytic methods, with λ an analytically given constant, and the constants c r given by

c 1 = 8 3 √ π, c 2 = 16 3 (1 + π 2 3 ), c 3 = 64 √ π, c r = 4 r 3 r(r -1)(r -3)Γ(r/2)(ζ(r -2) -ζ(r)) if r ≥ 4.
As τ n has n leaves and hence 2n -1 vertices in total, it follows by Theorem 1.1 that

(τ n , e {0,2} (2n -1) -1/2 d τn ) d -→ (T e , d Te )
and consequently, by the exponential tail-bounds for the diameter in Theorem 1.1, which imply arbitrarily high uniform integrability,

E [D(τ n ) r ] ∼ E [D(T e ) r ] (e {0,2} / √ 2) -r n r/2 . It follows that E [D(T e ) r ] = c r (e {0,2} /( √ 2λ)) r .
All that remains is to calculate the ratio e {0,2} /( √ 2λ), which is given by

e {0,2} /( √ 2λ) = E [D(T e )] /c 1 = 1/(2 √ 2), since E [D(T e )] = 4/3 π/2.

Outline of the paper

In Section 2 we fix basic notions on graphs and discrete trees. Section 3 gives a brief account on Gromov-Hausdorff convergence and the continuum random tree. Section 4 recalls the notion of local weak convergence and results for random Pólya trees. Section 5 introduces the reader to the language of combinatorial species, and Section 6 to the technique of cycle pointing that is formulated using these notions. Section 7 recalls the concept of (Pólya-)Boltzmann samplers, which builds a bridge from combinatorial structures to random algorithms that sample these structures. Section 8 discusses extremal component sizes in random multisets. In Section 9 we present the proofs of our main results.

Notation

Throughout, we set

N = {1, 2, . . .}, N 0 = {0} ∪ N, [n] = {1, 2, . . . , n}, n ∈ N 0 .
we assume that all considered random variables are defined on a common probability space whose measure we denote by P. All unspecified limits are taken as n becomes large, possibly along a shifted sublattice of the integers. We write d -→ and p -→ for convergence in distribution and probability, and

(d)
= for equality in distribution. An event holds with high probability, if its probability tends to 1 as n → ∞. We let O p (1) denote an unspecified random variable X n of a stochastically bounded sequence (X n ) n . The total variation distance of measures and random variables is denoted by d TV . For a sequence a n that is eventually positive the notation O(a n ) and o(a n ) refer to unspecified deterministic sequences that are bounded by a multiple of a n or whose order is negligible compared to a n . Given a multi-variate power series

f (z 1 , z 2 , . . .) we let [z t 1 1 • • • z tm m ]f (z 1 , z 2 , . . .) denote the coefficient corresponding to the monomial z t 1 1 • • • z tm m .

Discrete trees

A (labelled) graph G consists of a non-empty set V (G) of vertices (or labels) and a set E(G) of edges that are two-element subsets of V (G). The cardinality |V (G)| of the vertex set is termed the size of G.

Instead of v ∈ V (G) we will often just write v ∈ G. Two vertices v, w ∈ V (G) are said to be adjacent if {v, w} ∈ E(G). An edge e ∈ E(G) is adjacent to v if v ∈ e.
The cardinality of the set of all edges adjacent to a vertex v is termed its degree and denoted by d G (v). We say the graph G is connected if any two vertices u, v ∈ V (G) are connected by a path in G. The length of a shortest path connecting the vertices u and v is called the graph distance of u and v and it is denoted by

d G (u, v). Clearly d G is a metric on the vertex set V (G). A graph G together with a distinguished vertex v ∈ V (G) is called a rooted graph with root-vertex v. The height h(w) of a vertex w ∈ V (G) is its distance from the root.
The height H(G) of the entire graph is the supremum of the heights of the vertices in G. For any k ≥ 0 we let V k (G, v) denote k-neighbourhood of the vertex v in G, that is, the subgraph induced by all vertices with distance at most k from v. Two graphs G 1 and G 2 are termed isomorphic, if there is a bijection ϕ : V (G 1 ) → V (G 2 ) such that any two vertices x, y ∈ V (G 1 ) are adjacent in G 1 if and only if φ(x) and φ(y) are adjacent in G 2 . Any such bijection is termed an isomorphism between G 1 and G 2 . Rooted graphs

G • 1 = (G 1 , o 1 ) and G • 2 = (G 2 , o 2 ) are termed isomorphic, if there is a graph isomorphism φ from G 1 to G 2 that satisfies φ(o 1 ) = o 2 .
An isomorphism class of (rooted) graphs is also called an unlabelled (rooted) graph. We will often not distinguish between such a class or any fixed representative of that class.

A tree T is a non-empty connected graph without cyclic subgraphs, that is, we cannot walk from one vertex to itself without crossing at least one edge twice. Any two vertices of a tree are connected by a unique path. Figure 1 depicts the list of all unlabelled trees with 6 vertices. If T is rooted, then the vertices w ∈ V (T ) that are adjacent to a vertex w and have height h(w ) = h(w) + 1 form the offspring set of the vertex w. Its cardinality is the outdegree d + T (w) of the vertex w. Unlabelled rooted trees are also termed Pólya trees. Note that while any labelled tree with n vertices admits n different roots, this does not hold in the unlabelled setting. For example, as illustrated in Figure 2, there are 3 unlabelled trees with 5 vertices and each of them has a different number of rootings.

Scaling limits

We briefly recall several relevant results regarding the convergence of random rooted trees toward the continuum random tree.

Gromov-Hausdorff convergence

We introduce the required notions regarding the Gromov-Hausdorff convergence following Burago, Burago and Ivanov [START_REF] Burago | A course in metric geometry[END_REF]Ch. 7] and Le Gall and Miermont [START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF]

The Hausdorff metric

Recall that given subsets A and B of a metric space (X, d), their Hausdorff-distance is given by

d H (A, B) = inf{ > 0 | A ⊂ U (B), B ⊂ U (A)} ∈ [0, ∞],
where

U (A) = {x ∈ X | d(x, A) ≤ } denotes the -hull of A.
In general, the Hausdorff-distance does not define a metric on the set of all subsets of X, but it does on the set of all compact subsets of X ([13, Prop. 7.3.3]).

The Gromov-Hausdorff distance

The Gromov-Hausdorff distance allows us to compare arbitrary metric spaces, instead of only subsets of a common metric space. It is defined by the infimum of Hausdorff-distances of isometric copies in a common metric space. We are also going to consider a variation of the Gromov-Hausdorff distance given in [START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF] for pointed metric spaces, which are metric spaces together with a distinguished point.

Given metric spaces (X, d X ), and (Y, d Y ), and distinguished elements x 0 ∈ X and y 0 ∈ Y , the Gromov-Hausdorff distances of X and Y and the pointed spaces X • = (X, x 0 ) and Y • = (Y, y 0 ) are defined by

d GH (X, Y ) = inf ι X ,ι Y d H (ι X (X), ι Y (Y )) ∈ [0, ∞], d GH (X • , Y • ) = inf ι X ,ι Y max {d H (ι X (X), ι Y (Y )), d E (ι X (x 0 ), ι Y (y 0 ))} ∈ [0, ∞]
where in both cases the infimum is taken over all isometric embeddings ι X : X → E and ι Y : Y → E into any common metric space (E, d E ), compare with Figure 3. We will make use of the following characterisation of the Gromov-Hausdorff metric. Given two metric spaces (X, d X ) and (Y, d Y ) a correspondence between them is a relation R ⊂ X × Y such that any point x ∈ X corresponds to at least one point y ∈ Y and vice versa. If X and Y are pointed, we additionally require that the roots correspond to each other. The distortion of R is given by dis [START_REF] Burago | A course in metric geometry[END_REF]Thm. 7.3.25] and [START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF]Prop. 3.6]). Given two metric spaces X, Y and pointed metric spaces X • , Y • we have that

(R) = sup{|d X (x 1 , x 2 ) -d Y (y 1 , y 2 )| | (x 1 , y 1 ), (x 2 , y 2 ) ∈ R}. Proposition 3.1 ([
d GH (X, Y ) = 1 2 inf R dis(R), and d GH (X • , Y • ) = 1 2 inf R dis(R),
where R ranges over all correspondences between X and Y (or X • and Y • ).

Using this reformulation of the Gromov-Hausdorff distance, one may check that it satisfies the following properties. Lemma 3.2 ([13, Thm. 7.3.30] and [START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF]Thm. 3.5]). Let X, Y , and Z be (pointed) metric spaces. Then the following assertions hold.

i) d GH (X, Y ) = 0 if and only if X and Y are isometric. ii) d GH (X, Z) ≤ d GH (X, Y ) + d GH (Y, Z).
iii) If X and Y are bounded, then d GH (X, Y ) < ∞.

The space of isometry classes of compact metric spaces

In Section 3.1.1 we saw that the Hausdorff-distance defines a metric on the set of all compact subsets of a metric space. By Lemma 3.2 the Gromov-Hausdorff distance satisfies in a similar way the axioms of a (finite) pseudo-metric on the class of all compact metric spaces, and two metric spaces have Gromov-Hausdorff distance 0 if and only if they are isometric. Informally speaking, this yields a metric on the collection of all isometry classes of metric spaces, and in a similar way we may endow the collection of isometry classes of pointed metric spaces with a metric.

Note that from a formal viewpoint this construction is a bit problematic, since we are forming a collection of proper classes (as opposed to sets). A solution is presented as an exercise in [13, Rem. 7.2.5]: Proposition 3.3. Any set of pairwise non-isometric (pointed) metric spaces has cardinality at most 2 ℵ 0 , and there are specific examples of 2 ℵ 0 many non-isometric (pointed) spaces.

We may thus fix a representative of each isometry class of (pointed) metric spaces and let K (resp. K • ) denote the resulting sets of spaces. Lemma 3.2 now reads as follows. Corollary 3.4 ([13,Thm. 7.3.30]). The Gromov-Hausdorff distance defines a finite metric on the set K (resp. K • ) of representatives of isometry classes of (pointed) compact metric spaces.

The metric spaces K and K • have nice properties, which make them suitable for studying random elements: Proposition 3.5 [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.4.15]). The spaces K and K • are separable and complete, i.e. they are Polish spaces.

The continuum random tree

An R-tree is a metric space (X, d) such that for any two points x, y ∈ X the following properties hold 1. There is a unique isometric map from the interval ϕ x,y : [0, d f (x, y)] → X satisfying ϕ x,y (0) = x and ϕ x,y (d f (x, y)) = y.

2. If q : [0, d f (x, y)] → X is a continuous injective map, then q([0, d f (x, y)]) = ϕ x,y ([0, d f (x, y)]).
R-trees may be constructed as follows. Let f : [0, 1] → [0, ∞[ be a continuous function satisfying f (0) = f (1) = 0. Consider the pseudo-metric d on the interval [0, 1] given by

d(u, v) = f (u) + f (v) -2 inf u≤s≤v f (s) for u ≤ v. Let (T f , d T f ) = ([0, 1]/∼, d
) denote the corresponding quotient space. We may consider this space as rooted at the equivalence class 0 of 0.

Proposition 3.6 ([27, Thm. 3.1]). Given a continuous function f : [0, 1] → [0, ∞[ satisfying f (0) = f (1) the corresponding metric space T f is a compact R-tree.
Hence, this construction defines a map from a set of continuous functions to the space K • . It can be seen to be Lipschitz-continuous: Proposition 3.7 [START_REF] Gall | Probability and statistical physics in two and more dimensions[END_REF]Cor. 3.7]). The map

({f ∈ C([0, 1], R ≥0 ) | f (0) = f (1) = 0}, • ∞ ) → (K • , d GH ), f → T f is Lipschitz-continuous.
Hence we may define the continuum random tree as a random element of the polish space K • .

Definition 3.8. The random pointed metric space (T e , d Te , 0) coded by the Brownian excursion of duration one e = (e t ) 0≤t≤1 is called the Brownian continuum random tree (CRT).

Note that the Lipschitz-continuity (and hence measurability) of the above map ensures that the CRT is a random variable.

Scaling limits of random Pólya trees

It is known that for any subset Ω * ⊂ N 0 containing zero and at least one integer k ≥ 2, the Pólya tree A n drawn uniformly at random from the set of all Pólya trees with n vertices and vertex outdegrees in the set Ω * admits the CRT as scaling limit. That is, there is a constant c Ω * satisfying

(A n , c Ω * n -1/2 d An ) d -→ (T e , d Te ) (3.1)
as random elements of the space K • . See [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]. The diameter admits a tail-bound of the form

P (D(A n ) ≥ x) ≤ C exp(-cx 2 /n) (3.2)
for all n and x ≥ 0 [30, Thm. 1.2].

Local weak limits

We briefly recall relevant notions and concerning local weak convergence of random graphs.

The metric for local convergence

Given two rooted, locally finite (that is, the graph may have infinitely many vertices, but each vertex has only finitely many neighbours) connected graphs

G • = (G, o G ) and H • = (H, o H ), we may consider the distance d BS (G • , H • ) = 2 -sup{k∈N 0 | V k (G • ) V k (H • )} .
Here

V k (G • ) V k (H • ) denotes isomorphism of rooted graphs, that is, the existence of a graph isomorphism φ : V k (G • ) → V k (H • ) satisfying φ(o G ) = o H .
This defines a premetric on the collection of all rooted connected locally finite graphs.

If B denotes the collection of isomorphism classes of rooted locally finite connected graphs, then the (lift of) this distance defines a metric on B that is complete and separable. In other words, (B, d BS ) is a Polish space. Similarly as for the Gromov-Hausdorff metric, we may safely ignore the fact that B is a collection of proper classes (as opposed to sets). In order to be precise, we would only need to fix a representatives of each isomorphism class and work with the set of these representatives instead.

Benjamini-Schramm convergence of random Pólya trees

Let Ω ⊂ N denote a subset containing 1 and at least one integer k ≥ 3, and let Ω * = Ω -1 denote the corresponding shifted set. Let A n denote the random tree drawn uniformly at random from the set of all Pólya trees with n vertices and vertex outdegdrees in Ω * . Let u n denote a uniformly at random drawn selected vertex of A n . It was shown in [START_REF] Stufler | Random enriched trees with applications to random graphs[END_REF]Thm. 6.22], that there is a random infinite rooted trees A Ω * such that for each sequence k n = o( √ n) the random vertex u n has with high probability height strictly larger than k n in the tree A n and

d TV (V kn (A n , u n ), V kn (A Ω * )) → 0. (4.1)

Combinatorial species of structures

The language of combinatorial species was developed by Joyal [START_REF]Une théorie combinatoire des séries formelles[END_REF]. It is appropriate to use this framework in the context of combinatorial probability theory, as it allows for a systematic enumeration of a wide range of discrete structures. We recall the required theory and notations following [START_REF] Bergeron | Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications[END_REF][START_REF]Une théorie combinatoire des séries formelles[END_REF]. The language of combinatorial classes used by Flajolet and Sedgewick [START_REF] Flajolet | Analytic combinatorics[END_REF] is essentially equivalent in many aspects, although less emphasis is put on studying objects up to symmetry.

Combinatorial species of structures

Informally speaking, a combinatorial species is a collection of labelled discrete structures together with the information on when two such objects may be considered as structurally equivalent. The collection of labelled graphs together with the isomorphism relation is a natural example, that one may keep in mind to ease the understanding of the formal definition. Formally, a species may be defined as a functor F that maps any finite set U of labels to a finite set F[U ] of F-objects and any bijection σ : U → V of finite sets to its (bijective) transport function

F[σ] : F[U ] → F[V ]
along σ, such that composition of maps and the identity maps are preserved. Thus, for the species of graphs the labels correspond to the vertices and the transport functions to vertex relabellings.

An element

F U ∈ F[U ] has size |F U | := |U | and two F-objects F U and F V are termed isomorphic (or structurally equivalent) if there is a bijection σ : U → V such that F[σ](F U ) = F V . We will often just write σ.F U = F V instead, if there is no risk of confusion. We say σ is an isomorphism from F U to F V . If U = V and F U = F V then σ is an automorphism of F U . An isomorphism class of F-structures is called an unlabelled F-object.
The isomorphism class of a given F-object is also called its isomorphism type. By abuse of notation, we treat unlabelled objects as if they were regular objects. We will also write F ∈ F to state that F is an F-object.

We say that a species G is a subspecies of F, and write

G ⊂ F, if G[U ] ⊂ F[U ] for all finite sets U and G[σ] = F[σ]| U
for all bijections σ : U → V . For example, the species of connected graphs may be viewed as a subspecies of the species of graphs.

Given two species F and G, an isomorphism α :

F ∼ -→ G from F to G is a family of bijections α = (α U : F[U ] → G[U ]
) U where U ranges over all finite sets, such that for all bijective maps σ : U → V the following diagram commutes.

F[U ] α U F [σ] / / F[V ] α V G[U ] G[σ] / / G[V ]
The species F and G are isomorphic if there exists an isomorphism from one to the other. This is denoted by F G. The idea behind this is that we consider two collections of discrete structures as equivalent, if there is a bijective correspondence between them that preserves the notion of structural equivalence. This is essential for the study of discrete structures considered up to symmetry. For example, two collections of n-sized graphs may admit a bijective correspondence, but if this bijection does not preserve graph isomorphisms, the corresponding classes of unlabelled graphs may have different cardinalities.

In the alternative language of combinatorial classes, two classes of combinatorial structures are already considered as equivalent, if there is a size-preserving bijection between them [21, Def. I.3]. For this reason the framework of combinatorial species is more convenient when studying structures up to symmetry, although it has a more formal character and is actually best understood in a category theoretic formulation.

We will mostly be interested in the species of trees, and make use of standard species such as the SET-species given by SET[U ] = {U } for all U . Moreover, we let X the species with a single object of size 1.

Symmetries and generating power series

Letting fn denote the number of unlabelled F-objects of size n, the ordinary generating series of F is defined by

F(x) = ∞ n=0 fn x n .
A pair (F, σ) of an F-object together with an automorphism is called a symmetry. Its weight monomial is given by

w (F,σ) = 1 n! x σ 1 1 x σ 2 2 • • • x σn n ∈ Q[[x 1 , x 2 , . . .]]
with n denoting the size of F and σ i denoting the number of i-cycles of the permutation σ. (Recall that any permutation admits a unique decomposition into a product of disjoint cyclic permutations.) In particular σ 1 denotes the number of fixpoints. We may form the species Sym(F) of symmetries of F.

The cycle index sum of F is given by

Z F = (F,σ) w (F,σ)
with the sum index (F, σ) ranging over the set n∈N 0 Sym(F) [n]. The reason for studying cycle index sums is the following remarkable property. From a probabilistic viewpoint, this observation guarantees that the isomorphism type of the first coordinate of a uniformly at random drawn element from Sym(F)[n] is uniformly distributed among all n-element unlabelled F-objects. Lemma 5.1 also implies that the ordinary generating series and the cycle index sum are related by

F(z) = Z F (z, z 2 , z 3 , . . .).
(5.1)

See [START_REF]Une théorie combinatoire des séries formelles[END_REF]Sec. 3,Prop. 9] for a more detailed justification. For example, the cycle index sum Z SET is easily calculated: For any integer n ≥ 0 let S n denote the symmetric group of degree n. Then

Z SET = ∞ n=0 1 n! σ∈Sn x σ 1 1 x σ 2 2 • • • x σn n . (5.2)
For any permutation

σ let (σ 1 , σ 2 , . . .) ∈ N (N) 0 denote its cycle type. Then to each element m = (m i ) i ∈ N (N) 0
correspond only permutations of order n := ∞ i=1 im i and their number is given by n!/ ∞ i=1 (m i ! i m i ). Hence we have

Z SET = m∈N (N) 0 ∞ i=1 x m i i m i ! i m i = ∞ i=1 ∞ m i =0 x m i i m i ! i m i = ∞ i=1 exp x i i = exp ∞ i=1 x i i .
If (x i ) i would denote a sequence of sufficiently fast decaying positive real-numbers, then this calculation could easily be justified. But they denote a countable set of formal variables, and hence one has every right to ask for a rigorous justification of this argument, in particular why the involved infinite products of formal variables vanish. A correct formalization is to define a topology on the set of formal power series and interpret these infinite products as actual limits with respect to this topology. We refer the inclined reader to [21, Appendix A.5] for an adequate discussion of these questions.

Operations on combinatorial species

The framework of combinatorial species offers a large variety of constructions that create new species from others. In the following let F, (F i ) i∈I and G denote species and U an arbitrary finite set. The sum i∈I F i is defined by the disjoint union

( i F i )[U ] = i F i [U ]
if the right hand side is finite for all finite sets U . The product F • G is defined by the disjoint union

(F • G)[U ] = (U 1 ,U 2 ) U 1 ∩U 2 =∅,U 1 ∪U 2 =U F[U 1 ] × G[U 2 ]
with componentwise transport. Thus, n-sized objects of the product are pairs of F-objects and G-objects whose sizes add up to n. Two such pairs are considered as structurally equivalent, if their components are. If the species G has no objects of size zero, we can form the substitution F • G by

(F • G)[U ] = π partition of U F[π] × Q∈π G[Q].
An object of the substitution may be interpreted as an F-object whose labels are substituted by G-objects. The transport along a bijection σ is defined by applying the induced map

σ : π → {σ(Q) | Q ∈ π}, Q → σ(Q)
of partitions to the F-object, and the restricted maps σ| Q with Q ∈ π to their corresponding G-objects. We will often write F(G) instead of F • G. Explicit formulas for the generating series and cycle index sums of the discussed constructions are summarized in Table 1.

OGF

Cycle index sum

i F i i Fi (x) i Z F i (x 1 , x 2 , . . .) F • G F(x) G(x) Z F (x 1 , x 2 , . . .)Z G (x 1 , x 2 , . . .) F • G Z F ( G(x), G(x 2 ), . . .) Z F (Z G (x 1 , x 2 , . . .), Z G (x 2 , x 4 , . . .), . . .)
Table 1: Relation between combinatorial constructions and generating series.

Symmetries of composite structures

By Lemma 5.1, we know that random unlabelled structures may be studied using random symmetries. The coupled automorphism in the random symmetry gives us additional information on the shape of the object, and hence serves as a starting point for a probabilistic analysis. In this context, we will often encounter the following operation for composing cycles.

Definition 5.2. Given a cyclic permutation (a 1 , . . . , a k ) and a number ≥ 1, we may take "identical" copies (a i 1 , . . . , a i k ), 1 ≤ i ≤ and form a k -cycle

(a 1 1 , . . . , a 1 , a 1 2 , . . . , a 2 , . . . , a 1 k , . . . , a k ).
Any automorphism of an F • G composite structure has only cycles of this form. The key idea is that such a composite symmetry is essentially composed out of an F-symmetry where each atom is endowed with a G-symmetry, such that symmetries belonging to a common cycle of the F-symmetry are isomorphic copies of each other:

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 that is an automorphism of the composite structure (F, (G Q ) Q∈π . That is, we require the permutation σ to permute the partition classes and induce an automorphism

σ : π → π, Q → σ(Q)
of the F-object F . Moreover, for any partition class Q ∈ π we require that the restriction σ|

Q : Q → σ(Q) is an isomorphism from G Q to G σ(Q) . For any cycle τ = (Q 1 , . . . , Q ) of the F-automorphism σ it follows that for all 1 ≤ i ≤ we have σ (Q i ) = Q i and hence the restriction σ | Q i : Q i → Q i is an automorphism of G Q i . Moreover, if we know (G Q 1 , σ | Q 1 ) and the maps σ| Q i = (σ| Q 1 ) i for 1 ≤ i ≤ -1, we can reconstruct the G-objects G Q 2 , . . . , G Q and the restriction σ| Q 1 ∪...∪Q . Here any k-cycle (a 1 , . . . , a k ) of the permutation σ | Q 1 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 σ| Q 1 ∪...∪Q . Thus any cycle ν of σ is of the form as in Definition 5.2 and corresponds to a cycle of the induced permutation σ whose length is a divisor of the length of ν.

Note that the maps σ| Q i carry information about the labelling, but not really about the structure of the symmetry, as all G-structure pertaining to a common cycle need to be isomorphic anyway. Up to relabelling, an F • G-symmetry is already fully described by its induced F-symmetry and a family of G-symmetries, one for each cycle of the F-symmetry: Proposition 5.3. If we are given an F-symmetry (m, σ m ) and for each of its cycles c a G-symmetry (G c , σ c ), then there is a canonical way to assemble an F • G symmetry out of these objects. Here each atom of c receives an identical copy of G c , and the cycles of σ c are cloned and composed as in Definition 5.2. Up to relabelling, any F • G-symmetry may be constructed in this way. Then the product σ of all composed cycles (formed by all choices of c and ν) 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 c of σ m we choose c(b) instead of b, then the resulting automorphism is given by the conjugation (id, c)σ(id, c) -1 instead of σ. But (id, c) is an automorphism of the F • G-structure C, hence the resulting symmetry (C, (id, c)σ(id, c) -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.

More details on this structural result are given in [11, Sec. 2.6.2], [26, Section 3] and [9, Section 4.3]. The main point for our purposes is to know that we may form an F • G-symmetry by taking an F-symmetry and for each of its cycles c precisely |c| identical copies of a G-symmetry, which we compose into a permutation by composing the clones of each cycle of the G-symmetry as in Definition 5.2.

Cycle pointing

When studying random graphs or other discrete structures, it is often convenient to select a root vertex. If the vertices are distinguishable by labels, this is easy and natural, as any labelled n-vertex object may be rooted in n different locations. However, if the structure has a non-trivial automorphism, then it corresponds to less than n pointed unlabelled structures, because pointing at two vertices in symmetric positions produces the same unlabelled structure. See for example Figure 2 for an illustration of the root locations in unlabelled trees.

In order to tackle this general enumerative problem, Bodirsky, Fusy, Kang and Vigerske [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF] constructed an unbiased pointing operator, such that each unlabelled structure of size n gives rise to n pointed unlabelled structures.

The cycle pointing operator

The cycle pointing operator was constructed in [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF] and maps a species G to the species G • such that the G • -objects over a set U are pairs (G, τ ) with G ∈ G[U ] and τ a marked cycle of an arbitrary automorphism of G. Here we count fixpoints as 1-cycles. The transport is defined by σ.(G, τ ) = (σ.G, στ σ -1 ). Any subspecies S ⊂ G • is termed cycle-pointed. The symmetric cycle-pointed species G ⊂ G • is defined by restricting to pairs (G, τ ) with τ a cycle of length at least 2.

A rooted symmetry of the cycle-pointed species S ⊂ G • is a quadruple ((G, τ ), σ, v) such that (G, τ ) is an S-object, σ is an automorphism of G, τ is a cycle of σ and v is an atom of the cycle τ . Its weight monomial is given by

w ((G,τ ),σ,v) = t s w (G,σ) (s 1 , s 2 , . . .)
with w (G,σ) denoting the weight of the symmetry (G, σ) and the length of the marked cycle τ . We may form the species RSym(S) of rooted symmetries of S. The pointed cycle index sum of S is given by

ZS (s 1 , t 1 ; s 2 , t 2 ; . . .) = (G,τ,σ,v) w (G,τ,σ,v) ∈ Q[[s 1 , t 1 ; s 2 , t 2 ; . . .]]
with the sum index ranging over the set n∈N 0 RSym(S) [n]. Let G • ( ) ⊂ G • denote the subspecies given by all cycle pointed objects whose marked cycle has length . It follows from the definition of the pointed cycle index sum that [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Lem. 14]). Let U be a finite set with n elements and fix an arbitrary linear order on U .

ZG • ( ) = t ∂ ∂s Z G . Since G • = ∞ =1 G • ( ) it follows that ZG • = ∞ =1 t ∂ ∂s Z G and ZG = ∞ =2 t ∂ ∂s Z G . (6.1) Lemma 6.1 ([
1) The following map is bijective:

RSym(S)[U ] → Sym(S)[U ], M = ((G, τ ), σ, v) → ((τ 1-(M ) .G, τ ), στ (M )-1 )
with (M ) defined as follows: let k denote the length of the cycle τ and u its smallest atom. Let 0 ≤ (M ) ≤ k -1 be the unique integer satisfying v = τ (M ) .u.

2) Any unlabelled cycle-pointed S-object m of size n corresponds to precisely n! rooted c-symmetries from RSym(S)[U ] having the property that the isomorphism type of the underlying S-object equals m.

In particular, the pointed cycle index sum relates to the ordinary generating series by S(x) = ZS (x, x; x 2 , x 2 ; . . .). (6.2)

Moreover, if we draw an element from RSym(S)[n] uniformly at random, then the isomorphism class of the corresponding cycle pointed structure is uniformly distributed among all unlabelled cycle-pointed S-objects of size n. The main point of the cycle-pointing construction is evident from the following fact.

Lemma 6.2 [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Thm. 15]). Any unlabelled G-structure m of size n may be cycle-pointed in precisely n ways, that is, there exist precisely n unlabelled G • -structures with corresponding G-structure m.

Considered from a probabilistic viewpoint, this means that if we draw an unlabelled G • -structure of size n uniformly at random, then the underlying G-object is also uniformly distributed. Moreover, Lemma 6.1 tells us that in order to sample the G • -object we may sample a rooted symmetry of this size uniformly at random.

Studying the random G • -object might be easier due to the additional information given by the marked cycle. Moreover, Lemma 6.2 implies that

G• (z) = z d dz G(z). (6.3)
By Equations (6.1) and (5.2) the pointed cycle index sum of the species SET is given by

ZSET • = ∞ =1 t ∂ ∂s Z SET (s 1 , s 2 , . . .) = exp ∞ i=1 s i /i ∞ =1 t . (6.4)
As ZSET = ZSET • (s 1 , 0; s 2 , t 2 ; . . .), the cycle index sum for ZSET is given as in Equation (6.4), but with the sum index ranging from 2 to infinity.

Operations on cycle pointed species

Cycle pointed species come with a set of new operations introduced in [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]. If S ⊂ G • is a cycle-pointed species and H a species, then the pointed product S H is the subspecies of (G • H) • given by all cycle-pointed objects such that the marked cycle consists of atoms of the G-structure and the G-structure together with this cycle belongs to S. The corresponding pointed cycle index sum is given by

ZS H = ZS Z H . (6.5)
If H[∅] = ∅ we may form the pointed substitution S H ⊂ (G • H) • as follows. Any (G • H) • -structure P has a marked cycle τ of some automorphism σ. By the discussion in Section 5.4, this cycle corresponds to a cycle on the G-structure of P which does not depend on the choice of σ. Hence the G-structure of P is cycle-pointed and we say P belongs to S H if and only if this cycle pointed G-structure belongs to S. The corresponding pointed cycle index sum is given by ZS H = ZS (Z H (s 1 , s 2 , . . .), ZH • (s 1 , t 1 ; s 2 , t 2 ; . . .); Z H (s 2 , s 4 , . . .), ZH • (s 2 , t 2 ; s 4 , t 4 ; . . .); . . .). (6.6)

The sum i∈I S i of a family of cycle pointed species (S i ) i∈I is defined as the sum of regular species in Section 5.3. Its pointed cycle index sum satisfies

Z i∈I S i = i∈I ZS i . (6.7)

(Pólya-)Boltzmann samplers

Boltzmann samplers were introduced in [START_REF] Duchon | Random sampling from Boltzmann principles[END_REF][START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF][START_REF] Flajolet | Boltzmann sampling of unlabelled structures[END_REF] and generalized to Pólya-Boltzmann samplers in [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]. We briefly discuss the background to the extend required in our proofs.

Boltzmann models

The Pólya-Boltzmann model was introduced in [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]: Suppose that we are given a sequence of real numbers s 1 , s 2 , . . . ≥ 0 such that 0 < Z F (s 1 , s 2 , . . .) < ∞. Then we may consider the probability distribution on the set ∞ n=0 Sym(F)[n] that assigns the probability weight

w (F,σ) Z F (s 1 , s 2 , . . .) -1 = s σ 1 1 s σ 2 2 • • • n! Z F (s 1 , s 2 , . . .) -1
for each n and symmetry (F, σ) ∈ Sym(F) [n]. Here σ i denotes the number of i-cycles of the permutation σ. The corresponding Pólya-Boltzmann sampler is denoted by ΓZ F (s 1 , s 2 , . . .), and simply refers to a random variable following this distribution, possibly with a description on how to sample it. When describing a sampling procedure the pseudo-code notation

(F, σ) ← ΓZ F (s 1 , s 2 , . . .) (7.1)
means that we let (F, σ) denote a random F-symmetry that is independent from all previously considered random variables and sampled according to a Pólya-Boltzmann distribution for the species F with parameters (s i ) i .

Remark 7.1. In the special case (s i ) i = (x i ) i for some x > 0, for each fixed n it holds that all outcomes with size n are equally likely. This means that ΓZ F (x, x 2 , . . .) conditioned on having a given deterministic size n follows the uniform distribution. By Lemma 5.1 the n-sized symmetries from Sym(F)[n] are in a n : 1 relation to the unlabelled n-sized F-objects. Thus, the F-object corresponding to the conditioned Pólya Boltzmann sampler is uniformly distributed among all n-sized F-objects.

A Pólya-Boltzmann model for random cycle pointed species is given by a probability measure on random rooted symmetries: Let S be a cycle-pointed species. Given real non-negative numbers (s i , t i ) i≥1 such that 0 < ZS (s 1 , t 1 ; s 2 , t 2 ; . . .) < ∞ we may consider the probability measure on the set ∞ n=0 RSym(S)[n] that assigns probability weight w ((G,τ ),σ,v) ZS (s 1 , t 1 ; s 2 , t 2 ; . . .

) -1 = t s σ 1 1 • • • s σ -1 -1 s σ -1 s σ +1 +1 s σ +2 +2 • • • n! ZS (s 1 , t 1 ; s 2 , t 2 ; . . .)
for each n to each rooted symmetry ((G, τ ), σ, v) ∈ RSym(S) [n]. Here denotes the lengths of the marked cycle τ . The corresponding Pólya-Boltzmann sampler of this model is denoted by Γ ZS (s 1 , t 1 ; s 2 , t 2 ; . . .), and we use a similar notation as in (7.1) when describing sampling procedures.

Remark 7.2. In the special case (s i , t i ) i = (x i , x i ) i for some x > 0, for each fixed n we have that all outcomes with size n are equally likely. Hence conditioning Γ ZS (x, x; x 2 , x 2 ; . . .) on having size n yields the uniform distribution on RSym(F) [n]. By Lemma 6.1 we know that the rooted symmetries from RSym(F) [n] are in an n : 1 relation to the unlabelled n-sized cycle-pointed S-objects. Thus, the S-object corresponding to the conditioned Pólya-Boltzmann sampler follows the uniform distribution among all n-sized cycle pointed S-objects.

Rules for the construction of Boltzmann samplers

The sampling procedures described in the present exposition were established in [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Prop. 38,Prop. 43].

Pólya-Boltzmann samplers

Let F denote a species and (s i ) i≥1 non-negative real numbers such that 0 < Z F (x 1 , x 2 , . . .) < ∞.

Products

Suppose that F = F 1 • F 2 is the product of two species F 1 and F 2 . Then for any finite set U there is a bijection between the set Sym(F)[U ] and pairs (S 1 , S 2 ) such that S i is an F i -symmetry for all i and the label sets of the S i partition the set U . This is due to the fact, that given an F-symmetry

((F 1 , F 2 ), σ) ∈ Sym(F)[U ] the permutation σ must leave the label set Q i of the F i -object F i invariant and satisfy σ| Q i .F i = F i , that is (F i , σ| Q i ) ∈ Sym(F i )[Q i ].
The following procedure is a Pólya-Boltzmann sampler for the species F.

1. For i = 1, 2 set S i ← ΓZ F i (s 1 , s 2 , . . .).
By the bijection for the symmetries of products, the pair (S 1 , S 2 ) corresponds to an F-symmetry (F, σ) over the (exterior) disjoint union U of the label-sets of the S i .

2. Make a uniformly at random choice for a bijection ν from U to the set of integers [n] with n denoting the size of U . Return the relabelled symmetry ν.(F, σ) = (ν.F, νσν -1 ).

Substitution

Suppose that F = G • H with H[∅] = ∅ is the composition of a species G with another species H. The symmetries of the substitution were discussed in detail in Section 5.4. The following procedure is a Pólya-Boltzmann sampler for F.

1. Set (G, σ) ← ΓZ G (Z H (s 1 , s 2 , . . .), Z H (s 2 , s 4 , . . .), . . .).

That is, let (G, σ) denote a random G-symmetry that follows a Pólya-Boltzmann distribution with parameters Z H (s 1 , s 2 , . . .), Z H (s 2 , s 4 , . . .), . . ..

2.

For each cycle τ of σ let |τ | denote its lengths and set

(H τ , σ τ ) ← ΓZ H (s |τ | , s 2|τ | , . . .).
That is, the symmetries (H τ , σ τ ), τ cycle of σ, are independent (conditional on σ) and follow Pólya-Boltzmann distributions.

3. For each cycle τ , make |τ | identical copies copies of (H τ , σ τ ) and assemble an F-symmetry (F, γ) out of (G, σ) and the copies of the (H τ , σ τ ) as described in Proposition 5.3.

4.

Choose bijection ν from the vertex set of (F, γ) to an appropriate sized set of integers [n] and return the relabelled symmetry ν.(F, γ) = (ν.F, νγν -1 ).

Pólya-Boltzmann samplers for cycle-pointed species

In the following, we suppose that F is a cycle pointed species and that s 1 , t 1 , s 2 , t 2 , . . . are non-negative real numbers such that 0 < ZF (s 1 , t 1 ; s 2 , t 2 ; . . .) < ∞.

Cycle pointed products

Suppose that F = G H with G a cycle-pointed species and H a species. Then for any finite set U there is a canonical choice for a bijection between the set RSym(F)[U ] and tuples (S 1 , S 2 ) with S 1 a rooted symmetry of G, S 2 a symmetry of G, such that the label sets of S 1 and S 2 form a partition of U . The following procedure is a Pólya-Boltzmann sampler for F.

1. Set S 1 ← Γ ZG (s 1 , t 1 ; s 2 , t 2 ; . . .).

Set

S 2 ← ΓZ H (s 1 , s 2 , . . .).

3. Let U denote the exterior disjoint union of the label sets of S 1 and S 2 . The tupel (S 1 , S 2 ) corresponds to a rooted symmetry S over the set U .

4. Make a uniformly at random choice of a bijection ν from U to the set of integers [n] with n denoting the size of U . Return the relabelled rooted symmetry ν.S.

Cycle pointed substitution

Suppose that F = G H with G cycle-pointed and H[∅] = ∅. The symmetries of the substitution were discussed in detail in Section 5.4. The following procedure is a Pólya-Boltzmann sampler for F.

1. Set ((G, τ 0 ), σ, v 0 ) ← Γ ZG (h 1 , h1 ; h 2 , h2 ; . . .)
with parameters h i = Z H (s i , s 2i , . . .) and hi = ZH • (s i , t i ; s 2i , t 2i ; . . .).

2.

For each unmarked cycle τ of σ let |τ | denote its lengths and set

(H τ , σ τ ) ← ΓZ H (s |τ | , s 2|τ | , . . .).
3. For the marked cycle τ 0 set

((H τ 0 , c τ 0 ), σ τ 0 , v τ 0 ) ← ΓZ H • (s |τ 0 | , t |τ 0 | ; s 2|τ 0 | , t 2|τ 0 | ; . . .).
4. Assemble an F-symmetry (F, γ) out of the G-symmetry (G, σ) and the H-symmetries (H τ , σ τ ) according to the construction of Proposition 5.3.

Let c denote the cycle that gets composed out of the |τ 0 | copies of the cycle c τ 0 in this construction. The marked vertex v τ 0 has |τ 0 | copies (one for each atom of τ 0 ) and we let u denote the copy that corresponds to the marked atom v 0 of τ 0 . Thus

((F, c), γ, u)
is a rooted symmetry of F.

5.

Choose a bijection ν from the vertex set of ((F, c), γ, u) to an appropriate sized set of integers

[n] and return the relabelled rooted symmetry ν.((F, c), γ, u) = ((ν.F, νcν -1 ), νγν -1 , ν.u).

Random multisets

If F is a species of structures with F[∅] = ∅, then unlabelled SET • F-objects are termed multisets. They consist of unordered collections of unlabelled F-objects where each object is allowed to appear multiple times. The following preliminary observation is a consequence of a more general result established by Barbour

[z n ] F(z) = f (n)n -β ρ n
for some constants ρ > 0 and β > 1, and a function f that varies slowly at infinity. Then the largest component in a uniform n-sized multiset of unlabelled F-structures has size n + O p (1).

Proof of the main theorems

Throughout this section, let Ω be a set of positive integers containing the number 1 and at at least one integer equal or greater than 3. We let F denote the species of unrooted trees and F Ω its subspecies of trees with vertex degrees in the set Ω. Analogously, we let A denote the species of rooted trees and A Ω * the subspecies of rooted trees with vertex outdegrees in the shifted set Ω * = Ω -1. In the following we will always assume that n denotes an integer satisfying n ≡ 2 mod gcd(Ω * ) and n large enough such that trees with n vertices and vertex degrees in the set Ω exist. Let ρ denote the radius of convergence of the generating series ÃΩ * (z).

We let (T n , τ n ) denote a random cycle-pointed tree drawn uniformly from the unlabelled F • Ω -objects of size n. As discussed in Lemma 5.1, this implies that T n is the uniform random unlabelled unrooted tree with n vertices and vertex degrees in the set Ω. Moreover, let A n-1 a random rooted tree drawn uniformly from the unlabelled A Ω * -objects of size n -1.

We let c Ω * > 0 denote the constant from Equation (3.1) such that the uniformly drawn unlabelled rooted tree A n-1 satisfies

(A n-1 , c Ω * n -1/2 d A n-1 ) d -→ (T e , d Te )
with respect to the Gromov-Hausdorff metric. Moreover, let ÂΩ * denote the infinite rooted tree from Equation (4.1) with d TV (V kn (A n-1 , u n-1 ), V kn ( ÂΩ * )) → 0 for every sequence k n = o( √ n), with u n-1 denoting a uniformly at random selected vertex of A n-1 .

Decomposition of cycle-pointed trees

Given a cycle pointed tree (T, τ ) such that the marked cycle τ has length at least 2 we may consider its connecting paths, i.e. the paths in T that join consecutive atoms of τ . Any such path has a middle, which is either a vertex if the path has odd length, or an edge if the path has even length. All connecting paths have the same lengths and by [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Claim 22] they share the same middle, called the center of symmetry. See Figure 4 for an illustration. The cycle pointing decomposition given in [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Prop. 25] splits the species F • Ω into three parts,

F • Ω X • (SET Ω • A Ω * ) + SET {2} A Ω * + (SET Ω A Ω * ) X .
(9.1)

Here S := X • (SET Ω • A Ω * )
corresponds to the trees with a marked fixpoint and the other summands to trees with a marked cycle of length at least two. More specifically,

E := SET {2} A Ω *
corresponds to the symmetric cycle pointed trees whose center of symmetry is an edge and

V := (SET Ω A Ω * ) X
to those whose center of symmetry is a vertex.

Enumerative properties

We start by collecting some basic enumerative facts. The following preliminary observation summarizes enumerative properties of Pólya trees with vertex degree restrictions. i) The radius of convergence ρ of the series ÃΩ * (z) satisfies 0 < ρ < 1 and ÃΩ * (ρ) < ∞.

ii) There is a positive constant d Ω * such that

[z m ] ÃΩ * (z) ∼ d Ω * m -3/2 ρ -m
as the number m ≡ 1 mod gcd(Ω * ) tends to infinity.

iii) For any subset Λ ⊂ N the series

E Λ (z, w) = zZ SET Λ (w, ÃΩ * (z 2 ), ÃΩ * (z 3 ), . . .) satisfies E Λ (ρ + , ÃΩ * (ρ) + ) < ∞
for some > 0.

In [START_REF] Bodirsky | Boltzmann samplers, Pólya theory, and cycle pointing[END_REF]Prop. 24] the cycle-pointing decomposition was used in order to provide a new method for determining the asymptotic number of unlabelled unrooted trees. This may be extended to the case of vertex degree restrictions. A detailed justification is given in Section 9.5 below.

Proposition 9.2. The series FΩ (z) and ÃΩ * (z) both have the same radius of convergence ρ. Moreover, the following statements hold. i) There is a constant d Ω * such that

[z n ] FΩ (z) ∼ d Ω * ρ -n n -5/2
as n ≡ 2 mod gcd(Ω * ) tends to infinity. ii) For any set Λ ⊂ N the series

F Λ (z, w) = ZSET Λ (w, Õ Ω * (z); ÃΩ * (z 2 ), Õ Ω * (z 2 ); ÃΩ * (z 3 ), Õ Ω * (z 3 ); . . .)
satisfies F Λ (ρ + , ÃΩ * (ρ) + ) < 0 for some > 0.

iii) The ordinary generating series

SET {2} A Ω * (z) = Õ Ω * (z 2 )
has radius of convergence greater than ρ.

Approximation arguments

We are going to treat the classes S, E, and V separately.

9.3.1

The class E of symmetric cycle pointed trees whose center of symmetry is an edge

The event (T n , τ n ) ∈ E is so unlikely, that we will be able to neglect this case:

Lemma 9.3. There are constants C, c > 0, such that for all n

P ((T n , τ n ) ∈ E) ≤ C exp(-cn).
Geometrically speaking, this can be explained by the fact that any unlabelled cycle pointed tree from E corresponds bijectively to a cycle pointed Pólya tree from A • Ω * having precisely half of its size. Compare with Figure 5. The number of such objects is roughly given by ρ n/2 , while the number of all cycle pointed trees in F • Ω is roughly given by ρ n , which is exponentially larger.

S = X • (SET Ω • A Ω * )
objects of size n. Then the following properties hold.

a) There are constants C, c > 0 such that for all n and x ≥ 0 it holds that

P (D(T n ) ≥ x) ≤ C exp(-cx 2 /n).
b) There is a random number K n = n + O p (1) ≤ n and a coupling of S n with a partition into two rooted subtrees B n , C n that intersect only in their roots and satisfy C n

(d) = A Kn .
The reason for this is, that each unlabelled S = X • (SET Ω • A Ω * ) cycle pointed trees corresponds bijectively to a Pólya tree, in which each vertex degree must lie in Ω. That is, the outdegree of the root lies in Ω, and the outdegrees of all remaining vertices lie in Ω * . Compare with Figure 6.

P (D(V n ) ≥ x) ≤ C exp(-cx 2 /n).
b) There is a random number K n = n + O p (1) ≤ n and a coupling of V n with a partition into two rooted subtrees B n , C n that intersect only in their roots and satisfy C n

(d) = A Kn .
The key point is that any unlabelled cycle pointed tree from V corresponds to a Pólya tree A from A Ω * where each non-root vertex must have outdegrees in Ω * , together with a number K of identical copies of a symmetrically cycle pointed Pólya tree A • from A Ω * , such that the sum of the root degrees of A and the K copies of A • lies in Ω. Compare with Figure 7. Having the approximation results from Section 9.3 at hand, we may verify our main results.

Proof of Theorem 1.3. Lemma 9.3 implies that the total variation distance between the unrooted tree T n and a mixture of random S-structures and V-structures is exponentially small. Lemmas 9.4 and 9.5 imply that both S n and V n look like a large randomly sized Pólya tree with a stochastically bounded rest. Consequently their mixture looks like a large randomly sized Pólya tree with a small rest which is a mixture of the two stochastically bounded small trees corresponding to S n and V n . This completes the proof.

Proof of Theorem 1.2. Theorem 1.3 reduces the problem to studying a certain random tree Tn , that consists of a K n = n + O p (1)-sized random Pólya tree A Kn with a small tree B n attached to its root. For the local limit, let u n denote a uniformly at random drawn vertex of Tn , and let k n = o( √ n) denote a given sequence. It is clear that the random vertex u n lies with high probability in the subtree A Kn , and that, conditioned on this event, it is uniformly distributed among its vertices. Note that

K n = n + O p (1) implies that with high probability K n ≥ n -log n → ∞ and k n = o( √ n) = o( √ K n ).
By Equation (4.1) it follows that the radius k n neighbourhood of a random vertex in A Kn is close in total variation to the k n neighbourhood of the infinite random tree ÂΩ * , and that a random vertex in A Kn has with high probability height strictly larger than k n . In particular, with high probability the neighbourhood does not contain the root-vertex of A Kn and is hence not influenced by the small tree B n that gets attached to the root of A Kn to form the tree Tn . This readily verifies that

d TV (V kn ( Tn , u n ), V kn ( ÂΩ * )) → 0,
and hence completes the proof.

Proof of Theorem 1.1. For the scaling limit, it suffices by Theorem 1.3 to consider the tree Tn , that consists of two rooted trees glued together at their root vertices, specifically a K n = n + O p (1)-sized random Pólya tree A Kn and a small tree B n . As |B n | = O p (1) it follows that with high probability it holds that, say, |B n | ≤ n 1/4 . Hence

d GH ( Tn / √ n, A Kn / √ n) p -→ 0. (9.2)
Note that K n d -→ ∞ and the limit in (3.1) imply that

c Ω * A Kn / K n d -→ T e . (9.3)
In particular, D(A

Kn ) = O p ( √ K n ) and hence d GH (A Kn / √ n, A Kn / K n ) ≤ O p (1)(1 -K n /n) p -→ 0.
Together with Equation (9.2) this implies that

d GH ( Tn / √ n, A Kn / K n ) p -→ 0
and by the limit in (9.3) the scaling limit for Tn follows.

The inclined reader may note that the arguments above work just as fine for the Gromov-Hausdorff-Prokhorov metric with respect to the uniform measure on the leaves or on all vertices, if we build on Gromov-Hausdorff-Prokhorov convergence for the random Pólya trees, which was established in [START_REF] Haas | Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees[END_REF] for the most important cases of vertex outdegree restrictions.

For the tail bound of the diameter, note that it suffices to show such a bound for P (D(T n ) ≥ x) when x ≤ n. By Lemmas 9.3, 9.4 and 9.5 it follows that there are constants C i , c i > 0, for i = 1, 2, 3, such that

P (D(T n ) ≥ x) ≤ B∈{E,S,V} P (D(T n ) ≥ x | (T n , τ n ) ∈ B) P ((T n , τ n ) ∈ B) ≤ C 1 exp(-c 1 n) + 3 i=2 C i exp(-c i x 2 /n).
As we assumed that x ≤ n, it holds that

exp(-c 1 n) ≤ exp(-c 1 x 2 /n).
Hence for a suitable choice of constants C, c > 0, it follows that

P (D(T n ) ≥ x) ≤ C exp(-cx 2 /n)
for all n and x ≥ 0.

Proof of the enumerative observation Proposition 9.2

Proof of Proposition 9.2. We start with Claim iii). By the definition of the SET-species and the pointed cycle index sum it holds that ZSET {2} = t 2 . By Equations (6.6) and (6.2) it follows that

SET {2} A Ω * (z) = ZSET {2} A Ω * (z, z; z 2 , z 2 ; . . .) = Õ Ω * (z 2 ).
By Proposition 9.1 we know that 0 < ρ < 1. Hence the series

Õ Ω * (z) = z d dz ÃΩ * (z)
has radius of convergence √ ρ > ρ. This proves Claim iii).

We proceed with Claim ii). The series ZSET Λ is dominated coefficient-wise by the series ZSET , which by Equation (6.4) is given by

ZSET (s 1 , t 1 ; s 2 , t 2 ; . . .) = exp ∞ k=1 s k /k ∞ i=2 t i . It follows that F Λ (z, w) is dominated coefficient-wise by exp w + ∞ k=2 ÃΩ * (z k )/k ∞ i=2 Õ Ω * (z i ).
Since 0 < ρ < 1 and ÃΩ * (ρ) < ∞ by Proposition 9.1, this series is finite for z = ρ+ and w = ÃΩ * (ρ)+ , if > 0 is sufficiently small. This proves Claim ii).

In order to prove Claim i), note that by Equation ( 6.3) it holds that F• Ω (z) = z d dz FΩ (z). Hence it suffices to study the ordinary generating series of the species F • Ω . By the cycle pointing decomposition in Equation (9.1) it holds that

F • Ω X • (SET Ω • A Ω * ) + SET {2} A Ω * + (SET Ω A Ω * ) X .
By the relation of pointed cycle index sums with ordinary generating series given in Equation (6.2) and the rules (6.7), (6.5), and (6.6) for cycle index sums of the the sum, product and substitution, it follows that

F• Ω (z) = zh(z, ÃΩ * (z)) with h(z, w) = E Ω (z, w) + F Ω (z, w) + Õ Ω * (z 2 )/z.
Here we let E Ω be defined as in Proposition 9.1. The power series h(z, w) has non-negative coefficients. By Claims i) and ii) and Proposition 9.1 it holds furthermore that h( ÃΩ * (ρ) + , ρ + ) < ∞ for some > 0. This means that the behaviour of the series ÃΩ * (z) at its singularities on the circle |z| = ρ determines the asymptotic growth of the coefficients of the series F• Ω (z). Let us make this precise. A rooted tree with vertex outdegrees in the set Ω * consists of a root-vertex together with an unordered list of fringe subtrees dangling from it, such that the total number of fringe subtrees lies in the set Ω * , and each of these trees belongs to the species A Ω * . In the language of combinatorial species, this may concisely be expressed by

A Ω * X • SET Ω * (A Ω * ).
By Equation ( 1) and the rules for the interplay of the cycle index sums with the operations on species summarized in Table 1 it follows that

ÃΩ * (z) = E Ω * (z, ÃΩ * (z)). By Proposition 9.1 it holds that E Ω * (ρ + , ÃΩ * (ρ) + ) < ∞
for some > 0. By a general enumerative result by Bell, Burris and Yeats [7, Lem. 26, Cor. 12] and the rotational symmetry ÃΩ * (ζz) = ζ ÃΩ * (z) it follows that the series ÃΩ * (z) has dominant singularities (all of square-root type) precisely at the rotated points

ζ k , k = 0, . . . , d -1 with ζ = e 2πi d and d = gcd(Ω * ).
By the asymptotic expansion of the coefficients of ÃΩ * (z) in Proposition 9.1 and a singularity analysis result for functions with multiple dominant singularities [21, Thm. VI.5] it follows that there is a constant d > 0 with

[z m ]h(z, ÃΩ * (z)) ∼ d m -3/2 ρ -m (9.4)
as m ≡ 1 mod d becomes large. Consequently,

[z n ] FΩ (z) ∼ n -1 [z n ] F• Ω (z) ∼ d Ω * n -5/2 ρ -n
for some constant d Ω * > 0 as n ≡ 2 mod d becomes large.

9.6 Proofs of the approximation arguments: Lemmas 9.3, 9.4, and 9.5

Cycle pointed trees whose cycle center is an edge

Proof of Lemma 9.3. The probability for this event is given by the ratio of unlabelled cycle pointed trees of E with n vertices, and the unlabelled cycle pointed trees in F Ω with n vertices. Hence

P ((T n , τ n ) ∈ E) = [z n ] Ẽ(z) [z n ] F• (z) .
By Proposition 9.2, iii), the radius of convergence of the ordinary generating series Ẽ(z) is strictly larger than the radius of convergence ρ of F• (z). This yields the claim.

Cycle pointed trees whose cycle center is a fixpoint

It holds that

S = X • (SET Ω • A Ω * ) X • (SET Ω • A Ω * ),
hence we do not require cycle pointing techniques in this case. Let (S n , σ) be drawn uniformly at random from the set Sym(S) [n]. Let π n denote the corresponding partition. By the discussion in Section 5.4, σ induces an automorphism σ :

π n → π n of the SET Ω -object. Moreover, let F n ⊂ π n denote the fixpoints of σ, f n = |F n | their number and for each fixpoint Q ∈ F n let (A Q , σ Q ) denote the corresponding symmetry from Sym(A Ω * )[Q].
Let H n denote the total size of the trees dangling from cycles with length at least 2. We are going to make the following observations. Lemma 9.6. The following statements hold.

1) There are constants C 1 > 0 and 0 < γ < 1 such that for all n and x ≥ 0 we have that

P (H n ≥ x) ≤ C 1 n 3/2 γ x and P (f n ≥ x) ≤ C 1 n 3/2 γ x .
2) The maximum size of the individual trees corresponding to the fixpoints of σ satisfies

max Q∈Fn |A Q | = n + O p (1)
.

3) There is a constant

C 2 > 0 such that E [f n ] ≤ C 2 for all n.
We are first going to argue how these claims suffice to prove Lemma 9.4:

Proof of Lemma 9.4. We start with Claim a), the tail bound for the diameter. First, it suffices to verify such a bound uniformly for all n and

√ n ≤ x ≤ n. If D(S n ) ≥ x, then it must hold that H n ≥ x/2 or max Q∈Fn H(A Q ) ≥ x/2 -1. Hence P (D(S n ) ≥ x) ≤ P (H n ≥ x/2) + P max Q∈Fn H(A Q ) ≥ x/2 -1 . (9.5)
By Claim 1) of Lemma 9.6, we know that there are constants C 1 > 0 and 0 < γ < 1 with

P (H n ≥ x/2) ≤ C 1 n 3/2 γ x/2 .
Hence there are constants C 4 , c 4 > 0 such that for all n and √ n ≤ x ≤ n it holds that Hence

P (H n ≥ x/2) ≤ C 4 exp(-c 4 x 2 /n). ( 9
P max Q H(A Q ) ≥ x/2 -1 ≤ C 5 exp(-c 5 x 2 /n) F P (F n = F ) |F | ≤ E [f n ] C 5 exp(-c 5 x 2 /n). (9.7)
By 3) it holds that

E [f n ] ≤ C 2
for all n. Thus, by Equations (9.5) and (9.6) it holds for some C 6 , c 6 > 0 that

P (D(S n ) ≥ x) ≤ C 4 exp(-c 4 x 2 /n) + C 2 C 5 exp(-c 5 x 2 /n) ≤ C 6 exp(-c 6 x 2 /n)
uniformly for all n and √ n ≤ x ≤ n. This verifies Claim a). We continue with Claim b), the approximation argument. Make a canonical choice of a partition class of F n with maximal size and let X n denote the corresponding tree. Then, by Lemma 5.1, for all It remains to verify Lemma 9.6.

(X n | |X n | = ) (d) = A . ( 9
Proof of Lemma 9.6. We start with the first claim. By the discussion of Boltzmann samplers in Section 7.2.1 regarding the product and substitution operation, the probability generating function of H n is given by E w Hn = [z n-1 ]Z SET Ω ( ÃΩ * (ρz), ÃΩ * ((ρwz) 2 ), ÃΩ * ((ρwz) 3 ), . . .) [z n-1 ]Z SET Ω ( ÃΩ * (ρz), ÃΩ * ((ρz) 2 ), . . .) . (9.9)

Let us justify Equation (9.9) in more detail: By the product rule in Section 7.2.1 it suffices, to study (n -1)-sized symmetries of SET Ω • A Ω * . The substitution rule in Section 7.2.1 tells us that a Boltzmann distributed symmetry of this composition with parameters (ρ i ) i≥1 is obtained by first drawing a Pólya-Boltzmann distributed SET Ω -symmetry with parameters ( ÃΩ * (ρ i )) i≥1 , and then for each j ≥ 1 and each j-cycle of the symmetry an unlabelled Boltzmann distributed symmetry of A Ω * with parameters (ρ ij ) i≥1 , of which i identical copies are attached to the SET Ω -symmetry. Given a k ∈ Ω sized permutation ν, the probability for the SET Ω -symmetry to assume this permutation is given by

ÃΩ * (ρ) ν 1 • • • ÃΩ * (ρ k ) ν k k! SET Ω • A Ω * (ρ) (9.10)
Conditioned on this event, the probability generating function for the size of the resulting object is given by

ÃΩ * (ρz) ÃΩ * (ρ) ν 1 ÃΩ * ((ρz) 2 ) ÃΩ * (ρ 2 ) ν 2 • • • ÃΩ * ((ρz) k ) ÃΩ * (ρ k ) ν k . ( 9.11)
The exponents in the arguments are due to the fact that we attach i identical copies of each tree corresponding to an i-cycle. If we additionally want to keep track of the volume of the trees corresponding to cycles with length at least 2, we may form the corresponding bivariate probability generating function where w corresponds to this parameter and z to the total size by ÃΩ * (ρz) ÃΩ * (ρ)

ν 1 ÃΩ * ((ρwz) 2 ) ÃΩ * (ρ 2 ) ν 2 • • • ÃΩ * ((ρwz) k ) ÃΩ * (ρ k ) ν k . ( 9.12)
Multiplying (9.10) and (9.12) and summing over all outcomes that correspond to objects with size n -1 yields

[z n-1 ]Z SET Ω ( ÃΩ * (ρz), ÃΩ * ((ρwz) 2 ), ÃΩ * ((ρwz) 3 ), . . .) SET Ω • A Ω * (ρ) . (9.13)
Likewise multiplying (9.10) with (9.11) and summing up in the same way yields

[z n-1 ]Z SET Ω ( ÃΩ * (ρz), ÃΩ * ((ρz) 2 ), . . .) SET Ω • A Ω * (ρ) . (9.14)
The quotient of (9.13) and (9.14) is the probability generating function for the random number H n , and the expression obtained in this way agrees with Equation (9.9). Having verified Equation (9.9) we proceed with the argument. Since 1 ∈ Ω we may bound the denominator in (9.9) from below by [z n-1 ] ÃΩ * (ρz), and by Proposition 9.1 we have that

[z n-1 ] ÃΩ * (ρz) ∼ Cn -3/2 (9.15)
for some constant C > 0 as n ≡ 2 mod gcd(Ω * ) tends to infinity. Moreover, for all n the polynomial in the indeterminate w in the numerator is dominated coefficient wise by the series Z SET Ω ( ÃΩ * (ρ), ÃΩ * ((ρw) 2 ), . . .)

which by Proposition 9.1 has radius of convergence strictly greater than 1. In particular we have that

k≥x [w k ]Z SET Ω ( ÃΩ * (ρ), ÃΩ * ((ρw) 2 ), . . .) = O(γ x )
for some constant 0 < γ < 1. Hence there is a constant C such that

P (H n ≥ x) ≤ C n 3/2 γ x
for all n and x. By the discussion of Boltzmann samplers in Section 7.2.1 regarding the product and substitution operation, the probability generating function for the random number f n is given by

E w fn = [z n-1 ]Z SET Ω (w ÃΩ * (ρz), ÃΩ * ((ρz) 2 ), . . .) [z n-1 ]Z SET Ω ( ÃΩ * (ρz), ÃΩ * ((ρz) 2 ), . . .) . (9.16)
The corresponding bound for the event f n ≥ x follows by the same arguments as for the parameter H n . This proves Claim 1). We proceed with showing Claim 2). If Ω = N, then we may apply Lemma 8.1 to obtain that the largest component in a random (n -1)-sized multiset of unlabelled A Ω * -objects has size n + O p [START_REF] Abraham | Excursion theory for Brownian motion indexed by the Brownian tree[END_REF]. By Claim 1) it follows that with high probability H n ≤ log 2 n. Thus the largest component must correspond to a fixpoint, verifying Claim 2) for this special case. In order to treat the general case, it suffices by similar arguments to show that the largest component in a random (n -1)-sized unlabelled SET Ω • A Ω * -object has size n + O p (1). However, we cannot apply Lemma 8.1 directly, and hence argue as follows.

We need to show that for any sequence t n → ∞ the probability for all components in the random SET Ω • A Ω * -object to have size at most n -t n tends to zero. Using analogous arguments as in the justification of Equation (9.9), we may express this probability by the product of the normalizing factor ([z n-1 ]Z SET Ω ( ÃΩ * (ρz), ÃΩ * ((ρz) 2 ), . . .)) -1 (9.17) with the expression

k∈Ω 1 k! ν (a ij ) i,j   z n-1 i,j x a ij ij   i,j ÃΩ * ((ρz) i x ij ). (9.18)
Here the sum index ν ranges over all permutations of the set [k]. The indices (a ij ) i,j range over all families of numbers a ij with 1 ≤ i ≤ n -1, 1 ≤ j ≤ ν i , and such that a ij ≤ n -t n for all i, j and

1≤i≤n-1 1≤j≤ν i ia ij = n -1.
The indices i, j of the product range over all pairs of integers with 1 ≤ i ≤ n -1 and 1 ≤ j ≤ ν i . Applying a standard result for the singularity analysis of functions with multiple dominant singularities [21, Thm. VI.5] we obtain analogously as in the justification of Equation (9.4) that the factor in Equation (9.17) is asymptotically equivalent to n 3/2 times a constant. Thus, showing that the largest component in a random unlabelled n -1-sized SET Ω • A Ω * -object has size n + O p (1) is actually equivalent to showing that the expression in (9.18) multiplied by n 3/2 tends to zero as n ≡ 2 mod gcd(Ω * ) becomes large. Consider the species ĀΩ * where for each k ∈ N 0 we set ĀΩ * [k] = A Ω * [k -] for the smallest integer ≥ 0 satisfying k -∈ Ω * . Hence A Ω * is a subspecies of ĀΩ * , and ÃΩ * (z) has the same radius of convergence as ÃΩ * (z).

We may apply Lemma 8.1 to the composition SET • ĀΩ * , yielding that the expression obtained from (9.18) by letting k range over N and replacing ÃΩ * (•) with ÃΩ * (•) belongs to the class o(n -3/2 ) of sequences that still tend to zero when multiplied by n 3/2 . But this expression is clearly an upper bound to the expression in (9.18), yielding that (9.18) also belongs to o(n -3/2 ). Hence the largest component in a random (n -1)-sized unlabelled SET Ω • A Ω object has size n + O p (1). This verifies Claim 2).

It remains to prove Claim 3), i.e. we have to show that E [f n ] = O(1). If Ω ⊂ N is bounded, then this is trivial. Otherwise it seems to require some work. By Equation (9.16) it follows that

E [f n ] = [z n-1 ] s 1 ∂Z SET Ω ∂s 1 ( ÃΩ * (z), ÃΩ * (z 2 ), . . .) [z n-1 ]Z SET Ω ( ÃΩ * (z), ÃΩ * (z 2 ), . .

.) .

Since 1 ∈ Ω the denominator is bounded from below by [z n-1 ] ÃΩ * (z). By Proposition 9.1 it follows that

([z n-1 ] ÃΩ * (z)) -1 = O(n 3/2 ρ n ).
The power series in z in the numerator is bounded coefficient wise by

s 1 ∂Z SET ∂s 1 ( ÃΩ * (z), ÃΩ * (z 2 ), . . .) = ÃΩ * (z) exp ∞ i=1 ÃΩ * (z i )/i = h( ÃΩ * (z))g(z) with h(w) = w exp(w)
being analytic on C and

g(w) = exp   i≥2 ÃΩ * (z i )/i  
having radius of convergence strictly larger than ρ since ρ < 1. By an identical argument as in the justification of Equation (9.4) we may apply the singularity analysis result [21, Thm. VI.5] to obtain

[z n-1 ]h( ÃΩ * (z))g(z) = O(n -3/2 ρ -n ).
This concludes the proof.

Symmetrically cycle pointed trees whose cycle center is a vertex

Recall . Let H n denote the total size of the trees dangling from cycles with length at least 2. We are going to make the following observations.

that V = (SET Ω A Ω * ) X . Let (V n , τ n , σ, v n ) be
Lemma 9.7. The following statements hold.

1) There are constants C 1 > 0 and 0 < γ < 1 such that for all n and x ≥ 0 we have that

P (H n ≥ x) ≤ C 1 n 3/2 γ x and P (f n ≥ x) ≤ C 1 n 3/2 γ x .
2) The maximum size of the trees corresponding to the fixpoints of σ satisfies

max Q∈Fn |A Q | = n + O p (1) .
3) There is a constant

C 2 > 0 such that E [f n ] ≤ C 2 for all n.
From these claims we may deduce Lemma 9.5 in an analogous manner as we deduced Lemma 9.4 from Lemma 9.6: Proof of Lemma 9.5. As for Claim a), it suffices to show such a bound for all n and √ n ≤ x ≤ n. Clearly it holds that

P (D(V n ) ≥ x) ≤ P (H n ≥ x/2) + P max Q∈Fn H(A Q ) ≥ x/2 -1 . (9.19)
By Claim 1) of Lemma 9.7, we know that there are constants C , C, c > 0 and 0 < γ < 1 with

P (H n ≥ x/2) ≤ C n 3/2 γ x/2 ≤ C exp(-cx 2 /n). (9.20)
As for the second summand in Equation (9.19), we may argue analogously as for Equation (9.7) that there constants C * , c * > 0 with

P max Q H(A Q ) ≥ x/2 -1 ≤ E [f n ] C * exp(-c * x 2 /n).
Claim a) now follows from Equations (9.19), (9.20) and Claim 3) of Lemma 9.7. It remains to verify Claim b). Let X n denote the tree to a canonically chosen partition class of F n with maximal size. Lemma 5.1 implies that for all Proof of Lemma 9.7. We start with Claim 1). Using the Boltzmann-sampling methods from Section 7.2.2, we obtain that the probability generating function of H n is given by

(X n | |X n | = ) (d) = A . ( 9
E w Hn = [z n-1 ] ZSET Ω ( ÃΩ * (ρz), Õ Ω * (ρz); ÃΩ * ((ρwz) 2 ), Õ Ω * ((ρwz) 2 ); . . .) [z n-1 ] ZSET Ω ( ÃΩ * (ρz), Õ Ω * (ρz); ÃΩ * ((ρz) 2 ), Õ Ω * ((ρz) 2 ); . . .) . (9.22)
A detailed justification of this fact goes as follows. By the product rule in Section 7.2.2 it suffices to consider (n -1)-sized rooted symmetries of SET Ω • A Ω * . The composition rule states that to sample such a symmetry according according to the Boltzmann model with parameters (ρ i , ρ i ) i≥1 , we may start with a Pólya-Boltzmann distributed rooted symmetry of SET Ω with parameters ( ÃΩ * (ρ i ), Õ Ω * (ρ i )) i≥1 . Then, for each j ≥ 1 and each unmarked j-cycle a symmetry of A Ω * is sampled according to a Pólya-Boltzmann distribution with parameters (ρ ij ) i , and for the marked cycle we let s denote its length and draw a rooted symmetry of A Ω * according to a Pólya-Boltzmann distribution with parameters (ρ si , ρ si ) i≥1 . Given a k ∈ Ω sized permutation ν with a marked cycle having length ≥ 2 and a distinguished atom of this cycle, the probability for the rooted symmetry of SET Ω to assume this value is given by

Õ Ω * (ρ ) ÃΩ * (ρ ) ν -1 k! ZSET Ω ( ÃΩ * (ρ), Õ Ω * (ρ); ÃΩ * (ρ 2 ), Õ Ω * (ρ 2 ); . . .) 1≤i≤k i = ÃΩ * (ρ i ) ν i . (9.23)
Conditioned on this event, the probability generating function for the size of the resulting object is given by

Õ Ω * ((ρz) ) Õ Ω * (ρ ) 1≤i≤k i = ÃΩ * ((ρz) i ) ÃΩ * (ρ i ) ν i -1 i= . ( 9.24)
The exponents (ρz) i are due to the fact that for each object corresponding to an i-cycle we attach i identical copies, and likewise for the marked cycle. In order to keep track of the volume of the trees corresponding to cycles with length at least 2 we may form the bivariate probability generating function where the variable w corresponds to this parameter and z to the total size, given by The corresponding bound for the event f n ≥ x follows by the same arguments as for H n . This proves Claim 1).

Õ Ω * ((ρwz) ) Õ Ω * (ρ ) ÃΩ * (ρz) ÃΩ * (ρ) ν 1 2≤i≤k i = ÃΩ * ((ρwz) i ) ÃΩ * (ρ i ) ν i -1 i= . ( 9
In order to verify Claim 2), it suffices to show that for any sequence t n → ∞ the probability for all components in the random SET Ω A Ω * -object to have size at most n -t n tends to zero. It follows then by Claim 1) that the largest component corresponds with high probability to a class of F n , hence yielding Claim 2).

By analogous arguments as in the justification of Equation (9.22), the probability that all components have size at most n -t n may be expressed by the product of the normalizing factor Here the sum index ν ranges over all permutations of the set [k], and τ ranges over all cycles of ν with length at least 2. The indices t and (a ij ) i,j range over all pairs of an integer t ≥ 1 with a family of numbers a ij with 1 ≤ i ≤ n -1, 1 ≤ j ≤ ν i , such that t ≤ n -t n and a ij ≤ n -t n for all i, j and

|τ |t + 1≤i≤n-1 1≤j≤ν i ia ij = n -1.
The indices i, j of the product in (9.30) range over all pairs of integers with 1 ≤ i ≤ n -1 and 1 ≤ j ≤ ν i . Applying a standard result for the singularity analysis of functions with multiple dominant singularities [21, Thm. VI.5] we obtain similarly as in the justification of Equation (9.4) that the factor in Equation (9.29) is asymptotically equivalent to n 3/2 times a constant. Thus, showing that the largest component in a random unlabelled n -1-sized SET Ω A Ω * -object has with high probability size at least n -t n is actually equivalent to showing that the expression in (9.30) multiplied by n 3/2 tends to zero as n ≡ 2 mod gcd(Ω * ) becomes large.

We consider the species ĀΩ * where for each k ∈ N 0 we set ĀΩ * [k] = A Ω * [k -] for the smallest integer ≥ 0 satisfying k -∈ Ω * . Hence A Ω * is a subspecies of ĀΩ * , and ÃΩ * (z) has the same radius of convergence as ÃΩ * (z). The expression in (9.30) The intuitive explanation of this formula is that an unlabelled SET ĀΩ * -object is a multiset of unlabelled ĀΩ * -objects, accounting for the factor exp( i≥1 ĀΩ * (z i )/i), together with a number j ≥ 2 of identical copies of an unlabelled Õ Ω * -object, accounting for the second factor j≥2 Õ Ω * (z j ). By Lemma 8.1 we know that a large random multiset of ĀΩ * -objects consists of a giant component with a stochastically bounded rest. So in order to show that a large random unlabelled SET ĀΩ * -object also consists of a giant component with a stochastically bounded rest, it suffices to show that the total size of the copies of the Ā• Ω * -object is stochastically bounded. By Equation (9.31) and the substitution sampler rule in Section 7.2.2, we obtain that the probability for the total size of the Ā• Ω * -objects in a uniform random n-sized unlabelled SET ĀΩ * -object to equal a fixed integer k is given by

[z n-k ] exp i≥1 ÃΩ * (z i )/i [z k ] j≥2 Õ Ω * (z j ) [z n ] exp i≥1 ÃΩ * (z i )/i j≥2 Õ Ω * (z j ) (9.32)
Analogously as in the justification of Equation (9.4) we obtain that there is a constant c > 0 such that

[z n ] exp   i≥1 ÃΩ * (z i )/i   ∼ cρ -n n -3/2 .
As the series j≥2 Õ Ω * (z j ) has radius of convergence strictly larger than ρ, it follows by an elementary real analytic method [21, Thm. VI.12] that

[z n ] exp   i≥1 ÃΩ * (z i )/i   j≥2 Õ Ω * (z j ) ∼ cρ -n n -3/2 j≥2 Õ Ω * (ρ j ).
(9.33)

Thus, the expression in (9.32) is asymptotically equivalent to

ρ k   [z k ] j≥2 Õ Ω * (z j )   / j≥2 Õ Ω * (ρ j ).
(9.34)

As the limit probabilities in (9.34) sum up to 1 when k ranges over all non-negative integers, it follows that the total size of cycle-pointed part of the random unlabelled SET ĀΩ * -object is stochastically bounded. We have thus verified Claim 2).

It remains to prove Claim 3). By Equation (9.28) it follows that By an elementary real analytic method [21, Thm. VI.12] and Equation (9.33) it follows that this sequence belongs to O(ρ -n n -3/2 ). Using Equation (9.36) this implies that the expression in (9.35) is bounded. This concludes the proof of Claim 3).

E w fn = [z n-1 ] s 1 ∂ ZSET Ω

Theorem 1 . 1 .

 11 There is a constant e Ω such that(T n , e Ω n -1/2 d Tn ) d -→ (T e , d Te ) (1.1)

Figure 1 :

 1 Figure 1: All unlabelled unrooted trees with 6 vertices.

Figure 2 :

 2 Figure 2: All Pólya trees with 5 vertices.

.

  The distribution of D(T e ) is known and given by D(T e )

Figure 3 :

 3 Figure 3: The Gromov-Hausdorff distance.

Lemma 5 . 1 (

 51 [START_REF]Une théorie combinatoire des séries formelles[END_REF] Sec. 3]). Let U be a finite n-element set. For any unlabelled F-object m of size n there are precisely n! symmetries (F, σ) ∈ Sym(F)[U ] having the property that F has isomorphism type m.

13

  The details of the construction are as follows. For each cycle c of σ m let Q c denote the label set of the G-object G c . For every atom e of the cycle c setQ e := Q c × {e} and (G Qe , σ Qe ) := Sym(G)[f e ](G c , σ c ) with f e : Q c → Q e thecanonical 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 c be a cycle of σ m and ν a cycle of σ c . Fix an atom b = b(c) of c and an atom a = a(ν) of ν. Let denote the length of c and k the length of ν. Form the composed cycle by ((a, b), . . . , (a, c -1 (b)), (ν(a), b), . . . , (ν(a), c -1 (b)), . . . , (ν k-1 (a), b), . . . , (ν k-1 (a), c -1 (b))).

Figure 4 :

 4 Figure 4: Two unlabelled cycle-pointed trees. The marked cycle is depicted in blue, connecting paths in red, and the cycle-pointing centers in green.

Proposition 9 . 1 (

 91 [START_REF] Panagiotou | Scaling limits of random Pólya trees[END_REF] Prop. 4.1]). The following statements hold.

Figure 5 :

 5 Figure 5: Any unlabelled E = SET {2} A Ω * object corresponds to two identical copies of a cycle-pointed Pólya tree.

Figure 6 :

 6 Figure 6: Unlabelled S = X • (SET Ω • A Ω * ) cycle pointed trees correspond to Pólya trees, in which each vertex degree must lie in Ω.

9. 3 . 3

 33 The class V of symmetric cycle pointed trees whose center of symmetry is a vertex Lemma 9.5. Let V n be drawn uniformly from the unlabelled V = (SET Ω A Ω * ) X objects of size n. Then the following statements hold. a) There are constants C, c > 0 such that for all x ≥ 0 and n we have the tail bound

Figure 7 :

 7 Figure 7: Decomposition of an unlabelled V = (SET Ω A Ω * ) X object into a Pólya tree and a number of identical copies of a symmetrically cycle-pointed Pólya tree.

. 6 )

 6 It remains to bound the second summand in Equation(9.5). Let F ⊂ [n] be a subset with P (F n = F ) > 0. Given F n = F , it follows by the discussion of the symmetries of composite structures in Section 5.4 that the symmetries (A Q , σ Q ) Q∈F are independent and for each Q ∈ F we have that (A Q , σ Q ) gets drawn uniformly at random from the set Sym(A Ω * )[Q]. That is, by Lemma 5.1, A Q gets drawn uniformly at random from all |Q|-sized Pólya trees with outdegrees in the set Ω * . By Inequality (3.2) it follows that there are positive constants C 5 , c 5 such that uniformly for all n and xP max Q H(A Q ) ≥ x/2 -1 | F n = F ≤ C 5Q∈F exp(-c 4 x 2 /|Q|) ≤ |F |C 4 exp(-c 5 x 2 /n).

. 8 )

 8 Thus, settingK n = |X n |, it holds that X n (d) = A Kn . By Claim 2) of Lemma 9.6 we have |K n | = n + O p (1), hence the remainder that gets attached to the root of X n to form the tree S n is stochastically bounded. This completes the proof of Claim b).

  a rooted c-symmetry drawn uniformly at random from the set RSym(V)[n]. In particular, V n is distributed like the uniformly at random chosen unlabelled V-object with size n. Let π n denote the corresponding partition. By the discussion in Section 5.4, σ induces an automorphism σ : π n → π n of the SET Ω -object. Moreover, let F n ⊂ π n denote the fixpoints of σ, f n = |F n | their number and for each fixpoint Q ∈ F n let (A Q , σ Q ) denote the corresponding symmetry from Sym(A Ω * )[Q]

=A

  Kn for K n := |X n |. By Claim 2) of Lemma 9.7 we know that |K n | = n + O p (1). This completes the proof of Claim b). It remains to verify Lemma 9.7.

(

  [z n-1 ]Z SET Ω ( ÃΩ * (ρz), Õ Ω * (ρz); ÃΩ * ((ρz) 2 ), Õ Ω * ((ρz) 2 ); . . .)) Ω * (y(ρz) |τ | ) i,jÃΩ * ((ρz) i x ij ). (9.30)

∂s 1 (

 1 ÃΩ * (z), Õ Ω * (z); ÃΩ * (z 2 ), Õ Ω * (z 2 ); . . .) [z n-1 ] ZSET Ω ( ÃΩ * (z), Õ Ω * (z); ÃΩ * (z 2 ), Õ Ω * (z 2 ); . . .) . (9.35)As 1 ∈ Ω the denominator is bounded from below by [z n-1 ] ÃΩ * (z). By Proposition 9.1 it follows that([z n-1 ] ÃΩ * (z)) -1 = O(n 3/2 ρ n ). (9.36)The power series in z in the numerator is bounded coefficient wise bys 1 ∂ ZSET ∂s 1 ( ÃΩ * (z), Õ Ω * (z); ÃΩ * (z 2 ), Õ Ω * (z2); . . .) = ÃΩ * (z) exp

  and Granovsky [6, Thm. 2.2].

	Lemma 8.1. Suppose that

  ZSET Ω ( ÃΩ * (ρ), Õ Ω * (ρ); ÃΩ * (ρ 2 ), Õ Ω * (ρ 2 ); . . .)The quotient of (9.26) and (9.27) is the probability generating function for the parameter H n , and the expression obtained in this way agrees with Equation (9.22).Having verified Equation (9.22), we proceed with the argument. Since 1 ∈ Ω and there is a number k ≥ 3 with k ∈ Ω it follows that the denominator in (9.22) is bounded from below by[z n-1 ]z k-1 ÃΩ * (ρz) = [z n-k ] ÃΩ Cn -3/2as n ≡ 2 mod gcd(Ω * ) tends to infinity. The polynomial in the numerator in (9.22) with indeterminate w is bounded coefficient wise by the series ZSET Ω ( ÃΩ * (ρ), Õ Ω * (ρ); ÃΩ * ((ρw) 2 ), Õ Ω * ((ρw) 2 ); . . .) which does not depend on n and, by Proposition 9.2, has radius of convergence strictly larger than 1. It follows that there is a constant C such that P (H n ≥ x) ≤ C n 3/2 γ x for all n and x. By a similar argument as for Equation (9.22) the probability generating function for the random number number f n is given by E w fn = [z n-1 ] ZSET Ω (w ÃΩ * (ρz), w Õ Ω * (ρz); ÃΩ * ((ρz) 2 ), Õ Ω * ((ρz) 2 ); . . .) [z n-1 ] ZSET Ω ( ÃΩ * (ρz), Õ Ω * (ρz); ÃΩ * ((ρz) 2 ), Õ Ω * ((ρz) 2 ); . . .)

	.	(9.28)
	.	(9.27)

.

[START_REF] Janson | Scaling limits of random planar maps with a unique large face[END_REF]

Multiplying

(9.23)

with

(9.25)

and summing over all outcomes with total size n -1 yields

[z n-1 ] ZSET Ω ( ÃΩ * (ρz), Õ Ω * (ρz); ÃΩ * ((ρwz) 2 ), Õ Ω * ((ρwz) 2 ); . . .) ZSET Ω ( ÃΩ * (ρ), Õ Ω * (ρ); ÃΩ * (ρ 2 ), Õ Ω * (ρ 2 ); . . .) .

(9.26)

Similarly, multiplying (9.23) with (9.24) and summing over all outcomes with total size n -1 yields

[z n-1 ] ZSET Ω ( ÃΩ * (ρz), Õ Ω * (ρz); ÃΩ * ((ρz) 2 ), Õ Ω * ((ρz) 2 ); . . .) * (ρz).

Clearly it holds that n -k ≡ 1 mod gcd(Ω * ).

By Proposition 9.1 it follows that [z n-k ] ÃΩ * (ρz) ∼

  has an upper bound obtained by modifying (9.30) such that k ranges over all non-negative integers, and ÃΩ * and Õ Ω * get replaced by ÃΩ * and Õ Ω * . Showing that this upper bound belongs to o(n -3/2 ) is equivalent to showing that the largest component in a uniform random n-sized unlabelled SET ĀΩ * -object has with high probability size at least n -t n . Combining Equations (6.4),(6.6), (6.2) and (5.1) yields that the ordinary generating function of the species SET ĀΩ * is given by

				
	exp		ÃΩ * (z i )/i		Õ Ω * (z j ).	(9.31)
		i≥1		j≥2

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