2.1. Plane trees and their coding by laminations

Plane trees. We first define plane trees, following Neveu’s formalism [Reference Neveu37]. First, let $\mathbb{N}^* = \left\{ 1, 2, \ldots \right\}$ be the set of all positive integers, and let $\mathcal{U} = \cup_{n \geq 0} (\mathbb{N}^*)^n$ be the set of finite sequences of positive integers, with the convention that $(\mathbb{N}^*)^0 = \{ \emptyset \}$ .

By a slight abuse of notation, for $k \in \mathbb{Z}_+$ , we write an element u of $(\mathbb{N}^*)^k$ as $u=u_1 \cdots u_k$ , with $u_1, \ldots, u_k \in \mathbb{N}^*$ . For $k \in \mathbb{Z}_+$ , $u=u_1\cdots u_k \in (\mathbb{N}^*)^k$ , and $i \in \mathbb{N}^*$ , we denote by ui the element $u_1 \cdots u_k i \in (\mathbb{N}^*)^{k+1}$ and by iu the element $i u_1 \cdots u_k$ . A plane tree T is formally a subset of $\mathcal{U}$ satisfying the following three conditions:

1. (i) $\emptyset \in T$ ( $\emptyset$ is called the root of T).

2. (ii) If $u=u_1\cdots u_n \in T$ , then, for all $k \leq n$ , $u_1\cdots u_k \in T$ (these elements are called ancestors of u, and the set of all ancestors of u is called its ancestral line; $u_1 \cdots u_{n-1}$ is called the parent of u). The set of ancestors of a vertex u is denoted by $A_u(T)$ .

3. (iii) For any $u \in T$ , there exists a nonnegative integer $k_u(T)$ such that, for every $i \in \mathbb{N}^*$ , $ui \in T$ if and only if $1 \leq i \leq k_u(T)$ ( $k_u(T)$ is called the number of children of u, or the outdegree of u).

The elements of T are called vertices, and we denote by $|T|$ the total number of vertices in T. A vertex u such that $k_u(T)=0$ is called a leaf of T. The height h(u) of a vertex u is its distance to the root, that is, the unique integer k such that $u \in (\mathbb{N}^*)^k$ . We define the height of a tree T as $H(T) = {\sup}_{{u \in T}} \, h(u)$ . In the sequel, by tree we always mean plane tree unless specifically mentioned otherwise.

The lexicographical order $\prec$ on $\mathcal{U}$ is defined as follows: $\emptyset \prec u$ for all $u \in \mathcal{U} \backslash \{\emptyset\}$ , and for $u,w \neq \emptyset$ , if $u=u_1u'$ and $w=w_1w'$ with $u_1, w_1 \in \mathbb{N}^*$ , then we write $u \prec w$ if and only if $u_1 < w_1$ , or $u_1=w_1$ and $u' \prec w'$ . The lexicographical order on the vertices of a tree T is the restriction of the lexicographical order on $\mathcal{U}$ .

We do not distinguish between a finite tree T, and the corresponding planar graph where each vertex is connected to its parent by an edge of length 1, in such a way that the vertices with same height are sorted from left to right in lexicographical order. See Figure 8, left, for a tree labeled à la Neveu.

Figure 8.

A tree T labeled à la Neveu, its contour function C(T), and the associated lamination $\mathbb{L}(T)$ .

Subtrees and nodes. Let T be a plane tree and $u \in T$ one of its vertices. We define the subtree of T rooted in u as the set of vertices that have u as an ancestor. This subtree is denoted by $\theta_u(T)$ .

One will often consider large nodes in a tree, i.e. vertices whose removal splits the tree into at least two components of macroscopic size (that is, of the same order as the size of T) that do not contain the root. Specifically, $a \geq 0$ being fixed, we say that $u \in T$ is an a-node of T if there exists an integer $r \leq k_u(T)$ satisfying

\begin{align*}\sum_{w \in A_r(u,T)} |\theta_w(T)| \geq a, \qquad \sum_{w \in A_{-r}(u,T)} |\theta_w(T)| \geq a,\end{align*}

where $A_r(u,T)$ denotes the set of the first r children of u in lexicographical order, and $A_{-r}(u,T)$ the set of its other children. In other words, u is an a-node of T if one can split the set of its children into two disjoint subsets made up of consecutive children, in such a way that the sum of the sizes of the subtrees rooted in the elements of each of these two subsets is larger than a. In what follows, a will be of order $|T|$ (by this, we mean larger than $\epsilon |T|$ , for some $\epsilon>0$ ).

A particular case of a-nodes, for $a>0$ , is the case of a-branching points. We say that $u \in T$ is an a-branching point if there exist two children of u, say, $v_1(u)$ and $v_2(u)$ , such that $|\theta_{v_1(u)}(T)|\geq a, |\theta_{v_2(u)}(T)|\geq a$ . One easily sees that any a-branching point is an a-node. We denote by $E_a(T)$ the set of a-branching points of the tree T.

Contour function of a tree, and the associated lamination-valued process. We introduce here some important objects derived from a plane tree. Specifically, a finite plane tree T being given, we define its contour function, which is a walk on the nonnegative integers coding T in a bijective way. We then construct from this contour function a lamination $\mathbb{L}(T)$ and a random lamination-valued process $(\mathbb{L}_u(T))_{u \in [0,\infty]}$ which interpolates between $\mathbb{S}^1$ and $\mathbb{L}(T)$ . In what follows, T is a plane tree and n denotes its number of vertices.

The contour function C(T). First, it is useful to define the contour function

\begin{align*}(C_t(T), 0\leq t \leq 2n)\end{align*}

of T, which completely encodes the tree. To construct C(T), imagine a particle exploring the tree from left to right at unit speed, starting from the root. For $t \in [0,2n-2]$ , denote by $C_t(T)$ the distance of the particle to the root at time t. In addition, we set $C_t(T)=0$ for $2n-2 \leq t \leq 2n$ . (See Figure 8 for an example.) By construction, C(T) is continuous and nonnegative and satisfies $C_0(T)=C_{2n}(T)=0$ .

Chords and faces associated to vertices of T. We now propose a way of coding a vertex x of T by a chord in $\overline{\mathbb{D}}$ : define g(x) (resp. d(x)) to be the first (resp. last) time the particle performing this contour exploration is located at x, and denote by $c_x(T)$ the chord

\begin{align*}c_x(T) \,:\!=\, \left[e^{-2i\pi g(x)/2n}, e^{-2i\pi d(x)/2n}\right]\end{align*}

in $\overline{\mathbb{D}}$ . We define the lamination associated to the tree T by

\begin{align*}\mathbb{L}(T) \,:\!=\, \mathbb{S}^1 \cup \bigcup_{x \in T} c_x(T).\end{align*}

One can indeed check that the chords $(c_x(T), x \in T)$ do not intersect each other. See Figure 8, right, for an example.

The lamination-valued process $(\mathbb{L}_u(T))_{u \in [0,\infty]}$ . We derive here from T a random nondecreasing lamination-valued process, which interpolates between $\mathbb{S}^1$ and $\mathbb{L}(T)$ : at each integer time, we add a chord corresponding to a uniformly chosen vertex in the tree. More precisely, let $U_1$ be the root of T, and let $U_2, \ldots, U_n$ be a uniform random permutation of the $n-1$ other vertices of T. Then, for $u \in [0,\infty]$ , define

\begin{align*}\mathbb{L}_u(T) \,:\!=\, \mathbb{S}^1 \cup \bigcup_{i =1}^{\lfloor u \rfloor \wedge n} c_{U_i}(T).\end{align*}

Notice that, for $u \geq n$ , $\mathbb{L}_u(T) = \mathbb{L}(T)$ .

Lukasiewicz path of the tree. We define here another way to code the tree T, called its Lukasiewicz path and denoted by $(W_t(T))_{0 \leq t \leq n}$ . It is constructed as follows: start from $W_0(T)=0$ , and for all $i \in \mathbb{Z}_+, \, i \leq n-1$ , set $W_{i+1}(T)=W_i(T) + k_{v_i}(T) - 1$ , where $v_r$ denotes the $(r+1)$ th vertex of T in lexicographical order. Then W is the linear interpolation between these integer values. See Figure 9 for an example.

Figure 9.

A tree T and its Lukasiewicz path W(T).

One can check that $W_n(T)=-1$ and that, for all $t \leq n-1$ , $W_t \geq 0$ . This walk provides information on the degrees of the vertices of T, whereas the contour function provides information on the global shape of the tree.

2.2. Bi-type trees

We now give a plane tree additional structure, by coloring each of its vertices either black or white—a tree whose vertices are not colored will be called monotype from now on. We say that a finite plane tree T is a bi-type tree (in our context) if its vertices are colored white when their height is even and black when it is odd. In particular, white vertices only have black children and conversely, and the root is white. The number of white vertices in a bi-type tree T is denoted by $N^\circ(T)$ , and the number of black vertices by $N^\bullet(T)$ . See Figure 10, left, for an example of a bi-type tree.

Figure 10.

A labeled bi-type tree T, its associated white reduced tree $T^\circ$ , and the lamination $\mathbb{L}^\bullet_6(T)$ . To the left of some vertices are written the corresponding words in the definition of the tree à la Neveu.

We say that T is a labeled bi-type tree if, in addition, its black vertices are labeled from 1 to $N^\bullet(T)$ . Such models of trees have already been studied in the past, for example by Bouttier, Di Francesco, and Guitter [Reference Bouttier, Di Francesco and Guitter9], who establish a bijection between a class of planar maps and a class of labeled bi-type trees which they call mobiles.

Finally, for $n,k \geq 1$ , we denote by $\mathfrak{U}_n^{(k)}$ the set of labeled bi-type trees with n white vertices and k black vertices, whose leaves are all white, in which the labels of the black neighbors (parent and children) of each white vertex are sorted in decreasing clockwise order (starting from the neighbor with maximum label), and in which the labels of the children of the root are sorted in decreasing order from left to right. Notice that, then, $\mathfrak{U}_n = \cup_{k \geq 1} \mathfrak{U}_n^{(k)}$ .

The white reduced tree. Let T be a bi-type tree. We define its monotype white reduced tree $T^\circ$ as the plane tree satisfying the following:

• The vertices of $T^\circ$ are the white vertices of T.

• A vertex x is the child of a vertex y in $T^\circ$ if and only if x is a grandchild of y in the original tree T. Furthermore, the order of the children of a vertex in $T^\circ$ is their lexicographical order in T.

To stick to the definition of plane trees à la Neveu, notice that, given this planar structure (that is, the order of the children of each vertex), there is a unique consistent way of labeling the vertices of this white reduced tree (see Figure 10, middle).

This reduced tree encompasses the grandparent–grandchild relations between the white vertices in T. See Figure 10 for a picture of a tree and of the associated white reduced tree. For convenience, we make no distinction between a white vertex of T and the associated vertex of $T^\circ$ .

2.3. Colored laminations constructed from labeled bi-type trees

We propose here two ways to code a finite bi-type tree T by discrete nondecreasing colored lamination-valued processes. The first takes only white vertices into account, and is obtained from the contour function of the reduced tree $T^\circ$ . The second, which requires that the tree T be labeled, is obtained by considering the black vertices of T and their labeling.

