On the growth of random planar maps with a prescribed degree sequence

For non-negative integers (d n (k)) k 1 such that k 1 d n (k) = n, we sample a bipartite planar map with n faces uniformly at random amongst those which have d n (k) faces of degree 2k for every k 1 and we study its asymptotic behaviour as n → ∞. We prove that the diameter of such maps grow like σ 1/2 n , where

More precisely, we prove that the vertex-set of these maps equipped with the graph distance divided by σ 1/2 n and the uniform probability measure always admits subsequential limits in the Gromov-Hausdor -Prokhorov topology.

Our proof relies on a bijection with random labelled trees; we are able to prove that the label process is always tight when suitably rescaled, even if the underlying tree is not tight for the Gromov-Hausdor topology. We also rely on a new spinal decomposition which is of independent interest. Finally this paper also serves as a toolbox for a companion paper in which we discuss more precisely Brownian limits of such maps.

. Introduction

This paper deals with scaling limits of random planar maps as their size tends to in nity and the edgelengths tend to zero. We consider quite general distributions on maps which are essentially con guration models on their dual maps studied previously in [Mar c]. Let us rst present precisely the model.

. . Model and notation. -Recall that a (rooted planar) map is a nite (multi-)graph embedded in the two-dimensional sphere, in which one oriented edge is distinguished (the root-edge), and viewed up to orientation-preserving homeomorphisms to make it a discrete object. The embedding allows to de ne the faces of the map which are the connected components of the complement of the graph on the sphere, and the degree of a face is the number of edges incident to it, counted with multiplicity: an edge incident on both sides to the same face contributes twice to its degree. For technical reasons, we restrict ourselves to bipartite maps, in which all faces have even degree. The face incident to the right of the root-edge is called the root-face, whereas the other faces are called inner faces. The collection of edges incident to the root-face is the boundary of the map. A map with only two boundary edges can be seen as a map without boundary by gluing these two edges together.

For every integer n 1, we are given an integer ϱ n 1 and a sequence (d n (k)) k 1 in Z N + such that k 1 d n (k) = n, and we let M ϱ n d n denote the set of of all those bipartite maps with boundary-length 2ϱ n and n inner faces, amongst which exactly k have degree 2k for every k 1; see Figure for an example.

One can easily check that any such map has υ n ϱ n + k 1 kd n (k) edges, and so d n (0) + 1 υ n -n + 1 vertices by Euler's formula. Then for every n 1, the set M ϱ n d n is nite and non-empty, and its cardinal is precisely given by #M

ϱ n d n = 2ϱ n (υ n -1)! (d n (0) + 1)! 2ϱ n -1 ϱ n -1 k 1 1 d n (k)! 2k -1 k -1 d n (k ) .
This can be derived from the 'slicing formula' of Tutte [Tut ], but it is also an easy consequence of the bijective method we shall use which relates planar maps and labelled forests. A key quantity in this work is

σ 2 n k 1 k(k -1)d n (k),
which is a sort of global variance term. We sample M ϱ n

d n uniformly at random in M ϱ n d n and consider its asymptotic behaviour as n → ∞. A particular, well-studied case of such random maps are so-called random quadrangulations and more generally 2p-angulations, with any p 2 xed, where all faces have degree 2p, which corresponds to our model in which d n (p) = n so σ 2 n = p(p -1)n. Another well-studied model is that of Boltzmann planar maps introduced by Marckert and Miermont [MM ], which can be seen as a mixture of our model in which the face-degrees d n are random and then one samples M (d n ) n 1 = (1, 2, 1, 1, 0, 0, . . . ) face-degree sequence; faces are labelled by their degree.

. . Main result. -Roughly speaking, a map can be viewed as the topological gluing of polygons which forms a sphere; we are given n + 1 polygons whose half-number of sides is prescribed by d n and ϱ n , and we choose such a gluing uniformly at random. The simplest such model is ϱ n = 1 and d n (2) = n when all polygons are quadrangles, in which case it was rst shown by Chassaing & Schae er [CS ] that the diameter of a uniformly random quadrangulation with n faces scales like n 1/4 and converges in distribution after this scaling. Later, Le Gall [LG ] proved that the vertex-set of such random quadrangulations endowed with the graph distance multiplied by n -1/4 admits subsequential limits in the sense of the so-called Gromov-Hausdor topology, and this was extended by Bettinelli [Bet ] to quadrangulations with a boundary, when ϱ n is arbitrary. We prove that tightness is very general. In addition to the graph distance d gr on the vertex-set V (M

ϱ n d n ) of the map M ϱ n
d n , we also include the uniform probability measure p unif .

Theorem . Fix any sequence of boundary-lengths (ϱ n ) n 1 and any degree sequence (d n ) n 1 . From every increasing sequence of integers, one can extract a subsequence along which the sequence of metric measured spaces

V (M ϱ n d n ), (σ n + ϱ n ) -1/2 d gr , p unif n 1 converges in distribution in the sense of Gromov-Hausdor -Prokhorov.
Considering a map with a boundary seems arti cial since the result does not depend on the root-edge: we could add the face of degree 2ϱ n to the degree sequence d n and replace the factor

(σ n + ϱ n ) -1/2 by (σ n ) -1/2 , where (σ n ) 2 = σ 2 n + ϱ n (ϱ n -1)
. We chose to highlight the boundary in order to t in the existing literature.

Let us notice that, although we shall not prove it here, this statement is not void in the sense that we did not choose a scaling factor so large that the spaces degenerate to a single point. Indeed, it is easily shown that a face of degree, say, d, has diameter of order d 1/2 so we see that the diameter of the rescaled map is bounded away from zero whenever there exists a face (the outer face or an inner face) with degree of order σ n . If it is not the case, we shall prove in the companion paper [Mar] that these maps converge towards a universal non-degenerate limit called the Brownian map [MM , LG , Mie ].

In the paper [LG ], Le Gall proves tightness not only of random quadrangulations, but more generally of random 2p-angulations, with any p 2 xed, where all faces have degree 2p, which corresponds to our model in which d n (p) = n so σ 2 n = p(p -1)n. The preceding theorem enables us to let p depend on n: x any sequence (p n ) n 1 ∈ {2, 3, . . . } N and let M n,p n be a uniformly chosen random 2p n -angulation with n faces, then from every increasing sequence of integers, one can extract a subsequence along which the sequence of metric measured spaces

V (M n,p n ), (p n (p n -1)n) -1/4 d gr , p unif n 1
converges in distribution in the sense of Gromov-Hausdor -Prokhorov. Le Gall [LG ] and Miermont [Mie ] proved that, for random 2p-angulations, the subsequential limits agree and these maps converge to the aforementioned Brownian map. More recently Bettinelli and Miermont [BM ] extended this convergence to maps with a boundary, in which case the limit is called a Brownian disk. In the companion paper [Mar] we shall obtain the convergence of our general model of random maps towards such limits (as well as the Brownian Continuum Random Tree of Aldous [Ald ] in a so-called 'condensation' phenomenon) under appropriate assumption on the degree sequence. As a particular case, we shall see there that 2p n -angulations always converge to the Brownian map.

. . Strategy of the proof and further discussion. -We study planar maps via a bijection with labelled forests obtained by combining the works [BDFG , JS ] where each vertex in the forest is assigned a random number in Z in a particular way (see Section ). The graph distance on the map can be partially encoded by the label process which encodes the labels of the forest, and we prove that this process is tight when suitably rescaled, see Theorem . This tightness relies only on the so-called Łukasiewicz path of the forest, which is a very simple process: up to a discrete Vervaat's transform (also known as cyclic lemma), the latter is a uniformly random path which makes d n (k) jumps of size k -1 for each k 0. This is the simplest example of a random path with exchangeable increments and its asymptotic behaviour is well-understood. We stress that tightness of the label process does not require the contour of height process to be tight. As a matter of fact, the latter are not tight in full generality! Going from tightness of the label process to tightness of the map as in Theorem is then very standard in the theory.

