Invariance principles for labeled mobiles and bipartite planar maps

Jean-François MarckertLAMA, Universite de Versailles-Saint Quentin , Grégory MiermontEquipe Probabilités, Statistique et Modélisation, Bat. 425, Université Paris-Sud, 91405 Orsay, France

November 27, 2006

A class of labeled trees, called mobiles, was introduced by Bouttier-di Francesco and Guitter in order to generalize the bijective studies of planar maps initiated by Cori-Vauquelin and Schaeffer. We prove an invariance principle for rescaled random mobiles associated with bipartite random planar maps under a Boltzmann distribution. We infer that the latter converge in a certain sense to the Brownian map introduced by Marckert and Mokkadem, which encompasses results of Chassaing and Schaeffer on quadrangulations (although in a slightly different context). These results are derived from a new invariance principle for a class of two-type Galton-Watson trees coupled with a spatial motion, which are shown to converge to the Brownian snake.

Key Words: Random planar maps, labeled mobiles, invariance principle, spatial Galton-Watson trees M.S.C. Code: 60F17, 60J80, 05C30 1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1 Introduction, motivations and main results

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.1 Planar maps

A planar map is a proper embedding $\mathbf{m}$  of a graph into the two-dimensional sphere $\mathbb{S}$  , considered up to any homeomorphism of the sphere. A connected component of $\mathbb{S}\backslash \mathbf{m}$  is homeomorphic to a disk, and is called a face. The degree of a face is the number of edges that constitute its boundary (with the convention that an edge included in a face is counted twice). In this paper, we consider only bipartite planar maps, i.e. maps such that the degree of any face is an even number.

A pointed map is a map $\mathbf{m}$  in which a vertex $u$  is distinguished. When dealing with a pointed map, we may label each vertex by the length of the minimal path of edges linking this vertex to the distinguished one (the “geodesic distance” to $u$  ). A root in a pointed map $(\mathbf{m},u)$  is then a distinguished non oriented edge $vw$  . By the bipartite nature of the map, the two ends of such an edge have geodesic distances to $u$  of the form $k$  and $k+1$  , so the choice of a root is the same as that of an oriented edge starting at the vertex with least label.

Figure 1 : On the first picture, an element of ${\mathcal{ℳ}}_5$  . Its distinguished edge is $vw$  , the distinguished node is $u$  . The degree of the face where $w$  is written is 6. On the second picture, the nodes are labeled by their geodesic distance to the distinguished vertex. On the last picture, a labeled mobile.

Among all the families of maps, one of the best known is that of quadrangulations, because of the famous bijection of Cori & Vauquelin [10] between planar rooted quadrangulations and well labeled trees, and its description by Schaeffer (which can be found in [28, 9, 22] ). Informally, well labeled trees are planar trees in which nodes are labeled by integers subject to a positivity constraint. Using this bijection:

$\bullet$  Chassaing & Schaeffer [9] established that the longest distance to the root in uniform rooted quadrangulation with $n$  faces divided by $cn\sigma (\mathbf{p}{)}^{1/4}$  converges in law to the range of the Brownian snake (with lifetime process the normalized Brownian excursion), $\bullet$  Chassaing & Durhuus [8] showed that unscaled uniform rooted quadrangulation with $n$  faces converges locally to a measure on infinite quadrangulations, $\bullet$  Marckert & Mokkadem [22] give a description of quadrangulations in term of the gluing of two trees, and show that these trees converge when suitably normalized as $n$  goes to $\infty$  . They introduced the notion of Brownian map, and show that under a certain topology, rescaled quadrangulations converge weakly to the Brownian map.

We refer also to Angel & Schramm [3] who proved an analogous result as Chassaing & Durhuus for rooted triangulations, but their proof is based on a Markovian construction of triangulations rather than bijective methods.

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.2 Boltzmann laws on planar maps

We denote by $\mathcal{ℳ}$  the set of bipartite pointed rooted planar maps with at least one edge, and by $\mathcal{ℳ}\sigma (\mathbf{p}{)}_n^F$  , $\mathcal{ℳ}\sigma (\mathbf{p}{)}_k^S$  and ${\mathcal{ℳ}}_{n,k}$  the subsets of $\mathcal{ℳ}$  consisting of maps with $n$  faces, $k$  vertices, and both $n$  faces and $k$  vertices, respectively. It is natural in our setting to add a cemetery point in $\mathcal{ℳ}$  , which we call $†$  , and which we understand as a “map with no face”. In the sequel, unless otherwise specified, the term map is understood for “pointed, rooted, bipartite planar map”, and we will simply write $\mathbf{m}$  as a shorthand for $(\mathbf{m},u,vw)$  .

The goal of the present paper is to give asymptotic results generalizing [9] and [22] to several other “Boltzmann laws” on bipartite maps conditioned to have a large number of faces or vertices.

Let $\mathbf{q}=(q_i,i\ge 1)$  be a sequence of non-negative weights non identically zero. Consider the $\sigma$  -finite measure $W_{\mathbf{q}}$  on $\mathcal{ℳ}$  that assigns to each map $\mathbf{m}\in \mathcal{ℳ}$  a weight $q_i$  per face of degree $2i$  :

$$\begin{array}{c}{W}_{\mathbf{q}}(\mathbf{m})={\prod }_{f\in F(\mathbf{m})}{q}_{deg\left(f\right)/2}\end{array}$$

(1)

where $F(\mathbf{m})$  denotes the set of faces of $\mathbf{m}$  , and where $deg\left(f\right)$  is the degree of the face $f$  . By convention, we set $W_{\mathbf{q}}(†)=1$  . This multiplicative form is reminiscent of the measures associated with the so-called simply generated trees, which is of the form $w\left(t\right)={\prod }_{u\in t}{q}_{c_u\left(t\right)}$  for any tree $t$  , where $c_t\left(u\right)$  is the number of children of $u$  , and where $(q_i{)}_i$  is a sequence of non-negative numbers (Aldous [1,p.27-28] ). We will be interested in probability measures associated with $W_{\mathbf{q}}$  in the following way. If $Z_{\mathbf{q},n}\sigma (\mathbf{p}{)}^F:=W_{\mathbf{q}}(\mathcal{ℳ}\sigma (\mathbf{p}{)}_n^F)\in (0,+\infty )$  , we can consider the conditional probability distribution on $\mathcal{ℳ}\sigma (\mathbf{p}{)}_n^F$  $$P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F(\cdot )=\frac{W_{\mathbf{q}}(\cdot \cap \mathcal{ℳ}\sigma (\mathbf{p}{)}_n^F)}{Z_{\mathbf{q},n}\sigma (\mathbf{p}{)}^F}.$$  Similarly, we can consider the probability distribution $P\sigma (\mathbf{p}{)}_{\mathbf{q},k}^S=W_{\mathbf{q}}(\cdot \cap \mathcal{ℳ}\sigma (\mathbf{p}{)}_k^S)/Z\sigma (\mathbf{p}{)}_{\mathbf{q},k}^S$  as soon as $Z\sigma (\mathbf{p}{)}_{\mathbf{q},k}^S=W_{\mathbf{q}}(\mathcal{ℳ}\sigma (\mathbf{p}{)}_k^S)\in (0,+\infty )$  . If moreover $Z_{\mathbf{q}}=W_{\mathbf{q}}(\mathcal{ℳ})$  is finite, we can consider the Boltzmann probability distribution on $\mathcal{ℳ}$  defined by $$P_{\mathbf{q}}(\cdot )=\frac{W_{\mathbf{q}}(\cdot )}{Z_{\mathbf{q}}}.$$  We will see that when certain “criticality” hypotheses on $\mathbf{q}$  are satisfied (Definition  1 ), under $P\sigma (\mathbf{p}{)}_{\mathbf{q},k}^S$  or $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  several features of random maps satisfy an invariance principle. This is summed up in Sect.  4.4 by saying that such rescaled random maps converge to an object called the Brownian map, hence obtaining a generalization of [22] . In particular, we are able to give asymptotic results for the diameter and the profile of a large class of random maps, hence encompassing (in principle) results by Chassaing and Schaeffer [9] , which are obtained in the quadrangulation case, where $\mathbf{q}={\delta }_2$  . We also mention that it would be natural to look for asymptotic behavior of maps under the conditioned measure $P_{\mathbf{q}}(\cdot |M\in {\mathcal{ℳ}}_{n,k})$  , but we were not able to rule this out by our methods.

Remarks. $\bullet$  The reason why “in principle” is that Chassaing and Schaeffer work in the slightly different context of rooted maps, but which are not pointed. Considering these objects would lead us to extra non-trivial technicalities. Typically, pointing and rooting allows to consider freely labeled mobiles below, while simple rooting lead to considerations on labeled mobiles with a positivity condition. In a recent paper, Le Gall [17] has shown an invariance principle on labeled trees conditioned to be positive. His results imply the convergence of rescaled uniform rooted 1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS quadrangulations to the Brownian map.

$\bullet$  Notice that the law of $\#F\left(M\right)$  under $P_{\mathbf{q}}$  always charges every point of ${\mathbb{Z}}_{+}$  , so that $Z\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  is always non-zero. However, this is not always true for $Z\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  . More precisely, if we write the support of $\mathbf{q}$  as $({\kappa }_i,i\ge 1)$  , then the maps $\mathbf{m}$  that are charged by $P_{\mathbf{q}}$  are exactly those having $n_i$  faces of degree $2{\kappa }_i$  for some integer sequence $(n_i,i\ge 1)$  with finite support. By Euler’s formula, such maps have $2+{\sum }_i{n}_i({\kappa }_i-1)$  vertices, so that $\#S(\mathbf{m})$  has a maximal span $\mathsf{h}$  which is the g.c.d. of $({\kappa }_i-1,i\ge 1)$  . In the sequel, when conditioning on $\#S(\mathbf{m})=n$  we will therefore always tacitly suppose that $n$  is chosen among the admissible values.

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.3 Labeled mobiles, and the BdFG bijection

Consider the infinite regular planar tree $$T_{\infty }={\bigcup }_{n\ge 0}\mathbb{N}\sigma (\mathbf{p}{)}^n,$$  (by convention $\mathbb{N}\sigma (\mathbf{p}{)}^0=\{\mathbb{\varnothing }\}$  ). For $u=(u_1,\dots ,u_n),v=(v_1,\dots ,v_m)\in T_{\infty }$  , we let $uv=(u_1,\dots ,u_n,v_1,\dots ,v_m)$  be the concatenation of the words $u$  and $v$  . Recall that a planar tree $\mathbf{t}$  is a subset of $T_{\infty }$  containing the root-vertex $\mathbb{\varnothing }$  , and such that if $ui\in \mathbf{t}$  , then $uj\in \mathbf{t}$  for all $1\le j\le i$  , and $u\in \mathbf{t}$  . Seen as a map, a tree is canonically rooted on the oriented edge $(\mathbb{\varnothing },1)$  where $1$  is the left most child of $\mathbb{\varnothing }$  . We denote by $\mathbb{T}$  the set of planar trees. We let $c_u(\mathbf{t})=max\{i:ui\in \mathbf{t}\}$  be the number of children of $u$  .

Every tree has a canonical bipartite coloration of its vertices, which can be of two kinds $\circ$  and $\bullet$  , and such that the root-vertex is a $\circ$  . We let $\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }$  and $\mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }$  be the sets of vertices colored $\circ$  and $\bullet$  in a tree $\mathbf{t}$  , respectively. For reason that will appear later, we call such a colored tree, a mobile. In a rooted mobile, the root is canonically assimilated to an unoriented edge, since it naturally inherits an orientation from the fact that the root vertex is a $\circ$  .

A labeled mobile is a pair $(\mathbf{t},\ell )$  where $\mathbf{t}$  is a mobile and $\ell :\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }\to \mathbb{Z}$  is a function satisfying the following constraint. Suppose $v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }$  has father $v_0\in \mathbf{t}\sigma (\mathbf{p}{)}^{\circ }$  , and let $v_0,v_1,v_2\dots ,v_k$  be the neighboring vertices of $\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }$  , arranged so that $v_{i+1}$  is the vertex following $v_i$  when going clockwise around $v$  , with the convention that $k+1=0$  . Then $\ell$  satisfies

$$\begin{array}{c}\ell \left(v_{i+1}\right)\ge \ell \left(v_i\right)-1.\end{array}$$

(2)

We let $N\left(k\right)$  be the number of possible differences $(\ell (v_i)-\ell (v_{i+1}),1\le i\le k)$  that respect this constraint. By adding $2$  to each of the numbers $\ell \left(v_i\right)-\ell \left(v_{i+1}\right)$  , one sees that this is the same as the number of compositions of $2k$  in $k$  positive parts. Hence

$$\begin{array}{c}N\left(k\right)=\left(\genfrac{}{}{0ex}{}{2k-1}{k-1}\right).\end{array}$$

(3)

When dealing with rooted mobiles, we will always suppose, unless otherwise mentioned, that the root vertex has label $1$  . We let $\mathcal{W}$  be the set of rooted labeled mobiles, and ${\mathcal{W}}_{n,k}$  be the subset of those satisfying $|\mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }|=n$  and $|\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }|=k$  . The main tool for studying the laws introduced above is the bijection of Bouttier, Di Francesco & Guitter [7] generalizing that of Schaeffer.

Theorem 1 (Bouttier, Di Francesco & Guitter [7] ) There exists a one-to-one correspondence $\Phi$  between $\mathcal{ℳ}$  and $\mathcal{W}$  with the following properties. It maps $†$  to the tree $\{\mathbb{\varnothing }\}$  with label 1, and for any $n\ge 1$  and $k\ge 2$  , the restriction of $\Phi$  to ${\mathcal{ℳ}}_{n,k}$  is a bijection onto ${\mathcal{W}}_{n,k-1}$  . Next, for $\mathbf{m}=(\mathbf{m},u,vw)\in \mathcal{ℳ}\backslash \{†\}$  , letting $(\mathbf{t},\ell )=\Phi (\mathbf{m})$  , $■$  each vertex $\sigma$  of $\mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }$  corresponds to a face $f$  of $\mathbf{m}$  , and the (total) degree of $\sigma$  is half the degree of $f$  , $■$  each vertex $x\ne u$  of $\mathbf{m}$  corresponds to a vertex $\phi \left(x\right)$  of $\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }$  , $■$  the graph distance of any vertex $x\ne u$  of $\mathbf{m}$  to $u$  is equal to $1+\ell \left(\phi \right(x\left)\right)-{inf}_{\sigma \in \mathbf{t}\sigma (\mathbf{p}{)}^{\circ }}\ell \left(\sigma \right)$  .

We describe the bijection $\Phi$  in Section  4.1 and show that it has some useful additional properties.

Among these is the possibility to generalize the representation of quadrangulation as the gluing of two trees (given in [22] ) to bipartite maps.

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.4 Projection of $P_{\mathbf{q}},P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F,P\sigma (\mathbf{p}{)}_{\mathbf{q},k}^S$  on mobiles

Now suppose that $M$  is a $P_{\mathbf{q}}$  -distributed random planar map. Then by Theorem  1 , letting $(T,L)=\Phi \left(M\right)$  be the associated labeled random mobile, we can write, for any fixed labeled mobile $(\mathbf{t},\ell )$  , 1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

$$\begin{array}{ccc}{P}_{\mathbf{q}}(\Phi (M)=(\mathbf{t},\ell \left)\right)& =& \frac{{\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }}{q}_{c_v(\mathbf{t})+1}}{Z_{\mathbf{q}}}\end{array}$$

$$\begin{array}{ccc}& =& \left({\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\circ }}\frac{1}{Z_{\mathbf{q}}}\right)\left({\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }}{Z}_{\mathbf{q}}\sigma (\mathbf{p}{)}^{c_v(\mathbf{t})}{q}_{c_v(\mathbf{t})+1}N(c_v(\mathbf{t})+1)\right)\left({\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }}\frac{1}{N\left(c_v\right(\mathbf{t})+1)}\right),\end{array}$$

where $c_v(\mathbf{t})$  denotes the number of children of the vertex $v$  in $\mathbf{t}$  , and where we have used ${\sum }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }}{c}_v(\mathbf{t})=|\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }|-1$  for any mobile $\mathbf{t}$  . Now, by definition of $W_{\mathbf{q}}$  and the properties of the BdFG bijection, letting $(T,L)=\Phi \left(M\right)$  , we may rephrase this by saying that under $P_{\mathbf{q}}$  , the mobile $T$  has distribution $$P_{\mathbf{q}}(T=\mathbf{t})=\left({\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\circ }}\frac{1}{Z_{\mathbf{q}}}\right)\left({\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }}{Z}_{\mathbf{q}}\sigma (\mathbf{p}{)}^{c_v(\mathbf{t})}{q}_{c_v(\mathbf{t})+1}N(c_v(\mathbf{t})+1)\right),$$  and the labeling $L$  of the mobile $T$  is uniform among all possible conditionally on $T$  . More precisely, given $T$  , for each $v\in T\sigma (\mathbf{p}{)}^{\bullet }$  with father $v_0$  and children $v_1,\dots ,v_k$  , the sequence of differences $\left(L\right(v_i+1)-L(v_i),1\le i\le k)$  is uniform among the $N(k+1)$  possible, independently over $v$  ’s.

Now, the finiteness of the measure $P_{\mathbf{q}}$  plainly entails that

$$\begin{array}{c}f\left(x\right)={\sum }_{i\ge 0}x\sigma (\mathbf{p}{)}^i{q}_{i+1}N(i+1)\end{array}$$

(4)

is finite at $x=Z_{\mathbf{q}}$  , so we can define a probability measure

$$\begin{array}{c}\mu {\bullet }_{\mathbf{q}}\left(k\right)=\frac{Z_{\mathbf{q}}\sigma (\mathbf{p}{)}^{k}N(k+1)q_{k+1}}{f\left(Z_{\mathbf{q}}\right)},k\ge 0,\end{array}$$

(5)

and write

$$\begin{array}{c}{P}_{\mathbf{q}}(T=\mathbf{t})={\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\circ }}\mu {\circ }_{\mathbf{q}}\left(c_v\right(\mathbf{t}\left)\right){\prod }_{v\in \mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }}\mu {\bullet }_{\mathbf{q}}\left(c_v\right(\mathbf{t}\left)\right),\end{array}$$

(6)

where $$\mu {\circ }_{\mathbf{q}}\left(k\right):=Z_{\mathbf{q}}\sigma (\mathbf{p}{)}^{-1}f(Z_{\mathbf{q}}\left)\sigma \right(\mathbf{p}{)}^k,k\ge 0.$$  But it is easy that this measure must itself be a probability measure since $P_{\mathbf{q}}$  is one. Therefore, we get that $f\left(Z_{\mathbf{q}}\right)=1-Z_{\mathbf{q}}\sigma (\mathbf{p}{)}^{-1}$  , and $\mu {\circ }_{\mathbf{q}}$  is the geometric distribution with parameter $1/Z_{\mathbf{q}}$  , Therefore, we see that the study of Boltzmann random planar maps boils down to that of certain two-type Galton-Watson trees (see Sect.  2 ), that could be called “bi-generated trees” in our context, with a certain uniform labeling on their vertices. This and the forthcoming discussion in Sect.  2 motivates calling a weight sequence $\mathbf{q}$  critical if the associated two-type Galton-Watson process is, i.e. if $m_{\circ }{m}_{\bullet }=1$  , where $m_{\bullet },m_{\circ }$  are the respective means of $\mu {\bullet }_{\mathbf{q}},\mu {\circ }_{\mathbf{q}}$  .

This is easily equivalent to $m_{\bullet }=(Z_{\mathbf{q}}-1)\sigma (\mathbf{p}{)}^{-1}$  , and by ( 5 ) this can be rewritten as follows.

Definition 1 A weight $\mathbf{q}$  such that $Z_{\mathbf{q}}<\infty$  is said to be critical if

$$\begin{array}{c}{Z}_{\mathbf{q}}\sigma (\mathbf{p}{)}^2{f}_l^{\prime }(Z_{\mathbf{q}})=1,1\mathit{I}\mathit{N}\mathit{T}\mathit{R}\mathit{O}\mathit{D}\mathit{U}\mathit{C}\mathit{T}\mathit{I}\mathit{O}\mathit{N}\mathit{,}\mathit{M}\mathit{O}\mathit{T}\mathit{I}\mathit{V}\mathit{A}\mathit{T}\mathit{I}\mathit{O}\mathit{N}\mathit{S}\mathit{A}\mathit{N}\mathit{D}\mathit{M}\mathit{A}\mathit{I}\mathit{N}\mathit{R}\mathit{E}\mathit{S}\mathit{U}\mathit{L}\mathit{T}\mathit{S}\end{array}$$

(7)

where $f_l^{\prime }$  is the left-derivative of $f$  . Equivalently, $\mathbf{q}$  is critical if and only if the graphs of $x\mapsto f\left(x\right)$  and $x\mapsto 1-1/x$  are tangent at $x=Z_{\mathbf{q}}$  . We say that $\mathbf{q}$  is regular critical if moreover the radius of convergence of $f$  is $>Z_{\mathbf{q}}$  , i.e. if $\mu {\bullet }_{\mathbf{q}}$  has small exponential moments.

Our main results dealing with maps (Theorems  5 ,  6 ,  7 ) are proved under the assumption of regular criticality for the weight sequence. Let us however discuss more specifically on conditioned probability measures. It is straightforward from ( 1 ) that

Lemma 1 Fix $n,k$  . For any $\alpha >0$  such that $Z\sigma (\mathbf{p}{)}_{\alpha \mathbf{q},n}^F<\infty$  , the conditional laws $P\sigma (\mathbf{p}{)}_{\alpha \mathbf{q},n}^F$  are all equal to a single common distribution. Similarly, for any $\beta >0$  such that $Z\sigma (\mathbf{p}{)}_{\left(\beta \sigma \right(\mathbf{p}{)}^{i-1}{q}_i,i\ge 1),k}^S<\infty$  , the conditional laws $P\sigma (\mathbf{p}{)}_{\left(\beta \sigma \right(\mathbf{p}{)}^{i-1}{q}_i,i\ge 1),k}^S$  share a common value.

Therefore, when we are concerned with conditional laws $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F,P\sigma (\mathbf{p}{)}_{\mathbf{q},k}^S$  , we will suppose that there exists some $\alpha >0$  such that $Z_{\alpha \mathbf{q}}<\infty$  and $\alpha \mathbf{q}$  is regular critical, respectively that there exists some $\beta >0$  such that $Z_{\left(\beta \sigma \right(\mathbf{p}{)}^{i-1}{q}_i,i\ge 1)}<\infty$  and $\left(\beta \sigma \right(\mathbf{p}{)}^{i-1}{q}_i,i\ge 1)$  is critical, and focus on this critical weight. This changes $f$  respectively to $\alpha f$  and $f(\beta \cdot )$  . It is also true that conditioning both on the number of faces and vertices is insensitive to termwise multiplication of $\mathbf{q}$  by $\left(\alpha \beta \sigma \right(\mathbf{p}{)}^{i-1},i\ge 1)$  , so this would lead to finding a curve of $(\alpha ,\beta )$  ’s such that $\left(\alpha \beta \sigma \right(\mathbf{p}{)}^{i-1}{q}_i,i\ge 1)$  is critical. We do not concentrate on this last point, as our methods are unefficient in conditioning on both these data.

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.5 Overview of results and organization of the paper

It is therefore natural from ( 6 ), and the conditional law of the labeling $L$  discussed above, to look for a general invariance principle for labeled two-type Galton-Watson trees together with a branching spatial motion. We call such random labeled trees “two-type discrete snakes”. The trees we are interested in have an anti-diagonal mean matrix, i.e. particles of a type give birth exclusively to particles of the other type. In Section  3 , we show such an invariance principle under fairly general hypotheses, namely that the (critical) offspring distribution has small exponential moments and that the spatial displacement between vertices, which need not have the same law for each type, and may depend on the number $k$  of children of the current vertex, has moments of order $4+\varepsilon$  that vary at most polynomially with $k$  . Under these hypotheses, it is shown in Corollary  3 and Theorem  4 that critical rescaled discrete snakes converge to the Brownian snake (see [11] and definitions below) driven by a Brownian excursion distributed according to the Ito excursion measure, while conditioned discrete snakes converge to the Brownian snake driven by a standard Brownian excursion. The invariance principle is proved in Sections  2 and  3 and is interesting in its own right. It uses an ancestral decomposition of trees (Sect.  2.4 ) with a marked vertex, that was considered in a different form and context in [15] . This invariance principle improves over past literature [19, 13, 14] in two ways:

$\bullet$  First, it allows two types instead of only one, so that Theorem  2 below showing that the unlabeled critical two-type trees with finite variance converge to the Brownian continuum random tree generalizes previous results [2, 19, 11] , although we expect that the assumption of small exponential moments could be relaxed to a plain second moment condition. See [23] for the general irreducible multitype case.

$\bullet$  Second, it allows the spatial displacement to depend on the local structure of the tree, namely of the type and the number of neighbors of the different vertices, which seems not to have been considered before. Except for the exponential moment assumptions, we expect that the hypotheses of the invariance principle are close to the best possible, see [14] .

We specialize the invariance principle to the distributions $\mu {\circ }_{\mathbf{q}},\mu {\bullet }_{\mathbf{q}}$  above and the particular labeling of mobiles associated with Boltzmann random maps in Theorem  5 , Sect.  4.2 . We use this result in Sect.  4.4 to show that such random maps converge once properly rescaled to the Brownian map. As a corollary, we obtain for example the following generalization of the result of [9] . Let $N(de)$  be the Ito measure of the standard reflected Brownian motion, i.e. $N$  is supported by continuous functions on some compact subset $[0,\zeta ]$  of ${\mathbb{R}}_{+}$  with $\zeta >0$  , with zero value at the boundary and positive on $(0,\zeta )$  . We let $\mathbb{N}(de,dr)$  be the Ito measure of the head of the associated Brownian snake, i.e. with first marginal $N$  and such that given $e$  , the second marginal is the law of a centered Gaussian process with covariance $cov(r_s,r_{s^{\prime }})={min}_{u\in [s\wedge s^{\prime },s\vee s^{\prime }]}{e}_u$  . Similarly, we let $\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}(de,dr)$  be the law of the head of the snake driven by a standard Brownian excursion, i.e. the same distribution as above but where $N(de)$  is replaced by the law $N\sigma (\mathbf{p}{)}^{\left(1\right)}(de)$  of the standard Brownian excursion with unit duration.

Now suppose that $\mathbf{q}$  is a regular critical weight sequence, and let

$$\begin{array}{c}{\rho }_{\mathbf{q}}=2+Z_{\mathbf{q}}\sigma (\mathbf{p}{)}^3{f}^{\prime \prime }(Z_{\mathbf{q}}).\end{array}$$

(8)

Let $\Re (\mathbf{m})$  be the radius of $\mathbf{m}\in \mathcal{ℳ}$  , i.e. the maximal distance of a vertex to the distinguished point. Then

Corollary 1 (i) For any $a>0$  and under $P_{\mathbf{q}}$  , the law of the rescaled radius $\Re \left(M\right)/n$  given $\Re \left(M\right)>an$  converges weakly to $$\mathbb{N}\left(\left(\frac{4{\rho }_{\mathbf{q}}}{9Z_{\mathbf{q}}}\right)\sigma (\mathbf{p}{)}^{1/4}\Delta \in \cdot |\left(\frac{4{\rho }_{\mathbf{q}}}{9Z_{\mathbf{q}}}\right)\sigma (\mathbf{p}{)}^{1/4}\Delta >a\right),$$  where $\Delta =maxr-minr$  is the diameter of the Brownian snake 1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS (ii) As $n\to \infty$  , under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  , $$\frac{\Re \left(M\right)}{n\sigma (\mathbf{p}{)}^{1/4}}----\to weaklyn\to \infty \left(\frac{4{\rho }_{\mathbf{q}}}{9(Z_{\mathbf{q}}-1)}\right)\sigma (\mathbf{p}{)}^{1/4}\Delta \text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}.$$  (iii) As $n\to \infty$  , under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  , $$\frac{\Re \left(M\right)}{n\sigma (\mathbf{p}{)}^{1/4}}----\to weaklyn\to \infty \left(\frac{4{\rho }_{\mathbf{q}}}{9}\right)\sigma (\mathbf{p}{)}^{1/4}\Delta \text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}.$$ 

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.6 Two examples

