Scaling limits of random bipartite planar maps with a prescribed degree sequence

We study the asymptotic behaviour of uniform random maps with a prescribed face-degree sequence, in the bipartite case, as the number of faces tends to in nity. Under mild assumptions, we show that, properly rescaled, such maps converge in distribution towards the Brownian map in the Gromov-Hausdor sense. This result encompasses a previous one of Le Gall for uniform random q-angulations where q is an even integer. It applies also to random maps sampled from a Boltzmann distribution, under a second moment assumption only, conditioned to be large in either of the sense of the number of edges, vertices, or faces. The proof relies on the convergence of so-called "discrete snakes" obtained by adding spatial positions to the nodes of uniform random plane trees with a prescribed child sequence recently studied by Broutin & Marckert. This paper can alternatively be seen as a contribution to the study of the geometry of such trees.

Introduction . Random planar maps as metric spaces

The study of scaling limits of large random maps, viewed as metric spaces, towards a universal object called the Brownian map has seen numerous developments over the last decade. This paper is another step towards this universality as we show that the Brownian map appears as limit of maps with a prescribed face-degree sequence. This particular model is introduced in the next subsection, let us the rst discuss the general idea of such studies and recall some previous results.

Recall that a (planar) map is an embedding of a nite connected graph into the two-dimensional sphere, viewed up to orientation-preserving homeomorphisms. For technical reasons, the maps we consider will always be rooted, which means that an oriented edge is distinguished. Maps have been widely studied in combinatorics and random maps are of interest in theoretical physics, for which they are a natural discretised version of random geometry, in particular in the theory of quantum gravity (see e.g. [ ]). One can view a map as a ( nite) metric space by endowing the set of vertices with the graph distance: the distance between two vertices is the minimal number of edges of a path going from one to the other; throughout this paper, if M is a map, we shall denote the associated metric space, with a slight abuse of notation, by (M, d gr ). The set of all compact metric spaces, considered up to isometry, can be equipped with a metric, called the Gromov-Hausdor distance, which makes it separable and complete [ , ]; we can then study the convergence in distribution of random maps viewed as metric spaces.

The rst and fondamental result in this direction has been obtained simultaneously by Le Gall [ ] and Miermont [ ] using di erent approaches. We call faces of a map the connected components of the complement of the edges; the degree of a face is then the number of edges incident to it, with the convention that if both sides of an edge are incident to the same face, then it is counted twice. A quadrangulation is a map in which all faces have degree 4. In [ ] and [ ], it is shown that if Q n is a uniform random rooted quadrangulation with n faces, then the convergence in distribution

Q n , 9 8n 1/4 d gr (d) -→ n→∞ (M, D),
holds in the sense of Gromov-Hausdor , where the limit (M, D), called the Brownian map, is a random compact metric space, which is almost surely homeomorphic to the 2-sphere (Le Gall & Paulin [ ],

Miermont [ ]) and has Hausdor dimension 4 (Le Gall [ ]). Let us mention that the Brownian map rst appeared in the work of Marckert & Mokkadem [ ] as a limit of rescaled quadrangulations for a distance di erent than the Gromov-Hausdor distance.

Le Gall [ ] designs also a general method to prove such a limit theorem for other classes of random maps, using the above convergence of quadrangulations. Indeed, the main result in [ ] is stated for q-angulations (which are maps in which each face has degree q) with n faces, for any q ∈ {3, 4, 6, 8, . . . } xed. The limit is always the Brownian map as well as the scaling factor n -1/4 , only the multiplicative constant (9/8) 1/4 above depends on q (see the precise statement below). Note that apart from the case q = 3 of triangulations, [ ] only deals with maps with even face-degrees, which corresponds in the planar case to bipartite maps. The non-bipartite case is technically more involved and we henceforth restrict ourselves to bipartite maps as well. In this paper, we consider a large class of maps which enables us to recover and extend previous results, but we stress that it does not recover the one above on quadrangulations; as a matter of fact, as in [ ], we use the latter in our proof.

. Main result and notation

We generalise q-angulations by considering maps with possibly faces of di erent degrees. For every integer n ≥ 2, we are given a sequence n = (n i ; i ≥ 1) of non-negative integers satisfying i ≥1 n i = n, and we denote by M(n) the nite set of rooted planar maps with n i faces of degree 2i for every i ≥ 1. Let us introduce the notation that we shall use throughout this paper. Set

N n = i ≥1 in i and n 0 = 1 + N n -n. ( )
It is easy to see that every map in M(n) contains n faces and N n edges so, according to Euler's formula, it has 2 + N nn = n 0 + 1 vertices (this shift by one will simplify some statements later). We next de ne a probability measure and its variance by

p n (i) = n i N n + 1 for i ≥ 0 and σ 2 n = i ≥1 i 2 p n (i) - N n N n + 1 2 .
The probability p n is (up to the fact that there are n 0 + 1 vertices) the empirical half face-degree distribution of a map in M(n) if one sees the vertices as faces of degree 0. Last, let us denote by

∆ n = max{i ≥ 0 : n i > 0}
the right edge of the support of p n .

Our main assumption is the following: there exists a probability measure p = (p(i); i ≥ 0) with mean 1 and variance σ 2 p = i ≥1 i 2 p(i) -1 ∈ (0, ∞) such that, as |n| = n → ∞,

p n ⇒ p, σ 2 n → σ 2 p and n -1/2 ∆ n → 0, (H)
Its cardinal was rst calculated by Tutte [ ] who considered the dual maps, i.e. Eulerian maps with a prescribed vertexdegree sequence.

where "⇒" denotes the weak convergence of probability measures, which is here equivalent to p n (i) → p(i) for every i ≥ 0.

Theorem . Under (H), if M n is sampled uniformly at random in M(n) for every n ≥ 2, then the following convergence in distribution holds in the sense of Gromov-Hausdor :

M n , 9 4 1 -p(0) σ 2 p 1 n 1/4 d gr (d) -→ n→∞ (M, D).
Since the graph distance is de ned in terms of edges, it would be natural to make the rescaling depend on N n rather than n. Under (H), we have n/N n → 1-p(0) as n → ∞ so the previous convergence is equivalent to

M n , 9 4σ 2 p 1 N n 1/4 d gr (d) -→ n→∞ (M, D).
This result recovers the aforementioned one of Le Gall [ ] for 2κ-angulations for κ ≥ 2. Indeed, these correspond to M(n) where n i = n if i = κ and n i = 0 otherwise. In this case N n = nκ and (H) is ful lled with p(κ) = 1p(0) = κ -1 and so σ 2 p = κ -1. Theorem therefore immediately yields: .

Corollary (Le Gall [ ]).

Boltzmann random maps

Theorem also applies to random maps sampled from a Boltzmann distribution. Given a sequence q = (q k ; k ≥ 1) of non-negative real numbers, we de ne a measure W q on the set M of rooted bipartite maps by the formula W q (M) = f ∈Faces(M)

q deg(f )/2 , M ∈ M,
where Faces(M) is the set of faces of M and deg(f ) is the degree of such a face f . Set Z q = W q (M); whenever it is nite, the formula

P q (•) = 1 Z q W q (•)
de nes a probability measure on M. We consider next such random maps conditioned to have a large size for several notions of size. For every integer n ≥ 1, let M E=n , M V =n and M F =n be the subsets of M of those maps with respectively n edges, n vertices and n faces. For every S = {E, V , F } and every n ≥ 1, we de ne P q S =n (M) = P q (M | M ∈ M S =n ), M ∈ M S =n , the law of a Boltzmann map conditioned to have size n; here and later, we shall always, if necessary, implicitly restrict ourselves to those values of n for whichW q (M S =n ) 0, and limits shall be understood along this subsequence. Under mild integrability conditions on q, we prove in Section that for every S ∈ {E, V , F }, there exists a constant K q S > 0 such that if M n is sampled from P q S =n for every n ≥ 1, then the convergence in distribution

M n , K q S n 1/4 d gr (d) -→ n→∞ (M, D),
holds in the sense of Gromov-Hausdor . We refer to Theorem for a precise statement. Observe that for any choice S ∈ {E, V , F }, if M n is sampled from P q S =n then, conditional on its degree sequence, say, ν M n = (ν M n (i); i ≥ 1), it has the uniform distribution in M(ν M n ). The proof of the above convergence consists in showing that ν M n satis es (H) in probability for some deterministic limit law p q . Indeed, by Skorohod's representation Theorem, there exists then a probability space where versions of ν M n under P q S =n satisfy (H) almost surely so we may apply Theorem and conclude the convergence in law of the rescaled maps.

The case S = V was obtained by Le Gall [ , Theorem . ], relying on results of Marckert & Miermont [ ], when q is regular critical, meaning that the distribution p q (which is roughly that of the half-degree of a typical face when we see vertices as faces of degree 0) admits small exponential moments. Here, we generalise this result (and consider other conditionings) to all generic critical sequences q, i.e. those for which p q admits a second moment.

Let us mention that Le Gall & Miermont [ ] have also considered Boltzmann random maps with n vertices in which the distribution of the degree of a typical face is in the domain of attraction of a stable distribution with index α ∈ (1, 2) and obtained di erent objects at the limit (after extraction of a subsequence). Also, Janson & Stefánsson [ ] have studied maps with n edges which exhibit a condensation phenomenon and converge, after rescaling, towards the Brownian tree: a unique giant face emerges and its boundary collapses into a tree.

The conditioning S = E by the number of edges is somewhat di erent since the set M E=n is nite so the distribution P q E=n (•) = W q (•)/W q (M E=n ) on M E=n makes sense even if W q (M) is in nite; we shall see that the above convergence still holds in this case (Theorem ). The simplest example is the constant sequence q k = 1 for every k ≥ 1, in which case P q E=n corresponds to the uniform distribution in M E=n ; in this case, we calculate K q E = 1/2, which recovers a result rst due to Abraham [ ]:

Corollary (Abraham [ ]). For every n ≥ 1, let B n be a uniform random bipartite map with n edges. The following convergence in distribution holds in the sense of Gromov-Hausdor :

B n , 1 2n 1/4 d gr (d) -→ n→∞ (M, D).
.

Approach and organisation of the paper

Our approach to proving Theorem follows closely the robust one of Le Gall [ ]. Speci cally, we code our map M n by a certain labelled (or spatial) two-type tree (T n , ℓ n ) via a bijection due to Bouttier, Di Francesco & Guitter [ ]: T n is a plane tree and ℓ n is a function which associates with each vertex of T n a label (or a spatial position) in Z. Such a labelled tree is itself encoded by a pair of discrete paths (C • n , L • n ); we show that under (H), this pair, suitably rescaled, converges in distribution towards a pair (e, Z ) called in the literature the "head of the Brownian snake" (e.g. [ , , ]). The construction of the Brownian map from (e, Z ) is analogous to the Bouttier-Di Francesco-Guitter bijection; as it was shown by Le Gall [ ], Theorem follows from this functional limit theorem as well as a certain"invariance under re-rooting" of our maps.

To prove such an invariance principle for (T n , ℓ n ), we further rely on a more recent bijection due to Janson & Stefánsson [ ] which maps two-type trees to one-type trees which are easier to control. As a matter of fact, if M n is uniformly distributed in M(n) and (T n , l n ) is its corresponding labelled one-type tree, then the unlabelled tree T n is a uniform random tree with a prescribed degree (in the sense of o spring) sequence as studied by Broutin & Marckert [ ]. The labelled tree (T n , l n ) is again encoded by a pair of functions (H n , L n ) and the main result of [ ] is, under the very same assumption (H), the convergence of H n suitably rescaled towards e. Our main contribution, see Theorem , consists in strengthening this result by adding the labels to show that the pair (H n , L n ), suitably rescaled, converges towards (e, Z ), and then transporting this invariance principle back to the two-type tree (T n , ℓ n ).

The previous works on the convergence of large random labelled trees focus on the case when the tree is a size-conditioned (one or multi-type) Galton-Watson tree and a lot of e ort has been put to reduce the assumptions of the labels as much as possible, maintaining quite strong assumption on the tree itself; a common assumption is indeed to consider a Galton-Watson tree whose o spring distribution admits small exponential moments; in order to reduce the assumption on the labels, Marckert [ ] even supposes the o springs to be uniformly bounded. In this paper, we take the opposite direction: we focus only on the labels given by the bijection with planar maps, which satisfy rather strong assumptions, and work under weak assumptions on the tree (essentially a second moment condition). Furthermore, we consider trees with a prescribed degree sequence, which are more general than Galton-Watson trees and on which the literature is limited, which explains the length of this work.

Let us mention that other convergences towards the Brownian map similar to Theorem have been obtained using also other bijections with labelled trees: Beltran & Le Gall [ ] studied random quadrangulations without vertices of degree one, Addario-Berry & Albenque [ ] considered random triangulations and quadrangulations without loops or multiple edges and Bettinelli, Jacob & Miermont [ ] uniform random maps with n edges.

This work leaves open two questions that we plan to investigate in the future. First, one can consider non-bipartite maps with a prescribed degree sequence; we restricted ourselves here to bipartite maps because (except in the notable case of triangulations), in the non-bipartite case, the Bouttier-Di Francesco-Guitter bijection yields a more complicated labelled three-type tree which is harder to analyse; moreover, the Janson-Stefánsson bijection does not apply to such trees so the method of proof should be di erent. A second direction of future work would be to relax the assumption (H), in particular to consider maps with large faces. A rst step would be to extend the work of Broutin & Marckert [ ] on plane trees; we believe that the family of so-called inhomogeneous continuum random trees introduced in [ , ] appears at the limit; one would then construct a family of random maps from these trees, replacing the Brownian excursion e by their "exploration process" studied in [ ].

This paper is organised as follows. In Section , we rst introduce the notion of labelled onetype and two-type trees and their encoding by functions, then we describe the Bouttier-Di Francesco-Guitter and Janson-Stefánsson bijections. In Section , we de ne the pair (e, Z ) and the Brownian map and we state our main results on the convergence of discrete paths. Section is a technical section in which we extend a "backbone decomposition" of Broutin & Marckert [ ], the results are stated there and proved in Appendix A. We prove the convergence of the pairs (C • n , L • n ) and (H n , L n ), which encode the labelled trees (T n , ℓ n ) and (T n , l n ) respectively, in Section . Then we prove Theorem in section . Finally, we apply our results to Boltzmann random maps in Section .

Acknowledgments I am deeply indebted to Grégory Miermont for suggesting me to study this model, for several discussions during the preparation of this work and for pointing me out some inaccuracies in a rst draft. Many thanks also to all the persons I have asked about Remark , and in particular Olivier Hénard who then asked me every morning if I succeeded proving it until I tried another way (Corollary ). Finally, I am grateful to the two anonymous referees for their constructive remarks.

Maps and trees . Plane trees and their encoding with paths

Let N = {1, 2, . . . } be the set of all positive integers, set N 0 = { } and consider the set of words

U = n ≥0 N n .
For every u = (u 1 , . . . , u n ) ∈ U, we denote by |u| = n the length of u; if n ≥ 1, we de ne its pre x pr (u) = (u 1 , . . . , u n-1 ) and for = ( 1 , . . . , m ) ∈ U, we let u = (u 1 , . . . , u n , 1 , . . . , m ) ∈ U be the concatenation of u and . We endow U with the lexicographical order: given u, ∈ U, let w ∈ U be their longest common pre x, that is u = w(u 1 , . . . , u n ), = w( 1 , . . . , m ) and u 1 1 , then u < if u 1 < 1 . A plane tree is a non-empty, nite subset τ ⊂ U such that:

(i) ∈ τ ; (ii) if u ∈ τ with |u| ≥ 1, then pr (u) ∈ τ ;
(iii) if u ∈ τ , then there exists an integer k u ≥ 0 such that ui ∈ τ if and only if 1 ≤ i ≤ k u .

We shall denote the set of plane trees by T. We will view each vertex u of a tree τ as an individual of a population for which τ is the genealogical tree. The vertex is called the root of the tree and for every u ∈ τ , k u is the number of children of u (if k u = 0, then u is called a leaf, otherwise, u is called an internal vertex) and u1, . . . , uk u are these children from left to right, |u| is its generation, pr (u) is its parent and more generally, the vertices u, pr (u), pr • pr (u), . . . , pr |u | (u) = are its ancestors; the longest common pre x of two elements is their last common ancestor. We shall denote by u, the unique non-crossing path between u and .

Fix a tree τ with N edges and let = u 0 < u 1 < • • • < u N be its vertices, listed in lexicographical order. We describe three discrete paths which each encode τ . First, its Łukasiewicz path W = (W (j); 0 ≤ j ≤ N + 1) is de ned by W (0) = 0 and for every 0 ≤ j ≤ N ,

W (j + 1) = W (j) + k u j -1.
One easily checks that W (j) ≥ 0 for every 0 ≤ j ≤ N but W (N + 1) = -1. Next, we de ne the height process H = (H (j); 0 ≤ j ≤ N ) by setting for every 0 ≤ j ≤ N ,

H (j) = |u j |.
Finally, de ne the contour sequence (c 0 , c 1 , . . . , c 2N ) of τ as follows: c 0 = and for each i ∈ {0, . . . , 2N -1}, c i+1 is either the rst child of c i which does not appear in the sequence (c 0 , . . . , c i ), or the parent of c i if all its children already appear in this sequence. The lexicographical order on the tree corresponds to the depth-rst search order, whereas the contour order corresponds to "moving around the tree in clockwise order". The contour process C = (C(j); 0 ≤ j ≤ 2N ) is de ned by setting for every 0 ≤ j ≤ 2N ,

C(j) = |c j |.
Without further notice, throughout this work, every discrete path shall also be viewed as a continuous function after interpolating linearly between integer times.

. Labelled plane trees and label processes Two-type trees We will use the expression "two-type tree" for a plane tree in which we distinguish vertices at even and odd generation; call the former white and the latter black, we denote by •(T) and •(T) the sets of white and black vertices of a two-type tree T. We denote by T •,• the set of two-type trees. Let N be the number of edges of such a tree T, denote by (c 0 , . . . , c 2N ) its contour sequence and

C = (C(k); 0 ≤ k ≤ 2N ) its contour process; for every 0 ≤ k ≤ N , set c • k = c 2k , the sequence (c • 0 , . . . , c • N
) is called the white contour sequence of T and we de ne its white contour process

C • = (C • (k); 0 ≤ k ≤ N ) by C • (k) = |c • k |/2 for every 0 ≤ k ≤ N . One easily sees that sup t ∈[0,1] |C(2N t) -2C • (N t)| = 1 so C
• encodes the geometry of the tree up to a small error.

A labelling ℓ of a two-type tree T is a function de ned on the set •(T) of its white vertices to Z such that

• the root of T is labelled 0,

• for every black vertex, the increments of the labels of its white neighbours in clockwise order are greater than or equal to -1.

We de ne the white label process

L • = (L • (k); 0 ≤ k ≤ N ) of T by L • (k) = ℓ(c • k ) for every 0 ≤ k ≤ N .
The labelled tree (T, ℓ) is, up to a small error, encoded by the pair (C • , L • ), see Figure . A two-type labelled tree, its white contour process on top and its white label process below.

One-type trees As opposed to two-type trees, plane trees in which vertices at even and odd generation play the same role will be called "one-type trees" and not just "trees" to emphasise the di erence.

Recall that the geometry of a one-type tree T is encoded by its height process H . A labelling l of such a tree is a function de ned on the set of vertices to Z such that

• the root of T is labelled 0,

• for every internal vertex, its right-most child carries the same label as itself,

• for every internal vertex, the label increment between itself and its rst child is greater than or equal to -1, and so are the increments between every two consecutive children from left to right.

De ne the label process L(k) = l(u k ), where (u 0 , . . . , u N ) is the sequence of vertices of T in lexicographical order; the labelled tree is (exactly) encoded by the pair (H, L), see Figure . Notational remark We use roman letters T , l, H , L for one-type trees and calligraphic letters T, ℓ, C, L for two-type trees. We stress also that we consider the contour order for two-type trees and the lexicographical order for one-type trees.

. The Bouttier-Di Francesco-Guitter bijection

A map is said to be pointed if a vertex is distinguished. Given a sequence n of non-negative integers, we denote by M ⋆ (n) the set of rooted and pointed planar maps with n i faces with degree 2i for every i ≥ 1.

Let T •,• (n) denote the set of two-type trees with n i black vertices with degree i for every i ≥ 1; note that such a tree has n 0 white vertices and N n edges, which are both de ned in ( ). Let further LT •,• (n) be the set of such labelled two-type trees.

0 -1 -2 1 0 -1 -2 -1 -1 -2 0 ⋆ 0 -1 -2 1 0 -1 -2 -1 -1 -2 0 0 3 2 1 4 3 2 1 2 2 1 3 Figure :
The Bouttier-Di Francesco-Guitter bijection.

Bouttier, Di Francesco & Guitter [ ] show that M ⋆ (n) and {-1, +1} × LT •,• (n) are in bijection, we shall refer to it as the BDG bijection. Let us only recall how a map is constructed from a labelled two-type tree (T, ℓ), as depicted by Figure . Let N be the number of edges of T, we write (c • 0 , . . . , c • N ) for its white contour sequence and we adopt the convention that c • N +i = c • i for every 0 ≤ i ≤ N . A white corner is a sector around a white vertex delimited by two consecutive edges; there are N white corners, corresponding to the vertices c • 0 , . . . , c • N -1 ; for every 0 ≤ i ≤ 2N we denote by e i the corner corresponding to c • i . We add an extra vertex ⋆ outside the tree T and construct a map on the vertex-set of T and ⋆ by drawing edges as follows: for every

0 ≤ i ≤ N -1, • if ℓ(c • i ) > min 0≤k ≤N -1 ℓ(c • k )
, then we draw an edge between e i and e j where j = min{k > i :

ℓ(c • k ) = ℓ(c • i ) -1}, • if ℓ(c • i ) = min 0≤k ≤N -1 ℓ(c • k )
, then we draw an edge between e i and ⋆. It is shown in [ ] that this procedure indeed produces a planar map M, pointed at ⋆, and rooted at the rst edge that we drew, for i = 0, oriented according to an external choice ϵ ∈ {-1, +1} and, further, that this operation is invertible. Observe that M has N edges, as many as T, and that the faces of M correspond to the black vertices of T; one can check that the degree of a face is twice that of the corresponding black vertex, we conclude that the above procedure indeed realises a bijection between M ⋆ (n) and {-1, +1} × LT •,• (n). One may be concerned with the fact that the vertices of M di erent from ⋆ are labelled, which seems at rst sight to be an extra information; shift these labels by adding to each the quantity 1min c • ∈•(T) ℓ(c • ) and label 0 the vertex ⋆, then the label of each vertex corresponds to its graph distance in M to the origin ⋆.

. The Janson-Stefánsson bijection

Let T(n) denote the set of one-type trees possessing n i vertices with i children for every i ≥ 0; note that such a tree has N n edges and that p n de ned in Section . is its empirical o spring distribution. Uniform random trees in T(n) have been studied by Addario-Berry [ ] who obtained uniform sub-Gaussian tail bounds for their height and width and Broutin & Marckert [ ] who showed that, properly rescaled, under our assumption (H), they converge in distribution in the sense of Gromov-Hausdor , towards the celebrated Brownian tree, see ( ) below.

Janson & Stefánsson [ ] show that T(n) and T •,• (n) are in bijection, we shall refer to it as the JS bijection. In this bijection, the white vertices of the tree in T •,• (n) are mapped onto the leaves of the tree in T(n) and the black vertices in the former, with degree k ≥ 1, are mapped onto (internal) vertices of the latter with k children. Let us recall the construction of this bijection in the two directions.

Let us start with a two-type tree T; we construct a one-type tree T with the same vertex-set as follows. First, if T = { } is a singleton, then set T = { }; otherwise, for every white vertex u ∈ •(T), do the following:

• if u is a leaf of T, then draw an edge between u and pr (u);

• if u is an internal vertex, with k u ≥ 1 children, then draw edges between any two consecutive black children u1 and u2, u2 and u3, . . . , u(k u -1) and uk u , draw also an edge between u and uk u ;

• if furthermore u , then draw an edge between its rst child u1 and its parent pr (u) in the rst corner at the left of the edge between u and pr (u).

We root the new tree T at the rst child of the root of T. See Conversely, given a one-type tree T , we construct a two-type tree T as follows. Again, set T = { } whenever T = { }; otherwise, for every leaf u of T , denote by u ⋆ its last ancestor whose last child is not an ancestor of u; formally set

u ⋆ = sup {w ∈ , u : wk w , u } .
The set on the right may be empty, in which case u ⋆ = by convention. Then draw an edge between u and every vertex ∈ u ⋆ , u , in the rst corner at the right of the edge between and its only child which belongs to u ⋆ , u . This yields a tree that we root at the last leaf of T . See Figure for an illustration. One can check that the two procedures are the inverse of one another.

Figure :

The Janson-Stefánsson bijection from one-type trees to two-type trees.

Let further LT(n) be the set of labelled one-type trees possessing n i vertices with i children for every i ≥ 0, the JS bijection extends to a bijection between LT(n) and LT •,• (n) if every black vertex of a two-type tree is given the label of its white parent. Let us explain how this bijection translates in terms of the processes encoding the labelled trees (one may look at Figures and for an illustration). Fix (T, ℓ) a two-type labelled tree and denote by C • its white contour process and L • its white label process (in contour order). Fix also (T , l) a one-type labelled tree and denote by H its height process and L its label process (in lexicographical order). Finally, introduce a modi ed version of the height process: let N be the number of edges of T and (u 0 , . . . , u N ) be its vertices listed in lexicographical order; for each integer j ∈ {0, . . . , N }, we let H (j) denote the number of strict ancestors of u j whose last child is not an ancestor of u j , i.e.

H (j) = # w ∈ , u j : wk w , u j .

Lemma . If (T , l) and (T, ℓ) are related by the JS bijection, then

L • = L and C • = H .
Proof. Let us rst prove the equality of the label processes. We use the observation from [ ] that the lexicographical order on the vertices of T corresponds to the contour order on the black corners of T which, by a shift, corresponds to the contour order on the white corners of T. Speci cally, let N be the number of edges of both trees, x j ∈ {0, . . . , N } and consider the j-th white corner of T: it is a sector around a white vertex delimited by two consecutive edges, whose other extremity is therefore black; consider the previous black corner in contour order, in the construction of the JS bijection, an edge of T starts from this corner and we claim that the other extremity of this edge is u j the j-th vertex of T in lexicographical order. We refer to the proof of Proposition . and Figure

in [ ]. It follows that if c • j ∈ •(T)
is the white vertex of T visited at the j-th step in the white contour sequence, then the image of u j by the JS bijection is

• either c • j :
this is the case when c • j is a leaf or when the white corner is the one between the last child of c • j and its parent;

• or a child of c • j : precisely, its rst child if the white corner is the one between the parent of c • j and its rst child, and its k-th child if the corner is the one between the k -1st and k-th children of c • j .

Since a black vertex inherits the label of its white parent, we conclude that in both cases we have

L(j) = l(u j ) = ℓ(c • j ) = L • (j). Next, for every u ∈ T , set H (u) = # {w ∈ , u : wk w , u } ; if H (u) 0, recall the de nition u ⋆ = sup {w ∈ , u : wk w , u } .
Fix ∈ •(T) a white vertex of T and w ∈ •(T) one of its children, if it has any. Denote by JS( ), JS(w) ∈ T their image by the JS bijection, we argue that H (JS( )) and H (JS(w)) are both equal to half the generation of in T. Denote by u = JS( ); from the construction of the JS bijection, if is di erent from the root of T, then its parent in T is mapped onto u ⋆ and its children onto u ⋆ , u , thus

H (JS(w)) = H (JS( )) = H (u) = H (u ⋆ ) + 1 = H (JS(pr ( ))) + 1.
If is the root of T, then u is the right-most leaf of T and and its children are mapped onto the vertices of T for which H = 0. We conclude after an induction on the generation of that indeed, H (JS(w)) and H (JS( )) are equal, and their common value is given by half the generation of in T.

Recall the notation c • j ∈ •(T) for the white vertex of T visited at the j-th step in the white contour sequence and u j for the j-th vertex of T in lexicographical order. Since the image of u j by the JS bijection is either c • j or one of its children (if it has any), we conclude in both cases that

H (u j ) is half the generation of c • j in T, i.e. H (j) = C • (j).
Recall the well-known identity between the height process H and the Łukasiewicz path W of a one-type tree (see e.g. Le Gall & Le Jan[ ]):

H (j) = # i ∈ {0, . . . , j -1} : W (i) ≤ inf [i+1, j] W for each 0 ≤ j ≤ N . ( )
Indeed, for i < j, we have W (i) ≤ inf [i+1, j] W if and only if u i is an ancestor of u j ; moreover, the inequality is an equality if and only if the last child of u i is also an ancestor of u j . A consequence of Lemma is therefore the identity

C • (j) = # i ∈ {0, . . . , i -1} : W (i) < inf [i+1, j] W for each 0 ≤ j ≤ N . ( )
The latter was already observed by Abraham [ , Equation ] without the formalism of the JS bijection, where W (which corresponds to Y -1 there) was de ned directly from the two-type tree.

The Brownian map

. The Brownian snake and the Brownian map

Denote by e = (e t ; t ∈ [0, 1]) the standard Brownian excursion. For every s, t

∈ [0, 1], set m e (s, t) = min r ∈[s∧t,s∨t ]
e r and d e (s, t) = e s + e t -2m e (s, t).

One easily checks that d e is a random pseudo-metric on [0, 1], we then de ne an equivalence relation on [0, 1] by setting s ∼ e t whenever d e (s, t) = 0. Consider the quotient space T e = [0, 1]/∼ e , we let π e be the canonical projection [0, 1] → T e ; d e induces a metric on T e that we still denote by d e . The space (T e , d e ) is a so-called compact real-tree, naturally rooted at π e (0) = π e (1), called the Brownian tree coded by e, introduced by Aldous [ ].

We construct next another process Z = (Z t ; t ∈ [0, 1]) on the same probability space as e which, conditional on e, is a centred Gaussian process satisfying for every s, t ∈ [0, 1],