Theorem does not say anything about the subsequential limits. In the companion paper [Mar] we shall focus on Brownian limits such maps: we nd optimal assumptions on the degrees for the rescaled maps to converge towards the Brownian map, the Brownian disks, and even towards the Brownian CRT. Thanks to the results from this present work, it 'only' su ces to characterise the subsequential limits via the convergence of the nite-dimensional marginals of the label process.

In Section , we rst recall the de nition of plane forests and their encoding by paths, then we gather a few results about the Łukasiewicz path of the random forests associated with our random maps. Then in Section , we prove a new spinal decomposition which describes the behaviour of the ancestral lines of randomly chosen vertices; this result shall be used in the proof of tightness of the label process and it is one of the key ingredients to study its nite-dimensional marginals in [Mar]. Finally, in Section , we recall the bijection between planar maps and labelled forests, we then state and prove tightness of the label process in Theorem , before deducing Theorem .

Acknowledgement. -Many, many, thanks to Igor Kortchemski who spotted an important error in a rst draft.

. Preliminaries on forests and Łukasiewicz paths . . Plane forests and discrete paths. -We view (plane) trees as words: let N = {1, 2, . . . } and set N 0 = { }, then a tree is a non-empty subset T ⊂ n 0 N n such that: ∈ T , it is called the root of T , and for every x = (x 1 , . . . , x n ) ∈ T , we have pr (x) (x 1 , . . . , x n-1 ) ∈ T and there exists an integer k x 0 such that xi (x 1 , . . . , x n , i) ∈ T if and only if 1 i k x . We interpret the vertices of a tree T as individuals in a population. For every x = (x 1 , . . . , x n ) ∈ T , the vertex pr (x) is its parent, k x is the number of children of x (if k x = 0, then x is called a leaf, otherwise, x is called an internal vertex), and |x | = n is its generation; nally, we let χ x ∈ {1, . . . , k pr (x ) } be the only index such that x = pr (x)χ x , which is the relative position of x amongst its siblings. We shall denote by x, the unique geodesic path between x and .

Fix a tree T with υ n + 1 vertices, listed = x 0 < x 1 < • • • < x υ n in lexicographical order. It is well-known that T is described by each of the following two discrete paths. 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 x j -1.
One easily checks that W (j) 0 for every 0 j υ n but W (υ n + 1) = -1. Next, the height process H = (H (j); 0 j υ n ) is de ned by setting for every 0 j υ n ,

H (j) = |x j |.
Without further notice, throughout this work, every Łukasiewicz path shall be viewed as a step function, jumping at integer times, whereas the height processes shall be viewed as continuous functions after interpolating linearly between integer times.

A (plane) forest is a nite ordered list of plane trees, which we may view as a single tree by linking all the roots to an extra root-vertex; to be consistent, we also perform this operation when the forest originally consists of a single tree. Then we may de ne the Łukasiewicz path, height and contour processes of a forest as the paths describing the corresponding tree. In this case, the rst jump of the Łukasiewicz path is given by the number of trees minus one, say, ϱ -1, and then the path terminates by hitting -1 for the rst time. This rst possibly large jump is uncomfortable and we prefer instead cancelling it so the Łukasiewicz path starts at 0, makes a rst 0 step, and it terminates by hitting -ϱ for the rst time. We refer to Figure for an illustration. 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 [LG ] for a thorough discussion of such results). In order to simplify the notation, we shall identify the vertices of a tree with their index in the lexicographic order: if x is the i-th vertex of a tree T whose Łukasiewicz path is W , then we write W (x) for W (i).

Lemma . Let T be a plane tree and W be its Łukasiewicz path. Fix a vertex x ∈ T , then

W (xk x ) = W (x), W (x j ) = inf [x j,x j ]
W , and jj = W (x j) -W (x j )

for every 1 j j k x .

For any vertex x of a tree T , let R(x) be the number those vertices > x whose parent is a strict ancestor of x, and let L(x) be the number those vertices < x whose parent is a strict ancestor of x and which themselves are not. In other words, R(x) and L(x) count respectively the number of vertices branching-o of the ancestral line , x , those on the left for L(x) and those on the right for R(x) (and not x itself). We put LR(x) = L(x) + R(x). Then a consequence of this lemma is that, in a tree, we have R(x) = W (x). In the case of a forest, we de ne L(x) and R(x) (and so LR(x)) as the same quantities in the tree containing x, i.e. we really do want to view the forest as a forest and not as a tree, and then we have more generally

R(x) = W (x) -min 0 x W ( ). For example, if x is the vertex number in Figure , then R(x) = W (8) -min 0 i 8 W (i) = 2
, which corresponds to the vertices and : we do not count the -th one.

. . The Łukasiewicz path of a random forest as a cyclicly shifted bridge. -We consider random forest built as follows. Recall the notation from introduction; for every integer n, we consider the degree sequence

d n = (d n (k)) k 0 ∈ Z Z + + and let T ϱ n
d n be the set of all those plane forests with

ϱ n = k 0 (1 -k)d n (k) trees and υ n = k 0 d n (k) vertices, amongst which d n (k) have k children for every k 0; for a single tree, we simply write T d n for T 1 d n .
It is well-known (see e.g. [Pit , Chapter . ]) that the cardinal of this set is given by #T

ϱ n d n = ϱ n υ n υ n (d n (k)) k 0 = ϱ n (υ n -1)! k 0 d n (k)! . We sample T ϱ n d n uniformly at random in T ϱ n
d n and consider its asymptotic behaviour as n → ∞. Recall the notation σ

2 n = k 1 k(k -1)d n (k) which is sort of global variance of the o spring distribution. Let us also denote by ∆ n max{k 0 : d n (k) > 0}
the largest o spring of the forest and by

ϵ n k 1 kd n (k) = υ n -ϱ n
the number of edges of the forest (viewed as a forest).

The key to understand the behaviour of the Łukasiewicz path W

ϱ n d n of our random forest T ϱ n
d n is the well-known representation as a cyclic shift of a bridge, also called the discrete Vervaat's transform, see e.g. Pitman [Pit , Chapter ] for details. Fix two integers m, ϱ 1 and a vector b

= (b 1 , . . . , b m ) ∈ {-1, 0, 1, 2, . . . } m such that b 1 + • • • + b m = -ϱ. For any i, j ∈ {1, . . . , m}, we put b i j = b i+j , where the sum is understood modulo m. The sequence b i is called the i-th cyclic shift of b. Clearly, we have b i 1 + • • • +b i m = -ϱ for every i. Let I = inf 1 m b 1 + • • • +b , then the following properties are equivalent: (i) b i 1 + • • • + b i k 1 -ϱ for every 1 k m -1, (ii) there exists p ∈ {0, . . . , ϱ -1} such that i = inf {k ∈ {1, . . . , m} : b 1 + • • • + b k = I + p}.
In words, the path obtained by summing successively the b j 's is a bridge started from 0 and ending at -ϱ, and there is exactly ϱ ways to cyclicly shift it to turn it to a rst-passage bridge. In the case ϱ = 1, we have p = 0 so i is simply the left-most argmin of the bridge. Let B

ϱ n d n = (B ϱ n d n (k)) 0 k υ n
be a discrete path sampled uniformly at random amongst all those started from B ϱ n d n (0) = 0 and which make exactly d n ( ) jumps with value -1 for every 0, so B

ϱ n d n is a bridge from 0 to B ϱ n d n (υ n ) = 0 ( -1)d n ( ) = -ϱ n .
Independently, sample p n uniformly at random in {0, . . . , ϱ n -1} and set

i n = inf k ∈ {1, . . . , υ n } : B ϱ n d n (k) = p n + inf 1 υ n B ϱ n d n ( ) .
Then according to the preceding discussion, W

ϱ n d n has the law of (B ϱ n d n (i n + k) -B ϱ n d n (i n )) 1 k υ n ,
where again the sum is understood modulo υ n . Moreover, one can check that i n has the uniform distribution on {1, . . . , υ n } and is independent of the cyclicly shifted path.