We conclude this section by giving explicitly the constants mentioned above in two particular cases.

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.6.1 $2\kappa$  -angulations

Let $\kappa \ge 2$  be an integer, and consider the case when $\mathbf{q}=\alpha {\delta }_{\kappa }$  , for some constant $\alpha >0$  . The resulting distributions are the Boltzmann distributions on the set of maps with face degree fixed and equal to $2\kappa$  , as in [8] in the case $\kappa =2$  of quadrangulations (such distributions also appear in [4] for triangulations). Then $f\left(x\right)=\alpha N\left(\kappa \right)x\sigma (\mathbf{p}{)}^{\kappa -1}$  , and the equations $f\left(z\right)=1-1/z$  and $z\sigma (\mathbf{p}{)}^2{f}^{\prime }(z)=1$  are solved by $Z=\kappa /(\kappa -1)$  and determine a unique value for $\alpha$  . We thus have obtained the value ${\alpha }_{\kappa }$  of $\alpha$  , which makes $\mathbf{q}$  critical, i.e. $${\alpha }_{\kappa }=\frac{(\kappa -1)\sigma (\mathbf{p}{)}^{\kappa -1}}{\kappa \sigma (\mathbf{p}{)}^{\kappa }N(\kappa )},$$  while the partition function is $Z_{{\alpha }_{\kappa }{\delta }_{\kappa }}=\kappa /(\kappa -1)$  . Obviously, ${\alpha }_{\kappa }$  is also the largest allowed value for $\alpha >0$  that makes $W_{\mathbf{q}}$  a finite measure, i.e. so that $f\left(z\right)=1-1/z$  admits a solution.

In particular we check ${\alpha }_2=1/12,Z_{{\alpha }_2{\delta }_2}=2$  , as in [8] , and ${\rho }_{\mathbf{q}}=\kappa$  . Notice also that the constant appearing in (ii), Corollary  1 is $(8/9)\sigma (\mathbf{p}{)}^{1/4}$  in this case, as in [9] . Notice that conditioning on the number of vertices is equivalent in this case thanks to Euler’s formula (up to trivial renormalization constants).

1 INTRODUCTION, MOTIVATIONS AND MAIN RESULTS

1.6.2 $q_i=\beta \sigma (\mathbf{p}{)}^i$ 

Let $\beta >0$  , and let $q_i=\beta \sigma (\mathbf{p}{)}^i$  , so that the weight of a map $\mathbf{m}$  is $\beta \sigma (\mathbf{p}{)}^{\#A(\mathbf{m})}$  , where $A(\mathbf{m})$  is the set of edges of $\mathbf{m}$  . In this case, $$f\left(x\right)={\sum }_{i\ge 0}x\sigma (\mathbf{p}{)}^i\beta \sigma (\mathbf{p}{)}^{i+1}N(i+1)=\frac{2\beta }{\sqrt{1-4\beta x}\left(1+\sqrt{1-4\beta x}\right)}$$  is defined for $x<\left(4\beta \right)\sigma (\mathbf{p}{)}^{-1}$  , and the only interesting cases in our setting are for $\beta <1/4$  .

Now, the equation $f\left(z\right)=1-1/z$  has two real solutions $>1$  when $\beta <1/8$  , and these are given by $$\frac{1-\sqrt{1-8\beta }+4\beta }{8\beta }\text{and}\frac{1+\sqrt{1-8\beta }+4\beta }{8\beta }.$$  These two solutions merge into a unique one at $\beta =1/8$  , which is of course the value making $\mathbf{q}$  critical, as can be double-checked by solving $z\sigma (\mathbf{p}{)}^2{f}^{\prime }(z)=1$  , whose solution is $3/\left(16\beta \right)$  . This gives $Z_{\mathbf{q}}=3/2$  in the critical case, while ${\rho }_{\mathbf{q}}=27/4$  . The conditional version with respect to the number of vertices can be seen as the finite measure putting weight $8\sigma (\mathbf{p}{)}^{-\#A\left(m\right)}$  on each element $m$  of $\mathcal{ℳ}\sigma (\mathbf{p}{)}_n^S$  (i.e. $\mathbf{q}=8\sigma (\mathbf{p}{)}^{-1}1$  ) conditioned with respect to the number of vertices ; notice that in this case a conditional version with respect to the number of faces does not exist since $Z\sigma (\mathbf{p}{)}_{\alpha 1,n}^F=\infty$  for all $n,\alpha >0$  .

Figure 2 : Example  1.6.1 : drawing $f$  for $\alpha =1/18,1/12,1/8$  and $x\mapsto 1-1/x$  (dashed) in the case $\kappa =2$  of quadrangulations. Example  1.6.2 : drawing $f$  for $\beta =1/7,1/8,1/10$  and $x\mapsto 1-1/x$  (dashed)

2 CRITICAL TWO-TYPE DISCRETE SNAKES

2 Critical two-type discrete snakes

2 CRITICAL TWO-TYPE DISCRETE SNAKES

2.1 Planar trees

We begin with some generalities on planar trees and forests. Recall the definitions of Sect.  1 .

We let $\left|u\right|$  be the length of the word $u\in T_{\infty }$  , which is also the height (graph distance to the root) of $u$  if considered as a vertex of some tree. For $\mathbf{t}$  a tree and $n\ge 0$  , let $\mathbf{t}{|}_n=\{u\in \mathbf{t}:|u|\le n\}$  be the restriction of $\mathbf{t}$  to the $n$  first generations. For $u\in \mathbf{t}$  we let ${\mathbf{t}}_u=\{v\in T_{\infty }:uv\in \mathbf{t}\}$  be the fringe subtree of $\mathbf{t}$  rooted at $u$  , and $[\mathbf{t}{]}_u=\mathbf{t}\backslash \{uv:v\in {\mathbf{t}}_u\backslash \{\mathbb{\varnothing }\}\}$  the pruned subtree. For $u=i_1\dots i_n\in \mathbf{t}$  , we let $u_j=i_1\dots i_j$  and $\left[\right[\mathbb{\varnothing },u\left]\right]=\{\mathbb{\varnothing },u_1,\dots ,u_n\}$  be the ancestral line of $u$  back to the root.

The depth-first order on a planar tree is the order relation $\prec$  induced by the lexicographical order. We let $u\left(k\right)$  be the $k$  -th vertex in depth-first order. We also define the depth-first traversal, or contour order of a tree $\mathbf{t}$  with $n$  edges as a function: $$F_{\mathbf{t}}:\{0,...,2n\}\to \{\text{vertices of}\mathbf{t}\},$$  which we regard as a walk around $\mathbf{t}$  , as follows: $F_{\mathbf{t}}\left(0\right)=\mathbb{\varnothing }$  , and given $F_{\mathbf{t}}\left(i\right)=z$  , choose, if possible, and according to the depth-first order the smallest child $w$  of $z$  which has not already been visited, and set $F_{\mathbf{t}}(i+1)=w$  . If not possible, let $F_{\mathbf{t}}(i+1)$  be the father of $z$  .

A forest is a finite or infinite sequence of trees $\mathbf{f}=({\mathbf{t}}_1,{\mathbf{t}}_2,\dots )$  . The depth-first order on $\mathbf{f}$  is naturally defined as the linear order matching both the depth-first order on each ${\mathbf{t}}_i$  and the order in which the ${\mathbf{t}}_i$  appear. We define similarly as above $\mathbf{f}{|}_n,{\mathbf{f}}_u,[\mathbf{f}{]}_u,u(k)$  for a forest $\mathbf{f}$  .

Finally, for a forest $\mathbf{f}=({\mathbf{t}}_1,{\mathbf{t}}_2,\dots )$  , we let $H\sigma (\mathbf{p}{)}_k^{\mathbf{f}}=|u\left(k\right)|$  and $\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{f}}(k)=|F_{\mathbf{f}}\left(k\right)|$  , and define the height process $\left(H\sigma \right(\mathbf{p}{)}_s^{\mathbf{f}},s\ge 0)$  and the contour process $\left(\widehat{H}\sigma \right(\mathbf{p}{)}_s^{\mathbf{f}},s\ge 0)$  by interpolating linearly between integer abscissa. We also let $\Lambda \sigma (\mathbf{p}{)}_k^{\mathbf{f}}=max\{i\ge 1:u\left(k\right)\in {\mathbf{t}}_i\}$  and $\widehat{\Lambda }\sigma (\mathbf{p}{)}_k^{\mathbf{f}}=max\{i\ge 1:F\sigma (\mathbf{p}{)}^{\mathbf{f}}(k)\in {\mathbf{t}}_i\}$  . See Fig.  3 .

Figure 3 : A forest, its height process, and its contour process. On this example $\Lambda \sigma (\mathbf{p}{)}_7^{\mathbf{f}}=3$  and $\widehat{\Lambda }\sigma (\mathbf{p}{)}_7^{\mathbf{f}}=1$ 

2 CRITICAL TWO-TYPE DISCRETE SNAKES

2.2 Prerequisites on monotype Galton-Watson trees

For $\mu$  a probability measure on the set of nonnegative integers, we denote by $P\sigma (\mathbf{p}{)}^{\mu }$  the law of a single type GW tree with offspring distribution $\mu$  . We denote by $(H)$  the conditions that $\mu$  is non-degenerate, critical and has small exponential moments, namely: $$(H):=\{\begin{array}{c}\mu \left(0\right)+\mu \left(1\right)\ne 1\\ {\sum }_{k\ge 0}k\mu \left(k\right)=1\\ \text{there exists}a>0\text{s.t.}{\sum }_{k\ge 0}e\sigma (\mathbf{p}{)}^{ak}\mu (k)<+\infty .\end{array}$$  We denote by $P\sigma (\mathbf{p}{)}_r^{\mu }$  the law of a forest with $r\in {\mathbb{Z}}_{+}\cup \{\infty \}$  trees, in which the $r$  trees are $P\sigma (\mathbf{p}{)}^{\mu }$  distributed and independent.

We begin by giving some results on monotype forests that will be crucial for further study.

The following result improves over known tightness results for the rescaled height process of a Galton-Watson forest. Its proof as well as those of Lemma  2 and  3 are postponed to the Appendix at the end of the paper.

Proposition 1 Suppose $(H)$  . Under $P\sigma (\mathbf{p}{)}_{\infty }^{\mu }$  , for every $A>0,\alpha \in (0,1/2)$  , the $\alpha$  -Holder norm of $\left(n\sigma \right(\mathbf{p}{)}^{-1/2}H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}},0\le s\le A)$  is uniformly tight in $n$  , namely, for every $\varepsilon >0$  there exists $C>0$  such that $${sup}_{n\in \mathbb{N}}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left({sup}_{0\le s\ne t\le A}\frac{\left|H\sigma \right(\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-H\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}|}{\sqrt{n}|s-t|\sigma (\mathbf{p}{)}^{\alpha }}>C\right)\le \varepsilon .$$  Moreover, the same conclusion holds for the contour process $\widehat{H}$  .

Notice that the conditioned analog of this proposition, i.e. under the probability laws $P\sigma (\mathbf{p}{)}^{\mu }(\cdot \left|\right|T|=n)$  instead, and in the case of the contour process, is a consequence of the work of Gittenberger [13] .

In the unconditioned case, to the best of our knowledge, Proposition  1 has not been shown before.

Our proof is partly inspired by [11,Theorem1.4.4] , which is a kind of continuous counterpart of the present proposition.

The two following lemmæ will allow to give bounds on the maximal vertex-height and the number of trees visited before the $An$  -th vertex of a forest in depth-first order.

Lemma 2 Let $\mu$  be a distribution satisfying $(H)$  . In a $P\sigma (\mathbf{p}{)}_{\infty }^{\mu }$  -forest, for every $A>0,\eta >0$  , there exists $\varepsilon >0$  such that for $n$  large enough, $$P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left(max\left\{\right|u|,u\prec u(\left[An\right]\left)\right\}\ge n\sigma (\mathbf{p}{)}^{1/2+\eta }\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon }).$$ 

Lemma 3 Let $\mu$  be a distribution satisfying $(H)$  and $\mathcal{ℱ}$  be a $\mu$  -forest with $n\sigma (\mathbf{p}{)}^{1/2+\eta }$  trees.

For any $\eta >0$  and $A>0$  , there exists $\varepsilon >0$  , such that for $n$  large enough $$P\sigma (\mathbf{p}{)}_{\left[n\sigma \right(\mathbf{p}{)}^{1/2+\eta }]}^{\mu }(|\mathcal{ℱ}|\le An)<exp(-n\sigma (\mathbf{p}{)}^{\varepsilon })$$ 

We finish this section by stating Aldous-Le Gall’s theorems for convergence of the height process for conditioned tree (see also [19] ), and for forests, that can be found respectively in [2, 11] .

Proposition 2 Under hypotheses $(H)$  :

(i) Under $P\sigma (\mathbf{p}{)}_{\infty }^{\mu }$  , $${\left(\frac{H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{\sqrt{n}},\frac{\Lambda \sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{\sqrt{n}}\right)}_{s\ge 0}----\to weaklyn\to \infty {\left(\frac{2}{\sigma }\left|B_s\right|,\sigma L\sigma (\mathbf{p}{)}_s^0\right)}_{s\ge 0},2\mathit{C}\mathit{R}\mathit{I}\mathit{T}\mathit{I}\mathit{C}\mathit{A}\mathit{L}\mathit{T}\mathit{W}\mathit{O}\mathit{-}\mathit{T}\mathit{Y}\mathit{P}\mathit{E}\mathit{D}\mathit{I}\mathit{S}\mathit{C}\mathit{R}\mathit{E}\mathit{T}\mathit{E}\mathit{S}\mathit{N}\mathit{A}\mathit{K}\mathit{E}\mathit{S}$$  for the uniform topology on compact subsets of $[0,\infty )$  , where $\sigma \sigma (\mathbf{p}{)}^2$  is the variance of $\mu$  and $B$  is a standard Brownian motion with local time process at $0$  given by $\left(L\sigma \right(\mathbf{p}{)}_s^0,s\ge 0)$  (which is normalized to be the density at $0$  of the occupation measure of $B$  before time $s$  ). Moreover, the same conclusion holds for the processes $\widehat{H}\sigma (\mathbf{p}{)}_{2ns}^{\mathcal{ℱ}},\widehat{\Lambda }\sigma (\mathbf{p}{)}_{2ns}^{\mathcal{ℱ}}$  instead of $H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}},\Lambda \sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}$  .

(ii) Under $P\sigma (\mathbf{p}{)}^{\mu }(\cdot \left|\right|T|=n)$  , whenever the conditioning event has positive probability, the process $$\left(\frac{H\sigma (\mathbf{p}{)}_{ns}^T}{\sqrt{n}},0\le s\le 1\right)----\to weaklyn\to \infty \left(\frac{2}{\sigma }{e}_s,0\le s\le 1\right)$$  for the uniform topology, where $e$  is a standard Brownian excursion. The same result holds with $\widehat{H}\sigma (\mathbf{p}{)}_{2ns}^T$  instead of $H\sigma (\mathbf{p}{)}_{ns}^T$  .

2 CRITICAL TWO-TYPE DISCRETE SNAKES

2.3 Two-type Galton-Watson trees

Let $(\mu \circ ,\mu \bullet )$  be a pair of integer valued probability distributions with means $m_{\circ }$  and $m_{\bullet }$  , respectively. We denote by $\left(H_1\right)$  the set of assumptions : $$\left(H_1\right):=\{\begin{array}{c}\mu \circ \left(0\right)+\mu \circ \left(1\right)+\mu \bullet \left(0\right)+\mu \bullet \left(1\right)\ne 1,\\ m_{\circ }{m}_{\bullet }=1,\\ \text{there exists}\alpha >0\text{such that}{\sum }_{k\ge 0}e\sigma (\mathbf{p}{)}^{\alpha k}\mu \circ (k)<\infty ,{\sum }_{k\ge 0}e\sigma (\mathbf{p}{)}^{\alpha k}\mu \bullet \left(k\right)<\infty .\end{array}$$  We consider two-type $\{\circ ,\bullet \}$  GW trees with laws $P\sigma (\mathbf{p}{)}^{\circ }$  and $P\sigma (\mathbf{p}{)}^{\bullet }$  in which :

– the ancestor has type $\circ$  for $P\sigma (\mathbf{p}{)}^{\circ }$  and $\bullet$  for $P\sigma (\mathbf{p}{)}^{\bullet }$  , – an individual of type $\circ$  gives birth exclusively to individuals of type $\bullet$  according to the law $\mu \circ$  , – an individual of type $\bullet$  gives birth exclusively to individuals of type $\circ$  according to the law $\mu \bullet$  , – the progeny of distinct individuals are independent random variables.

Under the assumption $\left(H_1\right)$  , under $P\sigma (\mathbf{p}{)}^{\circ }$  or under $P\sigma (\mathbf{p}{)}^{\bullet }$  , $T$  is a.s. finite (see Proposition  5 ). So the law $P\sigma (\mathbf{p}{)}^{\circ }$  is characterized by $$P\sigma (\mathbf{p}{)}^{\circ }(T=\mathbf{t})={\prod }_{u\in \mathbf{t},\left|u\right|\text{even}}\mu \circ (c_u(\mathbf{t})){\prod }_{u\in \mathbf{t},\left|u\right|\text{odd}}\mu \bullet (c_u(\mathbf{t})),\mathbf{t}\in \mathbb{T}.$$  (For $P\sigma (\mathbf{p}{)}^{\bullet }$  replace in the last formula $\circ$  by $\bullet$  and $\bullet$  by $\circ$  ).

Notation In the sequel, unless otherwise mentioned the probability $P$  will denote $P\sigma (\mathbf{p}{)}^{\circ }$  , i.e. the law of a tree rooted at a $\circ$  individual. We will then denote by $\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }$  and $\mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }$  the sets of vertices of $\mathbf{t}$  with even resp. odd height.

Similarly, for $r\in \mathbb{N}\cup \{\infty \}$  we let $P_r$  be the law of a forest constituted of $r$  independent GW trees, all rooted at a $\circ$  individual. In particular, $P_1$  is naturally identified with $P\sigma (\mathbf{p}{)}^{\circ }$  .

2 CRITICAL TWO-TYPE DISCRETE SNAKES

2.4 Ancestral decomposition of a Galton-Watson tree

A key result for our study is a multitype version of an ancestral decomposition for Galton-Watson trees, related to the so-called size-biased Galton-Watson distribution. Let $$\widehat{\mu }\circ \left(k\right)=\frac{k\mu \circ \left(k\right)}{m_{\circ }},\widehat{\mu }\bullet \left(k\right)=\frac{k\mu \bullet \left(k\right)}{m_{\bullet }},k\ge 0$$  be the size-biased versions of the probabilities $\mu \circ ,\mu \bullet$  . The size-biased Galton-Watson tree is an infinite tree containing a unique spine, i.e. an infinite injective path starting from the root, and its distribution is defined as follows. The root is assigned a number of children $c_{\mathbb{\varnothing }}$  with distribution $\widehat{\mu }\circ$  , and a distinguished child is chosen uniformly among these. On all children but the distinguished one, independent trees with distribution $P\sigma (\mathbf{p}{)}^{\bullet }$  are grafted, while the distinguished child has an independent number of children with law $\widehat{\mu }\bullet$  . Again, one of these is chosen uniformly and distinguished. Independent trees with law $P\sigma (\mathbf{p}{)}^{\circ }$  originate from the undistinguished ones, and the distinguished one has offspring with law $\widehat{\mu }\circ$  , and so on, so that one uses distributions $P\sigma (\mathbf{p}{)}^{\circ },\widehat{\mu }\circ$  at even generations, and $P\sigma (\mathbf{p}{)}^{\bullet },\widehat{\mu }\bullet$  at odd ones. We let $\widehat{P}$  be the distribution of the resulting infinite tree, and we denote the infinite distinguished path $\left[\right[\mathbb{\varnothing },\infty \left]\right]=\{v_0=\mathbb{\varnothing },v_1,\dots \}$  . We let $\widehat{P}\sigma (\mathbf{p}{)}^{\left(h\right)}$  be the distribution of $\left(\right[T{]}_{v_h},v_h)$  under $\widehat{P}$  , and we denote by $(T,V)$  a random variable with this law. We also let $\circ \bullet \left(h\right)=\circ$  or $\bullet$  according to $h$  being even or odd.

Similarly, for $r\in \mathbb{N}=\{1,2,\dots \},h\ge 0$  , let $\widehat{P}\sigma (\mathbf{p}{)}_r^{\left(h\right)}$  be the law of a forest of $r$  independent trees all with law $P\sigma (\mathbf{p}{)}^{\circ }$  except for the $K$  -th one which has law $\widehat{P}\sigma (\mathbf{p}{)}^{\left(h\right)}$  , where $K$  is uniform on $\{1,2,\dots ,r\}$  .

Lemma 4 (Ancestral decomposition for Galton-Watson forests) For every $r\in \mathbb{N}$  and nonnegative functions $F,G$  $$E_r\left[{\sum }_{u\in \mathcal{ℱ}}F\left(\right|u|,[\mathcal{ℱ}{]}_u\left)G\right({\mathcal{ℱ}}_u)\right]=r{\sum }_{h\ge 0}{m}_{\circ }\sigma (\mathbf{p}{)}^{[h/2+1]}{m}_{\bullet }\sigma (\mathbf{p}{)}^{\left[\right(h+1)/2]}{\widehat{E}}_r\sigma (\mathbf{p}{)}^{\left(h\right)}[F(V,\mathcal{ℱ})\left]E\sigma \right(\mathbf{p}{)}^{\circ \bullet \left(h\right)}\left[G\right(T\left)\right].$$  (notice that by definition $[\mathcal{ℱ}{]}_u$  is a forest, while ${\mathcal{ℱ}}_u$  is a tree).

Otherwise said, if a vertex $u$  is taken according to the counting measure on $\mathcal{ℱ}$  , then its height is distributed according to the measure on $\mathbb{N}$  with weight $m_{\circ }\sigma (\mathbf{p}{)}^{[h/2+1]}{m}_{\bullet }\sigma (\mathbf{p}{)}^{\left[\right(h+1)/2]}$  on $\left\{h\right\}$  , and given $\left|u\right|=h$  , $\left(\right[\mathcal{ℱ}{]}_u,u),{\mathcal{ℱ}}_u$  are independent with respective laws $\widehat{P}\sigma (\mathbf{p}{)}_r^{\left(h\right)}$  and $P$  .

Notice that when $m_{\circ }{m}_{\bullet }=1$  , we can bound $$E_r\left[{\sum }_{u\in \mathcal{ℱ}}F(u,[\mathcal{ℱ}{]}_u\left)G\right({\mathcal{ℱ}}_u)\right]\le r(m_{\circ }\vee m_{\bullet }){\sum }_{h\ge 0}\widehat{E}\sigma (\mathbf{p}{)}_r^{\left(h\right)}[F(V,\mathcal{ℱ})\left]E\sigma \right(\mathbf{p}{)}^{\circ \bullet \left(h\right)}\left[G\right(T\left)\right].$$  Proof. This lemma is essentially deterministic, in that one can take $F(u,\mathbf{f})G\left({\mathbf{f}}^{\prime }\right)$  of the form $1_{u,\mathbf{f},{\mathbf{f}}^{\prime }}$  for some particular $u\in \mathbf{f},{\mathbf{f}}^{\prime }$  with say $\left|u\right|=h$  . It is then easy that the expectation we are looking for is just the probability $P_r(\mathcal{ℱ}=[\mathbf{f},u,{\mathbf{f}}^{\prime }\left]\right)$  where $[\mathbf{f},u,{\mathbf{f}}^{\prime }]$  is the unique forest ${\mathbf{f}}^{\prime \prime }$  satisfying $[{\mathbf{f}}^{\prime \prime }{]}_u=\mathbf{f},{\mathbf{f}}_u^{\prime \prime }={\mathbf{f}}^{\prime }$  . The subtrees originating from the spine $\left[\right[\mathbb{\varnothing },u\left]\right]$  are then plainly independent with the claimed laws $P\sigma (\mathbf{p}{)}^{\circ \bullet \left(h^{\prime }\right)},1\le h^{\prime }\le h$  , and independent of the structure of the spine. The latter is constituted of $\mathbb{\varnothing },u_1,\dots ,u_h=u$  and the brothers of $u_1,\dots ,u_h$  , whose respective numbers are $k_1-1,\dots ,k_h-1$  with probability 2 CRITICAL TWO-TYPE DISCRETE SNAKES $${\prod }_{0\le i\le h-1\text{even}}\mu \circ \left(k_{i+1}\right){\prod }_{1\le i\le h-1\text{odd}}\mu \bullet \left(k_{i+1}\right),$$  which we rewrite $$r{m}_{\circ }\sigma (\mathbf{p}{)}^{[h/2]}{m}_{\bullet }\sigma (\mathbf{p}{)}^{\left[\right(h-1)/2]}\frac{1}{r}{\prod }_{i=1}\sigma (\mathbf{p}{)}^h\frac{1}{k_i}{\prod }_{0\le i\le h-1\text{even}}\widehat{\mu }\circ (k_{i+1}){\prod }_{1\le i\le h-1\text{odd}}\widehat{\mu }\bullet (k_{i+1}),$$  and the first product corresponds to the probability of choosing the distinguished vertex $u_i$  at height $i$  , while the factor $1/r$  amounts to choosing the place of the distinguished tree in the forest with $r$  roots. Hence the result. $\square$  2 CRITICAL TWO-TYPE DISCRETE SNAKES

2.5 Criticality and the tree of grandfathers

We now use a natural reduction of two-type trees obtained when squeezing all the odd generations, i.e. by considering only the $\circ$  descendence of $\circ$  vertices. More precisely, given a tree $\mathbf{t}$  , we define recursively the reduced tree $\overline{\mathbf{t}}\circ$  (also called the tree of grandfathers in the sequel) starting from the root, by letting the children of the root in $\overline{\mathbf{t}}\circ$  be the grandchildren of $\mathbb{\varnothing }$  in $\mathbf{t}$  , taken in depth-first order, and letting the children of these be the corresponding grandchildren in $\mathbf{t}$  , and so on. Formally, if $k$  is the number of children of $\mathbb{\varnothing }$  in $\mathbf{t}$  , and if the $i$  -th of these children has $c_i$  children $i1,\dots ,i{c}_i$  itself, then root $\mathbb{\varnothing }$  has $c_1+\dots +c_k$  children in $\overline{\mathbf{t}}\circ$  , and we let $\overline{ij}=c_1+\dots +c_{i-1}+j$  . In stage $n$  , if we consider a vertex $\overline{u}$  of $\overline{\mathbf{t}}\circ$  which comes from a vertex $u$  of $\mathbf{t}$  by our construction, we let $uij,1\le i\le c_u,1\le j\le c_{ui}$  be its grandsons in $\mathbf{t}$  , and we map $uij$  to $\overline{uij}=\overline{u}(c_{u1}+\dots +c_{u(i-1)}+j)$  , hence determining the $c_{u1}+\dots +c_{uk}$  children of $\overline{u}$  in $\overline{\mathbf{t}}\circ$  .

Figure 4 : A two-type tree $T$  , the corresponding reduced tree ${\overline{T}}_{\circ }$  , and the forest ${\overline{T}}_{\bullet }$  .

It is now obvious by definition that

Proposition 3 If $T$  follows the law $P$  , then $\overline{T}\circ$  is a monotype Galton-Watson tree, whose offspring distribution $\overline{\mu }\circ$  has generating function $$G_{\overline{\mu }\circ }=G_{\mu \circ }\circ G_{\mu \bullet }.$$ 

By differentiating this expression, we obtain that the mean of this new offspring distribution is $m_{\bullet }{m}_{\circ }$  , so it is critical by our assumptions. Also, we can similarly consider a forest $T_1,T_2,\dots ,T_{c_{\mathbb{\varnothing }}\left(T\right)}$  of fringe subtrees rooted at the sons of the root of $T$  , and apply a similar transformation $\overline{T}\bullet$  to all these trees, skipping every $\circ$  generation. Again, this gives a critical GW forest (with random number of trees), also called forest of grandfathers in the sequel. By differentiating twice the expression above we also obtain that the variance is finite, and in fact small exponential moments are finite. A quick computation gives that the variance of $\overline{\mu }\circ$  is ${\overline{\sigma }}_{\circ }\sigma (\mathbf{p}{)}^2$  (resp. ${\overline{\sigma }}_{\bullet }\sigma (\mathbf{p}{)}^2$  for $\overline{\mu }\bullet$  ), where

