{'fraction_non_alphanumeric': 0.07823755531866783, 'fraction_numerical': 0.021384501082146203, 'mean_word_length': 3.3316076675528192, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Short cycles in high genus unicellular maps

We study large uniform random maps with one face whose genus grows linearly with the number of edges, which are a model of discrete hyperbolic geometry. In previous works, several hyperbolic geometric features have been investigated. In the present work, we study the number of short cycles in a uniform unicellular map of high genus, and we show that it converges to a Poisson distribution. As a corollary, we obtain the law of the systole of uniform unicellular maps in high genus. We also obtain the asymptotic distribution of the vertex degrees in such a map.


Introduction
Combinatorial maps. Maps are defined as gluings of polygons forming a (compact, connected, oriented) surface. They have been studied extensively in the last decades, especially in the case of planar maps, i.e. maps of the sphere. They were first approached from the combinatorial point of view, both enumeratively, starting with [24], and bijectively, starting with [23].
More recently, relying on previous combinatorial results, the properties of large random maps have been studied. More precisely, one can study the geometry of random maps picked uniformly in certain classes, as their size tend to infinity. In the case of planar maps, this culminated in the identification of two types of "limits" (for two well defined topologies on the set of planar maps): the local limit (the UIPT 1 [2]) and the scaling limit (the Brownian map [16; 19]).
All these works have been extended to maps with a fixed genus g > 0. Enumerative (asymptotic) results have been obtained (see for instance [3]), and there are bijections for maps on any surface (see for instance [8]). On the probabilistic side, equivalents of the Brownian map in genus g > 0 have been constructed [4].
High genus maps. Very recently, another regime has been studied: high genus maps are defined as (sequences of) maps whose genus grow linearly in the size of the map. They have a negative average discrete curvature, and can therefore be considered as a discrete model of hyperbolic geometry. It is usually hard to get geometric results on general models of maps (such as triangulations). So far, only the local convergence has been established [5; 6], along with a few other geometric features [17].
However, there is a model that is easier to work with: unicellular maps, i.e. maps with only one face. They are in bijection with decorated trees [7], which makes them easier to study. Although they belong to a different universality class, it is widely expected that unicellular maps in high genus actually share very similar features with more general models of maps. So far, the local limit [1], the diameter [22] and the presence of large expander subgraphs [18] of unicellular maps have been discovered (the last two properties are still open questions for general models of maps).
Distribution of short cycles. In this paper, we are interested in another geometric observable: the systole, i.e. the size of the smallest noncontractible cycles. The question of the systole is a well studied question in the field of geometry of surfaces (see for instance [11; 20; 21] and in particular [9] in the case of deterministic maps).
We will work with unicellular maps, in which we have the extra advantage that any cycle is non-contractible; hence the systole equals the girth (the length of the smallest cycle) of the underlying graph. A little bit of progress on the question of short non-contractible cycles in general maps is made in [17].
We actually prove a more general theorem, namely that the number of short cycles in a high genus unicellular map follows a Poisson law. For definitions, see Section 2; note that the unicellular maps are rooted at an oriented edge, and that we define the size of a map as its number of edges. Theorem 1.1. Take a sequence (g n ) such that gn n → θ ∈ (0, 1/2) as n → ∞. Let C (k) n,gn be the number of cycles of length k in a uniformly random unicellular map of size n and genus g n . Then, for all M , we have (C (1) n,gn , C (2) n,gn , . . . , C (M ) n,gn )

2)
where τ ∈ (0, 1) is the (unique) root of The parameter τ here is the same as β in [1]. It is easily seen that τ increases from 0 to 1 as θ increases from 0 to 1/2. This theorem is an analogue of the result of [21] for the Weil-Petersson measure (a classical continuous model of random hyperbolic geometry) as the genus tends to infinity. As an immediate corollary, we obtain the law of the systole of high genus unicellular maps: Corollary 1.2. Let syst(n, g n ) be the systole of a uniformly random unicellular map of size n and genus g n . Then, as n → ∞ with g n /n → θ ∈ (0, 1/2), where Z is a random variable with, letting the λ i be as in (1.2), It follows from (1.2) that λ = ∞, and thus the probabilities in (1.5) add up to 1. Therefore Z is a proper distribution, and, in particular, syst(n, g n ) is bounded in probability.
Vertex degrees. The methods we use also allow us to control the vertex degrees in the map: n,gn be the number of vertices of degree k ≥ 1 in a uniformly random unicellular map of size n and genus g n , and let m := n + 1 − 2g n be the total number of vertices. Then, as n → ∞, where (χ k ) ∞ 1 is a probability distribution given by with τ given by (1.3).
Remark 1.4. Theorem 1.3 is related to [1,Theorem 4], which gives the asymptotic distribution of the root degree of the map. To see the connection, note first that as a corollary of Theorem 1.3, the degree of a uniformly random vertex in the random unicellular map converges in distribution to the distribution (χ k ) given by (1.7). Since the number of edges and vertices in the map are deterministic, this means that if we consider a uniformly random unicellular map of size and genus as above, but rooted at a vertex instead of at an oriented edge, then the root degree distribution converges to (χ k ). It follows easily that for random unicellular maps rooted at an oriented edge, as in [1] and the present paper, the root degree distribution converges to the size biased distribution (ckχ k ), where c is a normalization factor (easily computed); this is [1,Theorem 4].
Structure of the paper. We end this section with a list of the main notations appearing in this paper. In section 2, we give definitions. Section 3 states previous results on paths in trees that we use, and Section 4 is devoted to results about cycles in C-permutations. In Section 5, we prove Theorem 1.1 and finally Section 6 contains the proof of Theorem 1.3.
Index of notations. This paper is quite notation heavy; we list here the main notations that appear throughout the paper.
• g n , θ: parameters of our model, (g n ) n ≥ 1 is the sequence of genuses of the unicellular maps we consider, with gn n → θ ∈ (0, 1/2); • τ, (λ ) ≥1 : parameters uniquely determined by θ (in (1.3) and (1.2)); • T n : the set of plane trees on n edges; • T: a random uniform element in T n (depends implicitly on n); • S C n,m : the set of C-permutations on n elements and m cycles; • σ: a random uniform element in S C n+1,n+1−2gn (depends implicitly on n); • T : denotes a fixed rooted tree; • t: denotes a fixed unrooted tree; • P (T ): number of paths of length in T ; • N t (T ): number of occurrences of t in T ; • (T n ) n≥1 : denotes a deterministic sequence of trees such that T n ∈ T n ; • C (k) n,gn : the number of cycles of length k in a uniformly random unicellular map of size n and genus g n (alternatively, in the underlying graph of (T, σ)); • Ext: will be used to denote the extremities of a path (or of a list of paths); • P: denotes a list of pairwise disjoint paths; • s(P): number of paths in P; • (P): total length of the paths of P; • m: denotes the list of lengths of a list of paths.