The white process $\left(\mathbb{L}^\circ_u(T)\right)_{u \in [0,\infty]}$ . The white process of a bi-type tree T is the lamination-valued process presented in Section 2.1, applied to the white reduced tree $T^\circ$ :

\begin{align*}\mathbb{L}^\circ_u(T) \,:\!=\, \mathbb{S}^1 \cup \bigcup_{i=1}^{\lfloor u \rfloor \wedge N^\circ(T)} c_{U_i}(T^\circ)\end{align*}

for any $u \in [0,\infty]$ , where we recall that $U_1=\emptyset$ and $U_2, \ldots, U_n$ is a uniform permutation of the other vertices. Note that this construction is not an injection, as it depends only on $C(T^\circ)$ , and different bi-type trees may have the same white reduced tree. Note also that this process consists only of laminations, without any black points.

The black process $\left(\mathbb{L}^\bullet_u(T)\right)_{u \in [0,\infty]}$ . The black process of a bi-type tree T is derived from the contour function $(C_t(T),0 \leq t \leq 2|T|)$ of the whole labeled bi-type tree T. Here, black vertices are coded by faces of a colored lamination, and not by chords as in the white process. More precisely, we define the face $F_x(T)$ associated to a black vertex x of T the following way: let $0 \leq t_1 < t_2 < \ldots < t_{k_x(T)+1}$ be the times at which x is visited by the contour function C(T). Then define the associated face as

\begin{align*}F_x(T) \,:\!=\, Conv \left(\bigcup_{j=1}^{k_x(T)+1} \left[e^{-2i\pi t_j/2|T|}, e^{-2i\pi t_{j+1}/2|T|} \right] \right),\end{align*}

whose boundary is colored red and whose interior is colored black. In this definition, by convention, $t_{k_x(T)+2} = t_1$ , and Conv(A) denotes the convex hull of A.

Now, for $u \geq 0$ , define

\begin{align*}\mathbb{L}^\bullet_u(T) \,:\!=\, \mathbb{S}^1 \cup \bigcup_{i=1}^{\lfloor u \rfloor \wedge N^\bullet(T)} F_{V_i}(T),\end{align*}

where $V_i$ is the black vertex labeled i in T. The process $(\mathbb{L}^\bullet_u(T))_{u \in [0,\infty]}$ is called the black process associated to T (Figure 10 shows a tree $T \in \mathfrak{U}_{11}^{(7)}$ (left) and the colored lamination $\mathbb{L}^\bullet_6(T)$ (right)).

2.4. Random trees

Let us now define random variables taking their values in the set of finite trees. We first define the so-called monotype simply generated trees, and then extend this framework to bi-type trees, providing some useful properties of both models. To avoid ambiguity, random monotype trees will be written with a straight double $\mathbb{T}$ , and random bi-type trees with a curved $\mathcal{T}$ .

Monotype simply generated trees. In the monotype case, we mainly rely on the deep survey of Janson [Reference Janson23] on simply generated trees, in which all proofs and further details can be found. Monotype simply generated (MTSG) trees were first introduced by Meir and Moon [Reference Meir and Moon33], and are random variables taking their values in the space of finite monotype trees. Specifically, for any $n \geq 1$ , denote by $\mathfrak{T}_n$ the set of trees with n vertices. Fix $w \,:\!=\, (w_i)_{i \geq 0} \in \mathbb{R}_+^{\mathbb{Z}_+}$ a weight sequence such that $w_0>0$ , and to a finite tree T associate a weight

\begin{align*}W_w(T) \,:\!=\, \prod\limits_{x \in T} w_{k_x(T)}.\end{align*}

Then, for each $n \geq 1$ , we define the w-MTSG $\mathbb{T}_n^w$ with n vertices as the random variable satisfying, for any tree $T \in \mathfrak{T}_n$ ,

\begin{align*}\mathbb{P} \left( \mathbb{T}_n^w = T \right) = \frac{1}{Z_{n,w}} W_w(T),\end{align*}

where

\begin{align*}Z_{n,w} \,:\!=\, \sum_{T \in \mathfrak{T}_n} W_w(T) .\end{align*}

Since, for any $n \geq 1$ , the set $\mathfrak{T}_n$ is finite, the tree $\mathbb{T}_n^w$ is well-defined provided that $Z_{n,w}>0$ , which we implicitly assume.

Note that different weight sequences may provide the same simply generated tree, as shown by the following lemma.

Proof. The proof that (ii) $\Rightarrow$ (i) is essentially due to Kennedy [Reference Kennedy25] in a slightly different setting, and can be found in our form in [Reference Janson23, (4.3)]. To prove that (i) $\Rightarrow$ (ii), we proceed by induction on n. Assume without loss of generality that $w^{\prime}_1 > 0$ (the proof works the same way if this is not the case). There exists a unique pair $(q,s) \in (\mathbb{R}_+^*)^2$ such that $w_0= q w^{\prime}_0$ and $w_1=q s w^{\prime}_1$ . Now we consider the two different trees with three vertices: one has weight $w_0 w_1^2$ and the other $w_0^2 w_2$ , so that $Z_{2,w} = w_0 w_1^2 + w_0^2 w_2>0$ , and also $Z_{2,w'} = w^{\prime}_0 w^{\prime 2}_1 + w^{\prime 2}_0 w^{\prime}_2 \gt 0$ . Since $\mathbb{T}_2^w$ and $\mathbb{T}_2^{w^{\prime}}$ have the same distribution, $Z_{2,w}^{-1} w_0 w_1^2 = Z_{2,w^{\prime}}^{-1} w^{\prime}_0 w^{\prime 2}_1$ , which implies that $Z_{2,w} = q^3 s^2 Z_{2,w^{\prime}}$ and therefore that $w_2 = q s^2 w^{\prime}_2$ . By induction on $i \geq 2$ , we get that $w_i=qs^iw^{\prime}_i$ for all $i \geq 0$ .

Galton–Watson trees. When a weight sequence $\mu$ satisfies $\mu_0>0$ and $\sum_{i \geq 0} \mu_i = 1$ , $\mu$ is a probability distribution. If, in addition, $\sum_{i \geq 0} i \mu_i \leq 1$ , we can define a random variable $\mathbb{T}^\mu$ such that, for any finite tree T,

\begin{align*}\mathbb{P} \left( \mathbb{T}^\mu = T \right) = W_\mu(T) = \prod_{x \in T}\mu_{k_x(T)}.\end{align*}

This variable is defined on the whole set of finite trees, and not only on the subset of trees of fixed size. In this case, we say that $\mathbb{T}^\mu$ is a $\mu$ -Galton–Watson ( $\mu$ -GW) tree, and that $\mu$ is its offspring distribution. Thus, for any $n \geq 1$ , the MTSG $\mathbb{T}_n^\mu$ is a $\mu$ -GW tree conditioned to have n vertices.

Stable trees and stable processes. Recall that the probability law $\mu$ is said to be critical if $\sum_{i \geq 0} i \mu_i= 1$ . A particular case of Galton–Watson trees is when the offspring distribution $\mu$ is critical and in the domain of attraction of an $\alpha$ -stable law, for $\alpha \in (1,2]$ .

If $\mu$ is in the domain of attraction of an $\alpha$ -stable law, the sequence of trees $(\mathbb{T}_n^\mu)_{n \geq 1}$ , restricted to the values of n such that $\mathbb{P}(|\mathbb{T}^\mu|=n)>0)$ , is known to have a scaling limit: these trees, seen as metric spaces for the graph distance and properly renormalized, converge in distribution, for the so-called Gromov–Hausdorff distance, to some random compact metric space, introduced by Duquesne and Le Gall [Reference Duquesne and Le Gall16] and called the $\alpha$ -stable tree, which we denote by $\mathcal{T}^{\,\,(\alpha)}$ . (See Figure 11, left, for a simulation of the $1.5$ -stable tree $\mathcal{T}^{\,\,(1.5)}$ .)

Figure 11.

A simulation of the $1.5$ -stable tree $\mathcal{T}^{\,\,(1.5)}$ , the stable height process $H^{(1.5)}$ , and the process $X^{(1.5)}$ .

These trees have recently become a topic of interest for probabilists. In particular, a fundamental result states that, jointly with the convergence of the renormalized trees $(\mathbb{T}_n^\mu)_{n \geq 1}$ towards $\mathcal{T}^{\,\,(\alpha)}$ , their contour functions and Lukasiewicz paths also converge, after renormalization, to some limiting càdlàg random processes $(X_t^{(\alpha)})_{0 \leq t \leq 1}$ and $(H_t^{(\alpha)})_{0 \leq t \leq 1}$ respectively, which can therefore be seen as the analogues of the Lukasiewicz path and the contour function of these stable trees. (See Figure 11 for a simulation of $H^{(1.5)}$ (middle) and $X^{(1.5)}$ (right).) In the particular case $\alpha=2$ , we have $\big(X^{(2)}, H^{(2)}\big)\overset{(d)}{=} (\unicode{x1D556}, \unicode{x1D556})$ , where $(\unicode{x1D556}_t)_{0 \leq t \leq 1}$ is a standard Brownian excursion.

Theorem 2.1. Let $\alpha \in (1,2]$ and let $\mu$ be a critical probability distribution in the domain of attraction of an $\alpha$ -stable law. If $(B_n)_{n \geq 0}$ is a sequence satisfying (1.2), then, in distribution in $\mathbb{D}([0,1], \mathbb{R})^2$ ,

\begin{align*}\left( \frac{1}{B_n} W_{nt}\left(\mathbb{T}_n^\mu\right), \frac{B_n}{n} C_{2nt}\left(\mathbb{T}_n^\mu\right) \right)_{t \in [0,1]} \overset{(d)}{\underset{n \rightarrow \infty}{\rightarrow}} \left( X_t^{(\alpha)}, H_t^{(\alpha)} \right)_{t \in [0,1]}.\end{align*}

This result is due to Marckert and Mokkadem [Reference Marckert and Mokkadem32] under the assumption that $\mu$ has a finite exponential moment (that is, $\sum_{i \geq 0} \mu_i e^{\beta i}>0$ for some $\beta>0$ ). The result in the general case can be deduced from the work of Duquesne [Reference Duquesne14], although it is not clearly stated in this form. See [Reference Kortchemski27, Theorem 8.1, (II)] (taking $\mathcal{A}=\mathbb{Z}_+$ in this theorem) for a precise statement.

In light of this convergence, investigating properties of these limiting objects makes it possible to obtain information on the shape of a typical realization of the tree $\mathbb{T}_n^\mu$ for n large. Let us immediately see an example. For $\alpha \in (1,2)$ , the limiting process $X^{(\alpha)}$ satisfies the following properties with probability 1, where, for $s \in (0,1]$ , we have set $\Delta_s \,:\!=\, X^{(\alpha)}_{s} - X^{(\alpha)}_{s-}$ :

1. (H1) The local minima of $X^{(\alpha)}$ are distinct (that is, for any $0 \leq s < t \leq 1$ , there exists at most one $r\in (s,t)$ such that $X^{(\alpha)}_r = \inf_{[s,t]} X^{(\alpha)}$ ).