$$\begin{array}{c}{\overline{\sigma }}_{\circ }=\sqrt{m_{\bullet }\sigma (\mathbf{p}{)}^2{\sigma }_{\circ }\sigma (\mathbf{p}{)}^2+m_{\circ }{\sigma }_{\bullet }\sigma (\mathbf{p}{)}^2},{\overline{\sigma }}_{\bullet }=\sqrt{m_{\bullet }{\sigma }_{\circ }\sigma (\mathbf{p}{)}^2+m_{\circ }\sigma (\mathbf{p}{)}^2{\sigma }_{\bullet }\sigma (\mathbf{p}{)}^2}.\end{array}$$

(9)

From the a.s. extinction criterium of monotype Galton-Watson trees, we also immediately deduce in our case the well-known extinction lemma for two-type trees:

Lemma 5 Let $(\mu \circ ,\mu \bullet )$  satisfy $\left(H_1\right)$  and $T$  be a $P\sigma (\mathbf{p}{)}^{\circ }$  (or $P\sigma (\mathbf{p}{)}^{\bullet }$  ) distributed tree. Then $T$  is a.s. finite.

Of course, the existence of small exponential moments can be lifted here. We also immediately get

Lemma 6 Assume that the pair $(\mu \circ ,\mu \bullet )$  satisfies $\left(H_1\right)$  . The conclusions of Lemmæ  2 and  3 remain valid for $P\sigma (\mathbf{p}{)}^{\circ }$  -forests (and $P\sigma (\mathbf{p}{)}^{\bullet }$  -forests) introduced in Section  2.1 .

We now give a result similar to [20] in the case of single type Galton-Watson trees. For $u\in \mathbf{t}$  and $k\ge 1$  let $a_{u,k}(\mathbf{t})$  be the number of ancestors $v\in \left[\right[\mathbb{\varnothing },u\left]\right]$  that have $k$  children exactly. Similar notations are taken for forests. The next lemma allows to bound the degree in large trees.

Lemma 7 Assume that the pair $(\mu \circ ,\mu \bullet )$  satisfies $\left(H_1\right)$  . For every $A,\xi >0$  there exists $\varepsilon >0$  such that for $n$  large enough,

$$\begin{array}{c}{P}_{\infty }\left({sup}_{k\ge n\sigma (\mathbf{p}{)}^{\xi },u\prec u(\left[An\right])}{a}_{u,k}(\mathcal{ℱ})\ge 1\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon }).\end{array}$$

(10)

Moreover, for every $D>0$  there exists $C>0$  such that for $n$  large enough,

$$\begin{array}{c}{P}_{\infty }\left({sup}_{k\ge Clogn,u\prec u\left(\right[An\left]\right)}{a}_{u,k}(\mathcal{ℱ})\ge 1\right)\le n\sigma (\mathbf{p}{)}^{-D}.2\mathit{C}\mathit{R}\mathit{I}\mathit{T}\mathit{I}\mathit{C}\mathit{A}\mathit{L}\mathit{T}\mathit{W}\mathit{O}\mathit{-}\mathit{T}\mathit{Y}\mathit{P}\mathit{E}\mathit{D}\mathit{I}\mathit{S}\mathit{C}\mathit{R}\mathit{E}\mathit{T}\mathit{E}\mathit{S}\mathit{N}\mathit{A}\mathit{K}\mathit{E}\mathit{S}\end{array}$$

(11)

Proof. Let $\eta >0$  . By first using Lemma  6 as in Lemma  8 , it suffices to bound $$P_{n\sigma (\mathbf{p}{)}^{1/2+\eta }}\left({sup}_{k\ge n\sigma (\mathbf{p}{)}^{\xi },|u|\le n\sigma (\mathbf{p}{)}^{1/2+\eta }}{a}_{u,k}\ge 1\right)\le E_{n\sigma (\mathbf{p}{)}^{1/2+\eta }}\left({\sum }_{u\in \mathcal{ℱ}}{1}_{\left|u\right|\le n\sigma (\mathbf{p}{)}^{1/2+\eta }}{1}_{c_u\ge n\sigma (\mathbf{p}{)}^{\xi }}\right)$$  and applying the ancestral decomposition, this is smaller than $$(m_{\circ }\vee m_{\bullet })n\sigma (\mathbf{p}{)}^{1/2+\eta }{\sum }_{0\le h\le n\sigma (\mathbf{p}{)}^{1/2+\eta }}\mu \sigma (\mathbf{p}{)}^{\circ \bullet \left(h\right)}\left(\left[n\sigma \right(\mathbf{p}{)}^{\xi },+\infty [\right).$$  The sum contains two kinds of terms depending on whether $h$  is odd or even. Since $\mu \sigma (\mathbf{p}{)}^{\circ }$  and $\mu \sigma (\mathbf{p}{)}^{\bullet }$  have small exponential moments, Markov’s inequality shows that, there exists $\varepsilon$  such that, for $n$  large enough, $\mu \sigma (\mathbf{p}{)}^{\circ }(\left[n\sigma \right(\mathbf{p}{)}^{\xi },+\infty \left)\right)+\mu \sigma (\mathbf{p}{)}^{\bullet }(\left[n\sigma \right(\mathbf{p}{)}^{\xi },+\infty \left)\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon /2})$  , which gives ( 10 ). We obtain ( 11 ) by a similar method. $\square$  2 CRITICAL TWO-TYPE DISCRETE SNAKES

2.6 Repartition of $\circ$  -nodes and $\bullet$  -nodes in two-type trees

Let now $J\sigma (\mathbf{p}{)}_{\mathbf{t}}^{\circ }(k)$  (resp. $J\sigma (\mathbf{p}{)}_{\mathbf{t}}^{\bullet }(k)$  ) be the number of vertices of type $\circ$  (resp. $\bullet$  ) occurring in depth-first order before the $k$  -th vertex of $\mathbf{t}$  in depth-first order. It is immediate that

$$\begin{array}{c}\left|H\sigma (\mathbf{p}{)}_k^{\mathbf{t}}-2H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathbf{t}}^{\circ }(k)}^{\overline{\mathbf{t}}\circ }\right|\le 2\left|H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathbf{t}}^{\circ }(k)}^{\overline{\mathbf{t}}\circ }-H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathbf{t}}^{\circ }(k)+1}^{\overline{\mathbf{t}}\circ }\right|+2,\end{array}$$

(12)

where by convention $H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathbf{t}}^{\circ }(k)+1}^{\overline{\mathbf{t}}\circ }=0$  when $J\sigma (\mathbf{p}{)}_{\mathbf{t}}^{\circ }(k)=|\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }|$  . A similar inequality holds when $\mathbf{t}$  is replaced by a forest $\mathbf{f}$  , and/or $\circ$  by $\bullet$  . The next lemma gives the asymptotic behavior for $\left(J\sigma \right(\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }\left(k\right),k\ge 0)$  .

Lemma 8 Under assumptions $\left(H_1\right)$  , for any $A,\gamma >0$  there exists $\varepsilon >0$  such that for $n$  large enough, $$P_{\infty }\left({sup}_{0\le k\le An}\left|J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(k)-\frac{k}{1+m_{\circ }}\right|>n\sigma (\mathbf{p}{)}^{1/2+\gamma }\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon }),$$  and similarly with $\left(J\sigma \right(\mathbf{p}{)}_{\mathcal{ℱ}}^{\bullet },m_{\bullet })$  instead of $\left(J\sigma \right(\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ },m_{\circ })$  .

Proof. Let $J_k^{\prime }$  be the total number of vertices that have been visited before exploring the $k$  -th $\circ$  , which we call $u$  (and which is counted in the number $J_k^{\prime }$  ). At time $J_k^{\prime }$  , one has visited all the children of the $k-1$  first $\circ$  -nodes $u_1,...,u_{k-1}$  except maybe some of the children of the ancestors of $u$  . Using Lemmas  7 and  2 , for any $\eta ,\xi >0$  , there exists $\varepsilon >0$  , for $n$  large enough, for any $k\le An$  , $$P\left(\left|J_k^{\prime }-(k+{\sum }_{i=1}\sigma (\mathbf{p}{)}^k{c}_{u_i})\right|\ge n\sigma (\mathbf{p}{)}^{1/2+\eta +\xi }\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon }).$$  Now, since the random variables $c_{u_i}$  are independent and have exponential moments, ${\sum }_{i=1}\sigma (\mathbf{p}{)}^k{c}_{u_i}$  is concentrated around its mean, and one gets that for $n$  large enough, for any $k\le An$  , $$P\left({sup}_{0\le k\le An}|J_k^{\prime }-(1+m_{\circ }\left)k\right|\ge n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon }).$$  The result on $J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }$  follows by a standard argument (it is uniformly close to the right-continuous inverse of $J^{\prime }$  ). The very same reasoning shows that $J_k^{\prime \prime }$  is uniformly close to $(1+m_{\bullet })k$  with high probability, where $J_k^{\prime \prime }$  is the number of $\bullet$  vertices visited before the $k$  -th vertex. $\square$  An immediate consequence of this is

Corollary 2 Under the hypotheses $(H)$  , the statement of Proposition  1 remains valid in the two-type case, i.e. for every $A,\varepsilon >0,\alpha \in (0,1/2)$  , there exists $C>0$  with $${sup}_{n\in \mathbb{N}}P\sigma (\mathbf{p}{)}_{\infty }^{\circ }\left({sup}_{0\le s\ne t\le A}\frac{\left|H\sigma \right(\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-H\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}|}{\sqrt{n}|s-t|\sigma (\mathbf{p}{)}^{\alpha }}>C\right)\le \varepsilon .$$ 

Proof. We bound $$\left|\frac{H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-H\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}}{\sqrt{n}}\right|\le \left|\frac{H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-2H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(ns)}^{{\overline{\mathcal{ℱ}}}_{\circ }}}{\sqrt{n}}\right|+2\left|\frac{H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(ns)}^{{\overline{\mathcal{ℱ}}}_{\circ }}-H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(nt)}^{{\overline{\mathcal{ℱ}}}_{\circ }}}{\sqrt{n}}\right|+\left|\frac{H\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}-2H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(nt)}^{{\overline{\mathcal{ℱ}}}_{\circ }}}{\sqrt{n}}\right|.2\mathit{C}\mathit{R}\mathit{I}\mathit{T}\mathit{I}\mathit{C}\mathit{A}\mathit{L}\mathit{T}\mathit{W}\mathit{O}\mathit{-}\mathit{T}\mathit{Y}\mathit{P}\mathit{E}\mathit{D}\mathit{I}\mathit{S}\mathit{C}\mathit{R}\mathit{E}\mathit{T}\mathit{E}\mathit{S}\mathit{N}\mathit{A}\mathit{K}\mathit{E}\mathit{S}$$  The term in the middle is $<C|s-t|\sigma (\mathbf{p}{)}^{\alpha }$  with high probability for $C$  large enough thanks to Proposition  1 and Lemma  8 , while the two others are bounded by $${sup}_{0\le k\le An}n\sigma (\mathbf{p}{)}^{-1/2}\left|H\sigma (\mathbf{p}{)}_k^{{\overline{\mathcal{ℱ}}}_{\circ }}-H\sigma (\mathbf{p}{)}_{k+1}^{{\overline{\mathcal{ℱ}}}_{\circ }}\right|$$  by ( 12 ) and the fact that $J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(k)\le k$  . Now this quantity converges to $0$  in probability by Proposition  2 . Therefore, we obtain the desired bound when $s\ne t$  are such that $ns,nt$  are integers, and this is extended similarly as above to any $s,t\le A$  by linear interpolation. $\square$  2 CRITICAL TWO-TYPE DISCRETE SNAKES

2.7 Two-type discrete snakes

We now couple the Galton-Watson trees with a spatial motion as follows. For every $k\ge 1$  consider two distributions ${\nu }_k\sigma (\mathbf{p}{)}^{\circ },{\nu }_k\sigma (\mathbf{p}{)}^{\bullet }$  on $\mathbb{R}\sigma (\mathbf{p}{)}^k$  .

We enrich the laws $P_r,r\in \mathbb{N}\cup \{\infty \}$  by associating with the children $(u1,\dots ,u{c}_u(\mathbf{f}\left)\right)$  of every vertex $u$  of $\mathbf{f}$  (given $\mathcal{ℱ}=\mathbf{f}$  ) a r.v. $(Y_{u1},Y_{u2}\dots ,Y_{u{c}_u(\mathbf{f})})$  with law $\nu \sigma (\mathbf{p}{)}_{c_u(\mathbf{f})}^{\circ }$  if $\left|u\right|$  is even, and $\nu \sigma (\mathbf{p}{)}_{c_u(\mathbf{f})}^{\bullet }$  otherwise, and we suppose these variables independent over different $u$  ’s.

We call ${\mathbb{P}}_r$  the associated probability. We let also $Y_{\mathbb{\varnothing }}=0$  and $\ell \left(u\right)={\sum }_{v\in \left[\right[\mathbb{\varnothing },u\left]\right]}{Y}_v$  . In the sequel, the notation $\mathbf{f}$  will stand for a labeled forest $(\mathbf{f},\ell )$  .Let $R\sigma (\mathbf{p}{)}_k^{\mathbf{f}}=\ell (\left(u\right(k\left)\right)$  , and define $\left(R\sigma \right(\mathbf{p}{)}_s^{\mathbf{f}},s\ge 0)$  by linear interpolation between values taken at integers. Similarly, we let $\widehat{R}\sigma (\mathbf{p}{)}_k^{\mathbf{f}}=l(F_{\mathbf{f}}\left(k\right))$  be the label of the $k$  -th vertex in depth-first traversal, and let $\widehat{R}\sigma (\mathbf{p}{)}^{\mathbf{f}}$  be the associated interpolated process. It is convenient to see this construction as done on Figure  5 :

assume that each node $u$  is drawn in the plane at position $(\ell (u),|u\left|\right)$  . The children of $u$  will be at position $\left\{\right(\ell \left(u\right)+Y_{ui},\left|u\right|+1),i\in \mathcal{J}1,c_{\mathbf{f}}(u\left)\mathcal{K}\right\}$  . Hence, the variable $Y_{ui}$  can be thought as abscissa displacements of $i$  th children of $u$  relative to $u$  .

Figure 5 : At first a tree in which each node $u$  is marked with $Y_u$  . On the second picture, $u$  is marked with $\ell \left(u\right)$  , then one sees a representation in the plan using the variable $Y_u$  as abscissa displacements. Then are represented on top $\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}}$  and below $\widehat{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}$  . The small rectangle in this Figure illustrates that the process $\widehat{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}$  must be constant on the nodes encoded by $\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}}$ 

We denote by $$M\sigma (\mathbf{p}{)}_{k,j,p}^{\circ }={\int }_{\mathbb{R}\sigma (\mathbf{p}{)}^k}|x_j\left|\sigma \right(\mathbf{p}{)}^p\nu \sigma (\mathbf{p}{)}_k^{\circ }(dx\left)\text{and}M\sigma \right(\mathbf{p}{)}_{k,j,p}^{\bullet }={\int }_{\mathbb{R}\sigma (\mathbf{p}{)}^k}\left|x_j\right|\sigma (\mathbf{p}{)}^p\nu \sigma (\mathbf{p}{)}_k^{\bullet }(dx)$$  the $p$  -th moments of the one-dimensional marginals of $\nu \sigma (\mathbf{p}{)}_k^{\circ }$  and $\nu \sigma (\mathbf{p}{)}_k^{\bullet }$  . We denote by $\left(H_2\right)$  the set of assumptions $$\left(H_2\right):=\{\begin{array}{c}\text{the one-dimensional marginals of}\nu \sigma (\mathbf{p}{)}_k^{\circ }\text{and}\nu \sigma (\mathbf{p}{)}_k^{\bullet }\text{are centered.}\\ \text{there exists}\varepsilon >0,\text{S.t. for any}k\ge 1,1\le j\le k,M\sigma (\mathbf{p}{)}_{k,j,4+\varepsilon }^{\circ }<+\infty \text{and}M\sigma (\mathbf{p}{)}_{k,j,4+\varepsilon }^{\bullet }<\infty \end{array}$$  We will denote these two last quantities by $M\sigma (\mathbf{p}{)}_{k,j}^{\circ },M\sigma (\mathbf{p}{)}_{k,j}^{\bullet }$  for the sake of brevity. We let also $(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ }\left)\sigma \right(\mathbf{p}{)}^2,(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2$  be the variances of the $j$  -th marginal, and define

$$\begin{array}{c}\Sigma =\sqrt{\frac{1}{2}{\sum }_{k\ge 1}\left[\frac{\mu \circ \left(k\right)}{m_{\circ }}{\sum }_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ }\left)\sigma \right(\mathbf{p}{)}^2+\frac{\mu \bullet \left(k\right)}{m_{\bullet }}{\sum }_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2\right]}.\end{array}$$

(13)

3 CONVERGENCE OF NORMALIZED LABELED FORESTS

3 Convergence of normalized labeled forests

3 CONVERGENCE OF NORMALIZED LABELED FORESTS

3.1 Convergence of the shape

Define

$$\begin{array}{c}\overline{\sigma }=\frac{1}{2}\sqrt{{\sigma }_{\circ }\sigma (\mathbf{p}{)}^2\frac{1+m_{\bullet }}{m_{\circ }}+{\sigma }_{\bullet }\sigma (\mathbf{p}{)}^2\frac{1+m_{\circ }}{m_{\bullet }}},\end{array}$$

(14)

so that $\overline{\sigma }=\sqrt{1+m_{\circ }}{\overline{\sigma }}_{\circ }/2=\sqrt{1+m_{\bullet }}{\overline{\sigma }}_{\bullet }/2$  .

Theorem 2 Let $(\mu \circ ,\mu \bullet )$  satisfying $\left(H_1\right)$  ; under $P_{\infty }$  , $${\left(\frac{H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{\sqrt{n}},\frac{\widehat{H}\sigma (\mathbf{p}{)}_{2ns}^{\mathcal{ℱ}}}{\sqrt{n}},\frac{\Lambda \sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{\sqrt{n}},\frac{\widehat{\Lambda }\sigma (\mathbf{p}{)}_{2ns}^{\mathcal{ℱ}}}{\sqrt{n}}\right)}_{s\ge 0}--\to \left(d\right)n{\left(\frac{2}{\overline{\sigma }}\left|B_s\right|,\frac{2}{\overline{\sigma }}\left|B_s\right|,\frac{{\overline{\sigma }}_{\circ }}{\sqrt{1+m_{\circ }}}L\sigma (\mathbf{p}{)}_s^0,\frac{{\overline{\sigma }}_{\circ }}{\sqrt{1+m_{\circ }}}L\sigma (\mathbf{p}{)}_s^0\right)}_{s\ge 0}$$  where $B$  is a standard Brownian motion and $L\sigma (\mathbf{p}{)}^0$  is its local time at 0.

Remark. We suspect that the small exponential moments assumption is only technical, and that this theorem holds assuming only finite variance. However, dropping this assumption is likely to make all the proofs much more involved. The fact that convergence holds jointly for rescaled height and contour processes is an amelioration obtained in [19] , see also [11] , and we will exclusively concentrate on the height process in the sequel, referring the interested reader to the above references.

Proof. This is an easy consequence of the preceding results. From ( 12 ) and Proposition  2 , we have that under $P\sigma (\mathbf{p}{)}_{\infty }^{\circ }$  , $\left(n\sigma \right(\mathbf{p}{)}^{-1/2}H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}},s\ge 0)$  has the same limit as $\left(n\sigma \right(\mathbf{p}{)}^{-1/2}2H\sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(\left[ns\right])}^{{\overline{\mathcal{ℱ}}}_{\circ }},s\ge 0)$  . By Propositions  2 and  8 and a standard argument using Skorokhod’s representation’s theorem, we obtain that the latter process converges to $\left(2{\overline{\sigma }}_{\circ }\sigma \right(\mathbf{p}{)}^{-1}\left|B_{(1+m_{\circ })\sigma (\mathbf{p}{)}^{-1}s}\right|,s\ge 0)$  , and it suffices to use Brownian scaling and check that $2/\left(\sqrt{1+m_{\circ }}{\overline{\sigma }}_{\circ }\right)=2/\overline{\sigma }$  . The joint convergence with $\left(n\sigma \right(\mathbf{p}{)}^{-1/2}\Lambda \sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}},s\ge 0)$  is then easy, using that $\Lambda \sigma (\mathbf{p}{)}_k^{\mathcal{ℱ}}=\Lambda \sigma (\mathbf{p}{)}_{J\sigma (\mathbf{p}{)}_{\mathcal{ℱ}}^{\circ }(k)}^{{\overline{\mathcal{ℱ}}}_{\circ }}$  for every $k\ge 0$  . $\square$  3 CONVERGENCE OF NORMALIZED LABELED FORESTS

3.2 Convergence of the labels

For $(X_s,s\ge 0)$  a real-valued function, we let ${\check{X}}_{s,s^{\prime }}={inf}_{s\wedge s^{\prime }\le u\le s\vee s^{\prime }}{X}_u$  . Denote by $\left(H_3\right)$  the assumption $$\left(H_3\right):=\{\text{there exists}D>0\text{such that}{max}_{1\le j\le k}\left(M\sigma \right(\mathbf{p}{)}_{k,j}^{\circ }\vee M\sigma (\mathbf{p}{)}_{k,j}^{\bullet })=O\left(k\sigma \right(\mathbf{p}{)}^D).$$  The goal of this section is to prove the following theorem.

Theorem 3 If $\left(H_1\right)$  , $\left(H_2\right)$  and $\left(H_3\right)$  are satisfied then $\Sigma$  is finite, and under ${\mathbb{P}}_{\infty }$  , we have $$\left(\frac{H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{\Lambda \sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}\right)----\to weaklyn\to \infty \left(\frac{2}{\overline{\sigma }}\left|B_s\right|,\frac{{\overline{\sigma }}_{\circ }}{\sqrt{1+m_{\circ }}}L\sigma (\mathbf{p}{)}_s^0,\Sigma \sqrt{\frac{2}{\overline{\sigma }}}{r}_s\right),s\ge 0,$$  in $C\left(\right[0,1],\mathbb{R}\sigma (\mathbf{p}{)}^3)$  , endowed with the topology of uniform convergence on compact sets, and where conditionally on $B$  , $r$  is a centered Gaussian process with covariance $$cov(r_s,r_{s^{\prime }})=|\check{B}{|}_{s,s^{\prime }},s,s^{\prime }\ge 0.$$  Similarly, $$\left(\frac{\widehat{H}\sigma (\mathbf{p}{)}_{2ns}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{\widehat{\Lambda }\sigma (\mathbf{p}{)}_{2ns}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{\widehat{R}\sigma (\mathbf{p}{)}_{2ns}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}\right)----\to weaklyn\to \infty \left(\frac{2}{\overline{\sigma }}\left|B_s\right|,\frac{{\overline{\sigma }}_{\circ }}{\sqrt{1+m_{\circ }}}L\sigma (\mathbf{p}{)}_s^0,r_s\right),s\ge 0.$$ 

Remarks. $\bullet$  In case of i.i.d. random variables $Y_v$  , the minimum moment condition is the existence of a moment of order $4+\varepsilon$  (see [14] ). There, since we allow the law of $Y_v$  to depend on the degree (this is the case in the application to mobiles associated with random maps), the moments of order $4+\varepsilon$  must exist and also must not grow too fast with the degree: the rate of growing depends on the apparition of nodes with large degree in the tree; this is ruled off by Lemma  7 .

$\bullet$  In fact, a joint convergence result similar to that of Theorem  2 could be obtained here, but we do not concentrate on this. Also, the proofs will be done only in the case of the height process, the case of the contour process being similar, and easier in many ways (e.g. the analog of Lemma  11 is straightforward).

From Theorem  3 , we deduce, recalling the notations of Sect.  1.5 ,

Corollary 3 Supposing $\left(H_1\right),\left(H_2\right),\left(H_3\right)$  , for any $a>0$  , the process $\left(\right(n\sigma (\mathbf{p}{)}^{-1/2}H\sigma (\mathbf{p}{)}_{ns}^T,n\sigma (\mathbf{p}{)}^{-1/4}R\sigma (\mathbf{p}{)}_{ns}^T),0\le s\le n\sigma (\mathbf{p}{)}^{-1}\left|T\right|)$  under $\mathbb{P}(\cdot |maxR\sigma (\mathbf{p}{)}^T-minR\sigma (\mathbf{p}{)}^T>an\sigma (\mathbf{p}{)}^{1/4})$  converges to $\left(2\overline{\sigma }\sigma \right(\mathbf{p}{)}^{-1}e,\Sigma \sqrt{2\overline{\sigma }\sigma (\mathbf{p}{)}^{-1}}r)$  under $\mathbb{N}(\cdot |\Sigma \sqrt{2\overline{\sigma }\sigma (\mathbf{p}{)}^{-1}}\Delta >a)$  .

We will not give a detailed proof of this statement, as a very similar result appears in [11,Section2.5] , to which we refer the interested reader. Also, many other kinds of non-singular conditionings could be chosen instead of our choice on the diameter of the range of the process $r$  . We use this one because of the specialization to the mobiles associated with maps as discussed in the Introduction and in Sect.  4 : the diameter of the range of $r$  corresponds to the radius of the map.

In order to prove Theorem  3 , we must first control the behavior of the random variables $Y_v$  involved in $R_{ns}$  . This passes through the control of the largest degree in a our random trees, which is the aim of the following subsection.

3 CONVERGENCE OF NORMALIZED LABELED FORESTS

3.3 Preliminary lemmæ

Now, for $1\le j\le k$  we let $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }(\mathbf{t})$  be the number of ancestors $v\in \left[\right[\mathbb{\varnothing },u\left]\right]$  such that $\left|v\right|$  is even, $c_{\mathbf{t}}\left(v\right)=k$  , and such that $u$  is moreover in the $j$  -th fringe subtree ${\mathbf{t}}_{vj}$  . The quantity $a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }(\mathbf{t})$  is defined similarly. We define the same quantity for forests rather than trees. Under a GW law (of a tree of a forest), we will unambiguously denote $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }(T)$  or $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }(\mathcal{ℱ})$  by $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }$  , and so on.

Lemma 9 Let $(\mu \circ ,\mu \bullet )$  satisfying $\left(H_1\right)$  . For every $\gamma ,A>0$  , there exists $\varepsilon >0$  such that for $n$  large enough, $$P_{\infty }\left({sup}_{k\ge 1,1\le j\le k,u\prec u\left(\right[An\left]\right)}\frac{\left|a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{2m_{\circ }}|u|\right|}{\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}}\ge n\sigma (\mathbf{p}{)}^{1/4+\gamma }\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon })$$  and similarly for $a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }$  .

Proof. Notice that the number of $\circ$  vertices under a vertex of height $h$  is $[h/2+1]$  . By Lemma  4 , for a given $k\ge 1,1\le j\le k$  , 3 CONVERGENCE OF NORMALIZED LABELED FORESTS

$$\begin{array}{ccc}{P}_{n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}}\left({sup}_{\left|u\right|\le n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}}\left|a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{m_{\circ }}\left[\frac{\left|u\right|}{2}+1\right]\right|\ge \sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}n\sigma (\mathbf{p}{)}^{1/4+\gamma }\right)& & \end{array}$$

(15)

$$\begin{array}{ccc}& \le & E_{n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}}\left[{\sum }_{u\in \mathcal{ℱ}}{1}_{\left\{\left|a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{m_{\circ }}\left[\frac{\left|u\right|}{2}+1\right]\right|\ge \sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}n\sigma (\mathbf{p}{)}^{1/4+\gamma }\right\}}{1}_{\left\{\right|u|\le [n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}]\}}\right]\end{array}$$

