Abstract
We discuss various forms of convergence of the vicinity of a uniformly at random selected vertex in random simply generated trees, as the size tends to infinity. For the standard case of a critical Galton-Watson tree conditioned to be large the limit is the invariant random sin-tree constructed by Aldous (1991) . In the condensation regime, we describe in complete generality the asymptotic local behaviour from a random vertex up to its first ancestor with large degree. Beyond this distinguished ancestor, different behaviour may occur, depending on the branching weights. In a subregime of complete condensation, we obtain convergence toward a novel limit tree, that describes the asymptotic shape of the vicinity of the full path from a random vertex to the root vertex. This includes the case where the offspring distribution follows a power law up to a factor that varies lorigonzales@example.org.
Introduction
The study of the asymptotic local behaviour of the vicinity of the fixed root vertex of random trees has received considerable attention in recent literature. Jonsson and Stefánsson [15] described a phase transition between an infinite spine case and a condensation setting for large Galton-Watson trees with a powerlaw offspring distribution. A third regime for random simply generated trees with superexponential branching weights was studied by Janson, Jonsson and Stefánsson [14] . The asymptotic shape of large simply generated trees as their size tends to infinity was later described in complete generality by Janson [13] . Abraham and Delmas [2, 3] classified the limits of conditioned Galton-Watson trees as the total number of vertices with outdegree in a given fixed set tends to infinity. Limits of Galton-Watson trees having a large number of protected nodes were established by Abraham, Bouaziz, and Delmas [1] . The asymptotic shape of conditioned multi-type Galton-Watson trees was studied by Stephenson [18] , Abraham, Delmas, and Guo [4] , and Pénisson [17] .
Clearly considerable effort and progress is being made in understanding local limits of random trees that describe the asymptotic behaviour near the fixed root vertex, and for random simply generated trees even a complete classification is available. As for the question of the asymptotic shape of the vicinity of a random vertex, Aldous [5] studied in his pioneering work asymptotic fringe distributions for general families of random trees. For the case of critical Galton-Watson trees, he established, at least when the offspring distribution has finite variance, convergence of the tree obtained by rerooting at a random vertex. A recent work by Holmgren and Janson [11] studied fringe trees and extended fringe trees of models of random trees that may be described by the family tree of a Crump-Mode-Jagers branching process stopped at a suitable time, including random recursive trees, preferential attachment trees, fragmentation trees and m-ary search trees.
Janson [13] distinguishes three types of simply generated trees, numbered I, II and III, and for each the local limit exhibits a distinguishing characteristic. We use this terminology in our study of the vicinity of a random vertex. In the type I setting, the simply generated tree T n is distributed like a critical Galton-Watson tree conditioned on having n vertices. Thus the height of a random vertex in T n is typically large and extended fringe trees are typically small. In this regime, the limit is given by the random sin-tree constructed by Aldous [5] . Here the word sin refers to the fact that, like the Kesten tree, this tree has almost surely up to finite initial segments only a single infinite path. When the offspring distribution has finite variance, we may even verify total variational convergence of the extended fringe subtree up to o( √ n)-distant ancestors. While trees in the type I regime usually have small maximum degree, the types II and III are characterized by the appearance of vertices with large degree, which may be viewed as a form of condensation. Specifically, type II simply generated trees correspond to subcritical Galton-Watson trees with a heavy-tailed offspring distribution, and type III simply generated trees have superexponential branching weights such that no equivalent conditioned Galton-Watson tree exists. Our main contribution is in this condensation setting, where contrary to the type I regime a random vertex may be near to the root, and extended fringe trees may have size comparable to the total number of vertices of T n , as we are likely to encounter an ancestor with large degree. This is also a major difference to the settings addressed in the mentioned works by Aldous [5] and Holmgren and Janson [11] .
We set up a compact space that encodes rooted plane trees that are centered around a second distinguished vertex, and establish several limit theorems. For arbitrary weight-sequences having type II or III, we establish a limit that describes the vicinity of a random vertex up to and including its first ancestor with large degree. Here large means having outdegree bigger than a deterministic sequence that tends to infinity sufficiently slowly. The asymptotic shape of what lies beyond this ancestor appears to depend on the branching weights. In a way, the vertex with large degree obstructs the view to older generations.
We describe a novel limit object T * given by a random pointed plane tree, in which the pointed vertex has random distance from its first ancestor with infinite degree, and this ancestor again has a random number of ancestors with finite degree before the construction breaks off. For arbitrary weight-sequences, the asymptotic probability for the vicinity of a random vertex of T n to have a specific shape that admits at most one single ancestor of large degree, but allows ancestors with small degrees afterwards, coincides with the corresponding probability for the tree T * . Our approach is based on a heavily modified depth-first-search to explore the tree T n . This yields information on how parts of a limit tree for the complete vicinity, that is not truncated at the first large ancestor, must look, if the simply generated tree T n pointed at a random vertex converges weakly (along a subsequence). Note also that the compactness of the space, in which we formulate our limits, guarantees the existence of such subsequences. Thus the obstruction by the ancestor with large degree, that prevents us from seeing older generations, is not a complete blockage. However, this is not yet sufficient to deduce convergence in the space of pointed plane trees. In general, the tip of the backwards growing spine, where the construction of T * breaks off, may correspond to the root vertex of T n , but just as well to a second ancestor with large degree.
If the branching weights belong to a general regime of complete condensation, we manage to surpass the blockage and deduce weak convergence toward T * . There are two main steps involved. First, we show that convergence toward T * is in fact equivalent to weak convergence of the height of a random vertex in T n to the height of the pointed vertex in the tree T * , which in the type II regime is distributed like 1 plus the sum of two independent identically distributed geometric random variables, and in the type III regime equals 1. In this case, the root of T * really corresponds to the root of T n . The second step verifies this property in the case of complete condensation, where the maximum degree of T n has the correct order.
In particular, Kortchemski's central limit theorem for the maximum degree [16, Theorem 1] allows us to deduce convergence toward T * in the general case of a subcritical Galton-Watson tree conditioned on having n vertices, if the offspring distribution ξ satisfies
for a constant α > 2 and a function f that varies lorigonzales@example.org. In the type III regime where branching weights grow superexponentially fast, we consider the specific case where
It is known that for these weights the maximum degree of T n has order n + o p (n), which may also be seen as complete condensation, see Janson, Jonsson, and Stefánsson [14] and Janson [13, Example 19.36] . Thus here the tree T * is also the weak limit of the simply generated tree T n pointed at a random vertex. There are, however, also examples of superexponential branching weights that exhibit a more irregular behaviour [13, Example 19.38] , in which we are going to argue that weak convergence toward T * does not hold.
Outline
In Section 2 we fix basic notations, and Section 3 is dedicated to recall necessary background on simply generated trees. In Section 4 we describe the metric space of rooted plane trees that are centered at a pointed vertex. This will be the setting in which we formulate our limit theorems. In Section 5 we present our main results, and in Section 6 their proofs.
Notation
We let N denote the set of positive integers and set N 0 = N∪{0}. The positive real numbers are denoted by R >0 . Throughout, we usually assume that all considered random variables are defined on a common probability space. The total variation distance between two random variables X and Y with values in a countable state space S is defined by
A sequence of real-valued random variables (X n ) n≥1 is stochastically bounded, if for each > 0 there is a constant M > 0 with lim sup
We denote this by X n = O p (1). Likewise, we write X n = o p (1) if the sequence converges to 0 in probability. We use d −→ and p −→ to denote convergence in distribution and probability. A function
is termed slowly varying, if for any fixed t > 0 it holds that
Given sets M and N , we let N M denote the set of all maps from M to N . We also let N (N) denote the set of all finite sequences of elements from N .
Simply generated trees
A plane tree is a rooted tree in which the offspring set of each vertex is endowed with a linear order. (Such trees are also sometimes referred to as planted plane trees or corner rooted plane trees, in order to distinguish them from related planar structures [9] .) Given a plane tree T and a vertex v ∈ T we let d + T (v) denote its outdegree, that is, the number of offspring. Its height h T (v) is its distance from the root-vertex.
We let w = (ω i ) i≥0 denote a sequence of non-negative weights satisfying ω 0 > 0 and ω k > 0 for at least one k ≥ 2. The weight of a plane tree T is defined by
The simply generated tree T n with n vertices gets drawn from the set of all nvertex plane trees with probability proportional to its weight. Galton-Watson trees conditioned on having a fixed number of vertices are encompassed by this model of random plane trees. Of course, the tree T n is only well-defined if there is at least one plane tree with n vertices that has positive weight. We set
As argued in [13, Corollary 15.6] , n-sized trees with positive weight may only exist for n ≡ 1 mod span(w), and conversely, they always exist if n is large enough and belongs to this congruence class. We tacitly only consider such n throughout this paper.
Three types of weight-sequences
Janson [13, Chapter 8] distinguishes three types of weight-sequences. The classification is as follows. Let ρ φ denote the radius of convergence of the generating series
As argued in [13, Lemma 3.1], if ρ φ > 0 then the function
with the following properties. If ν ≥ 1, then there is a unique number τ with ψ(τ ) = 1 and we say the weight sequence w has type I. If 0 < ν < 1, then we set τ := ρ φ < ∞ and say w has type II. If ρ φ = 0, we say w has type III and set ν = 0 and τ = 0.
The constant ν has a natural interpretation as the supremum of the means of all probability weight sequences equivalent to w. The inclined reader may see [13, Remark 4.3] for details.
An associated Galton-Watson tree
We define the probability distribution (π k ) k on N 0 by
The mean and variance of the distribution (π k ) k are given by
We let ξ denote a random non-negative integer with density (π k ) k , and T a GaltonWatson tree with offspring distribution ξ. Note that if w has type III, then ξ = 0 almost surely and the tree T consists of a single deterministic vertex. As detailed in [13, Section 4] , if w has type I or II then the simply generated tree T n is distributed like the Galton-Watson tree T conditioned on having n vertices.
4 The space of pointed plane trees 4 .1 Centering at a specified vertex
The offspring of each vertex in a plane tree is endowed with a linear order. We usually imagine a planar embedding where the root is at the top and the offspring of each vertex is ordered from the left to the right below it, ascendingly according to the corresponding linear order. Thus the "left-most" offspring is the minimum of the order. This is of course purely a matter of taste. Some prefer their trees to grow upwards, but regardless of the way for visualizing plane trees, we may use terms like height and depth-first-search in their usual sense without risk of confusion. In the present work we will also encounter plane trees that have no root, but whose vertex sets are endowed with a partial order that specifies the ancestry relations, and whose offspring sets are endowed with a linear order that is not required to have a smallest element. Traditionally, plane trees are encoded as subtrees of the Ulam-Harris tree. The Ulam-Harris tree U ∞ is an infinite plane tree with vertex set
given by the space of finite sequences of non-negative integers. Its root vertex is the unique sequence with length zero, and the ordered offspring of a vertex v are the concatenations (v, i) for i ≥ 1. Thus a plane tree is a subtree of the Ulam-Harris tree that contains its root, such that the offspring set of each vertex is an initial segment of the offspring of the corresponding vertex in U ∞ . Here we explicitly allow trees with infinitely many vertices, and vertices with countably infinite outdegree. If all outdegrees of a plane tree are finite, we say that it is locally finite. The tree is finite, if its total number of vertices is. We will usually let o denote the root-vertex of a plane tree.
Subtrees of the Ulam-Harris tree are however not an adequate form to represent the vicinity of a specified vertex in a plane tree. If this vertex does not coincide with the root of the tree, then it has an ordered sequence of ancestors and possibly also siblings that lie to the left and right of it. If we look at a random vertex of the simply generated T n , then it may happen that the number of siblings to the left and/or right of it is asymptotically large, or that its distance from the root vertex is large. A sensible space in which we may describe the limit of the vicinity of the random vertex in T n must hence contain trees with a center that may have infinitely many ancestors, such that each may have infinitely many siblings to the left and/or right of it, including the center vertex itself.
For this reason, we describe the construction of an infinite tree U
• ∞ that is embedded in the plane and has a spine (u i ) i≥0 that grows "backwards". That is, we construct the tree U • ∞ by starting with an infinite path u 0 , u 1 , . . . u i of abstract vertices and define u i to be a parent of u i−1 for all i ≥ 1. Additionally, any vertex u i with i ≥ 1 receives an infinite number of vertices to the left and to the right of its distinguished offspring u i−1 , and each of these "non-centered" offspring vertices is the root of a copy of the Ulam-Harris tree U ∞ . To conclude the construction, the start-vertex u 0 of the spine also gets identified with the root of a copy of U ∞ . We let V Figure 1 .
Note that the vertex set V
• ∞ carries a natural partial order (given by the transitive hull of the parent-child relations specified in the construction of U • ∞ ), and the offspring set of any given vertex carries a natural linear order. This allows us to continue using the terms ancestor and offspring in this context.
The precise realization of the tree U • ∞ will not be relevant for our arguments. One way to make its construction formal would be to define V
, with u i corresponding to (i, 0, ∅) for all i ≥ 0, and u i having the linearly ordered offspring set {(i, j, ∅) | j ∈ Z} for all i ≥ 1. Any point (i, j, ∅) with either (i, j) = (0, 0), or i ≥ 1 and j ∈ Z \ {0} is the root of a copy of the Ulam-Harris tree with vertex set {(i, j, v) | v ∈ N (N) }. A plane tree T together with a distinguished vertex v 0 is called a pointed plane tree, and may be interpreted in a canonical way as a subtree of U 
Topological properties
Any plane tree T may be identified with its family of outdegrees
where we set N 0 = N 0 ∪ {∞}. Here we use the convention d
is not a vertex of the tree T . We endow N 0 with the one-point compactification topology of the discrete space N 0 . Thus plane trees are elements of the compact product space N V∞ 0 . It is not hard to see that the subspace
of all plane trees is closed.
Similarly, we may identify a pointed plane tree T • = (T, v 0 ) with the corresponding family of outdegrees (d
for v / ∈ {u 1 , u 2 , . . .}, and
Here the two numbers represent the number of offspring vertices to the left and right of the distinguished son u i−1 , and the * -placeholder represents the fact that the vertex has no offspring. Since N 0 is a compact Polish space, so are the product N 0 ×N 0 and the disjoint union topology on { * } (N 0 × N 0 ). Hence the space of all families (d
is the product of countably many compact Polish spaces, and hence also compact and Polish. The subset T
• of all elements that correspond to trees (that is, connected acyclic graphs) is closed, and hence also a compact Polish space with respect to the subspace topology.
Checking that T • is closed is analogous to the arguments for T: We may define the subset T
• by certain local conditions. In order for a family (d
for all siblings v of u i−1 that lie more than b to the right of u i−1 or more than b to the left of u i−1 . We furthermore require that for any vertex u ∈ V
for all offspring vertices v of u that are placed more than k to the right in the linear order of the offspring set of u. Now, if τ • n is a deterministic sequence in the product space that converges toward a limit τ / ∈ T • , then the limit must violate one of these conditions. But this implies that τ
• n violates this condition as well for all sufficiently large n. So, by contraposition, T
• must be closed. The limit tree T * in the type I regime. Each triangle represents an independent copy of the Galton-Watson tree T . For each i ≥ 1 the vertex u i receives offspring according to an independent copy ofξ, and the location of u i−1 within that offspring set is chosen lorigonzales@example.org.
The limit theorems
As discussed in Section 3 there is a probability distribution (π k ) k associated with the weight sequence w, with density given in (3.1). Let ξ be distributed according to (π k ) k and let T be a ξ-Galton-Watson tree. By Equation 3.2 it holds that
We may consider the size-biased random variableξ with values in N 0 and distribution given by
For any tree T and any vertex v ∈ T we let f (T, v) denote the fringe-subtree of T at v. That is, the maximal subtree of T that is rooted at the vertex v.
Throughout the following, we let v 0 denote a uniformly at random selected vertex of the simply generated plane tree T n , that in the type I and II regime is distributed like the Galton-Watson tree T conditioned on having n vertices.
The type I regime
If the weight-sequence w has type I, thenξ < ∞ almost surely, and we define the random pointed tree T * as follows. Let u 0 be the root of an independent copy of the Galton-Watson tree T . For each i ≥ 1, we let u i receive offspring according to an independent copy ofξ. The vertex u i−1 gets identified with an uniformly at random chosen offspring of u i . All other offspring vertices of u i becomes the root of an independent copy of the Galton-Watson tree T . Compare with Figure 2 .
Theorem 5.1. If the weight-sequence w has type I, then
Let T be a plane tree, v ∈ T a vertex, and k ≥ 0 an integer. If the vertex v has a kth ancestor v k , then we may define the pointed plane tree H k (T, v) as the fringe tree f (T, v k ) that is rooted at the vertex v k and pointed at the vertex v. Here we use the term vertex in the graph-theoretic sense, since the coordinates of the vertex v as node of the Ulam-Harris tree depend on whether we talk about v ∈ T or v ∈ f (T, v k ). If the vertex v has height h T (v) < k, we set H k (T, v) = for some placeholder symbol .
Theorem 5.2. Suppose that weight-sequence has type I and the offspring distribution ξ has finite variance. Let k n be an arbitrary sequence of non-negative integers that satisfies k n / √ n → 0. Then
as n becomes large.
Here we use the redundant notation (T * , u 0 ) to emphasize that the tree T * is marked at the vertex u 0 .
Complete condensation in the type II regime
If the weight-sequence w has type II or III, then we construct T * similarly as in the type I case, letting u 0 become the root of an independent copy of the Galton-Watson tree T , and letting for i = 1, 2, . . . the vertex u i receives offspring according to an independent copyξ i ofξ, where a uniformly at random chosen son gets identified with u i−1 (specifying the number of siblings to the left and right of u i−1 ) and the rest become roots of independent copies of T . We proceed in this way for i = 1, 2, . . . until it occurs for the first time i 1 thatξ i 1 = ∞. When ξ 1 , . . . ,ξ i 1 −1 < ∞ andξ i 1 = ∞, then u i 1 receives infinitely many offspring to the left and right of its son u i 1 −1 . Each of these vertices (except u i 1 −1 of course) gets identified with an independent copy of the Galton-Watson tree T . We then proceed as before for i = i 1 , i 1 + 1, . . ., such that u i receives offspring according to an independent copyξ i ofξ, with a random son being identified with u i−1 and the rest becoming roots of independent copies of T , until it happens for the second time i 2 thatξ i 2 = ∞. 
In particular, this is the case when there is a constant α > 2 and a slowly varying function f such that for all k
Figure 3:
The limit tree T * in the complete condensation regime. The vertex u i 1 is the only one having infinite degree, and each triangle represents an independent copy of the Galton-Watson tree T .
Here we make use of a result by Kortchemski [16, Theorem 1] who established a central limit theorem for the maximum degree, that ensures that ∆(T n ) has the correct order if the offspring distribution ξ has a power law up to a slowly varying factor. There are also examples of offspring distributions with a more irregular behaviour. Janson [13, Example 19 .37] constructed a weight sequence such that along a subsequence n = n k it holds that ∆(T n ) = o p (n), and along another subsequence several vertices with degree comparable to n exist. This may be seen as incomplete condensation.
The proof idea of Theorem 5.3 is to deduce the asymptotic distribution of the height h Tn (v 0 ) by localizing the vertex of T n having maximum degree at a position, that was also given in [16, Theorem 2] using results by Armendáriz and Loulakis [6] concerning conditioned random walks having a subexponential jump distribution. To do so, we employ results of Janson [13, Chapter 20 ] that (partially) use
but do not assume the offspring distribution to be subexponential. The following main lemma, which characterizes convergence toward the tree T * in terms of weak convergence of the height h Tn (v 0 ), then finalizes the proof of Theorem 5.3.
Lemma 5.4. If the weight-sequence w has type II or III, then the following three conditions are equivalent.
Note that h T * (u 0 ) is distributed like 1 plus the sum of two independent identically distributed geometric random variables that assume an integer i with probability µ i (1 − µ).
Complete condensation in the type III regime
If the weight-sequence w has type III, then it holds that µ = 0 and almost surely ξ = 0 andξ = ∞. Here the Galton-Watson tree T is always equal to a single point. Hence the tree T * is obtained by letting u 1 have infinitely many offspring to the left and right of u 0 , all of which (including u 0 ) are leaves.
Proposition 5.5. If the weight-sequence w has type III, then the following claims are equivalent.
A general class of weight-sequences that demonstrate this behaviour is given by
Here we have used that if ω k = k! α with α > 0 a constant, then it is known [13, Example 19.36] , that the largest degree in T n has size n + o p (n). But there are also other examples that exhibit a more irregular behaviour. In [13, Example 19 .38] a weight-sequence is constructed such that along a subsequence n = n k , for each j ≥ 1 the jth largest degree Y (j) in T n k satisfies Y (j) = 2 −j with high probability. This may be seen as incomplete condensation. It is clear that in this case the limit of (T n , v 0 ), if it exists at all, must have a different shape than T * .
Large nodes and truncated limits
Suppose that the weight sequences w has type II or type III. The limit theorems in Subsections 5.2 and 5.3 work in settings of complete condensation, where the maximum degree of the tree T n satisfies
If we content ourselves with the vicinity of the vertex v 0 up to and including the first vertex having large degree, we may obtain a limit theorem in complete generality. We are also going to construct a coupling to demonstrate how the vertex with infinite degree in the limit corresponds to a vertex with large degree in the simply generated tree T n .
Janson [13, Lemma 19 .32] showed that there is a deterministic sequence Ω n that tends to infinity sufficiently slowly, such that for any sequence K n → ∞ with K n ≤ Ω n it holds that the numbers N k of vertices with outdegree k in the tree T n satisfy
and
The sequence Ω n may be replaced by any sequence that tends to infinity more slowly. Hence we may assume without loss of generality that Ω n additionally satisfies
LetD n denote a random positive integer, that is independent from all previously considered random variables, with distribution given bỹ
Here we let o denote the root-vertex of T n . That is,D n is distributed like the root-degree conditioned to be "large". We form the random treeT * n in a similar manner as the random tree T * . The vertex u 0 becomes the root of an independent copy of the Galton-Watson tree T . For i = 1, 2, . . . the vertex u i receives offspring according to independent copyξ i ofξ, where a randomly chosen son gets identified with u i−1 and the rest become roots of independent copies of T . We proceed in this way for i = 1, 2, . . . until it occurs thatξ i = ∞. Whenξ 1 , . . . ,ξ i−1 < ∞ and ξ i = ∞, then u i receivesD n offspring vertices, such that a uniformly at random chosen one gets identified with u i−1 , and the rest get identified with the roots of independent copies of T . Rather than continuing with the spine as in the construction of the tree T * , we stop at this point, so that u i becomes the root of this tree.
Given a pointed tree T • = (T, v) and an ancestor a of v, we let f • (T • , a) denote the fringe subtree of T at a that we consider as pointed at the vertex v. We refer to f
• (T • , a) as the pointed fringe subtree of the pointed tree T • at the vertex a. Let v 0 denote a uniformly at random selected vertex of the simply generated tree T n . Let H(T n , v 0 , Ω n ) denote the pointed fringe subtree of (T n , v 0 ) at the youngest ancestor of v 0 that has outdegree bigger than Ω n . If no such vertex exists (which is unlikely to happen, as we are going to verify), set H(T n , v 0 , Ω n ) = for some fixed placeholder value .
Theorem 5.6. Suppose that the weight sequence w has type II or III. LetT * denote the pointed fringe subtree of the tree T * at its unique vertex with infinite degree. Then it holds that
The strength of this theorem is its generality, as we make no additional assumptions on the lorigonzales@example.org. It is suitable for applications where it is not necessary to look behind the large vertex.
We may still improve upon this. For each n, let T * n be constructed fromT * by pruning at its root vertex such that its outdegree becomesD n . Of course we have to select one of theD n ways of how much we prune from the left and right so that the total outdegree becomesD n , and we choose an option lorigonzales@example.org. For each integer m ≥ 0 we letV
• of locally finite trees is induced by the metric
This can be verified using the fact that a sequence (T n ) n in T • converges towards an element T ∈ T
• if and only if d
Theorem 5.7. Suppose that the weight sequence w has type II or III. For any finite set of vertices x 1 , . . . , x r ∈ V
• ∞ it holds that
Equivalently, there is a coupling of (T n , v 0 ) andT * n such that
In Equation (20.4) and the subsequent paragraph of [13] , Janson also argues that if
Hence in the complete condensation regime, we may chooseD n in the coupling of Theorem 5.7 such thatD n = ∆(T n ) with probability tending to 1 as n becomes large. This yields the asymptotic location of the vertex with maximum degree with respect to the random vertex v 0 . In a way, we could say that the ancestor of the random vertex v 0 with large degree in T n blocks the view, if we are not in the complete condensation regime. As we shall see in Lemma 6.1 and Lemma 6.2 it does not block it completely though. Roughly said, for each fixed k ≥ 1 we obtain the asymptotic probability for the event, that the pointed fringe subtree at the kth ancestor of the random vertex v 0 has a given shape that involves at most one large vertex on the spine. This yields more information than Theorem 5.6 on how a limit treeT must look, if (T n , v 0 ) converges weakly (along a subsequence). (Note that the compactness of the space T
• guarantees the existence of such subsequences.) It also suggests that if the center vertex ofT has almost surely at most one ancestor with infinite degree, then it must already hold thatT d = T * , but we leave it to the inclined reader to pursue this line of thought further.
6 Proof of the main results
Preliminaries
for all i, as this will be the case that we will consider most of the time. This model is related to the outdegree sequence (d 0 , . . . , d n−1 ) of the simply generated tree T n by
Here we may form the outdegree sequence according to depth-first-search order, but many other form of vertex explorations are possible. In general, consider the following family of algorithms, that order the vertices of finite deterministic plane trees.
1. Take a plane tree T as input.
2. Let P denote the ordered list of visited vertices, that initially is empty. Let Q denote the ordered queue of vertices that are scheduled to be visited next, that we initialize with the root of T .
3. Move the first vertex v of the ordered queue Q to the end of the list P of visited vertices. We then modify the queue Q of vertices that are scheduled to be visited next so that it additionally contains all the sons of the vertex v in the tree T . We do so by a fixed rule, that may take into account the current state of Q and P, and need not respect the previous order of vertices in Q or the order of the offspring vertices of v.
4. We repeat the third step until the queue Q of scheduled vertices is empty.
If we order the vertices of the random tree T n according to an algorithm of this form, then the corresponding sequence of outdegrees satisfies Equation (6.1). This degree of freedom will be crucial in our analysis of extended fringe subtrees of T n in the condensation regime. A classical combinatorial result (see for example [13, Cor 15.4] 
, . . . , z n−1 ) = (y j mod n , y j+1 mod n , . . . , y j+n−1 mod n ) (6.2)
Thus there is a coupling of the simply generated tree T n with the balls-in-boxes model (Y 0 , . . . , Y n−1 ) such that the degree sequence (d 0 , . . . , d n−1 ) of T n is a random cyclic shift of (Y 0 , . . . , Y n−1 ).
Large nodes near the root in the condensation regime
Suppose that the weight-sequence w has type II or type III. Let ξ denote the offspring distribution defined in Section 3 and
LetD n be the random non-negative integer defined in Equation (5.3). Consider the random variableξ defined by
for k ∈ N, and P(ξ = ) = 1 − µ for some placeholder . Janson [13, Chapter 20] defined the following modified Galton-Watson treeT 1n . There are normal and special vertices, and we start with a special root. Each normal vertex receives offspring according to an independent copy of ξ, all its sons are also normal. For any special vertex we consider an independent copy ofξ. If it is a finite number, then we add accordingly many offspring and declare a uniformly at random selected son as special. If it assumes the placeholder value , then we add offspring according toD n , all of which are normal. Thus the treeT 1n comes with an almost surely finite spine whose tip v * satisfies P(hT
for all k ≥ 0. Janson [13, Theorem 20.2] showed that for any finite list of vertices v 1 , . . . , v ∈ V ∞ it holds that
as n becomes large. For each integer m ≥ 0 we let V [m] ⊂ V ∞ denote the vertex set of the tree obtained from U ∞ by truncating at height m and pruned so that all out-degrees are equal to m. That is, V [m] corresponds to all sequences of non-negative integers with length at most m such that each element of the sequences less than or equal to m. The topology on the space of locally finite plane trees is induced by the metric
}. The convergence (6.3) is equivalent to the existence of a coupling of the random trees T n andT 1n such that
(6.4)
Convergence in the type I regime
We present a proof of Theorem 5.2, in which we make use of properties that are characteristic of the type I regime, where extended fringe subtrees are typically small and random vertices have typically large height. Theorem 5.1, which states convergence of (T n , v 0 ) toward T * if w has type I, follows directly from a general observation, given in Lemma 6.1 below, that is valid for weight sequences having arbitrary type.
Proof of Theorem 5.2. Suppose that the weight sequence w has type I, and that the offspring distribution ξ has finite variance σ 2 . By assumption it holds that k n = n 1/2 t n for some sequence t n → 0. Without loss of generality, we may assume that k n → ∞.
For any k let E k,n denote the set of all pairs (T, x) of a plane tree T having at most nt n vertices and a vertex x having height h T (x) = k, such that P(H k (T n , v 0 ) = (T, x)) > 0. We are going to argue that as n ≡ 1 mod span(w) becomes large
This suffices, as i) and ii) imply that
and this expression converges to zero by iii). We start with property i). We have to show that H kn (T * , u 0 ) has with high probability at most nt n vertices. The size of H k (T * , u 0 ) is given by the sum of
= |T | and the independent differences
withξ the size-biased version of the offspring distribution ξ, and
a sum of independent copies (X j ) j of |T |. The reason for this is that
is given by the root-vertex u i , with the tree H i−1 (T * , u 0 ) and d
=ξ − 1 independent copies of T dangling from it. Compare with Figure 2 .
Hence
is stochastically bounded by the sum S M k+1 with
the sum of i independent copies ofξ for all i ≥ 1. (Here we have used thatξ ≥ 1 by definition.) By a general result for the size of Galton-Watson forests, there is a constant C > 0 such that We assumed that σ 2 < ∞, henceξ has a finite first moment. It follows that
Setting x = nt n and k = k n = n 1/2 t n , it follows by k n → ∞ and t n → 0 that
This verifies i). Property ii) is actually a consequence of properties i) and iii). Indeed, iii) implies that
and by i) it follows that
It remains to verify iii). Let (T, x) ∈ E kn,n . Given T n , there is a one to one correspondence between the vertices v ∈ T n with fringe subtree f (T n , v) = T , and the vertices v with H kn (T n , v ) = (T, x). Thus
The fringe subtree f (T * , u kn ) is distributed like the modified Galton-Watson tree, in which there are two types of vertices, normal and special, and we start with a special root. Normal vertices receive offspring according to an independent copy of ξ and all of those are normal again. Special vertices receive offspring according to an independent copy ofξ, and one of them is selected uniformly at random and declared its heir. If the heir has height less than k n , then it is declared special, and otherwise it becomes a normal vertex. Here the unique heir that is not special corresponds to the vertex u 0 . The probability for a special vertex to have offspring such that precisely the ith is selected as heir is given by
Combining Equations (6.6) and (6.7) yields
Remark 15.8, Equation (17.1) and subsequent equations in Janson's survey [13] yield that
with S denoting the sum of independent copies of ξ − 1. Since (T, x) ∈ E kn,n , the tree T has at most nt n vertices. Consequently, the local limit theorem for sums of lattice distributed random variables [10, Ch. 3.5] yields that uniformly for all (T, x) ∈ E kn,n as n ≡ 1 mod span(w) becomes large
This verifies iii) and hence completes the proof.
General observations
We state two observations that are valid for weight sequences having arbitrary type. The first describes the asymptotic probability to encounter small extended fringe subtrees.
Lemma 6.1. Let v 0 be a uniformly at random selected vertex of the simply generated plane tree T n . Let T • be a pointed plane tree whose pointed vertex has height h ≥ 0. Then the probability, that the pointed fringe subtree at the hth ancestor v h of the random vertex v 0 ∈ T n is equal to the pointed tree T
• , converges to the probability, that the pointed fringe subtree of T * at the spine vertex u h is equal ot T
• . That is, with T
Here we consider T * as pointed at the center u 0 . If we let V ⊂ V
• ∞ denote the subtree of the modified Ulam-Harris tree U • ∞ that corresponds to the pointed tree T
• , then this may be expressed by
Here f • (·, ·) denotes the pointed fringe subtree as defined in Section 5.4. The following result describes the asymptotic probability for extended fringe subtrees containing an ancestor with large degree. Lemma 6.2. Let v 0 be a uniformly at random selected vertex of the simply generated plane tree T n . Let T
• be a pointed plane tree whose pointed vertex has height h ≥ 0. For all integers 1 ≤ k ≤ h and all sufficiently large we may consider the event, that the outdegrees of the pointed fringe subtree of the hth ancestor of the random vertex v 0 ∈ T n all agree with the outdegrees of T
• , except for the kth ancestor of v 0 , which is required to have at least offspring to the left and at least offspring to the right of its unique son that is also an ancestor of v 0 . As n becomes large, this probability converges toward an expression that depends on . If we let tend to infinity, then this expression converges toward the probability, that the outdegrees of the fringe subtree of T * at the spine vertex u h agree with the outdegrees of T
• , except for u k , which must have outdegree (∞, ∞). In other words, u k is required to have an infinite number of offspring vertices to the left and to the right of u k−1 . Expressed in more formal words, let V ⊂ V
• ∞ denote the subtree of U • ∞ that corresponds to the tree T
• . Then the event E( , n) that
These results certainly deserve some explanation. If the weight sequence w has type I, then Lemma 6.1 immediately yields weak convergence of (T n , v 0 ) toward T * . This proves Theorem 5.1. Aldous [5] showed a similar form of convergence for the case where w has type I and the associated offspring distribution has finite variance, and Janson [13, Thm. 7 .12] established convergence of the fringe subtree at v 0 for arbitrary weights. The proof of Lemma 6.1 uses this result and various others from [13] .
In the type II and III setting, the situation is more complicated and Lemma 6.2 is not sufficient to deduce convergence in T
• for arbitrary weight-sequences. It is intuitive, that a random vertex is only likely to be close to the root, if one of its ancestors has large degree. Lemma 6.2 provides a description of what happens near a random root up to its first ancestor that has large degree. Beyond that, we only obtain information on what happens in the case that the ancestors of this ancestor have small degree. Since the space T
• is compact, the sequence (T n , v n ) clearly converges weakly toward a limit along a subsequence, and the distribution of this limit must agree by Lemma 6.2 with T * until the point where the spine of T * stops. However, at this location, we could encounter the root vertex of the limit, but just as well a second ancestor with large degree.
Proof of Lemma 6.1. Let v 0 , v 1 , . . . be the directed path from v 0 to the root of T n . Let T • = (T, v) be a pointed, finite plane tree and let h denote the height of the vertex v in T . Consider the event that v 0 has height at least h, and that the pointed fringe subtree f
• . Given T n , there is a one to one correspondence between the vertices v with fringe subtree f (T n , v) = T and the vertices v whose h-th ancestor u has pointed fringe subtree
Janson [13, Thm. 7.12] showed that
The probability for the size-biased random variableξ to assume a value , and that a uniformly at random choice out of options yields a specific value 0 , is equal to the probability that ξ equals . Thus
Combined with Equations (6.8) and (6.9) this yields that
This proves the first claim.
Proof of Lemma 6.2. Let T • = (T, v) denote a finite pointed plane tree, where the pointed vertex is not equal to its root. Let k 1 , k 2 be arbitrary non-negative integers whose sum is larger than the maximum degree of the tree T . This assumption will be crucial in the following argument.
Suppose that o is a vertex that lies on the path from the root to the pointed vertex of T
• , but is not equal to the pointed vertex. In order to not confuse the three vertices, let us call the root of T the inner root, the pointed vertex of T • the outer root, and the vertex o the middle root.
Let E k 1 ,k 2 (T • ) denote the set of pointed plane trees obtained by connecting the root vertices of k 1 arbitrary plane-trees from the left to the middle root o of T
• , and k 2 from the right. We are interested in the event that f
denote the corresponding set where we forget about which outer-root (the pointed vertex) we distinguished. Equation (6.8) yields
In order to study this asymptotic probability, we make use of a modified depth-first search of the tree. Traditional depth-first-search (DFS) lists the vertices of a plane tree by starting with the root, and traverses in each step along the left-most previously unvisited son. If no such son exists, we go to the parent of the current vertex and try again.
The process terminates with an ordered list of all vertices of the tree. Note that at any time the search maintains an ordered list of vertices that it already visited, and an ordered list Q of vertices that are scheduled to be visited next. Anytime we visit a new vertex that is not a leaf, vertices are added to the front of the queue Q of vertices that are to be visited next.
Let K be the sum of k 1 , k 2 and the outdegree d + T (o) of the middle root of T . We may modify the DFS by treating vertices with out-degree K in a special manner. When we encounter such a vertex, instead of putting all its offspring in front of the queue Q, we put the (k 1 + 1)th to (k 1 + d + T (o))th offspring to the front of the queue Q, and the remaining offspring to the back. Thus, if none of the fringe subtrees of the vertices we put to the front of the queue has a vertex with degree K, we traverse next along the (k 1 + 1)th son its entire fringe subtree, and so on, until the (k 1 + d + T (o)) son and its entire fringe subtree. After this we proceed with the remaining siblings of o.
As we assumed that K is larger than the maximum degree of T , this means that if we search a tree T from E k 1 ,k 2 (T ), the first |T | vertices in the resulting list of ordered vertices correspond to the vertices of T , and their outdegrees are equal to those in T , except for the vertex o, which has outdegree d
We now proceed similarly as in the proof of Janson's result [13, Thm. 7.12] where classical DFS was used. Let d 0 , . . . , d n−1 denote the list of outdegrees in the simply generated tree T n according to the modified DFS-order. For any i ≥ n we set d i = d i mod n . Letd 0 , . . . ,d denote the DFS-ordered list of outdegrees in T , and let i 0 denote the unique index that corresponds to the vertex o. Since K is larger than the maximal outdegree of T , the vertices v of T n with fringe-subtree in E k 1 ,k 2 (T ) correspond bijectively to the indices 0 ≤ i ≤ n − 1 with
This explicitly includes the case where i is so close to n − 1 such that i + > n − 1. It is not possible for a tree to have an ending segment in its list of vertices that is equal to an initial segment of (K,d 1 , . . . ,d ) , because then the search of the tree would have terminated with a non-empty queue Q of vertices that still need to be visited.
Consider the balls-in-boxes model (Y 0 , . . . , Y n−1 ) from Equation (6.1). We set Y i = Y i mod n for i ≥ n. For all 0 ≤ j ≤ n − 1 let I j be the indicator for the event
The sum n−1 j=0 I j is rotational invariant, hence it follows from Equation (6.2) that
For ease of notation, we define
By exchangeability, it follows that
Combining this with Equation (6.11) yields
it follows that (with the slight notational difference that Janson labelled the boxes from 1 to n rather than from 0 to n − 1), it follows that for r ≥ K
with c i denoting the number of 1 ≤ j < i withd j =d i . (Here we have used the fact that K (and hence also r) is larger thand 1 , . . . ,d .) Hence
where the implicit constant in the O term does not depend on n or r. It follows by Equation (6.13) that
It holds that j≥1 jN j = n − 1 and
By Janson's result [13, Thm. 11.4] it holds for each fixed j as n becomes large that
Thus, by dominated convergence, it follows that as n becomes large
Recall that the first moment of ξ is given by
Clearly it holds that
as K becomes large. As for a lower bound, we may write for every 0 < < 1
as K becomes large. As > 0 was arbitrary, it follows that
as K tends to infinity. Hence Equation (6.16) implies that for any sequences k 1 (r) and k 2 (r) with k 1 (r) + k 2 (r) → ∞ as r becomes large it holds that
this concludes the proof.
6.4
The limit theorems in the condensation regime 6.4 
.1 The type II regime
Proof of Lemma 5.4 . Suppose that the weight-sequence w has type II or III. We need to show that the following three statements are equivalent.
It is clear that the first claims implies the second, since the height
is a continuous functional on the space T • . The height h T * (u 0 ) of the pointed vertex in T * is distributed like 1 plus the sum of two independent identically geometric random variables with parameter µ. Thus the second claim implies the third. The convergence in Lemma 6.2 immediately yields that for all t ≥ 1 lim inf
Hence the third claim implies the second. It remains to verify that the second claim implies the first. Suppose that
Since the space T • is compact, any sequence of random pointed plane trees has a convergent subsequence. In particular, the sequence (T n , v 0 ) converges toward a limit objectT along a subsequence (n k ) k . We are going to show that
regardless of the subsequence. By standard methods [7, Thm. 2.2] this implies
By Equation (6.17) it holds that
Lemma 6.1 yields that for any finite tree
By Lemma 6.2 we know furthermore that for any index 1 ≤ i ≤ k it holds that
with V ⊂ V • ∞ denoting the subset corresponding to the vertices of T
• . We are going to show that Equations (6.19), (6.20) and (6.21) are sufficient to verify thatT d = T * . The first step is to verify that
as random elements of the product space
For this, it is sufficient to verify that for all k ≥ 1
To this end, let
be given, such that there exists an index 0 ≤ j ≤ k such that for all i > j it holds that d i = * . We are going to show that
This suffices, as the set of indices i with d + T * (u i ) = * must form a tail-segment of (1, . . . , k), since T * is a tree, and likewise forT . Moreover, Equation (6.19) implies that almost surely
Hence we may additionally assume that j ≥ 1.
First, let us observe that
Indeed, the left-hand side is equal to zero unless d i ∈ N 0 × N 0 for all 1 ≤ i ≤ j with the exception of at most one index i 0 for which we allow that
If the d i satisfy this property, we may argue as follows. We constructed the tree T * in a way such that for all vertices v ∈ V Thus Inequality (6.24) holds. If we sum over all d 1 , . . . , d j ∈ N 0 × N 0 , then the left-hand side of (6.24) sums up to P(h T * (u 0 ) ≥ j), and the right-hand side to P(hT (u 0 ) ≥ j). But these two quantities are equal by Equation (6.19 ). Thus it follows that already
) is identical to Equation (6.23). Otherwise, if 1 ≤ j < k, then Equation (6.25) implies that
Of course, the same holds if we replace T * byT . It follows by Equation (6.25) , that the last expression is equal for T * andT . This verifies Equation (6.23), and hence also Equation (6.22) .
In order to verify that T * d
=T , we may proceed in a similar manner. Letting d 1 , . . . , d k and 1 ≤ j ≤ k be as before, Equations (6.20), (6.21) and (6.22) imply that 
may assume. By Equation (6.20) and (6.22), the tree
assumes each with the same probability as T 1 , so it follows that the tree T 2 is also supported on a countable set and
As for the other case, suppose that d i 0 = (∞, ∞) for a unique index 1 ≤ i 0 ≤ j. For each ≥ 0 we may look at the canonically ordered finite list L (T 1 ) of fringe subtrees at the sons v = u 1 , . . . , u j−1 of the u i for i = i 0 and at the first siblings to the left and to the right of u j−1 . Again there are only countably many outcomes for L (T 1 ), as each of these fringe trees must be finite. By Equations (6.21) and (6.22) , the list L (T 2 ) assumes each with the same probability. Hence L (T 2 ) is also supported on a countable set and 
In order to deduce that T * d
=T , we need to show that any Borel-measurable set E ⊂ T
• and any h ≥ 1 it holds that
Clearly it suffices to show this when E contains only trees T ∈ T • with h T (u 0 ) = h. In this case, it follows by Equation (6.27) that
This verifies Equation (6.28) and hence completes the proof.
Proof of Theorem 5.3. Suppose that the weight sequence w has type II and that the maximum degree ∆(T n ) has order 
LetD n denote the random integer defined in Equation (5.3) bỹ
for any fixed deterministic sequence Ω n that tends to infinity slowly enough such that Equation (5.1) holds. Here o ∈ T n denotes the root-vertex of the tree T n . LetT 1n denote the modified Galton-Watson tree constructed in Subsection 6.1.2. Janson [13, Equation (20.2) ] argued that it follows from the assumption (6.29) that
By Equations (5.1), (6.1) and (6.2) it holds that
as n becomes large. In particular there is a sequence δ n → 0 such that
with high probability. For any plane tree T let (F (T ), v(T )) denote the pointed plane tree obtained by marking the first vertex with outdegree larger than Ω n in the depth-first-search ordered list of vertices of T and cutting away all its descendants. The convergence in (6.4) implies that
Note that the distribution of (F (T 1n ), v(T 1n )) does not depend on n and that
) the the ordered list of fringe subtrees dangling from the vertex v(T n ) in T n are conditionally distributed like a simply generated forest with d + Tn (v(T n )) trees and n − |F (T n )| of vertices. That is, if (F (T n ), v(T n )) is equal to some finite pointed plane tree F and d + Tn (v(T n )) = for some integer ∈ (1 − µ ± δ n )n then the list is distributed like the forest
with (T i ) i≥1 denoting independent copies of the ξ-Galton-Watson tree T . Let (ξ i ) i≥1 denote independent copies of the offspring distribution ξ. It follows from [ 
uniformly for all ∈ (1 − µ ± δ n )n. For each k ≥ 0, let
denote the map that sends a tree to its width at height k. By the Azuma-Hoeffding inequality it follows that for any integer r ≥ 1 and any > 0 there are constants C, c > 0 such that 
By Equation (6.15), it follows that
By Equation (5.1) we know that
Janson's result [13, Thm. 11.4] implies that for each fixed j
and hence for each fixed K
Consequently,
By dominated convergence, it follows that
Let V ⊂ V
• ∞ denote the subset corresponding to the vertices of the tree T • . Recall that the pointed vertex in T
• has height k. It holds that
It readily follows that
Before proceeding with the proof of the main results, we make the following observation.
Lemma 6.3. It holds thatD n ≤ (1 − ν + o(1))n with probability tending to 1 as n becomes large.
Proof. By Equation (5.3) we have that
and [13, Lem. 19 .32] states that Proof of Theorem 5.7. Let > 0 be given, and m ≥ 1 be arbitrarily large but fixed. The height of the pointed vertex inT * n is stochastically bounded. Hence if M 1 ≥ 1 is large enough, the probability for this height to be larger than M 1 is less than for all n.
The total size of the tree obtained by pruningT * n at its vertex with large degree, such that at most m trees to the left and right of its spine offspring remain, is also stochastically bounded. Hence if M 2 ≥ 1 is large enough the probability for this size to be larger than M 2 is at most for all n.
By Lemma 6.3, we know that there is a sequence t n = o(1) such that the probability for the root-degree ofT * n to be larger than (1 − ν + t n )n tends to zero as n becomes large. By modifying t n for finitely many n we may also assume that additionally this probability is less than for all n.
Let x 1 , . . . , x r ∈ V
• ∞ be given vertices, and let M 3 denote the distance from the center u 0 to the youngest common ancestor of x 1 , . . . , x r .
Let M > M 1 , M 2 , M 3 be a fixed constant. Let V ⊂ V
• ∞ correspond to the vertex set of a pointed tree (T, x) with at most M vertices such that 1 ≤ h T (x) ≤ M and the root o has at most m offspring vertices to the left and to the right of its unique son that lies on the spine.
We are going to show that sup (k 1 ,k 2 ) Ωn≤k 1 +k 2 ≤(1−ν+tn)n P(d
(6.40)
Note that the nominator and denominator are either both non-zero or both zero, and we will tacitly only consider the case where this expression is well-defined. In particular, this entails considering only trees T such that
for all vertex v ∈ V (T ) \ {o}. There are only finitely many choices for T and V . Hence the limit (6.40) implies that
for large enough n. As > 0 was arbitrary, this suffices to prove the claim. It remains to verify the limit in (6.40). We may assume that n is large enough such that Ω n > M . By Equation (6.37), we may order the outdegrees of T by By the construction ofT * n it holds that
.
By Equation (5.3) and K ≥ Ω n it holds that
For any integer k ≥ 0 it holds by the discussion in Section (6.1.1) and in particular Equation (6.2) that
See also [13, Lemma 15.7] . Hence
It follows by Equation ( 
with the implicit bound in the O(n −1 ) term not depending on K. Recall that in Section 3.1 we defined φ(z) = k≥0 ω k z k , ψ(z) = zφ (z)/φ(z), and a parameter τ . As the weight sequence (ω i ) i has type II or III, it holds that τ = ρ φ is the radius of convergence of φ(z). In Section 3.2 we defined furthermore P(ξ = k) = ω k τ k /φ(τ ) for all k. Janson [13, Theorem 11.6] is continuous. For x ≤ ν = µ it holds that τ (x) is the unique number with ψ(τ (x)) = x, and for x > ν it holds that τ (x) = ρ φ = τ . Furthermore, for each fixed non-negative integer d it holds uniformly for all m ≤ n that
We assumed that K ≤ (1 − µ + t n )n with t n = o(1). In particular, uniformly for all K. This verifies Equation (6.41) and hence completes the proof.

{'paper_id': '24464105', 'title': 'Local limits of large Galton-Watson trees rerooted at a random vertex', 's2_url': 'https://api.semanticscholar.org/CorpusID:24464105', 'source': 'S2ORC'}