The fact that all the jumps of the random bridge B ϱ n d n are larger than or equal to -1 leads to exponential decay of the negative tails. Indeed, the arguments developed by Addario-Berry [AB , Section ] in the case ϱ n = 1 are easily extended to show that the 'remaining sequence' (remaining space divided by the remaining time)

-ϱ n -B ϱ n d n (i) υ n -i 0 i υ n -1 is a martingale for the natural ltration (F i ) 0 i υ n -1 , started from -ϱ n /υ n , which satis es furthermore that for every 0 i υ n -2, - B ϱ n d n (i + 1) + ϱ n υ n -(i + 1) + B ϱ n d n (i) + ϱ n υ n -i υ n (υ n -(i + 1)) 2 , and Var B ϱ n d n (i + 1) + ϱ n υ n -(i + 1) F i σ 2 n (υ n -(i + 1)) 3 .
Then the martingale Cherno -type bound, see e.g. McDiarmid [McD ], Theorem . and the remark at the end of Section . there, claims that for every z 0 and every 1 k υ n -1,

P min i k B ϱ n d n (i) + ϱ n υ n -i - ϱ n υ n -z exp - z 2 2 k σ 2 n (υ n -k ) 3 + 2 3 z υ n (υ n -k ) 2 exp - (υ n -k) 3 z 2 2kσ 2 n + υ 2 n z
.

Observe that

B ϱn dn (i)+ϱ n υ n -i - ϱ n υ n = B ϱn dn (i)+iϱ n /υ n υ n -i
so for every z 0 and every 1 k υ n -1,

P min i k B ϱ n d n (i) + iϱ n υ n -z P min i k B ϱ n d n (i) + iϱ n /υ n υ n -i - z υ n exp - (υ n -k) 3 z 2 /υ 2 n 2kσ 2 n + υ n z . Finally, since B ϱ n d n (i) + iϱ n /υ n B ϱ n d n (i) + kϱ n /υ n when i k, taking k = αυ n with α ∈ (0, 1)
, we have for every z 0,

P min i αυ n B ϱ n d n (i) + αϱ n -σ n z exp - (υ n -αυ n ) 3 (σ n z) 2 /υ 2 n 2αυ n σ 2 n + υ n σ n z exp - (1 -α) 3 σ n z 2 2ασ n + z . ( )
In the next two subsections we apply this tail bound to derive precious information about the Łukasiewicz path.

. . Further results. -When dealing with forests, vertices with out-degree 1 play an important role and removing them may drastically change the geometry. On the other hand, when dealing with planar maps, these correspond to faces of degree 2 which play no role in the geometry: precisely, if one glues together the two edges of every face of degree 2, then one does not a ect the number of vertices nor their graph distance, so the metric measured space induced by the map stays unchanged. The point is that a forest in which the proportion of vertices with out-degree 1 is bounded is easier to study. For example, assume that d n (1) (1 -δ )ϵ n for some δ ∈ (0, 1), then we have

σ 2 n = k 2 k(k -1)d n (k) k 2 kd n (k) = ϵ n -d n (1) δϵ n ,
and similarly

d n (0) = ϱ n + k 2 (k -1)d n (k) ϱ n + k 2 k 2 d n (k) ϱ n + δ 2 ϵ n δ 2 υ n .
Proposition . Fix δ ∈ (0, 1). For every n ∈ N, every degree sequence d n such that d n (1) (1 -δ )ϵ n , every 0 s < t 1 with |t -s | 1/2, and every x > 0, it holds that

P W ϱ n d n (υ n s) -min s r t W ϱ n d n (υ n r ) -ϱ n |t -s | > σ n |t -s | 1/2 x 2 exp - x 2 16(2 + δ -1 )
.

Consequently, for every p ∈ N, there exists C(p) > 0 such that the bound

E W ϱ n d n (υ n s) -min s r t W ϱ n d n (υ n r ) p C(p) • (σ n + ϱ n ) p • |t -s | p/2 , holds uniformly for 0 s < t 1 with |t -s | 1/2.
Proof. Note that in ( ), since min i αυ n B ϱ n d n (i) -αυ n , we may assume that σ n z α(υ n -ϱ n ). From the preceding discussion, under our assumption the latter equals αϵ n αδ -1 σ 2 n , whence

P min i αυ n B ϱ n d n (i) + αϱ n -σ n z exp - (1 -α) 3 σ n z 2 2ασ n + αδ -1 σ n = exp - (1 -α) 3 z 2 α(2 + δ -1 ) ,
for all z > 0. Therefore, if α 1/2, we have

P min i αυ n B ϱ n d n (i) + αϱ n -σ n α 1/2 z exp - z 2 8(2 + δ -1 )
, for all z > 0. By exchangeability, we have for any 0

s < t 1 xed with |t -s | 1/2, P B ϱ n d n (υ n s) -min s r t B ϱ n d n (υ n r ) -ϱ n |t -s | > σ n |t -s | 1/2 z exp - z 2 8(2 + δ -1 )
.

We then transfer this bound to W

υ n t + i n -υ n . Using that for every a, b 0, we have (a + b) 1/2 2 -1/2 (a 1/2 + b 1/2 ), we then obtain that in this case, since |t -s | = |1 -(s + i n υ n )| + |t + i n υ n -1|, P W ϱ n d n (υ n s) -min s r t W ϱ n d n (υ n r ) -ϱ n |t -s | > σ n |t -s | 1/2 z P B ϱ n d n (υ n s + i n ) - min υ n s+i n k υ n B ϱ n d n (k) -ϱ n 1 -s + i n υ n > σ n 1 -s + i n υ n 1/2 z 2 1/2 + P - min 0 k υ n t +i n -υ n B ϱ n d n (k) -ϱ n t + i n υ n -1 > σ n t + i n υ n -1 1/2 z 2 1/2 2 exp - z 2 16(2 + δ -1 )
.

Finally, by integrating this tail bound applied to z 1/p , we obtain

E W ϱ n d n (υ n s) -min s r t W ϱ n d n (υ n r ) -ϱ n |t -s | σ n |t -s | 1/2 p ∫ ∞ 0 2 exp - z 2/p 16(2 + δ -1 ) dz c(p). Since a p + b p (a + b) p 2 p-1 (a p + b p ) for every a, b 0, we conclude that E W ϱ n d n (υ n s) -min s r t W ϱ n d n (υ n r ) p 2 p-1 E W ϱ n d n (υ n s) -min s r t W ϱ n d n (υ n r ) -ϱ n |t -s | p + (ϱ n |t -s |) p 2 p-1 σ p n |t -s | p/2 c(p) + ϱ p n |t -s | p/2 2 p-1 (c(p) + 1) (σ n + ϱ n ) p |t -s | p/2 ,
and the proof is complete.

The next result states that vertices with a given out-degree are homogeneously spread in the forest. For a subset A ⊂ Z -1 = {-1, 0, 1, 2, . . . } and a real r ∈ [0, υ n ], let Λ A (r ;W

d n ) = inf {r : Λ A (r ;W ϱ n d n ) = p } for all real p 1. Let us set d n (A + 1) = k ∈A d n (k + 1).
Lemma . Fix any subset A ⊂ Z -1 . If d n (A + 1) → ∞, then we have the convergence in probability

Λ A (υ n t;W ϱ n d n ) d n (A + 1) , ζ A (d n (A + 1)t;W ϱ n d n ) υ n t ∈[0,1] P -→ n→∞ (t, t) t ∈[0,1] .
We shall apply this result to A = {-1} at the very end of this paper. Note that since the two functions are inverse of one another and non-decreasing, the two convergences are equivalent.

Proof. Let us rst prove the similar convergence when the Łukasiewicz path W