Definitions
A unicellular map of size n is a 2n-gon whose sides were glued two by two to form a (compact, connected, oriented) surface. The genus of the map is the genus of the surface created by the gluings (its number of handles). After the gluing, the sides of the polygon become the edges of the map, and the vertices of the polygon become the vertices of the map. Note that the number of edges equals the size n. By Euler's formula, a unicellular map of genus g and size n has n + 1 − 2g vertices. The underlying graph of a unicellular map is the graph obtained from this map by only remembering its edges and vertices. (In general, this is a multigraph.) We consider in this paper only rooted unicellular maps, where an oriented edge is marked as the root. The underlying graph is then a rooted graph.
A rooted unicellular map of genus 0 is the same as a plane tree (i.e., an ordered rooted tree). We denote by T n the set of plane trees of size n (and thus n + 1 vertices).
A path P of length ≥ 0 in a (multi)graph is a list (v 0 , e 1 , v 1 , e 2 , . . . , e , v ) of alternating distinct 2 vertices and edges such that for all 1 ≤ i ≤ , v i−1 and v i are joined by the edge e i . We define start(P) := v 0 and end(P) := v , and let Ext(P) := {start(P), end(P)}. Similarly, a cycle of length ≥ 1 is a list (v 0 , e 1 , v 1 , e 2 , . . . , e ) of distinct vertices and edges such that (v 0 , e 1 , v 1 , e 2 , . . . , v −1 ) is a path and e is an edge joining v −1 to v 0 . In a simple graph (for example, a tree), the edges e i in a path or cycle are determined by the vertices, so it suffices to specify (v 0 , v 1 , . . . ). We denote the length of a path p by |p|; this is thus the number of edges in p.
A C-permutation is a permutation whose cycles are of odd length. Let S C n be the set of C-permutations of length n, and S C n,m the subset of permutations in S C n with exactly m cycles. (This is empty unless n ≡ m (mod 2); we assume tacitly in the sequel that we only consider cases with S C n,m = ∅.) Note that our definition of a C-permutation differs from the one given in [7], where each cycle carries an additional sign. Here we do not include the signs as they will not play a role in our proofs.
A C-decorated tree of size n and genus g is a pair (T, σ) ∈ T n ×S C where σ is seen as a C-permutation of the vertices of T . The underlying 2 with this definition, such objects are also commonly called simple paths.
graph of (T, σ) is the graph obtained by merging the vertices of T that belong to the same cycle in σ. If v, v ∈ T , we write v ∼ v if v and v belong to the same cycle in σ. Theorem 5). Unicellular maps of size n and genus g are in 2 2g to 1 correspondence with C-decorated trees of size n and genus g. This correspondence preserves the underlying graph.
Therefore, with this correspondence, it is sufficient to study C-decorated trees.
More precisely, from now on, we fix a number θ ∈ (0, 1/2) and a sequence (g n ) n≥1 such that gn n → θ. Now, we define (for each n, with n only implicit in the notation) T to be a uniformly random tree in T n , and σ to be a uniformly random Cpermutation in S C n+1,n+1−2gn , with T and σ independent. From now on, thanks to Theorem 2.1, we can assume that C (k) n,gn is the number of cycles of size k in the underlying graph of (T, σ).

