Michael Drmota
email: michael.drmota@tuwien.ac.at

Emma Yu

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

GRAPH LIMITS OF RANDOM GRAPHS FROM A SUBSET OF CONNECTED k-TREES

Keywords: partial k-trees, Continuum Random Tree, modified Galton-Watson tree

√ n) where H k is the k-th Harmonic number and σ Ω > 0, converges to the Continuum Random Tree Te. Furthermore, we prove the local convergence of the rooted random Ω-k-tree G • n,k to an infinite but locally finite random Ω-k-tree G ∞,k .

Introduction and main results

A k-tree is a generalization of a tree and can be defined recursively: a k-tree is either a complete graph on k vertices (= a k-clique) or a graph obtained from a smaller k-tree by adjoining a new vertex together with k edges connecting it to a k-clique of the smaller k-tree (and thus forming a (k + 1)-clique). In particular, a 1-tree is a usual tree. (Note that the parameter k is always fixed.) Subgraphs of k-trees are called partial k-trees; see Figure 1 A partial k-tree is an interesting graph from an algorithmic point of view since many NP-hard problems on graphs have polynomial, in fact usually linear, dynamic programming algorithms when restricted to partial k-trees for fixed values of k [START_REF] Arnborg | Linear time algorithms for NP-hard problems restricted to partial k-trees[END_REF][START_REF] Telle | Practical algorithms on partial k-trees with an application to domination-like problems[END_REF][START_REF] Grötschel | Building Bridges: between Mathematics and Computer Science[END_REF]; such NP-hard problems include maximum independent set size, minimal dominating set size, chromatic number, Hamiltonian circuit, network reliability and minimum vertex removal forbidden subgraph [START_REF] Arnborg | Efficient algorithms for combinatorial problems on graphs with bounded decomposability-A survey[END_REF][START_REF] Bertele | On non-serial dynamic programming[END_REF]. Several graphs which are important in practice [START_REF] Krause | Bounded treewidth graphs-A survey[END_REF], have been shown to be partial k-trees, among them are [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF] Trees/ Forests (partial 1-trees) (2) Series parallel networks (partial 2-trees) (3) Outplanar graphs (partial 2-trees) (4) Halin graphs (partial 3-trees); see [START_REF]Handbook of graph theory[END_REF]. However, other interesting graph classes like planar graphs or bipartite graphs are not partial ktrees. On the other hand, partial k-trees are very interesting from a combinatorial point of view, although the enumeration of partial k-trees for general k is still missing. The number of k-trees, which are "saturated" partial k-trees, has been counted in various ways; see [9, 51, 27, 16, 37, 38, holds with respect to the Gromov-Hausdorff metric. Here H k = 1 + 1/2 + . . . + 1/k denotes the k-th Harmonic number and σ Ω is a positive constant. If Ω = N 0 , the constant σ N0 equals 1.

In particular this shows that the diameter as well as the expected distance of two vertices in a random Ω-k-tree G n,k are of order √ n and they have up to a constant scaling factor the same limiting distribution as random 1-trees. The constant kH k has also a natural explanation. In the proof of Theorem 1 we will partition an Ω-k-tree into rooted blocks that constitute subsets of the same distance to the root of the Ω-k-tree, and kH k is actually the expected length of the path from the selected good node in a block to the root of this block. Instead of the class G n,k we could equivalently also consider the class of Ω-k-trees with n hedra that are rooted at a fixed labelled front. In Subsection 2.2 below we will argue that the two models are equivalent and hence our results apply to both. We recall that (partial) 1-trees are just trees and partial 2-trees are series-parallel graphs. In both cases it is known [START_REF] Aldous | The Continuum Random Tree III[END_REF][START_REF] Panagiotou | Scaling Limits of Random Graphs from Subcritical Classes[END_REF] that the CRT appears as the scaling limit (if we scale by c/ √ n for some positive constant c). We conjecture that the CRT also arises as the scaling limit of partial k-trees for larger k.

Conjecture 1. Let PT n,k be the class of all connected labelled partial k-trees and let PT n,k be a uniformly chosen random graph from PT n,k . Then PT n,k converges toward the CRT in the Gromov-Hausdorff sense for every k ≥ 1, after rescaling the metric by a factor c k / √ n for some constant c k > 0.

At the moment this property seems to be out of reach since there is no precise asymptotic analysis of partial k-trees if k ≥ 3. Nevertheless Theorem 1 is a strong indication that such a property should hold. For example, if we delete o( √ n) edges from a random Ω-k-tree we (usually)

do not destroy the connectivity and also the distance function might be slightly affected but not more than o( √ n). Thus, if we construct partial k-trees in that way we still observe a scaling limit of the above form.

Theorem 1 describes the asymptotic global metric properties of random k-trees, but gives little information about asymptotic local properties. Hence we provide a second limit theorem that establishes the local weak convergence of the random Ω-k-tree G n,k toward an infinite but locally finite Ω-k tree G ∞,k . This type of convergence describes the asymptotic behaviour of neighborhoods around a randomly chosen front.

Theorem 2. Let G n,k be the class of labelled Ω-k-trees with n hedra and denote by G • n,k a random Ω-k-tree that is uniformly selected from the class G n,k and then rooted at a uniformly at random chosen front. Then, as n tends to infinity, the random graph G • n,k converges in the local-weak sense toward a front-rooted infinite Ω-k-tree G ∞,k , that is,

G • n,k d -→ G ∞,k .
Our proof of Theorem 2 builds on the classical local convergence of simply generated trees toward a modified Galton-Watson tree. See for example Theorem 7.1 in Janson's survey [START_REF] Janson | Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation[END_REF], which unifies some results by Kennedy [START_REF] Kennedy | The Galton-Watson process conditioned on the total progeny[END_REF], Aldous and Pitman [START_REF] Aldous | Tree-valued Markov chains derived from Galton-Watson processes[END_REF], Grimmett [START_REF] Grimmett | Random labelled trees and their branching networks[END_REF], Kolchin [START_REF] Kolchin | Random mappings[END_REF], Kesten [START_REF] Kesten | Subdiffusive behavior of random walk on a random cluster[END_REF], Aldous [START_REF] Aldous | The Continuum Random Tree II, An overview. Stochastic analysis[END_REF], Jonsson and Stefánsson [START_REF] Jonsson | Condensation in nongeneric trees[END_REF] and Janson, Jonsson and Stefánsson [START_REF] Janson | Random trees with superexponential branching weights[END_REF].

A result similar to Theorem 2 is known for partial 2-trees since series-parallel graphs belong to the family of subcritical graph classes [START_REF] Stufler | Random enriched trees with applications to random graphs[END_REF][START_REF] Georgakopoulos | Limits of subcritical random graphs and random graphs with excluded minors[END_REF]. Therefore we can also formulate the following conjecture.

Conjecture 2. The random labelled partial k-tree PT n,k converges in the local-weak sense for every k ≥ 1. That is, the neighborhoods of a random front in PT n,k converge weakly toward the neighborhoods of a front-rooted infinite partial k-tree PT ∞,k as n → ∞.

The plan of the paper is as follows. In Section 2 we recall the combinatorial background for Ω-k-trees, introduce the Boltzmann sampler -a method of generating efficiently a uniform random combinatorial object, describe Darrasse and Soria's algorithm on computing the distances between two vertices in an Ω-k-tree, present Aldous's result on the convergence of critical Galton-Watson * AND BENEDIKT STUFLER trees to the CRT T e , and recall the notion of local convergence. In Section 3 we prove our first main result -Theorem 1, and in Section 4 our second main result -Theorem 2.

Combinatorics, Boltzmann Samplers and Graph Limits

Let Ω ⊂ N 0 denote a set of non-negative integers which contains 0, 1 and at least one integer greater than 1. We will review the generating function approach from [START_REF] Darrasse | Limiting distribution for distances in k-trees, Combinatorial Algorithms[END_REF] to count the number Par k,Ω (n) of Ω-k-trees. The key ingredient to count the number Par k,Ω (n) is a bijection between rooted Ω-k-trees and (k, Ω)-front coding trees; see [START_REF] Darrasse | Limiting distribution for distances in k-trees, Combinatorial Algorithms[END_REF].

Definition 2 ((k, Ω)-front coding tree). For any set Ω of non-negative integers which contains 0, 1 and at least one integer greater than 1, a (k, Ω)-front coding tree of size n is a tree T consisting of (kn + 1) white nodes and n black nodes which satisfies:

(1) T is rooted at a white node, every white node has only black nodes as children and every black node has only k white nodes as children. [START_REF] Aldous | The Continuum Random Tree I[END_REF] The number of black children of the white root belongs to the set Ω and the number of black children of any other white node belongs to the set

{i | i + 1 ∈ Ω, i ≥ 0}. (3)
The white root of T is labeled by a k-subset A of [n + k] = {1, 2, . . . , n + k} and the black nodes are labeled by the integers from the set [n + k] -A such that for every white node, the subtrees stemming from its black children are not ordered between themselves.

The labels on the white root and black nodes determine the labels on the rest white nodes. We start from the white root and recursively label other white nodes. For every white node, we label it with a set {r 1 , . . . , r i-1 , r, r i+1 , . . . , r k } if the white node is the i-th child (from left to right) of a black node labeled by r and the white parent of this black node is labeled with the set {r 1 , . . . , r k }.

If the white root of a (k, Ω)-front coding tree has precisely one black child, we call it reduced (k, Ω)-front coding tree.

We first list all important notations of Ω-k-trees and (k, Ω)-front coding trees that are necessary in our argument.

(1) G n,k : the class of labelled Ω-k-trees with n hedra.

(2) G n,k : a random Ω-k-tree that is uniformly selected from the class G n,k .

(3) G • n,k : a random Ω-k-tree G n,k that is rooted at a uniformly chosen front. (4) G n,k : the class of labelled Ω-k-trees with n hedra that are rooted at a fixed front {1, 2, . . . , k}.

(5) G • n,k : the class of labelled Ω-k-trees with n hedra that are rooted at a fixed front {1, 2, . . . , k} and this root front is contained in only one hedron. (6) C n,k : the class of (k, Ω)-front coding trees of size n that are rooted at a white node {1, 2, . . . , k}. (7) C n,k : a random (k, Ω)-front coding tree that is uniformly selected from C n,k . (8) B n,k : the class of reduced (k, Ω)-front coding trees of size n that are rooted at a white node {1, 2, . . . , k}. (9) B n,k : a random reduced (k, Ω)-front coding tree that is uniformly selected from B n,k . (10) G • n,k : a random Ω-k-tree that uniquely corresponds to B n,k under the bijection ϕ where the bijection ϕ will be shown in subsection 2.1. This is equivalent to uniformly choose a random Ω-k-tree from the class G • n,k . (11) G n,k : a random Ω-k-tree that uniquely corresponds to C n,k under the bijection ϕ. This is equivalent to uniformly choose a random Ω-k-tree from the class G n,k .

2.1.

A one-to-one correspondence ϕ. We recall that a rooted Ω-k-tree is an Ω-k-tree rooted at a front (or equivalently a k-clique). For the case Ω = N 0 , we simply call a (k, N 0 )-front coding tree a k-front coding tree. By Definition 2, a k-front coding tree is a bipartite tree of black and white nodes which is rooted at a white node and where every black node has precisely k successors.

We will present a one-to-one correspondence

ϕ : G n,k → C n,k
when Ω = N 0 , that is, a one-to-one correspondence ϕ between rooted k-trees and k-front coding trees. The bijection ϕ holds for any Ω-k-tree when we specify the outdegrees of the white nodes in the corresponding (k, Ω)-front coding tree.

The correspondence ϕ will be built in a way that black nodes in a k-front coding tree correspond to hedra in a k-tree. Every black node also gets a label which is equal to the label of one of the vertices of the corresponding hedron. A white node in a k-front coding tree corresponds to a front of the k-trees and is labelled by the set {a 1 , a 2 , . . . , a k } of labels of the corresponding front. A black node connects with a white node if the corresponding hedron contains the corresponding front and the label of the black node is just the label of the vertex that is not contained in the front. Thus, if we start with the root front of the k-tree we can recursively build up a corresponding k-front coding tree; see Figure 2.1. With the help of this correspondence ϕ, the problem of counting the Ω-k-trees with n hedra is reduced to count the corresponding (k, Ω)-front coding trees with n black nodes. We use the notation •-rooted (k, Ω)-front coding trees if the white root node has a fixed label and use the notation • -• (k, Ω)-front coding tree if the white root of a reduced (k, Ω)-front coding tree has a fixed label.

Let G k be the class of Ω-k-trees rooted at a fixed front {a 1 , a 2 , . . . , a k }, furthermore let C k be the class of the (k, Ω)-front coding trees and B k be the class of • -• (k, Ω)-front coding trees. In fact, the correspondence ϕ also establishes the relation ϕ : G k → C k . Furthermore, every (k, Ω)front coding tree can be identified as a set of • -• (k, Ω)-front coding trees with the outdegree set Ω, which leads to the relation

C k = Set Ω (B k ). (2.1)
In terms of exponential generating functions (where the size is always the number of black nodes), we thus get

C k (x) = i∈Ω (B k (x)) i i ! . (2.2)
We recall that C n,k is a random (k, Ω)-front coding tree that is uniformly selected from the (k, Ω)front coding trees of size n. We denote by L n,k one of the largest • -• (k, Ω)-front coding trees that is contained in C n,k and denote by L n,k the size of L n,k . By employing a unified analytic * AND BENEDIKT STUFLER framework given by Xavier Gourdon [START_REF] Gourdon | Largest component in random combinatorial structures[END_REF], from (2.1) we can prove that for any sufficiently small ε such that ε > 0, one has

P[n -L n,k ≥ n ε ] → 0. (2.3)
Now we continue to decompose the • -• (k, Ω)-front coding tree. Let C • k be the class of •-rooted (k, Ω)-front coding trees that are contained in the • -• (k, Ω)-front coding trees. Then every tree from C • k can be identified as a set of • -• (k, Ω)-front coding trees with the outdegree set Ω out of the white nodes where Ω out = {i | i + 1 ∈ Ω, i ≥ 0}. Moreover, every • -• (k, Ω)-front coding tree can be decomposed into a k-tuple of •-rooted (k, Ω)-front coding trees. This yields the following specification:

B k = {•} * Seq k (C • k ) and C • k = Set Ω out (B k ). (2.4)
In terms of exponential generating functions, one gets

B k (x) = x • C • k (x) k and C • k (x) = i+1∈Ω i≥0 (B k (x)) i i ! . (2.5) In particular B k (x) satisfies (2.6) B k (x) = x( i+1∈Ω i≥0 (B k (x)) i i ! ) k .
Consequently there exists a unique positive dominant singularity

ρ k,Ω of B k (x) such that i+1∈Ω i≥1 (ki -1) i ! (B k (ρ k,Ω )) i = 1 and B k (ρ k,Ω ) < ∞. (2.7) It follows immediately from (2.2) and (2.5) that C k (ρ k,Ω ) < ∞ and C • k (ρ k,Ω ) < ∞. We set b k,Ω (n) = n![x n ]B k (x) and c k,Ω (n) = n![x n ]C k (x)
which counts the number of •-rooted (k, Ω)front coding trees of n black nodes and the root • has a fixed label {a 1 , a 2 , . . . , a k }. Since there are n+k k ways to choose the root {a 1 , a 2 , . . . , a k }, the number of Ω-k-trees having n hedra that are rooted at a front is

(kn + 1)Par k,Ω (n) = n + k k c k,Ω (n), (2.8)
and Par k,Ω (n) can be derived from (2.8) for any specific Ω. One can analyze the asymptotic behaviors of b k,Ω (n) and c k,Ω (n) from (2.6); see [START_REF] Drmota | Random trees, An Interplay between Combinatorics and Probability[END_REF][START_REF] Flajolet | Analytic Combinatorics[END_REF], which yields

b k,Ω (n) ∼ d 1 n -3/2 n!(ρ k,Ω ) -n and c k,Ω (n) ∼ d 2 n -3/2 n!(ρ k,Ω ) -n (2.9)
for some positive constants d 1 , d 2 . Together with (2.8) this leads to

Par k,Ω (n) ∼ d 2 n n+k-2 k • k! (ρ k,Ω ) -n .
Furthermore, one can also estimate the number

U k,Ω (n) of unlabeled Ω-k-trees. U k,Ω (n) ∼ d 3 n -5/2 (τ k,Ω ) -n
where d 3 is a positive constant and τ k,Ω is the dominant singularity of A k (z) that is given by

A k (z) = z k∈Ω λ k (kA k (z)) λ1 λ 1 ! (kA k (z 2 )) λ2 λ 2 !2 λ2 • • • (kA k (z k )) λ k λ k !k λ k , (2.10)
in which λ k is a partition of k and by λ i we denote the number of parts in λ with length i. The dominant singularity z = τ k,Ω is the unique solution of (2.10) and

1 k = z k∈Ω λ k λ1≥1 (kA k (z)) λ1-1 (λ 1 -1)! (kA k (z 2 )) λ2 λ 2 !2 λ2 • • • (kA k (z k )) λ k λ k !k λ k .
For the case Ω = N 0 , the number U k,N0 (n) of unlabeled k-trees is estimated in [START_REF] Drmota | An asymptotic analysis of labelled and unlabelled k-trees[END_REF].

Remark 1.

If Ω = N 0 , it was shown in [START_REF] Beineke | The number of labelled k-dimensional trees[END_REF][START_REF] Moon | The number of labeled k-trees[END_REF][START_REF] Foata | Enumerating k-trees[END_REF][START_REF] Darrasse | Limiting distribution for distances in k-trees, Combinatorial Algorithms[END_REF] that the number Par k,N0 (n) of N 0 -k-trees having n hedra is given by

(2.11) Par k,N0 (n) = n + k k (kn + 1) n-2 , thus, asymptotically by Par k,N0 (n) ∼ n k (kn) n-2 e 1/k (k!) -1 as n → ∞.
By applying the Lagrange inversion formula on (2.6) for the case Ω = N 0 , we obtain that the number of • -• (k, N 0 )-front coding trees with n black nodes where the root

• has a fixed label {a 1 , a 2 , . . . , a k }, is b k,N0 (n) = n! [x n ]B k (x) = (n -1)![x n-1 ] exp(knx) = (kn) n-1 (2.12)
and the number of •-rooted (k, N 0 )-front coding trees with n black nodes where the root

• has a fixed label {a 1 , a 2 , . . . , a k } is c k,N0 (n) = n! [x n ]C k (x) = (n -1)![x n-1 ] exp((kn + 1)x) = (kn + 1) n-1 . (2.13)
In view of (2.13), the closed formula (2.11) for Par k,N0 (n) is proved. It follows from (2.6) that the dominant singularity of B k (x) for the case Ω = N 0 is ρ k,N0 = (ek) -1 and B k (ρ k,N0 ) = k -1 ; see [START_REF] Darrasse | Limiting distribution for distances in k-trees, Combinatorial Algorithms[END_REF][START_REF] Drmota | An asymptotic analysis of labelled and unlabelled k-trees[END_REF] for details.

Reduction of Theorem 1.

We reduce Theorem 1 to the scaling limit of a random rooted Ω-k-trees where the root front has vertices labelled by 1, 2, . . . , k.

Since any Ω-k-tree with n hedra has the same number, (kn + 1), of fronts, it makes no difference whether we root G n,k at a uniformly at random chosen front, or if we select an element from the class G • n,k uniformly at random. From (2.8) and the bijection ϕ we find that for all g ∈ G • n,k and c ∈ C n,k we have

P[G • n,k = g] = n + k k -1 P[C n,k = c] = n + k k -1 P[G n,k = ϕ -1 (c)],
which means that the probability to uniformly choose a front-rooted Ω-k-tree is equal to the probability to first uniformly choose a rooted Ω-k-tree from G n,k and then replace the label {1, 2, . . . , k} on the root by a uniformly chosen k-subset of [n]. Since the relabeling will not change the distance of two vertices in the graph and will not change the probability to choose an Ω-k-tree of a given shape, without loss of generality we can fix the labeling of the root front and consider the random Ω-k-tree G n,k . That is, it suffices to prove Theorem 1 for the random Ω-k-tree that is uniformly selected from G n,k . This is equivalent to uniformly choose a (k, Ω)-front coding tree

C n,k from C n,k and consider the corresponding random Ω-k-tree G n,k = ϕ -1 (C n,k ).
We can further reduce Theorem 1 to the scaling limit of a random rooted Ω-k-tree such that the root front is contained in only one hedron. That is, a random rooted Ω-k-tree that uniquely corresponds to a • -• (k, Ω)-coding tree from B k . We put this in Section 3 after we introduce the Gromov-Hausdorff metric in subsection 2.5.

Since B k has a proper recursive specification (2.5), these random objects can be constructed (or sampled) by a so-called Boltzmann sampler ΓB k (x).

Boltzmann Sampler.

Boltzmann samplers provide a way to efficiently generate a combinatorial object at random. They were introduced by Duchon, Flajolet, Louchard and Schaeffer [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF] and were further developed by Flajolet, Fusy and Pivoteau [START_REF] Flajolet | Boltzmann sampling of unlabelled structures[END_REF]. Here we refer the readers to their papers [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF][START_REF] Flajolet | Boltzmann sampling of unlabelled structures[END_REF] for a detailed description of the Boltzmann samplers. We just mention that the Boltzmann sampler ΓM (x) is a random generator which chooses an object c ∈ M with probability P(ΓM (x) = c) = x |c| /(M (x)|c|!), where M (x) denotes the exponential generating function of c ∈ M and the parameter x > 0 ist such that 0 < M (x) < ∞. An important property of Boltzmann samplers is that they generate objects conditioned on output size n uniformly. *

AND BENEDIKT STUFLER

More precisely we will describe a Boltzmann sampler ΓB k (x) with parameter x = ρ k,Ω (which is possible since B k (ρ k,Ω ) < ∞). We denote by ξ • the random variable with probability distribution

P[ξ • = i] = 1 C • k (ρ k,Ω ) (B k (ρ k,Ω )) i i ! if i ∈ Ω out and P[ξ • = i] = 0 otherwise. (2.14)
Lemma 3. The following recursive procedure ΓB k (ρ k,Ω ) terminates almost surely and draws a random • -• (k, Ω)-front coding tree according to the Boltzmann distribution with parameter ρ k,Ω , i.e., any • -• (k, Ω)-front coding tree of size n is drawn with probability

ρ n k,Ω /(n! B k (ρ k,Ω )). ΓB k (ρ k,Ω ): x 1 ← a black node • for i := 1 → k x 2 ← a single white node • merge x 2 into x 1 by adding an edge • -• m ← ξ • and m ∈ Ω out F ← an m-tuple (ΓB k (ρ k,Ω ), . . . , ΓB k (ρ k,Ω )),
drop the labels merge F into x 1 by connecting x 2 to the roots of F x 1 ← label the black nodes of x 1 uniformly at random return x 1 Remark 2. Boltzmann sampler can be compiled automatically from combinatorial specifications. In the present case of Ω-k-trees, the specification given in (2.4) involves product * and Set Ω out , consequently we need the rules of Seq k and Set Ω out for the inductive construction of Boltzmann sampler ΓF (x) and ΓC

• k (x), which are Construction Generator F = Seq k (C • k ) return the k-tuple (ΓC • k (x), • • • , ΓC • k (x)) relabeled uniformly at random. C • k = Set Ω out (B k ) m ← ξ • and m ∈ Ω out , return the m-tuple (ΓB k (x), . . . , ΓB k (x))
relabeled uniformly at random.

For the case Ω = N 0 , we have

C k = C • k = Set(B k ) and from (2.14) it follows that ξ • is Poisson distributed with parameter B k (ρ k,N0 ) = k -1 where ρ k,N0 = (ek) -1 .
Note that (k, Ω)-front coding trees satisfy the specification (2.5), but they do not represent the distance relation in the Ω-k-trees; see Figure 2.1. Since we have fixed the label on the white root •, which is {1, 2, . . . , k}, the labels on the black nodes of ΓB k (ρ k,Ω ) determine the corresponding labels on the other white nodes.

2.4. Ω-k-tree distance algorithm. For a random (k, Ω)-front coding tree C n,k , G n,k is the corresponding Ω-k-tree under the bijection ϕ

-1 : C n,k → G n,k in subsection 2.1. So G n,k is rooted at the front {1, 2, . . . , k}.
We use the notation (i m , j k-m ) to represent the sequence of length k that has m occurrences of i and (km) occurrences of j. Here we shall consider the distances to the vertex 1 in an Ω-k-tree G n,k . Darrasse and Soria [START_REF] Darrasse | Limiting distribution for distances in k-trees, Combinatorial Algorithms[END_REF] provided an algorithm to calculate the distances to the vertex 1 in an Ω-k-tree G n,k by marking the distances on the corresponding (k, Ω)-front coding tree C n,k , which is similar to the algorithm given by Proskurowski in [START_REF] Proskurowski | K-trees: representation and distances In: Congressus Numerantium[END_REF]. Note that every black node of the (k, Ω)-front coding tree is related to a vertex of the corresponding Ω-k-tree via its label, and the vertices that label a white node of the (k, Ω)-front tree represent k vertices that constitute a front of the corresponding Ω-k-tree. We recall Darrasse and Soria's algorithm. Algorithm 1: Distances in an Ω-k-tree Input: a (k, Ω)-front coding tree C and a sequence (a i ) k i=1 = (0, 1 k-1 ) Output: an association table (vertex, distance) p := min{a i } k i=1 + 1 and A = ∅ for all sons v of the root C do

A := A ∪ {(v, p)} for i := 1 → k do
A ← A ∪ the recursive call on the i-th son of v and (a 1 , . . . , a i-1 , p, a i+1 , . . . , a k ) return A If we implement this algorithm on the (2, Ω)-front coding tree (middle) in Figure 2.1, we get a distance table marked on every black node in Figure 2.2. The distance sequences on the white nodes help us to recursively mark the distances on the black nodes.

Remark 3. Based on this distance algorithm, Darrasse and Soria used the generating function approach to show a Rayleigh limiting distribution for the expected distances between pairs of vertices in a random k-tree; see [START_REF] Darrasse | Limiting distribution for distances in k-trees, Combinatorial Algorithms[END_REF]. , where r 0 (T e ) is the equivalence class of the origin, is the Continuum Random Tree (CRT). We will simply use T e to denote the CRT. Recall that the isometry classes of (pointed) compact metric spaces K(K • ), where a pointed compact space is a triple (X, d, r), where (X, d) is a metric space and r ∈ X is a distinguished element, constitute a Polish space with respect to the (pointed) Gromov-Hausdorff metric d GH .

1, 1 0, 1 1 1, 1 0, 1 1 1, 1 0, 1 2, 1 1, 2 1
We shall briefly introduce the Gromov-Hausdorff metric and refer the readers to [START_REF] Burago | A course in metric geometry[END_REF][START_REF] Evans | Probability and real trees[END_REF] for a full description of this metric. Given two compact metric spaces (X, d 2 ) and (Y, d 2 ), a correspondence between X and Y is a subset R ⊂ X × Y such that for any x ∈ X, there is a y ∈ Y with (x, y) ∈ R and conversely for any y ∈ Y , there is an x ∈ X with (x, y) ∈ R. The distortion of the correspondence is defined as follows:

dis(R) = sup{|d 1 (x 1 , x 2 ) -d 2 (y 1 , y 2 )| : (x 1 , y 1 ), (x 2 , y 2 ) ∈ R}. (2.15)
Given two pointed compact metric spaces (X, d 1 , r 1 ) and (Y, d 2 , r 2 ), we define the Gromov-Hausdorff distance between the pointed compact metric spaces (X, d 1 , r 1 ) and (Y, d 2 , r 2 ) by

d GH ((X, d 1 , r 1 ), (Y, d 2 , r 2 )) = 1 2 inf R dis(R) (2.16) *

AND BENEDIKT STUFLER

where R ranges over all correspondences between X and Y such that r 1 and r 2 corresponds to each other. The Gromov-Hausdorff metric of two compact spaces (X, d 1 ) and (Y, d 2 ) is then defined to be (2.16) without r 1 , r 2 .

A pointed metric space (X, d 1 , r 1 ) may be rescaled by multiplying the metric with a positive constant a. We shall denote the rescaled space (X, ad 1 , r 1 ) in the following simply by aX.

Let T be a Galton-Watson tree, we say T is critical if the offspring distribution ξ of T satisfies Eξ = 1. In fact, T is almost surely finite if and only if Eξ ≤ 1. Let supp(ξ) = {m | P(ξ = m) > 0} denote the support of ξ and define the span, denoted by span(ξ), as the greatest common divisor of {m | m ∈ supp(ξ)}. If a Galton-Watson tree T is finite, then

|T | = 1 + v∈V (T ) d + T (v) ≡ 1 mod span(ξ) (2.17)
where V (T ) is the vertex set of T and d + T (v) represents the outdegree of v in T . The convergence of a Galton-Watson tree T n conditioned on size n (properly scaled) to T e is due to Aldous [START_REF] Aldous | The Continuum Random Tree III[END_REF].

Theorem 4. Let T n be a Galton-Watson tree conditioned on having n vertices, where T n is critical and the offspring distribution ξ of T n has finite variance Var ξ = σ 2 . As n tends to infinity, T n with edges rescaled to length σ/( 2√ n) converges in distribution to the CRT, i.e.,

σ 2 √ n T n d -→ T e in the metric space (K • , d GH ).
The Galton-Watson tree conditioned on having n vertices is also called the conditioned Galton-Watson tree. The conditioned Galton-Watson trees are essentially the same as the random simply generated trees; see [START_REF] Devroye | Branching Processes and Their Applications in the Analysis of Tree Structures and Tree Algorithms[END_REF][START_REF] Drmota | Random trees, An Interplay between Combinatorics and Probability[END_REF]. 2.6. Local convergence. Let X denote the collection of rooted graphs that are connected and locally finite. Given two rooted graphs

G * = (G, v G ) and H * = (H, v H ) from X, we define the distance d(G * , H * ) = 2 -sup{m∈N0 | Um(G * ) Um(H * )}
where U m (G * ) denotes the rooted subgraph of G induced by all vertices with graph-distance at most m from the root-vertex v G , and U m (G * ) U m (H * ) represents that the two subgraphs are isomorphic as rooted graphs. The distance d satisfies the axioms of a premetric and two elements from X have distance zero from each other if and only if they are isomorphic as rooted graphs. Hence d defines a complete and separable metric on the collection of all isomorphism classes of graphs from X [START_REF] Burago | A course in metric geometry[END_REF][START_REF] Evans | Probability and real trees[END_REF].

A random rooted graph

G * n = (G n , v n ) from X converges in the local weak sense toward a random element from G * ∞ = (G ∞ , v ∞ ), denoted by (G n , v n ) d -→ (G ∞ , v ∞ ),
if the corresponding isomorphism classes converge weakly with respect to this metric. This is equivalent to requiring that for all fixed positive number r, and for all rooted graphs (G, v) it holds that

lim n→∞ P[U r (G n , v n ) (G, v)] = P[U r (G ∞ , v ∞ ) (G, v)]. (2.18)

Proof of Theorem 1

We recall that C n,k is a random (k, Ω)-front coding tree of size n that is uniformly selected from the class C n,k and the size L n,k of the largest • -• (k, Ω)-front coding tree in C n,k satisfies (2.3). This implies that the Gromov-Hausdorff distance between C n,k and L n,k is bounded by n ε with high probability. If we choose ε = 1/4, it follows that

d GH (L n,k n -1/2 , C n,k n -1/2 ) p -→ 0. (3.1)
Let B n,k denote a random • -• (k, Ω)-coding tree that is uniformly chosen from all the • -• (k, Ω)-coding trees of size n, so in order to establish the convergence of rescaled C n,k to T e , from (3.1) it suffices to show that for the rescaled B n,k .

First we generate the random •-• (k, Ω)-front coding tree by the Boltzmann sampler ΓB k (ρ k,Ω ). Let T n be the black tree obtained from B n,k by replacing every edge • -• -• by an edge • -• which keeps the labels on the black nodes, consequently black trees are in bijection with • -• (k, Ω)-front coding trees; see Figure 2.1.

From the construction of the Boltzmann sampler ΓB k (ρ k,Ω ), it is clear that any black node has k white children and the number of black children ξ • of the white node in B n,k follows the probability distribution (2.14). This implies, the black grandchildren ξ • of any black node has the probability distribution

P[ξ • = i] = P[ k j=1 ξ •,j = i] and ξ •,j d = ξ • . (3.2)
Furthermore, (3.2) is exactly the offspring distribution of the black tree T n , thus from (2.7) we know that E ξ • = kE ξ • = 1 and T n is a critical Galton-Watson tree with span gcd(Ω out ) where gcd(Ω out ) denotes the greatest common divisor of the integers in Ω out .

We denote by G • n,k the Ω-k-tree that corresponds to the random (k, Ω)-coding tree B n,k under the bijection ϕ -1 : B n,k → G • n,k . For any two black nodes x, y in B n,k , we set d B n,k (x, y) = dist Tn (x, y), where dist denotes the usual graph theoretical distance. For the case k = 1, the distance

d B n,k (x, y) of two black nodes x, y in B n,k is different from the distance dist G • n,k (x, y) of x, y in the original Ω-k-tree G • n,k .
In order to represent the distances dist G • n,k (x, y) for any two black nodes x, y in the tree B n,k , we need to decompose B n,k into blocks according to the distance table from Algorithm 1. We implement the Algorithm 1 on the random tree B n,k to have every black node marked with a distance and every white node marked with a distance sequence. For this random tree B n,k , denote by B i,n,k a subtree of B n,k that we call an i-block :

(1) B 1,n,k is rooted at the root and is induced by the root and all the black nodes that are in distance one to the vertex 1. (2) B i,n,k , i ≥ 2, is rooted at a white node with distance sequence ((i -1) k ) and is induced by this node and all its black descendants that have distance i to the vertex 1. By construction, there is only one subtree B 1,n,k in B n,k , but there could be many subtrees B i,n,k of B n,k for i = 1; see Figure 3.1. For any two black nodes x, y in B n,k , let δ B n,k (x, y) = a -1 where a is the minimal number of blocks necessary to cover the path connecting x and y. In particular if x, y are in the same block of B n,k , then δ B n,k (x, y) = 0. The following lemma will show that, for any two black nodes x, y, the distance dist G • n,k (x, y) is almost the same as the block-distance δ B n,k (x, y).

(0, 1) (1, 1) (1, 1) (1, 1) (2, 2) (2, 2) (2, 2) (3, 3) (3, 3) (0, 1) (1, 1) (1, 1) (1, 1) (2, 2) (2, 2) (2, 2) (3, 3) (3, 3)
G • n,k , (3.3) dist G • n,k (x, y) = δ B n,k (x, y) + i where i ∈ {0,
, then dist G • n,k (x, y) ≤ dist G • n,k (x, 1) + dist G • n,k (y, 1) = 2 = δ B n,k (x, y) + 2.
If both of them are in a block B i+1,n,k for some i ≥ 1, recall that the root of B i+1,n,k is a white node with distance sequence (i k ). Suppose the root of B i+1,n,k has label {a 1 , a 2 , . . . , a k }, then for x ∈ B i+1,n,k , there exists an integer p such that dist G

• n,k (a p , x) = 1. Otherwise if for all m ≤ k, dist G • n,k (a m , x) > 1.
It follows that dist ϕ(B n,k ) (x, 1) > i + 1, which contradicts to the fact x ∈ B i+1,n,k . Similarly, there is an integer q such that dist

B • n,k (a q , y) = 1. Consequently dist G • n,k (x, y) ≤ dist G • n,k (a p , x) + dist G • n,k (a q , y) + dist G • n,k (a q , a p ) = 3, which implies (3.3).
If x, y are not in the same block, let b be the last common parent of x and y in B n,k , then b must be a black node. Let a 1 (resp. b 1 ) be the second black node on the path b -

• -a 1 -• • • -• -x (resp. b -• -b 1 -• • • -• -y) in B n,k .
Then one of the minimal paths connecting x and y in G • n,k must pass node b. This is true because the Ω-k-tree corresponding to the subtree of B n,k rooted at a 1 and the Ω-k-tree corresponding to the subtree of

B n,k rooted at b 1 are completely disjoint in G • n,k . This implies dist G • n,k (x, y) = dist G • n,k (x, b) + dist G • n,k (y, b). Suppose x ∈ B i+1,n,k , there must exist a black node v 1 on the path b -• -a 1 -• • • -• -x, such that dist G • n,k (x, v 1 ) = 1 and v 1 ∈ B i,n,k . For the node v 1 , there exists a black node v 2 on the path such that v 2 ∈ B i-1,n,k and dist G • n,k (x, v 2 ) = 2.
We continue this process until we reach a black node v t such that v t and b are in the same block. Similarly, we can find a sequence of black nodes w 1 , . . . , w s from different blocks such that w s and b are in the same block and dist

G • n,k (y, w s ) = s. It follows that dist G • n,k (x, b) + dist G • n,k (y, b) = δ B n,k (x, b) + δ B n,k (y, b) + dist G • n,k (v t , w s ) = δ B n,k (x, y) + dist G •
n,k (v t , w s ). Since v t and w s are in the same block, we have dist G • n,k (v t , w s ) ≤ 3 and the proof is complete. Lemma 5 allows us to transfer the distance dist G • n,k (x, y) of two vertices x, y in a random Ω-ktree G • n,k to the distance δ B n,k (x, y) of two blocks in a random tree B n,k . In order to prove the convergence of G • n,k to the CRT T e , it is sufficient to prove that with high probability the difference between m k δ B n,k (x, y) and dist Tn (x, y) is uniformly small for all choices of x, y, where T n is the above conditioned critical Galton-Watson tree and m k is a constant. For this purpose we consider the spine of a size-biased enriched tree, which was adapted from the size-biased Galton-Watson tree. This idea has been used in studying the scaling limit of random graphs from subcritical graph classes [START_REF] Panagiotou | Scaling Limits of Random Graphs from Subcritical Classes[END_REF] and was further generalized to the random R-enriched trees [START_REF] Stufler | Random enriched trees with applications to random graphs[END_REF].

In fact, the block-distance δ B n,k (v, 1) to the vertex 1 in the random tree B n,k is not related to the depth of v in B n,k . It turns out that we have to choose a good black node ν i from a block B i,n,k of the random tree B n,k , such that they form a spine ν 1 , . . . , ν m and δ B n,k (ν i , 1) increases as the depth of ν i on this spine increases; see We call a black node v in a (k, Ω)-front coding tree good if one of its white children has distance sequence (i k ) for some integer i ≥ 1. Let B k denote the random (k, Ω)-front coding tree that is generated by the above Boltzmann sampler so that B n,k = (B k : |B k | = n). In the same way, let C i,k be a block of B k which equals B i,n,k if we condition B k on size n. The next Lemma 6 will enable us to construct a size-biased enriched tree. Lemma 6. Suppose that i ≥ 1 and let ξ k,i be the random variable counting the number of good black nodes v in an i-block

C i,k in B k . Then E ξ k,i = 1.
Proof. The offspring ξ • of every white root in B k follows probability distribution (2.14) and the offspring of every black node in B k is distributed as the sum of k independent and identically distributed random variables ξ •,i which are copies of ξ • . The distance sequence on every white node of B k determines if its children (black nodes) are good or not. We first compute E ξ k,1 . Together with (2.7), the first generation of the white root of C 1,k has

E(ξ • ) = i∈Ω out i (C • k (ρ k,Ω )) -1 (B k (ρ k,Ω )) i i! = k -1 (3.4)
expected number of black nodes. We assume that µ 1 is a black node in the first generation, µ 1 has k white-node children in C 1,k , among which (k -1) white nodes have distance sequence (0 k-2 , 1 2 ) and they have E ξ k-1,1 expected number of good black descendants in B k . One white-node child has distance sequence (0 k-1 , 1) and it has E ξ k,1 expected number of good black descendants in

B k . It follows that E ξ k,1 = k -1 E ξ k,1 + (1 -k -1 )E ξ k-1,1 which implies E ξ k,1 = E ξ 2,1 . It is easy to compute E ξ 2,1 by repeating the same procedure, which yields E ξ k,1 = E ξ 2,1 = 1. Similarly, we can show for i = 1, E(ξ k,i ) = k -1 • k • E(ξ k,1 ) = 1. (0, 1) 1 (1, 1) 1 (1, 1) 1 (1, 1) 2 2 2 (2, 2) (2, 2) 2 3 (3, 3) (2, 3) (0, 1) 1 (1, 1) 1 (1, 1) 1 (1, 1) 2 2 2 (2, 2) (2, 2) 2 3 (3, 3) (2, 3) (1, 1) (0, 1) (1, 1) (0, 1) Figure 3.2. A (2,
coding tree B 2 with good nodes drawn with black dots (left) and a size-biased enriched tree B(3) 2 with a spine consisting of selected good nodes drawn with black squares (right).

We will next define a size-biased enriched tree B(m) k from a random (k, Ω)-front coding tree B k . This construction is adapted from [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF], which is a truncated version of the infinite size-biased Galton-Watson tree introduced by Kesten [44], Lyons, Pemantle and Peres [START_REF] Lyons | Conceptual proofs of LlogL criteria for mean behavior of branching process[END_REF]. The size-biased Galton-Watson tree considered the distribution of offsprings in each generation of a Galton-Watson tree, while our size-biased enriched tree considered the distribution of good nodes in every block of B k . Let ξk,i be a random variable with the size-biased distribution (3.5) P( ξk,i = q) = q P(ξ k,i = q).

The expected value E ξ k,i = 1 in Lemma 6 guarantees that ξk,i is a probability distribution on the set N 0 = {0, 1, 2, . . .}.

The size-biased enriched tree B(m)

k is now defined as follows. It starts with a mutant block C 1,k which is rooted at a usual root (that has distance sequence (0, 1 k-1 )) and contains good nodes. We now choose one of these good nodes (which number is distributed according to ξk,1 ) and call it heir (and also mutant). The block C 2,k that is rooted at the child with distance sequence (1 k ) of this heir will be the next mutant block, where we again assume that it has at least one good node. All other blocks that are adjacent to C 1,k are normal. We again choose one of the good nodes of the mutant block C 2,k (which number is distributed according to ξk,2 ) and proceed inductively to * AND BENEDIKT STUFLER choose mutant blocks and heirs till C m,k . All other blocks stay normal. We denote the heir in the m-th mutant block C m,k by h. The path from the root to h is called spine of B(m) k ; see Figure 3.2. The probability that a given mutant block contains q good nodes and one of them is chosen as heir is, see (3.5), q -1 P( ξk,i = q) = P(ξ k,i = q). For any given random (k, Ω)-front coding tree T , let T α denote the tree T with a fixed spine α of block-depth m. Then the probability This shows, once the spine is fixed, that the probability that the size biased tree B(m) k equals T α is the same as the probability of generating T . In fact, (3.6) is true for any fixed spine α; see Eq.(3.2) in [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF]. We will need (3.6) to build a connection between m k δ B n,k (x, y) and d B n,k (x, y) with high probability in Lemma 7.

Lemma 7. Let B n,k be the class of • -• (k, Ω)-front coding trees of size n such that the white root has label {1, 2, . . . , k} and B n,k ∈ B n,k is uniformly selected at random. Let m k = kH k . Then for all s > 1 and 0 < < 1/2 with 2 s > 1, we have for all black nodes x, y in B n,k such that x is an ancestor of y, that one of these two properties

δ B n,k (x, y) ≥ log s (n) and |d B n,k (x, y) -m k δ B n,k (x, y)| ≤ δ B n,k (x, y) 1/2+ , (3.7) δ B n,k (x, y) < log s (n) and d B n,k (x, y) ≤ log s+2 (n) (3.8)
holds with high probability.

Proof. Suppose the opposite of (3.7) is true, that is, there exist black nodes x, y in B k such that x is an ancestor of y and they satisfy

δ B k (x, y) ≥ log s (|B k |) and |d B k (x, y) -m k δ B k (x, y)| > δ B k (x, y) 1/2+ . (3.9)
We will denote by F 1 the set of triples (B k , x, y) (with x, y in B k ) that satisfy (3.9). Thus we just have to show that P((B k , x, y)

∈ F 1 |B k | = n) = o(1)
as n tends to infinity.

Recall that B n,k is a random (k, Ω)-front coding trees generated by the Boltzmann sampler ΓB k (ρ k,Ω ) with n black nodes. Thus, in combination of Lemma 3 and the universal analytic solution of functional equations; see Theorem 2.19 in [START_REF] Drmota | Random trees, An Interplay between Combinatorics and Probability[END_REF], it holds that for a positive constant

σ 2 Ω = kVar ξ • , P[B n,k ] = P[|ΓB k (ρ k,Ω )| = n] = b k,Ω (n)ρ n k,Ω n! B k (ρ k,Ω ) ∼ n -3/2 σ Ω √ 2π as n → ∞. (3.10)
We apply (3.6) on the random (k, Ω)-front coding tree B n,k with a spine that connects x to y. The block-depth of this spine is at least log s n by assumption (3.9), which leads to

P[(B k , x, y) ∈ F 1 |B k | = n] ≤ P[B n,k ] -1 n-1 m=log s n P[( B(m) k , x, y) ∈ F 1 and | B(m) k | = n] ∼ σ Ω √ 2πn 3/2 n-1 m=log s n P[( B(m) k , x, y) ∈ F 1 and | B(m) k | = n] (3.11)
as n → ∞. Here the length of the spine in B(m) k is distributed as the sum of m independent random variables ζ 1,k , ζ 2,k , . . . , ζ m,k where each ζ i,k is distributed as the length of the path from the selected good node in some block C i,k to the root of this block. We have for k ≥ 2, the probability generating functions of random variables ζ i,k are

E z ζ 1,k = k-1 i=1 iz k -iz where i = 1 and E z ζ i,k = z • E z ζ 1,k .
(We just have to extend the proof idea of Lemma 6.) For the case k = 1, every ζ i,1 is distributed with probability P[ζ i,1 = 1] = 1. As an immediate consequence, ζ i,k has finite exponential moments for every i, k and

E[ζ i,k ] = kH k , E[ζ 1,k ] = kH k-1 for k ≥ 2, i = 1 and H k is the k-th Harmonic number. For the case k = 1 we have E[ζ i,1 ] = 1 for every i. We set m k = kH k for k ≥ 1.
Furthermore, the assumption in (3.9) implies

P[( B(m) k , x, y) ∈ F 1 and | B(m) k | = n] ≤ P[| m i=1 ζ i,k -m • m k | > m 1/2+ ]. (3.12)
By applying the deviation inequality (see [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF][START_REF] Panagiotou | Scaling Limits of Random Graphs from Subcritical Classes[END_REF][START_REF] Panagiotou | Scaling Limits of Random Pólya trees[END_REF]) on the random variables ζ 1,k , ζ 2,k , . . . , ζ m,k , we get for some positive constant c1 and m ∈ [log s n, n -1],

P[| m i=1 ζ i,k -m • m k | > m 1/2+ ] ≤ 2 exp(-c 1 (log n) 2s ) = o(n -5/2 ).
Together with (3.11) and (3.12), we can conclude that P

[(B k , x, y) ∈ F 1 |B k | = n] = o(1).
Now we turn to suppose the opposite of (3.8) is true, i.e., there exist black nodes x, y in B k such that x is an ancestor of y. They satisfy

(3.13) δ B k (x, y) < log s (|B k |) and d B k (x, y) > log s+2 (|B k |).
We use the notation F 2 to represent the set of triples (B k , x, y) (with x, y in B k ) that satisfy (3.13).

Again from (3.11) and from the deviation inequality, we obtain for some positive constant c2 ,

P[(B k , x, y) ∈ F 2 |B k | = n] ≤ σ Ω √ 2πn 3/2 log s n m=1 P[( B(m) k , x, y) ∈ F 2 and B(m) k | = n] ≤ σ Ω √ 2πn 3/2 log s n m=1 P[ m i=1 ζ i,k > log s+2 n] = O(n 3/2 )(log s n) exp(-c 2 log 2s+4 (n)) = o (1)
and the proof is complete. Now we are ready to prove our first main result.

Proof of Theorem 1. It follows from Lemma 7 that with high probability

|d B n,k (x, y) -m k δ B n,k (x, y)| ≤ δ B n,k (x, y) 1/2+ + log s+2 (n)
holds for any fixed s and such that 0 < < 1 2 and 2 s > 1, and holds for all black nodes x, y where x is an ancestor of y in the random (k, Ω)-front coding tree B n,k . For any two black nodes µ, ν in B n,k , let α be the last common ancestor of µ and ν (α could be a white node of B n,k ), then (3.14) where H(B n,k ) is the height of random tree B n,k . We recall that d B n,k (µ, ν) = dist Tn (µ, ν). It is clear that H(B n,k ) = H(T n ) and consequently, (3.14) rewrites to

|d B n,k (µ, ν) -m k δ B n,k (µ, ν)| ≤ δ B n,k (µ, α) 1/2+ + δ B n,k (ν, α) 1/2+ + 2 log s+2 (n) ≤ 2H(B n,k ) 1/2+ + 2 log s+2 (n),
|dist Tn (µ, ν) -m k δ B n,k (µ, ν)| ≤ 2H(T n ) 1/2+ + 2 log s+2 (n).
The tree T n contains all black nodes of B n,k and it is a critical conditioned Galton-Watson tree. By applying the tails for the height of T n ; see Theorem 1.2 in [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF] and left-tail upper bounds for the height in [START_REF] Addario-Berry | Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees[END_REF], we obtain the Gromov-Hausdorff distance

d GH (n -1/2 T n , n -1/2 m k B n,k ) ≤ 1 2 max µ,ν |n -1/2 dist Tn (µ, ν) -n -1/2 m k δ B n,k (µ, ν)| ≤ n -1/2 H(T n ) 1/2+ + n -1/2 log s+2 (n) p -→ 0.
Namely, for any fixed ε, the probability of the event d GH (n -1/2 T n , n -1/2 m k B n,k ) ≤ ε converges to 1 as n tends to infinity. Since ξ • has probability distribution (2.14), for any specific degree set Ω, the variance of the offspring distribution in the first generation of the random tree T n is σ 2 Ω = kVar ξ • . Then it follows from Theorem 4 that

σ Ω T n 2 √ n d -→ T e in the metric space (K • , d GH ).
Hence from the convergence of Gromov-Hausdorff distance and with the help of Lemma 5, we get

m k σ Ω 2 √ n B n,k d -→ T e and m k σ Ω 2 √ n G • n,k d -→ T e
where G • n,k is the corresponding rooted Ω-k-tree of B n,k under the bijection ϕ -1 : B n,k → G • n,k . In the beginning of Section 3 and in subsection 2.2 we know that it suffices to prove Theorem 1 for the random k-tree

G • n,k that is uniformly selected from G • n,k . This indicates m k σ Ω 2 √ n G • n,k d -→ T e and m k σ Ω 2 √ n G n,k d -→ T e
where m k = kH k .

In particular, if Ω = N 0 , then σ N0 = k • Var(ξ • ) = 1 where ξ • is Poisson distributed with parameter k -1 . The proof of Theorem 1 is complete.

Proof of Theorem 2

In this section, we are going to construct an infinite Ω-k-tree G ∞,k that is rooted at a front of distinguishable vertices. We then establish the convergence of G • n,k toward this random graph in the sense, that for each fixed integer ≥ 0 the front-rooted sub-(k, Ω)-tree U (G • n,k ) that is induced by all vertices with distance at most from the marked front, converges in distribution to the corresponding sub-(k, Ω)-tree U (G ∞,k ) of the limit object.

By the discussion in Subsection 2.2, the random Ω-k-tree G • n,k is up to relabeling distributed like the Ω-k-tree G n,k that is rooted at a fixed front with labels from 1 to k. Hence we only need to study the neighborhoods of the root-front. If we distinguish any fixed vertex of the marked front in G n,k , for example the vertex with label 1, and also distinguish a fixed vertex of the marked front in G ∞,k , then our limit may be interpreted as a classical local weak limit of a sequence of vertex-rooted random graphs as discussed in Subsection 2.6. This may be justified by the following two arguments. First, as rooted graphs, all k possible vertex-rootings of G n,k are identically distributed, and we shall see below that the same is true for the limit G ∞,k . Second, the -neighborhood of a vertex of any front-rooted Ω-k-tree is always a subgraph of the -neighborhood of the marked front, and hence the weak convergence of the neighborhoods of the front implies the weak convergence of the neighborhoods of the vertices. The strategy of the proof is as follows. We may generate the random Ω-k-tree G n,k by applying the bijection ϕ -1 : C n,k → G n,k to the random (k, Ω)-front coding tree C n,k . This random coding tree may be generated by conditioning a Boltzmann sampler ΓC k (ρ k,Ω ) on producing a coding tree with n black vertices. We observe that any ordered tree of white vertices where the outdegree of any vertex is a multiple of k may be interpreted as a (k, Ω)-front coding tree by adding black vertices in a canonical way. Here different plane trees may correspond to the same unlabelled (k, Ω)-tree, but this will not be an issue. We may use this construction in order to formulate a coupling of the Boltzmann sampler ΓC k (ρ k,Ω ) with a Galton-Watson tree T • that has a modified root-degree. If we condition this locally modified Galton-Watson tree on having (kn + 1) vertices, then the result T n,• corresponds, up to relabeling, to the (k, Ω)-front coding tree C n,k . By the similar arguments as for the classical local convergence of simply generated trees, the random tree T n,• converges weakly toward an infinite plane tree T ∞,• that may be interpreted as a (k, Ω)coding tree C ∞,k and consequently also as a front-rooted Ω-k-tree G ∞,k . The final step in the proof is to deduce local convergence of the random Ω-k-tree G n,k from this convergence of random trees.

The construction of a (k, Ω)-front coding tree ψ(T ) out of a plane trees T , where the outdegree of each vertex is a multiple of k, is straight-forward. We canonically partition the offspring set of each vertex v of T into an ordered list of groups G 1 (v), G 2 (v), . . . of k consecutive vertices. The edges between v and its offspring are then deleted, and for each group G i (v) we add a black offspring vertex u i (v) to v and add further edges such that G i (v) is the offspring set of u i (v). This construction is illustrated in Figure 4.1.

We may now use this to formulate a coupling of Boltzmann distributed (k, Ω)-front coding trees with a modified Galton-Watson tree. Similar as in Remark 2, a Boltzmann sampler ΓC k (ρ k,Ω ) is given by starting with a white root, and connecting it with the roots of a random number η • of independent • -• (k, Ω)-front coding trees where each is sampled according to an independent call to the Boltzmann sampler ΓB k (ρ k,Ω ) from Lemma 3. The distribution of η • is given by

P(η • = i) = 1 C k (ρ k,Ω ) (B k (ρ k,Ω )) i i!
for all i ∈ Ω. Recall that the sampler in Lemma 3 starts with a black node with k white nodes as offspring. Each of the white nodes receives black offspring according to an independent copy of the random number ξ • , whose distribution is given in (2.14). Then the sampler recurs, that is, any black node in the youngest generation receives k white vertices as offspring, each of which receives a random number (possibly zero) of black offspring, and so on. Let T • denote a modified Galton-Watson tree, where each vertex receives offspring according to an independent copy of ξ := kξ • , except for the root, which receives offspring according to η := kη • . The order in which the recursion takes place in ΓB k (ρ k,Ω ) and ΓC k (ρ k,Ω ) does not matter, hence the (k, Ω)-coding tree ψ(T • ) is up to relabeling distributed like the (k, Ω)-coding tree ΓC k (ρ k,Ω ). Moreover, if we let T n,• denote the tree T • conditioned on having (kn+1) vertices, then ψ(T n,• ) is distributed like the random (k, Ω)-front coding tree C n,k .

Note that (3.4) implies that E[ξ] = 1, and both ξ and η have finite exponential moments. We define the size-biased versions of these offspring distributions by

P( ξ = i) = iP(ξ = i) and P(η = i) = iP(η = i)/E[η].
Let T ∞,• denote the following random infinite (but locally finite) plane tree. There are two types of non-root vertices, mutant and normal. The root receives offspring according to η, and one of its sons is selected uniformly at random and declared mutant, whereas the others are normal. Normal vertices receive offspring according to an independent copy of ξ, all of which are normal. Mutant vertices receive offspring according to an independent copy of ξ, among which one is selected uniformly at random and declared mutant, whereas the others are normal. Hence T ∞,• is an infinite plane tree with a distinguished path that starts at the root and traverses the mutant vertices. We call this path the spine of T ∞,• .

We describe the convergence of the random tree T n,• toward the limit tree T ∞,• using a slight modification of the arguments in Janson's survey [START_REF] Janson | Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation[END_REF]. For each plane tree T and each integer h ≥ 0 let T [h] denote the tree obtained by cutting away all vertices with height larger than h. Lemma 8. For any integer h ≥ 0, it holds that T A classical combinatorial observation, also called the cycle lemma, states that for any sequence x 1 , . . . , x s ≥ -1 of integers satisfying s i=1 x i = -r for some r ≥ 1, there are precisely r integers 1 ≤ u ≤ s such that the cyclically shifted sequence x The tree T has precisely (Dt + 1) vertices with height h. Hence the event T which, together with (4.4), implies (4.1) and we are done.

We are now finally in the position to complete the proof of our second main theorem.

Proof of Theorem 2. Let be an integer and let G be an arbitrary finite unlabelled Ω-k-tree that is rooted at a front. We claim that there exist an integer L ≥ 0, that depends on both and G, and a set E of finite plane trees, such that any plane tree T , that corresponds to a (k, Ω)-front coding tree ψ(T ) and hence to a front-rooted Ω-k-tree G(T ) := ϕ The reason why there exist such an integer L and the set E is rather subtle. To each plane tree T we may associate a unique sequence of increasing subtrees T 0 , T 1 , . . . of T that all contain the root-vertex of T and have the property G(T i ) = U i (G(T )) for all i. Of course, the tree T may, in general, have arbitrarily large height. However, in order to satisfy G(T ) = G, the tree T may not have more vertices, than the number of fronts in G. In particular, the height of T is bounded by the number of fronts of G. Hence there exists a finite integer L such that for any plane tree T we may decide whether U (G(T )) = G by only looking at T [L] .

  .1.

Figure 1 . 1 .

 11 Figure 1.1. a 2-tree (left), a partial 2-tree (middle) and an Ω-2-tree (right) where Ω = {0, 1, 2}.

2 'Figure 2 . 1 .

 221 Figure 2.1. When Ω = {0, 1, 2, 3}, an Ω-2-tree rooted at a front whose vertices are labelled by 1, 2 (left) and the corresponding (2, Ω)-front coding tree C n,2 rooted at a white node labelled by {1, 2} (middle); finally the derived black tree T n consists just of only black nodes of C n,2 (right).

2. 5 .

 5 Gromov-Hausdorff convergence and the CRT. Let e = (e t ) 0≤t≤1 denote the Brownian excursion of duration one. Then this (random) continuous function e induces a pseudo-metric on the interval [0, 1] by d e (u, v) = e(u) + e(v) -2 inf u≤s≤v e(s) for u ≤ v. This defines a metric on the quotient T e = [0, 1]/ ∼ where u ∼ v if and only if d e (u, v) = 0. The corresponding random pointed metric space (T e , d e , r 0 (T e ))

Figure 3 . 1 .

 31 Figure 3.1. A decomposition of a random (2, Ω)-front coding tree B n,2 into blocks B i,n,2 (left) where the pair (a, b) of integers represents the distance sequence on the root of a block. A spine (right) consists of selected good nodes in B n,2 .

  Fig 3.1 and 3.2.

=

  T α , with α as a spine) = P(B k = T ).

  ψ

Figure 4 . 1 .

 41 Figure 4.1. The construction of (k, Ω)-front coding trees out of plane trees where the outdegree of each vertex is a multiple of illustrated for the special case k = 2.

  .Proof. It suffices to show for each plane tree T with height h that lim n→∞P(T[h] n,• = T ) = P(T [h] ∞,• = T ). (4.1)As T ∞,• has infinite height, this already implies that H(T n,• ) ≥ h occurs with probability tending to 1, and consequently T . In order to check (4.1), let d 1 , . . . , d t denote the depth-firstsearch ordered list of the degrees of all vertices in the pruned tree T[h-1] . Moreover, let (ξ i ) i∈N denote a family of independent copies of ξ. Set N = kn + 1 andD = d 1 + • • • + d t . The probability P(|T • | = N, T [h] • = T ) is given by P(η = d 1 ) N -1, D + m j=t+1ξ j ≥ m for all t < m < N ).(4.2)

=

  x 1+(i+u) mod s satisfies i=1 x (u) i > r for all 1 ≤ ≤ s -1; see for example[START_REF] Janson | Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation[END_REF] Lem. 15.3]. Consequently, (4.2) may be simplified toDt + 1 Nt P(η = d 1 )