ϱ n d n is replaced by the bridge B ϱ n d n . Fix ε > 0, then P max i d n (A+1) ζ A (i; B ϱ n d n ) υ n - i d n (A + 1) > ε i d n (A+1) P ζ A (i; B ϱ n d n ) -i υ n d n (A + 1) > ευ n . Let us set Λ A (k; B ϱ n d n ) = d n (A + 1) if k υ n and Λ A (k; B ϱ n d n ) = 0 if k 0. Note that ζ A (i; B ϱ n d n ) > k if and only if Λ A (k; B ϱ n d n ) > i, so the right-hand side above is bounded by i d n (A+1) P Λ A i υ n d n (A + 1) + ευ n ; B ϱ n d n i + P Λ A i υ n d n (A + 1) -ευ n ; B ϱ n d n i d n (A + 1) • P ∃j υ n : Λ A j; B ϱ n d n (j -ευ n ) d n (A + 1) υ n + d n (A + 1) • P ∃j υ n : Λ A j; B ϱ n d n (j + ευ n ) d n (A + 1) υ n 2d n (A + 1) • P max j υ n Λ A j; B ϱ n d n -j d n (A + 1) υ n εd n (A + 1) .
The quantity Λ a (j;

B ϱ n d n )
is the sum of dependent Bernoulli random variables: we start with an urn containing υ n balls in total, amongst which d n (A+1) are labelled A, we sample j balls without replacement and count the number of balls labelled A picked. The Cherno bound applies in the same way it does with i.i.d. Bernoulli coming from sampling with replacement (this is arleady shown in Hoe ding's seminal paper [Hoe , Theorem ]) so for every ε > 0, it holds that

P max j υ n Λ A (j; B ϱ n d n ) -j d n (A + 1) υ n > εd n (A + 1) 2 exp - ε 2 d n (A + 1) 2 + 2ε/3 .
We conclude that

P max i d n (A+1) ζ A (i; B ϱ n d n ) υ n - i d n (A + 1) > ε 4d n (A + 1) exp - ε 2 d n (A + 1) 2 + 2ε/3 ,
which converges to 0 since we assume that d n (A + 1) → ∞. This shows that

ζ A (d n (A + 1)t; B ϱ n d n ) υ n t ∈[0,1] and Λ A (υ n t; B ϱ n d n ) d n (A + 1) t ∈[0,1] ,
both converge in probability to the identity.

In order to transfer these bounds from the bridge B . . Tail bounds for the width of a single tree. -The results of this subsection will not be used here but in the companion paper [Mar]; the discussion also shows that the behaviour of the random forests T ϱ n d n is more complicated than the random maps M ϱ n d n . Indeed, we claim in Theorem that the latter are always tight, but as we discuss below, even in the case of a single tree, this is not the case of T ϱ n d n in full generality.

Proposition . Suppose that ∆ n 2. Let x n be a uniformly random vertex of T

ϱ n d n , then P (LR(x n ) zσ n ) 4 exp - z 288
uniformly in z 1/2 and n ∈ N.

Proof. Recall that LR(x n ) = L(x n ) + R(x n ) denotes
x n ) = W ϱ n d n (x n ) -min 0 x n W ϱ n d n ( ).
Recall also that W

W ϱ n d n (υ n -i n ) -min 0 j υ n -i n W ϱ n d n (j) = B ϱ n d n (υ n ) -min 0 j υ n B ϱ n d n (j) = -ϱ n -min 0 j υ n B ϱ n d n (j).
Note that υ n -i n is uniformly distributed in {0, . . . , υ n -1} and is independent of W ϱ n d n , whereas x n is the vertex visited at a random time uniformly distributed in {1, . . . , υ n } and independently of W

ϱ n d n . Since W ϱ n d n (0) -min 0 j 0 W ϱ n d n (j) = W ϱ n d n (υ n ) -min 0 j υ n W ϱ n
d n (j) = 0, we have that R(x n ) has the same law as -ϱ nmin 0 j υ n B ϱ n d n (j). Let us next observe the following bound

-ϱ n -min 0 j υ n B ϱ n d n (j) - ϱ n 2 -min 0 j υ n /2 B ϱ n d n (j) + - ϱ n 2 -min υ n /2 j υ n B ϱ n d n (j) + B ϱ n d n υ n 2 ,
and the two terms on the right have the same law. From our assumption, we have σ 2 n ∆(∆ n -1) 1 so by ( ), for every z 1/4 we have after two union bounds

P (LR(x n ) zσ n ) 4 • P min 0 j υ n /2 B ϱ n d n (j) + ϱ n 2 - zσ n 4 4 exp - 2 -3 σ n (z/4) 2 σ n + z/4 .
Since both z 1 2 and σ n 1, we have that σ n + z 4 9 4 σ n z, which yields the bound in our claim.

Let us next focus on the case of a single tree ϱ n = 1. Let us denote by wid(T d n ) the maximum over all i 1 of the number of vertices of T d n at distance i from the root, called the width of T d n , and by ht(T d n ) the greatest i 1 such that there exists at least one vertex of T d n at distance i from the root, called the height of T d n . the preceding result gives a universal tail bound on the rst quantity.

Corollary . For every n ∈ N, for every degree sequence d n such that ∆ n 2, we have for every z 1:

P wid(T d n ) zσ n 3e -z/48 .
This tail bound slightly improves, when the forests are long and thin, on the one obtained by Addario-Berry [AB ] for a single tree which considered the larger scaling factor given by the Euclidian norm of the degrees

( k 1 k 2 d n (k)) 1/2 = (σ 2 n + ϵ n ) 1/2 .
The proof in [AB ] (see also [Kor , Theorem ]) is a direct application of Theorem there; Equation there does not depend on the degrees, and Equation may be replaced by the bound

P min 0 j υ n /2 B d n (j) + 1 2 -zσ n exp - z 16 ,
for all z 1, which follows from ( ) as in the preceding proof, which yields our corollary. Thanks to the simple observation that wid(T d n ) × ht(T d n ) ϵ n , we obtain the lower bound

P ht(T d n ) ϵ n /(zσ n ) 3e -z/48 ,
for all z 1. Following [AB ] we may also obtain

P ht(T d n ) zσ n c 1 e -c 2 z , ( )
for some constants c 1 , c 2 > 0, but the scalings σ n and ϵ n /σ n are of the same order only in a ' nitevariance' regime, when σ n is of order ϵ 1/2 n , otherwise the former is larger than the latter. We stress that an upper-bound at the scaling ϵ n /σ n in full generality is not possible. As a matter of fact, the height of the tree may be much larger than ϵ n /σ n as it is the case for subcritical size-conditioned Bienaymé-Galton-Watson trees, for which ϵ n /σ n is of constant order, but the height grows like log ϵ n , see Kortchemski [Kor ]. Nonetheless, the scaling ϵ n /σ n is correct for typical vertices, see Proposition below.

. A spinal decomposition

We describe in this section the ancestral lines of i.d.d. random vertices of T ϱ n d n . A related result on trees was rst obtained by Broutin & Marckert [BM ] for a single random vertex and it was extended in [Mar c] to several vertices. This present one is di erent, we shall compare them after the statement.

Suppose that an urn contains initially kd n (k) balls labelled k for every k 1, so ϵ n balls in total; let us pick balls repeatedly one after the other without replacement; for every 1 i ϵ n , we denote the label of the i-th ball by ξ d n (i). Conditional on (ξ d n (i)) 1 i ϵ n , let us sample independent random variables (χ d n (i)) 1 i ϵ n such that each χ d n (i) is uniformly distributed in {1, . . . , ξ d n (i)}. We shall use the fact that the ξ d n (i)'s are identically distributed, with

E ξ d n (i) -1 = k 1 (k -1) kd n (k) ϵ n = σ 2 n ϵ n and so Var ξ d n (i) -1 ∆ n σ 2 n ϵ n . ( )
Let us x a plane forest F , viewed as a forest and not a tree. Recall that we denote by χ x the relative position of a vertex x amongst its siblings; for every 0 i |x |, let us also denote by a i (x) the ancestor of x at height i, so a |x | (x) = x and a 0 (x) is the root of the tree containing x. De ne next for every vertex x the content of the branch a 0 (x), x as