2. (H2) Let t be a local minimum of $X^{(\alpha)}$ (i.e. $X^{(\alpha)}_t = \min \{ X^{(\alpha)}_u, t-\epsilon \leq u \leq t+\epsilon\}$ for some $\epsilon>0$ ), and define $s \,:\!=\, \sup \left\{ r \leq t, X^{(\alpha)}_{r} < X^{(\alpha)}_{t} \right\}$ . Then $\Delta_s>0$ , and $X^{(\alpha)}_{s-} < X^{(\alpha)}_{t} < X^{(\alpha)}_{s}$ .

3. (H3) If $s \in (0,1)$ is such that $\Delta_s>0$ , then for all $0 \leq \epsilon \leq s$ , $\inf_{[s-\epsilon, s]} X^{(\alpha)} < X^{(\alpha)}_{s-}$ .

These three properties are used for instance in [Reference Kortchemski28], to construct the lamination $\mathbb{L}_\infty^{(\alpha)}$ , and are proved in [Reference Kortchemski28, Proposition 2.10]. The following lemma, which is a consequence of these properties of $X^{(\alpha)}$ , provides useful information about the structure of a large $\mu$ -GW tree.

In other words, (i) means that, with high probability, there is at least one vertex in $\mathbb{T}_n^\mu$ whose number of children is of order $B_n$ . Furthermore, (ii) states that all $\epsilon n$ -nodes of $\mathbb{T}_n^\mu$ (which appear to correspond to large faces in the associated lamination $\mathbb{L}(\mathbb{T}_n^\mu)$ ) have a number of children of order $B_n$ .

Proof of Lemma 2.2. The proof of (i) is straightforward: it is known that the set of points $t \in [0,1]$ where $\Delta_t>0$ is dense in [0,1] (for instance, the process satisfies Assumption (H0) in [Reference Kortchemski28]). In particular, almost surely, $M \,:\!=\, \max \, \{\Delta_t, t \in [0,1] \}>0$ . Fix $\epsilon>0$ , and take $\eta>0$ such that $M>2\eta$ with probability $\geq 1-\epsilon/2$ . By the convergence of Theorem 2.1, for n large enough, the maximum degree in $\mathbb{T}_n^\mu$ is larger than $\eta B_n$ with probability $\geq 1-\epsilon$ .

Let us now prove (ii). For x a vertex of $\mathbb{T}_n^\mu$ , denote by i(x) the position of x in $\mathbb{T}_n^\mu$ in lexicographical order. Take u to be an $\epsilon n$ -node in $\mathbb{T}_n^\mu$ . In particular, $W_{i(u)}-W_{i(u)-1} = k_u(\mathbb{T}_n^\mu)-1$ . By definition of an $\epsilon n$ -node, its children can be split into two subsets $A_r(u), A_{-r}(u)$ for some $r \geq 1$ , such that

\begin{align*}\sum_{w \in A_r(u)} |\theta_w(\mathbb{T}_n^\mu)| \geq \epsilon n\end{align*}

and

\begin{align*}\sum_{w \in A_{-r}(u)} |\theta_w(\mathbb{T}_n^\mu)| \geq \epsilon n.\end{align*}

Let $v(u) \in \mathbb{T}_n^\mu$ be the first vertex of $A_{-r}(u)$ in lexicographical order. Then it is clear by definition of W that

(2.1) \begin{equation}W_{i(u)-1}(\mathbb{T}_n^\mu) \leq W_{i(v(u))-1}(\mathbb{T}_n^\mu) \leq W_{i(u)}(\mathbb{T}_n^\mu).\end{equation}

Now assume by the Skorokhod representation theorem that the convergence of Theorem 2.1 holds almost surely. Assume that, for n along a subsequence, there exists an $\epsilon n$ -node $u_n$ in $\mathbb{T}_n^\mu$ such that $W_{i(u_n)}(\mathbb{T}_n^\mu) - W_{i(u_n)-1}(\mathbb{T}_n^\mu) = o(B_n)$ as $n \rightarrow \infty$ (that is, $u_n$ has $o(B_n)$ children). Since [0,1] is compact, up to extraction, one can assume in addition that there exist $0<s<t<1$ such that $i(u_n)/n \rightarrow s$ and $i(v(u_n))/n \rightarrow t$ . Thus, the limiting process $X^{(\alpha)}$ should satisfy