$$\begin{array}{ccc}& \le & C_{\circ \bullet }n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}{\sum }_{h=0}\sigma (\mathbf{p}{)}^{\left[n\sigma \right(\mathbf{p}{)}^{1/2+\gamma /2}]}P\left(\left|{\sum }_{l=1}\sigma (\mathbf{p}{)}^{[h/2+1]}X\sigma (\mathbf{p}{)}_{k,j}^{\circ }\left(l\right)-\frac{\mu \circ \left(k\right)}{m_{\circ }}\left[\frac{h}{2}+1\right]\right|\ge \sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}n\sigma (\mathbf{p}{)}^{1/4+\gamma }\right),\end{array}$$

(16)

where $C_{\circ \bullet }=m_{\circ }\vee m_{\bullet }$  , and where on a probability space $(\Omega ,\mathcal{A},P)$  , $X\sigma (\mathbf{p}{)}_{k,j}^{\circ }(l),l=0,\dots ,[h/2+1]$  are i.i.d. random variables with Bernoulli( $\mu \circ \left(k\right)/m_{\circ }$  ) law (which corresponds to the probability that $\widehat{X}=k,U_k=j$  where $\widehat{X}$  has law $P(\widehat{X}=k)=k\mu \circ \left(k\right)/m_{\circ }$  , and given $\widehat{X}=k$  , $U_k\in \{1,\dots ,k\}$  is uniform). Now Hœffding’s inequality says that if $S_n\sigma (\mathbf{p}{)}^{\left(p\right)}$  is a binomial variable with parameter $p$  and $n$  trials. Then for every $y\ge 0$  ,

$$\begin{array}{c}P\left(\left|S_n\sigma \right(\mathbf{p}{)}^{\left(p\right)}-np|>\sqrt{p}y\right)\le 2exp(-2y\sigma (\mathbf{p}{)}^2/n).\end{array}$$

(17)

This allows to bound each term in the sum ( 16 ) by $2e\sigma (\mathbf{p}{)}^{-2n\sigma (\mathbf{p}{)}^{\gamma }}$  , and so the right member of ( 16 ) is $O\left(e\sigma \right(\mathbf{p}{)}^{-n\sigma (\mathbf{p}{)}^{\gamma }})$  where the $O$  is uniform on $k$  . To conclude, we have to remove the condition $sup\left\{\right|u\left|\right\}\le n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}$  and to move the supremum on $k$  inside the probability.

The first point is done thanks to Lemma  6 .

Second point : The left hand side of ( 15 ) is bounded by $O\left(ne\sigma \right(\mathbf{p}{)}^{-2n\sigma (\mathbf{p}{)}^{\gamma }})$  , if we add ${sup}_{k\le n}$  in the probability. Let us handle the $k$  larger than $n$  . For $n$  large enough, with probability $\ge 1-exp(-n\sigma (\mathbf{p}{)}^{{\varepsilon }_1})$  , all $a_{u,k}$  , and thus all $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }$  , are null for $k>n$  , and all $\left|u\right|\le n$  (by Lemma  10 ). Thus with this high probability, $${sup}_{k>n}\frac{\left|a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{2m_{\circ }}|u|\right|}{\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}}={sup}_{k>n}\sqrt{\frac{\mu \circ \left(k\right)}{4m_{\circ }}}\left|u\right|\le n{sup}_{k>n}\sqrt{\frac{\mu \circ \left(k\right)}{4m_{\circ }}}\le {sup}_{k>n}k\sqrt{\frac{\mu \circ \left(k\right)}{4m_{\circ }}}\le n\sigma (\mathbf{p}{)}^{1/4+\gamma },$$  for $n$  large, because $\mu \circ$  has exponential moments.

The same reasoning applies to $a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }$  . $\square$  The next lemma sharpens the preceding one, subject to relaxing a little the uniformity on $u$  .

For $u\in \mathbf{t},0\le l\le \left|u\right|,k\ge 1,1\le j\le l$  , we define the quantity $a\sigma (\mathbf{p}{)}_{u,l,k,j}^{\circ }$  to be the number of ancestors $v\in \left[\right[\mathbb{\varnothing },u\left]\right]$  with even height satisfying $\left|v\right|>\left|u\right|-l$  , and for which $c_v(\mathbf{t})=k$  and $u\in {\mathbf{t}}_{vj}$  .

Lemma 10 Let $(\mu \circ ,\mu \bullet )$  satisfying $\left(H_1\right)$  . For every $A,\gamma ,\xi >0$  , there exists $\varepsilon >0$  such that, for $n$  large enough $$P_{\infty }\left({sup}_{k\ge 1,1\le j\le k,u\prec u\left(\right[An\left]\right),n\sigma (\mathbf{p}{)}^{\xi }\le l\le |u|}\frac{\left|a\sigma (\mathbf{p}{)}_{u,l,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{2m_{\circ }}l\right|}{l\sigma (\mathbf{p}{)}^{1/2+\gamma }\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}}\ge 1\right)\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon }).$$ 

Proof. Again we consider a forest with $n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}$  trees and bound $\left|u\right|\le n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}$  up to losing an exponentially small probability. Also, notice that the number of $\circ$  vertices comprised between a vertex with height $h$  and its ancestor at height $h-l$  is $[h/2+1]-\left[\right(h-l)/2+1]$  .

For fixed $k,l$  , and for $c>0$  we write similarly as above 3 CONVERGENCE OF NORMALIZED LABELED FORESTS

$$\begin{array}{ccc}{P}_{n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}}\left({sup}_{n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}\ge |u|\ge l\ge n\sigma (\mathbf{p}{)}^{\xi }}\frac{\left|a\sigma (\mathbf{p}{)}_{u,l,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{m_{\circ }}\left(\left[\frac{h}{2}+1\right]-\left[\frac{h-l}{2}+1\right]\right)\right|}{\left(\left[\frac{h}{2}+1\right]-\left[\frac{h-l}{2}+1\right]\right)\sigma (\mathbf{p}{)}^{1/2+\gamma }\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}}\ge c\right)& & \end{array}$$

$$\begin{array}{ccc}& \le & C_{\circ \bullet }n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}{\sum }_{h=n\sigma (\mathbf{p}{)}^{\xi }}\sigma (\mathbf{p}{)}^{n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}}P\left({sup}_{n\sigma (\mathbf{p}{)}^{\xi }\le l\le h}\frac{\left|{\sum }_{i=\left[\right(h-l)/2+1]}\sigma (\mathbf{p}{)}^{[h/2+1]}X\sigma (\mathbf{p}{)}_{k,j}^{\circ }\left(i\right)-\frac{\mu \circ \left(k\right)}{m_{\circ }}\left(\left[\frac{h}{2}+1\right]-\left[\frac{h-l}{2}+1\right]\right)\right|}{\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}\left(\left[\frac{h}{2}+1\right]-\left[\frac{h-l}{2}+1\right]\right)\sigma (\mathbf{p}{)}^{1/2+\gamma }}\ge c\right)\end{array}$$

$$\begin{array}{ccc}& \le & 2C_{\circ \bullet }n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}{\sum }_{h=n\sigma (\mathbf{p}{)}^{\xi }}\sigma (\mathbf{p}{)}^{n\sigma (\mathbf{p}{)}^{1/2+\gamma /2}}hexp(-2c\sigma (\mathbf{p}{)}^{2}n\sigma (\mathbf{p}{)}^{2\xi \gamma })\le 2C_{\circ \bullet }n\sigma (\mathbf{p}{)}^{3/2+3\gamma /2}exp(-n\sigma (\mathbf{p}{)}^{2\gamma \xi })\end{array}$$

and this gives the result, using the same method as in the preceding lemma and choosing $c$  small enough. $\square$  3 CONVERGENCE OF NORMALIZED LABELED FORESTS

3.4 Finite-dimensional convergence

The first step in the proof of Theorem  3 is the following

Proposition 4 Suppose that the pair $(\mu \circ ,\mu \bullet )$  satisfies $\left(H_1\right)$  , and that the displacements distribution $\nu \sigma (\mathbf{p}{)}^{\bullet }$  and $\nu \sigma (\mathbf{p}{)}^{\circ }$  are centered.

Suppose moreover that $${max}_{1\le j\le k}\left({\Sigma }_{k,j}\sigma \right(\mathbf{p}{)}^{\circ }\vee {\Sigma }_{k,j}\sigma (\mathbf{p}{)}^{\bullet })\sigma (\mathbf{p}{)}^2=O(k\sigma (\mathbf{p}{)}^D),$$  for some $D>0$  . Then the convergence of finite-dimensional marginals holds in Theorem  3 .

Notice that this statement shows that the finite-dimensional convergence holds even without the extra $4+\varepsilon$  moment hypothesis. Also, note that under the hypothesis of the proposition, the variance $\Sigma$  associated with the limiting process is finite, because $\mu \circ ,\mu \bullet$  have small exponential moments.

Let us give the intuition for the one-dimensional convergence. By using Skorokhod’s representation theorem, we may assume that we are working in a new probability space on which all the discrete forests $\left({\mathcal{ℱ}}_n\right)$  are living, and such that the convergence of $\left(n\sigma \right(\mathbf{p}{)}^{-1/2}\left(H\sigma \right(\mathbf{p}{)}_{ns}^{{\mathcal{ℱ}}_n},\Lambda \sigma (\mathbf{p}{)}_{ns}^{{\mathcal{ℱ}}_n}),s\ge 0)$  to $\left(\right(2\overline{\sigma }\sigma (\mathbf{p}{)}^{-1}|B_s|,\overline{\sigma }L\sigma (\mathbf{p}{)}_s^0),s\ge 0)$  is almost-sure. In the remaining of the section, it is implicit that we are working on this new probability space, and all the probabilities are taken conditionally on $B\sigma (\mathbf{p}{)}^{\left(\overline{\sigma }\right)}=2\overline{\sigma }\sigma (\mathbf{p}{)}^{-1}\left|B\right|$  . We write simply $\mathcal{ℱ}$  instead of ${\mathcal{ℱ}}_n$  .

Fix $s\ge 0$  . If $u=u\left(\right[ns\left]\right)$  , we can rewrite

$$\begin{array}{c}R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}={\sum }_{k\ge 1}{\sum }_{1\le j\le k}\left({\sum }_{l=1}\sigma (\mathbf{p}{)}^{a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }}Y\sigma (\mathbf{p}{)}_{k,j}^{\circ }\left(l\right)+{\sum }_{l=1}\sigma (\mathbf{p}{)}^{a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }}Y\sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left(l\right)\right),\end{array}$$

(18)

where the variables $Y\sigma (\mathbf{p}{)}_{k,j}^{\circ }(l),Y\sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left(l\right)$  are all independent, and independent of $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }$  and $a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }$  , with law the $j$  -th marginal of $\nu \sigma (\mathbf{p}{)}_k^{\circ }$  and $\nu \sigma (\mathbf{p}{)}_k^{\bullet }$  respectively.

Since $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }$  is approximately $\mu \circ \left(k\right)\left|u\right|/\left(2m_{\circ }\right)$  (with similar estimate for $a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }$  ), and since $\left|u\right|$  is approximately $n\sigma (\mathbf{p}{)}^{1/2}B\sigma (\mathbf{p}{)}_s^{\left(\overline{\sigma }\right)}$  , it is expected that $n\sigma (\mathbf{p}{)}^{-1/4}R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}$  converges to a centered Gaussian law with variance $$\frac{B\sigma (\mathbf{p}{)}_s^{\left(\overline{\sigma }\right)}}{2}{\sum }_{k\ge 1}\left[\frac{\mu \circ \left(k\right)}{m_{\circ }}{\sum }_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ }\left)\sigma \right(\mathbf{p}{)}^2+\frac{\mu \bullet \left(k\right)}{m_{\bullet }}{\sum }_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2\right]=\Sigma \sigma (\mathbf{p}{)}^{2}B\sigma (\mathbf{p}{)}_s^{\left(\overline{\sigma }\right)},$$  which is what is wanted. Let us now proceed to the rigorous proof. We start with a

Lemma 11 Suppose $\left(H_1\right)$  and that ${max}_{1\le j\le k}\left(M\sigma \right(\mathbf{p}{)}_{k,j,p}^{\circ }\vee M\sigma (\mathbf{p}{)}_{k,j,p}^{\bullet })=O\left(k\sigma \right(\mathbf{p}{)}^D)$  as $k\to \infty$  , for some $p>1$  and $D>0$  . Then for every fixed $s$  , $$n\sigma (\mathbf{p}{)}^{-1/4}\left|R_{ns}\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}-R_{\left[ns\right]}\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}\right|\to 0$$  in probability as $n\to \infty$  .

Proof. By definition of $R\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}$  the r.v. $R_{k-1}\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}-R_k\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}$  is a sum of at most $\left|H_k\sigma \right(\mathbf{p}{)}^{\mathcal{ℱ}}-H_{k-1}\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}|+2$  random variables corresponding to the variables $Y$  that are present on the path $\left[\right[u(k-1),u\left(k\right)\left]\right]$  . Let $\mathcal{A}\sigma (\mathbf{p}{)}_r^n$  be the event $$\mathcal{A}\sigma (\mathbf{p}{)}_r^n=\left\{{sup}_{1\le k\le \left[An\right]}d\left(u\right(k-1),u(k\left)\right)>rlogn\right\}.3\mathit{C}\mathit{O}\mathit{N}\mathit{V}\mathit{E}\mathit{R}\mathit{G}\mathit{E}\mathit{N}\mathit{C}\mathit{E}\mathit{O}\mathit{F}\mathit{N}\mathit{O}\mathit{R}\mathit{M}\mathit{A}\mathit{L}\mathit{I}\mathit{Z}\mathit{E}\mathit{D}\mathit{L}\mathit{A}\mathit{B}\mathit{E}\mathit{L}\mathit{E}\mathit{D}\mathit{F}\mathit{O}\mathit{R}\mathit{E}\mathit{S}\mathit{T}\mathit{S}$$  For any $r_1>0$  , there exists $r_2$  such that

$$\begin{array}{c}{\mathbb{P}}_{\infty }(\mathcal{A}\sigma (\mathbf{p}{)}_{r_2}^n)=O(n\sigma (\mathbf{p}{)}^{-r_1}).\end{array}$$

(19)

Indeed, consider a forest with $n\sigma (\mathbf{p}{)}^{1/2+\gamma }$  trees for some $\gamma >0$  . A negative jump with size at least $\delta$  in the height process corresponds to a run of at least $\delta$  nodes that have at least one child, when exploring the forest in reverse depth-first search. Since $\mu \circ \left(0\right)+\mu \bullet \left(0\right)>0$  (because $m_{\circ }{m}_{\bullet }=1$  ), one sees that runs of consecutive children having at least one child is smaller than twice a geometrical random variable with parameter $(1-\mu \circ (0\left)\right)(1-\mu \bullet (0\left)\right)$  . Now, it is easy to prove that the maximum of $\left[An\right]$  i.i.d. such geometric r.v. satisfies ( 19 ). Using ( 11 ) for $r$  large enough, the event $${\mathcal{ℬ}}_r\sigma (\mathbf{p}{)}^n=\left\{sup\{c_{u\left(k\right)},k\le An\}\le rlogn\right\}\cap \mathcal{A}\sigma (\mathbf{p}{)}_r^n,$$  satisfies ${\mathbb{P}}_{\infty }\left({\mathcal{ℬ}}_r\sigma \right(\mathbf{p}{)}^n)\to 1$  when $n$  goes to infinity. Using the hypothesis, ${\mathbb{E}}_{\infty }\left(\right|R_{k-1}-R_k\left|\sigma \right(\mathbf{p}{)}^p\left|{\mathcal{ℬ}}_r\sigma \right(\mathbf{p}{)}^n)=O(log\sigma (\mathbf{p}{)}^{K}n)$  for a certain $K>0$  , and this concludes the proof. $\square$  Proof of Proposition  4 . Let us prove the one-dimensional convergence. Thanks to Lemma  11 , we restrict our attention to the values of $s$  , such that $ns$  is an integer. We use a truncation procedure, that is we choose $C$  large and write $$R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}=R_{ns}\sigma (\mathbf{p}{)}^C+\tilde{R}\sigma (\mathbf{p}{)}_{ns}^C,$$  where $R\sigma (\mathbf{p}{)}_{ns}^C,\tilde{R}\sigma (\mathbf{p}{)}_{ns}^C$  are the sum of ( 18 ) with $k$  ranging respectively from $1$  to $C$  and from $C+1$  to $\infty$  . Assume for a moment that for every $\varepsilon >0$  ,

$$\begin{array}{c}{lim}_{B\to \infty }{limsup}_{n\to \infty }{\mathbb{P}}_{\infty }\left(\right|\tilde{R}\sigma (\mathbf{p}{)}_{ns}^C|>n\sigma (\mathbf{p}{)}^{1/4}\varepsilon )=0.\end{array}$$

(20)

In this case, we can use Lemma  9 together with the central limit theorem as $n\to \infty$  in the first sum conditionally on $B\sigma (\mathbf{p}{)}^{\left(\overline{\sigma }\right)}$  , to obtain that a.s. $R\sigma (\mathbf{p}{)}_{ns}^C/n\sigma (\mathbf{p}{)}^{1/4}$  converges in distribution as $n\to \infty$  to a centered Gaussian variable with variance equal to the partial sum $${\Sigma }_C\sigma (\mathbf{p}{)}^2=\frac{B\sigma (\mathbf{p}{)}_s^{\left(\overline{\sigma }\right)}}{2}{\sum }_{1\le k\le C}\left[\frac{\mu \circ \left(k\right)}{m_{\circ }}{\sum }_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ }\left)\sigma \right(\mathbf{p}{)}^2+\frac{\mu \bullet \left(k\right)}{m_{\bullet }}{\sum }_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2\right],$$  which converges to a normal variable with claimed variance as $C\to \infty$  . Now still supposing ( 20 ) we write, for $\varepsilon >0$  $$\left|{\mathbb{P}}_{\infty }\left(R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}>n\sigma (\mathbf{p}{)}^{1/4}x\right)-{\mathbb{P}}_{\infty }\left(R_{ns}\sigma (\mathbf{p}{)}^C+{\tilde{R}}_{ns}\sigma (\mathbf{p}{)}^C>n\sigma (\mathbf{p}{)}^{1/4}x,|{\tilde{R}}_{ns}\sigma (\mathbf{p}{)}^C|\le \varepsilon n\sigma (\mathbf{p}{)}^{1/4}\right)\right|\le {\mathbb{P}}_{\infty }\left(\right|{\tilde{R}}_{ns}\sigma (\mathbf{p}{)}^C|>\varepsilon n\sigma (\mathbf{p}{)}^{1/4})\le \varepsilon ,$$  as soon as $C$  , then $n$  are chosen large enough. Therefore $${\mathbb{P}}_{\infty }\left(\frac{R_{ns}\sigma (\mathbf{p}{)}^C}{n\sigma (\mathbf{p}{)}^{1/4}}>x+\varepsilon \right)-2\varepsilon \le {\mathbb{P}}_{\infty }\left(\frac{R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}>x\right)\le {\mathbb{P}}_{\infty }\left(\frac{R_{ns}\sigma (\mathbf{p}{)}^C}{n\sigma (\mathbf{p}{)}^{1/4}}>x-\varepsilon \right)+\varepsilon ,3\mathit{C}\mathit{O}\mathit{N}\mathit{V}\mathit{E}\mathit{R}\mathit{G}\mathit{E}\mathit{N}\mathit{C}\mathit{E}\mathit{O}\mathit{F}\mathit{N}\mathit{O}\mathit{R}\mathit{M}\mathit{A}\mathit{L}\mathit{I}\mathit{Z}\mathit{E}\mathit{D}\mathit{L}\mathit{A}\mathit{B}\mathit{E}\mathit{L}\mathit{E}\mathit{D}\mathit{F}\mathit{O}\mathit{R}\mathit{E}\mathit{S}\mathit{T}\mathit{S}$$  and the result is obtained by taking the sup and inf limits as $n\to \infty$  , then letting $C\to \infty$  and finally $\varepsilon \to 0$  .

It remains to prove ( 20 ). Let ${\mathcal{ℬ}}_n$  be the union of the three events $$\left\{{sup}_{k\ge n,u\prec u\left(An\right)}{a}_{u,k}\ge 1\right\},\left\{{max}_{\{0,\dots ,[nt\left]\right\}}H\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}\ge 2n\sigma (\mathbf{p}{)}^{1/2}{sup}_{[0,t]}B\sigma (\mathbf{p}{)}^{\left(\overline{\sigma }\right)}\right\},$$  $$\left\{{sup}_{k\ge 1,1\le j\le k,u\prec u\left(An\right)}\frac{\left|a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{2m_{\circ }}|u|\right|}{\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}}\vee \frac{\left|a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }-\frac{\mu \bullet \left(k\right)}{2m_{\bullet }}|u|\right|}{\sqrt{\frac{\mu \bullet \left(k\right)}{m_{\bullet }}}}\ge n\sigma (\mathbf{p}{)}^{3/8}\right\}.$$  Then $${\mathbb{P}}_{\infty }\left(\tilde{R}\sigma (\mathbf{p}{)}_{ns}^C>n\sigma (\mathbf{p}{)}^{1/4}\varepsilon \right)\le {\mathbb{P}}_{\infty }\left({\mathcal{ℬ}}_n\right)+{\mathbb{P}}_{\infty }\left(\tilde{R}\sigma (\mathbf{p}{)}_{ns}^C>n\sigma (\mathbf{p}{)}^{1/4}\varepsilon ,{\mathcal{ℬ}}_n\sigma (\mathbf{p}{)}^c\right)$$  The first term of the right-hand side goes to $0$  as $n\to \infty$  by Lemmæ  7 ,  9 . By first conditioning on the $a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ },a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }$  , the second term can be rewritten and bounded by 3 CONVERGENCE OF NORMALIZED LABELED FORESTS

$$\begin{array}{ccc}{\mathbb{P}}_{\infty }\left(\left|{\sum }_{C\le k\le n}{\sum }_{1\le j\le k}\left({\sum }_{l=1}\sigma (\mathbf{p}{)}^{a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }}Y\sigma (\mathbf{p}{)}_{j,k}^{\circ }\left(l\right)+{\sum }_{l=1}\sigma (\mathbf{p}{)}^{a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }}Y\sigma (\mathbf{p}{)}_{j,k}^{\bullet }\left(l\right)\right)\right|>n\sigma (\mathbf{p}{)}^{1/4}\varepsilon ,{\mathcal{ℬ}}_n\sigma (\mathbf{p}{)}^c\right)& & \end{array}$$

$$\begin{array}{ccc}& \le & \frac{1}{\varepsilon \sigma (\mathbf{p}{)}^{2}n\sigma (\mathbf{p}{)}^{1/2}}E\left[{\sum }_{k=C}\sigma (\mathbf{p}{)}^n{\sum }_{1\le j\le k}(a\sigma (\mathbf{p}{)}_{u,k,j}^{\circ }(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ })\sigma (\mathbf{p}{)}^2+a\sigma (\mathbf{p}{)}_{u,k,j}^{\bullet }(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2)1_{{\mathcal{ℬ}}_n\sigma (\mathbf{p}{)}^c}\right]\end{array}$$

$$\begin{array}{ccc}& \le & \frac{2B\sigma (\mathbf{p}{)}_s^{\left(\overline{\sigma }\right)}}{2\varepsilon \sigma (\mathbf{p}{)}^2}{\sum }_{k=C}\sigma (\mathbf{p}{)}^n\left(k\frac{\mu \circ \left(k\right)}{m_{\circ }}{max}_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ }\left)\sigma \right(\mathbf{p}{)}^2+k\frac{\mu \bullet \left(k\right)}{m_{\bullet }}{max}_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2\right)\end{array}$$

$$\begin{array}{ccc}& & +\frac{1}{\varepsilon \sigma (\mathbf{p}{)}^{2}n\sigma (\mathbf{p}{)}^{1/8}}{\sum }_{k=C}\sigma (\mathbf{p}{)}^n\left(\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}k{max}_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ }\left)\sigma \right(\mathbf{p}{)}^2+\sqrt{\frac{\mu \bullet \left(k\right)}{m_{\bullet }}}k{max}_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2\right)\end{array}$$

By the assumption made on variances, and the fact that $\mu \circ ,\mu \bullet$  have small exponential moments, the second term converges to $0$  while the first converges to $$B\sigma (\mathbf{p}{)}_s^{\left(\overline{\sigma }\right)}\varepsilon \sigma (\mathbf{p}{)}^{-2}{\sum }_{k\ge C}\left(k\frac{\mu \circ \left(k\right)}{m_{\circ }}{max}_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\circ }\left)\sigma \right(\mathbf{p}{)}^2+k\frac{\mu \bullet \left(k\right)}{m_{\bullet }}{max}_{1\le j\le k}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2\right),$$  and this does converge to $0$  as $C\to \infty$  .

The case of multi-dimensional convergence is similar, although some extra care must be taken because of nodes, where dependencies can occur. We only sketch the proof, referring the reader to [14] for more details. Let $0\le s_1<s_2<\dots <s_k$  . Also, notice that for any forest $\mathbf{f}$  and $k<k^{\prime }$  , the distance $d_{\mathbf{f}}\left(u\right(k),u(k^{\prime }\left)\right)$  satisfies $\left|d_{\mathbf{f}}\right(u\left(k\right),u\left(k^{\prime }\right))-(H\sigma (\mathbf{p}{)}_k^{\mathbf{f}}+H\sigma (\mathbf{p}{)}_{k^{\prime }}^{\mathbf{f}}-2{min}_{k\le l\le k^{\prime }}H\sigma (\mathbf{p}{)}_l^{\mathbf{f}})|\le 2$  (it is in fact always equal to 2 except when $u\left(k\right)$  is an ancestor of $u\left(k^{\prime }\right)$  ). It follows that up to forgetting two steps in each branch, the lengths of branches of the subforest of $\mathbf{f}$  spanned by the root and $u\left(\right[n{s}_i\left]\right),1\le i\le k$  (a branch being a maximal chain of neighboring vertices with degree $\le 2$  ), are determined by the vector $$\left(H_{\left[n{s}_1\right]}\sigma \right(\mathbf{p}{)}^{\mathbf{f}},{\check{H}}_{\left[n{s}_1\right],\left[n{s}_2\right]}\sigma (\mathbf{p}{)}^{\mathbf{f}},H_{\left[n{s}_2\right]}\sigma (\mathbf{p}{)}^{\mathbf{f}},\dots ,{\check{H}}_{\left[n{s}_{k-1}\right],\left[n{s}_k\right]}\sigma (\mathbf{p}{)}^{\mathbf{f}},H_{\left[n{s}_k\right]}\sigma (\mathbf{p}{)}^{\mathbf{f}}).$$  Now, the proof of the one-dimensional convergence shows that the spatial displacements along each branch converge to independent normal variables with respective variances $\Sigma \sigma (\mathbf{p}{)}^{2}l$  , where $l$  is the limiting renormalized length of the branch of the Continuum Random Tree, as the only dependent variables in the walks appear only at the nodes of the subtrees, which number is bounded by $2k$  . This ends the proof. $\square$  3 CONVERGENCE OF NORMALIZED LABELED FORESTS

3.5 Tightness

To end the proof of Theorem  3 , we need

Proposition 5 If assumptions $\left(H_1\right)$  , $\left(H_2\right)$  and $\left(H_3\right)$  are fulfilled, the sequence of laws of the processes $\left(n\sigma \right(\mathbf{p}{)}^{-1/4}R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}},s\ge 0),n\ge 1$  is tight in $C\left(\right[0,\infty \left)\right)$  .

Proof. Our way of proceeding follows closely the arguments of [21, 14] . We know from Corollary  2 that for every $\alpha \in (0,1/2)$  , and $A,C_1>0$  , with $P_{\infty }$  -probability arbitrarily close to $1$  we have for all $n$  ,

$$\begin{array}{c}\left|H\sigma \right(\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}|\le C_{1}n\sigma (\mathbf{p}{)}^{1/2}|s-t\left|\sigma \right(\mathbf{p}{)}^{\alpha }\end{array}$$

(21)