E |Z s -Z t | 2 e = d e (s, t) or, equivalently, E [Z s Z t | e] = m e (s, t).
It is known (see, e.g. Le Gall [ , Chapter IV. ] on a more general path-valued process called the Brownian snake whose Z is only the "tip") that the pair (e, Z ) admits a continuous version and, without further notice, we shall work throughout this paper with this version. Observe that, almost surely, Z 0 = 0 and Z s = Z t whenever s ∼ e t so Z can be seen as a Brownian motion indexed by T e by setting Z π e (t ) = Z t for every t ∈ [0, 1]. We interpret Z x as the label of an element x ∈ T e ; the pair (T e , (Z x ; x ∈ T e )) is a continuous analog of labelled plane trees and the construction of the Brownian map from this pair, that we next recall, is somewhat an analog of the BDG bijection presented above.

Let us follow Le Gall [ ] to which we refer for details. For every s, t ∈ [0, 1], de ne

Ž (s, t) = min{Z r ; r ∈ [s, t]} if s ≤ t, min{Z r ; r ∈ [s, 1] ∪ [0, t]} otherwise,
and then

D Z (s, t) = Z s + Z t -2 max{ Ž (s, t); Ž (t, s)}.
For every x, ∈ T e , set

D Z (x, ) = inf {D Z (s, t); s, t ∈ [0, 1], x = π e (s) and = π e (t)} ,
and nally

D(x, ) = inf k i=1 D Z (a i-1 , a i ); k ≥ 1, (x = a 0 , a 1 , . . . , a k-1 , a k = ) ∈ T e .
The function D is a pseudo-distance on T e , we de ne an equivalence relation by setting x ≈ whenever D(x, ) = 0 for x, ∈ T e . The Brownian map is the quotient space M = T e /≈ equipped with the metric induced by D, that we still denote by D. Note that D can be seen as a pseudo-distance on [0, 1] by setting D(s, t) = D(π e (s), π e (t)) for every s, t ∈ [0, 1], thus M can be seen as a quotient space of [0, 1].

The following observation shall be used later on. As a function on T 2 e , we clearly have D ≤ D Z and in fact, D is the largest pseudo-distance on T e satisfying this property. Indeed, if D is another such pseudo-distance, then for every x, ∈ T e , for every k ≥ 1 and every a 0 , a 1 , . . . , a k-1 , a k ∈ T e with a 0 = x and a k = , by the triangle inequality D(x,

) ≤ k i=1 D(a i-1 , a i ) ≤ k i=1 D Z (a i-1 , a i
) and so D(x, ) ≤ D(x, ). Furthermore, if we view D as a function on [0, 1] 2 , then for all s, t ∈ [0, 1] such that d e (s, t) = 0 we have π e (s) = π e (t) and so D(π e (s), π e (t)) = 0. We deduce from the previous maximality property that D is the largest pseudo-distance D on [0, 1] satisfying the following two properties:

D ≤ D Z and d e (s, t) = 0 implies D(s, t) = 0.
.

Functional invariance principles

Let T n ∈ T(n) be a one-type tree; it has N n = i ≥1 in i edges, we denote by W n , H n and C n respectively its Łukasiewicz path, its height process and its contour process. The main result of Broutin & Marckert [ ] is the following: under (H), if T n is sampled uniformly at random in T(n) for every n ≥ 1, then the following convergence in distribution holds in C([0, 1], R 3 ):

W n (N n t) N 1/2 n , H n (N n t) N 1/2 n , C n (2N n t) N 1/2 n t ∈[0,1] (d) -→ n→∞ σ p e, 2 σ p e, 2 σ p e t ∈[0,1] . ( )
Denote by L n the label process (in lexicographical order) of a labelled tree (T n , l n ) ∈ LT(n). Consider also a labelled two-type tree (T n , ℓ n ) ∈ LT •,• (n); it has N n edges as well, we denote by C • n its white contour function and by L • n its label function (in contour order).

Theorem . If (T n , l n ) and (T n , ℓ n ) are related by the JS bijection and have the uniform distribution in LT(n) and LT •,• (n) respectively for every n ≥ 1, then, under (H), the following convergences in distribution hold jointly in C([0, 1], R 2 ):

σ 2 p 4 1 N n 1/2 H n (N n t), 9 4σ 2 p 1 N n 1/4 L n (N n t) t ∈[0,1] (d) -→ n→∞ (e t , Z t ) t ∈[0,1] ,
( )

and σ 2 p 4p 2 0 1 N n 1/2 C • n (N n t), 9 4σ 2 p 1 N n 1/4 L • n (N n t) t ∈[0,1] (d) -→ n→∞ (e t , Z t ) t ∈[0,1] . ( )
Remark . Denote by C n the contour function of T n . We have already observed in Section . that

sup t ∈[0,1] |C n (2N n t) -2C • n (N n t)| = 1, so ( ) implies σ 2 p 16p 2 0 1 N n 1/2 C n (2N n t) t ∈[0,1] (d) -→ n→∞ (e t ) t ∈[0,1] .
Consequently, we have the joint convergences in the sense of Gromov-Hausdor :

T n , N -1/2 n d gr (d) -→ n→∞ T e , 4p 0 σ p d e , and
T n , N -1/2 n d gr (d) -→ n→∞ T e , 2 σ p d e .
Remark . By de nition, if (T , l) is a labelled one-type tree and u is a vertex of T with r ≥ 1 children, then the sequence (0, l(u1)l(u), . . . , l(ur )l(u)) belongs to the set of bridges

B + r = (x 0 , . . . , x r ) : x 0 = x r = 0 and x j -x j-1 ∈ {-1, 0, 1, 2, . . . } for 1 ≤ j ≤ r . ( )
Since the cardinal of B + r is 2r -1 r -1 , it follows that a one-type tree T possesses

u ∈T :k u ≥1 2k u -1 k u -1 ( )
possible labellings. Observe that this quantity is constant over T(n) so if we rst sample an unlabelled tree T n uniformly at random in T(n) and if we then add labels uniformly at random, in the sense that the sequences (0, l(u1)l(u), . . . , l(uk u )l(u)) u ∈T n are sampled independently and uniformly at random in B + k u respectively, then the labelled tree has the uniform distribution in LT(n).

Let us comment on the constants in Theorem . The one in front of H n is taken from ( ). Next, the label of a vertex u ∈ T n is the sum of the increments of the labels between consecutive ancestors; there are |u| such terms, which are independent and distributed, when an ancestor has i children and the one on the path to u is the j-th one, as the j-th marginal of a uniform random bridge in B + i , as de ned in ( ); the latter is a centred random variable with variance 2j(ij)/(i + 1). As we will see, there is typically a proportion about p n (i) of such ancestors so L n (u) has variance about

i ≥1 i j=1 |u|p n (i) 2j(i -j) i + 1 = |u| i ≥1 p n (i) i(i -1) 3 ≈ |u| σ 2 p 3 .
If u is the vertex visited at time ⌊N n t⌋ in lexicographical order, then |u| ≈ (4N n /σ 2 p ) 1/2 e t so we expect L n (N n t), once rescaled by N 1/4 n , to be asymptotically Gaussian with variance

4 σ 2 p 1/2 e t σ 2 p 3 = 4σ 2 p 9 1/2 e t .
Regarding the two-type tree, the proof of the convergence of C • n relies on showing that, as n → ∞, it is close to p 0 H n when T n and T n are related by the JS bijection. Finally, according to Lemma , when T n and T n are related by the JS bijection, then the processes L • n and L n are equal. We next explain how Theorem will follow from several results proved in Section .

Proof of Theorem . Recall from Lemma that the processes L n and L • n are equal. Appealing to this lemma, we shall also obtain in Proposition below the joint convergence

σ 2 p 4 1 N n 1/2 H n (N n t), σ 2 p 4p 2 0 N n 1/2 C • n (N n t) t ∈[0,1] (d) -→ n→∞ (e t , e t ) t ∈[0,1] .
In Proposition , we shall prove that, jointly with this convergence, for every k ≥ 1, if (U 1 , . . . , U k ) are i.i.d. uniform random variables in [0, 1] independent of the trees, then the convergence

9 4σ 2 p 1 N n 1/4 (L n (N n U 1 ), . . . , L n (N n U k )) (d) -→ n→∞ Z U 1 , . . . , Z U k ( )
holds in R k , where the process Z is independent of (U 1 , . . . , U k ). Finally, in Proposition , we shall prove that the sequence

N -1/4 n L n (N n t); t ∈ [0, 1] n ≥1 is tight in C([0, 1], R).
This ensures that the sequences on the left-hand side of ( ) and ( ) are tight in C([0, 1], R 2 ). Using the equicontinuity given by this tightness, as well as the uniform continuity of the pair (e, Z ), one may transpose ( ) to a convergence for deterministic times, by approximating them by i.i.d. uniform random times, see e.g. Addario-Berry & Albenque [ , proof of Proposition . ] for a detailed argument; this characterises the sub-sequential limits of ( ) and ( ) in C([0, 1], R 2 ) as (e, Z ).

The proofs of the above intermediate results are deferred to Section , they rely on a precise description of the branches from the root of T n to i.i.d. vertices which is the content of the next section.

Spinal decompositions

In this section, we describe the branches from the root to i.i.d. vertices in a tree T n sampled uniformly at random in T(n), extending results due to Broutin & Marckert [ ]. We only state the results, the proofs are technical and are deferred to Appendix A for the sake of clarity.

. A one-point decomposition

For a given vertex u in a plane tree T , we denote by A i (u) its number of strict ancestors with i children:

A i (u) = # { ∈ , u : k = i} . We write A(u) = (A i (u); i ≥ 1); note that |u| = |A(u)| = i ≥1 A i (u). The quantity A(u) is crucial in order to control the label l n (u) of the vertex u ∈ T n when (T n , l n ) is chosen uniformly at random in LT(n). Indeed, one can write l n (u) = ∈ ,u l n ( ) -l n (pr ( )),
and, conditional on T n , the random variables l n ( )l n (pr ( )) are independent and their law depends on the number of children of pr ( ). If m = (m i ; i ≥ 1) is a sequence of non-negative integers, then we set

LR(m) = 1 + i ≥1 (i -1)m i .
The notation comes from the fact that removal of the path , u produces a forest of LR(A(u)) trees, so, in other words, LR(A(u)) is the number of vertices lying directly on the left or on the right of this path (and the component "above"). For every x > 0 de ne the following set of "good" sequences:

Good(n, x) = m ∈ Z N + : LR(m) ≤ xN 1/2 n and |m| ≤ xN 1/2 n .
Consider also the more restrictive set

Good + (n, x) = m ∈ Z N + : LR(m) ≤ xN 1/2 n and x -1 N 1/2 n ≤ |m| ≤ xN 1/2 n .
The following result has been obtained by Broutin & Marckert [ ]; it is not written explicitly there but the arguments that we recall in Appendix A can be found in Sections and . there.

Lemma . For every n ≥ 1, sample T n uniformly at random in T(n) and then sample a vertex u n uniformly at random in T n . For every ε > 0, there exists x > 0 such that, under (H),

lim inf n ≥1 P (A(u) ∈ Good(n, x) for all u ∈ T n ) ≥ 1 -ε, and lim inf n ≥1 P A(u n ) ∈ Good + (n, x) ≥ 1 -ε.
Furthermore, there exists a constant C > 0 (which depends on x) such that for every sequence m ∈ Good(n, x), setting h = |m|, we have

P (A(u n ) = m) ≤ C • N -1/2 n • P Ξ (h) n = m ,
where Ξ (h) n = (Ξ (h) n,i ; i ≥ 1) has the multinomial distribution with parameters h and (in i /N n ; i ≥ 1). Observe that replacing A(u n ) by such a multinomial sequence means that the random variables (k pr ( ) ; ∈ , u n ) are independent and distributed according to the size-biased law (in i /N n ; i ≥ 1). Also, clearly, conditional on (k pr ( ) ; ∈ , u n ), the random variables (χ ; ∈ , u n ) are independent and each one has the uniform distribution in {1, . . . , k pr ( ) } respectively.

The following corollary, which shall be used in Section . , sheds some light on Lemma . The argument used in the proof shall be used at several other occasions.

Corollary . Recall the notation χ w ∈ {1, . . . , k pr (w ) } for the relative position of a vertex w ∈ T n among its siblings. Let c = 1 -p 0 2 and h n = 16 p 2 0 ln N n and consider the event

E n = #{w ∈ u, : χ w = 1} # u, ≤ c for every u, ∈ T n such that u ∈ , and # u, > h n .
If T n is sampled uniformly at random in T(n), then under (H), we have

P(E n ) → 1 as n → ∞.
In words, this means that in T n , there is no branch longer than some constant times ln n along which the proportion of individuals which are the left-most child of their parent is too large.

Proof. For every ∈ T n , for every 1 ≤ j ≤ | |, let us denote by a j ( ) the unique element of , such that # a j ( ), = j, then set X j ( ) = 1 if χ a j ( ) = 1 and X j ( ) = 0 otherwise so

E n = ∈T n h n ≤j ≤ | | #{1 ≤ i ≤ j : X i ( ) = 1} ≤ c • j = ∈T n h n ≤j ≤ | | j i=1 X i ( ) ≤ c • j .
Let u 0 , . . . , u N n be the vertices of T n listed in lexicographical order. Sample q n uniformly at random in {1, . . . , N n } and independently of T n , let n = u q n and let Ξ (h) n denote a random sequence with the multinomial distribution with parameters h and (in i /N n ; i ≥ 1). Fix ε > 0, and let x > 0 and C > 0 as in Lemma . Then for n large enough,

P E c n ≤ ε + 1≤q ≤N n h n ≤j ≤x N 1/2 n j ≤h ≤x N 1/2 n m∈Good(n,x ) |m |=h P j i=1 X i (u q ) > c • j and A(u q ) = m ≤ ε + Cx 2 N 3/2 n sup j ≥h n sup h ≥j m∈Good(n,x ) |m |=h P j i=1 X i ( n ) > c • j A( n ) = m P Ξ (h) n = m .
Observe that conditional on the o springs k a i ( n )'s of the ancestors a i ( n )'s, the X i ( n )'s are independent and have the Bernoulli distribution with parameter 1/k a i ( n ) respectively. We thus have

m∈Good(n,x ) |m |=h P j i=1 X i ( n ) > c • j A( n ) = m P Ξ (h) n = m = P j i=1 Y n,i > c • j ,
where the Y n,i 's are independent and have the Bernoulli distribution with parameter

r ≥1 1 r • rn r N n = 1 - n 0 -1 N n .
Recall that c = 1 -p 0 2 ; x n large enough so that, according to (H), n 0 -1

N n > 3p 0 4 and so c -(1 -n 0 -1 N n ) = n 0 -1 N n - p 0 2 > p 0
4 . The Cherno bound then reads

P j i=1 Y n,i > c • j ≤ P j i=1 (Y n,i -E Y n,i ) > p 0 4 • j ≤ exp - p 2 0 8
• j , so nally, for n large enough,

P E c n ≤ ε + Cx 2 N 3/2 n exp - p 2 0 8 • h n ,
which converges to ε as n → ∞ from our choice of h n .

.

A multi-point decomposition

We next extend the previous decomposition according to several i.i.d. uniform random vertices. Let us rst introduce some notation. Fix a plane tree T and k distinct vertices u 1 , . . . , u k of T and denote by T (u 1 , . . . , u k ) the tree T reduced to its root and these vertices:

T (u 1 , . . . , u k ) = 1≤j ≤k , u j ,
which naturally inherits a plane tree structure from T . Denote by k ′ ≤ k -1 the number of branchpoints of T (u 1 , . . . , u k ) and by 1 , . . . , k ′ these branch-points. Let F (u 1 , . . . , u k ) be the forest obtained from T (u 1 , . . . , u k ) by removing the edges linking these branch-points to their children; note that F (u 1 , . . . , u k ) contains k + k ′ connected components which are only single paths, i.e. each one contains one root and only one leaf and the latter is either one of the u i 's or one of the i 's. Let us rank these connected components in increasing lexicographical order of their root and denote by j and λ j respectively the root and the leaf of the j-th one. For every 1 ≤ j ≤ k + k ′ and every i ≥ 1, we set

A (j) i (u 1 , . . . , u k ) = # z ∈ j , λ j : k z = i ,
where k z must be understood as the number of children in the original tree T of the vertex z. We set

A(u 1 , . . . , u k ) = A (1) (u 1 , . . . , u k ), . . . , A (k+k ′ ) (u 1 , . . . , u k ) .
Fix n, k ≥ 1, sample T n uniformly at random in T(n) and then sample i.i.d. uniform random vertices u n,1 , . . . , u n,k inT n ; denote by Bin k the following event: the reduced treeT n (u n,1 , . . . , u n,k ) is binary, has k leaves and its root has only one child. Note that on this event, the u n,i 's are distinct and the number of branch-points of the reduced tree is k ′ = k-1. Let us also denote by

Bin + k = {max a ∈T n |a| ≤ N 3/4 n }∩Bin k . The next result is proved in Appendix A.
Lemma . For every n ≥ 1, sample T n uniformly at random in T(n) and then sample i.i.d. uniform random vertices u n,1 , . . . , u n,k in T n . For every ε > 0, there exists x > 0 such that, under (H),

lim inf n ≥1 P Bin + k ∩ 2k-1 i=1 A (i) (u n,1 , . . . , u n,k ) ∈ Good + (n, x) ≥ 1 -ε.
Furthermore, there exists C > 0 (which depends on x) such that for every sequences m (1) , . . . , m (2k-1) ∈ Good(n, x), setting |m (j) | = h j for each 1 ≤ j ≤ 2k -1, we have

P A(u n,1 , . . . , u n,k ) = (m (1) , . . . , m (2k-1) ) Bin + k ≤ C • N -(2k-1)/2 n • 2k-1 j=1 P Ξ (h j ) n = m , where Ξ (h j ) n = (Ξ (h j )
n,i ; i ≥ 1) has the multinomial distribution with parameters h j and (in i /N n ; i ≥ 1).

Functional invariance principles

We state and prove in this section the intermediate results used in the proof of Theorem . Let (T n , l n ) be a uniform random labelled tree in LT(n) and let H n and L n denote its height and label processes. Let also T n be its associated two-type tree, which has the uniform distribution in T •,• (n), with white contour process C • n . Our aim is to show that, under (H), the three convergences

σ 2 p 4p 2 0 N n 1/2 C • n (N n t); t ∈ [0, 1] (d) -→ n→∞ (e t ; t ∈ [0, 1]) ( )
as well as

σ 2 p 4 1 N n 1/2 H n (N n t); t ∈ [0, 1] (d) -→ n→∞ (e t ; t ∈ [0, 1]) ( ) and 9 4σ 2 p 1 N n 1/4 L n (N n t); t ∈ [0, 1] (d) -→ n→∞ (Z t ; t ∈ [0, 1]), ( ) hold jointly in C([0, 1], R).
The second one is the main result of [ ] recalled in ( ). We prove ( ) in the next subsection. Then we prove the convergence of random nite-dimensional marginals of (N -1/4 n L n (N n •)) n ≥1 in Section . and the tightness of this sequence in Section . .

. Convergence of the contour

Let T n have the uniform distribution in T(n) and let T n be its associated two-type tree, which has the uniform distribution in T •,• (n).

Proposition . Under (H), we have the convergence in distribution in C([0, 1], R 2 )

σ 2 p 4 1 N n 1/2 H n (N n t), σ 2 p 4p 2 0 N n 1/2 C • n (N n t) t ∈[0,1] (d) -→ n→∞ (e t , e t ) t ∈[0,1] .
The key observation is the identity from Lemma :

C • n = H n ,
where H n (j) is the number of strict ancestors of the j-th vertex of T n whose last child is not one of its ancestors. We have seen in the previous section that for a "typical" vertex u of T n , at generation |u|, the number of ancestors having i children for i ≥ 1 forms approximately a multinomial sequence with parameters |u| and (in i /N n ; i ≥ 1); further, for each such ancestor, there is a probability 1 -1/i that its last child is not an ancestor of u and therefore contributes to

C • n . Since i ≥1 (1 -1/i)(in i /N n ) → 1 -(1 -p 0 ) = p 0 , we conclude that, at a "typical" time, C • n ≈ p 0 H n .
Proof. The convergence of the rst marginal comes from ( ); since, under (H), we have p 0 = lim n→∞ (n 0 -1)/N n it su ces then to prove that

N -1/2 n sup 0≤t ≤1 H n (N n t) - n 0 -1 N n H n (N n t) P -→ n→∞ 0.
Note that we may restrict ourselves to times t of the form i/N n with i ∈ {1, . . . , N n }. We proceed as in the proof of Corollary . Let i n be a uniform random integer in {1, . . . , N n } and u n the i n -th vertex of T n in lexicographical order. Fix δ, ε > 0 and choose x > 0 and C > 0 as in Lemma . Then for n large enough,

P sup 1≤i ≤N n H n (i) - n 0 -1 N n H n (i) > δ N 1/2 n ≤ ε + xN 3/2 n sup 1≤h ≤x N 1/2 n m∈Good(n,x ) |m |=h P (A(u n ) = m) P H n (i n ) - n 0 -1 N n h > δ N 1/2 n A(u n ) = m . ≤ ε + CxN n sup 1≤h ≤x N 1/2 n m∈Good(n,x ) |m |=h P Ξ (h) n = m P H n (i n ) - n 0 -1 N n h > δ N 1/2 n A(u n ) = m .
Observe that conditional on the vector (k ; ∈ , u n ), the random variable H n (i n ) is a sum of independent Bernoulli random variables, with respective parameter

(1 -k -1 ; ∈ , u n ). Note that i ≥1 1 - 1 i • in i N n = n 0 -1 N n ,
we let (Y n,i ; 1 ≤ i ≤ h) be independent Bernoulli random variables with parameter (n 0 -1)/N n . We then conclude, applying the Cherno bound for the second inequality, that for every n large enough,

P sup 1≤i ≤N n H n (i) - n 0 -1 N n H n (i) > δ N 1/2 n ≤ ε + CxN n sup 1≤h ≤x N 1/2 n P h i=1 Y n,i - n 0 -1 N n h > δ N 1/2 n ≤ ε + CxN n sup 1≤h ≤x N 1/2 n 2e -2δ 2 N n /h , which converges to ε as n → ∞.
.

Maximal displacement at a branch-point

Recall that for every vertex u, we denote by k u its number of children and these children by u1, . . . , uk u .

Proposition . For every n ≥ 1, sample (T n , l n ) uniformly at random in LT(n). Under (H), we have the convergence in probability

N -1/4 n max u ∈T n max 1≤j ≤k u l n (uj) -min 1≤j ≤k u l n (uj) P -→ n→∞ 0.
To prove this result, we shall need the following sub-Gaussian tail bound for the maximal gap in a random walk bridge. The proof is easy, we refer to Appendix B.

Lemma . Let (S k ; k ≥ 0) be a random walk such that S 0 = 0 and (S k+1 -S k ; k ≥ 0) are i.i.d. random variables, taking values in Z ∩ [-b, ∞) for some b ≥ 0, centred and with variance σ 2 ∈ (0, ∞). There exists two constants c, C > 0 which only depend on b and σ such that for every r ≥ 1 and x ≥ 0, we have

P max 0≤k ≤r S k -min 0≤k ≤r S k ≥ x S r = 0 ≤ Ce -cx 2 /r .
Proof of Proposition . Recall that conditional onT n , the sequences (0, l n (u1)-l n (u), . . . , l n (uk u )-l n (u)) u ∈T n are independent and distributed respectively uniformly at random in B + r de ned in ( ), with r = k u , and that there are n r such vertices in T n . Consider the random walk (S i ; i ≥ 0) such that S 0 = 0 and (S i+1 -S i ; i ≥ 0) are i.i.d. random variables, distributed as a shifted geometric law:

P (S 1 = k) = 2 -(k+2)
for every k ≥ -1. Then it is easy to check that for every r ≥ 1, on the event {S r = 0}, the path (S 0 , . . . , S r ) has the uniform distribution in B + r . Therefore, according to Lemma , there exists two universal constants c, C > 0 such that for every ε > 0, for every n large enough,

P max u ∈T n max 1≤i ≤k u l n (ui) -min 1≤i ≤k u l n (ui) ≤ εN 1/4 n = ∆ n r =1 P max 0≤k ≤r S k -min 0≤k ≤r S k ≤ εN 1/4 n S r = 0 n r ≥ ∆ n r =1 1 -C exp -cε 2 N 1/2 n /r n r ≥ exp - ∆ n r =1 n r C exp -cε 2 N 1/2 n /r 1 -C exp -cε 2 N 1/2 n /r ≥ exp -C ∆ n r =1 n r exp -cε 2 N 1/2 n /r (1 + o(1)) ,
where we have used the bound ln(1x) ≥ -x 1-x for x < 1, jointly with the fact that, under (H), we have sup 1≤r

≤∆ n exp(-cε 2 N 1/2 n /r ) → 0 since ∆ n = o(N 1/2 n ).
Recall furthermore that under (H), we have

∆ n r =1 r 2 n r /N n → σ 2 p + 1 < ∞, we conclude that for every n large enough, since x → x 2 e -x is decreasing on [2, ∞), ∆ n r =1 n r exp -cε 2 N 1/2 n r ≤ ∆ n r =1 r 2 n r N n × N n ∆ 2 n exp -cε 2 N 1/2 n ∆ n -→ n→∞ 0,
and the claim follows.

.

Random nite-dimensional convergence

As in Section , in order to make the notation easier to follow, we rst treat the one-dimensional case.

Proposition . For every n ≥ 1, sample independently (T n , l n ) uniformly at random in LT(n) and U uniformly at random in [0, 1]. Under (H), the convergence in distribution

9 4σ 2 p 1 N n 1/4 L n (N n U ) (d) -→ n→∞ Z U
holds jointly with ( ), where the process Z is independent of U .

Proof. The approach of the proof was described in Section . when explaining the constant (9/(4σ 2 p )) 1/4 . Note that the vertex u n visited at the time ⌈N n U ⌉ in lexicographical order has the uniform distribution in T n ; denote by l n (u n ) = L n (⌈N n U ⌉) its label and by |u n | = H n (⌈N n U ⌉) its height and observe that

9 4σ 2 p 1 N n 1/4 l n (u n ) = σ 2 p 4 1 N n |u n | • 3 σ 2 p 1 |u n | l n (u n ).
Since, according to ( ), the rst term on the right converges in distribution towards e U , it is equivalent to show that, jointly with ( ), we have

1 |u n | l n (u n ) =⇒ n→∞ N 0, σ 2 p 3 , ( )
where N(0, σ 2 p /3) denotes the centred Gaussian distribution with variance σ 2 p /3 and "⇒" is a slight abuse of notation to refer to the weak convergence of the law of the random variable.

Precisely u n has the uniform distribution in T n \ { }, but we omit this detail for the sake of clarity.

Recall that we denote by A i (u n ) the number of strict ancestors of u n with i children:

A i (u n ) = # { ∈ , u n : k = i} ;
denote further by A i, j (u n ) the number of strict ancestors of u n with i children, among which the j-th one is again an ancestor of u n :

A i, j (u n ) = # { ∈ , u n : k = i and j ∈ , u n } .
We have seen in Section that when T n is uniformly distributed in T(n) and u n is uniformly distributed in T n , then A(u n ) = (A i (u n ); i ≥ 1) can be compared to a multinomial sequence with parameters |u n | and (in i /N n ; i ≥ 1). Observe further that given the sequence A(u n ), the vectors (A i, j (u n ); 1 ≤ j ≤ i) i ≥1 are independent and distributed respectively according to the multinomial distribution with parameters

A i (u n ) and ( 1 i , . . . , 1 i ). Let (X i, j,k ; 1 ≤ j ≤ i ≤ ∆ n , k ≥ 1
) be a collection of independent random variables which is also independent of A(u n ), and such that X i, j,k has the law of the j-th marginal of a uniform random bridge in B + i ; note that the latter is centred and has variance, say, σ 2 i, j . Then let us write

l n (u n ) = ∆ n i=1 i j=1 A i, j (u n ) k=1 X i, j,k , and l K n (u n ) = K i=1 i j=1 A i, j (u n ) k=1 X i, j,k , for K ≥ 1.
The proof of ( ) is divided into two steps: we rst show that for every K ≥ 1, l K n (u n )/ |u n | converges towards a limit which depends on K and which in turn converges towards N(0, σ 2 p /3) as K → ∞, and then we show that |l n (u n )l K n (u n )|/ |u n | can be made arbitrarily small uniformly for n large enough by choosing K large enough.

Let us rst prove the convergence of

l K n (u n ) as n → ∞. For every h ≥ 1, let Ξ (h) n = (Ξ (h)
n,i ; i ≥ 1) denote a random sequence with the multinomial distribution with parameters h and (in i /N n ; i ≥ 1) and

x ε > 0, and let x > 0 and C > 0 as in Lemma .

Fix i ≥ 1 such that p(i) 0. Since Ξ (h) n,i has the binomial distribution with parameters h and in i /N n , Lemma and Markov inequality yield for every δ > 0 and every n large enough,

P N n |u n |in i A i (u n ) -1 > δ ≤ ε + Cx sup x -1 N 1/2 n ≤h ≤x N 1/2 n P N n hin i Ξ (h) n,i -1 > δ ≤ ε + Cx sup x -1 N 1/2 n ≤h ≤x N 1/2 n h -1 δ -2 N n in i -1 , which converges to ε as n → ∞ since in i /N n → ip(i) ∈ (0, 1). Given A i (u n ), the vector (A i, j (u n ); 1 ≤ j ≤ i) has the multinomial distribution with parameters A i (u n ) and ( 1 i , . . . , 1 i ) so for every 1 ≤ j ≤ i, we further have N n |u n |n i A i, j (u n ) P -→ n→∞ 1.
Since the random variables X i, j,k are independent, centred and have variance σ 2 i, j , the central limit theorem then reads, when p(i) 0, 1

|u n | A i, j (u n ) k=1 X i, j,k =⇒ n→∞ N 0, p(i)σ 2 i, j . ( )
In the case p(i) = 0, we claim that

1 |u n | i j=1 A i, j (u n ) k=1 X i, j,k P -→ n→∞ 0. ( )
Indeed, with the same argument as above, it su ces to show that for every δ > 0, we have

lim n→∞ sup x -1 N 1/2 n ≤h ≤x N 1/2 n |m |=h P Ξ (h) n = m P i j=1 M i, j k=1 X i, j,k ≥ δ √ h = 0,
where the vector (M i, j ; 1 ≤ j ≤ i) has the multinomial distribution with parameters m i and ( 1 i , . . . , 1 i ) and is independent of the X i, j,k 's. For every sequence m, we have