$(\textrm{a}')$ $X^{(\alpha)}_{s} = X^{(\alpha)}_{t-}$ ,

$(\textrm{b}')$ $X^{(\alpha)}_{t-} = \inf_{[t-\epsilon, t+\epsilon]} X^{(\alpha)}$ .

Indeed, (a^′) can be deduced from (2.1) and the fact that $W_{i(u_n)}(\mathbb{T}_n^\mu) - W_{i(u_n)-1}(\mathbb{T}_n^\mu) = o(B_n)$ , while (b^′) comes from (a^′) along with the fact that W is larger than $W_{i(u_n)}(\mathbb{T}_n^\mu)-1$ on $[i(u_n), i(v(u_n))+2\epsilon n]$ as $|\theta_u(\mathbb{T}_n^\mu)| \geq 2 \epsilon n$ . There are now two possible cases:

• First, if $\Delta_s=0$ , then, as by (H1) the local minima of $X^{(\alpha)}$ are almost surely distinct, $X^{(\alpha)}_s$ is not a local minimum of $X^{(\alpha)}$ (since by (b^′) $X^{(\alpha)}_{t-}$ is a local minimum). Therefore, $s= \sup \big\{r \leq t, X^{(\alpha)}_r < X^{(\alpha)}_t \big\}$ , and by (H2), $\Delta_s>0$ , which contradicts our assumption.

• Second, if $\Delta_s>0$ then by (H3) $s= \sup \big\{r \leq t, X^{(\alpha)}_r < X^{(\alpha)}_t \big\}$ ; by (H2), it should happen that $X^{(\alpha)}_t<X^{(\alpha)}_s$ , which is not the case by (a^′).

In conclusion, almost surely, there exists $\eta>0$ such that, as $n \rightarrow \infty$ , all $\epsilon n$ -nodes in $\mathbb{T}_n^\mu$ have at least $\eta B_n$ children.

We can now present a first result of convergence concerning the lamination-valued process associated to the trees $\mathbb{T}_n^\mu$ , $n \geq 1$ . As the renormalized contour functions of these trees converge as $n \rightarrow \infty$ to $H^{(\alpha)}$ by Theorem 2.1, it appears that the associated processes of laminations converge towards the $\alpha$ -stable lamination-valued process $(\mathbb{L}_c^{(\alpha)})_{c \in [0,\infty]}$ .

Theorem 2.2. Let $\alpha \in (1,2]$ , let $\mu$ be a distribution in the domain of attraction of an $\alpha$ -stable law, and let $(B_n)$ satisfy (1.2). Jointly with the convergence of Theorem 2.1, the following holds in distribution in $\mathbb{D}([0,\infty],\mathbb{CL}(\overline{\mathbb{D}}))$ :

\begin{align*}\left( \mathbb{L}_{cB_n}\left(\mathbb{T}_n^\mu\right) \right)_{c \in [0,\infty]} \overset{(d)}{\rightarrow}\left(\mathbb{L}_c^{(\alpha)}\right)_{c \in [0,\infty]},\end{align*}

where we recall that the process $(\mathbb{L}_c^{(\alpha)})_{c \in [0,\infty]}$ is obtained from $H^{(\alpha)}$ by the construction of Section 1.

This result is an immediate consequence of [Reference Thévenin40, Theorem 3.3 and Proposition 4.3], and is a cornerstone of the proof of (1.4).

To end this section on random monotype trees, we provide a useful tool in the study of Galton–Watson trees called the local limit theorem. It can be seen for instance as a consequence of [Reference Kortchemski27, Theorem 8.1, (I)], taking $\mathcal{A}=\mathbb{Z}_+$ in the following statement.

Theorem 2.3. (Local limit theorem.) Let $\mu$ be a critical distribution in the domain of attraction of a stable law, and let $(B_n)$ satisfy (1.2). Then there exists a constant $C>0$ such that, for the values of n for which $\mathbb{P}( |\mathbb{T}^\mu|=n)>0$ ,

\begin{align*}\mathbb{P} \left( |\mathbb{T}^\mu|=n \right) \sim \frac{C}{n B_n}\end{align*}

as $n \rightarrow \infty$ .

In particular, $\mathbb{P}(|\mathbb{T}^\mu|=n)$ decreases more slowly than some polynomial in n.

Bi-type simply generated trees. We now define the bi-type analogue of MTSG trees, which we call bi-type simply generated (BTSG) trees. Such random bi-type trees appear for instance in [Reference Le Gall and Miermont30].

Let $w^\circ, w^\bullet$ be two weight sequences, and impose that $w^\bullet_0=0$ and $w^\circ_0>0$ . For T a bi-type tree, define the weight of T as

\begin{align*}W_{w^\circ,w^\bullet}(T) \,:\!=\, \prod\limits_{x \in T, x \text{ white}} w^\circ_{k_x(T)} \times \prod\limits_{y \in T, y \text{ black}} w^\bullet_{k_y(T)}.\end{align*}

An integer n being fixed, a $(w^\circ, w^\bullet)$ -BTSG with n white vertices is a random variable $\mathcal{T}_n^{\,\,(w^\circ, w^\bullet)}$ , taking its values in the set $\mathfrak{BT}_n$ of bi-type rooted trees with n white vertices, such that the probability that $\mathcal{T}_n^{\,\,(w^\circ, w^\bullet)}$ is equal to some bi-type tree $T \in \mathfrak{BT}_n$ is

\begin{align*}\mathbb{P}\left( \mathcal{T}_n^{\,\,(w^\circ, w^\bullet)} = T \right) = \frac{1}{Z_{n,w^\circ,w^\bullet}} W_{w^\circ,w^\bullet}(T).\end{align*}

Here,

\begin{align*}Z_{n,w^\circ,w^\bullet} = \sum_{T \in \mathfrak{BT}_n} W_{w^\circ,w^\bullet}(T)\end{align*}

is a renormalization constant (as before, we shall restrict ourselves to the values of n such that $Z_{n,w^\circ,w^\bullet}>0$ ). Note that, since we impose the condition $w^\bullet_0=0$ , the set $\{ T \in \mathfrak{BT}_n, W_{w^\circ,w^\bullet}(T)>0 \}$ is finite at n fixed, and therefore $Z_{n,w^\circ,w^\bullet}<\infty$ . In addition, the leaves of $\mathcal{T}_n^{\,\,(w^\circ, w^\bullet)}$ are all white, and the number of black vertices in $\mathcal{T}_n^{\,\,(w^\circ,w^\bullet)}$ is at most $n-1$ .

As in the monotype case (Lemma 2.1), different pairs $(w^\circ,w^\bullet)$ may give the same BTSG.

Lemma 2.3. (Exponential tilting.) Take two sequences $w^\circ,w^\bullet$ such that $w^\bullet_0=0$ and $w^\circ_0>0$ . Take $p,q,r,s \in \mathbb{R}_+^*$ such that $qr=1$ , and define two new weight sequences $\tilde{w}^\circ,\tilde{w}^\bullet$ as, for $i \in \mathbb{Z}_+$ ,

\begin{align*}\tilde{w}^\circ_i=pq^iw^\circ_i, \tilde{w}^\bullet_i=rs^iw^\bullet_i.\end{align*}

Then, for all $n\geq 1$ , $\mathcal{T}_n^{\,\,(w^\circ, w^\bullet)}$ has the same distribution as $\mathcal{T}_n^{\,\,(\tilde{w}^\circ, \tilde{w}^\bullet)}$ .

In this case, we say that $(w^\circ,w^\bullet)$ and $(\tilde{w}^\circ,\tilde{w}^\bullet)$ are two equivalent pairs of weight sequences. One easily checks that this indeed defines an equivalence relation on the set of pairs of weight sequences $(w^\circ,w^\bullet)$ such that $w^\bullet_0=0$ and $w^\circ_0>0$ .

Proof. Fix $n \geq 1$ . Take T to be a bi-type tree with n white vertices, and denote by k the number of black vertices in T. Observe that

\begin{align*}W_{\tilde{w}^\circ,\tilde{w}^\bullet}(T) &= \prod\limits_{x \in T, \, x \text{ white}} \tilde{w}^\circ_{k_x(T)} \times \prod\limits_{y \in T, \, y \text{ black}} \tilde{w}^\bullet_{k_y(T)}\\&= \prod\limits_{x \in T, \, x \text{ white}} p q^{k_x(T)}w^\circ_{k_x(T)} \times \prod\limits_{y \in T, \, y \text{ black}} r s^{k_y(T)} w^\bullet_{k_y(T)}\\&= p^n q^k r^k s^{n-1} \prod\limits_{x \in T, \, x \text{ white}} w^\circ_{k_x(T)} \times \prod\limits_{y \in T, \, y \text{ black}} w^\bullet_{k_y(T)}\\&= p^n s^{n-1} W_{w^\circ, w^\bullet}(T) \quad \text{ since } qr=1.\end{align*}

This implies in particular that $Z_{n,\tilde{w}^\circ,\tilde{w}^\bullet} = p^n s^{n-1} Z_{n,w^\circ,w^\bullet}$ . Thus, for any tree $T \in \mathfrak{BT}_n$ ,

\begin{align*}\mathbb{P} \left( \mathcal{T}_n^{\,\,(\tilde{w}^\circ, \tilde{w}^\bullet)}=T \right) = \mathbb{P} \left( \mathcal{T}_n^{\,\,(w^\circ, w^\bullet)}=T \right),\end{align*}

which provides the result.

3.1. Coding a minimal factorization by a colored lamination

The first step of our bijection consists in adapting the bijection introduced by Goulden and Yong [Reference Goulden and Yong20] to code minimal factorizations into transpositions by monotype trees with labeled vertices. In our broader framework, we code general minimal factorizations by bi-type trees with n white vertices and labeled black vertices. We check first that we can code a minimal factorization of the n-cycle by a colored lamination, as explained in Section 1.2. For this, we need to be able to define the face associated to a cycle appearing in the factorization.

For $n \geq 1$ , we say that a cycle $\tau \in \mathfrak{C}_n$ is increasing if it can be written as $(e_1 \, e_2 \, \cdots \, e_{\ell(\tau)})$ , where $e_1 < e_2 < \ldots < e_{\ell(\tau)}$ .

Although this result is already proven in [Reference Biane and Josuat-Vergès6], we provide here a different proof, introducing tools that will be useful in what follows.

To prove Proposition 3.1, we make use of what we call the transposition slicing of a minimal factorization, which is roughly speaking a decomposition into transpositions of the factorization.

Definition 3.1. Let $n,k \geq 1$ and $f \,:\!=\, (\tau_1,\ldots,\tau_k) \in \mathfrak{M}_n^{(k)}$ . We define from f a factorization $\tilde{f}$ of the n-cycle into transpositions as follows: for $1 \leq i \leq k$ , let us write the cycle $\tau_i$ as

\begin{align*}\Big(d^{(i)}_1 \ldots d^{(i)}_{\ell(\tau_i)}\Big),\end{align*}

where $d^{(i)}_1$ is the minimum of the support of $\tau_i$ . Now observe that $\tau_i$ can be written as the product of $(\ell(\tau_i)-1)$ transpositions:

\begin{align*}\Big(d_1^{(i)} d_2^{(i)}\Big) \, \Big(d_1^{(i)} d_3^{(i)}\Big) \cdots \Big(d_1^{(i)} d_{\ell(\tau_i)}^{(i)}\Big).\end{align*}

By replacing all cycles of f by their decomposition into transpositions, we obtain a factorization $\tilde{f}$ of the n-cycle into transpositions, which we call the transposition slicing of f.

See Figure 12 for an example. It is clear that, if f is a minimal factorization of the n-cycle, then its transposition slicing $\tilde{f}$ consists of $n-1$ transpositions, and hence is a minimal factorization of the n-cycle into transpositions. This allows us to translate results on $\tilde{f}$ (mostly taken from [Reference Goulden and Yong20]) into results on f.

Figure 12.

The labeled colored laminations $S_{lab}(f)$ (left) and $S_{lab}(\tilde{f})$ (right), for $f \,:\!=\, (5678)(23)(125)(45)$ . Constructing the second one from the first one just consists in triangulating each black face, starting from the smallest of its vertices.

Proof of Proposition 3.1. Let $n,k \geq 1$ and $f \,:\!=\, (\tau_1, \ldots, \tau_k) \in \mathfrak{M}_n^{(k)}$ . We first construct a lamination, denoted by $S_{lab}(\tilde{f})$ , by giving labels to the faces of $S(\tilde{f})$ (which are in fact all chords): for the ith transposition of $\tilde{f}$ , say $(a_i \, b_i)$ , draw the chord $[e^{-2i\pi a_i/n}, e^{-2i\pi b_i/n}]$ , and label it i. This provides a lamination in which all chords are labeled. Furthermore, [Reference Goulden and Yong20, Theorem $2.2$ (iii)] states that chords in $S_{lab}(\tilde{f})$ are labeled in increasing clockwise order around each vertex $e^{-2i j \pi/n}, 1 \leq j \leq n$ . (Note that they are sorted in decreasing clockwise order in [Reference Goulden and Yong20]: indeed the coding of [Reference Goulden and Yong20] is slightly different from ours, since they label the nth roots of unity decreasingly clockwise. Nonetheless, our result is an easy consequence of theirs.)

Thus, for any $i \leq k$ , around the vertex $e^{-2i\pi d_1^{(i)}/n} \in \overline{\mathbb{D}}$ , the chords of $S_{lab}(\tilde{f})$ are labeled in clockwise increasing order (see Figure 12, right, for an example). This implies that $d_1^{(i)} < d_2^{(i)} < \ldots < d_{\ell(i)}^{(i)}$ and the result follows.

We can therefore code a factorization f by a colored lamination with labeled faces, by labeling the black faces of S(f) from 1 to k (where k denotes the number of cycles that appear in f) in the order in which they appear. See Figure 12, left, for an example. We denote this labeled colored lamination by $S_{lab}(f)$ .

These properties can be easily deduced from the results of [Reference Goulden and Yong20, Section 2], which straightforwardly imply that they are satisfied by $S_{lab}(\tilde{f})$ . In particular, the chords of $S_{lab}(\tilde{f})$ form a tree and are labeled in increasing clockwise order around each vertex (see Figure 12, right, for an example).

Proof. Let us first check $P_1$ . It is clear by definition that $S_{lab}(f)$ has k black faces. Now observe that each white face contains exactly one arc of the form $\widehat{(e^{-2i\pi a/n},e^{-2i\pi(a+1)/n})}$ (where $a \in \mathbb{Z})$ in its boundary, since the chords of $S_{lab}(\tilde{f})$ form a tree (see [Reference Goulden and Yong20, Theorem 2.2(i)]). As there are exactly n such arcs, $P_1$ is satisfied.

To prove $P_2$ , notice that two white faces cannot be neighbors, as they need a chord to separate them, which belongs to a black face. In addition, one can check that two black faces cannot have a chord in common in their boundaries; otherwise either the same transposition would appear twice in $\tilde{f}$ , or there would be a cycle of chords in $S_{lab}(\tilde{f})$ . None of these configurations can happen, which proves $P_2$ .

$P_3$ follows from a similar argument, again using the fact that the chords of $S_{lab}(\tilde{f})$ form a tree.

To prove $P_4$ , let a be an nth root of unity and F, F ^′ two consecutive black faces around a in clockwise order. Then there exist two chords c (resp. c ^′) in their respective boundaries in $S_{lab}(\tilde{f})$ having a as an endpoint, and corresponding to a transposition that appears in the cycle of f coded by F (resp. F ^′). By [Reference Goulden and Yong20, Theorem 2.2], the labels of c and c ^′ are sorted in increasing clockwise order around a. By definition of $\tilde{f}$ , so are the labels of F and F ^′.

One can check in addition that, if a labeled colored lamination has these four properties, then it also satisfies the following:

1. P₅: Let F be a white face of $S_{lab}(f)$ . By $P_4$ , F has exactly one arc in its boundary, of the form $\widehat{(e^{-2i\pi a/n},e^{-2i\pi(a+1)/n})}$ for some $a \in \mathbb{Z}$ . The labels of its neighboring black faces are sorted in decreasing clockwise order around F, starting from this unique arc.

For $n,k \geq 1$ , we now define $\mathfrak{K}_n^{(k)}$ to be the set of labeled colored laminations having the properties $P_1$ – $P_4$ . In addition, setting $\mathfrak{K}_n = \cup_{1 \leq k \leq n-1} \mathfrak{K}_n^{(k)}$ , we have the following.

Theorem 3.1. Let $n,k \geq 1$ . The map

\begin{align*}\Phi_n^{(k)}: \left\{\begin{array}{l} \mathfrak{M}_n^{(k)} \rightarrow \mathfrak{K}_n^{(k)} \\[5pt] f \mapsto S_{lab}(f)\end{array}\right.\end{align*}

is a bijection.

As a corollary, the map $\Phi_n\,:\, \mathfrak{M}_n \rightarrow \mathfrak{K}_n, f \mapsto S_{lab}(f)$ is also a bijection.

Proof. Let f be an element of $\mathfrak{M}_n^{(k)}$ . By Proposition 3.2, $S_{lab}(f)$ is an element of $\mathfrak{K}_n^{(k)}$ , and therefore $\Phi_n^{(k)}$ is well-defined. It is also clearly an injection. Let us now take $L \in \mathfrak{K}_n^{(k)}$ . We prove that there exists a minimal factorization $f \in \mathfrak{M}_n^{(k)}$ such that $L=S_{lab}(f)$ . To this end, for $i \in [\![ 1,k ]\!]$ , denote by $F_i$ the black face of L labeled i, and denote by $\ell(i)$ the number of chords in its boundary. These chords connect $\exp(-2i\pi a_1/n), \ldots, \exp(-2i\pi a_{\ell(i)}/n)$ so that $1 \leq a_1<a_2<\cdots<a_{\ell(i)} \leq n$ . Let $c_i \,:\!=\, (a_1 \, a_2 \, \cdots \, a_{\ell(i)})$ , and consider the product $\sigma \,:\!=\, c_1 c_2 \cdots c_k$ . By $P_4$ and $P_5$ , it is clear that, for all $j \in [\![ 1,n ]\!]$ , $\sigma(j)=j+1 \mod n$ . Thus, $\sigma$ is the n-cycle. In addition, $f \,:\!=\, (c_1, c_2, \ldots, c_k)$ is an element of $\mathfrak{M}_n^{(k)}$ , which satisfies $L = S_{lab}(f)$ . The result follows.

3.2. Coding a minimal factorization by a bi-type tree

We now construct from $S_{lab}(f)$ a tree T(f). We then prove that, for $n,k \geq 1$ , the map

\begin{align*}\Psi_n^{(k)}\,:\, f \rightarrow T(f)\end{align*}

is a bijection from $\mathfrak{M}_n^{(k)}$ to the set of bi-type trees $\mathfrak{U}_n^{(k)}$ . For this we rely on Theorem 3.1, proving in fact that the mapping $\Psi^{(k)}_n \circ (\Phi_n^{(k)})^{-1}$ is bijective. As a corollary,

\begin{align*}\Psi_n\,:\, \mathfrak{M}_n \rightarrow \mathfrak{U}_n, f \rightarrow T(f)\end{align*}

is also a bijection.

Let $n,k \geq 1$ and take $f \,:\!=\, (\tau_1, ..., \tau_k) \in \mathfrak{M}_n^{(k)}$ to be a minimal factorization of the n-cycle. To f, we associate the graph T(f), constructed as the dual graph of $S_{lab}(f)$ : black vertices correspond to black faces of $S_{lab}(f)$ , while white vertices correspond to its white faces. Specifically, put a white vertex in each white face of $S_{lab}(f)$ , and a black vertex in each of its black faces (including faces of perimeter 2, which correspond to transpositions in f). Now, draw an edge between two vertices whenever the boundaries of the corresponding faces share a chord. Finally, root this graph at the white vertex corresponding to the white face whose boundary contains the arc $\widehat{1,e^{-2i\pi/n}}$ , and give to each black vertex of T(f) the label of the corresponding face in $S_{lab}(f)$ . See Figure 13 for an example.

Figure 13.

An application of the bijection $\Psi_8$ to the minimal factorization $f \,:\!=\, (5678)(23)(125)(45) \in \mathfrak{M}_8$ . Top left: the colored lamination $S_{lab}(f)$ . Top right: the same lamination, with its dual tree T(f) drawn in blue. The larger white vertex is its root. Bottom: the dual tree T(f).

Proof. Let us check all properties of $\mathfrak{U}_n^{(k)}$ one by one. First, T(f) is clearly connected by construction. Moreover, since each chord splits the unit disk into two disjoint connected components, T(f) is necessarily a tree. By the property $P_1$ , T(f) has exactly k black vertices and n white vertices, and by $P_2$ all neighbors of a white vertex are black and vice versa. The root of T(f) is white by construction, and it is therefore a bi-type tree. In addition, a leaf of T(f) has only one neighbor, and hence necessarily corresponds to a face that has an arc in its boundary. In particular this face is white, and thus all leaves of T(f) are white. Finally, by $P_5$ , the labels of the neighbors of each white face are sorted in decreasing clockwise order and the labels of the children of the root are decreasing from left to right. In conclusion, $T(f) \in \mathfrak{U}_n^{(k)}$ .

Notice in particular that the degree of a black vertex in T(f) corresponds to the length of the corresponding cycle in f. This mapping is a bijection, as stated in the following theorem.

Theorem 3.2. For any $n,k \geq 1$ , the map

\begin{align*}\Psi_n^{(k)} : \, & \mathfrak{M}_n^{(k)} \rightarrow \mathfrak{U}_n^{(k)} \\& f \mapsto T(f)\end{align*}

is a bijection.

Notice that, by Lemma 3.1, $\Psi_n^{(k)}$ is well-defined from $\mathfrak{M}_n^{(k)}$ to $\mathfrak{U}_n^{(k)}$ .

Proof of Theorem 3.2. We rely here on [Reference Goulden and Yong20, Section 3], where the Goulden–Yong bijection and its inverse are constructed. Let us construct as well the inverse of the map $\Psi_n^{(k)}$ . Fixing a tree $T \in \mathfrak{U}_n^{(k)}$ , we shall construct a lamination $L \,:\!=\, S_{lab}(f)$ associated to a minimal factorization f, such that $T=T(f)$ .

To this end, we define a labeling of the white vertices of the tree T. For each white vertex, define its special corner as the corner between its black neighbors with minimal and maximal labels, in counterclockwise order. Then explore the tree according to the contour process and label the white vertices in the order in which their special corners are visited. An example is given in the top right panel of Figure 14.

Figure 14.

An example of the inverse bijection $\Phi_8 \circ (\Psi_8)^{-1}$ . Top left: a tree $T \in \mathfrak{U}_8$ . The red crosses show the special corners of two white vertices. Top right: the tree T with labels on its white vertices, following the white exploration process. Bottom left: the locations of the arcs corresponding to these white vertices, on the circle. Bottom right: the associated colored lamination. We recover from this that $\Psi_8^{-1}(T)=(5678)(23)(125)(45)$ .

Let us now construct a colored lamination L whose dual tree is exactly T. The idea (which is the main interest of this labeling of white vertices) is that the white vertex labeled k shall correspond to the white face whose boundary contains the arc $(\widehat{e^{-2i(k-1)\pi/n},e^{-2ik\pi/n}})$ . In particular, the root corresponds to the arc $(\widehat{1,e^{-2i\pi/n}})$ . The colored lamination L is constructed by drawing the faces that correspond to black vertices of T, and giving them the label of the associated vertices. See Figure 14 for an example. There is a unique way of drawing such a colored lamination; to see this, observe that there is only one way to draw the face corresponding to a black vertex whose children are all leaves, and that this drawing does not depend on the label of the white parent of this black vertex. Thus, by induction on the maximum height of the children of a black vertex, there is only one way to draw all black faces from the leaves to the root, which gives L. Furthermore, L belongs to $\mathfrak{K}_n^{(k)}$ by construction. Thus, by Theorem 3.1, there exists $f \in \mathfrak{M}_n$ such that $L=S_{lab}(f)$ . Hence, f satisfies $T=T(f)$ , and $\Psi_n^{(k)}$ is a bijection.

3.3. Image of a random weighted minimal factorization

We now investigate random weighted minimal factorizations of the n-cycle. Take $(w_i)_{i \geq 1}$ to be a weight sequence, and recall that $f_n^w$ is a minimal factorization of the n-cycle chosen proportionally to its weight:

\begin{align*}\mathbb{P} (f_n^w=f) \propto \prod\limits_{i=1}^{k(f)} w_{\ell(\tau_i)-1},\end{align*}

where k(f) is the number of cycles in f. Then it turns out that the random tree $T(f_n^w)$ (which is the image of $f_n^w$ by $\Psi_n$ ) is a BTSG.

Proof of Theorem 3.3. Take T to be a bi-type tree with n white vertices, whose leaves are all white. The number of labelings of the black vertices that are clockwise decreasing around each white vertex is exactly

\begin{align*}n! \left(\prod\limits_{x \in T, \, x \,\text{ white}} k_x(T)!\right)^{-1}.\end{align*}

Furthermore, by Theorem 3.2, given such a labeling of T, exactly one minimal factorization is coded by the tree T labeled this way, and this factorization has weight

\begin{align*} \prod\limits_{y \in T, y \,\text{ black}} w^\bullet_{k_y(T)}.\end{align*}

Finally,

\begin{align*}\mathbb{P} \left( T(f_n^w) = T \right) \propto \prod\limits_{x \in T, x \,\text{ white}} \frac{1}{k_x(T)!} \prod\limits_{y \in T, y \,\text{ black}} w_{k_y(T)}.\end{align*}

The result follows.

Proof. Take $n, k \geq 1$ . For any $f \,:\!=\, (\tau_1,\ldots,\tau_k) \in \mathfrak{M}_n$ , we have

\begin{align*}W_{w^{(s)}}(f) &= \prod_{i=1}^k w_{\ell(\tau_i)-1} s^{\ell(\tau_i)-1} = s^{\sum_{i=1}^k \left(\ell(\tau_i)-1 \right)} \times \prod_{i=1}^k w_{\ell(\tau_i)-1} = s^{n-1} W_w(f)\end{align*}

by definition of $\mathfrak{M}_n$ . Recalling that we have defined

\begin{align*}Y_{n,v} = \sum_{f \in \mathfrak{M}_n} W_v(f)\end{align*}

for any weight sequence v, this implies that $Y_{n,w^{(s)}} = s^{n-1} Y_{n,w}$ and therefore that, for $f \in \mathfrak{M}_n$ ,

\begin{align*}\mathbb{P}\left( f_n^{w^{(s)}} = f \right) = \frac{W_{w^{(s)}}(f)}{Y_{n,w^{(s)}}} = \frac{W_w(f)}{Y_{n,w}} = \mathbb{P}\left( f_n^w = f \right).\end{align*}

The result follows.

Recall that we say that two weight sequences w, w ^′ are equivalent if, for all $n \geq 1$ ,

\begin{align*}\mathcal{T}_n^{\,\,(\mu_*,w)} \overset{(d)}{=} \mathcal{T}_n^{\,\,(\mu_*,w^{\prime})}.\end{align*}

One can check, the same way as in Lemma 2.1, that the sequences $w^{(s)}$ , $s>0$ , are the only sequences equivalent to w. Indeed, recalling the notation of Lemma 2.3, the white weight sequence $w^\circ$ is the same (equal to $\mu_*$ ) in both trees $\mathcal{T}_n^{\,\,(\mu_*,w)}$ and $\mathcal{T}_n^{\,\,(\mu_*,w')}$ , and thus the parameters p and q will be equal to 1. Since we impose the condition $qr=1$ , the only parameter that is allowed to vary is s. It is therefore natural to obtain a family indexed by only one parameter s.

4.1. Reachable distributions: a study of the white reduced tree

Before proving Theorem 4.1, we study some properties of the white reduced tree $\mathcal{T}_n^\circ$ , in order to control the white process of $\mathcal{T}_n$ .

Recall that, a weight sequence $(w_i)_{i \geq 1}$ being given, there exists at most one critical probability distribution $\nu$ , called the critical equivalent of w, such that, for some $s>0$ , for all $i \geq 1$ , $\nu_i = w_i s^i$ . If this is the case, the white reduced tree $\mathcal{T}_n^\circ$ is distributed as a size-conditioned Galton–Watson tree whose offspring distribution may be chosen to be critical. In what follows, we denote by $\mu$ this unique critical offspring distribution. The goal of this section is to investigate the possible behaviors of its offspring distribution, and in particular for which sequences w this white reduced tree converges to a stable tree. Indeed, in this case, the white process of $\mathcal{T}_n$ converges by Theorem 2.2, which helps us prove the convergence of the black process of $\mathcal{T}_n$ . As a byproduct, we provide a proof of Proposition 1.2.

Let us state this formally. To a weight sequence w, we associate its generating function

\begin{align*}F_w\,:\, x \rightarrow \sum\limits_{i = 0}^\infty w_i x^i.\end{align*}

In particular, $F_{\mu_*}(x) \,:\!=\, e^{x-1}$ is defined for any $x \in \mathbb{R}$ . It is a simple matter of fact that the white reduced tree $\mathcal{T}_n^{\circ}$ is distributed as the MTSG tree $\mathbb{T}_n^{\tilde{w}}$ , where $\tilde{w}$ is the weight sequence whose generating function satisfies

\begin{align*}F_{\tilde{w}} = F_{\mu_*} \circ F_w \,:\!=\, e^{F_w-1}.\end{align*}

We say that a critical probability distribution $\mu$ is reachable if there exists a weight sequence $(w_i)_{i \geq 1}$ such that, for all $n \geq 1$ , $\mathcal{T}_n^{\circ}$ is a $\mu$ -GW tree conditioned to have n vertices. In this case, we say that w reaches $\mu$ . The following theorem states that a large range of distributions are reachable.

Theorem 4.2. For any $\alpha \in (1,2)$ and any slowly varying function L, there exists a reachable critical distribution $\mu$ such that

(4.1) \begin{equation}F_\mu(1-u)-(1-u) \underset{\substack{u \downarrow 0 \\ u \neq 0}}{\sim} u^\alpha L\left(u^{-1}\right).\end{equation}

For any $\alpha=2$ and any $\ell>0$ , there exists a reachable critical distribution $\mu$ such that

(4.2) \begin{equation}F_\mu(1-u)-(1-u) \underset{\substack{u \downarrow 0 \\ u \neq 0}}{\sim} u^2 \ell\end{equation}

if and only if $\ell \geq 1/2$ . This is equivalent to saying that $\mu$ has finite variance $2\ell$ .

Furthermore, if w is a weight sequence that reaches a critical probability distribution $\mu$ , then the following two points are equivalent:

• $\mu$ satisfies (4.1) or (4.2);

• the critical equivalent $\nu$ of w satisfies

  \begin{align*}F_\nu(1-u)-(1-u) \underset{\substack{u \rightarrow 0 \\ u \neq 0}}{\sim}\begin{cases}\displaystyle \quad u^\alpha L(u^{-1}) \quad { if }\ \alpha \in (1,2), \\[4pt] \displaystyle \quad u^2 \left( \ell-1/2 \right) \quad { if }\ \mu\ { has\ finite\ variance.}\end{cases}\end{align*}

Furthermore, by e.g. [Reference Feller17, XVII.5, Theorem 2] and [Reference Björnberg and Stefánsson8 Lemma 4.7], if a distribution $\mu$ satisfies (4.1), then a variable X of law $\mu$ satisfies (1.1) for the same slowly varying function L. Thus, if $(B_n)_{n \geq 1}$ is a sequence of positive numbers satisfying (1.2) for $\nu$ , and $(\tilde{B}_n)_{n \geq 1}$ is the sequence constructed from $(B_n)_{n \geq 1}$ as in (1.3), then $(\tilde{B}_n)$ satisfies (1.2) for $\mu$ . This relation between the two is the reason for the scaling in $\tilde{B}_n$ appearing in both Theorems 1.1 and 4.1.

Theorem 4.2 also means that the only way to reach a distribution in the domain of attraction of a stable law is to start from a weight sequence whose critical equivalent is already in the domain of attraction of a stable law.

Theorem 4.2 is the consequence of a general result about reachable distributions, which may be of independent interest: a reachable $\mu$ being given, all weight sequences that reach it are closely related.

Proposition 4.1. Let $\mu$ be reachable, and choose w to be a weight sequence reaching $\mu$ . Then, for any weight sequence w^′, w^′ reaches $\mu$ if and only if there exist $s,t>0$ such that

\begin{align*}F_{w^{\prime}}(tx) - F_{w^{\prime}}(t) = F_w(sx) - F_w(s).\end{align*}

In particular, the set of weight sequences reaching $\mu$ can be written as $\{ w^{(s)}, s \in \mathbb{R}_+^* \}$ , defined as follows: for any $s>0$ and any $i \geq 1$ , $w^{(s)}_i \,:\!=\, w_i s^i$ .

Proof. Let w be a weight sequence reaching $\mu$ , and let $\tilde{w}$ be the weight sequence such that $F_{\tilde{w}} = e^{F_w-1}$ . Then $\tilde{w}$ satisfies, for some $q,s>0$ , by Lemma 2.1,

\begin{align*}\forall x \in [-1,1], \qquad F_\mu(x) = q F_{\tilde{w}}(sx) = q e^{F_w(sx)-1}.\end{align*}

Applying this for $x=1$ , one gets $1=q e^{F_w(s)-1}$ , which finally gives

\begin{align*}\forall x \in [-1,1], \qquad F_\mu(x) = e^{F_w(sx)-F_w(s)}.\end{align*}

The result follows directly.

Let us see how this implies Theorem 4.2.

Proof of Theorem 4.2. We start by proving the first part of this theorem. When $\alpha<2$ , one can define $\nu$ to be a critical distribution satisfying $\nu_k = k^{-1-\alpha} L(k)$ , for k large enough. Thus, $F_\nu(1-u)-(1-u) \sim u^\alpha (L(u^{-1}))$ as $u \rightarrow 0$ , by e.g. [Reference Bingham, Goldie and Teugels7 Theorem 8.1.6]. Now, define the weight sequence w by $w_0=0$ and $w_i=\nu_i$ for $i \geq 1$ . In particular,

\begin{align*}F_w(1-u)-F_w(1)=F_\nu(1-u)-F_\nu(1)=-u+u^\alpha L(u^{-1}) (1+o(1)),\end{align*}

and $F^{\prime}_w(1)=1$ . One can check that the probability law $\mu$ such that $F_\mu(x)=e^{F_w(x)-F_w(1)}$ is reached by w and is critical. One gets in addition

\begin{align*}F_\mu(1-u) = e^{F_w(1-u)-F_w(1)} &= e^{F_\nu(1-u)-1}\\&= F_\nu(1-u) + \frac{1}{2} ( (F_\nu(1-u)-1)^2 )\\&= 1-u + u^\alpha L( u^{-1}) + o(u^\alpha),\end{align*}

which implies the first part of Theorem 4.2.

When $\alpha=2$ and $L(x) \underset{x \rightarrow \infty}{\rightarrow} \ell \geq 1/2$ , choose any critical distribution $\nu$ with variance $2\ell-1$ and construct w from $\nu$ the same way. This leads to

\begin{align*}F_\mu(1-u) =1-u+u^2 \left(\ell-\frac{1}{2} \right) + \frac{u^2}{2} + o(u^2).\end{align*}

Next, we shall prove that any critical reachable distribution has variance greater than 1. For any $\mu$ reachable and any weight sequence w reaching $\mu$ , there exists $s>0$ such that, for all $x \in (-1,1)$ , $F_\mu(x)=e^{F_w(sx)-F_w(s)}$ . After differentiating once and applying at $x=1$ , one gets

(4.3) \begin{equation}1=F^{\prime}_\mu (1)=sF^{\prime}_w(s).\end{equation}

By differentiating twice, one gets, for any $x \in (-1,1)$ ,

(4.4) \begin{equation}F^{\prime\prime}_\mu (x) = s^2 \left(F^{\prime\prime}_w (sx) + \left( F^{\prime}_w (sx)\right)^2 \right) e^{F_w(sx)-F_w(s)}.\end{equation}

Assume now that $\mu$ has finite variance $\sigma_\mu^2$ . Since $\mu$ is critical, $\sigma^2_\mu=F^{\prime\prime}_\mu (1)$ . Letting x go to 1 in (4.4), we get by (4.3) that $\sigma_\mu^2=s^2 F^{\prime\prime}_w(s)+1 \geq 1$ .

The second part is just a consequence of Lemma 4.1 and the construction of suitable weight sequences in the beginning of this proof.

Using Theorem 4.2, we can now prove Proposition 1.2. To this end, we rely on the following lemma, inspired by [Reference Le Gall and Miermont30, Section 5, Lemma 5].

Let us see how this implies Proposition 1.2.

Proof of Proposition 1.2. It is clear, by the bijection of Section 3, that the maximum length of a cycle in a minimal factorization F is the maximum degree of a black vertex in T(F). Thus, by Theorem 3.3, we need to study the maximum degree of a black vertex in the conditioned BTSG $\mathcal{T}_n$ . Let us denote by $\mu$ the critical distribution such that $\mathcal{T}_n^\circ$ is a size-conditioned $\mu$ -GW tree. By Theorem 4.2, $(\tilde{B}_n)_{n \geq 0}$ satisfies (1.2) for $\mu$ . If $\alpha=2$ , by the convergence of Theorem 2.1 applied to $\mathcal{T}_n^\circ$ , the maximum degree of a white vertex in $\mathcal{T}_n^{\circ}$ (that is, the maximum number of grandchildren of a white vertex in $\mathcal{T}_n$ ) is $o(B_n)$ with high probability. Thus, the maximum degree of a black vertex in $\mathcal{T}_n$ is necessarily $o(B_n)$ as well. In particular, if $\nu$ has finite variance then this maximum degree is $o(\sqrt{n})$ .

If $\alpha<2$ , then for any $\epsilon>0$ , again by the convergence of Theorem 2.1, there exists $C>0$ such that, with probability larger than $1-\epsilon$ , the maximum degree of a white vertex in $\mathcal{T}_n^\circ$ is less than $C \tilde{B}_n$ . Thus the maximum degree of a black vertex is also less than $C \tilde{B}_n$ with probability larger than $1-\epsilon$ . To prove the lower bound on this quantity, take $\epsilon>0$ and $\eta$ such that, with probability larger than $1-\epsilon$ , there exists a white vertex u in $\mathcal{T}_n^{\,\,(\mu_*,w)}$ with at least $\eta\tilde{B}_n$ white grandchildren. Such an $\eta$ exists by Lemma 2.2(i). Then, by Lemma 4.1, one can choose $\delta>0$ such that, with high probability, all white grandchildren of u except at most $\tilde{B}_n n^{-\delta}$ of them have the same black parent b(u). Hence, for n large enough, with probability larger than $1-2\epsilon$ , b(u) has at least $\eta\tilde{B}_n/2$ children. The result follows.

We finish by proving Lemma 4.1.

Proof of Lemma 4.1. The proof is inspired by [Reference Le Gall and Miermont30, Section 5, Lemma 5]. Fix $\delta>0$ such that $2 \delta (\alpha+1/\alpha)<1-1/\alpha$ .

Take $\eta>0$ , and n large enough so that $\eta \tilde{B}_n > 2 \tilde{B}_n n^{-\delta}$ . For u a white vertex of a bi-type tree T, for any $k,M \geq 1$ , define the following event E(T, u, k, M): u has k black children and a number $M \geq \eta \tilde{B}_n$ of white grandchildren, and simultaneously none of its black children has more than $M - \tilde{B}_n n^{-\delta}$ white children.

Notice that the event E(T, u, k, M) implies that at least two black children of u have more than $\tilde{B}_n n^{-\delta}/k$ white children. Hence

\begin{align*}p_{n,\,k} \, & \,:\!=\, \mathbb{P} \left( \bigcup_{\substack{u \in \mathcal{T}^{\,\,\circ}_n \\ M \geq \eta \tilde{B}_n}} E(\mathcal{T}_n, u, k, M) \right) \leq n \sum_{M \geq \eta \tilde{B}_n} \mathbb{P} \left( E(\mathcal{T}_n, U, k, M) \right)\\&\leq n \sum_{M \geq \eta \tilde{B}_n} \mathbb{P} \left( k_U(\mathcal{T}_n^\circ)=M \right) \mathbb{P} \left( E'(\mathcal{T}_n, U, k) | k_U(\mathcal{T}_n^\circ)=M \right),\end{align*}

where E ^′(T, u, k) is the probability that u has k black children, two of which have at least $\tilde{B}_n n^{-\delta}/k$ white children, and U is a white vertex of $\mathcal{T}_n$ chosen uniformly at random. Observe now that, by independence properties of the tree $\mathcal{T}_n$ , for all $M \geq 1$ such that $\mathbb{P}\left( k_U(\mathcal{T}_n^\circ)=M \right)>0$ , we have

\begin{align*}\mathbb{P} \left( E'(\mathcal{T}_n, U, k) | k_U(\mathcal{T}_n^\circ)=M \right) = \mathbb{P} \left( E'(\mathcal{T}, \emptyset, k) | k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right),\end{align*}

where we recall that $\mathcal{T}$ is the unconditioned bi-type Galton–Watson tree and $\emptyset$ is its root. Observe indeed that $\mathbb{P}\left( k_U(\mathcal{T}_n^\circ)=M \right)>0$ implies $\mathbb{P}\left( k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)>0$ . Thus, one gets

\begin{align*}p_{n,\,k} &\leq n \sum_{M \geq \eta \tilde{B}_n} \mathbb{P} \left( k_U(\mathcal{T}_n^\circ)=M \right) \mathbb{P} \left( E'(\mathcal{T}, \emptyset, k) | k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)\\&\leq n \sum_{M \geq \eta \tilde{B}_n} \frac{\mathbb{P} \left( k_U(\mathcal{T}_n^\circ)=M \right)}{\mathbb{P} \left( k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)} \mathbb{P} \left( E'(\mathcal{T}, \emptyset, k), k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right),\end{align*}

where we implicitly restrict ourselves to the values of M such that $\mathbb{P} \left( k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)>0$ .

Assume that there exists a constant $C>0$ such that, for n large enough, for all $M \geq \eta \tilde{B}_n$ , $\mathbb{P} \left( k_U(\mathcal{T}_n^\circ)=M \right) \leq C \tilde{B}_n \mathbb{P} \left( k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)$ , which we will show later. Then one gets

\begin{align*}p_{n,\,k} &\leq C \tilde{B}_n \, n \, \sum_{M \geq \eta \tilde{B}_n} \mathbb{P} \left( E'(\mathcal{T}, \emptyset, k), k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right) \leq C \tilde{B}_n \, n \, \mathbb{P}\left( E'(\mathcal{T}, \emptyset, k) \right)\\&\leq C \tilde{B}_n \, n \, \mu_*(k) \binom{k}{2} \nu \left([\tilde{B}_n n^{-\delta}/k, \infty) \right)^2\end{align*}

by construction of $\mathcal{T}$ .

On the other hand, by standard properties of the domain of attraction of stable laws (see e.g. [Reference Feller17, Corollary XVII.5.2]), there exists a constant $K>0$ such that, for all $R>0$ , $\nu ([R, \infty)) \leq K R^{-\alpha+\delta}$ . Hence, one gets

\begin{align*}C \tilde{B}_n \, n \sum_{k=2}^\infty \mu_*(k) \binom{k}{2} \nu \left([\tilde{B}_n n^{-\delta}/k, \infty) \right)^2 &\leq C \tilde{B}_n \, n K^2 \left(\sum_{k=2}^\infty \mu_*(k) \binom{k}{2} k^{2\alpha-2\delta} \right) \tilde{B}_n^{-2\alpha+2\delta} n^{2\alpha \delta}\\&= O \left( n^{1+2\alpha \delta} \tilde{B}_n^{1+2\delta-2\alpha} \right).\end{align*}

Using (4.14) and the definition of $\delta$ ,

\begin{align*}n^{1+2\alpha \delta} \tilde{B}_n^{1+2\delta-2\alpha} \leq n^{2\delta(\alpha+1/\alpha)-1} \ell(n)^{2\delta-2\alpha}\end{align*}

for some slowly varying function $\ell$ . Finally, it is well-known that, for any $\epsilon>0$ , for n large enough, $\ell(n) \in (n^{-\epsilon}, n^{\epsilon})$ , by the so-called Potter bounds (see e.g. [Reference Bingham, Goldie and Teugels7 Theorem 1.5.6] for a precise statement and a proof). Thus,

\begin{align*}n^{1+2\alpha \delta} \tilde{B}_n^{1+2\delta-2\alpha} = o(1)\end{align*}

as $n \rightarrow \infty$ , which proves our result.

The only thing we need to prove is that for some constant $C>0$ , for n large enough, for all $M \geq \eta \tilde{B}_n$ , $\mathbb{P} \left( k_U(\mathcal{T}_n^\circ)=M \right) \leq C \tilde{B}_n \mathbb{P} \left( k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)$ . To this end, observe that

\begin{align*}\mathbb{P} \left( k_U(\mathcal{T}_n^\circ)=M \right) &=\frac{1}{n} \sum_{i=0}^n \mathbb{E} \left[ \sum_{u \in \mathcal{T}^{\,\,\circ}_n} F_{n-i} \left(Cut_u(\mathcal{T}^{\,\,\circ}_n) \right) G_i\left( \theta_u(\mathcal{T}^{\,\,\circ}_n) \right) \right],\end{align*}

where $F_{n-i}(T)=\unicode{x1D7D9}_{|T|=n-i}$ and $G_i(T)=\unicode{x1D7D9}_{k_\emptyset(T)=M, |T|=i}$ . Thus, we have

\begin{align*}\mathbb{P} \left( k_U(\mathcal{T}_n^\circ)=M \right) &= \frac{1}{n} \frac{1}{\mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=n \right)}\sum_{j \geq 0} \sum_{i=0}^n \mathbb{E} \bigg[ \unicode{x1D7D9}_{|\mathcal{T}^{\,\,\circ}|=n} \sum_{u \in \mathcal{T}^{\,\,\circ}, |u|=j} F_{n-i} \left(Cut_u(\mathcal{T}^{\,\,\circ}) \right) G_i\big( \theta_u(\mathcal{T}^{\,\,\circ}) \big) \bigg]\\[3pt]&\leq \frac{1}{n} \frac{1}{\mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=n \right)}\sum_{j \geq 0} \sum_{i=0}^n \mathbb{E} \bigg[ \sum_{u \in \mathcal{T}^{\,\,\circ}, |u|=j} F_{n-i} \left(Cut_u(\mathcal{T}^{\,\,\circ}) \right) G_i\big( \theta_u(\mathcal{T}^{\,\,\circ}) \big) \bigg].\end{align*}

Here, for T a tree and u a vertex of T, $Cut_u(T)$ denotes the tree $T\backslash \theta_u(T)$ , obtained by cutting T at the level of u (not keeping u).

In order to investigate this quantity, let us now define $\mathcal{T}^{\,*}$ , the so-called local limit of the conditioned Galton–Watson trees $\mathcal{T}^{\,\,\circ}_n$ : $\mathcal{T}^{\,*}$ is a random variable taking its values in the set of infinite trees, and satisfies, for all $r \geq 1$ ,

\begin{align*}B_r(\mathcal{T}^{\,\,\circ}_n) \overset{(d)}{\rightarrow} B_r(\mathcal{T}^{\,*}),\end{align*}

where, a tree T (finite or infinite) being given, $B_r(T)$ denotes the ball of radius r around the root of T for the graph distance—that is, all edges have length 1. The structure of this tree $\mathcal{T}^{\,*}$ , called Kesten’s tree, is known: it has a unique infinite branch, on which independent nonconditioned $\mu$ -GW trees are planted. See Figure 15 for an illustration, and [Reference Kesten26] for more background. Information on the large tree $\mathcal{T}^{\,\,\circ}_n$ can therefore be deduced from the properties on $\mathcal{T}^{\,*}$ .

Figure 15.

Kesten’s infinite tree $\mathcal{T}^{\,*}$ . On the infinite branch (in the middle), independent $\mu$ -GW trees are planted.

In particular, by estimates à la Lyons–Pemantle–Peres (see [Reference Duquesne15, Section 3]), we obtain that, for any $j \geq 0$ ,

(4.5) \begin{equation}\mathbb{E} \left[ \sum_{u \in \mathcal{T}^{\,\,\circ}, |u|=j} F_{n-i}(Cut_u(\mathcal{T}^{\,\,\circ})) G_i(\theta_u(\mathcal{T}^{\,\,\circ})) \right] = \mathbb{E} \left[ F_{n-i}\left(Cut_{U^*_j}(\mathcal{T}^{\,*}) \right) \right] \mathbb{E} \left[ G_i(\mathcal{T}^{\,\,\circ}) \right],\end{equation}

where $U_j^*$ denotes the unique vertex of the infinite branch of $\mathcal{T}^{\,*}$ at height j. This is equal to

\begin{align*}\mathbb{P}\left(|Cut_{U^*_j}(\mathcal{T}^{\,*})|=n-i\right) \mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=i, k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right).\end{align*}

By summing over all $0 \leq i \leq n$ and all $j \geq 0$ , one gets finally

\begin{align*}\mathbb{P}\! \left( k_U(\mathcal{T}_n^\circ)=M \right) &\leq \frac{1}{n} \frac{1}{\mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=n \right)} \sum_{i=0}^n \!\left( \sum_{j \geq 0} \mathbb{P}\!\left( |Cut_{U^*_j}(\mathcal{T}^{\,*})|=n-i \right)\!\! \right)\! \mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=i, k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)\\&\leq \frac{1}{n} \frac{1}{\mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=n \right)}\sum_{i=0}^n \mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=i, k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right)\\&\leq \frac{1}{n} \frac{1}{\mathbb{P}\left( |\mathcal{T}^{\,\,\circ}|=n \right)} \mathbb{P}\left(k_\emptyset(\mathcal{T}^{\,\,\circ})=M \right).\end{align*}