for all $s,t\le A$  . We let ${\mathcal{ℬ}}_n$  be the intersection of the corresponding event and of the events $$\left\{{max}_{u\prec u\left(An\right),k\ge Clogn}{a}_{k,u}=0\right\},$$  $$\left\{{sup}_{u\prec u\left(An\right),k\ge 1,1\le j\le k,n\sigma (\mathbf{p}{)}^{\xi }\le l\le |u|}\frac{\left|a\sigma (\mathbf{p}{)}_{u,l,k,j}^{\circ }-\frac{\mu \circ \left(k\right)}{2m_{\circ }}l\right|}{l\sigma (\mathbf{p}{)}^{1/2+\gamma }\sqrt{\frac{\mu \circ \left(k\right)}{m_{\circ }}}}\vee \frac{\left|a\sigma (\mathbf{p}{)}_{u,l,k,j}^{\bullet }-\frac{\mu \bullet \left(k\right)}{2m_{\bullet }}l\right|}{l\sigma (\mathbf{p}{)}^{1/2+\gamma }\sqrt{\frac{\mu \bullet \left(k\right)}{m_{\bullet }}}}\le 1\right\}$$  where $C>0$  is chosen so that the probability of ${\mathcal{ℬ}}_n$  stays $\ge 1-\lambda$  for any prescribed $\lambda >0$  , and $\xi >0$  will be fixed later.

Our goal is to show that with high probability, there exists $C_2,\beta >0$  such that for every $s,t\le A$  , and $n$  large enough, $$\left|R\sigma \right(\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}|\le C_{2}n\sigma (\mathbf{p}{)}^{1/4}|s-t\left|\sigma \right(\mathbf{p}{)}^{\beta }.$$  Notice that it suffices to show this property for all $n$  large and $s\ne t$  such that $ns$  and $nt$  are integers, which we suppose from now on.

Under ${\mathcal{ℬ}}_n$  , the number of variables to sum between $u\left(ns\right)$  and $u\left(nt\right)$  is the distance ${\ell }_n(s,t)$  between these nodes, where $\left|{\ell }_n\right(s,t)-(H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}+H\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}-2\check{H}\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}(ns,nt\left)\right)|\le 2$  , so ${\ell }_n(s,t)$  is bounded by $C_{3}n\sigma (\mathbf{p}{)}^{1/2}|s-t\left|\sigma \right(\mathbf{p}{)}^{\alpha }$  uniformly on $s,t\le A$  (with $ns,nt$  integers) as soon as ( 21 ) holds.

Let $u(ns,nt)$  be the highest common ancestor of $u\left(ns\right),u\left(nt\right)$  . Let also $j\left(s\right),j\left(t\right)$  be such that $u\left(ns\right),u\left(nt\right)$  respectively belong to the fringe subtrees $T_{u(ns,nt)j\left(s\right)},T_{u(ns,nt)j\left(t\right)}$  . Then we can rewrite 3 CONVERGENCE OF NORMALIZED LABELED FORESTS

$$\begin{array}{ccc}R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}& =& (Y_{u(ns,nt)j\left(s\right)}-Y_{u(ns,nt)j\left(t\right)})\end{array}$$

$$\begin{array}{ccc}& & +{\sum }_{k\ge 1}{\sum }_{1\le j\le k}\left({\sum }_{l=1}\sigma (\mathbf{p}{)}^{a\sigma (\mathbf{p}{)}_{s,t,k,j}^{\circ }}Y\sigma (\mathbf{p}{)}_{k,j}^{\circ }\left(l\right)+{\sum }_{l=1}\sigma (\mathbf{p}{)}^{a\sigma (\mathbf{p}{)}_{s,t,k,j}^{\bullet }}Y\sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left(l\right)\right)\end{array}$$

$$\begin{array}{ccc}& & -{\sum }_{k\ge 1}{\sum }_{1\le j\le k}\left({\sum }_{l=1}\sigma (\mathbf{p}{)}^{b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\circ }}Z\sigma (\mathbf{p}{)}_{k,j}^{\circ }\left(l\right)+{\sum }_{l=1}\sigma (\mathbf{p}{)}^{b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\bullet }}Z\sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left(l\right)\right),\end{array}$$

where the terms of the sums are all independent. Here, $a\sigma (\mathbf{p}{)}_{s,t,k,j}^{\circ }$  is the number of nodes in $\left]\right]u(s,t),u\left(s\right)\left]\right]$  with even height, with $k$  children and for which $u\left(s\right)$  is in the $j$  -th fringe subtree, and $b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\circ }$  is the same but for $\left]\right]u(s,t),u\left(t\right)\left]\right]$  , and similarly for $a\sigma (\mathbf{p}{)}_{s,t,k,j}^{\bullet },b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\bullet }$  , and the $Y\sigma (\mathbf{p}{)}_{k,j}^{\circ }(l),Z\sigma (\mathbf{p}{)}_{k,j}^{\circ }\left(l\right)$  are independent conditionally on the $a,b$  , with law the $j$  -th marginal of $\nu \sigma (\mathbf{p}{)}_k^{\circ }$  , and so on. Then, using ( 32 ), we get for $p=4+\varepsilon$  3 CONVERGENCE OF NORMALIZED LABELED FORESTS

$$\begin{array}{ccc}{\mathbb{E}}_{\infty }\left[\left|R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}\right|\sigma (\mathbf{p}{)}^p|{\mathcal{ℬ}}_n,(a,b)\right]& & \end{array}$$

$$\begin{array}{ccc}& \le & C\left(p\right){\ell }_n(s,t)\sigma (\mathbf{p}{)}^{p/2-1}\left(\begin{array}{c}{\mathbb{E}}_{\infty }\left[\right|Y_{u(ns,nt)j\left(s\right)}-Y_{u(s,t)j\left(t\right)}\left|\sigma \right(\mathbf{p}{)}^p]\\ +{\sum }_{1\le k\le Clogn}{\sum }_{1\le j\le k}\left(a\sigma \right(\mathbf{p}{)}_{s,t,k,j}^{\circ }+b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\circ })M\sigma (\mathbf{p}{)}_{k,j}^{\circ }\\ +{\sum }_{1\le k\le Clogn}{\sum }_{1\le j\le k}\left(a\sigma \right(\mathbf{p}{)}_{s,t,k,j}^{\bullet }+b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\bullet })M\sigma (\mathbf{p}{)}_{k,j}^{\bullet }\end{array}\right)1_{{\mathcal{ℬ}}_n}\end{array}$$

$$\begin{array}{ccc}& \le & C\left(p\right)C_4{\ell }_n(s,t)\sigma (\mathbf{p}{)}^{p/2-1}\left(\begin{array}{c}2\sigma (\mathbf{p}{)}^p{c}_{u(s,t)}\sigma (\mathbf{p}{)}^D\\ +{\sum }_{1\le k\le Clogn}k\sigma (\mathbf{p}{)}^D{\sum }_{1\le j\le k}(a\sigma (\mathbf{p}{)}_{s,t,k,j}^{\circ }+b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\circ })\\ +{\sum }_{1\le k\le Clogn}k\sigma (\mathbf{p}{)}^D{\sum }_{1\le j\le k}(a\sigma (\mathbf{p}{)}_{s,t,k,j}^{\bullet }+b\sigma (\mathbf{p}{)}_{s,t,k,j}^{\bullet })\end{array}\right)1_{{\mathcal{ℬ}}_n},\end{array}$$

where $C_4$  is such that ${max}_{1\le j\le k}\left(M\sigma \right(\mathbf{p}{)}_{k,j}^{\circ }\vee M\sigma (\mathbf{p}{)}_{k,j}^{\bullet })\le C_{4}k\sigma (\mathbf{p}{)}^D$  for some $D>0$  and all $k\ge 1$  . Let now $${\mathcal{C}}_n=\left\{\right|u\left(s\right)|-|u(s,t)|\le n\sigma (\mathbf{p}{)}^{\xi }\},{\mathcal{D}}_n=\{\left|u\right(t\left)\right|-\left|u\right(s,t\left)\right|\le n\sigma (\mathbf{p}{)}^{\xi }\},$$  for the same $\xi$  as in the definition of ${\mathcal{ℬ}}_n$  . Since ${\ell }_n(s,t)=\left|u\right(s\left)\right|-\left|u\right(s,t\left)\right|+\left|u\right(t\left)\right|-\left|u\right(s,t\left)\right|$  , we deduce $${\mathbb{E}}_{\infty }\left[\left|\frac{R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}\right|\sigma (\mathbf{p}{)}^p|{\mathcal{ℬ}}_n,{\mathcal{C}}_n,{\mathcal{D}}_n\right]\le C_{5}n\sigma (\mathbf{p}{)}^{-p/4}{\ell }_n(s,t\left)\sigma \right(\mathbf{p}{)}^{p/2}(logn)\sigma (\mathbf{p}{)}^D{1}_{{\mathcal{C}}_n,{\mathcal{D}}_n}\le C_{6}n\sigma (\mathbf{p}{)}^{p(\xi /2-1/4)}(logn)\sigma (\mathbf{p}{)}^D,$$  since the sum of all $a,b$  plus $1$  is ${\ell }_n(s,t)$  . We then choose (recall $p=4+\varepsilon$  ) $\xi$  so that $(4+\varepsilon )(\xi /2-1/4)<-1$  , and since $ns$  and $nt$  are supposed to be distinct integers $|s-t|\ge 1/n$  , this gives that $${\mathbb{E}}_{\infty }\left[\left|\frac{R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}\right|\sigma (\mathbf{p}{)}^p|{\mathcal{ℬ}}_n,{\mathcal{C}}_n,{\mathcal{D}}_n\right]\le C_6|s-t|\sigma (\mathbf{p}{)}^{1+\eta },$$  for some $\eta >1$  and $n$  large enough.

Next, we have, applying the equality satisfied in ${\mathcal{ℬ}}_n$  to $u=u\left(s\right),l=\left|u\right(s\left)\right|-\left|u\right(s,t\left)\right|$  and $u=u\left(t\right),l=\left|u\right(t\left)\right|-\left|u\right(s,t\left)\right|$  , which is valid under ${\mathcal{C}}_n\sigma (\mathbf{p}{)}^c\cap {\mathcal{D}}_n\sigma (\mathbf{p}{)}^c$  , 3 CONVERGENCE OF NORMALIZED LABELED FORESTS

$$\begin{array}{ccc}{\mathbb{E}}_{\infty }\left[\left|\frac{R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}\right|\sigma (\mathbf{p}{)}^p|{\mathcal{ℬ}}_n,{\mathcal{C}}_n\sigma (\mathbf{p}{)}^c,{\mathcal{D}}_n\sigma (\mathbf{p}{)}^c\right]& & \end{array}$$

$$\begin{array}{ccc}& \le & C_{7}n\sigma (\mathbf{p}{)}^{-p/4}{\ell }_n(s,t\left)\sigma \right(\mathbf{p}{)}^{p/2-1}{\sum }_{k\ge 1}k\sigma (\mathbf{p}{)}^{D+1}\left((\mu \circ (k)+\mu \bullet (k\left)\right){\ell }_n(s,t)+(\sqrt{\mu \circ \left(k\right)}+\sqrt{\mu \bullet \left(k\right)}){\ell }_n(s,t)\sigma (\mathbf{p}{)}^{1/2+\gamma }\right)1_{{\mathcal{ℬ}}_n}\end{array}$$

$$\begin{array}{ccc}& \le & \left(C_{8}n\sigma (\mathbf{p}{)}^{-p/4}{\ell }_n(s,t\left)\sigma \right(\mathbf{p}{)}^{p/2}+C_{9}n\sigma (\mathbf{p}{)}^{-p/4}{\ell }_n(s,t\left)\sigma \right(\mathbf{p}{)}^{p/2-1/2+\gamma }\right)1_{{\mathcal{ℬ}}_n}\end{array}$$

$$\begin{array}{ccc}& \le & C_{10}|s-t|\sigma (\mathbf{p}{)}^{\alpha p/2}+C_{11}n\sigma (\mathbf{p}{)}^{-1/4+\gamma /2}|s-t|\sigma (\mathbf{p}{)}^{\alpha p/2-\alpha /2+\alpha \gamma }\end{array}$$

$$\begin{array}{ccc}& \le & C_{10}|s-t|\sigma (\mathbf{p}{)}^{\alpha p/2}+C_{11}|s-t\left|\sigma \right(\mathbf{p}{)}^{\alpha p/2+1/4-\alpha /2+\alpha \gamma -\gamma /2}\end{array}$$

$$\begin{array}{ccc}& \le & C_{12}|s-t|\sigma (\mathbf{p}{)}^{1+{\eta }^{\prime }}\end{array}$$

for $\alpha$  chosen close enough to $1/2$  and $\gamma$  to $0$  and for some ${\eta }^{\prime }>0$  .

Finally, we similarly estimate 3 CONVERGENCE OF NORMALIZED LABELED FORESTS

$$\begin{array}{ccc}{\mathbb{E}}_{\infty }\left[\left|\frac{R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}\right|\sigma (\mathbf{p}{)}^p|{\mathcal{ℬ}}_n,{\mathcal{C}}_n\sigma (\mathbf{p}{)}^c,{\mathcal{D}}_n\right]& & \end{array}$$

$$\begin{array}{ccc}& \le & \left(C_{8}n\sigma (\mathbf{p}{)}^{-p/4}{\ell }_n(s,t\left)\sigma \right(\mathbf{p}{)}^{p/2}+C_{9}n\sigma (\mathbf{p}{)}^{-p/4}{\ell }_n(s,t\left)\sigma \right(\mathbf{p}{)}^{p/2-1/2+\gamma }\right)1_{{\mathcal{ℬ}}_n}+C_{6}n\sigma (\mathbf{p}{)}^{p(\xi /2-1/4)}(logn\left)\sigma \right(\mathbf{p}{)}^D,\end{array}$$

and this is bounded by quantities similar as above, and things are similar for conditioning by ${\mathcal{C}}_n,{\mathcal{D}}_n\sigma (\mathbf{p}{)}^c$  . Finally, $${\mathbb{E}}_{\infty }\left[\left|\frac{R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-R\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}}{n\sigma (\mathbf{p}{)}^{1/4}}\right|\sigma (\mathbf{p}{)}^{4+\varepsilon }|{\mathcal{ℬ}}_n\right]\le C^{\prime }|s-t|\sigma (\mathbf{p}{)}^{1+{\eta }^{\prime \prime }},$$  for some $C^{\prime },{\eta }^{\prime \prime }>0$  , and since the probability of ${\mathcal{ℬ}}_n$  can be chosen as close of $1$  as wanted, this implies by standard considerations that the $(1+{\eta }^{\prime \prime })/(4+\varepsilon )$  -Holder norm on compacts of the process $\left(n\sigma \right(\mathbf{p}{)}^{-1/4}R\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}},s\ge 0)$  is tight, and this implies the tightness of this sequence of processes.

This ends the proof of Proposition  5 , and thus of Theorem  3 . $\square$  3 CONVERGENCE OF NORMALIZED LABELED FORESTS

3.6 Convergence of size conditioned discrete snakes

Lemma 12 If hypothesis $\left(H_1\right)$  is fulfilled, we have $$P\sigma (\mathbf{p}{)}^{\circ }(\left|T\sigma \right(\mathbf{p}{)}^{\circ }|=n)\sim \frac{{\mathsf{h}}_{\circ }}{{\overline{\sigma }}_{\circ }\sqrt{2\pi }}n\sigma (\mathbf{p}{)}^{-3/2},P\sigma (\mathbf{p}{)}^{\circ }\left(\right|T\sigma (\mathbf{p}{)}^{\bullet }|=n)\sim \frac{{\mathsf{h}}_{\bullet }{m}_{\circ }}{{\overline{\sigma }}_{\bullet }\sqrt{2\pi }}n\sigma (\mathbf{p}{)}^{-3/2},$$  along values of $n$  making these probabilities positive, where ${\mathsf{h}}_{\circ }$  is the span of the law of $\left|T\sigma \right(\mathbf{p}{)}^{\circ }|$  under $P\sigma (\mathbf{p}{)}^{\circ }$  , and ${\mathsf{h}}_{\bullet }$  the span of $\left|T\sigma \right(\mathbf{p}{)}^{\bullet }|$  under $P\sigma (\mathbf{p}{)}^{\circ }$  .

Proof. The first quantity is the probability that the grandfather critical tree ${\overline{T}}_{\circ }$  has $n$  nodes.

This is computed thanks to the Otter-Dwass formula that can be found in [25] and the central local limit theorem (see [26,p.706] ). For the second quantity, write

$$\begin{array}{c}n\sigma (\mathbf{p}{)}^{3/2}P\sigma (\mathbf{p}{)}^{\circ }\left(\right|T\sigma (\mathbf{p}{)}^{\bullet }|=n)={\sum }_{i}n\sigma (\mathbf{p}{)}^{3/2}P\sigma (\mathbf{p}{)}^{\circ }\left(\left|T\sigma \right(\mathbf{p}{)}^{\bullet }|=n|c_{\mathbb{\varnothing }}=i\right)P\sigma (\mathbf{p}{)}^{\circ }(c_{\mathbb{\varnothing }}=i).\end{array}$$

(22)

First, $P\sigma (\mathbf{p}{)}^{\circ }(c_{\mathbb{\varnothing }}=i)=\mu \circ (i)$  . Then, $$n\sigma (\mathbf{p}{)}^{3/2}P\sigma (\mathbf{p}{)}^{\circ }\left(\right|T\sigma (\mathbf{p}{)}^{\bullet }|=n|c_{\mathbb{\varnothing }}=i)=n\sigma (\mathbf{p}{)}^{3/2}P\sigma (\mathbf{p}{)}_i^{\bullet }\left(\right|\mathcal{ℱ}\sigma (\mathbf{p}{)}^{\bullet }|=n)\to i{\mathsf{h}}_{\bullet }/({\overline{\sigma }}_{\bullet }\sqrt{2\pi })$$  thanks to the Otter-Dwass formula applied to the grandfather forest ${\overline{\mathcal{ℱ}}}_{\bullet }$  and the central local limit theorem. To conclude, use Lebesgue dominated convergence theorem in ( 22 ). $\square$  The conditioning argument Let $\left(k\right(i),i\ge 1)$  be a sequence of elements of $\{+\infty ,1,2,3,...\}$  ; let $A_i$  be an event on the set of forests ${\mathbb{F}}_i=\{\mathbf{f}=({\mathbf{t}}_1,...,{\mathbf{t}}_{k\left(i\right)}\left)\right\}$  with $k\left(i\right)$  trees rooted on a $\circ$  -node. For $n$  large enough, under $\left(H_1\right)$  thanks to Lemma  12 , $$\mathbb{P}\sigma (\mathbf{p}{)}_{k\left(i\right)}^{\circ }\left(A_i\left|\right|{\mathbf{t}}_1\sigma (\mathbf{p}{)}^{\bullet }|=n\right)\le cn\sigma (\mathbf{p}{)}^{3/2}{\mathbb{P}}_{k\left(i\right)}\left(A_i\right).$$  For any sequence $(a_i{)}_i$  , $1\le a_i\le k\left(i\right)$  , consider now events of the type $$A_i=\left\{{\sum }_{j=1}\sigma (\mathbf{p}{)}^{a\left(i\right)}g({\mathbf{t}}_j)\ge Z\right\}\text{or}{A}_i=\left\{{sup}_{j=1,...,a\left(i\right)}g\left({\mathbf{t}}_j\right)\ge Z\right\},\text{and}B=\left\{g\right({\mathbf{t}}_1)\ge Z\}$$  for a given non negative function $g$  . We have $$\mathbb{P}\sigma (\mathbf{p}{)}_{k\left(i\right)}^{\circ }\left(B\left|\right|{\mathbf{t}}_1\sigma (\mathbf{p}{)}^{\bullet }|=n\right)\le \mathbb{P}\sigma (\mathbf{p}{)}_{k\left(i\right)}^{\circ }\left(A_i\left|\right|{\mathbf{t}}_1\sigma (\mathbf{p}{)}^{\bullet }|=n\right)\le cn\sigma (\mathbf{p}{)}^{3/2}\mathbb{P}\sigma (\mathbf{p}{)}_{k\left(i\right)}^{\circ }\left(A_i\right).$$  The contents of this paragraph remains unchanged replacing $\left|{\mathbf{t}}_1\sigma \right(\mathbf{p}{)}^{\bullet }|$  by $\left|{\mathbf{t}}_1\sigma \right(\mathbf{p}{)}^{\circ }|$  .

Hence, the probability of an event involving a tree conditioned by its size is controlled by the corresponding event for forests.

Consider $P\sigma (\mathbf{p}{)}^{\circ }$  a critical Galton-Watson distribution on two-type trees. Let $Q\sigma (\mathbf{p}{)}_n^{\circ }$  (resp. $Q\sigma (\mathbf{p}{)}_n^{\bullet }$  ) the probability induced on $\mathbb{T}$  by the conditioning by $\left|T\sigma \right(\mathbf{p}{)}^{\circ }|=n$  (resp.

$\left|T\sigma \right(\mathbf{p}{)}^{\bullet }|=n$  ), whenever these events have positive probability. Formally, $$Q\sigma (\mathbf{p}{)}_n^{\circ }=P\sigma (\mathbf{p}{)}^{\circ }(\cdot |\left|T\sigma \right(\mathbf{p}{)}^{\circ }|=n),Q\sigma (\mathbf{p}{)}_n^{\bullet }=P\sigma (\mathbf{p}{)}^{\circ }(\cdot |\left|T\sigma \right(\mathbf{p}{)}^{\bullet }|=n).$$  Using the conditioning argument and Lemma  8 , we get

Lemma 13 If hypothesis $\left(H_1\right)$  is fulfilled:

$\left(i\right)$  Under $Q\sigma (\mathbf{p}{)}_n^{\circ }$  , $\left|T\right|/n---\to proban1+m_{\circ },$  $\left(ii\right)$  Under $Q\sigma (\mathbf{p}{)}_n^{\bullet }$  , $\left|T\right|/n---\to proban1+m_{\bullet }$  .

3 CONVERGENCE OF NORMALIZED LABELED FORESTS Theorem 4 If assumptions $\left(H_1\right)$  , $\left(H_2\right)$  and $\left(H_3\right)$  are fulfilled, under $Q\sigma (\mathbf{p}{)}_n^{\bullet }$  , (resp. under $Q\sigma (\mathbf{p}{)}_n^{\circ }$  ), the process ${\left(n\sigma (\mathbf{p}{)}^{-1/2}\widehat{H}\sigma (\mathbf{p}{)}_{2\left(\right|T|-1)s}^T,n\sigma (\mathbf{p}{)}^{-1/4}\widehat{R}\sigma (\mathbf{p}{)}_{2\left(\right|T|-1)s}^T\right)}_{s\in [0,1]}$  converges weakly to $${\left(\frac{4}{{\overline{\sigma }}_{\bullet }}{e}_s,\frac{2\Sigma }{\sqrt{{\overline{\sigma }}_{\bullet }}}{r}_s\right)}_{s\in [0,1]},\left(\mathit{r}\mathit{e}\mathit{s}\mathit{p}\mathit{.}{\left(\frac{4}{{\overline{\sigma }}_{\circ }}{e}_s,\frac{2\Sigma }{\sqrt{{\overline{\sigma }}_{\circ }}}{r}_s\right)}_{s\in [0,1]}\right)\mathit{u}\mathit{n}\mathit{d}\mathit{e}\mathit{r}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)},$$  in $C\left(\right[0,1],\mathbb{R}\sigma (\mathbf{p}{)}^2)$  endowed with the topology of uniform convergence.

Remark. The limit in the theorem is, up to a multiplicative constant, the head of the Brownian snake with lifetime process the normalized Brownian excursion. Convergence of discrete snake to the Brownian snake with i.i.d. increment (or that may be dependent between brothers) are proved in [9, 21, 14] . In the two last references, the space of convergence is $\mathbb{H}$  , the space of the head of the Brownian snake : $\mathbb{H}$  is the subspace of $C\left(\right[0,1],\mathbb{R})\times C\left(\right[0,1],[0,+\infty \left[\right)$  of functions $(\zeta ,f)$  that satisfy $\zeta \left(0\right)=\zeta \left(1\right)=0$  and for any $0\le s\le s^{\prime }\le 1,f\left(s\right)=f\left(s^{\prime }\right)\text{if}\zeta \left(s\right)=\zeta \left(s^{\prime }\right)={min}_{s\le u\le s^{\prime }}\zeta \left(u\right)$  . Here, the convergence holds also in $\mathbb{H}$  . As a consequence, thanks to the homeomorphism Theorem of [21] , the convergence in $\left(i\right)$  and $\left(ii\right)$  entails that corresponding two-type discrete snakes, suitably normalized, converge to the Brownian snake with lifetime process the normalized Brownian excursion.

Proof. $\left(i\right)$  Under $Q\sigma (\mathbf{p}{)}_n^{\circ }$  , the grandfather tree ${\overline{T}}_{\circ }$  of $T$  is a single type critical $\overline{\mu }\circ$  -GW tree conditioned to have size $n$  . By Proposition  2 (ii), we have $n\sigma (\mathbf{p}{)}^{-1/2}(H\sigma (\mathbf{p}{)}_{ns}^{{\overline{T}}_{\circ }}{)}_{s\in [0,1]}----\to weaklyn\frac{2}{{\overline{\sigma }}_{\circ }}(e_s{)}_{s\in [0,1]}$  . Now, the total number of nodes in $T$  is, according to Lemma  8 and the conditionning argument, concentrated around $n(1+m_{\circ })$  . The good repartition of $\circ$  -nodes in $T$  gives the results.

$\left(ii\right)$  Under $Q\sigma (\mathbf{p}{)}_n^{\bullet }$  , the total number of nodes in $T$  is concentrated around $n(1+m_{\bullet })$  .

The main difference with the proof of $\left(i\right)$  , if we think in terms of grandfathers forest ${\overline{T}}_{\bullet }$  , is that the conditionning is on the number of nodes in ${\overline{T}}_{\bullet }$  which has a random number of trees.

The first argument to identify the limit is the following : the number of trees in ${\overline{T}}_{\bullet }$  is $c_{\mathbb{\varnothing }}$  ; it converges in distribution when $n\to \infty$  (the arguments are given in the proof of Lemma  12 ).

Now, for any $i$  , if we condition ${\overline{T}}_{\bullet }$  to have $i$  trees and $n$  nodes, the normalized height process ${\left(n\sigma (\mathbf{p}{)}^{-1/2}H\sigma (\mathbf{p}{)}_{ns}^{{\overline{T}}_{\bullet }}\right)}_{s\in [0,1]}$  converges weakly to ${\left(\frac{2}{{\overline{\sigma }}_{\bullet }}{e}_s\right)}_{s\in [0,1]}$  (when $n$  goes to $+\infty$  ). Since the limit is the same for any $i$  , this implies that the limit is the same under the only conditioning by $\left|T\sigma \right(\mathbf{p}{)}^{\bullet }|=n$  .

Let us establish the convergence of the label processes. We review now the arguments used for the convergence of label processes of forests, and shows that they can be extended when conditioning by the size of the tree. First, thanks to the conditioning argument, Lemmæ  2 ,  3 ,  6 ,  7 ,  9 ,  10 and  11 hold under the conditioning by $\left|T_1\sigma \right(\mathbf{p}{)}^{\bullet }|=n$  or $\left|T_1\sigma \right(\mathbf{p}{)}^{\circ }|=n$  and the property proved holds for the conditioned snakes if one takes $A$  large enough. Then one follows line by line the proof of the finite fimensional convergence (in the proof of Proposition  4 we use a Skohorod’s representation space on which $n\sigma (\mathbf{p}{)}^{-1/2}H\sigma (\mathbf{p}{)}_{{\beta }_{\circ }n.}^T$  converges to $4e./{\overline{\sigma }}_{\circ }$  or $n\sigma (\mathbf{p}{)}^{-1/2}H\sigma (\mathbf{p}{)}_{{\beta }_{\bullet }n.}^T$  converges to $4e./{\overline{\sigma }}_{\bullet }$  almost surely, depending on whether we are proving $\left(i\right)$  or $\left(ii\right)$  ). For proving the analogue of Proposition  5 , we only need an extension of ( 21 ). Such a formula is known for critical single type Galton-Watson trees conditioned by the size (simple adaptation of Lemma 1 in [14] ); then it is true for the underlying grandfather tree (or forest). $\square$  4 ASYMPTOTICS FOR MAPS

4 Asymptotics for maps

4 ASYMPTOTICS FOR MAPS

4.1 BDG’s bijection between bipartite maps and mobiles

We present here the construction of Bouttier & al. [7] for seek of completness.

Description of $\Phi$  Consider a rooted pointed map $\mathbf{m}\in {\mathcal{ℳ}}_{n,k}$  , with distinguished node $u$  and root $vw$  . We present the construction of $(\mathbf{t},\ell )=\Phi (\mathbf{m})$  , the rooted labeled mobile associated with $\mathbf{m}$  (see Fig.  7 ).

1) Label each node $x$  of $\mathbf{m}$  by $g\left(x\right)$  , the geodesic distance to $u$  .

2) The construction takes place now in each face, independently : Let $F$  be a face of $\mathbf{m}$  , with degree $2j$  . Add in this face a $\bullet$  -node. Since $\mathbf{m}$  is bipartite, the difference between two consecutive labels around $F$  is $+1$  or $-1$  . Among the $2j$  vertices of $F$  , select the $j$  ones immediately followed by vertices with smaller labels. Add now an edge between the $\bullet$  -node and each of the $j$  selected vertices (see Figure  6 ).

) Remove all the edges of the original map. Only the distinguished node $u$  is isolated. Remove uneface Figure 6 : Step 2 of $\Phi$  . it.