P i j=1 M i, j k=1 X i, j,k ≥ δ √ h ≤ 1 δ 2 h i j=1 E M i, j σ 2 i, j = 1 δ 2 h m i i i j=1 σ 2 i, j , whence |m |=h P Ξ (h) n = m P i j=1 M i, j k=1 X i, j,k ≥ δ √ h ≤ |m |=h P Ξ (h) n = m 1 δ 2 h m i i i j=1 σ 2 i, j ≤ E Ξ (h) n,i 1 δ 2 h 1 i i j=1 σ 2 i, j ≤ n i N n 1 δ 2 i j=1 σ 2 i, j .
Under (H), we have n i /N n → p(i) = 0 as n → ∞ and ( ) follows.

We conclude using ( ), ( ) and the independence of the X i, j,k 's as i and j vary that for every K ≥ 1, the convergence 1

|u n | l K n (u n ) =⇒ n→∞ N 0, K i=1 p(i) i j=1 σ 2 i, j holds. Marckert & Miermont [ , page
] have calculated the variance of the random variables X i, j,k :

σ 2 i, j = 2j(i -j) i + 1 so i j=1 σ 2 i, j = i(i -1) 3 . Consequently, K i=1 p(i) i j=1 σ 2 i, j -→ K →∞ ∞ i=1 p(i) i(i -1) 3 = σ 2 p 3 , which implies N 0, K i=1 p(i) i j=1 σ 2 i, j =⇒ K →∞ N 0, σ 2 p 3 .
It only remains to show that for every δ > 0, we have

lim K →∞ lim sup n→∞ P l n (u n ) -l K n (u n ) ≥ δ |u n | = 0. ( )
Again, with the same notation as above, it is enough to show that for every x > 0 and every δ > 0, we have

lim K →∞ lim sup n→∞ sup x -1 N 1/2 n ≤h ≤x N 1/2 n |m |=h P Ξ (h) n = m P ∆ n i=K i j=1 M i, j k=1 X i, j,k ≥ δ √ h = 0.
Note that they consider uniform random bridges in

B + i +1 !
By the same calculation as above,

|m |=h P Ξ (h) n = m P ∆ n i=K i j=1 M i, j k=1 X i, j,k ≥ δ √ h ≤ |m |=h P Ξ (h) n = m 1 δ 2 h ∆ n i=K m i i i j=1 σ 2 i, j = 1 δ 2 h ∆ n i=K 1 i E Ξ (h) n,i i j=1 σ 2 i, j = 1 δ 2 ∆ n i=K n i N n i(i -1) 3 ,
Under (H), we have

∆ n i=K n i N n i(i -1) -→ n→∞ i ≥K p(i)i(i -1) -→ K →∞ 0.
This concludes the proof of ( ).

We next give a multi-dimensional extension of Proposition . The proof of the latter relied on Lemma , the proof of its extension appeals to Lemma .

Proposition . For every n ≥ 1, sample independently (T n , l n ) uniformly at random in LT(n) and U 1 , . . . , U k uniformly at random in [0, 1]. Under (H), the convergence in distribution

9 4σ 2 p 1 N n 1/4 (L n (N n U 1 ), . . . , L n (N n U k )) (d) -→ n→∞ Z U 1 , . . . , Z U k
holds jointly with ( ), where the process Z is independent of (U 1 , . . . , U k ).

Proof. As for Lemma , we focus on the case k = 2 and comment on the general case at the end. Let u n and n be independent uniform random vertices of T n and w n be their most recent common ancestor, let further ûn and ˆ n be the children of w n which are respectively an ancestor of u n and n . We write:

l n (u n ) = l n (w n ) + (l n ( ûn ) -l n (w n )) + (l n (u n ) -l n ( ûn )),
and we have a similar decomposition for n . The point is that, conditional on T n , u n and n , the random variables l n (w n ), l n (u n )-l n ( ûn ) and l n ( n )-l n ( ˆ n ) are independent. Moreover, according to Proposition , with high probability, l n ( ûn )l n (w n ) and l n ( ˆ n )l n (w n ) are both small compared to N 1/4 n . According to ( ), we have

σ 2 p 4 1 N n 1/2 (|w n |, |u n | -| ûn |, | n | -| ˆ n |) (d) -→ n→∞ (m e (U , V ), e U -m e (U , V ), e V -m e (U , V )) ,
where U and V are i.i.d uniform random variables on [0, 1] independent of e. We shall prove that, jointly with ( ),

3 σ 2 p l n (w n ) |w n | , l n (u n ) -l n ( ûn ) |u n | -| ûn | , l n ( n ) -l n ( ˆ n ) | n | -| ˆ n | (d) -→ n→∞ (G 1 , G 2 , G 3 ) , ( )
where G 1 , G 2 , G 3 are i.i.d. standard Gaussian random variables. Proposition and ( ) then imply that, jointly with ( ), the pair

9 4σ 2 p 1 N n 1/4 (l n (u n ), l n ( n )) n ≥1 converges in distribution towards m e (U , V )G 1 + e U -m e (U , V )G 2 , m e (U , V )G 1 + e V -m e (U , V )G 3 = (Z U 1 , Z U 2 ).
The proof of ( ) is mutatis mutandis the same as that of Proposition : consider the three branches , w n , ûn , u n and ˆ n , n , we use Lemma to compare the number of elements in each branch which have i children and among which the j-th one belongs to the branch to independent multinomial distributions; then we may use the arguments of the proof of Proposition to each branch independently which yields ( ).

The general case k ≥ 2 hides no di culty. Sample i.i.d. uniform random vertices u n,1 , . . . , u n,k of T n ; appealing to Proposition , we neglect the contribution of the branch-points of the reduced tree T n (u n,1 , . . . , u n,k ) and we decompose the labels of each vertex u n,i as the sum of the increments over all the branches of the forest F n (u n,1 , . . . , u n,k ); Lemma then yields the generalisation of ( ).

.

Concentration results for discrete excursions

In this subsection, we shall prove two concentration inequalities for the Łukasiewicz path of T n . The rst one shall be used to derive the tightness of the label process in the next subsection, and the second one in Section in the proof of Theorem .

Proposition . Assume that (H) holds and let W n be the Łukasiewicz path of a tree sampled uniformly at random in T(n). There exists a constant C > 0 such that, uniformly for t ≥ 0, n ∈ N and 0

≤ j < k ≤ N n +1 with k -j ≤ N n /2, P W n (j) -min j ≤i ≤k W n (i) > t ≤ exp - t 2 C • (k -j)
.

Consequently, for every r > 0, if C(r

) = Γ(1 + r 2 ) • C r /2 , then the bound E W n (j) -min j ≤i ≤k W n (i) r ≤ C(r ) • (k -j) r /2 , holds uniformly for n ∈ N and 0 ≤ j < k ≤ N n + 1 such that k -j ≤ N n /2.
This result follows from Section of Addario-Berry [ ]. Fix m = (m 0 , m 1 , m 2 , . . . ) a sequence of non-negative integers with nite sum satisfying

M = i ≥0 m i , i ≥0 (i -1)m i = -1 and ς 2 = i ≥0 (i -1) 2 m i ,
and de ne

B(m) = x = (x 1 , . . . , x M ) : #{j : x j = i -1} = m i for every i ≥ 0 .
Given x ∈ B(m), we consider the walk S x de ned by S x (0) = 0 and S

x (k) = x 1 + • • • + x k for 1 ≤ k ≤ M.
A careful reading of [ , Section ] which focuses on the case k = ⌊M/2⌋, and which relies on a concentration inequality similar to Lemma applied to the martingale (S x (k) + 1)/(Mk), yields the following result.

Lemma (Addario-Berry [ ]). If x is sampled uniformly at random in B(m), then

P -min 0≤i ≤k S x (i) ≥ t ≤ exp - t 2
(16

ς 2 M + 8 3 (1 -1 M ))k
for every 1 ≤ k ≤ ⌊M/2⌋ and every t ≥ 0.

Observe that S x (M) = -1 for every x ∈ B(m); we de ne further

E(m) = {x ∈ B(m) : S x (k) ≥ 0 for every 1 ≤ k ≤ M -1} .
The sets E(m) and T(m) are in one-to-one correspondence: each path S x with x in E(m) is the Łukasiewicz path of a tree in T(m). For x ∈ B(m) and j ∈ {1, . . . , M}, denote by x (j) ∈ B(m) the j-th cyclic shift of x de ned by

x (j) k = x k+j mod M , 1 ≤ k ≤ M.
It is well-known that, given x ∈ B(m), we have x (j) ∈ E(m) if and only if j is the least time at which the walk S x achieves its minimum overall value:

j = inf 1 ≤ k ≤ M : S x (k) = inf 1≤i ≤M S x (i) . ( )
Given x ∈ B(m), we let x * be the unique cyclic shift of x in E(m). It is a standard fact that if x has the uniform distribution in B(m), then the time j satisfying ( ) has the uniform distribution on {1, . . . , M} and furthermore x * = x (j) is uniformly distributed in E(m) and is independent of j.

Proof of Proposition . According to the previous remark, we know that W n is distributed as S x * where x has the uniform distribution in B(n). With the previous notation, M = N n + 1 and

ς 2 = (N n + 1)σ 2 n + N 2 n N n + 1 -N n + 1 = (N n + 1)σ 2 n + 1 N n + 1 .
We then apply Lemma to S x * : for every t ≥ 1, for every