Since $\mathcal{T}^{\,\,\circ}$ is a $\mu$ -GW tree where $\mu$ is in the domain of attraction of a stable law, the estimate of Theorem 2.3 allows us to conclude.

4.2. Compared counting of the vertices in the tree $\mathcal{T}_n$ and the white reduced tree $\mathcal{T}_n^{\circ}$

Before we prove Theorem 4.1 in the next subsection, we gather results concerning the number of black vertices in different connected components of the tree $\mathcal{T}_n$ , comparing them to the number of white vertices in these connected components. It appears that these quantities are asymptotically proportional, the proportionality constant being the average number of black children of a white vertex. Let us state things properly.

Lemma 4.2. (Number of black vertices in a BTSG.) Let w be a weight sequence of $\alpha$ -stable type for some $\alpha \in (1,2]$ , and let $\nu$ be its critical equivalent. As $n \rightarrow \infty$ ,

\begin{align*}\frac{1}{n} N^\bullet\left(\mathcal{T}_n \right) \overset{\mathbb{P}}{\rightarrow} 1-\nu_0.\end{align*}

Notice that Lemma 4.2 straightforwardly implies Proposition 1.1, using Theorem 3.3.

Proof. The idea of the proof is to split the set of black vertices in the tree according to the number of white grandchildren of their parents. Letting $N_k^{n,\circ}$ denote the number of white vertices in $\mathcal{T}_n$ that have exactly k white grandchildren, we observe two things: (i) for any fixed $K \in \mathbb{Z}_+$ , jointly for $k \in [\![ 1,K ]\!]$ , we have with high probability