4) We obtain a tree in which the edges connect $\bullet$  -nodes to labeled nodes of the original map :

consider these last nodes as $\circ$  -node (there are $k-1$  such nodes since only the root is isolated).

There are $n$  $\bullet$  -nodes, one per face of $\mathbf{m}$  .

5) Choose the root of the mobile as the first edge that links $w$  to the $\bullet$  -node in the face adjacent to $vw$  , to the right of $\overrightarrow{wv}$  .

6) Add $-g\left(v\right)+1$  to the label of each node.

The resulting mobile belongs to ${\mathcal{W}}_{n,k-1}$  , call it $\Phi (\mathbf{m})$  .

Figure 7 : Illustration of the application $\Phi$  . The two arrows explain how to choose the root of $\mathbf{t}$  .

Description of $\Phi \sigma (\mathbf{p}{)}^{-1}$  Consider a rooted labeled mobile $(\mathbf{t},\ell )\in {\mathcal{W}}_{n,k-1}$  with root $v^{\prime }{w}^{\prime }$  . Up to renaming the vertices, we assume that $v^{\prime }$  is a $\circ$  -node and $w^{\prime }$  a $\bullet$  -node. We now give the construction of $\mathbf{m}=\Phi \sigma (\mathbf{p}{)}^{-1}(\mathbf{t},\ell )$  . 1) Let $m$  be the minimum of the labels of $\mathbf{t}$  . Add $-m+1$  to each label.

A corner of $\mathbf{t}$  is a sector with apex at a labeled vertex of $\mathbf{t}$  and delimited by two consecutive edges around this vertex. We label each corner by the label of its apex. To each corner $C$  with label $l\ge 2$  , we associate its successor $s\left(C\right)$  defined as the first encountered corner with label $l-1$  when going clockwise around the tree (there is always a successor).

2) We construct the map $\mathbf{m}$  associated with $\mathbf{t}$  by first drawing an edge between each corner with label $l\ge 2$  and its successor within the external face of $\mathbf{t}$  and in such a way that no two edges intersect. This can be done due to the nested structure around $\mathbf{t}$  of corners and their successors, namely : if a corner $C^{\prime }$  lies strictly between a corner $C$  and its successor $s\left(C\right)$  , then $s\left(C^{\prime }\right)$  lies between $C^{\prime }$  and $s\left(C\right)$  (with possibly $s\left(C^{\prime }\right)=s\left(C\right)$  ).

3) Add an origin vertex $u$  labeled $0$  in the external face and view the unique sector around this isolated point as the successor of all corners labeled $1$  , which we therefore also connect to the origin via non-crossing edges. This is possible because each corner has its successor before or at the first encountered corner labeled $1$  ; hence all corners labeled $1$  are incident to the external face.

4) Erase all unlabeled vertices and their adjacent edges.

5) The result is a map $\mathbf{m}$  that has $n$  faces and $k$  vertices. It remains to root it and to distinguish a node :

– the distinguished node is $u$  , 4 ASYMPTOTICS FOR MAPS – the root, is the first edge of $\mathbf{m}$  that starts from $v^{\prime }$  to the left of $\overrightarrow{v^{\prime }{w}^{\prime }}$  .

The resulting pointed rooted map is $\Phi \sigma (\mathbf{p}{)}^{-1}(\mathbf{t},\ell )$ 

Figure 8 : Illustration of $\Phi \sigma (\mathbf{p}{)}^{-1}$  . The two arrows explain how to choose the root of $\mathbf{m}$  . It remains to remove the labels.

4 ASYMPTOTICS FOR MAPS

4.2 Mobiles derived from random maps

In this section, we show how the invariance principles of Sects.  3 and  3.6 has to be interpreted in the context of the mobiles constructed from random maps. Recall the notations from Sect.  1 , and consider the labeled mobiles $(T,L)=\Phi \left(M\right)$  under the laws $P_{\mathbf{q}},P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  or $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  .

First, notice that contrary to what we considered in the two previous sections, the $\bullet$  vertices in mobiles $T$  with law $P_{\mathbf{q}}$  do not have a label, but this is a minor difference since we can suppose that they inherit the label of their respective fathers, so that the spatial displacement from any $\circ$  vertex to its children is $0$  . We therefore set ${\nu }_k\sigma (\mathbf{p}{)}^{\circ }={\delta }_0$  , the Dirac measure at the origin of $\mathbb{R}\sigma (\mathbf{p}{)}^k$  . Now, according to the labeling constraint ( 2 ) of mobiles obtained by the BdFG bijection, and the fact that it is uniform according to these constraints conditionally on $T$  , we naturally set, for any $k\ge 1$  and $a_1,\dots ,a_k\in \mathbb{Z}$  , $${\nu }_k\sigma (\mathbf{p}{)}^{\bullet }(a_1,...,a_k)=\frac{{\prod }_{i=0}\sigma (\mathbf{p}{)}^k{1}_{a_{i+1}\ge a_i-1}}{N(k+1)},$$  where $a_0=a_{k+1}=0$  .

From now on, suppose that $\mathbf{q}$  is a regular critical weight, and we define $\mu {\circ }_{\mathbf{q}},\mu {\bullet }_{\mathbf{q}}$  as in Sect.  1 .

Lemma 14 The data $\mu {\circ }_{\mathbf{q}},\mu {\bullet }_{\mathbf{q}},\nu \sigma (\mathbf{p}{)}^{\circ },\nu \sigma (\mathbf{p}{)}^{\bullet }$  satisfy the hypotheses $\left(H_1\right),\left(H_2\right),\left(H_3\right)$  . More precisely, $\left(i\right)$  For any $k\ge 1$  , the distribution ${\nu }_k\sigma (\mathbf{p}{)}^{\bullet }$  is centered. For any $k\ge 1,j\in \mathcal{J}1,k\mathcal{K},$  $$(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2=\frac{2j(k+1-j)}{k+2}.$$  $\left(ii\right)$  For any $k\ge 1$  , ${\sum }_{j=1}\sigma (\mathbf{p}{)}^k({\Sigma }_{k,j}\sigma (\mathbf{p}{)}^{\bullet })\sigma (\mathbf{p}{)}^2=\frac{k(k+1)}{3}$  .

$\left(iii\right)$  ${max}_{1\le j\le k}{M}_{k,j,p}\sigma (\mathbf{p}{)}^{\circ }\le (k+1\left)\sigma \right(\mathbf{p}{)}^p$  in particular ${max}_{1\le j\le k}\left(M_{k,j}\sigma \right(\mathbf{p}{)}^{\bullet }\vee M_{k,j}\sigma (\mathbf{p}{)}^{\circ })=O\left(k\sigma \right(\mathbf{p}{)}^{4+\varepsilon })$  .

Proof. Since $\mathbf{q}$  is regular critical, $\left(H_1\right)$  is plainly satisfied. Next, consider a $\bullet$  -node $u$  with total degree $k+1$  (for $k\ge 0$  ). Denote by $u_0,...,u_k$  , the neighbors of $u$  sorted in the depth first order (so $u_0$  is the grandfather of the other nodes). By the convention on ${\nu }_{\circ }$  , the distribution of $(\ell (u_1)-\ell (u_0),...,\ell (u_k)-\ell (u_0\left)\right),$  is given by $\nu \sigma (\mathbf{p}{)}_k^{\bullet }$  . The condition ( 2 ) on the labels can be rewritten $$x_1\ge -1,x_2\ge -1,...,x_k\ge -1,x_{k+1}\ge -1,\text{and}{\sum }_{i=1}\sigma (\mathbf{p}{)}^{k+1}{x}_i=0$$  where the $x_i$  are the integers $x_i=\ell \left(u_i\right)-\ell \left(u_{i-1}\right)$  with the convention $\ell \left(u_{k+1}\right)=\ell \left(u_0\right)$  . Now, let put $k+1$  balls in $k+1$  urns and note $(y_i,1\le i\le k+1)$  the number of balls in the urns $1,2...,k+1$  . We have $$(y_i,1\le i\le k+1)=\left(d\right)(x_i+1,1\le i\le k+1).$$  Then, $\nu \sigma (\mathbf{p}{)}_{k,j}^{\bullet }$  is the distribution of $x_1+\cdot \cdot \cdot +x_j$  and also the one of $s_{k,j}=y_1+\cdot \cdot \cdot +y_j-j$  .

By symmetry, the mean of $y_1$  is 1 and then $s_{k,j}$  is centered. Let us compute its variance.

Using the urn representation, we obtain $$\mathbb{P}(s_{k,j}=l)=\frac{\left(\genfrac{}{}{0ex}{}{l+2j-1}{l+j}\right)\left(\genfrac{}{}{0ex}{}{2k-2j-l+1}{k-j+1-l}\right)}{\left(\genfrac{}{}{0ex}{}{2k+1}{k+1}\right)}\text{for any}l\in \{-j,...,k+1-j\}.$$  Now, 4 ASYMPTOTICS FOR MAPS

$$\begin{array}{ccc}\left({\Sigma }_{k,j}\sigma \right(\mathbf{p}{)}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2=Var\left(s_{k,j}\right)& =& {\sum }_{l=-j}\sigma (\mathbf{p}{)}^{k+1-j}\frac{\left(\genfrac{}{}{0ex}{}{l+2j-1}{l+j}\right)\left(\genfrac{}{}{0ex}{}{2k-2j-l+1}{k-j+1-l}\right)}{\left(\genfrac{}{}{0ex}{}{2k+1}{k+1}\right)}l\sigma (\mathbf{p}{)}^2={\sum }_{l=0}\sigma (\mathbf{p}{)}^{k+1}\frac{\left(\genfrac{}{}{0ex}{}{l+j-1}{j-1}\right)\left(\genfrac{}{}{0ex}{}{2k-j-l+1}{k-j}\right)}{\left(\genfrac{}{}{0ex}{}{2k+1}{k+1}\right)}(l-j\left)\sigma \right(\mathbf{p}{)}^2\end{array}$$

(23)

Note that the following sum does not depend on $j$  , $${\sum }_{l=0}\sigma (\mathbf{p}{)}^{k+1}(\genfrac{}{}{0ex}{}{l+j-1}{j-1}\left)\right(\genfrac{}{}{0ex}{}{2k-j-l+1}{k-j})=(\genfrac{}{}{0ex}{}{2k+1}{k}).$$  Indeed, when one counts the number of possible choices of $k+1$  numbers among $\mathcal{J}1,2k+1\mathcal{K}$  , one may specify at first that the $j$  th chosen is $j+l$  (with $l\in \mathcal{J}0,k+1\mathcal{K}$  ) and then choose $j-1$  numbers in $\mathcal{J}1,l+j-1\mathcal{K}$  , and $k-j$  numbers in $\mathcal{J}j+l+1,2k+1\mathcal{K}$  .

Using $\frac{a+1}{b+1}\left(\genfrac{}{}{0ex}{}{a}{b}\right)=\left(\genfrac{}{}{0ex}{}{a+1}{b+1}\right)$  and $(l-j)\sigma (\mathbf{p}{)}^2=(l+j\left)\right(l+j+1)-(l+j\left)\right(4j+1)+4j\sigma (\mathbf{p}{)}^2$  , the numerator of ( 23 ) can be rewritten $$4j\sigma (\mathbf{p}{)}^2(\genfrac{}{}{0ex}{}{2k+1}{k})-(4j+1\left)j{\sum }_{l=0}\sigma \right(\mathbf{p}{)}^{k+1}\left(\genfrac{}{}{0ex}{}{l+j}{j}\right)\left(\genfrac{}{}{0ex}{}{2k-j-l+1}{k-j}\right)+j(j+1){\sum }_{l=0}\sigma (\mathbf{p}{)}^{k+1}(\genfrac{}{}{0ex}{}{l+j+1}{j+1}\left)\right(\genfrac{}{}{0ex}{}{2k-j-l+1}{k-j})$$  and then 4 ASYMPTOTICS FOR MAPS

$$\begin{array}{ccc}(\Sigma \sigma (\mathbf{p}{)}_{k,j}^{\bullet }\left)\sigma \right(\mathbf{p}{)}^2& =& \frac{4j\sigma (\mathbf{p}{)}^2(\genfrac{}{}{0ex}{}{2k+1}{k})-(4j+1\left)j\right(\genfrac{}{}{0ex}{}{2k+2}{k+1})+j(j+1\left)\right(\genfrac{}{}{0ex}{}{2k+3}{k+2})}{\left(\genfrac{}{}{0ex}{}{2k+1}{k}\right)}=\frac{2j(k+1-j)}{(k+2)}.\end{array}$$

Now, replacing $(l-j)\sigma (\mathbf{p}{)}^2$  by $(l-j)\sigma (\mathbf{p}{)}^p$  in ( 23 ), and bounding this quantity by $(k+1)\sigma (\mathbf{p}{)}^p$  , we obtain easily $\left(ii\right)$  and $\left(iii\right)$  . $\square$  From (ii) in this lemma we easily deduce, by elementary computations:

Lemma 15 The constants ${\overline{\sigma }}_{\circ },{\overline{\sigma }}_{\bullet }$  , $\overline{\sigma }$  and $\Sigma$  corresponding as in ( 14 ), ( 13 ) to the data $\mu {\circ }_{\mathbf{q}},\mu {\bullet }_{\mathbf{q}},\nu \sigma (\mathbf{p}{)}^{\circ },\nu \sigma (\mathbf{p}{)}^{\bullet }$  of Sect.  1 are given by $${\overline{\sigma }}_{\circ }=\sqrt{{\rho }_{\mathbf{q}}},{\overline{\sigma }}_{\bullet }=\sqrt{(Z_{\mathbf{q}}-1){\rho }_{\mathbf{q}}},\overline{\sigma }=\frac{\sqrt{Z_{\mathbf{q}}{\rho }_{\mathbf{q}}}}{2}\text{and}\Sigma =\sqrt{\frac{{\rho }_{\mathbf{q}}}{6}},$$  for ${\rho }_{\mathbf{q}}$  defined at ( 8 ).

As a corollary of this and Corollary  3 , and Theorem  4 , we finally obtain

Theorem 5 Let $\mathbf{q}$  be a regular critical weight. Then (i) Under $P_{\mathbf{q}}$  and given $\Re \left(M\right)>an$  for some $a>0$  , the process $\left(n\sigma \right(\mathbf{p}{)}^{-2}\widehat{H}\sigma (\mathbf{p}{)}_{2n\sigma (\mathbf{p}{)}^{4}s}^T,n\sigma (\mathbf{p}{)}^{-1}\widehat{R}\sigma (\mathbf{p}{)}_{2n\sigma (\mathbf{p}{)}^{4}s}^T{)}_{s\ge 0}$  associated with $\Phi \left(M\right)$  converges to the head of the Brownian snake determined by $$\left(\frac{4}{\sqrt{Z_{\mathbf{q}}{\rho }_{\mathbf{q}}}}e,\left(\frac{4{\rho }_{\mathbf{q}}}{9Z_{\mathbf{q}}}\right)\sigma (\mathbf{p}{)}^{1/4}r\right)\text{under}\mathbb{N}\left(\cdot \left|\left(\frac{4{\rho }_{\mathbf{q}}}{9Z_{\mathbf{q}}}\right)\sigma \right(\mathbf{p}{)}^{1/4}\Delta >a\right).$$  (ii) Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  , the process $\left(n\sigma \right(\mathbf{p}{)}^{-1/2}\widehat{H}\sigma (\mathbf{p}{)}_{2\left(\right|T|-1)s}^T,n\sigma (\mathbf{p}{)}^{-1/4}\widehat{R}\sigma (\mathbf{p}{)}_{2\left(\right|T|-1)s}^T{)}_{0\le s\le 1}$  associated with $\Phi \left(M\right)$  converges to $$\left(\frac{4}{\sqrt{(Z_{\mathbf{q}}-1){\rho }_{\mathbf{q}}}}e,\left(\frac{4{\rho }_{\mathbf{q}}}{9(Z_{\mathbf{q}}-1)}\right)\sigma (\mathbf{p}{)}^{1/4}r\right)\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}.$$  (iii) Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  , the process $\left(n\sigma \right(\mathbf{p}{)}^{-1/2}\widehat{H}\sigma (\mathbf{p}{)}_{2\left(\right|T|-1)s}^T,n\sigma (\mathbf{p}{)}^{-1/4}\widehat{R}\sigma (\mathbf{p}{)}_{2\left(\right|T|-1)s}^T{)}_{0\le s\le 1}$  associated with $\Phi \left(M\right)$  converges to $$\left(\frac{4}{\sqrt{{\rho }_{\mathbf{q}}}}e,\left(\frac{4{\rho }_{\mathbf{q}}}{9}\right)\sigma (\mathbf{p}{)}^{1/4}r\right)\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}.$$ 

4 ASYMPTOTICS FOR MAPS

4.3 The profile of random maps

Let $\mathbf{m}\in \mathcal{ℳ}$  and $(\mathbf{t},\ell )=\Phi (\mathbf{m})$  . Assume that $|\mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }|=n$  . The duration of the contour process of $\mathbf{t}$  is twice its number of edges, that is $2\left(\right|\mathbf{t}|-1)$  . The $|\mathbf{t}|-n$  type- $\circ$  vertices are visited at times $(0,2,4,...,2(|\mathbf{t}|-1\left)\right)$  . We want to consider only the labels of $\circ$  -vertices, and so we set $$\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}(k)=\ell (F\left(2k\right))\text{for}k\in \mathcal{J}0,|\mathbf{t}|-1\mathcal{K},$$  and we extend $\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}$  linearly between successive integers. A consequence of Theorem  4 and of Lemma  7 is the following :

Corollary 4 Theorem  5  (ii) and (iii) still hold with $n\sigma (\mathbf{p}{)}^{-1/4}\mathbf{R}\sigma (\mathbf{p}{)}^T\left(\right(\left|T\right|-1).)$  instead of $n\sigma (\mathbf{p}{)}^{-1/4}\widehat{R}\sigma (\mathbf{p}{)}_{2\left(\right|T|-1).}^T$  .

In this section, we consider the convergence of the profile of bipartite maps (this is the distribution’s generalization of Chassaing & Schaeffer [9] , where the convergence of moments were also proven in the case of quadrangulation). Consider $\mathbf{m}\in \mathcal{ℳ}$  and $(\mathbf{t},\ell )$  a rooted labeled mobile.

For any $k\in \mathbb{Z}$  , let ${\lambda }_k\sigma (\mathbf{p}{)}^{\mathbf{t}}$  be the number of nodes with label $k$  in $\mathbf{t}$  and let $L_k\sigma (\mathbf{p}{)}^{\mathbf{m}}$  be the number of vertices at distance $k$  from the distinguished node in $\mathbf{m}$  ; denote by $\underline{\lambda }=min\{j,{\lambda }_j>0\}$  the smallest label in the mobile. The sequence $\left(L_k\sigma \right(\mathbf{p}{)}^{\mathbf{m}}{)}_{k\ge 0}$  is called the profile of $\mathbf{m}$  . As a simple consequence of the construction of $\Phi$  , $${\lambda }_{k+\underline{\lambda }}\sigma (\mathbf{p}{)}^{\mathbf{t}}=\#\left\{j,\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}(j)=k+min\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}\right\}=L_{k+1}\sigma (\mathbf{p}{)}^{\mathbf{m}}\mathbf{}\mathbf{}\text{for any}k\ge 0.$$  Similarly, denoting by $I\sigma (\mathbf{p}{)}^{\mathbf{m}}$  , the integrated profile , we have $$I\sigma (\mathbf{p}{)}^{\mathbf{m}}(k)={\sum }_{j=0}\sigma (\mathbf{p}{)}^k{L}_j\sigma (\mathbf{p}{)}^{\mathbf{m}}=\#\left\{j,\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}(j)\le k+min\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}\right\}\text{for}k\in {\mathbb{Z}}_{+}$$  Using the same argument as in [9] (see also [22] ), we get

Theorem 6 (i) Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  , (resp. $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  ) the largest distance to the root $n\sigma (\mathbf{p}{)}^{-1/4}max\{i,L_i\sigma (\mathbf{p}{)}^M>0\}$  converges in distribution to $$\left(\frac{4{\rho }_{\mathbf{q}}}{9(Z_{\mathbf{q}}-1)}\right)\sigma (\mathbf{p}{)}^{1/4}\Delta \text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)},\left(\text{resp.}\left(\frac{4{\rho }_{\mathbf{q}}}{9}\right)\sigma (\mathbf{p}{)}^{1/4}\Delta \text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}\right).$$  (ii) Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  , (resp. $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  ), the process ${\left(\frac{I\sigma (\mathbf{p}{)}^M(n\sigma (\mathbf{p}{)}^{1/4}x)}{n(1+m_{\bullet })}\right)}_{x\ge 0}$  (resp. ${\left(\frac{I\sigma (\mathbf{p}{)}^M(n\sigma (\mathbf{p}{)}^{1/4}x)}{n(1+m_{\circ })}\right)}_{x\ge 0}$  converges weakly to $${\left(Leb\left\{t\in [0,1],\left(\frac{4{\rho }_{\mathbf{q}}}{9(Z_{\mathbf{q}}-1)}\right)\sigma (\mathbf{p}{)}^{1/4}\left(r\left(t\right)-minr\right)\le x\right\}\right)}_{x\ge 0}\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}$$  $$\left(\text{resp.}{\left(Leb\left\{t\in [0,1],\left(\frac{4{\rho }_{\mathbf{q}}}{9}\right)\sigma (\mathbf{p}{)}^{1/4}\left(r\left(t\right)-minr\right)\le x\right\}\right)}_{x\ge 0}\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}\right)$$  in $C[0,+\infty )$  endowed with the topology of uniform convergence on compact sets.

4 ASYMPTOTICS FOR MAPS

4.4 Convergence to the Brownian map

The Brownian map is introduced in Marckert & Mokkadem [22] . Informally, it is the quotient of a continuous tree, where the equivalence class are defined with the help of a second continuous tree. We show that normalized bipartite maps converge to the Brownian map. Most of what is done here is a generalization of [22] , where the work was based on the bijection between quadrangulations and “labeled trees”. We will be sometimes a little bit sketchy referring the interested reader to the above reference.

4 ASYMPTOTICS FOR MAPS

4.4.1 Bipartite maps as a tree glued on a second tree

Consider a rooted labeled mobile $(\mathbf{t},\ell )\in {\mathcal{W}}_{n,k-1}$  with root $v^{\prime }{w}^{\prime }$  (such that $v^{\prime }$  is a $\circ$  -node and $w^{\prime }$  a $\bullet$  -node). To obtain a representation of $\mathbf{m}=\Phi \sigma (\mathbf{p}{)}^{-1}(\mathbf{t},\ell )$  with the help of two trees, we need to reroot the mobile on one of the $\circ$  -node with minimum label. We need also to keep the tracks of $v^{\prime }$  and $w^{\prime }$  : they are necessary to build the root of $\mathbf{m}$  . We denote by $\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}$  the rooted labeled mobile obtained from $\mathbf{t}$  by rerooting it on the edge $\left(F_{\mathbf{t}}\right(\theta ),F_{\mathbf{t}}(\theta +1\left)\right)$  , and with labels, the labels of $\mathbf{t}$  plus $-\ell \left(F_{\mathbf{t}}\right(\theta \left)\right)+1$  , where $\theta$  is the integer belonging to $\{0,2,4,...,2(|\mathbf{t}|-1)-2\}$  .

The label of the root-node of $\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}$  is 1, $\mathbf{t}$  and $\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}$  are equal as unrooted unlabeled trees, the difference between the labels of neighbors are the same in $\mathbf{t}$  and $\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}$  . Let $\oplus$  denotes the addition modulo $2\left(\right|\mathbf{t}|-1)$  . For any $i\in \mathcal{J}0,2\left(\right|t|-1)\mathcal{K}$  , $$\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}}(i)=\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}}(\theta \oplus i)+\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}}(\theta )-2min\left\{\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}}(x),x\in \mathcal{J}(\theta \oplus i)\wedge \theta ,(\theta \oplus i)\vee \theta )\mathcal{K}\right\},$$  and for any $i\in \mathcal{J}0,\left|t\right|-1\mathcal{K}$  , $$\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}}(i)=\ell (F_{\mathbf{t}}(\theta \oplus 2i))-\ell (F_{\mathbf{t}}\left(\theta \right))+1=\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}\left(\frac{\theta \oplus 2i}{2}\right)-\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}\left(\frac{\theta }{2}\right)+1.$$  On $\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}$  , $v^{\prime }$  is visited at time $2\left(\right|\mathbf{t}|-\theta )$  and $w^{\prime }$  at time $2\left(\right|\mathbf{t}|-\theta )+1$  . Hence, the variable $X\left(\theta \right)=2\left(\right|\mathbf{t}|-\theta )$  suffices to reconstitute $v^{\prime }$  and $w^{\prime }$  .

Figure 9 : Encoding of a mobile.

Let $${\Theta }_{\mathbf{t}}=inf\{\theta ,\ell (F_{\mathbf{t}}\left(\theta \right))=min\ell (F_{\mathbf{t}}\left)\right\},$$  be the first visit time of a $\circ$  -node with minimum label. We will often write $\Theta$  instead of ${\Theta }_{\mathbf{t}}$  . The mobile $\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}$  has positive labels. We now build the rooted pointed map $\Phi (\mathbf{t})$  from $(\Theta ,\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )})$  .

Figure 10 : Rerooting on the first minimum.

Construction of $\Phi \sigma (\mathbf{p}{)}^{-1}(\mathbf{t},\ell )$  from $(\Theta ,\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )})$  The process $\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}$  contains all the informations needed to build the edges of $\Phi (\mathbf{t})$  .

(1) Add in the plane the point $u=N_{|\mathbf{t}|}=\left(\right|\mathbf{t}|,0)$  , and for $i\in \mathcal{J}1,|\mathbf{t}|-1\mathcal{K}$  draw the node $N_i=(i,\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}\left(i\right))$  .

(2) For $j\in \mathcal{J}1,|\mathbf{t}|-1\mathcal{K}$  , add an edge in the plane between $N_j$  and $N_{j^{\prime }}$  where $j^{\prime }$  encodes the successor of the corner encoded by $j$  in $\mathbf{t}\sigma (\mathbf{p}{)}^{\left(\theta \right)}$  as on Figure  11 . That is : draw the edges in such a way that the edges do not cross, and in such a way that the edge $(N_j,N_{j^{\prime }})$  surrounds from above the edges that start from abscissas lying between $j$  and $j^{\prime }$  . The set of nodes and edges drawn is a tree (see [22] for a proof ); we call this tree $\mathcal{D}$  .

Figure 11 : Doddering tree.