ξ 2 d=1P

 2 = T corresponds to precisely (Dt + 1) possible outcomes for the first (h + 1) levels of T ∞,• , depending on the location for the unique spine vertex with height h. Each has the same probability given byE[η] -1 P(η = d 1 ) t j=2 P(ξ = d j ). Thus, P(T [h] ∞,• = T ) = (Dt + 1)E[η] -1 P(η = d 1 ) t j=2 P(ξ = d j ) and (4.2) becomes P(|T • | = N, T j = N -1).The central local limit theorem for the sum of independent identically distributed random integers yields thatP(D + N j=t+1 ξ j = N -1) = (1 + o(1)) k gcd (Ω out ) 2πN Var[ξ]and consequentlyP(|T • | = N, T [h] • = T ) = (1 + o(1))P(T [h] ∞,• = T )n -3/2 E[η] gcd (Ω out ) 2πkVar[ξ] .(4.4)Let d(o) denote the root-degree of T • . It holds, since ζ has finite exponential moments, that P(η ≥ log(n) 2 ) is exponentially small. Hence, using the cycle lemma and central local limit theorem in an identical fashion as above, it follows thatP(|T • | = N ) = o(n -3/2 ) + log(n)

  -1 (ψ(T )), has the propertyU (G(T )) = G if and only if T [L] ∈ E.This is certainly sufficient for deducing Theorem 2, as by Lemma 8 it then follows that limn→∞ (G • n,k ) = G) = P(U (G ∞,k ) = G) with G ∞,k denoting the Ω-k-tree corresponding to T ∞,• .

  If x, y are in the same block, i.e., δ B n,k (x, y) = 0. If both of them are in a block B 1,n,k

1, 2, 3}. * AND BENEDIKT STUFLER Proof.

Acknowledgement

We would like to thank three anonymous reviewers from Analco 16 for their very helpful suggestions and comments on the earlier version of this manuscript.

The first author is partially supported by the Austrian Science Fund FWF, Project SFB F50-02. The second author was supported by the German Research Foundation DFG, JI 207/1-1, and is supported by the Austrian Research Fund FWF, Project SFB F50-03. The third author is supported by the German Research Foundation DFG, STU 679/1-1.

MICHAEL DRMOTA, EMMA YU JIN *