(4.6) \begin{equation}\left| N_k^{n,\circ} - n \mu_k \right| \leq n^{3/4};\end{equation}

(ii) conditionally to the fact that a white vertex has k white grandchildren, its number of black children is independent of the rest of the tree, and is distributed as a variable $X_k$ satisfying $X_0=0$ almost surely and $1 \leq X_k \leq k$ for all $k \geq 1$ .

Indeed, (i) is a consequence of the joint asymptotic normality of the quantities $N_k^{n,\circ}$ (see e.g. [Reference Thévenin41, Theorem 6.2(iii)]), while (ii) is clear by definition of the BTSG. Let us see how this implies our result. Fix $\epsilon>0$ , and $K\geq 1$ such that $\sum_{k=1}^K k \mu_k \geq 1-\epsilon$ . Such a K exists by criticality of $\mu$ . By (i) and (ii), a central limit theorem on the variables $X_k,k \leq K$ gives that, with high probability, jointly for any $0 \leq k \leq K$ ,

(4.7) \begin{equation}|N_k^{n,\bullet}-n\mu_k \mathbb{E}[X_k]|\leq n^{4/5},\end{equation}

where $N_k^{n,\bullet}$ denotes the number of black vertices in the tree whose parent has k white grandchildren. On the other hand, a white vertex u being given, its number of black children is necessarily less than its number of white grandchildren. Thus we get that the total number of black vertices in the tree whose parent has at least $K+1$ white grandchildren satisfies