(3) We call $\mathcal{G}$  the underlying tree of $\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}$  . Its contour process is $\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}$  . Each node of $\mathcal{D}$  (but the root) corresponds to a $\circ$  -corner of $\mathcal{G}$  : for $j\ge 1$  , the node $N_j$  of $\mathcal{D}$  corresponds to the node visited at time $2j$  in $\mathcal{G}$  . Glue the nodes of $\mathcal{D}$  that correspond to corners of the same node of $\mathcal{G}$  in such a way that the edges do not intersect. (On Figure  12 , glue the nodes of $\mathcal{D}$  that correspond to corners of the same node of $\mathcal{D}$  below the tree. They are specified by horizontal 4 ASYMPTOTICS FOR MAPS doted lines).

(4) Choose the root and the distinguished node of $\mathbf{m}$  : the distinguished node is the point $u$  added in (1). In $\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}$  , $v^{\prime }$  and $w^{\prime }$  are visited at time $X(\Theta )$  and $X(\Theta )+1$  . To get the root of $\mathbf{m}$  , we have to turn around $v^{\prime }$  , starting from $\overrightarrow{v^{\prime }{w}^{\prime }}$  on the right. Proceed as on Fig.  12 .

Remark. One may also construct the root of $\mathbf{m}$  on $\mathcal{D}$  (before the gluing of the nodes of $\mathcal{D}$  ). $v^{\prime }$  is the node $N_{X(\Theta )/2}$  on $\mathcal{D}$  . $w^{\prime }$  is the last node in the list $N_1,N_2,...,N_{X(\Theta )/2-1}$  with successor $v^{\prime }$  , and if such a node does not exists, $w^{\prime }$  is the successor of $v^{\prime }$  (this is the case on Figure  11 ).

Figure 12 : Drawing of the doddering tree on the gluer tree.

The two trees $\mathcal{D}$  and $\mathcal{G}$  are called doddering tree and gluer tree, respectively, in [22] . The doddering tree contains all the edges of the maps and, as one guesses easily in view of Figure  12 , using the gluer tree one may reconstitute the original map. For this, draw $\mathcal{D}$  on the contour process of $\mathcal{G}$  as on Figure  12  : place the root of $\mathcal{D}$  in the plane (not on the graph of $\mathcal{G}$  ). Then, for $i\in \mathcal{J}0,|\mathbf{t}|-2\mathcal{K}$  , place the $i+1$  th node of $\mathcal{D}$  on the $2|\mathbf{t}|-2i-2$  th $\circ$  corner of $\mathcal{G}$  . Now, it remains to use a deformation of the plane, in order to “glue” together the corners of the gluer tree, corresponding to the same nodes. This is possible as one may imagine easily on Fig.  12 in considering the horizontal line as elastic strings. One may also proceed, as on Fig.  13 where two first gluings are done. At the end, it remains to remove the doted lines and the $\bullet$  -nodes.

Figure 13 : Two first gluings.

Remark. We have constructed the map $\mathbf{m}$  with the help of the labeled mobile $(\mathbf{t},\ell )$  (given by the BdFG bijection), which itself has been encoded by the triplet $\left(\Theta ,\left(\widehat{H}\sigma \right(\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}},\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}})\right)$  where, $\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}$  is the contour process of $\mathcal{G}$  , the value $\Theta$  is used to reconstitute the root of $\mathbf{m}$  , and by construction

Proposition 6 Setting $\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}(|\mathbf{t}|)=0$  , the process ${\left(\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}(|\mathbf{t}|-i)\right)}_{i=0,...,|\mathbf{t}|-1}$  is the height process of $\mathcal{D}$  .

4 ASYMPTOTICS FOR MAPS

4.4.2 Asymptotics of $\mathcal{D}$  and $\mathcal{G}$ 

In order to get the asymptotics of the trees $\mathcal{D}$  and $\mathcal{G}$  under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  or $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  , we follow and modify slightly when needed some arguments given with considerable more details in [22] . We recall the operation of rerooting of a normalized labeled tree defined for any $\theta \in [0,1]$  by

$$\begin{array}{cccc}J:& \mathbb{H}& \mathbb{⟶}& [0,1]\times \mathbb{H}\end{array}$$

$$\begin{array}{cccc}& (\zeta ,f)& \mapsto & J\sigma (\mathbf{p}{)}^{\left(\theta \right)}(\zeta ,f)=(\zeta \sigma (\mathbf{p}{)}^{\left(\theta \right)},f\sigma (\mathbf{p}{)}^{\left(\theta \right)})\end{array}$$

, where for any $x\in [0,1]$  ,

$$\begin{array}{c}\begin{array}{ccc}f\sigma (\mathbf{p}{)}^{\left(\theta \right)}(x)& =& f(\theta +x)-f\left(\theta \right),\\ \zeta \sigma (\mathbf{p}{)}^{\left(\theta \right)}(x)& =& \zeta (\theta +x)+\zeta \left(\theta \right)-2\check{\zeta }(\theta \oplus x,\theta ),\end{array}\end{array}$$

(24)

where the additions in the arguments are modulo 1. This may be understood as follows : $(\zeta ,f)$  is the encoding of a labeled tree $T$  (that may be continuous) for which $\zeta$  is the contour process of the underlying tree $t$  , and $f$  is a labeling of the nodes of $t$  . $\left(\zeta \sigma \right(\mathbf{p}{)}^{\left(\theta \right)},f\sigma (\mathbf{p}{)}^{\left(\theta \right)})$  is the encoding of a labeled tree $T^{\prime }$  which is obtained from $T$  as follows: reroot $T$  on the corner $\theta$  (that is visited at time $\theta$  using the contour order), and add $-f\left(\theta \right)$  to each label (this fixes the root label of $T^{\prime }$  to 0). We refer also to Aldous [1] p.40 for this operation of rerooting. We are particularly interested by the rerooting on $I\left(f\right)=infArgminf$  , the first minimum of the label process :

$$\begin{array}{cccc}\Psi :& \mathbb{H}& \mathbb{⟶}& [0,1]\times \mathbb{H}\end{array}$$

$$\begin{array}{cccc}& (\zeta ,f)& \mapsto & \left(I\left(f\right),\left(\zeta \sigma \right(\mathbf{p}{)}^{+},f\sigma (\mathbf{p}{)}^{+})\right):=\left(I\left(f\right),\left(\zeta \sigma \right(\mathbf{p}{)}^{\left(I\right(f\left)\right)},f\sigma (\mathbf{p}{)}^{I\left(f\right)})\right).\end{array}$$

The application $\Psi$  is invertible (note that, it would not be without the first coordinate $I\left(f\right)$  ). The pair $(e\sigma (\mathbf{p}{)}^{+},r\sigma (\mathbf{p}{)}^{+})$  corresponding to the head of the Brownian snake $(e,r)$  under $\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}$  will be called the head of the positive snake. We refer to Le Gall & Weill [18] and Le Gall [17] for properties of $(e\sigma (\mathbf{p}{)}^{+},r\sigma (\mathbf{p}{)}^{+})$  and its occurrence as a limit of conditioned spatial trees.

Lemma 16 Under $\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}$  , $I(r)$  is uniform on $[0,1]$  and independent of $(e\sigma (\mathbf{p}{)}^{+},r\sigma (\mathbf{p}{)}^{+})$  .

Proof. First, according to Lemma 16 in [22] (see also [18,[Prop.2.5] ), $\#Argminr=1$  a.s.. The law of $(e,r)$  is preserved by rerooting (see [22] ) and $I(r\sigma (\mathbf{p}{)}^{\left(\theta \right)})=I(r)-\theta mod1$  . Then $I(r)$  is uniform in [0,1]. Now, let us check the independence. Suppose that $r$  reaches its minimum once. For any $x\in [0,1)$  , $\Psi (e\sigma (\mathbf{p}{)}^{\left(x\right)},r\sigma (\mathbf{p}{)}^{\left(x\right)})=(\theta -xmod1,(e\sigma (\mathbf{p}{)}^{+},r\sigma (\mathbf{p}{)}^{+}\left)\right)$  . Hence, in each class stable by rerooting, the positive representative $(e\sigma (\mathbf{p}{)}^{+},r\sigma (\mathbf{p}{)}^{+})$  is independent of $I\left(r\right)$  . $\square$  Recall that in mobile a $\bullet$  -node is labeled as its father.

Proposition 7 Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  (resp. $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  ), the process $\Psi \left(\frac{\widehat{H}\sigma (\mathbf{p}{)}^T\left(2\left(\right|T|-1).\right)}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{\widehat{R}\sigma (\mathbf{p}{)}^T\left(2\left(\right|T|-1).\right)}{n\sigma (\mathbf{p}{)}^{1/4}}\right)$  converges weakly to $$\Psi \left(\frac{4}{\sqrt{(Z_{\mathbf{q}}-1){\rho }_{\mathbf{q}}}}e,\left(\frac{4{\rho }_{\mathbf{q}}}{9(Z_{\mathbf{q}}-1)}\right)\sigma (\mathbf{p}{)}^{1/4}r\right)\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}$$  $$\left(\mathit{r}\mathit{e}\mathit{s}\mathit{p}\mathit{.}\Psi \left(\frac{4}{\sqrt{{\rho }_{\mathbf{q}}}}e,\left(\frac{4{\rho }_{\mathbf{q}}}{9}\right)\sigma (\mathbf{p}{)}^{1/4}r\right)\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}\right).$$ 

Proof. First, the weak convergence is a consequence of Corollary  4 and the fact that under $\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}$  , the process $r$  reaches a.s. its minimum once. Indeed, the applications $Argmin$  and then $\Psi$  are continuous on the space of continuous functions that reach their minimum once, and so one may conclude using Billingsley [6,Theorem(5.2)] . $\square$  Since a $\bullet$  -node has the same labels as its father, it is clear that $I\left(\widehat{R}\sigma \right(\mathbf{p}{)}^{\mathbf{t}}\left(2\left(\right|\mathbf{t}|-1).\right))$  is a real that encodes a $\circ$  -node. Hence, one may check that $I\left(\widehat{R}\sigma \right(\mathbf{p}{)}^{\mathbf{t}})=notI\left(\widehat{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}\left(2\left(\right|\mathbf{t}|-1).\right)\right)=\frac{\Theta (\mathbf{t})}{2\left(\right|\mathbf{t}|-1)}$  , $$\left(\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}}\left(2\left(\right|\mathbf{t}|-1).\right)\right)\sigma (\mathbf{p}{)}^{\left(I\right(\widehat{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}))}=\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}\left(2\right(|\mathbf{t}|-1).)4\mathit{A}\mathit{S}\mathit{Y}\mathit{M}\mathit{P}\mathit{T}\mathit{O}\mathit{T}\mathit{I}\mathit{C}\mathit{S}\mathit{F}\mathit{O}\mathit{R}\mathit{M}\mathit{A}\mathit{P}\mathit{S}$$  and that the processes $\left(\widehat{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}(2\left(\right|\mathbf{t}|-1).)\right)\sigma (\mathbf{p}{)}^{\left(I\right(\widehat{R}\sigma (\mathbf{p}{)}^{\mathbf{t}}))}+1$  and $\mathbf{R}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}\left(\left(\right|\mathbf{t}|-1).\right)$  coincide on $\left\{0,\frac{1}{\left(\right|\mathbf{t}|-1)},\frac{2}{\left(\right|\mathbf{t}|-1)},...,\frac{\left(\right|\mathbf{t}|-1)}{\left(\right|\mathbf{t}|-1)}\right\}$  . Denote by $\mathbf{C}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}$  the contour process of $\mathcal{D}$  . By Proposition  6 and  7 ,

Corollary 5 Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  (resp. $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  ), the process $\left(\frac{\Theta \left(T\right)}{2\left(\right|T|-1)},\frac{\widehat{H}\sigma (\mathbf{p}{)}^{T\sigma (\mathbf{p}{)}^{(\Theta )}}(2\left(\right|T|-1).)}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{\mathbf{R}\sigma (\mathbf{p}{)}^{T\sigma (\mathbf{p}{)}^{(\Theta )}}(\left(\right|T|-1).)}{n\sigma (\mathbf{p}{)}^{1/4}}\right)$  has the same limit as $\Psi \left(\frac{\widehat{H}\sigma (\mathbf{p}{)}^T\left(2\left(\right|T|-1).\right)}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{\widehat{R}\sigma (\mathbf{p}{)}^T\left(2\left(\right|T|-1).\right)}{n\sigma (\mathbf{p}{)}^{1/4}}\right)$  given in Proposition  7 .

For any $x\in [0,1]$  , set $\pi \left(x\right)=1-x$  . The process $\left(\frac{\widehat{H}\sigma (\mathbf{p}{)}^{T\sigma (\mathbf{p}{)}^{(\Theta )}}(2\left(\right|T|-1).)}{n\sigma (\mathbf{p}{)}^{1/2}},\frac{\mathbf{C}\sigma (\mathbf{p}{)}^{T\sigma (\mathbf{p}{)}^{(\Theta )}}(2\left(\right|T|-1).)}{n\sigma (\mathbf{p}{)}^{1/4}}\right)$  converges weakly to $$\left(\frac{4}{\sqrt{(Z_{\mathbf{q}}-1){\rho }_{\mathbf{q}}}}e\sigma (\mathbf{p}{)}^{+},\left(\frac{4{\rho }_{\mathbf{q}}}{9(Z_{\mathbf{q}}-1)}\right)\sigma (\mathbf{p}{)}^{1/4}r\sigma (\mathbf{p}{)}^{+}\circ \pi \right)\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}$$  $$\left(\mathit{r}\mathit{e}\mathit{s}\mathit{p}\mathit{.}\left(\frac{4}{\sqrt{{\rho }_{\mathbf{q}}}}e\sigma (\mathbf{p}{)}^{+},\left(\frac{4{\rho }_{\mathbf{q}}}{9}\right)\sigma (\mathbf{p}{)}^{1/4}r\sigma (\mathbf{p}{)}^{+}\circ \pi \right)\text{under}\mathbb{N}\sigma (\mathbf{p}{)}^{\left(1\right)}\right).$$ 

This is also a consequence of the general result, proven in [22] , that asserts that if the space normalization is not trivial, the contour process and the height process have the same limit.

4 ASYMPTOTICS FOR MAPS

4.4.3 Abstract map and Brownian map

We saw that bipartite maps can be obtained with the help of two trees $\mathcal{G}$  and $\mathcal{D}$  thanks to a “gluing procedure”. The last theorem says that the codings of these trees converge. The idea now is to use the convergence of trees to define the convergence of maps. Some changes appear in the present paper as compared with [22]  :

– Here the maps are rooted pointed instead of being only rooted.

– Here, the natural traversal for both trees is the clockwise traversal.

– Here $|\mathcal{D}|=|\mathcal{G}|$  instead of $|\mathcal{D}|=2|\mathcal{G}|$  .

– Here $|\mathcal{D}|$  and $|\mathcal{G}|$  are random (conditionally on $|\mathbf{t}\sigma (\mathbf{p}{)}^{\circ }|=n$  or $|\mathbf{t}\sigma (\mathbf{p}{)}^{\bullet }|=n$  ).

We recall now few points of the definitions of abstract maps and abstract trees. We modify them slightly in order to take into account the list of differences given above.

Abstract trees Consider $C\sigma (\mathbf{p}{)}^{+}[0,1]$  the set of continuous functions $g$  from $[0,1]$  to $\mathbb{R}\sigma (\mathbf{p}{)}^{+}$  that satisfy $g\left(0\right)=g\left(1\right)=0$  . For any $g\in C\sigma (\mathbf{p}{)}^{+}[0,1]$  , we introduce the equivalence relation in $[0,1]$  , $$x\sim gy⟺g\left(x\right)=g\left(y\right)=\check{g}(x,y),$$  We denote by $E_g$  the quotient space $E_g=[0,1]/\sim g$  and we consider the canonical surjection $F_g$  from $[0,1]$  in $E_g$  : $$F_g\left(x\right)=\{y,y\in [0,1],x\sim gy\}.$$  For short, we write sometimes $\dot{x}$  instead of $F_g\left(x\right)$  and we say that $x$  is a representative of $\dot{x}$  .

Let $\mathcal{ℳ}$  be the set of finite measures on $[0,1]$  and for $\mu \in \mathcal{ℳ}$  set $E_{\mu }=F_g(supp(\mu \left)\right),$  the image of the support of $\mu$  by $F_g$  . A pair $(g,\mu )\in C\sigma (\mathbf{p}{)}^{+}[0,1]\times \mathcal{ℳ}$  is said to be a tree-encoding if it satisfies:

$$\begin{array}{c}{E}_g\sigma (\mathbf{p}{)}^{\left(T\right)}=def\{u\in E_g,\#F_g\sigma (\mathbf{p}{)}^{-1}(u)\ne 2\}\cup \left\{\dot{0}\right\}\subset E_{\mu }.\end{array}$$

(25)

Let $(g,\mu )$  be a tree encoding. For any $\dot{x}$  and $\dot{y}$  in $E_g$  , set $$d_{E_g}(\dot{x},\dot{y})=g\left(x\right)+g\left(y\right)-2\check{g}(x,y).$$  It is not difficult to check that $d_{E_g}$  is a metric on $E_g$  .

Definition 2 Let $(g,\mu )$  be a tree encoding. The rooted tree $\mathcal{T}$  encoded by $(g,\mu )$  , we write $\mathcal{T}=Tree(g,\mu )$  , is the metric space $\mathcal{T}=(E_g,d_{E_g})$  . The function $F_g$  is called the depth first traversal of $\mathcal{T}$  . The elements of $E_g$  are called points of $\mathcal{T}$  , the elements of $E_{\mu }$  are called nodes of $\mathcal{T}$  . The class $F_g\left(0\right)=\dot{0}$  is called the root-vertex of $\mathcal{T}$  . The set of corners of $\mathcal{T}$  is $[0,1)$  . The set of corners around a point $\dot{x}$  is $F_{\mathcal{T}}\sigma (\mathbf{p}{)}^{-1}(\dot{x})\cap [0,1)$  . The corner 0 is the root-corner.

Set of trees We denote by $\Gamma$  the set of trees. Let $d_{\Gamma }:\Gamma \sigma (\mathbf{p}{)}^2\to \mathbb{R}\sigma (\mathbf{p}{)}^{+}$  be the application defined for $({\mathcal{T}}_1,{\mathcal{T}}_2)=\left(Tree(g_1,{\mu }_1),Tree(g_2,{\mu }_2)\right)$  elements of $\Gamma \sigma (\mathbf{p}{)}^2$  by $$d_{\Gamma }({\mathcal{T}}_1,{\mathcal{T}}_2)=\parallel g_1-g_2{\parallel }_{\infty }+d_{\mathcal{ℳ}}({\mu }_1,{\mu }_2)$$  with $$\parallel g_1-g_2{\parallel }_{\infty }=sup\left\{\right|g_1\left(x\right)-g_2\left(x\right)|,x\in [0,1\left]\right\}$$  and $$d_{\mathcal{ℳ}}({\mu }_1,{\mu }_2)={sup}_{x\in \mathbb{R}}\left|C_{{\mu }_1}\right(x)-C_{{\mu }_2}(x\left)\right|$$  where $C_{\mu }(.)=\mu \left(\right(-\infty ,.]$  is the repartition function of $\mu$  . The application $d_{\Gamma }$  is a metric on $\Gamma$  .

4 ASYMPTOTICS FOR MAPS Abstract maps

Definition 3 Let $(\mathcal{D},\mathcal{G})=(Tree(f,{\mu }_{\mathcal{D}}),Tree(\zeta ,{\mu }_{\mathcal{G}}\left)\right)\in \Gamma \sigma (\mathbf{p}{)}^2$  and let $b$  be an application from $E_{{\mu }_{\mathcal{D}}}\backslash \left\{\text{root-vertex}\right\}$  to the set of corners (i.e. $[0,1)$  ) of $\mathcal{G}$  . The 3-tuple $(\mathcal{D},\mathcal{G},b)$  is said to be admissible if the three following conditions are satisfied:

$\left(i\right)$  $b$  is an injection.

$\left(ii\right)$  $b$  is decreasing : if $u\preccurlyeq v$  in $\mathcal{D}$  , then $b\left(u\right)\ge b\left(v\right)$  in $[0,1)$  .

$\left(iii\right)$  If $u$  and $v$  are two nodes in $\mathcal{D}$  such that $b\left(u\right)\sim \zeta b\left(v\right)$  (that is $b\left(u\right)$  and $b\left(v\right)$  are corners of the same node in $\mathcal{G}$  ), then the depth of $u$  and the depth of $v$  in $\mathcal{D}$  are equal.

Let $(\mathcal{D},\mathcal{G},b)$  be $a$  -admissible. We define an equivalence relation: for $x,y\in E_{\mathcal{D}}$  , we say that

$$\begin{array}{c}x\sim My\iff (x=y)\text{or}\left(\{x,y\}\subset E_{{\mu }_{\mathcal{D}}}\backslash \left\{\text{root-vertex}\right\}\text{and}b\left(x\right)\sim \zeta b\left(y\right)\right).\end{array}$$

(26)

For $x\in E_{\mathcal{D}}$  we set $\hat{x}=\{y\in E_{\mathcal{D}},y\sim Mx\}$  . A class $\hat{x}$  is either a point of $\mathcal{D}$  , or the set of the nodes of $\mathcal{D}$  glued with $x$  (the node $x$  included), or the root of $\mathcal{D}$  .

Let $M$  be the set $$M=\left\{\hat{x},x\in E_{\mathcal{D}}\right\}.$$ 

Definition 4 Let $x\in [0,1]$  . The space $(M,x)$  is called the rooted pointed map encoded by $(\mathcal{D},\mathcal{G},b)$  (rooted in the root at $\mathcal{D}$  , and marked at $x$  ). We denote this space by $M=\text{Map}(\mathcal{D},\mathcal{G},b)$  .

We denote by $\overrightarrow{\mathfrak{M}}$  the set of rooted pointed maps. We refer to [22] for topological aspect of abstract maps.

Remark. For any $\hat{u},\hat{w}\in M$  and any $k>0$  , set $$d\sigma (\mathbf{p}{)}^{\left(k\right)}(\hat{u},\hat{w})=inf{\sum }_{i=0}\sigma (\mathbf{p}{)}^k{d}_{\mathcal{D}}(u_{2i},u_{2i+1}),$$  where the infimum is taken on the set $E=\left\{\right(u_0,...,u_{2k+1})\in E_{\mathcal{D}}\sigma (\mathbf{p}{)}^{2k+2}\text{s.t.}{\hat{u}}_0=\hat{u},{\hat{u}}_{2k+1}=\hat{w},{\hat{u}}_{2i+1}={\hat{u}}_{2i+2}\}$  and where $d_{\mathcal{D}}$  is the metric in $\mathcal{D}$  . Each element $e\in E$  defines a path in the map : between ${\hat{u}}_{2i}$  and ${\hat{u}}_{2i+1}$  it is the image by $S$  of the geodesic between $u_{2i}$  and $u_{2i+1}$  in $\mathcal{D}$  .

Since $u_{2i+1}$  and $u_{2i+2}$  are glued to build $M$  , in the map, ${\hat{u}}_{2i+1}={\hat{u}}_{2i+2}$  .

The application $d_M:M\sigma (\mathbf{p}{)}^2\to \mathbb{R}\sigma (\mathbf{p}{)}^{+}$  defined for any $\hat{u},\hat{w}\in M$  by $$d_M(\hat{u},\hat{v})={inf}_{k\ge 0}d\sigma (\mathbf{p}{)}^{\left(k\right)}(\hat{u},\hat{v}),$$  is a metric on $M$  . For discrete maps, this metric coincides with the graph distance.

This metric is called the ”quotient metric” in [5] . It is somehow the maximal one compatible both with the metric on $\mathcal{D}$  and the fact that equivalent points of $\mathcal{D}$  should be at distance $0$  .

The metric space $(M,d_M)$  is therefore the simplest candidate for being the limit e.g. in the Gromov-Haussdorf sense of discrete maps seen as metric spaces. Unfortunately, proving (or recusing) this assertion would require a lot more information than only the geodesic distance from a fixed point in the map, and seems unreachable by our methods.

The set $\overrightarrow{\mathfrak{M}}$  of maps Consider the application $d_{\overrightarrow{\mathfrak{M}}}:\overrightarrow{\mathfrak{M}}\sigma (\mathbf{p}{)}^2\to \mathbb{R}\sigma (\mathbf{p}{)}^{+}$  defined by: $$d_{\overrightarrow{\mathfrak{M}}}\left(\right(M_1,x_1),(M_2,x_2\left)\right)=|x_1-x_2|+d_{\Gamma }({\mathcal{D}}_1,{\mathcal{D}}_2)+d_{\Gamma }({\mathcal{G}}_1,{\mathcal{G}}_2)+\parallel C_{{\mu }_{{\mathcal{D}}_1}\circ b_1\sigma (\mathbf{p}{)}^{-1}}-C_{{\mu }_{{\mathcal{D}}_2}\circ b_2\sigma (\mathbf{p}{)}^{-1}}{\parallel }_{\infty },$$  where for $i\in \{1,2\}$  , $$M_i=\text{Map}\left({\mathcal{D}}_i,{\mathcal{G}}_i,b_i\right)=\text{Map}\left(Tree(f_i,{\mu }_{{\mathcal{D}}_i}),Tree({\zeta }_i,{\mu }_{{\mathcal{G}}_i}),b_i\right),4\mathit{A}\mathit{S}\mathit{Y}\mathit{M}\mathit{P}\mathit{T}\mathit{O}\mathit{T}\mathit{I}\mathit{C}\mathit{S}\mathit{F}\mathit{O}\mathit{R}\mathit{M}\mathit{A}\mathit{P}\mathit{S}$$  and where the function $$x\mapsto C_{{\mu }_{{\mathcal{D}}_1}\circ b_1\sigma (\mathbf{p}{)}^{-1}}\left(x\right)={\mu }_{{\mathcal{D}}_1}\left(b_1\sigma \right(\mathbf{p}{)}^{-1}(-\infty ,x])={\mu }_{{\mathcal{D}}_1}(\{y\in E_{{\mu }_{{\mathcal{D}}_1}},b_1(y)\in (-\infty ,x\left]\right\})$$  measures the amount of nodes of the doddering trees glued on the corners interval $(-\infty ,x]$  of the gluer tree ${\mathcal{G}}_1$  . The application $d_{\overrightarrow{\mathfrak{M}}}$  is a metric on $\overrightarrow{\mathfrak{M}}$  .

4 ASYMPTOTICS FOR MAPS

4.4.4 Normalized bipartite maps and abstract maps

We now represent normalized bipartite maps as abstract maps in the sense introduced above.

For this, we need two steps :

$1)$  We need to normalize the doddering tree and the gluer tree and endow these objects by a corner measure.

$2)$  Identity the gluing injection $b_{\mathbf{t}}$  that sends the nodes of the doddering tree in the set of corners of the gluer tree.

Let $(\mathbf{t},\ell )$  or simply $\mathbf{t}$  be a labeled mobile and set ${\mu }_{{\mathcal{G}}_{\mathbf{t}}}={\mu }_{{\mathcal{D}}_{\mathbf{t}}}=\frac{1}{2\left(\right|\mathbf{t}|-1)}{\sum }_{k=0}\sigma (\mathbf{p}{)}^{2\left(\right|\mathbf{t}|-1)-1}{\delta }_{k/\left(2\right(|\mathbf{t}|-1\left)\right)}$  .