Cont(x) = k a i -1 (x ) , χ a i (x ) ; 1 i |x | . ( )
In words, Cont(x) lists the number of children of each strict ancestor of x and the position of the next ancestor amongst these children. More generally, let x 1 , . . . , x q be q vertices of F and let us consider the forest F reduced to its root and these vertices: F (x 1 , . . . , x q ) contains only the vertices x 1 , . . . , x q and their ancestors, and it naturally inherits a plane forest structure from F ; let us further remove all the vertices with at least two children in this forest to produce F (x 1 , . . . , x q ) which is a collection of single branches, and let Cont(x 1 , . . . , x q ) be the sequence of the pairs (k pr ( ) , χ ) where ranges over F (x 1 , . . . , x q ) in lexicographical order, and where the quantities k pr ( ) and χ are those in the original forest F .

Lemma . Fix n ∈ N and d n a degree sequence such that ∆ n 2. Let q 1 and sample x n,1 , . . . , x n,q independently uniformly at random in T ϱ n d n . Let (k i , j i ) 1 i h be positive integers such that 1 j i k i for each i. If q 2, assume that h, q υ n /4. Then for every integers 0 b q -1 and 1 c q, the probability that Cont(x n,1 , . . . , x n,q ) = (k i , j i ) 1 i h , and that the reduced forest T ϱ n d n (x n,1 , . . . , x n,q ) possesses c trees, q leaves, and b branch-points is bounded above by

q 2 2 q-1 σ n υ n q+b ϱ n σ n c-1 ϱ n + (q -1)∆ n + 1 i h (k i -1) σ n • P i h (ξ d n (i), χ d n (i)) = (k i , j i ) .
Note that the reduced forest T ϱ n d n (x n,1 , . . . , x n,q ) possesses q leaves when no x n,i is an ancestor of another; we shall see below that the height of a random vertex is at most of order ϵ n /σ n , so indeed with high probability no x n,i is an ancestor of another as soon as σ n → ∞. Also, if the forest has b branch-points, then q + b denotes the number of branches once we remove these branch-points; these branches typically have length of order ϵ n /σ n , so the factor (σ n /υ n ) q+b is important. The other factors will be typically bounded in our applications.

In words, roughly speaking, along distinguished paths (removing the branch-points), up to a multiplicative factor, the individuals reproduce according to the size-biased law (kd n (k)) k 1 , and conditional on the o springs, the paths continue via one of the children chosen uniformly at random. Note that these size-biased picks are not independent, since we are sampling without replacement. In the case of a single tree ϱ n = 1, an analogous result when sampling with replacement was obtained by Broutin & Marckert [BM ] for a single random vertex and it was extended in [Mar c] to several vertices. The signi cant di erence is that when comparing to sampling with replacement, an extra factor of order e h 2 /ϵ n appears in the bound, and one cannot remove it. This was not an issue in [BM , Mar c] which focus on the ' nite-variance regime', when σ 2 n is of order ϵ n since then the bound ( ) on the height ensures that it does not explode but this is not the case here. Moreover, we feel that sampling without replacement is more natural in this model.

We stress that the fact that the random variables ξ d n (i) are sampled without replacement is not a technical issue. As a matter of fact, it is known, see e.g. [Ald , Proposition . ], that these are more concentrated than their version sampled with replacement ξ * d n (i) in the sense that for any integer h and any convex function f , it holds that

E[f ( 1 i h ξ d n (i))] E[f ( 1 i h ξ * d n (i))].
Therefore, the Markov inequality and any Cherno -type bound based on controlling the Laplace transform applies to the ξ d n (i)'s in the same way it applies to the ξ * d n (i)'s.

. . Proof of the one-point decomposition. -Let us rst consider the simpler case of a single random vertex. In this case, we have b = 0 and c = 1 so the upper bound reads simply

ϱ n + 1 i h (k i -1) υ n • P i h (ξ d n (i), χ d n (i)) = (k i , j i ) . ( )
Proof of Lemma for q = 1. The proof relies on the fact that there is a one-to-one correspondence between a plane forest with ϱ trees and a distinguished vertex x on the one hand, and on the other hand the triplet given by the knowledge of which of the ϱ trees contains x, the vector Cont(x), and the plane forest obtained by removing all the strict ancestors of x; note that this forest contains ϱ + 0 i < |x | (k a i (x ) -1) trees. Recall that for any sequence θ = (θ ) 0 of non-negative integers with nite sum |θ |, the number of plane forests having exactly θ vertices with children for every 0 is given by

#F(θ ) = r |θ | |θ | (θ ) 0 ,
where r = 0 (1 -)θ is the number of roots. Fix (k i , j i ) 1 i h a sequence of positive integers such that 1 j i k i for each i. For every 1, let m = #{1 i h : k i = } and assume that m d n ( ); let also m 0 = 0 and m = (m ) 0 . By the preceding bijection, if x n is a vertex chosen uniformly at random, then we have

P (Cont(x n ) = (k i , j i ) 1 i h ) = ϱ n #F(d n -m) υ n #F(d n ) = ϱ n ϱ n + 1 i h (k i -1) υ n -h υ n -h (d n ( )-m ) 0 υ n ϱ n υ n υ n (d n ( )) 0 = ϱ n + 1 i h (k i -1) υ n -h (υ n -h)! υ n ! 1 d n ( )! (d n ( ) -m )! .
Let us set

P((k i , j i ) i h ) = P i h (ξ d n (i), χ d n (i)) = (k i , j i ) = 1 -m ( d n ( ))( d n ( ) -1) • • • ( d n ( ) -m + 1) ϵ n (ϵ n -1) • • • (ϵ n -h + 1) = (ϵ n -h)! ϵ n ! 1 -m ( d n ( ))! ( d n ( ) -m )!
.

Then, we have

P (Cont(u n ) = (k i , j i ) 1 i h ) = ϱ n + 1 i h (k i -1) υ n -h (υ n -h)! υ n ! ϵ n ! (ϵ n -h)! 1 m d n ( )!( d n ( ) -m )! (d n ( ) -m )!( d n ( ))! P((k i , j i ) i h ).
Observe that υ n ϵ n + 1, so

(υ n -h)! υ n ! ϵ n ! (ϵ n -h)! = υ n -h υ n h-1 i=0 ϵ n -i υ n -1 -i υ n -h υ n . Moreover, we claim that m d n ( )!( d n ( )-m )! (d n ( )-m )!( d n ( ))!
1 for every 1. Indeed, it equals 1 when = 1; we suppose next that 2, so in particular m d n ( ) d n ( )/2. It is simple to check that for every x ∈ [0, 1/2], we have (1 -x) -1 2 2x , and for every x ∈ [0, 1], we have 1 -x 2 -x . It follows that for every 2 such that d n ( ) 0,

m d n ( )!( d n ( ) -m )! (d n ( ) -m )!( d n ( ))! = d n ( )! (d n ( ) -m )!d n ( ) m ( d n ( ) -m )!( d n ( )) m ( d n ( ))! = m -1 i=0 d n ( ) -i d n ( ) d n ( ) d n ( ) -i m -1 i=0 exp ln 2 - i d n ( ) + 2i d n ( ) ,
which is indeed bounded by 1 for 2. This concludes the proof in the case q = 1.

. . Proof of the multi-point decomposition. -We next turn to the proof in the general case; the di erence is that one has to deal with the branch-points of the reduced forest, which, we recall, are not considered in the vector of content.

Proof of Lemma for q 2. Fix q 2 and sample x n,1 , . . . , x n,q i.i.d. uniformly random vertices in T

ϱ n d n .
As in the case q = 1, there is a one-to-one correspondence between the plane forest T ϱ n d n and x n,1 , . . . , x n,q on the one hand, and on the other hand the plane forest obtained by removing T ϱ n d n (x n,1 , . . . , x n,q ) from the whole forest T ϱ n d n , the vector Cont(x n,1 , . . . , x n,q ), and the following data: rst the number c of trees containing at least one of the x n,i 's and the knowledge of which ones, second for each of the b branch-points: their total number r of children in T d n (x n,1 , . . . , x n,q ), and the relative positions z i 's of these children.

Therefore, x (k i , j i ) 1 i h , also c ∈ {1, . . . , q}, b ∈ {0, . . . , q -1}, and for every p ∈ {1, . . . , b}, x r (p) d(p) 2 and integers 1 z p,1 < • • • < z p,d (p) r (p), and let us consider the following event:

rst Cont(x n,1 , . . . , x n,q ) = (k i , j i ) 1 i h , second, in the forest spanned by x n,1 , . . . , x n,q , we have c trees, b branch-points, for every p b, the p-th branch-point in lexicographical order has r (p) children in total in the original forest T ϱ n d n , amongst which d(p) belong to the reduced forest, and the relative positions of the latter are given by the z p,i 's. If we set m 0 = 0 and for every 1, we let m = #{1 i h : k i = } and m = m + 1 p b 1 {r (p)= } , then on this event, the complement of the reduced forest is a forest with degree sequence (d n ( )-m ) 0 ; note that it contains R = ϱ n -c +q + 1 p b (r (p)-d(p))+ 1 i h (k i -1) trees and υ n -hb vertices. Therefore the probability of our event is given by

ϱ n c #F(d n -m) υ q n #F(d n ) = ϱ n c R υ n -h-b υ n -h-b (d n ( )-m ) 0 υ q n ϱ n υ n υ n (d n ( )) 0
. . Labelled trees and pointed maps. -For every k 1, let us consider the following set of discrete bridges

B -1 k = {(b 1 , . . . , b k ) : b 1 , b 2 -b 1 , . . . , b k -b k-1 ∈ {-1, 0, 1, 2, . . . } and b k = 0} .
Then a labelling of a plane tree T is a function from the vertices of T to Z which satis es that (i) the root of T has label ( ) = 0, (ii) for every vertex x with k x 1 children, the sequence of increments ( (x1)-(x), . . . , (xk x )-(x))

belongs to B -1 k x .

We encode then the labels into the label process L(k) = (x k ), where x k is the k-th vertex of T is lexicographical order; the labelled tree is encoded by the pair (H , L). We extend the de nition to forests by considering the associated tree, see Figure . ) is a pointed map, let us denote by e + and e -the extremities of the root-edge, so that d gr (e -, ) = d gr (e + , ) -1, where d gr refers to the graph distance; the root-edge is oriented either from e -to e + , in which case the map is said to be positive by Marckert & Miermont [MM ], or it is oriented either from e + to e -, in which case the map is said to be negative.

Let us immediately note that since every map in M d n is positive, we may re-root it to get a negative map. Therefore it is equivalent to work with random negative maps in PM

ϱ n d n instead of maps in M ϱ n d n .
This case is simpler to handle; indeed, combining the bijections due to Bouttier, Di Francesco, & Guitter [BDFG ] and to Janson & Stefánsson [JS ], the set LT (i) The leaves of the forest are in one-to-one correspondence with the vertices di erent from the distinguished one in the map, and the label of a leaf minus the in mum over all labels, plus one, equals the graph distance between the corresponding vertex of the map and the distinguished vertex.

(ii) The internal vertices of the forest are in one to one correspondence with the inner faces of the map, and the out-degree of the vertex is half the degree of the face.

(iii) The root-face of the map corresponds to the extra root-vertex of the forest, and the out-degree of the latter is half the boundary-length of the map.

(iv) The number of edges of the map and the forest are equal.

The third property only holds for negative maps, which is the reason why we restricted ourselves to this case.

0 -1 -2 1 0 0 -1 -2 0 -1 1 0 0 0 -1 -2 -1 -3 0 -1 -2 1 0 0 -1 -2 0 -1 1 0 0 0 -1 -2 -1 -3 -1 -2 0 -2 0 -1 1 0 -1 -2 -1 Figure :
The pointed map associated with a labelled forest. Labels indicate, up a to a shi , the graph distance to the distinguished vertex, which is the one carrying the smallest label. The map is the one in Figure , seen from a di erent perspective.

. . Tightness of the label process. -The rst key step to understand the asymptotic behaviour of a random map in PM d n be the associated label process.

Theorem . Fix any sequence of boundary-lengths (ϱ n ) n 1 and any degree sequence (d n ) n 1 such that ∆ n 2 for every n 1 and lim sup n→∞ ϵ -1 n d n (1) < 1. Then from every increasing sequence of integers, one can extract a subsequence along which the label processes

(σ n + ϱ n ) -1/2 L ϱ n d n (υ n t) t ∈[0,1] converge in the space C([0, 1], R).
Let us discuss the assumption on d n (1) which is not present in Theorem . The point is that it corresponds to faces of degree 2 which play no role in the geometry of the map: one could just glue the two edges together for each such face and this would not change the number of vertices nor their distances. So, replacing the degree sequence by d n (k)1 {k 1} , we could assume that d n (1) = 0 in fact; we chose a weaker assumption which is easily veri ed in many interesting models, such as so-called size-conditioned critical stable Boltzmann maps. Such an assumption is needed when coding the map by a labelled forest. Indeed, these vertices with out-degree 1 induce at steps of the label process so one could think similarly that we could remove them harmlessly, but if lim n→∞ ϵ -1 n d n (1) = 1 and lim n→∞ υ -1 n ϱ n = 0, then we have in total υ n -d n (1) = o(υ n ) other vertices so this completely changes the time-scaling and it may induce jumps at the limit (for example if the number of vertices with out-degree 1 in a small portion of the tree is abnormally small).

Theorem extends [Mar c, Proposition ] which is restricted to the case of a single tree and in the nite-variance regime, when σ 2 n is of order υ n . Many arguments generalise here so shall only brie y recall them and focus on the main di erence. First, we shall need a technical result which extends [Mar c, Corollary ], a slight adaptation of the proof is needed here.

Lemma . Recall the notation χ z ∈ {1, . . . , k pr (z) } for the relative position of a vertex z ∈ T ϱ n d n amongst its siblings. Let

c n = 1 - d n (0) 2υ n and l n = 4υ n d n (0) 2 ln 4υ 3 n d n (0) ,
and consider the event

E n = #{z ∈ x, : χ z = 1} # x, c n whenever x is an ancestor of such that # x, > l n . Then P(E n ) → 1 as n → ∞.
In words, this means that in T ϱ n d n , there is no branch longer than l n along which the proportion of individuals which are the left-most (or right-most by symmetry) child of their parent is too large. Let us point out that when lim sup n→∞ ϵ -1 n d n (1) < 1, then we have seen in Section . that lim inf n→∞ υ -1 n d n (0) > 0, so this length l n is at most of order ln υ n and the proportion c n is bounded away from 1.

Proof. For a vertex x in the forest T

| -i + 1, so α 1 (x) is x itself, α 2 (x) is its parent, etc. Let us write E n = x ∈T ϱn dn l n l |x | l i=1 1 { χ α i (x ) =1} c n l . Let x n be a vertex sampled uniformly at random in T ϱ n d n ; a union bound yields P E c n υ n • P |x n | l =l n l i=1 1 { χ α i (xn ) =1} > c n l .
Appealing to Lemma , since the ratio in ( ) is bounded by 1, this is bounded above by

υ n h υ n h l =l n P l i=1 1 { χ dn (i)=1} > c n l . Let us set n = υ n -n 4υ n , so c n = 2 n + n υ n . Then a union bound yields P l i=1 1 { χ dn (i)=1} > c n l = P l i=1 1 { χ dn (i)=1} -l n υ n > 2 n l P l i=1 1 { χ dn (i)=1} - l i=1 1 ξ d n (i) > n l + P l i=1 1 ξ d n (i) -l n υ n > n l .
Note that each ξ d n (i) -1 takes values in [0, 1] and has mean

E ξ d n (i) -1 = k 1 k -1 kd n (k) υ n = n υ n .
If these variables were obtained by sampling with replacement, then we could apply a well-known concentration result, see e.g. [McD , Theorem . ] to obtain

P l i=1 ξ d n (i) -1 -l n υ n > n l exp -2 2 n l .
This remains true here since this concentration is obtained by controlling the Laplace transform of l i=1 ξ d n (i) -1 and the expectation of any convex function of this sum is bounded above by the corresponding expectation when sampling with replacement, see e.g. [Ald , Proposition . ]. Further, conditional on the ξ d n (i)'s, the variables 1 { χ dn (i)=1} are independent and Bernoulli distributed, with parameter ξ d n (i) -1 respectively, so we have similarly