1 ≤ k -j ≤ ⌊N n /2⌋, P S x * (j) -min j ≤i ≤k S x * (i) ≥ t = P -min 0≤i ≤k-j S x (i) ≥ t ≤ exp - t 2 (16(σ 2 n + 1 N n +1 ) + 8 3 (1 -1 N n +1 )(k -j)
, which corresponds to the rst claim, with

C = sup n ≥1 {16(σ 2 n + 1 N n +1 ) + 8 3 (1 -1 N n +1
)} < ∞; the second claim follows by integrating this tail bound applied to t 1/r . We next show that the vertices of T n with a given o spring are in some sense uniformly distributed for large n. If T ∈ T is a tree and u 0 , . . . , u N are its vertices listed in lexicographical order, then for every set A ⊂ Z + and every integer 1

≤ i ≤ N + 1, we let Λ T,i (A) = # 0 ≤ j ≤ i -1 : k u j ∈ A
be the number of vertices of T amongst the rst i which have a number of children in A. The next result shows that this quantity grows roughly linearly with i.

Proposition . Assume that (H) holds and sample T n uniformly at random in T(n) for every n ≥ 1. Then for every A ⊂ Z + ,

P max 1≤i ≤N n +1 Λ T n ,i (A) -p n (A)i > N 3/4 n -→ n→∞ 0. Proof. For every ∈ B(n), every A ⊂ Z + and every 1 ≤ i ≤ N n + 1, set λ ,i (A) = #{1 ≤ k ≤ i : k + 1 ∈ A}.
Note that λ , N n +1 (A) = (N n + 1)p n (A). As previously discussed, the Łukasiewicz path of T n has the law of S x where x is uniformly distributed in E(n), so

P max 1≤i ≤N n +1 Λ T n ,i (A) -p n (A)i > N 3/4 n = P max 1≤i ≤N n λ x,i (A) -p n (A)i > N 3/4 n . Let us rst consider uniformly distributed in B(n). For each 1 ≤ i ≤ N n + 1 xed, λ ,i (A) = i k=1 1 { k +1∈A }
is the sum of i dependent Bernoulli random variables, which arise from a sampling without replacement in an urn with initial con guration of i ∈A n i "good" balls and N n + 1i ∈A n i "bad" balls. It is well-known that the expected value of any continuous convex function of λ ,i (A) is bounded above by the corresponding quantity for the sum of i i.i.d. Bernoulli random variables with parameter p n (A), which arise from sampling with replacement, see e.g. Hoe ding's seminal paper [ , Theorem ]. In particular, the Cherno bound for binomial random variables still holds and yields

P max 1≤i ≤N n λ ,i (A) -p n (A)i > N 3/4 n ≤ N n max 1≤i ≤N n P λ ,i (A) -p n (A)i > N 3/4 n ≤ 2N n max 1≤i ≤N n exp -2N 3/2 n /i = o(N -1 n ).
Next, let j be as in ( ) and recall that j is uniformly distributed in {1, . . . , N n + 1} and that x = * = (j) is uniformly distributed in E(n) and independent of j. If j = N n + 1, then x = and our claim follows from the above bound. We then implicitly condition j to be less than N n + 1, in which case it has the uniform distribution in {1, . . . , N n } and it is independent of x. Observe that N n + 1j also has the uniform distribution in {1, . . . , N n } and is independent of x, so

P max 1≤i ≤N n λ x,i (A) -p n (A)i > N 3/4 n ≤ N n P λ x, N n +1-j (A) -p n (A)(N n + 1 -j) > N 3/4 n . Furthermore, in our coupling, λ x, N n +1-j (A) = #{1 ≤ k ≤ N n + 1 -j : x k + 1 ∈ A} is also equal to #{1 ≤ k ≤ N n + 1 -j : N n +2-k + 1 ∈ A}.
By time-reversal, we have the identity

( N n +2-k ; 1 ≤ k ≤ N n + 1); N n + 1 -j (d) = (( k ; 1 ≤ k ≤ N n + 1); j ′ ) , where j ′ = sup{0 ≤ k ≤ N n : S (k) = max 1≤l ≤N n +1 S x (l)}. We conclude that P max 1≤i ≤N n +1 Λ T n ,i (A) -p n (A)i > N 3/4 n ≤ N n P λ , j ′ (A) -p n (A)j ′ > N 3/4 n + P (j = N n + 1) ,
which converges to 0 as n → ∞.

. Tightness of the label process

Let us prove the tightness of the label process; jointly with Proposition , this will end the proof of Theorem .

Proposition . For every n ≥ 1, sample (T n , l n ) uniformly at random in LT(n). Under (H), the sequence

N -1/4 n L n (N n t); t ∈ [0, 1] n ≥1 is tight in C([0, 1], R).
In the remainder of this section, we shall use the notationC(q) for a positive constant which depends only on a real number q and, implicitly, on the sequences n, and which will often di er from one line to another.

We shall prove that, for some sequence of events E n satisfying P(E n ) → 1 as n → ∞ (those from Corollary ), for every q > 4, for every β ∈ (0, q/4 -1), for every n large enough, for every i, j ∈ {0, . . . , N n },

E [|L n (i) -L n (j)| q | E n ] ≤ C(q) • N q/4 n • i -j N n 1+β . ( ) Set L (n) (t) = N -1/4 n L n (N n t) for n ∈ N and t ∈ [0, 1], then the previous display reads E L (n) (s) -L (n) (t) q E n ≤ C(q) • |s -t | 1+β ,
whenever s, t ∈ [0, 1] are such that N n s and N n t are both integers. Since L (n) is de ned by linear interpolation between such times, this bound then holds for every s, t ∈ [0, 1] (possibly with a di erent constant C(q)). Since q can be chosen arbitrarily large, the standard Kolmogorov criterion then implies the following bound for the Hölder norm of L (n) : for every α ∈ (0, 1/4), lim

K →∞ lim sup n→∞ P sup 0≤s t ≤1 |L (n) (s) -L (n) (t)| |s -t | α > K E n = 0; since P(E n ) → 1 as n → ∞, we obtain lim K →∞ lim sup n→∞ P sup 0≤s t ≤1 |L (n) (s) -L (n) (t)| |s -t | α > K = 0,
and the sequence

(L (n) ; n ≥ 1) is tight in C([0, 1], R).
The proof of ( ) relies on the coding of T n by its Łukasiewicz path. The next lemma, whose proof is left as an exercise, gathers some deterministic results that we shall need (we refer to e.g. Le Gall [ ] for a thorough discussion of such results). In order to simplify the notation, we identify for the remainder of this section the vertices of a one-type tree with their index in the lexicographic order: if u and u ′ are the i-th and i ′ -th vertices of T n , we write u ≤ K if i ≤ K, W n (u) for W n (i) and |uu ′ | for |ii ′ |, the lexicographic distance between u and u ′ . Recall also that uj is the j-th child of a vertex u.

Lemma . Let T be a one-type plane tree and W be its Łukasiewicz path. Fix a vertex u ∈ T , then

W (uk u ) = W (u), W (uj ′ ) = inf [u j,u j ′ ] W and j ′ -j = W (uj) -W (uj ′ )
for every 1 ≤ j ≤ j ′ ≤ k u .

In the course of the proof of ( ), we shall need the following two ingredients. First, a consequence of the so-called Marcinkiewicz-Zygmund inequality, see e.g. Gut [ , Theorem . ]: x q ≥ 2 and consider independent and centred random variables Y 1 , . . . , Y m which admit a nite q-th moment, then there exists C(q) ∈ (0, ∞) such that

1 C(q) • E       m i=1 |Y i | 2 q/2      ≤ E m i=1 Y i q ≤ C(q) • E       m i=1 |Y i | 2 q/2      .
Consider the right-most term, and raise it temporarily to the power 2/q in order to apply the triangle inequality for the L q/2 -norm, the second inequality thus yields the following bound:

E m i=1 Y i q ≤ C(q) • m i=1 E [|Y i | q ] 2/q q/2 . ( )
Second, for every r ≥ 1, consider X (r ) a uniform random bridge in B + r , de ned in ( ); Le Gall & Miermont [ , Lemma ] have shown that for every q ≥ 2 and every i, j ∈ {0, . . . , r },

E X (r ) i -X (r ) j q ≤ C(q) • |i -j | q/2 . ( )
Proof of Proposition . Recall that we identify the vertices of T n with their index in the lexicographic order. Fix q > 4, β ∈ (0, q/4 -1), n large enough so that E n de ned in Corollary has probability larger than 1/2, and two integers 0 ≤ u < ≤ N n + 1 withu ≤ ⌊N n /2⌋; we aim at showing

E [|l n (u) -l n ( )| q | E n ] ≤ C(q) • N q/4 n • u - N n 1+β .
Let u ∧ , be the most recent common ancestor of u and in T n and further û and ˆ be the children of u ∧ which are respectively ancestor of u and . We stress that u and are deterministic times, whereas u ∧ , û and ˆ are random and measurable with respect to T n . We write:

l n (u) -l n ( ) = w ∈ û,u l n (w) -l n (pr (w)) + (l n ( û) -l n ( ˆ )) + w ∈ ˆ ,
l n (pr (w))l n (w) .

Recall the notation 1 ≤ χ û ≤ χ ˆ ≤ k u∧ for the relative position of û and ˆ among the children of u ∧ . By construction of the labels on T n , the bound ( ) reads in our context:

E [|l n ( û) -l n ( ˆ )| q | T n ] ≤ C(q) • (χ ˆ -χ û ) q/2 .
Next, x w ∈ û, u , since l n (pr (w)) = l n (pr (w)k pr (w ) ), as previously, the bound ( ) gives:

E [|l n (w) -l n (pr (w))| q | T n ] ≤ C(q) • (k pr (w ) -χ w ) q/2 .
Similarly, for every w ∈ ˆ , , we have

E [|l n (pr (w)) -l n (w)| q | T n ] ≤ C(q) • χ q/2 w .
According to the inequality ( ), we thus have

E [|l n (u) -l n ( )| q | T n ] ≤ C(q) • w ∈ û,u (k pr (w ) -χ w ) + (χ ˆ -χ û ) + w ∈ ˆ , χ w q/2 ≤ C(q) • w ∈ û,u (k pr (w ) -χ w ) + (χ ˆ -χ û ) q/2 + w ∈ ˆ , χ w q/2 . ( )
Let us rst consider the rst term in ( ). Appealing to Lemma , we have

χ ˆ -χ û = W n ( û) -W n ( ˆ ),
and similarly, for every w ∈ û, u ,

k pr (w ) -χ w = W n (w) -W n (pr (w)k pr (w ) ) = W n (wk w ) -W n (pr (w)k pr (w ) ), so w ∈ û,u (k pr (w ) -χ w ) + (χ ˆ -χ û ) = W n (u) -W n ( ˆ ) = W n (u) -inf [u, ]
W n .

Proposition then yields

E       w ∈ û,u (k pr (w ) -χ w ) + (χ ˆ -χ û ) q/2 E n       ≤ C(q) • |u -| q/4 ≤ C(q) • N q/4 n • u - N n 1+β .
We next focus on the second term in ( ). We would like to proceed symmetrically but there is a technical issue: on the branch û, u , we strongly used the fact that l n (wk w ) = l n (w) and this does no hold on ˆ , : we do not have l n (w1) = l n (w) in general. Let T - n be the "mirror image" of T n , i.e. the tree obtained from T n by ipping the order of the children of every vertex; let us write w -∈ T - n for the mirror image of a vertex w ∈ T n ; make the following observations:

• T - n has the same law as T n , so in particular, its Łukasiewicz path has the same law as that of T n ;

• for every w ∈ ˆ , , the quantity χ w -1 in T n corresponds to the quantity k pr (w -)χ w -in T - n ;

• the lexicographical distance between the last descendant inT - n of respectively ˆ -and -is smaller than the lexicographical distance between ˆ and in T n (the elements of ˆ , = ˆ -, -are missing).

With theses observations, the previous argument used to control the branch û, u shows that

E       w ∈ ˆ , (χ w -1) q/2 E n       ≤ C(q) • |u -| q/4 ≤ C(q) • N q/4 n • u - N n 1+β .
Since χ w ≤ 2(χ w -1) whenever χ w ≥ 2, it only remains to show that

E #{w ∈ ˆ , : χ w = 1} q/2 E n ≤ C(q) • N q/4 n • u - N n 1+β .
Let C and h n be as in Corollary . On the one hand, since h n is small compared to any positive power of N n , we have for n large enough,

E #{w ∈ ˆ , : χ w = 1} q/2 1 {# ˆ , ≤h n } ≤ h q/2 n ≤ N q/4 n • u - N n 1+β .
On the other hand, if # ˆ , > h n , then on the event E n , we know that

#{w ∈ ˆ , : χ w = 1} ≤ C • #{w ∈ ˆ , : χ w ≥ 2} ≤ C w ∈ ˆ ,
(χ w -1).

We then conclude from the previous bound.

Remark . It is possible that the following stronger bound than ( ) holds: for every q > 4 and every

0 ≤ u < ≤ N n + 1, E [|L n (u) -L n ( )| q ] ≤ C(q) • |u -| q/4 . ( )
Indeed, the only missing point in the previous proof is the last bound on the moments of #{w ∈ ˆ , : χ w = 1 and k pr (w ) ≥ 2}. Observe that

#{w ∈ ˆ , : χ w = 1 and k pr (w ) ≥ 2} ≤ # w ∈ [u, [: W n (w) < inf ]w, ] W n (d) = # w ∈]0, -u] : S n (w) > sup [0,w [ S n ≤ sup 0≤w ≤ -u S n (w),
where S n is a uniform random bridge in B(n), as de ned in Section . ; it is obtained by rst taking the -th cyclic shift of W n and then going backward in time and space.

Under the stronger assumption that ∆ n is uniformly bounded (which is the case for e.g. uniform random 2κ-angulations), Proposition shows that for every r > 0,

E sup 0≤w ≤ -u S n (w) r ≤ C(r ) • |u -| r /2 ,
uniformly for n ∈ N and 0 ≤ u < ≤ N n + 1 such that |u -| ≤ ⌊N n /2⌋, which yields ( ). On another model, Miermont [ , Proof of Proposition ], obtained the bound

E # w ∈]0, -u] : S(w) = sup [0,w ] S r ≤ C(r ) • |u -| r /2 ,
where S is a centred random walk with nite variance. The argument used in the proof of Lemma enables us to extend it to such a walk conditioned to be at -1 at time N n + 1. This case corresponds to Boltzmann random maps (with generic critical weight sequence) studied in Section , for which ( ) therefore holds.

Note that we did not include the condition k pr (w ) ≥ 2 in the previous proof but the increment of label is zero if k pr (w ) = 1.

De nition . An admissible sequence q is called critical when Z ⋆ q is the unique xed point of q and satis es moreover ′ q (Z ⋆ q ) = 1. It is called generic critical when it is admissible, critical, and ′′ q (Z ⋆ q ) < ∞, and regular critical when moreover Z ⋆ q < R q . Note that an admissible sequence q induces a probability measure on Z + with mean smaller than or equal to one:

p q (k) = (Z ⋆ q ) k-1 2k -1 k -1 q k , k ≥ 0. ( ) Indeed, k ≥0 p q (k) = q (Z ⋆ q ) Z ⋆ q = 1, and k ≥0 kp q (k) = ′ q (Z ⋆ q ) ≤ 1.
This distribution has mean 1 if and only if q is critical, and in this case, its variance is

Σ 2 q = k ≥0 k 2 p q (k) -1 = d dx x ′ q (x) x =Z ⋆ q -1 = Z ⋆ q ′′ q (Z ⋆ q ), ( )
which is nite if and only if q is generic critical. In terms of the function

f q from [ ], we have Σ 2 q = (2 + (Z ⋆ q ) 3 f ′′ q (Z ⋆ q ))/Z ⋆ q .
The argument of [ , Proposition ] show that if q is regular critical, then p q admits small exponential moments.

Theorem . Suppose q is generic critical, de ne p q by ( ) and Σ 2 q by ( ) and for every subset A ⊂ N, de ne

C q E = 1, C q V = p q (0) = 1 Z ⋆ q , C q F = 1 -p q (0) = 1 - 1 Z ⋆ q , C q F,A = p q (A).
Fix S ∈ {E, V , F } ∪ A ⊂N {F , A} and for every n ≥ 2, sample M n from P q S =n , then the convergence in distribution

M n , 9 4 C q S Σ 2 q 1 n 1/4 d gr (d) -→ n→∞ (M, D),
holds in the sense of Gromov-Hausdor .

Note that the Boltzmann laws in this statement are not the pointed versions. We shall prove rst that it holds under the pointed version P q,⋆ S =n , relying on the composition of the BDG and JS bijections to check that (H) is ful lled with the probability p q given by ( ). Then we will show that P q,⋆ S =n and P q S =n are close as n → ∞; the argument of the latter will closely follow that of Bettinelli & Miermont [ , Section . ], see also Abraham [ , Section ], and Bettinelli, Jacob & Miermont [ , Section ].

Remark . Le Gall [ , Theorem . ] obtained this result in the case S = V , when q is supposed to be regular critical, not only generic critical. Bettinelli & Miermont [ , Theorem ] also obtained similar convergences in the three cases S = E, V , F for Boltzmann maps with a boundary, associated with regular critical weights. Theorem completes (and improves since we only assume q to be generic critical) their Remark .

Note that M E=n is nite for every n ≥ 2 so the Boltzmann distribution P q E=n makes sense even if Z q = ∞. The proof of Theorem shows that we do not need q to be admissible in this case.

Theorem . Suppose there exists x > 0 (necessarily unique) such that q (x) < ∞,

x ′ q (x) = q (x), and x ′′ q (x) < ∞.

Then if M n is sampled from P q E=n for every n ≥ 2, the convergence in distribution

M n , 9 4 q (x) x 2 ′′ q (x) 1 n 1/4 d gr (d) -→ n→∞ (M, D),
holds in the sense of Gromov-Hausdor .

If q is generic critical, then the assumptions are ful lled by x = Z ⋆ q : we have q (Z ⋆ q ) = Z ⋆ q so x ′ q (x) = q (x) is equivalent to ′ q (Z ⋆ q ) = 1 and then q (x)

x 2 ′′ q (x) = 1 Z ⋆ q ′′ q (Z ⋆ q ) = 1 Σ 2 q = C q E Σ 2 q ,
so Theorem recovers Theorem .

As an application of Theorem , consider the case q k = 1 for every k ≥ 1, then P q E=n is the uniform distribution in M E=n . In this case, q has a radius of convergence equal to 1/4 and is given by .

q (x) = 1 + k ≥1 x k 2k -1 k -1 = 1 + √ 1 -4x 2 √ 1 -4x , 0 < x < 1/4. Furthermore, x ′ q (x) = q (x) if

Simply generated trees

Let us de ne a measure on the set of nite one-type tree T by

Θ q (T ) = u ∈T w(k u ), T ∈ T.
Let ϒ q = Θ q (T), if the latter is nite, we de ne a probability measure on T by

SG q (•) = 1 ϒ q Θ q (•).
A random tree sampled according to SG q is called a simply generated tree. Such distributions have been introduced by Meir & Moon [ ] and studied in great detail by Janson [ ] on the set of trees with a given number of vertices. A particular case is when the weight sequence q is a probability measure on Z + with mean less than or equal to one: in this case, ϒ q = 1 and SG q = Θ q is the law of a subcritical Galton-Watson tree with o spring distribution q; we denote it by GW q . When the expectation of q is exactly equal to one, we say that q (as well as any random tree sampled from GW q ) is critical.

Note that we may de ne simply generated trees with n vertices even if ϒ q is in nite by rescaling the measure Θ q restricted to this nite set by its total mass.

Lemma . Let us denote by #T the number of vertices of a tree T ∈ T.

(i) Fix c > 0 and set qk = c k-1 q k for every k ≥ 0. Then ϒ q < ∞ if and only if ϒ q < ∞ and in this case, the laws SG q and SG q coincide.

(ii) Fix a, b > 0 and set qk = ab k q k for every k ≥ 0. Then the conditional laws SG q( • | #T = n) and SG q ( • | #T = n) coincide for all n ≥ 1.

Proof. Note that for every tree T ∈ T, one has

u ∈T k u = #T -1 and so u ∈T (k u -1) = -1; it follows that Θ q(T ) = u ∈T c k u -1 q k u = c -1 Θ q (T ),
so ϒ q = c -1 ϒ q and the rst claim follows. Similarly,

Θ q(T ) = u ∈T ab k u q k u = a #T b #T -1 Θ q (T ), so Θ q({T ∈ T : #T = n}) = a n b n-1 Θ q ({T ∈ T : #T = n})
and the second claim follows.

We shall use Lemma with sequences q or q which are probability measures with mean 1 so, in the rst case, SG q = GW q is the law of a critical Galton-Watson tree, and in the second case, SG q( • | #T = n) = GW q( • | #T = n) is the law of such a tree conditioned to have n vertices.

We close this section with two results on size-conditioned critical Galton-Watson; the proofs are deferred to Section . . We rst claim that the empirical degree sequence of a Galton-Watson tree conditioned to be large satis es (H). For a plane tree T and an integer i ≥ 0, let us denote by n T (i) = #{u ∈ T : k u = i} the number of vertices of T with i children. For any subset A ⊂ Z + , set n T (A) = i ∈A n i (T ); note that n T (Z + ) is the total number of vertices of T , n T (0) is its number of leaves and n T (N) its number of internal vertices. Consider the empirical o spring distribution of T and its variance, given by

p T (i) = n T (i) n T (Z + ) for i ≥ 0 and σ 2 T = i ≥0 i 2 p T (i) - n T (Z + ) -1 n T (Z + ) 2 ,
and nally set ∆ T = max{i ≥ 0 : n T (i) > 0}.

Proposition . Let µ be a critical distribution in Z + with variance σ 2 ∈ (0, ∞) and x A ⊂ Z + ; under

GW µ ( • | n T (A) = n), the convergence p T , σ 2 T , n T (Z + ) -1/2 ∆ T P -→ n→∞ (µ, σ 2 , 0), holds in probability.
This result was obtained by Broutin & Marckert [ , Lemma ] in the case A = Z + . Their proof extends to the general case using arguments due to Kortchemski [ ].

Finally, we claim that the inverse of the number of leaves, normalised to have expectation 1, converges to 1 in L 1 .

Lemma . Let µ be a critical distribution in Z + with variance σ 2 ∈ (0, ∞). For every A ⊂ Z + , we have

lim n→∞ GW µ 1 n T (0) 1 GW µ [ 1 n T (0) | n T (A) = n] -1 n T (A) = n = 0.
.

Convergence of Boltzmann random maps

We rst prove the convergence of rooted and pointed Boltzmann maps, using the BDG and the JS bijections, and next compare the pointed and non pointed Boltzmann laws to deduce Theorems and .

Proposition . Theorems and hold under their respective assumptions when the measures P q S =n are replaced by their pointed version P q,⋆ S =n . The main idea is to observe that for every n ≥ 2 and S ∈ {E, V , F } ∪ A ⊂N {F , A}, the composition of the BDG and the JS bijections maps the set M ⋆ S =n onto the subset of T of those trees T satisfying n T (B S ) = n, where for every A ⊂ N,

B E = Z + , B V = {0}, B F = N and B F,A = A. ( )
Proof. Fix a rooted and pointed map (M, ⋆) ∈ M ⋆ and let (T , l) be its associated labelled one-type tree after the BDG and then the JS bijections. Recall that the faces of M are in bijection with the internal vertices of T , whereas the vertices of M di erent from ⋆ are in bijection with the leaves of T ; in particular, with the notation of the previous subsection, for every i ≥ 1, the number of faces of M of degree 2i is given by n T (i), and its number of vertices minus one by n T (0). Thereby,

W q,⋆ ((M, ⋆)) = f ∈Faces(M) q deg(f )/2 = u ∈T :k u ≥1 q k u .
Recall also from ( ) the number of possible labellings of a given plane tree. The measure W q,⋆ on M ⋆ thus induces a measure on T, where each T ∈ T is given the weight

u ∈T :k u ≥1 2k u -1 k u -1 q k u = Θ q (T ),
where q is given by ( ). This shows that if (M, ⋆) has the law P q,⋆ and (T , l) its associated labelled onetype tree after the BDG and then the JS bijections, thenT has the law SG q . Similarly, for every n ≥ 2 and S ∈ {E, V , F } ∪ A ⊂N {F , A}, if (M, ⋆) has the law P q,⋆ S =n , then T has the law SG q ( • | n T (B S ) = n), where B S is given by ( ). Furthermore, in both cases, conditional on the tree T , the labelling l is uniformly distributed amongst all possibilities.

Let us now prove that Theorem holds for the pointed maps sampled from P q,⋆ E=n . Suppose that x > 0 is such that q (x) < ∞,

x ′ q (x) = q (x), and x ′′ q (x) < ∞.

De ne a probability measure on Z + similar to ( ) where Z ⋆ q is replaced by x:

µ q (k) = x k q k q (x) , k ≥ 0. ( )
Note that µ q has expectation k ≥0 kµ q (k) = x ′ q (x) q (x)

= 1, and variance k ≥0

k 2 µ q (k) -1 = x ′ q (x) + x 2 ′′ q (x) q (x) -1 = x 2 ′′ q (x) q (x) ∈ (0, ∞).

According to Lemma (ii), the tree T has the law GW µ q ( • | n T (Z + ) = n), Proposition and Skorohod's representation Theorem ensure then that, on some probability space, (H) is ful lled almost surely with p = µ q and we conclude from Theorem . The proof of the fact that Theorem holds for the pointed maps sampled from P q,⋆ S =n is similar. If q is generic critical, then Z ⋆ q satis es the above assumptions on x and furthermore q (Z ⋆ q ) = Z ⋆ q so µ q is the probability p q given by ( ):

µ q (k) = p q (k) = (Z ⋆ q ) k-1 q k , k ≥ 0.
According to Lemma (i), the tree T has the law GW p q ( • | n T (B S ) = n). Again, Proposition ensures then that (H) is ful lled with p = p q and the claim follows.

We have seen all the ingredients to prove Proposition . The proof is inspired from [ ].

Proof of Proposition . Let q be given by ( ). According to the previous proof, we have

Z ⋆ q = (M,⋆)∈M ⋆ W q,⋆ ((M, ⋆)) = T ∈T Θ q (T ) = ϒ q ,
Suppose that this quantity is nite, we next decompose the second sum according to the degree of the root of T . If the latter is k, then T is made of k trees, say T 1 , . . . ,T k , attached to a common root; this leads to the following equation:

T ∈T Θ q (T ) = k ≥0 q k T 1 , ...,T k ∈T k i=1 Θ q (T i ) = k ≥0 q k T ∈T Θ q (T ) k ,
in other words Z ⋆ q = q (Z ⋆ q ). Let us prove furthermore that ′ q (Z ⋆ q ) ≤ 1. Since Z ⋆ q = q (Z ⋆ q ), the sequence p q de ned by p q (k) = (Z ⋆ q ) k-1 q k for every k ≥ 0 is a probability and ′ q (Z ⋆ q ) is its mean. According to Lemma (i), the law SG q coincides with SG p q so T ∈T SG p q (T ) = 1 ϒ q T ∈T Θ q (T ) = 1.

We conclude that SG p q = GW p q is the law of a sub-critical Galton-Watson tree with o spring distribution p q , which has therefore mean ′ q (Z ⋆ q ) ≤ 1. Conversely, suppose that q has at least one xed point and let us prove that Z ⋆ q is nite. Recall that one of the xed points, say, x > 0, must satisfy ′ q (x) ≤ 1; we set µ q (k) = x k-1 q k for every k ≥ 0, the previous calculations show that µ q is a probability measure with mean ′ q (x) ≤ 1. According to (the proof of) Lemma (i), we have

1 x Z ⋆ q = 1 x (M,⋆)∈M ⋆ W q,⋆ ((M, ⋆)) = 1 x T ∈T Θ q (T ) = T ∈T Θ µ q (T ) = 1.
We conclude that Z ⋆ q = x is indeed nite.

Finally, we show that the pointed and non pointed Boltzmann laws are close to each other, following arguments from [ , , ]. Theorems and follow from Propositions and .

Proposition . Fix S ∈ {E, V , F } ∪ A ⊂N {F , A} and let q satisfy the assumptions of Theorem or of Theorem if S = E. Let ϕ : M ⋆ → M : (M, ⋆) → M and let ϕ * P q,⋆ S =n be the push-forward measure induced on M by P q,⋆ S =n , then P q S =nϕ * P q,⋆ S =n T V -→ n→∞ 0, where • T V refers to the total variation norm.

Proof. For each pointed map (M, ⋆) ∈ M ⋆ , let V (M) be the number of vertices of M. If T is the one-type tree associated with (M, ⋆), then V (M) = n T (0) -1. Notice that P q,⋆ S =n is absolutely continuous with respect to P q S =n : for every measurable and bounded function f : M → R, we have

E q S =n [f (M)] = E q,⋆ S =n V (M) -1 -1 E q,⋆ S =n V (M) -1 f • ϕ((M, ⋆)) .
Let p q be given by ( ) or ( ) in the case S = E and let B S be given by ( ). We have

P q S =n -ϕ * P q,⋆ S =n T V = 1 2 sup -1≤f ≤1 E q S =n [f (M)] -E q,⋆ S =n [f • ϕ((M, ⋆))] ≤ 1 2 sup -1≤f ≤1 E q,⋆ S =n E q,⋆ S =n V (M) -1 -1 V (M) -1 -1 f • ϕ((M, ⋆)) ≤ E q,⋆
S =n E q,⋆ S =n V (M) -1 -1 V (M) -1 -1 = GW p q GW p q [(n T (0) -1) -1 | n T (B S ) = n] -1 (n T (0) -1) -1 -1 n T (B S ) = n .

Lemma states that the last quantity above tends to zero as n → ∞, which concludes the proof.

. On Galton-Watson trees conditioned to be large

It remains to prove Proposition and Lemma . The proof of the former result relies on the coding of a tree by its Łukasiewicz path which, in the case of Galton-Watson trees is an excursion of a certain random walk. Our proofs use many results from [ ] (see in particular sections and there), written explicitly for A = {0} but which hold true in general, mutatis mutandis, as explained in Section there.

According to [ , Theorem . ], there exists an explicit constant C > 0 which depends only on µ and A (see [ , Theorem . ]) such that GW µ (n T (A) = n) ∼ C • n -3/2 as n → ∞. Moreover, from [ , Corollary . ],

GW µ n T (0) µ(0)n T (Z + ) -1 > n -1/4 n T (Z + ) ≥ n = oe 1/2 (n).

Indeed, taking t = 1 in [ , Corollary . ], we read n T (0) = Λ T (ζ (T )). This result holds also when 0 is replaced by A; it follows that

GW µ n T (0)µ(A) n T (A)µ(0) -1 > µ(A) µ(0) ε n T (Z + ) ≥ n = oe 1/2 (n),
and the proof is complete.

Proof of Lemma . Fix ε ∈ (0, 1) and observe that, since n T (0) -1 ≤ 1,

GW µ µ(0)n µ(A)n T (0) -1 n T (A) = n ≤ ε + µ(0)n µ(A) + 1 GW µ µ(0)n µ(A)n T (0) -1 > ε n T (A) = n .
Next, the probability on the right-hand side is bounded above by

GW µ n T (0) n < 1 2 µ(0) µ(A) n T (A) = n + GW µ µ(0) µ(A) - n T (0) n > ε 2 µ(0) µ(A) n T (A) = n ,
which is oe δ (n) for some δ > 0 according to Lemma . This yields The claim now follows from these two limits.

are distributed as (B k ; 0 ≤ k ≤ r /2).

Proof of Lemma . First note that on the event {S r = 0}, max 0≤k ≤r S k -min 0≤k ≤r S k cannot exceed br . Moreover, on the event {S r = 0}, the path (S 0 , . . . , S r ) is an exchangeable bridge so, according to Lemma , it su ces to show that there exists two constants c, C > 0 which only depend on b and σ such that for every r ≥ 1 and 0 ≤ x ≤ br , We conclude that for every r ≥ 1 and every 0 ≤ x ≤ br , we have

P min 0≤k ≤ ⌈r /2⌉
S k ≤ -x S r = 0 ≤ C exp -x 2 2σ 2 ⌈r /2⌉ + 2bx/3 ≤ C exp -x 2 (2σ 2 + 2b 2 /3)r , and the proof is complete.

  Fix κ ≥ 2 and for every n ≥ 2, let M (κ) n be a uniform random 2κ-angulation with n faces. The following convergence in distribution holds in the sense of Gromov-Hausdor :

  Figure :A two-type labelled tree, its white contour process on top and its white label process below.

  Figure :A one-type labelled tree, its height process on top and its label process below.

  Figure for an illustration.

Figure :

 : Figure :The Janson-Stefánsson bijection from two-type trees to one-type trees.

  lim n→∞ GW µ µ(0)n µ(A)n T (0) -1 n T (A) = n = 0, and so lim n→∞ µ(0)n µ(A) GW µ 1 n T (0) n T (A) = n = 1.

S

  k ≤ -x S r = 0 ≤ Ce -cx 2 /r .For every k ≥ 1 and every x ∈ Z, let us set θ k (x) = P (S k = -x). According to the local limit theorem, for every k ≥ 1 and x ∈ Z,√ kθ k (x) = (x/ √ k) + ε k (x),where (x) = (2π σ 2 ) -1/2 e -x 2 /(2σ 2 ) and lim k→∞ supx ∈Z |ε k (x)| = 0. It follows that C ≔ sup r ≥1,x ∈Z θ r -⌈r /2⌉ (x) θ r (0) = sup r ≥1,x ∈Z r r -⌈r /2⌉ (-x/ r -⌈r /2⌉) + ε r -⌈r /2⌉ (x) (0) + ε r (0) < ∞.Using the Markov property at time ⌈r /2⌉, we have therebyP min 0≤k ≤ ⌈r /2⌉ S k ≤ -x S r = 0 = P min 0≤k ≤ ⌈r /2⌉ S k ≤ -x and S r = 0 P (S r = 0) = E 1 {min 0≤k ≤⌈r /2⌉ S k ≤-x } θ r -⌈r /2⌉ (S ⌈r /2⌉ ) θ r (0) ≤ C • P min 0≤k ≤ ⌈r /2⌉ S k ≤ -x .Finally, since -S is a random walk with step distribution bounded above by b, centred and with variance σ 2 , we have the following concentration inequality (see e.g. Mc Diarmid [ ], Theorem . and the remark at the end of Section there): for every n ≥ 1 and every x ≥ 0,

  The proofs of Theorems and use the notion of simply generated trees that we next recall.

	and only if x =	3 16	,	and then	q (3/16) (3/16) 2 ′′ q (3/16)	=	9 2	,
	so Theorem yields Corollary .

This worked was supported by the Fondation Sciences Mathématiques de Paris and the Univ. Pierre et Marie Curie for a major part, and then the Fondation Mathématique Jacques Hadamard; partial support also from the grant ANR-14-CE25-0014 (ANR GRAAL).

Convergence of random maps

In this short section we deduce Theorem from Theorem , following the argument of Le Gall [ , Section . ] and [ , Section ]. First, observe that every map in M(n) has n 0 + 1 vertices so, if M n has the uniform distribution in M(n) and M ⋆ n is a pointed map obtained by distinguishing a vertex of M n uniformly at random, then M ⋆ n has the uniform distribution in M ⋆ (n). It is therefore su cient to prove Theorem with M n replaced by M ⋆ n . Let M ⋆ n be a (deterministic) pointed and rooted planar map in M ⋆ (n) and denote by ⋆ its origin; let (T n , ℓ n ) be its associated two-type labelled tree via the BDG bijection and let (c • 0 , . . . , c • N n ) be the white contour sequence of the latter. Recall that the vertices c • i are identi ed to the vertices of M n di erent from ⋆. For every i, j ∈ {0, . . . , N n }, we set

where d gr is the graph distance of M n . We then extend d n to a continuous function on [0, N n ] 2 by "bilinear interpolation" on each square of the form [i, i + 1] × [j, j + 1] as in [ , Section . ]. Recall the convention c • N n +i = c • i for every 0 ≤ i ≤ N n and the interpretation, at the very end of Section . , of the labels as distances from ⋆ in M n : for every 0 ≤ i ≤ N n ,

Then, using the triangle inequality at a point where a geodesic from c • i to ⋆ and a geodesic from c • j to ⋆ merge, Le Gall [ , Equation ] obtains the bound

See also Lemma . in [ ] for a detailed proof in a slightly di erent context. De ne for every t ∈ [0, 1]:

C n (2N n t), and

and for every s, t ∈ [0, 1]:

where Ľ• (n) is de ned in a similar way as Ž in Section . .

holds, where D is de ned in Section . .

Proof. The convergence ( ), jointly with Remark yields the convergence in distribution

The bound ( ) implies further the tightness of (d (n) ; n ≥ 1), see Proposition . in [ ] for a proof in a similar context. Therefore, from every sequence of integers converging to ∞, we can extract a subsequence along which we have

where (D(s, t); 0 ≤ s, t ≤ 1) depends a priori on the subsequence. We claim that

From the bound ( ), D is bounded above by D Z , also (see Proposition . in [ ]), one can check that D is a pseudo-metric on [0, 1] which satis es D(s, t) = 0 as soon as d e (s, t) = 0. It thus follows from the maximality property discussed in section . that D ≤ D almost surely. Our aim is to show the following: let X , Y be i.i.d. uniform random variables on [0, 1] such that the pair (X , Y ) is independent of everything else, then

where s ⋆ is the (a.s. unique [ ]) point at which Z attains its minimum. The second equality is a continuous analog of ( ) which can be obtained from the latter by letting n → ∞ along the same subsequence as in ( ). Le Gall [ , Corollary . ] has proved that ( ) holds true when D is replaced by D. ) and let 1 , . . . , n 0 be its white vertices listed in the order of their last visit in the contour sequence; for example the root is n 0 . For

) is an enumeration of the white vertices of T n without redundancies. We then set (0) = 0 and extend linearly to a continuous function on [0, n 0 ]. Let us prove that

Let Λ(0) = 0 and for every 1 ≤ j ≤ N n , let

denote the number of vertices fully explored at time j in the white contour exploration. Then ( ) is equivalent to

Let T n be the image of T n by the JS bijection; it can be checked along the same line as the proof of Lemma that for every 1 ≤ j ≤ N n , Λ(j) denotes the number Λ T n , j (0) of leaves among the rst j vertices of T n in lexicographical order. The above convergence of Λ thus follows from Proposition . Fix X , Y i.i.d. uniform random variables on [0, 1] such that the pair (X , Y ) is independent of everything else, and set x = c • ( ⌈n 0 X ⌉) and = c • ( ⌈n 0 Y ⌉) . Note that x and are uniform random white vertices of T n , they can therefore be coupled with two independent uniform random vertices x ′ and ′ of M ⋆ n in such a way that the conditional probability given M ⋆ n that (x, ) (x ′ , ′ ) is at most 2(n 0 + 1) -1 → 0 as n → ∞; we implicitly assume in the sequel that (x, ) = (x ′ , ′ ). Since ⋆ is also a uniform random vertex of M ⋆ n , we obtain that d gr (x, )

= d gr (⋆, ). ( ) By de nition,

and, according to ( ),

We obtain ( ) by letting n → ∞ in ( ) along the same subsequence as in ( ), appealing also to ( ).

The proof of Theorem is then routine.

Proof of Theorem . We aim at showing the convergence of metric spaces

for the Gromov-Hausdor topology. Recall (see e.g. [ , Chapter . ]) that a correspondence between two metric spaces (X , d X ) and

Finally, the Gromov-Hausdor distance between (X , d X ) and (Y , d Y ) is given by ([ , Theorem . . ])

where the in mum is taken over all correspondences R between (X , d X ) and (Y , d Y ).

The proof is deterministic: we show that the convergence ( ) holds whenever that in Proposition does. Indeed, let (M ⋆ n \ {⋆}, d gr ) be the metric space given by the vertices of M ⋆ n di erent from ⋆ and their graph distance in M ⋆ n and observe that the Gromov-Hausdor distance between (M ⋆ n , d gr ) and (M ⋆ n \ {⋆}, d gr ) is bounded by one. Recall that the vertices of M ⋆ n di erent from ⋆ are in bijection with the white vertices of its associated two-type tree T n , which are given (with redundancies) by the white contour sequence (c • 0 , . . . , c • N n ). Let Π be the canonical projection T e → M = T e /≈, then the set

and (M, D) and its distortion is given by sup

which tends to 0 whenever the convergence in Proposition holds. This concludes the proof.

Boltzmann random maps

In this last section, we state and prove the results alluded in Section . on Boltzmann random maps. Let us make a preliminary remark: we shall divide by real numbers which depend on an integer n, and consider conditional probabilities with respect to events which depend on n; we shall therefore, if necessary, implicitly restrict ourselves to those values of n for which such quantities are well-de ned and statements such as "as n → ∞" should be understood along the appropriate sequence of integers.

Let us x a sequence of non-negative real numbers q = (q i ; i ≥ 0) which, in order to avoid trivialities, satis es q i > 0 for at least one i ≥ 2.

.

Rooted and pointed Boltzmann maps

Let M ⋆ be the set of all rooted and pointed bipartite maps, that we shall view as pairs (M, ⋆), where M ∈ M is a rooted bipartite map, and ⋆ is a vertex of M. We adapt the distributions described in Section . to such maps by setting

where Faces(M) is the set of faces of M and deg(f ) is the degree of such a face f . We set Z ⋆ q = W q,⋆ (M ⋆ ).

De nition . The sequence q is called admissible when Z ⋆ q is nite.

If q is admissible, we set

For every integer n ≥ 2, let M ⋆ E=n , M ⋆ V =n and M ⋆ F =n be the subsets of M ⋆ of those maps with respectively n -1 edges, n + 1 vertices (these shifts by one will simplify the statements) and n faces. More generally, for every A ⊂ N, let M ⋆ F,A=n be the subset of M ⋆ of those maps with n faces whose degree belongs to 2A (and possibly other faces, but with a degree in 2N \ 2A). For every S = {E, V , F } ∪ A ⊂N {F , A} and every n ≥ 2, we de ne

the law of a rooted and pointed Boltzmann map conditioned to have size n.

Given the sequence q, set q 0 = 1 and

and de ne the power series

Denote by R q its radius of convergence, note that q is convex, strictly increasing and continuous on [0, R q ] and q (0) = 1. In particular, it has at most two xed points, necessarily in (1, R q ]; in fact, we have the following exclusive four cases:

(i) There are no xed points.

(ii) There are two xed points

(iii) There is a unique xed point 1 < x ≤ R q , with ′ q (x) < 1.

(iv) There is a unique xed point 1 < x ≤ R q , with ′ q (x) = 1.

Marckert & Miermont [ ] have de ned another power series f q , such that q (x) = 1 + x f q (x) for every x ≥ 0. Proposition in [ ] reads as follows with our notation.

Proposition (Marckert & Miermont [ ])

. The sequence q is admissible if and only if q has at least one xed point. In this case, Z ⋆ q is the xed point satisfying ′ q (Z ⋆ q ) ≤ 1.

The proof in [ ] is based on the BDG bijection, we shall present a short adaption in Section . using the composition of the BDG and the JS bijections. Following [ ] let us introduce more terminology.

Proof of Proposition . Fix ε > 0 and consider the event

where d is a metric on the product space of probability measures on Z + and R 2 , compatible with the product topology. We aim at showing

Let us denote by (X k ; k ≥ 1) a sequence of i.i.d. random variables with distribution (µ(i + 1); i ≥ -1) and

As in Section . , given a path x = (x 1 , . . . ,

Using a time-reversibility property of (X 1 , . . . ,

. ], it su ces to show that

As in the proof of [ , Theorem . ], for any α > 0, the event F (ζ n/2 (A), ε) is included in the union of the following three events: By [ , Lemmas . & . ] (argument similar to the one we use in the proof of Lemma , based on a local limit theorem), there exists a constant C > 0 independent of α such that for every n large enough, the conditional probability P( • | S X (ζ n (A)) = -1) of the rst event is bounded above by

Next, according to [ , Equation ],

and, by [ , Lemma . (i)],

We conclude that there exists a constant C > 0 such that

On the event |ζ n/2 (A) -n µ(A) | ≤ n 3/4 , we have for every i ≥ 0,

and the claim from the fact that P(F (n, ε)) → 0 as n → ∞.

We next turn to the proof of Lemma . We shall need the following concentration result. For a sequence (x n ; n ≥ 1) of non-negative real numbers and δ > 0, we write

Lemma . Let µ be a critical distribution in Z + with variance σ 2 ∈ (0, ∞) and x A ⊂ Z + ; there exists δ > 0 such that

Proof. We bound

A Proof of the spinal decompositions

In this section, we prove Lemma and its extension Lemma .

A. The one-point decomposition

Proof of Lemma . First, concerning the rst good event, consider the "mirror image" T - n of T n , i.e. the tree obtained from T n by ipping the order of the children of every vertex. Denote by W - n the Łukasiewicz path of T - n . Observe that T - n and T n have the same law therefore W - n and W n as well. Furthermore, from Lemma , we have for all i ∈ {0, . . . , N n },

where i -is the index in T - n of the image of the i-th vertex of T n . The convergence of W n and H n in ( ) then yields

Regarding the second good event, let U be uniformly distributed in [0, 1] and independent of e, then ( ) implies similarly that for every x > 0, we have

Let us next turn to the comparison between A(u n ) conditioned on being in Good(n, x) and a multinomial sequence. Recall that we denote by χ u the relative position of a vertex u among its siblings. De ne next for every vertex u the content of the branch , u as

where the elements ∈ , u are sorted in increasing order of their height. For any sequence m ∈ Z N + , denote by Γ(m) the set of possible vectors Cont(u) when A(u) = m and note that

The removal of the branch , u from T produces a plane forest of LR(A(u)) trees and there is a oneto-one correspondence between the pair (T , u) on the one hand and this forest and Cont(u) on the other hand. For any sequence q = (q i ; i ≥ 0) of non-negative integers with nite sum, let F(q) be the set of plane forests having exactly q i vertices with i children for every i ≥ 0; such a forest possesses r = i ≥0 (1i)q i roots and it is well-known that

Sample T n uniformly at random in T(n) = F(n) and u n uniformly at random in T n , the previous bijection readily implies that for any sequence m satisfying m 0 = 0 and m i ≤ n i for every i ≥ 1 and for any vector C ∈ Γ(m), we have

, and so

.

Consequently, if we set h = |m|, we have

Note that

Putting things together, we obtain that if h ≤ N n /2, then

If m ∈ Good(n, x), then LR(m) and h are both bounded above by xN 1/2 n , so the proof is complete.

A. The multi-point decomposition

We next extend the previous decomposition according to several i.i.d. uniform random vertices.

Proof of Lemma . First, the fact that the probability of Bin + k tends to 1 can be seen as a consequence of ( ) and the fact that such a property holds almost surely for the Brownian tree. The rest of the event is similar to the previous proof and we omit the details to focus on the bound on the law of A(u n,1 , . . . , u n,k ). Precisely, we shall prove that for every sequences m (1) , . . . , m (2k-1) ∈ Good(n, x), if

Since ∆ n , each h j and each LR(m (j) ) is at most of order N 1/2 n , the claim follows. We treat in detail the case k = 2 and comment on the general case at the end. Fix r ≥ 2 and three sequences of non-negative integers m (1) , m (2) , m (3) with m (1) 0 = m (2) 0 = m (3) 0 = 0 and set |m (j) i | = h j for each j ∈ {1, 2, 3}. For every i ≥ 0, set

Given T n , we say that a pair of vertices (u, ) is "good" if the reduced tree T n (u, ) satis es Bin 2 . Observe that on the event {max a ∈T n |a| ≤ N 3/4 n }, there are more than N 2 n -o(N 2 n ) ≥ N 2 n /2 good pairs. If u n and n are independent uniform random vertices of T n , then the conditional probability given {max a ∈T n |a| ≤ N 3/4 n } that this pair is good tends to 1, and then on this event, (u n , n ) has the uniform distribution in the set of good pairs. In the remainder of this proof, we thus assume that (u n , n ) is a good pair sampled uniformly at random. Let w n be the most recent common ancestor of u n and n . Let ûn be the child of w n which is an ancestor of u n and de ne similarly ˆ n so this distribution. Let w n be the most recent common ancestor of u n and n . Let ûn be the child of w n which is an ancestor of u n and de ne similarly

Let Cont(u n , n ) be the triplet of contents of these branches, de ned in a similar way as in ( ). Let Γ(m (1) , m (2) , m (3) ) be the set of possible such triplets when A(u n , n ) = (m (1) , m (2) , m (3) ); as previously,

Observe that LR(m) = 1 + i ≥1 (i -1)m i = 2 + (r -2) + i ≥1 (i -1)m i denotes the number of trees in the forest obtained from T n by removing the reduced tree T n (u n , n ) when A(u n , n ) = (m (1) , m (2) , m (3) ) and k w n = r : there are i -1 components for each of the m i elements of , w n ∪ ûn , u n ∪ ˆ n , n with i children, as well as r -2 components corresponding to the children of w n di erent from ûn and ˆ n , and the two components above u n and n . As previously, the triplet (T n , u n , n ) is characterised by the forest obtained by removing the reduced tree T n (u n , n ) and the content of the latter, which is Cont(u n , n ) plus the information (k w n , χ ûn , χ ˆ n ) about the branch-point. We therefore have for every C ∈ Γ(m (1) , m (2) , m (3) ) and every B ∈ {(r, i, j);

Also, note that we must have r ≤ ∆ n and so

Then, as previously, we have j) , and

as well as, as soon as h

This concludes the case k = 2.

In the general case, the same argument applies. First, on the event {max a ∈T n |a| ≤ N 3/4 n }, for every n large enough, the number of k-tuples of vertices such that the associated reduced tree satis es Bin k is larger than

. . , u n,k is such a k-tuple sampled uniformly at random, then we may still decompose the tree according to the reduced tree T n (u n,1 , . . . , u n,k ) to obtain an explicit expression of the joint law of A(u n,1 , . . . , u n,k ) and the number of children of all the branch-points of T n (u n,1 , . . . , u n,k ). Speci cally, denote by n,1 , . . . , n,k-1 these branch-points, x m (1) , . . . , m (2k-1) and r 1 , . . . , r k-1 ≤ ∆ n , set h j = |m (j) | for 1 ≤ j ≤ 2k -1 and h = h 1 + • • • + h 2k-1 , as well as m i = 2k-1 j=1 m (j) i + k-1 j=1 1 {i=r j } for i ≥ 1, so |m| = h + k -1. Then, we have I P A(u n,1 , . . . , u n,k ) = (m (1) , . . . , m (2k-1) ) and k n, j = r j for every 1

Nota that r 1 , ...,r k -1 ≥2

k-1 j=1 r j (r j -1)n r j

, as well as, for h ≤ N n /2,

The rest of the proof is adapted verbatim.

B On the maximal gap in a random walk bridge Our aim in this section is to prove Lemma . Recall that for r ≥ 1, a discrete bridge of length r is a vector (B 0 , . . . , B r ) satisfying B 0 = B r = 0 and B k+1 -B k ∈ Z for every 0 ≤ k ≤ r -1. A random bridge is said to be exchangeable if the law of its increments (B 1 , B 2 -B 1 , . . . , B r -B r -1 ) is invariant under permutation.

Lemma . Fix r ≥ 1 and let B = (B 0 , . . . , B r ) be a discrete bridge.