We set $${\mathcal{G}}_{\mathbf{t}}\sigma (\mathbf{p}{)}^n=Tree(n\sigma (\mathbf{p}{)}^{-1/2}\widehat{H}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}\left(2\left(\right|\mathbf{t}|-1).\right),{\mu }_{{\mathcal{G}}_{\mathbf{t}}}\left)\text{and}{\mathcal{D}}_{\mathbf{t}}\sigma \right(\mathbf{p}{)}^n=Tree\left(n\sigma \right(\mathbf{p}{)}^{-1/4}\mathbf{C}\sigma (\mathbf{p}{)}^{\mathbf{t}\sigma (\mathbf{p}{)}^{(\Theta )}}\left(2\left(\right|\mathbf{t}|-1).\right),{\mu }_{{\mathcal{D}}_{\mathbf{t}}}).$$  The application $b_{\mathbf{t}}$  is the application sending the $k$  th node of ${\mathcal{D}}_{\mathbf{t}}$  on the $2\left(\right|\mathbf{t}|-k)$  th corner of ${\mathcal{G}}_{\mathbf{t}}$  . Consider $M_{\mathbf{t}}\sigma (\mathbf{p}{)}^n=\text{Map}({\mathcal{G}}_{\mathbf{t}}\sigma (\mathbf{p}{)}^n,{\mathcal{D}}_{\mathbf{t}}\sigma (\mathbf{p}{)}^n,b_{\mathbf{t}})$  marked at $$U_{\mathbf{t}}=X(\Theta (\mathbf{t}\left)\right)/\left(2\right(|\mathbf{t}|-1\left)\right)$$  (to mark the corner visited at time $U_{\mathbf{t}}$  in the normalized doddering tree or to marked the root is equivalent and). The rooted pointed ${\overrightarrow{M}}_{\mathbf{t}}\sigma (\mathbf{p}{)}^n:=(M_{\mathbf{t}}\sigma (\mathbf{p}{)}^n,U_{\mathbf{t}})$  is called the normalized bipartite map.

4 ASYMPTOTICS FOR MAPS

4.4.5 Rooted pointed Brownian map

Consider $(e\sigma (\mathbf{p}{)}^{+},r\sigma (\mathbf{p}{)}^{+})$  the head of the positive snake. Let ${\mu }_{{\mathcal{G}}_{\infty }}={\mu }_{{\mathcal{D}}_{\infty }}=Leb\sigma (\mathbf{p}{)}^{[0,1]}$  and for $c>0$  , set $${\mathcal{G}}_{\infty }\sigma (\mathbf{p}{)}^c=Tree(ce\sigma (\mathbf{p}{)}^{+},{\mu }_{{\mathcal{G}}_{\infty }})\text{and}{\mathcal{D}}_{\infty }\sigma (\mathbf{p}{)}^c=Tree(cr\sigma (\mathbf{p}{)}^{+}(1-.),{\mu }_{{\mathcal{D}}_{\infty }}).$$  The application $b$  is defined for any $x\in [0,1]$  by $b\left(x\right)=1-x$  . Consider $U$  a random variable independent of $(e\sigma (\mathbf{p}{)}^{+},r\sigma (\mathbf{p}{)}^{+})$  . We set $M_{\infty }(c_1,c_2)=\text{Map}\left({\mathcal{G}}_{\infty }\sigma \right(\mathbf{p}{)}^{c_1},{\mathcal{D}}_{\infty }\sigma (\mathbf{p}{)}^{c_2},b)$  and consider the element ${\overrightarrow{M}}_{\infty }=\left(M_{\infty }\right(c_1,c_2),U)\in \overrightarrow{\mathfrak{M}}$  , which we call the rooted pointed Brownian map.

4 ASYMPTOTICS FOR MAPS

4.4.6 Convergence to the Brownian map

Theorem 7 (i) Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  , the sequence ${\overrightarrow{M}}_T\sigma (\mathbf{p}{)}^n$  converges weakly to $${\overrightarrow{M}}_{\infty }\left(\frac{4}{\sqrt{(Z_{\mathbf{q}}-1){\rho }_{\mathbf{q}}}},\left(\frac{4{\rho }_{\mathbf{q}}}{9(Z_{\mathbf{q}}-1)}\right)\sigma (\mathbf{p}{)}^{1/4}\right)\text{in}(\overrightarrow{\mathfrak{M}},d_{\overrightarrow{\mathfrak{M}}})$$  (ii) Under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  , the sequence ${\overrightarrow{M}}_T\sigma (\mathbf{p}{)}^n$  converges weakly to $${\overrightarrow{M}}_{\infty }\left(\frac{4}{\sqrt{{\rho }_{\mathbf{q}}}},\left(\frac{4{\rho }_{\mathbf{q}}}{9}\right)\sigma (\mathbf{p}{)}^{1/4}\right)\text{in}(\overrightarrow{\mathfrak{M}},d_{\overrightarrow{\mathfrak{M}}})$$ 

Proof : By Lemma  16 the marked point is asymptotically uniform and independent of the rerooted snake. As in [22] , under $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^F$  or $P\sigma (\mathbf{p}{)}_{\mathbf{q},n}^S$  , the function $C_{{\mu }_{{\mathcal{D}}_T}}\circ b_T\sigma (\mathbf{p}{)}^{-1}$  converges weakly in $C(\mathbb{R})$  to $C_{Leb\sigma (\mathbf{p}{)}^{[0,1]}}$  . According to the definition of $d_{\overrightarrow{\mathfrak{M}}}$  , the Corollary  5 suffices to conclude. $\square$  Appendix Proof of Proposition  1 . We prove only the statement for the height process, which is more irregular than the contour process. Indeed, if $\phi \left(k\right)$  and $\phi \left(l\right)$  are the rank in depth-first order of the vertices $F\left(k\right),F\left(l\right)$  visited in rank $k,l$  in contour order, then $\left|\phi \right(k)-\phi (l\left)\right|\le |k-l|$  . Now, if the conclusion of the proposition holds for $H$  , from $|{\widehat{H}}_k-{\widehat{H}}_l|=|H_{\phi \left(k\right)}-H_{\phi \left(l\right)}|$  , it will also hold for $\widehat{H}$  .

Recall e.g. from [11] that if we let $$S\sigma (\mathbf{p}{)}_n^{\mathbf{f}}={\sum }_{k=1}\sigma (\mathbf{p}{)}^n\left(c_{\mathbf{f}}\right(u\left(k\right))-1),n\ge 0$$  be the Łukaciewicz walk associated with the forest $\mathbf{f}$  , then the height process of $\mathbf{f}$  is given by

$$\begin{array}{c}H\sigma (\mathbf{p}{)}_n^{\mathbf{f}}=\#\left\{k\in \{0,1,\dots ,n-1\}:S\sigma (\mathbf{p}{)}_k^{\mathbf{f}}={min}_{k\le l\le n}S\sigma (\mathbf{p}{)}_l^{\mathbf{f}}\right\}.\end{array}$$

(27)

Under $P\sigma (\mathbf{p}{)}_{\infty }^{\mu }$  , $S\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}$  is a random walk on $\mathbb{Z}$  with centered step distribution $\mu (\cdot +1)$  on $\{-1,0,1,2,\dots \}$  , and thanks to the time reversal property $$\left(\widehat{S}\sigma \right(\mathbf{p}{)}_k^{\left(n\right)}=S_n-S_{n-k},0\le k\le n)=d(S_k,0\le k\le n),$$  we have $$H\sigma (\mathbf{p}{)}_n^{\mathcal{ℱ}}=d\#\left\{k\in \{1,2,\dots ,n\}:S_k\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}={max}_{0\le l\le k}S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\right\},$$  which is the number of (weak) records of $S$  until time $n$  .

Now, suppose $0\le s<t\le A$  are such that $ns,nt\in {\mathbb{Z}}_{+}$  . Write $\lambda \left(x\right)=max\{l\in [0,ns]:S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\le x\}$  . Using ( 27 ), we have

$$\begin{array}{c}H\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}-H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}=\#\left\{k\in [ns,nt):S\sigma (\mathbf{p}{)}_k^{\mathcal{ℱ}}={min}_{k\le l\le nt}S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\right\}-\#\left\{\lambda \left({min}_{ns\le l\le nt}S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\right)<k<ns:S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}={min}_{k\le l\le ns}S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\right\},4\mathit{A}\mathit{S}\mathit{Y}\mathit{M}\mathit{P}\mathit{T}\mathit{O}\mathit{T}\mathit{I}\mathit{C}\mathit{S}\mathit{F}\mathit{O}\mathit{R}\mathit{M}\mathit{A}\mathit{P}\mathit{S}\end{array}$$

(28)

and the rest of the proof will consist in estimating the moments of the two terms above, which correspond to the lengths of the branches of $\mathcal{ℱ}$  from $u\left(ns\right),u\left(nt\right)$  down to their highest common ancestor. Thanks to the time-reversal property mentioned above, the first term is equal in distribution to $$G_{n(t-s)}=\#\left\{1\le k\le n(t-s):S\sigma (\mathbf{p}{)}_k^{\mathcal{ℱ}}={max}_{0\le l\le k}S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\right\},$$  the number of (weak) records before $n(t-s)$  .

Let $M_n={max}_{0\le k\le n}S\sigma (\mathbf{p}{)}_k^{\mathcal{ℱ}}$  . Let ${\tau }_0=0$  , and ${\tau }_i,i\ge 1$  be the $i$  -th record time, i.e. the $i$  -th time $\tau \ge 1$  such that $S\sigma (\mathbf{p}{)}_{\tau }^{\mathcal{ℱ}}=M_{\tau }$  . Then it is easy and well-known that $({\tau }_i-{\tau }_{i-1},i\ge 1)$  form a sequence of i.i.d. random variables. Moreover, since $S\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}$  is centered and its increments have finite second moment under $P\sigma (\mathbf{p}{)}_{\infty }^{\mu }$  , it is a consequence of the proof of [12,XII,7Theorem1a] and the discussion before that the Laplace exponent $\phi \left(s\right)=-logE\sigma (\mathbf{p}{)}_{\infty }^{\mu }[exp(-s{\tau }_1)]\sim Cs\sigma (\mathbf{p}{)}^{1/2}$  as $s\to 0$  for some $C>0$  (Feller considers the case of strict ladder epochs, but the treatment of weak ones is similar). Now, for any $p>1$  , and integer $u$  , 4 ASYMPTOTICS FOR MAPS

$$\begin{array}{ccc}E\sigma (\mathbf{p}{)}_{\infty }^{\mu }[G\sigma (\mathbf{p}{)}_u^p]& =& p{\int }_0\sigma (\mathbf{p}{)}^{\infty }x\sigma (\mathbf{p}{)}^{p-1}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left(G_u\ge x\right)dx\end{array}$$

$$\begin{array}{ccc}& =& p{\int }_0\sigma (\mathbf{p}{)}^{\infty }x\sigma (\mathbf{p}{)}^{p-1}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left({\sum }_{i=1}\sigma (\mathbf{p}{)}^x({\tau }_i-{\tau }_{i-1})\le u\right)dx\end{array}$$

$$\begin{array}{ccc}& \le & pe{\int }_0\sigma (\mathbf{p}{)}^{\infty }x\sigma (\mathbf{p}{)}^{p-1}E\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left[exp\left(-{\sum }_{i=1}\sigma (\mathbf{p}{)}^x\frac{{\tau }_i-{\tau }_{i-1}}{u}\right)\right]dx\le C^{\prime }\phi (u\sigma (\mathbf{p}{)}^{-1})\sigma (\mathbf{p}{)}^{-p}\le C^{\prime \prime }u\sigma (\mathbf{p}{)}^{p/2},\end{array}$$

for some $C^{\prime },C^{\prime \prime }>0$  and every $u$  large enough. Therefore, the same kind of bound, with possibly larger $C^{\prime \prime }$  , holds for every $u\ge 1$  , and since $ns,nt$  are distinct integers, we showed that $E\left[G_{n(t-s)}\sigma \right(\mathbf{p}{)}^p]\le C_{1}n\sigma (\mathbf{p}{)}^{p/2}|s-t|\sigma (\mathbf{p}{)}^{p/2}$  uniformly in such $n,s,t$  , where $C_1=C_1(\mu ,p)>0$  .

Let us now handle the second term in ( 28 ). Using time-reversal, we see that this equals $$\#\left\{n(t-s)<k\le nt\wedge \kappa \left({max}_{1\le l\le n(t-s)}S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\right):S\sigma (\mathbf{p}{)}_k^{\mathcal{ℱ}}={max}_{n(t-s)\le l\le k}S\sigma (\mathbf{p}{)}_l^{\mathcal{ℱ}}\right\}$$  in distribution, where $\kappa \left(x\right)=max\{k:S\sigma (\mathbf{p}{)}_k^{\mathcal{ℱ}}<x\}$  (with the convention $max\mathbb{\varnothing }=0$  ). By using Markov’s property at time $n(t-s)$  , this has same distribution as $G_{ns\wedge \kappa ({\tilde{M}}_{n(t-s)}-{\tilde{S}}_{n(t-s)})}$  , where $G$  is defined as above, while $\tilde{S}$  is an independent copy of $S\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}$  with maximum process $\tilde{M}$  .

By monotonicity of $G$  this is less than $G_{{\kappa }^{\prime }({\tilde{M}}_{n(t-s)}-{\tilde{S}}_{n(t-s)})}$  where ${\kappa }^{\prime }\left(x\right)=min\{k:S\sigma (\mathbf{p}{)}_k^{\mathcal{ℱ}}\ge x\}$  .

Let us prove that $E\sigma (\mathbf{p}{)}_{\infty }^{\mu }[G_{{\kappa }^{\prime }\left(x\right)}\sigma (\mathbf{p}{)}^p]\le Cx\sigma (\mathbf{p}{)}^p$  for every $x\ge 0$  , for some $C>0$  . To this end, notice that

$$\begin{array}{c}{M}_{n(t-s)}={\sum }_{i=1}\sigma (\mathbf{p}{)}^{G_{n(t-s)}}(S\sigma (\mathbf{p}{)}_{{\tau }_i}^{\mathcal{ℱ}}-S\sigma (\mathbf{p}{)}_{{\tau }_{i-1}}^{\mathcal{ℱ}}),\end{array}$$

(29)

and it is a classical result of fluctuation theory that the variables $S\sigma (\mathbf{p}{)}_{{\tau }_i}^{\mathcal{ℱ}}-S\sigma (\mathbf{p}{)}_{{\tau }_{i-1}}^{\mathcal{ℱ}}$  are independent with common distribution $P\sigma (\mathbf{p}{)}_{\infty }^{\mu }(S\sigma (\mathbf{p}{)}_{{\tau }_1}^{\mathcal{ℱ}}=i)=\mu \left(\right[i+1,\infty \left)\right),i\ge 0$  , so their mean is $\sigma \sigma (\mathbf{p}{)}^2/2$  , where $\sigma \sigma (\mathbf{p}{)}^2$  is the variance of $\mu$  , and notice that these variables have small exponential moments. Now, the usual large deviations theorem shows that for some $a,N>0$  and for every $n\ge N$  ,

$$\begin{array}{c}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left(\frac{{\sum }_{i=1}\sigma (\mathbf{p}{)}^n(S\sigma (\mathbf{p}{)}_{{\tau }_i}^{\mathcal{ℱ}}-S\sigma (\mathbf{p}{)}_{{\tau }_{i-1}}^{\mathcal{ℱ}})}{n}<\frac{\sigma \sigma (\mathbf{p}{)}^2}{4}\right)\le exp(-an).\end{array}$$

(30)

Now, using ( 29 ) in the second equality, 4 ASYMPTOTICS FOR MAPS

$$\begin{array}{ccc}E\sigma (\mathbf{p}{)}_{\infty }^{\mu }[G_{{\kappa }^{\prime }\left(x\right)}\sigma (\mathbf{p}{)}^p]& =& p{\int }_0\sigma (\mathbf{p}{)}^{\infty }u\sigma (\mathbf{p}{)}^{p-1}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }(G_{{\kappa }^{\prime }\left(x\right)}>u)du\end{array}$$

$$\begin{array}{ccc}& =& p{\int }_0\sigma (\mathbf{p}{)}^{\infty }u\sigma (\mathbf{p}{)}^{p-1}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left({\sum }_{i=1}\sigma (\mathbf{p}{)}^{\lceil u\rceil }(S\sigma (\mathbf{p}{)}_{{\tau }_i}^{\mathcal{ℱ}}-S\sigma (\mathbf{p}{)}_{{\tau }_{i-1}}^{\mathcal{ℱ}})<x\right)du\end{array}$$

$$\begin{array}{ccc}& =& px\sigma (\mathbf{p}{)}^p{\int }_0\sigma (\mathbf{p}{)}^{\infty }v\sigma (\mathbf{p}{)}^{p-1}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left({\sum }_{i=1}\sigma (\mathbf{p}{)}^{\lceil xv\rceil }(S\sigma (\mathbf{p}{)}_{{\tau }_i}^{\mathcal{ℱ}}-S\sigma (\mathbf{p}{)}_{{\tau }_{i-1}}^{\mathcal{ℱ}})<\frac{xv}{v}\right)dv\end{array}$$

$$\begin{array}{ccc}& \le & px\sigma (\mathbf{p}{)}^p\left({\int }_0\sigma (\mathbf{p}{)}^{4\sigma \sigma (\mathbf{p}{)}^{-2}}v\sigma (\mathbf{p}{)}^{p-1}dv+{\int }_{4\sigma \sigma (\mathbf{p}{)}^{-2}}\sigma (\mathbf{p}{)}^{\infty }v\sigma (\mathbf{p}{)}^{p-1}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left({\sum }_{i=1}\sigma (\mathbf{p}{)}^{\lceil xv\rceil }(S\sigma (\mathbf{p}{)}_{{\tau }_i}^{\mathcal{ℱ}}-S\sigma (\mathbf{p}{)}_{{\tau }_{i-1}}^{\mathcal{ℱ}})<\frac{\sigma \sigma (\mathbf{p}{)}^{2}xv}{4}\right)dv\right).\end{array}$$

Now, as soon as $x$  is large enough, i.e. $4x\sigma \sigma (\mathbf{p}{)}^{-2}\ge N$  , where $N$  is defined before ( 30 ), the probability in the second integral is bounded by $exp(-axv)\le exp(-v)$  if we further ask $x>a\sigma (\mathbf{p}{)}^{-1}$  . Thus the wanted bound on $E\sigma (\mathbf{p}{)}_{\infty }^{\mu }[G_{{\kappa }^{\prime }\left(x\right)}\sigma (\mathbf{p}{)}^p]$  . By the independence of $\tilde{S}$  , we conclude that 4 ASYMPTOTICS FOR MAPS

$$\begin{array}{ccc}E\sigma (\mathbf{p}{)}_{\infty }^{\mu }[\left(G_{{\kappa }^{\prime }({\tilde{M}}_{n(t-s)}-{\tilde{S}}_{n(t-s)})}\right)\sigma (\mathbf{p}{)}^p]& \le & CE\sigma (\mathbf{p}{)}_{\infty }^{\mu }[(M_{n(t-s)}-S\sigma (\mathbf{p}{)}_{n(t-s)}^{\mathcal{ℱ}}\left)\sigma \right(\mathbf{p}{)}^p]\end{array}$$

(31)

$$\begin{array}{ccc}& \le & 2\sigma (\mathbf{p}{)}^{p-1}C\left(1+\left(\frac{p}{p-1}\right)\sigma (\mathbf{p}{)}^p\right)E\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left[\right(S\sigma (\mathbf{p}{)}_{n(t-s)}^{\mathcal{ℱ}})\sigma (\mathbf{p}{)}^p],\end{array}$$

where we used Doob’s inequality $E\sigma (\mathbf{p}{)}_{\infty }^{\mu }[M_{n(t-s)}\sigma (\mathbf{p}{)}^p]\le (p/(p-1\left)\right)\sigma (\mathbf{p}{)}^{p}E\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left[\right(S\sigma (\mathbf{p}{)}_{n(t-s)}^{\mathcal{ℱ}})\sigma (\mathbf{p}{)}^p]$  , since $S\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}$  is centered. Now we use the following consequence of Rosenthal’s inequality [24] : if $X_1,\dots ,X_n$  are independent centered random variables (not necessarily identically distributed), then for every $p\ge 2$  there exists $C\left(p\right)$  such that

$$\begin{array}{c}\mathbb{E}\left[\right|X_1+\dots +X_n\left|\sigma \right(\mathbf{p}{)}^p]\le C(p\left)n\sigma \right(\mathbf{p}{)}^{p/2-1}{\sum }_{i=1}\sigma (\mathbf{p}{)}^n\mathbb{E}[\left|X_i\right|\sigma (\mathbf{p}{)}^p].\end{array}$$

(32)

This shows that $E\sigma (\mathbf{p}{)}_{\infty }^{\mu }[\left(S\sigma \right(\mathbf{p}{)}_{n(t-s)}^{\mathcal{ℱ}}\left)\sigma \right(\mathbf{p}{)}^p]\le C^{\prime }(p\left)n\sigma \right(\mathbf{p}{)}^{p/2}|s-t|\sigma (\mathbf{p}{)}^{p/2}$  for some $C^{\prime }\left(p\right)>0$  , for every $s,t$  such that $ns,nt\in {\mathbb{Z}}_{+}$  , and therefore the same kind of upper bound holds for the quantity in ( 31 ).

Putting things together, we have obtained that for every $p\ge 2$  and some $C_2=C_2(\mu ,p)>0$  , $${sup}_{n\ge 1}{sup}_{s,t\ge 0,ns,nt\in {\mathbb{Z}}_{+}}E\sigma (\mathbf{p}{)}_{\infty }^{\mu }\left[\left|\frac{H\sigma (\mathbf{p}{)}_{ns}^{\mathcal{ℱ}}-H\sigma (\mathbf{p}{)}_{nt}^{\mathcal{ℱ}}}{\sqrt{n}}\right|\sigma (\mathbf{p}{)}^p\right]\le C_2|s-t\left|\sigma \right(\mathbf{p}{)}^{p/2}.$$  Since $H\sigma (\mathbf{p}{)}^{\mathcal{ℱ}}$  is defined by linear interpolation between integer abscissa, it is elementary that a similar estimate holds when taking the supremum over all $s,t\ge 0$  , up to taking a larger $C_2$  .

The proof of the usual Kolmogorov’s continuity theorem (see e.g. [27] ) entails the result. $\square$  Proof of Lemma  2 . This result follows an approach taken in [20] , using again the Łukaciewicz walk, and can be found in [16] . We therefore only sketch details. We bound the probability under consideration by $\left[An\right]{max}_{0\le k\le An}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }(\left|u\right(k\left)\right|\ge n\sigma (\mathbf{p}{)}^{1/2+\eta })$  , then use the fact that $\left|u\right(k\left)\right|$  is equal in law to $G_k$  , the number of weak records introduced above. Then, using ( 29 ) and a moderate deviation theorem allows to bound ${max}_{0\le k\le n}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }(|M_k-\sigma \sigma (\mathbf{p}{)}^2{G}_k/2|>n\sigma (\mathbf{p}{)}^{1/2+\eta /2})\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon })$  for some $\varepsilon >0$  and $n$  large, so it suffices to show that ${max}_{0\le k\le n}P\sigma (\mathbf{p}{)}_{\infty }^{\mu }(M_k\ge n\sigma (\mathbf{p}{)}^{1/2+\eta })\le exp(-n\sigma (\mathbf{p}{)}^{\varepsilon })$  for some $\varepsilon >0$  and $n$  large, and this is easy by a standard maximal inequality and applying the proof of the standard large deviations theorem. $\square$  Proof of Lemma  3 . By the Otter-Dwass formula, the probability that a forest with $r$  roots has $N$  individuals is given by $rP(S_N=N-r)/N$  , where $S$  is a random walk with step distribution equal to the offspring distribution of the GW process. Now, letting $r=n\sigma (\mathbf{p}{)}^{1/2+\eta }$  , REFERENCES

$$\begin{array}{ccc}P\sigma (\mathbf{p}{)}_{\left[n\sigma \right(\mathbf{p}{)}^{1/2+\eta }]}^{\mu }(|\mathcal{ℱ}|<An)& =& {\sum }_{i=\left[n\sigma \right(\mathbf{p}{)}^{1/2+\eta }]}\sigma (\mathbf{p}{)}^{\left[An\right]}\frac{n\sigma (\mathbf{p}{)}^{1/2+\eta }}{i}P(S_i-i=-n\sigma (\mathbf{p}{)}^{1/2+\eta })\end{array}$$

$$\begin{array}{ccc}& \le & An{max}_{1\le i\le An}P(S_i-i=-n\sigma (\mathbf{p}{)}^{1/2+\eta }),\end{array}$$

the lemma is deduced thanks to a classical moderate deviations estimate, using the fact that $\mu$  has small exponential moments. $\square$  References

1. D. Aldous, (1991) The continuum random tree. II: An overview., Stochastic analysis, Proc. Symp., Durham/UK 1990, Lond. Math. Soc. Lect. Note Ser. 167, 23-70.
2. D. Aldous, (1991), The continuum random tree. III., Ann. Probab. 21, No.1, 248-289.
3. O. Angel & O. Schramm, (2003) Uniform infinite planar triangulations, Comm. Math. Phys., vol. 241, No. 2-3, 191–213.
4. O. Angel, (2003) Growth and percolation on the uniform infinite planar triangulation, Geom. Funct. Anal., Vol. 13, No. 5, 935–974.
5. D. Burago, Y. Burago, Yuri & S. Ivanov, (2001) A course in metric geometry, Graduate Studies in Math., 33, Am. Math. Soc., Providence, RI.
6. P. Billingsley, (1968) Convergence of probability measures, New York-London-Sydney-Toronto: Wiley and Sons.
7. J. Bouttier, P. Di Francesco & E. Guitter, (2004) Planar maps as labeled mobiles, Elec. Journ. Comb. 11 , #R 69.
8. P. Chassaing & B. Durhuus, (2003) Statistical Hausdorff dimension of labeled trees and quadrangulations, arXiv: math.PR/0311532.
9. P. Chassaing & G. Schaeffer, (2004) Random planar lattices and integrated superBrownian excursion., Prob. Theory Rel. Fields., Vol. 128, No. 2, 161 212.
10. R. Cori & B. Vauquelin, (1981) Planar maps are well labeled trees. Canad. J. Math. 33(5), 1023-1042.
11. T. Duquesne & J.-F. Le Gall, (2002) Random trees, Levy processes and spatial branching processes, Astérisque 281.
12. W. Feller, (1971) An introduction to probability theory and its applications, Volume II, 2nd edition, Wiley.
13. B. Gittenberger, (2003) A note on “State spaces of the snake and its tour – Convergence of the discrete snake” by J.-F. Marckert and A. Mokkadem. J. Theo. Probab. 16, No. 4, 1063-1067.
14. S. Janson & J.F. Marckert, (2003) Convergence of discrete snake., To appear in J. Theor. Probab.
15. REFERENCES T. Kurtz, R. Lyons, R. Pemantle & Y. Peres, (1994) A conceptual proof of the Kesten Stigum Theorem for mutlitype branching processes. Classical and modern branching processes (Minneapolis, MN), IMA Vol. Math. Appl 84, 181–185, Springer, New York
16. J.-F. Le Gall, (2004) Arbres aléatoires et applications. Cours de DEA. Available via http://www.dma.ens.fr.
17. J.-F. Le Gall, (2005) An invariance principle for conditioned trees arXiv: math.PR/0503263.
18. J.-F. Le Gall & M. Weill, (2005) Conditioned Brownian trees. arXiv: math.PR/0501066.
19. J.-F. Marckert & A. Mokkadem, (2003) The depth first processes of Galton-Watson trees converge to the same Brownian excursion, Ann. Probab. Vol. 31, No. 3.
20. J.-F. Marckert & A. Mokkadem, (2003) Ladder variables, Internal structure of Galton-Watson trees and Finite branching random walks, J. of App. Probab. Vol. 40, No. 3.
21. J.-F. Marckert & A. Mokkadem, (2003) States spaces of the snake and of its tour – Convergence of the discrete snake, J. Theor. Probab. 16, No.4, 1015-1046.
22. J.-F. Marckert & A. Mokkadem, (2003) Limit of Normalized Quadrangulations : the Brownian map, arxiv: math.PR/0403398.
23. G. Miermont, (2005) The limiting genealogy of critical multitype Galton-Watson trees, in preparation.
24. V.V. Petrov, (1995) Limit theorems of probability theory. Sequences of independent random variables, Oxford Studies in Probab. 4.
25. J. Pitman, (2002) Combinatorial Stochastic Processes, Lecture Notes for St-Flour Summer School. Available via www.stat.berkeley.edu/ $\sim$  pitman
26. S.C. Port, (1994) Theoretical probability for applications,Wiley.
27. D. Revuz & M. Yor, (1999) Continuous martingales and Brownian motion, Springer.
28. G. Schaeffer, (1998) Conjugaison d’arbres et cartes combinatoires aléatoires., PhD Thesis, Université Bordeaux I.