P l i=1 1 { χ dn (i)=1} - l i=1 ξ d n (i) -1 > n l
exp -2 2 n l .

Since n ∈ (0, 1/2), it holds that 1exp(-2 2 n )

2 n , so we obtain

P E c n υ n h υ n h l =l n 2 exp -2 2 n l 2υ 2 n exp(-2 2 n l n ) 1 -exp(-2 2 n ) 2υ 2 n -2
n exp(-2 2 n l n ).

Finally, we have l n = -2 n ln( -1 n υ 2 n ), so P(E c n ) 2υ -2 n , which converges to 0.

We may now prove the tightness of the label process, relying on this result and Proposition .

Proof of Theorem . Let E n be the event from Lemma , whose probability tends to 1. We claim that for every q > 4, for every β ∈ (0, q/4 -1), there exists a constant C q > 0 such that for every n large enough, for every 0 s t 1, it holds that

E L ϱ n d n (υ n s) -L ϱ n d n (υ n t) q E n C q • (σ n + ϱ n ) q/2 • |t -s | 1+β .
The standard Kolmogorov criterion then implies that for every γ ∈ (0, 1/4), lim

K →∞ lim sup n→∞ P sup s t |L ϱ n d n (υ n s) -L ϱ n d n (υ n t)| (σ n + ϱ n ) q/2 • |t -s | γ > K E n = 0.
Then the same holds for the unconditioned probability and this implies the tightness as claimed.

We may, and do, suppose that υ n s and υ n t are integers and that |t -s | 1/2. Let us view T ϱ n d n as a tree, let x and be the vertices visited at time υ n s and υ n t respectively, and let x and ˆ be the children of their last common ancestor which are ancestor of x and respectively. Then it was argued in [Mar c] that E L