\begin{align*}\sum_{k \geq K+1} N_k^{n,\bullet} \leq \sum_{k \geq K+1} k N_k^{n,\circ} = (n-1) - \sum_{k =0}^K k N_k^{n,\circ},\end{align*}

as $\sum_{k \in \mathbb{Z}_+} k N_k^{n,\circ}$ is the number of white grandchildren in the tree, which is equal to $n-1$ (only the root is not a grandchild of any white vertex). Therefore, applying (4.6) to each $k \leq K$ , we get that

\begin{align*}\sum_{k \geq K+1} N_k^{n,\bullet} \leq \epsilon n + (K+1) n^{3/4}\end{align*}

with high probability. Finally, using (4.7), as $n \rightarrow \infty$ ,

\begin{align*}\mathbb{P} \left( \left|\frac{N^\bullet\left(\mathcal{T}_n\right)}{n} - \sum_{k \in \mathbb{Z}_+} \mu_k \mathbb{E}[X_k] \right| \geq 2 \epsilon \right) \rightarrow 0.\end{align*}

The only thing left to prove is that

(4.8) \begin{equation}\sum_{k \geq 0} \, \mu_k \, \mathbb{E}\left[ X_k \right] = 1-\nu_0.\end{equation}

To this end, we see the tree $\mathcal{T}_n$ as a bi-type Galton–Watson tree. We define two probability measures $\mu^\circ, \mu^\bullet$ as follows:

(4.9) \begin{align}&\forall i \geq 0, \qquad \mu^\circ_i = (\mu_*)_i \, e^{\nu_0} \, (1-\nu_0)^i; \nonumber \\&\mu^\bullet_0=0, \quad \text{ and } \forall i \geq 1, \qquad \mu^\bullet_i = (1-\nu_0)^{-1} \nu_i.\end{align}

One easily checks that these measures have total mass 1. A quantity of particular interest is the mean of $\mu^\circ$ :

(4.10) \begin{equation}\sum_{j \geq 1} j \, \mu^\circ_j = \sum_{j \geq 1} j \, (\mu_*)_j \, e^{\nu_0} \, (1-\nu_0)^j = e^{\nu_0-1} \, \sum_{j \geq 1} j \, \frac{(1-\nu_0)^j}{j!} = 1-\nu_0.\end{equation}

Furthermore, by Lemma 2.3, for any $n \geq 1$ , $\mathcal{T}_n^{\,\,(\mu^\circ, \, \mu^\bullet)} \overset{(d)}{=} \mathcal{T}_n$ . We can therefore write

\begin{align*}\sum_{k \geq 0} \, \mu_k \, \mathbb{E}\left[ X_k \right] &= \sum_{k \geq 0} \, \mu_k \, \sum_{j \geq 1} j \, \mathbb{P} \left( k_\emptyset\left(\mathcal{T}_n^{\,\,(\mu^\circ, \, \mu^\bullet)}\right)=j \big| k_\emptyset\left(\mathcal{T}_n^{\circ,(\mu^\circ, \, \mu^\bullet)}\right)=k \right).\end{align*}

Indeed, by definition, the variable $X_k$ is distributed as the number of black children of $\emptyset$ (or any other white vertex) conditionally to the fact that $\emptyset$ has k white grandchildren. Now observe that, since $\mu^\circ$ and $\mu^\bullet$ are probability measures, one can define the bi-type Galton–Watson tree $\mathcal{T}^{\,\,(\mu^\circ, \, \mu^\bullet)}$ as in the monotype case, as the random variable on the set of finite bi-type trees satisfying, for any bi-type tree T,

\begin{align*}\mathbb{P} \left( \mathcal{T}^{\,\,(\mu^\circ, \, \mu^\bullet)} = T \right) = \prod\limits_{x \in T, x \text{ white}} \mu^\circ_{k_x(T)} \times \prod\limits_{y \in T, y \text{ black}} \mu^\bullet_{k_y(T)}.\end{align*}

In particular, the BTSG $\mathcal{T}_n^{\,\,(\mu^\circ, \, \mu^\bullet)}$ is distributed as the tree $\mathcal{T}^{\,\,(\mu^\circ, \, \mu^\bullet)}$ conditioned to have n white vertices. Now recall that $\mu$ is the critical distribution such that $\mathcal{T}_n^\circ\overset{(d)}{=} \mathbb{T}_n^\mu$ for all $n \geq 1$ . For all k, $\mu_k=\mathbb{P}(k_\emptyset(\mathcal{T}^{\circ,(\mu^\circ, \, \mu^\bullet)})=k)$ . Thus, using the fact that, conditionally to the number of white grandchildren of a white vertex u of $\mathcal{T}_n$ , the number of black children of u is independent of the rest of the tree, we can prove (4.8). Here, for convenience, we write $\mathcal{T}$ for $\mathcal{T}^{\,\,(\mu^\circ, \, \mu^\bullet)}$ and $\mathcal{T}^{\,\,\circ}$ for $\mathcal{T}^{\circ,(\mu^\circ, \, \mu^\bullet)}$ . We have

\begin{align*}\sum_{k \geq 0} \, \mu_k \, \mathbb{E}\left[ X_k \right] &= \sum_{k \geq 0} \, \mu_k \, \sum_{j \geq 1} j \, \mathbb{P} \left( k_\emptyset\left(\mathcal{T}\,\right)=j \big| k_\emptyset\left(\mathcal{T}^{\,\,\circ}\right)=k \right)\\&= \sum_{j\geq 1} j \sum_{k \geq 0} \, \mathbb{P} \left( k_\emptyset\left(\mathcal{T}\,\right)=j \big| k_\emptyset\left(\mathcal{T}^{\,\,\circ}\right)=k \right) \mathbb{P} \left(k_\emptyset\left(\mathcal{T}^{\,\,\circ}\right)=k\right)\\&= \sum_{j \geq 1} j \, \mathbb{P} \left(k_\emptyset\left(\mathcal{T}\,\right)=j\right) = \sum_{j \geq 1} j \, \mu^\circ_j,\end{align*}

which implies (4.8) by (4.10).

We now generalize this statement, by investigating the number of black vertices in different components of a tree. This refinement allows us to precisely control the location of large faces in the black process of the tree, and thus to prove Theorem 4.1. Specifically, a tree T being given, each vertex u of T induces a partition of the set of vertices of T into three parts: the set $G_1(u,T)$ of vertices that are visited for the first time by the contour function C(T) before u, the subtree $G_2(u,T)$ rooted in u, and the set $G_3(u,T)$ of the vertices visited for the first time by C(T) after u has been visited for the last time.

Lemma 4.3. We have the following convergence in probability as $n \rightarrow \infty$ , jointly for $i=1,2,3$ :

\begin{align*}n^{-1} \underset{u \in \mathcal{T}_n, u \text{ white }}{\max} \left| \left|G_i\left(u,\mathcal{T}_n^{\circ}\right) \right| - \left(1+(1-\nu_0)\right)^{-1} \, \left|G_i(u,\mathcal{T}_n)\right|\right| \overset{\mathbb{P}}{\rightarrow} 0,\end{align*}

where we recall that we also denote by u the vertex in $\mathcal{T}_n^{\circ}$ corresponding to u.

In other words, the proportions of vertices in $\mathcal{T}_n$ in lexicographical order respectively before u, in the subtree rooted at u and after u are, with high probability, close to the proportions of vertices in $\mathcal{T}_n^{\circ}$ in lexicographical order before u, in the subtree rooted at u and after u. This boils down to proving that, in each of these components, the number of black vertices is roughly $(1-\nu_0)$ times the number of white vertices.

Proof. Fix $\epsilon>0$ , and take $K \in \mathbb{Z}_+$ such that $\sum_{k=0}^K k \mu_k \geq 1-\epsilon$ . For $0 \leq k \leq K$ , denote by $N^k_{2nt}(\mathcal{T}_n^{\circ})$ , for $0 \leq t \leq 1$ , the number of different vertices in $\mathcal{T}_n^{\circ}$ with k children visited by the contour function $C(\mathcal{T}_n^\circ)$ before time 2nt. Then it is known (see [Reference Thévenin41, Theorem 1.1(ii)] for the finite variance case and [Reference Thévenin41, Theorem 6.1(ii)] for the infinite variance case) that, uniformly in $k \leq K$ ,

(4.11) \begin{equation}\left( \frac{N^k_{2nt}\left( \mathcal{T}_n^{\circ} \right) - n \mu_k t}{\sqrt{n}} \right)_{0 \leq t \leq 1} \underset{n \rightarrow \infty}{\overset{(d)}{\rightarrow}} \left(C_1 \unicode{x1D556}_t + C_2 B_t \right)_{0 \leq t \leq 1},\end{equation}

where $C_1, C_2$ are constants that depend only on $\mu$ , $\unicode{x1D556}$ is a normalized Brownian excursion, and B is a Brownian motion independent of $\unicode{x1D556}$ .