Further notation. The multivariate Poisson distribution Po
(n) r denotes the descending factorial n(n − 1) · · · (n − r + 1). C and c denote unspecified constants that may vary from one occurrence to the next. C r denotes a constant depending on r.
Unspecified limits are as n → ∞.

Paths in trees
The following lemma helps us estimate the number of paths of a certain length in the random tree T. In general, for a rooted tree T , we let P (T ) be the number of paths of length in T .
, Example 4.3, (4.9)). Let, as above, T be a uniformly random tree in T n . Then, as n → ∞, for every fixed ≥ 1, To estimate the numbers of intersecting paths, we will also use the following, more general, result. (We count paths as oriented, but general subtrees t as unlabelled.) 14]). Let, as above, T be a uniformly random tree in T n . Let t be a fixed unrooted tree, and let N t (T) be the number of subtrees of T isomorphic to t. Then, as n → ∞,

Cycles in C-permutations
Let σ n,m be a uniformly random element of S C n,m , and let N k;n.m be its number of cycles of length k. Thus N k;n.m = 0 unless k ≥ 1 is odd. Note also that k N k;n.m = m, k kN k;n.m = n. (4.1) where (π k ) is a probability distribution supported on {1, 3, 5, . . . } given by and Φ(τ ) is a normalizing constant given by (4.12) below. Furthermore, for any with convergence of all moments. Finally, there exists a constant C α such that, if we define the event E := {The largest cycle of σ n,m is shorter than C α log 2 n} (4.6) Proof. Let L 1 , . . . , L m be the lengths of the cycles of σ n,m , taken in (uniformly) random order. Note that We say that a permutation with m cycles has labeled cycles if we have labeled its cycles by 1, . . . , m.
For any positive integers 1 , . . . , m with i i = n, the number of permutations of length n with m labelled cycles with lengths 1 , . . . , m , respectively, is (4.9) Consequently, where Z = Z(n, m) is a normalization factor. This means that (L 1 , . . . , L m ) is an instance of a well-known random allocation model, called balls-in-boxes in [13,Section 11], with weights (Warning: n and m have opposite meanings in [13].) In the notation of [13, (3.4)], we have the generating function and, see [13, (3 We apply [13,Theorem 11.4] with λ = 1/α > 1; this theorem is stated assuming w 0 > 0, but we may apply the theorem to the random allocation and it is easily seen that the conclusions of [13, Theorem 11.4] hold for any λ ≥ 1. This yields (4.2); note that (4.4) is equivalent to Ψ(τ ) = 1/α = λ.
To show (4.5), we first show that the expectations are bounded: for every r ≥ 0, In fact, we will show the stronger estimate that if 1 < A < τ −1 , then To see (4.19), we use arguments similar to those in [13,Section 14]. Note that, by symmetry, Let τ n,m be given by Ψ(τ n,m ) = n/m. Since n/m → λ, it follows that τ n,m → τ < A −1 . Thus, τ n,m < A −1 when n and m are large enough; consider only such n (and m).
Given such n and m, let ξ ( Consequently, (4.19) follows by (4.20) and (4.23), and then (4.18) follows. Next, we have for any K < ∞, Given any ε > 0, we can by (4.19) and (4.3) choose K so large that the two last sums each are less than ε for all large n; furthermore, each term in the first sum is o(1) by (4.2) and bounded convergence. It follows that the left-hand side of (4.24) is o(1), and thus (4.5) holds. Finally, for any p ≥ 1, by Hölder's inequality, k N k;n.m /m = 1 and (4.18), To prove (4.6), notice that for C α large enough, we have by (4.23), and we conclude by a union bound, since the number of cycles is m ≤ n.
Let M := M n,m be the number of (unordered) pairs of elements of [n] that belong to the same cycle in σ n,m , and thus are merged together when cycles are merged. Then Using the crude bound k 2 ≥ k − 1 and (4.1), we obtain the following deterministic bound: M n,m ≥ n − m.
(4.28) The following lemma gives a better estimation of M n,m . . Equivalently, Proof. The convergence in probability and with all moments follows by (4.27) and (4.5). To compute the sum, note that if ξ is a random variable with distribution (π k ) k , then its probability generating function is , (4.32) and the result follows using (4.4).
The results above hold in full generality, but here we go back to our setting. We recall that gn n → θ and we set α = 1 − 2θ (and therefore the constant γ now depends on θ); thus m/n = (n + 1 − 2g n )/n → α. In what follows, we will reason conditionally on E. We let ∆ be the size of the biggest cycle in σ. Thus, by the definition (4.6), E is the event ∆ ≤ C α log 2 n. The number of r-tuples of (unordered, non overlapping) pairs of elements of [n + 1] that belong to the same cycle in σ is at most (M n+1,n+1−2gn ) r (because this quantity counts r-tuples with possible overlaps). On the other hand, we can lower bound the number of r-tuples of pairs of elements of [n + 1] belonging to r distinct cycles by (4.36) By (4.28) and (4.35), we have The total number of r-tuples of (non-overlapping) pairs of elements of [n] is n 2,2,...,2,n−2r . Therefore, (4.38) Finally, using (4.34) and the convergence in probability established in (4.30), we can conclude that n,gn be the probability that, in σ, there exist r +k distinct cycles C 1 , C 2 , . . . , C r ,C 1 ,C 2 , . . . ,C k such that 2i − 1 and 2i belong C i for all 1 ≤ i ≤ r, and 2r + i belongs toC i for all 1 ≤ i ≤ k . Then, for every fixed r and k, P (r,k) n,gn = (1 − o(1)) P (r) n,gn . Condition also on the fact that there exists r distinct cycles C 1 , C 2 , . . . , C r of σ such that 2i − 1 and 2i belong to C i for all 1 ≤ i ≤ r (which amounts to conditioning on E (r) n,gn ). We want to show that the rest of the constraint holds with high probability. Note that the numbers 2r + 1 ≤ i ≤ 2r + k are distributed uniformly in the cycles of σ among all remaining spots. Therefore, given 2r + 1 ≤ j ≤ 2r + k, the probability that j belongs to a given C i is less than ∆ n+1−2r−k . By the same reasoning, given 2r + 1 ≤ i < j ≤ 2r + k, the probability that i and j belong to the same cycle is also bounded by ∆ n+1−2r−k . By a union bound, the conditional probability of failure is bounded by which is o(1) by (4.41).
Lemma 4.5. For fixed k and t < k, the probability that 1, 2, . . . , k belong to exactly t distinct cycles of σ is

43)
Proof. Let ∆ be the maximal size of a cycle in σ. By the same reasoning as in the proof of Lemma 4.3, we can work conditionally on ∆ and assume ∆ ≤ C α log 2 n. (4.44) Let us call succ the event that 1, 2, . . . , k belong to exactly t distinct cycles of σ. We will prove a stronger result, namely that, conditioned on ∆, (4.45) and we conclude using (4.44).
Let disj be the event that 1, 2, . . . , t belong to exactly t distinct cycles of σ.
By a union bound and symmetry, we have Now, conditioning also on disj, the elements t + 1, . . . , k are placed uniformly in the remaining spots of σ. The total size of the cycles containing 1, 2, . . . , t is less than t∆; hence, (4.47) Combining (4.46) and (4.47) yields (4.45) and thus (4.43).

Cycles in C-decorated trees
If (T, σ) is a C-decorated tree, then any simple cycle of length in its underlying graph can be decomposed into a list P = (p 1 , p 2 , . . . , p k ) of nonintersecting simple paths in T such that (C1) k i=1 |p i | = , (C2) end(p i ) ∼ start(p (i+1 mod k) ) for all i, (C3) for every other pair of vertices v, v ∈ (p 1 , p 2 , . . . , p k ), we have v ∼ v . This decomposition is unique up to cyclically reordering the p i , or reversing them all and their order, or a combination of both.
For two lists P, P ∈ P(T ), we write P ≡ P if and only if P can be obtained from P by cyclically reordering its paths, or reversing them all and their order, or a combination of both. Note that P ≡ P entails s(P) = s(P ) and (P) = (P ), and that each list P is in an equivalence class [P] with exactly 2s(P) elements. Let P ( ) (T ) be a subset of P ( ) (T ) obtained by selecting exactly one element from each equivalence class in P ( ) (T ).
Given also a C-permutation σ of the vertex set of T , so that (T, σ) is a C-decorated tree, let C ( ) (T, σ) be the set of lists P = (p 1 , . . . , p k ) ∈ P ( ) (T ) that satisfy (C1)-(C3) above. Thus, there is a bijection between C ( ) (T, σ) and the set of cycles of length in the underlying graph of the C-decorated tree (T, σ). Hence, C ( ) (T n , σ) := |C ( ) (T n , σ)| equals the number of cycles of length in the underlying graph.
As in Section 3, let P (T ) be the number of paths of length in T . Similarly, if t is an unrooted tree, let N t (T ) be the number of subtrees of T that are isomorphic to t.

5.2.
Lemmas and proof of Theorem 1.1. We are really interested in random trees T, but it will be convenient to first consider non-random trees. We suppose for the following lemmas that (T n ) is a given sequence of (deterministic) rooted trees, with T n ∈ T n . We say that the sequence is good, if, as n → ∞, and, for every finite unrooted tree t, there is a constant c t ≥ 0 such that N t (T n )/n → c t .
Proof. An element of P [m] is a sequence of disjoint paths p 1 , . . . , p k in T n , with |p i | = m i . Thus, if we ignore the condition that the paths be disjoint, each p i may be chosen in P m i (T n ) ways, which gives k 1 P m i (T n ) sequences. We have to subtract the number of sequences with two intersecting paths p i and p j . It suffices to consider the case when p 1 and p 2 intersect. Then their union is a subtree t of T n with at most m 1 + m 2 + 1 vertices. Regard t as an unlabelled treet. There is only a finite number of possible sucht, and for each choice, the condition (5.5) shows that the number of possible subtrees t in T n is O(n). Moreover, for each t, the paths p 1 and p 2 are subsets of t and can thus be chosen in O(1) ways. The remaining paths p 3 , . . . , p k can, as above, each be chosen in O(n) ways. Consequently, the number of sequences of paths (p 1 , . . . , p k ) such that |p i | = m i and two of the paths intersect is O n k−1 . It follows that, using (5.4) and (5.3), which proves (5.6) In the remainder of this section, σ = σ n is a uniformly random Cpermutation in S C n+1,n+1−2gn . We begin by calculating the expectation of C ( ) (T n , σ).
Lemma 5.2. Let (T n ) be a good sequence of trees. Then, for every ≥ 1, as n → ∞, given by (1.2). Furthermore, Proof. We begin with the simpler C ( ) (T n , σ) = | C ( ) (T n , σ)|. For each given list P = (p 1 , . . . , p k ) ∈ P ( ) (T n ), letπ(P) be the probability that P ∈ C ( ) (T n , σ), in other words, the probability that (C2) holds. Then, by definitions and symmetry, To findπ(P), we may relabel the 2k endpoints in Ext(P) as 1, . . . , 2k in an order such that (C2) becomes 2i − 1 ∼ 2i for i = 1, . . . , k, i.e., that 2i − 1 and i belong to the same cycle in σ. There are two cases: either these k cycles are distinct, or at least two of them coincide. The first event is E (k) n,gn in Lemma 4.3, and that lemma shows that its probability is The second event means that 1, . . . , 2k belong to at most k − 1 different cycles of σ. Hence, Lemma 4.5 shows that the probability of this event is Summing (5.11) and (5.12), we see that where k = s(P).
We next extend Lemma 5.2 and show convergence also in distribution.
Idea of the proof: This proof is a bit long and technical, but the general idea is quite classical. We will use the method of moments (by considering factorial moments), and roughly speaking, the proof amounts to showing that given a finite number of cycles taken uniformly conditionally on being pairwise distinct, they are pairwise disjoint with high probability. Then, calculating the value of the desired expectations will be straightforward from the results we obtained beforehand. In order to show that our uniform cycles are pairwise disjoint, we will again use their decomposition into lists of paths, and, thanks to Lemmas 5.1 and 5.2, we will only have to consider possible intersections at the endpoints of the paths.
We use the method of moments, so we want to estimate the factorial moment E q i=1 C ( i ) (T n ) r i for any given positive integers q, 1 < · · · < q and r 1 , . . . , r q . We argue similarly as in the special case q = 1 and r 1 = 1 in Lemma 5.2, and write this expectation as where we sum over all sequences of distinct lists (P(i, j)) 1≤i≤q, 1≤j≤r i such that P(i, j) ∈ P ( i ) (T n ), and π((P(i, j)) ij ) is the probability that every P(i, j) ∈ C ( i ) (T n ). Recalling the definition of P ( ) , we can rewrite (5.29) as i,j 2s(P(i, j)) , (5.30) where we now sum over all sequences of lists (P(i, j)) ij such that P(i, j) ∈ P ( i ) (T n ) and no two P(i, j) are equivalent (for ≡).
First, we show that the Ext(P(i, j)) are pairwise disjoint whp. For each such sequence (P(i, j)) ij , define a graph H with vertex set V (H) := i,j Ext(P(i, j)), the set of endpoints of all participating paths, and edges of two colours as follows: For each list P(i, j) = (p ν ) k 1 , add for each ν a green edge between start(p ν ) and end(p ν ), and a red edge between end(p ν ) and start(p ν+1 ) (see Figure 1 for an example). (We use here and below the convention p k+1 := p 1 .) Hence, by the definitions above, every P(i, j) ∈ C ( i ) (T n ) if and only if each red edge in H joins two vertices in the same cycle of σ. Thus, π((P(i, j)) ij ) in (5.30) is the probability of this event.
For each graph H constructed in this way, let H G be the subgraph consisting of all green edges, and say that a connected component of H G is a green component of H. Define a red component in the same way, and let ζ G (H) and ζ R (H) be the numbers of green and red components, respectively.
Let M H = M H (n) be the number of terms in (5.30) with a given graph H. (For some fixed q, 1 , . . . , q and r 1 , . . . , r q .) We estimate M H as follows. Each green component of H corresponds to some paths p i,j,ν such that their union is a connected subtree t of T n . All these paths have lengths bounded by max i i , so the union t has bounded size. Thus, regarding t as an unlabelled treet, there is only a finite set of possible choices oft. Hence, the assumption This implies that all green or red components have size 2, and thus are isolated edges. It follows that if two different lists P(i 1 , j 1 ) and P(i 2 , j 2 ) contain two paths p i 1 ,j 1 ,ν 1 and p i 2 ,j 2 ,ν 2 that have a common endpoint, then these paths have to coincide (up to orientation). Furthermore, if they coincide, and have, say, the same orientation so end(p i 1 ,j 1 ,ν 1 ) = end(p i 2 ,j 2 ,ν 2 ), then the red edges from that vertex have to coincide, so start(p i 1 ,j 1 ,ν 1 +1 ) = start(p i 2 ,j 2 ,ν 2 +1 ). It follows easily that the two lists P(i 1 , j 1 ) and P(i 2 , j 2 ) are equivalent in the sense P(i 1 , j 1 ) ≡ P(i 2 , j 2 ) defined above. However, we have excluded this possibility, and this contradiction shows that all paths p i,j,ν in the lists have disjoint sets of endpoints Ext(p i,j,ν ).
Consider now this case, and assume, moreover, that for all i and j, we have s(P(i, j)) = k(i, j) and P(i, j) ∈ P [m(i,j)] for some given k(i, j) and m(i, j) = (m i,j,1 , . . . , m i,j,k(i,j) ) such that |m(i, j)| = i . Then we can write P(i, j) = (p i,j,1 , . . . , p i,j,k(i,j) ), where all paths p i,j,ν have disjoint endpoints and |p i,j,ν | = m i,j,ν . It follows as in the proof of Lemma 5.1 that the number of such sequences of lists (P(i, j)) ij is, with K := i,j k(i, j), the total number of paths in the lists, and using (5. Hence, π (P(i, j)) ij is the probability that K given pairs of vertices in T n belong to the same cycles in σ. As in the proof of Lemma 5.2, it follows from Lemmas 4.3 and 4.5 that, using (5.17), This proves the desired convergence of the factorial moments, and the method of moments yields the result. (For C ( ) (T n , σ), which is enough as said at the beginning of the proof.) To prove the main theorem, it remains only to replace the deterministic trees T n in Lemma 5.3 by the random T.
Proof of Theorem 1.1. Recall that, for each n, T = T n is a uniformly random tree in T n . By Lemmas 3.1 and 3.2, (5.4) and (5.5) hold in probability if we take T n as the random tree T. We can regard this as convergence in probability of infinite sequences indexed by the countable set { } ∪ {t}, i.e., convergence in R ∞ . By the Skorohod coupling theorem [15,Theorem 4.30], we may assume that this convergence actually holds almost surely, i.e., that (5.4) and (5.5) hold a.s. for every and t. In other words, we may assume that the random trees T n for different n are coupled such that the sequence (T n ) is good a.s.
We now condition on the sequence (T n ). We have just seen that Lemma 5.3 applies a.s., and thus (1.1) holds for the conditional distributions, i.e.

Vertex degrees
In this section, we prove Theorem 1.3. Again, we may by Theorem 2.1 consider the underlying graph of (T, σ). It is convenient to first consider deterministic trees and permutations, with only the relative position of them random. Lemma 6.1. Let (g n ) be a sequence with n − 2g n → ∞ as n → ∞. Let (T n , σ n ) be a given (deterministic) sequence, where T n is a plane tree of size n, and σ n is a permutation of [n + 1] with exactly m cycles, where m = m n := n + 1 − 2g n . Let T n be T n with the vertices labeled 1, . . . , n + 1 uniformly at random, and letN (k) n,gn be the number of vertices of degree k in the underlying graph of the corresponding decorated tree (T n , σ n ).
Let n (k) n be the number of vertices of degree k in T n , and let m ( ) n be the number of cycles of length in σ n . Suppose that (ρ k ) and (π ) are probability distributions on {1, 2, . . . } such that, as n → ∞, where (χ k ) is a probability distribution which equals the distribution of the random sum M i=1 Y i , where M, Y 1 , Y 2 , . . . are independent, M has the distribution (π ) and each Y i has the distribution (ρ k ). Equivalently, (χ k ) is given by the probability generating function where H ρ and H π are the probability generating functions of (ρ k ) and (π ).
Proof. Let G n be the underlying graph of (T n , σ n ). Fix and number the cycles in σ n of length as C 1 , . . . , C m ( ) n . For each i ≤ m ( ) n , let X i1 , . . . , X i be the degrees in T n of the vertices covered by C i , taken in uniformly random order, and let D i = j=1 X ij be the degree of the corresponding vertex in G n .
For any sequence d = (d 1 , . . . , d ) ∈ Z + and i ≤ m Let |d| := d 1 + · · · + d . Then, by our definitions, Note that, for any given k, this is a finite sum. Hence, (6.12) implies, recalling (6.6), (6.14) This proves (6.3), with the limit χ k given by the right-hand side of (6.14). This clearly equals P( M 1 Y i = k), with M as in the statement. Furthermore, (6.14) implies that the generating function H χ is given by π l H ρ (x) = H π (H ρ (x)). (6.15) Proof of Theorem 1.3. We apply Theorem 2.1 and consider the underlying graph of (T, σ). Furthermore, we may do an extra randomization as in Lemma 6.1 of the way the tree T is decorated by the permutation σ; this obviously will not change the distribution ofN (k) n,gn . Now condition on T and σ, and note that the conditional distribution ofN (k) n,gn is as in Lemma 6.1, with T n = T and σ n = σ. These are random, and thus n with (π ) given by (4.3), where τ is given by (4.4) with α = 1 − 2θ. Furthermore, it is well-known that the degree distribution in a random plane tree is asymptotically Ge(1/2), see e.g. [10, Section 3.2.1] or [13, Theorem 7.11(ii) and Example 10.1]; more precisely, (6.1) holds in probability: By the Skorokhod coupling theorem [15,Theorem 4.30], we may assume that (6.16) and (6.17) hold a.s., for all k and , and then Lemma 6.1 apples after conditioning on T and σ. Consequently, (6.3) holds conditioned on T and σ, a.s., which implies that (6.3) holds without conditioning. This proves (1.6), and it remains only to identify the limit distribution.