ϱ n d n (υ n s) -L ϱ n d n (υ n t) q T ϱ n d n C R( x, ˆ ) q/2 + (# ˆ , + L( ˆ , )) q/2 ,
where C > 0 is independent of n, s, and t, where R( x, ˆ ) counts the number of vertices visited strictly between x and ˆ and whose parent is a (strict) ancestor of x, and where L( ˆ , ) counts the number of vertices visited strictly between ˆ and , which are not (strict) ancestor of but whose parent is. We stress that, as opposed to Section . , we do view T ϱ n d n as a single tree here, so if x and belong to two di erent components of the forest, then x and ˆ are their respective roots and R( x, ˆ ) takes into account the other roots between them. From Lemma , one gets that R( x, ˆ ) = W C(q/2) • (σ n + ϱ n ) q/2 • |t -s | q/4 , Next, let us consider the branch from ˆ to ; under the event E n , if this branch has length greater than l n , then the proportion of individuals which are the rst child of their parent is at most c n ; all other vertices (a proportion at least 1 -c n ) contribute to L( ˆ , ) so there are at most L( ˆ , ) of them and therefore

(# ˆ , + L( ˆ , )) 1 E n c n 1 -c n + 1 L( ˆ , )1 {E n ∩{# ˆ , l n } } + (l n + L( ˆ , )) 1 {E n ∩{# ˆ , <l n } } l n + c n 1 -c n + 2 L( ˆ , ).
We have seen in Section . that our assumption that d n (1)/ϵ n is bounded away from 1 implies that c n = 1 -d n (0)/(2υ n ) is bounded away from 1 and so c n /(1 -c n ) is uniformly bounded, say by K -2. Similarly as above, using the 'mirror forest' obtained by ipping the order of the children of every vertex, it holds that E L( ˆ , ) q/2 C(q/2) • (σ n + ϱ n ) q/2 • |t -s | q/4 . This yields the bound E (# ˆ , + L( ˆ , )) q/2 1 E n 2 q/2-1 l q/2 n + K q/2 C(q/2) • (σ n + ϱ n ) q/2 • |t -s | q/4 .

We have seen in Section . that when d n (1)/ϵ n is bounded away from 1, the ratio σ 2 n /(υ n -ϱ n ) is bounded away from 0. Then so is (υ n ) -1/2 (σ n + ϱ n ). Finally, recall that we have assumed υ n s and υ n t to be integers so |t -s | υ -1 n , and thus, for β < q/4 -1, it holds that (σ n + ϱ n ) q/2 |t -s | 1+β (σ n + ϱ n ) q/2 υ -( 1+β) n is bounded below by some positive power of υ n . Since, the threshold l n is at most of order ln υ n , we see that for n large enough (but independently of s and t), we have l q/2 n (σ n + ϱ n ) q/2 |t -s | 1+β . It follows that E (# ˆ , + L( ˆ , )) q/2 1 E n 2 q/2-1 (σ n + ϱ n ) q/2 |t -s | 1+β + K q/2 C(q/2) • (σ n + ϱ n ) q/2 • |t -s | q/4 2 q/2-1 1 + K q/2 C(q/2)

• (σ n + ϱ n ) q/2 • |t -s | 1+β ,
and the proof is complete.

Figure :

 : Figure : An element of M ϱ n d n with n = 5 inner faces, ϱ n = 4 half boundary-length and(d n) n 1 = (1, 2, 1, 1, 0, 0, . . . ) face-degree sequence; faces are labelled by their degree.

  Figure :A planted forest on the le with the lexicographical order of the vertices, and on the right, its Łukasiewicz path on top and its height process below.

  ϱ n d n between υ n s and υ n -i n is moved to the part of B ϱ n d n between υ n s + i n and υ n , and the part of W ϱ n d n between υ n -i n and υ n t is moved to the part of B ϱ n d n between 0 and

  ϱ n d n ) denote the number of jumps with value in A amongst the rst r jumps of W ϱ n d n , and consider its inverse ζ A (p;W ϱ n

  we use the same reasoning as in the proof of Proposition , by constructing W ϱ n d n by cyclicly shifting B ϱ n d n at a uniformly random time which is independent of W ϱ n d n , we leave the details to the reader.

  the number of those vertices branching-o of the ancestral line of x n in the tree of T ϱ n d n which contains it. By symmetry, considering the 'mirror forest' obtained from T

  ϱ n d n by ipping the order of the children of every vertex, L(x n ) and R(x n ) have the same law so it su ces to consider the tails of R(

  be obtained by cyclicly shifting the bridge B ϱ n d n at the random time i n which is uniformly distributed in {1, . . . , υ n } and is independent of W ϱ n d n . In this coupling, we have that

  ϱ n d n , their number d of children which belong to T ϱ n

  Figure :A labelled forest on the le , and on the right, its height process on top and its label process below.

d

  n has d n (0) vertices, then a uniformly random map in M ϱ n d n in which we further distinguish a vertex uniformly at random has the uniform distribution in PM ϱ n d n . Moreover, half of the 2ϱ n edges on the boundary are 'positively oriented' and half of them are 'negatively oriented', so if M ϱ n

  in one-to-one correspondence with the set negative maps in PM ϱ n d n . Let us refer to these papers as well as to[Mar a] for a direct construction of the bijection (see alsoFigure ), and let us only recall here the properties we shall need.

  to study the label process of the associated random labelled forest (Tϱ n d n , ) in LT ϱ n d n .The law of the latter can be constructed as follows: rst sample Tϱ n d n uniformly at random in T ϱ n d n ,and then, conditional on it, label its root 0 and independently for every branch-point with, say, k 1 o springs, sample the label increments between these o springs and the branch-point uniformly at random in B -1 k . Let L ϱ n

  ϱ n d n and 1 i |x |, let us denote by α i (x) the ancestor of x at height |x

  ϱ n d n (υ n s)inf r ∈[s,t ] W ϱ n d n (υ n r ), so, according to Proposition E R( u, ˆ ) q/2

  n at time υ n -i n . The reader may want to consult Figure in[Mar b], where i n is denoted by a n . Fix 0 s < t 1, there are two cases: either υ n -i n falls between υ n s and υ n t, or it does not. If it does not, then the path of W ϱ n d n between υ n s and υ n t is moved without change in B ϱ n d n so the claim follows from the preceding bound applied to the image of s and t after the cyclic shift operation, which are still at distance |t -s |υ n from each other. If υ n -i n does fall between υ n s and υ n t, then the part of W

	so one recover B	ϱ n d n using that the latter is the cyclic shift of B d n by cyclicly shifting W ϱ n ϱ n	ϱ n d n at the random time i n ,

d

This work was supported by rst a public grant as part of the Fondation Mathématique Jacques Hadamard and then the European Research Council, grant ERC-2016-STG 716083 (CombiTop).

Now as previously, we have

Finally, we have seen that

so we obtain

where the last bound was shown in the poof of the case q = 1. Since c 1, b q -1, and 2 d(p) r (p) ∆ n , we have

Moreover, from our assumption that h, q υ n /4,

and nally, since ϱ n c ϱ c n , we obtain

On the left is the probability that Cont(x n,1 , . . . , x n,q ) = (k i , j i ) 1 i h and that the reduced forest has c trees, b branch-points and that for every p b, the p-th branch-point has r (p) children amongst which d(p) 2 belong to the reduced forest, with relative positions given by 1

We now want to sum over all quantities besides (k i , j i ) 1 i h ; we consider them one after the other, from the last to the rst. Indeed, the sum of the right-hand side above over all the possible z's is bounded by

where for the last line, we note that, since the d(p)'s are the number of children of the branch-points in the reduced forest, which contains c trees and q leaves, then q

Note the very crude bound: there are less than bq q 2 such vectors (d(1), . . . , d(b)). We next want to sum the last bound (times q 2 ) over all the vectors (r (1), . . . , r (b)); we have

n , so nally the probability that Cont(x n,1 , . . . , x n,q ) = (k i , j i ) 1 i h and the reduced forest has c 1 trees and b branch-points is bounded by

and the proof is complete.

. . Exponential tails for the height of a typical vertex. -We next derive a tail bound for the height of a typical vertex x n of T ϱ n d n . This result shall be used in the companion paper [Mar].

Proposition . There exists two universal constants c 1 , c 2 > 0 such that the following holds: Suppose that ∆ n 2 and let x n be a uniformly random vertex of T ϱ n d n , then its height |x n | satis es

uniformly in z 1 and n ∈ N.

As we already discussed in Section . , this bound does not hold for the maximal height of the forest, since the latter may be much larger than ϵ n /σ n .

Our argument is the following: if x n is at height at least zϵ n /σ n and if its ancestors reproduce according to the size-biased law as the ξ n,d n 's in the preceding section, then, according to ( ), the number of vertices LR(x n ) branching-o of its ancestral line is in average

and we known from Proposition that this has a sub-exponential cost.

Proof. According to Proposition , it is su cient to bound

Recall the de nition of Cont(

We deduce from Lemma with a single random vertex that

Let us write X n (i) = ξ d n (i) -1 in order to simplify the notation. Recall from ( ) that these random variables have mean σ 2 n /ϵ n so for h zϵ n /σ n , we have

The X n (i)'s come from sampling balls without replacement; as we already mentioned, by [Ald , Proposition . ], their sum satis es any concentration inequality based on controlling the Laplace transform the similar sum when sampling with replacement does. In particular, we may apply [McD , Theorem . ], and get

.

We next appeal to the following two bounds: rst (1e -t ) t(1 -t/2) 19t/20 for every 0 t 1/10, second te -t e -t /2 for all t 0. We thus have

Recall that we assume that ∆ n 2, which implies ∆ 2 n 2σ 2 n and also σ n 1. We thus obtain for every z 1,

.

Jointly with the exponential bound from Proposition , this completes the proof.

.

Maps and labelled forests

In this last section, we discuss random planar maps with prescribed face-degrees. The link with the rest of this work is via a bijection with labelled forests which we rst recall.

. . Tightness of random maps. -In this section, we prove tightness of maps as claimed in Theorem , relying on Theorem about the label process of the associated labelled forest. The argument nds its root in the work of Le Gall [LG ] and has now become very standard, adapted e.g. in [LG ,

LG , Abr , BJM , BM , Mar c, Mar a] so we only give the main steps and refer in particular to [Mar a, Section . to . ] for details.

Let us rst brie y de ne the Gromov-Hausdor -Prokhorov distance following Miermont [Mie , Proposition ], which makes separable and complete the set of measure-preserving isometry classes of compact metric spaces equipped with a Borel probability measure. Let (X , d x , m x ) and (Y , d Y , m ) be two such spaces, a correspondence between them is a subset R ⊂ X × Y such that for every x ∈ X , there exists ∈ Y such that (x, ) ∈ R and vice-versa. The distortion of R is de ned as

Then the Gromov-Hausdor -Prokhorov distance between these spaces is the in mum of all those ε > 0 such that there exists a coupling ν between m X and m Y and a compact correspondence R between X and Y such that ν (R) 1 -ε and dis(R) 2ε.

. . Distances are tight. -Recall that starting from a uniformly random map in M ϱ n

d n , we may sample a vertex uniformly at random to obtained a uniformly random pointed map in PM We want to rely on Theorem on the label process of the associated labelled forest (T ϱ n d n , ). This theorem demands the ratio d n (1)/ϵ n to be bounded away from 1. Recall the discussion after the statement of this theorem: we may always if needed discard the faces of degree 2 by gluing their two edges together; the only risk in doing so is that υ n -d n (1) does not tend to in nity, in which case Theorem does not hold anymore. But if υ n -d n (1) is bounded, then so are d n (0), ϱ n , and σ n so the number of vertices, faces, and edges of the new map without the faces of degree 2 is bounded, and so is the normalising factor so tightness is easy in this case. In the rest of this section, we therefore assume that d n (0) → ∞ and that we may apply Theorem (already extracting a subsequence if necessary).

Recall that in the bijection relating (M

), the vertices of the former di erent from correspond to the leaves of the latter, and the internal vertices of T

lexicographical order and for every i, j ∈ {0, . . . , υ n }, we set

where d gr is the graph distance in M ϱ n d n . We then extend d n to a continuous function on [0, υ n ] 2 by 'bilinear interpolation' on each square of the form [i, i + 1] × [j, j + 1] as in [LG , Section . ] or [LGM , Section ]. For every 0 s t 1, let us set

For a continuous function : [0, 1] → R, let us set for every 0 s t 1,

In a slightly di erent context (the coding of [BDFG ], but it is adapted in this context, see [Mar c]) Le Gall [LG , Equation ] (see also [LG , Lemma . ] for a detailed proof) obtained the bound

for every s, t ∈ [0, 1]. According to Theorem , from every increasing sequence of integers, one can extract a subsequence along which the continuous processes L (n) converge in distribution to some limit process, say L. From the previous bound, one can extract a further subsequence along which we have

where (d ∞ (s, t)) s,t ∈[0,1] depends a priori on the subsequence and satis es d ∞ D L , see [LG , Proposition . ] for a detailed proof in a similar context.

. . Planar maps are tight. -Let us implicitly restrict ourselves to a subsequence along which ( ) holds. Appealing to Skorokhod's representation theorem, let us assume furthermore that it holds almost surely. The fonction d ∞ is continuous on [0, 1] 2 and is a pseudo-distance (as limit of d (n) ). We then de ne an equivalence relation on [0, 1] by setting

and we let M ∞ be the quotient [0, 1]/≈, equipped with the metric induced by d ∞ , which we still denote by d ∞ . We let Π be the canonical projection from

is a compact metric space, which nally we endow with the Borel probability measure m ∞ given by the push-forward by Π of the Lebesgue measure on [0, 1]. We claim that, deterministically, from ( ), we may deduce the convergence

for the Gromov-Hausdor -Prokhorov distance, this will end the proof of Theorem . The sequence (φ(x i )) 0 i υ n lists with redundancies the vertices of M

which, appealing to ( ), tends to 0 whenever the convergence ( ) holds, which concludes the proof of Theorem .