Jean-François Marckert

Minmin Wang

A new combinatorial representation of the additive coalescent

Keywords: Mathematics Subject Classification (2000) 60C05, 60K35, 60J25, 60F05, 68R05 additive coalescent, Cayley trees, increasing trees, parking, random walks on trees

The standard additive coalescent starting with n particles is a Markov process which owns several combinatorial representations, one by Pitman as a process of coalescent forests, and one by Chassaing & Louchard as the block sizes in a parking scheme. In the coalescent forest representation, some edges are added successively between a random node and a random root. In this paper, we investigate an alternative construction by adding edges between the roots. This construction induces the same process at the level of cluster sizes, but allows one to make numerous connections with some combinatorial and probabilistic models that were not known to be connected with additive coalescent. The variety of the combinatorial objects involved here -size biased percolation, parking scheme in a tree, increasing trees, random cuts of trees -justifies our interests in this construction.

Introduction

The aim of this paper is to present a new combinatorial point of view on the additive coalescent starting with n particles with same masses. In his paper [START_REF] Pitman | Coalescent random forests[END_REF], Pitman proposes a combinatorial construction of this process. The idea of his construction is rooted in the combinatorics of Cayley trees. In this construction, the coalescence is realized by successively adding (random) edges in a forest, giving rise eventually to a uniform Cayley tree in the end. Here, we investigate an alternative construction which leads to, as we believe, a richer combinatorial environment in providing a link with several other processes defined on trees: a notion of size-biased percolation on a tree, a treeshape parking scheme, a random walker model in the tree, a model of decreasing edge-labellings of a Cayley tree, as well as the random cutting problem which dates back to Meir & Moon [START_REF] Meir | Cutting down random trees[END_REF]. Finally, we propose an enriched version of the parking scheme studied by Chassaing & Louchard [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF] for the additive coalescence which unifies our construction and Pitman's construction. We also study the asymptotics for the additive coalescence, based on the parking scheme.

Notation. Throughout the paper, for any integer n ≥ 1, [n] denotes the set {1, • • • , n}. We use both notation #A and |A| for the cardinal of a finite set A. If t is a tree or a forest, its size |t| is the number of its nodes. The number of edges of t is denoted by |t| E , and the set of edges by E(t). In the paper, all random variables (r.v.) are assumed to be defined on a common probability space (Ω, A, P). For any finite set E, we write X ∼ Uniform(E) to state that the r.v. X is uniform on E.

Additive coalescent process

Throughout this work, n ≥ 1 denotes a positive integer. Let us first recall the Marcus-Lushnikov process. At time 0 the system contains n particles labelled from 1 to n, each with mass 1. Consider these particles as the vertices of a complete graph with virtual edges, and equip the edges between vertices i and j with random exponential clocks of parameter K(x i , x j ) = x i + x j where x i and x j are the masses of i and j. When the clock between i and j rings, replace the masses x i and x j by x i + x j and 0, respectively, and update the parameters of the clocks involving i and j so that the rates remain given by the kernel. This is the so-called Marcus-Lushnikov [START_REF] Marcus | Stochastic coalescence[END_REF][START_REF] Lushnikov | Some new aspects of coagulation theory[END_REF] process, which is a continuous-time Markov process. Marcus-Lushnikov processes may be defined even when the number of particles is infinite, provided that the total mass is finite (see e.g. [START_REF] Evans | Construction of Markovian coalescents[END_REF]). The Marcus-Lushnikov process has been introduced in order to model coalescence systems, in which particles have a propensity (represented by the kernel K) to coalesce.

Another representation of this process relies on a combinatorial process taking its values in P [n] the set of partitions of [n]. Again, at time 0, n particles labelled from 1 to n are present in the system at time 0. The masses do not play an explicit role here, but it may help the reader to consider that the particles all have mass 1 at time 0. Denote by P [n] the set of partitions of [n]. The additive coalescent (of length n) is a Markov chain {Π + k : 0 ≤ k ≤ n -1} taking values in P [n] such that: 1) Π + k is a partition of [n] into nk subsets (so that Π + 0 is the partition of [n] into n singletons); 2) given Π

+ k = {π + k,1 , • • • , π + k,n-k } with n i = |π + k,i |, 1 ≤ i ≤ n -k, Π +
k+1 is obtained from Π + k as follows: pick a pair of parts {π + k,i , π + k,j } with probability

n i + n j 1≤i <j ≤n-k (n i + n j ) = n i + n j n(n -k -1)
, 1 ≤ i < j ≤ nk ;

and merge this pair into one subset (and let the other parts unchanged).

At the level of component sizes, the Markov chain {Π + k : 0 ≤ k ≤ n -1} has the same evolution as the Marcus-Lushnikov process (at its jumping times) as described above.

Proposition 1 ( [START_REF] Pitman | Coalescent random forests[END_REF], Proposition 6). For each 0 ≤ k ≤ n-1 and each partition π

:= {π 1 , • • • , π n-k } of [n] into n -k subsets with |π i | = n i , 1 ≤ i ≤ n -k, we have P Π + k = π = 1≤i≤n-k n n i -1 i n k n-1 n-k-1 . (1)
An idea to encode coalescence consists in adding some edges between the components that merge, creating in such a way forests and trees... and this works wonderfully, since the forests and trees that come into play are particularly simple, and this has numerous implications.

Let us briefly recall Pitman's construction of (Π + k ) in [START_REF] Pitman | Coalescent random forests[END_REF] which is based on a coalescent process of rooted forests. A rooted forest over [n] here is a graph on [n] whose connected components are trees, each tree t being rooted at one of its vertex r. Here and below, edges are considered directed towards their roots. For 1 ≤ k ≤ n, denote by F k,n the set of rooted forests over [n] which have k tree components. Notice that F 1,n is the set of rooted labelled trees (Cayley trees) with n nodes. By Riordan [START_REF] Riordan | Forests of cayley trees[END_REF] or Pitman [START_REF] Pitman | Coalescent random forests[END_REF]Formula (5)],

#F k,n = n n-k n -1 k -1 , for 1 ≤ k ≤ n. (2)
Let us define a sequence of random rooted forests (F PF k , 0 ≤ k ≤ n -1) over [n] as follows (the exponent "PF" refers to "Pitman's forest"). First, F PF 0 is the only element of F n,n , namely, the trivial forest of n trees reduced to their roots which are labelled from 1 to n.

Pitman's Algorithm (PF Algo). Clearly, F PF k ∈ F n-k,n and has exactly k edges, for 0 ≤ k ≤ n -1. Observe that the vertex sets of the tree components of F PF k form a partition of [n]; denote by Π PF k this partition.

For 1 ≤ k ≤ n -1, to construct F PF k from F PF k-1 ,

Theorem 2. [[29], Theorem 4] (i)

The following distribution equality holds

(Π PF k , 0 ≤ k ≤ n -1) (d) = (Π + k , 0 ≤ k ≤ n -1). ( 3
) (ii) Moreover, for 0 ≤ k ≤ n -1, F PF k ∼ Uniform (F n-k,n ).
This representation has led to several interesting consequences: -one gets a limit representation of the coalescent process when n → +∞ (see Section 1.4 for more information); -one shows that the time-reversal of the coalescence process, the so-called fragmentation process, is simple too, since it amounts to choosing at each step a uniform edge and removing it (see Section 3 for details and a related question) ; -the genealogy of the fragments hence produced has a branching structure, studied per se [START_REF] Bertoin | The cut-tree of large galton-watson trees and the brownian crt[END_REF] (see also [START_REF] Dieuleveut | The vertex-cut-tree of galton-watson trees converging to a stable tree[END_REF][START_REF] Broutin | Cutting down p-trees and inhomogeneous continuum random trees[END_REF] and Section 3).

We wish to comment on two simple facts: • It is not apparent at first glance that the evolution of tree sizes in Pitman's construction coincides with the additive coalescent, because of the asymmetry in the construction of the forest. On the other hand, two trees t 1 and t 2 will be connected anyway either we add an edge from t 1 to t 2 or from t 2 to t 1 . Thus, the probability that these two trees get merged is proportional to |t i | + |t j |.

• In above, an edge is added between a uniform random vertex u taken in the global forest, and a random root r taken among the roots of the trees which do not contain u. This rule is somehow arbitrary. Another choice of the edge will yield the same partitions (thus the same distribution as given in Theorem 2 (i)), as long as it connects the same pairs of trees. And a natural question is to wonder what will become Theorem 2 (ii) if another rule is applied. The following paragraph answers partially to this question.

The sorted coalescence algorithm

We propose the following variant of Pitman's Algo.

Sorted coalescence algorithm (SC Algo).

Let F SC 0 be the trivial forest of n trees. We construct

F SC k from F SC k-1 for 1 ≤ k ≤ n -1, as follows. (a) Choose a uniform node α SC k in F SC k-1 . Let t k be the tree which contains α SC k , and let r(α SC k ) be the root of t k . (b) Choose a tree t SC k in F SC k-1 uniformly in F SC k-1 among the trees different from t k . Denote by β SC k the root of t SC k . (c) Add the directed edge e SC k := r(α SC k ) → β SC k .
In other words, the dynamic is almost the same as that of Pitman's. Instead of adding the edge β PF k → α PF k , we add the edge r(α SC k ) → β SC k , but the distribution of (α PF , β PF ) coincides with that of (α SC , β SC ). The new edge is then added between roots of trees in the forest, when it was between a random node and a root before. Since this "small" difference occurs for each k, the successive adding of edges leads finally to much different forests.

However, in terms of the cluster size evolution, or in terms of the induced partitions, both constructions induce exactly the same distribution: at each time step, both construction consist in merging two components, the first one being chosen with probability proportional to its size, the second one being taken uniformly among the other parts.

For 0 ≤ k ≤ n -1, let Π SC k be the partition of [n] induced by the vertex sets of the tree components of F SC k . We then have immediately Theorem 3. The following distributional equality holds

(Π SC k , 0 ≤ k ≤ n -1) (d) = (Π PF k , 0 ≤ k ≤ n -1) (d) = (Π + k , 0 ≤ k ≤ n -1). ( 4
)
On the other hand, by putting the label k on the kth created edge e k (we denote L SC e k = k), we obtain at each time step a forest of Cayley trees equipped with a decreasing edge-labelling along the branches (Theorem 6). We call such a tree a decreasing tree. Knowing the complete sequence

(F SC k , 0 ≤ k ≤ n -1)
, the edge labelling can be recovered since between time k and k + 1 only one edge has been added... and it has label k + 1. On the other hand, the single tree (F SC n-1 , L SC n-1 ) equipped with its edge labelling also encodes completely the history of the additive coalescent. Remark 4. Visibly, there is a similarity in the constructions of the processes

(F PF k , 0 ≤ k ≤ n -1) and (F SC k , 0 ≤ k ≤ n -1)
. We can construct a coupling between the two sequences of forests, but this is not the right moment... We postpone it to Section 2.8.

Content of the paper

In Section 2.1, we study the distribution of the process ((

F SC k , L SC k ), 0 ≤ k ≤ n-1).
In particular, we will see that conditional on F SC n-1 , the labelling L SC n-1 is uniform among the decreasing edge labellings of F SC n-1 (Theorem 6). We then show ((

F SC k , L SC k ), 0 ≤ k ≤ n -1)
-our forest encoding of the additive coalescent -is connected to many new natural stochastic models:

• In Section 2.2, it is shown that, given a Cayley tree T , a uniform decreasing edge-labelling may be constructed thanks to a simple Markov model that we call "random walker algorithm" in the tree (Lemma 7).

• In Section 2.3, Proposition 9 shows a link between the uniform decreasing edge-labelling and a percolation process in the tree that we call size-biased percolation: the infection starts from the root; at each step a neighboring node is infected proportionally to the size of the tree hanging out of this node.

• In Section 2.4, the model of decreasing trees is shown to be related with a parking scheme in the tree in which successive cars choose an edge e uniformly and park at the edge nearest to the root among the available edges on the branch from e to the root.

Each of the constructions mentioned above provides a representation of the additive coalescent conditional on the final tree.

• In Section 2.5, we recall the representation of the additive coalescent using a linear parking scheme introduced in Chassaing & Louchard [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF]. Based on this representation, they study the asymptotic behaviors of the cluster sizes in the additive coalescent which has started with n particles and has experienced nλ √ n mergings (this is the critical window). In Section 2.6, we revisit and enrich this construction in order to make it encode faithfully the additive coalescent, and not only the cluster sizes. Using this enriched parking scheme, the study of the asymptotic is still possible and we recover the limit behavior proved by [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF] (see Section 2.9). Moreover, the connection between this enriched parking problems, Pitman construction and our model of decreasing trees appears to be somehow trivial (Sections 2.6.2 and 2.6.3).

Finally in Section 3, we use the forests (F SC k , 0 ≤ k ≤ n -1) and the coupling with (F PF k , 0 ≤ k ≤ n -1) to give a new and simple proof on a well-known problem on random cutting of trees.

Related works on the additive coalescent

The aim of coalescent processes is to model physical/chemical systems containing a large numbers of weighted particles that have a propensity to merge. There are several types of models, but each of them relies on the so-called collision kernel K, which encodes the propensity of two particles with masses x and y to merge: they merge "at rate K(x, y)".

Smoluchowski coagulation equations [START_REF] Smoluchowski | Drei Vortrage uber Diffusion, Brownsche Bewegung und Koagulation von Kolloidteilchen[END_REF][START_REF] Aldous | Deterministic and stochastic models for coalescence (aggregation, coagulation): a review of the mean-field theory for probabilists[END_REF] provide a description of the so-called mean-field behavior of a coalescent system with an infinite number of particles by specifying the evolution of the densities of particle masses. These equations form an infinite system of ordinary differential equations. Explicit solutions are available in some special cases, including the additive kernel, i.e., K(x, y) = x + y, the multiplicative one, i.e., K(x, y) = xy (see [START_REF] Aldous | Deterministic and stochastic models for coalescence (aggregation, coagulation): a review of the mean-field theory for probabilists[END_REF][START_REF] Bertoin | Random fragmentation and coagulation processes[END_REF] and [START_REF] Fournier | Well-posedness of Smoluchowski's coagulation equation for a class of homogeneous kernels[END_REF]), and the Kingman coalescent K(x, y) = 1 ( [START_REF] Kingman | The coalescent[END_REF]).

The probabilistic counterpart of the Smoluchowski equations is the Marcus-Lushnikov model [START_REF] Marcus | Stochastic coalescence[END_REF][START_REF] Lushnikov | Some new aspects of coagulation theory[END_REF], intended to describe the continuous-time evolution of the masses -at the particles levelfor a system with a finite number of particles. Between each pair of particles (p 1 , p 2 ), put a clock which rings according to independent exponential variables with parameter K(Mass(p 1 ), Mass(p 2 )). When a clock rings, merge the corresponding pair of particles and update all the clocks. For any K this is a time homogeneous continuous-time Markov process.

In the additive coalescent case, when starting from n particles with initial mass 1, the time needed to pass from the kth merging to the (k +1)th in the Marcus-Lushnikov model is given by τ k = min{τ (p 1 , p 2 ), {p 1 , p 2 } ∈ P k } where the τ (p, p ) are independent, exponentially distributed with parameter Mass(p) + Mass(p ), and P k is the set of pairs of (different) particles in the system after k merging. One checks that τ k is exponential with parameter n(nk -1), so that it depends only on the number of mergings already done, and not on the details of the current masses. For this reason, the discrete-time version studied here, which is parametrized by the number of mergings, can be related to the continuous-time version by a simple time change.

There is an extensive literature in general coalescent processes or in the additive coalescent (see Pitman [START_REF] Pitman | Combinatorial stochastic processes[END_REF]Section 9] for an overview). Let us cite a few works which are most related to the present one.

First of all, in his work [START_REF] Pitman | Coalescent random forests[END_REF] where he introduced the model of coalescent forests for the additive coalescence as recalled in Section 1.1, Pitman also observed the following things: a) the tree obtained eventually from the construction is uniform among the set of Cayley trees with n nodes; b) if we rank the edges according to their appearance, given the final tree, this ordering of the edges is uniformly distributed among all the edge-orderings of the tree. This leads to a representation of the additive coalescent as a time reversal of a fragmentation process defined on the uniform tree.

We have discussed the case where initially there are n masses. We can also talk about the limit case when n → ∞. This "limit", or the convergence of the additive coalescence processes, say, is well understood thanks to Evans & Pitman [START_REF] Evans | Construction of Markovian coalescents[END_REF] who showed the following. There exists a Feller process

X ∞ = (X ∞ (t), t ∈ R + ) taking values in 1 ↓ = {(x i , i ≥ 1) : x 1 ≥ • • • ≥ x i ≥ x i+1 ≥ • • • ≥ 0, x i < +∞} (5)
which has the dynamics of additive coalescent; moreover, if X n denotes the Markov process with the same kernel starting from (1/n, • • • , 1/n, 0, 0, • • • ) (this corresponds to the component sizes in Marcus-Lushnikov model with n initial masses 1/n), then

(X n (. + (log n)/2)) (d) ---→ n→∞ (X ∞ (.)),
where the convergence holds in D((-∞, +∞), 1 ↓ ). The limit is called the standard additive coalescent (see Section 2.9 below for more information). Moreover, the coalescence-fragmentation duality mentioned above remains valid when n tends to infinity, leading to the Aldous-Pitman's representation [START_REF] Aldous | The standard additive coalescent[END_REF] of the standard additive coalescent on Aldous' continuum random tree.

Another combinatorial representation of the additive coalescent has been investigated by Chassaing & Louchard [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF] (see Section 2.5). They observe that in a certain parking scheme, known to be related to a well-known data structure named "hashing with linear probing" in computer science, parking blocks evolve as the additive coalescent. This representation has the following advantage: it allows for a direct encoding of the additive coalescent (starting with n particles with mass 1) by a Markov chain on Z such that the sizes of the parking blocks at each time correspond to the excursion lengths of the process above its running infimum (see Section 2.5). Moreover, it is shown in [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF] that these excursions lengths converge to those of a Brownian excursion with a linear drift. See Bertoin [START_REF] Bertoin | A fragmentation process connected to brownian motion[END_REF] for a related work. Let us also mention that this is close in spirit in the way that Aldous encodes the multiplicative coalescent using another random walk which converges to the Brownian motion with a parabolic drift (see [START_REF] Aldous | Brownian excursions, critical random graphs and the multiplicative coalescent[END_REF]).

Recently, Broutin and the first author [START_REF] Broutin | A new encoding of combinatorial coalescent processes[END_REF] revisited the study of the asymptotic additive and multiplicative coalescents. They proved by a unified approach, by a passage to the limit, that the excursions of the Brownian motion with parabolic drift above the running minimum (B t -λt 2 /2, t ≥ 0), and those of (e t -λt) are the limit of the cluster sizes in the multiplicative and additive coalescent as a process indexed by the time (which is λ here).

A new point of view on the additive coalescent 2.1 Alternative to Pitman's construction

We discuss here the properties of the sequence of forests (F SC k , 0 ≤ k ≤ n -1) produced by SC Algo, introduced in Section 1.2.

The terminology "sorted coalescence algorithm" is motivated by the following fact. We will see that in this construction, if we fix the tree that appears in the end, then the coalescence takes place in an ordered manner: along the branches of the tree, from the leaves towards the root.

Recall that the edges of the forest F SC k have been labelled by their rank of appearance. We say that an edge-labelling

L = (L e , e ∈ E(f )) of a forest f = (f 1 , • • • , f k ) is decreasing if it has the following properties: -the set of labels is {1, • • • , |f | E },
each label being used exactly once, -in each tree f j , the labelling is decreasing along each simple path going out of the root r: if

(u 0 = r, u 1 , • • • , u h ) is a simple path in f j for some h ≥ 1 , then L (u 0 ,u 1 ) > • • • > L (u h-1 ,u h ) . (6)
Let DL(f ) be the set of decreasing edge-labellings of a forest f . For a vertex u ∈ f , let Sub u (f ) denote the subtree of f rooted at u. Also recall that for a tree or a forest t, |t| stands for the number of its nodes.

Lemma 5. For 1 ≤ k ≤ n and f ∈ F k,n , #DL(f ) = (n -k)! u∈f \{ρ i ,1≤i≤k} 1 |Sub u (f )| , (7)
where ρ i , 1 ≤ i ≤ k, are the k roots of f .

Proof. We first show that for a rooted tree t,

#DL(t) = u∈t (|Sub u (t)| -1)! v: child of u |S v (t)|! . ( 8
)
Notice that after simplification, (8) leads to the formula ( 7) when k = 1. Now, ( 8) can be checked by an induction on the size of t. For |t| = 1, this is trivial. Suppose (8) holds for trees with sizes up to m -1 ≥ 1. For a rooted tree t of size m with root r, denote by J the in-degree of r. Let (E j , 1 ≤ j ≤ J) be the partition of the edge set of t induced by the J subtrees above r. Then a decreasing edge labelling of t is obtained by first choosing the subsets of the labels for E j , 1 ≤ j ≤ J, and then assigning the largest label of each subset to the edge adjacent to the root. Applying the induction hypothesis yields [START_REF] Bertoin | Random fragmentation and coagulation processes[END_REF]. To get to the enumeration for rooted forests, we first choose the subsets of labels for t i , 1 ≤ i ≤ k, then apply (8) for each t i . Equation [START_REF] Bertoin | A fragmentation process connected to brownian motion[END_REF] easily follows.

Write T SC = F SC n-1 , the tree which appears at the end of the construction. Recall that we defined an edge labelling by defining L SC e = k if e is the kth added edge. Let L SC = (L e , e ∈ E(T SC )) be the global edge labelling of T SC . For 0 ≤ k ≤ n -1, let L SC k be the subset of L SC obtained by removing those labels > k. Then it is clear that L SC k is a decreasing edge-labelling of F SC k . As said before, the pair (T SC , L SC ) encodes the history of the coalescence so that we can recover from (T SC , L SC ) the sequence of the pairs (r(α SC k ),

β SC k ), 1 ≤ k ≤ n -1. Theorem 6. For 0 ≤ k ≤ n -1, we have P (F SC k , L SC k ) = (f, ) = 1 F n-k,n (f ) #F n-k,n 1 DL(f ) ( ) #DL(f ) . (9)
Hence,

F SC k ∼ Uniform (F n-k,n ) and conditional on F SC k , L SC k ∼ Uniform(DL(F SC k )).
In contrast to Theorem 3, this theorem should appear a bit unexpected, since at the level of forests the sorted coalescence construction is rather different from the one of Pitman, and seems to "favor" the neighborhoods of the roots. On the other hand, notice that after the edge r(α SC k ) → β SC k has been added, then r(α SC k ) is not a root anymore, so that in the sequel of the construction, no more edges will be added from or to r(α SC k ).

Proof. Let f ∈ F n-k,n and ∈ DL(f ). Notice that if (F SC k , L SC k ) = (f, ) we can recover the sequence (F SC j , 0 ≤ j ≤ k) from (f, ).
In particular, if we write x j → y j for the edge labelled j in the labelling (recall that the edges are directed towards the root), then Sub x j (f ) is the tree component of F SC j-1 which contains α SC j , 1 ≤ j ≤ k. By our construction, the probability that F SC j is obtained from F SC j-1 by adding the edge x j → y j is |Sub x j (f )|/(n(nj)). This yields

P F SC k = f ; L SC k = = (n -k -1)! n k (n -1)! 1≤j≤k |Sub x j (f )|.
Since each vertex of f except the nk roots appears exactly once in {x j , 1 ≤ j ≤ k}, we obtain that

P F SC k = f ; L SC k = = (n -k -1)! n k (n -1)! u∈f \{ρ i ,1≤i≤n-k} |Sub u (f )|,
where ρ i , 1 ≤ i ≤ nk are the nk roots of f . Comparing this with ( 2) and ( 7), we get (9).

Random walker algorithm

Here we discuss a model of random walkers in a Cayley tree T with n nodes. In this model, n -1 random walkers will climb successively in the tree, walking from one edge to an adjacent one. The kth walker will decide to stop at a certain edge e, and will label this edge k. The global labelling will be a uniform decreasing edge-labelling of T .

At time 0 all the edges of T are white. Let r be the root of T . Add to T an extra white edge e from an extra vertex u and r (see Fig. 1). The starting point for the random walkers will always be this edge e . Consider T ∪ {u} rooted in the extra vertex u. The usual parent-children relation among the nodes can be extended to the edges in an obvious way. This leads to a notion of child-edges of an edge e ∈ E(T ).

Random walker algorithm.

For k going from 1 to n -1, the kth walker starts from the root-edge e . Its journey runs as follows. Assume that at some moment, she is at some edge e. Let d be the number of white children-edges of e.

-If d = 0, that is, if there are no white child-edge of e, paint in black this last edge e and label it with the rank of the walker (put L RW e (T ) = 1 for the first random walker, L RW e (T ) = 2 for the second, etc). if d ≥ 1, let e 1 , e 2 , . . . , e d be the white child-edges of e. The walker goes to e i with probability proportional to W i , 1 ≤ i ≤ d, where W i is the number of the white edges contained in the subtree of T rooted at e i (including e i ).

Hence, when k walkers have climbed, there are exactly k black edges, labelled from 1 to k (see Fig. 1). In the end, all the edges of T are painted black. Moreover, T is equipped with an edge-labelling L RW (T ) = (L RW e (T ), e ∈ E(T )) induced by the ranks of the walkers.

Lemma 7. For each fixed T ∈ F 1,n , L RW (T ) ∼ Uniform (DL(T )). had probability (7/8)(3/5)(1/2) = 21/80 to be chosen, after this choice, the second one had probability (6/7)(2/4) = 12/28 to be chosen. In terms of partitions, the evolution is as follows:

Π RW 0 = {{1}, • • • , {9}}, Π RW 1 = {{1}, {2}, {3}, {4, 6}, {5}, {7}, {8}, {9}}, Π RW 2 = {{1}, {2, 3}, {4, 6}, {5}, {7}, {8}, {9}}, Π RW 3 = {{1, 2, 3}, {4, 6}, {5}, {7}, {8}, {9}}, Π RW 8 = {1, • • • , 9}.
Proof. If e i , 1 ≤ i ≤ k, are the edges adjacent to the root, write T + i for the subtrees rooted at e i . By a decomposition at the root and an induction argument, we see that the proof reduces to identifying the joint distribution of ({ (e), e ∈ T + i }, 1 ≤ i ≤ k), the sets of the labels attributed to the T + i 's. For this, only the first step of each walker needs to be followed. If the wth walker goes in

T + i , let us set c(w) = i, 1 ≤ w ≤ n -1.
When t walkers have climbed, let l t (i) = #{w ∈ {1, 2, . . . , t} : c(w) = i} be the number of the walkers which have gone into T + i ; then

P(c(t + 1) = i) = (|T + i | E -l t (i))/(|T | E -t). It follows that ({ (e), e ∈ T + i }, 1 ≤ i ≤ k) forms a uniform partition of {1, . . . , |T | E } into k parts of respective sizes |T + i | E , 1 ≤ i ≤ k.
By the previous arguments, this shows that L RW (T ) ∼ Uniform(DL(T )).

For 0 ≤ k ≤ n -1, by discarding the edges e whose labels L RW e (T ) > k, we obtain a forest over [n]. Then the vertex sets of the tree components of this forest induce a partition of [n], which we denote by Π RW k . Alternatively, Π RW k can be defined by looking at the black components of T defined as follows. When k walkers have climbed, there are exactly k black edges. Then we find in T (see Fig. 1): -the white edges constitute the edge set of a subtree of T which contains the root, -the black edges along with the n vertices form a forest over [n] with nk black tree components.

Here is another representation of the additive coalescent:

Theorem 8. For T ∼ Uniform (F 1,n ), Π RW k , 0 ≤ k ≤ n -1 (d) = Π + k , 0 ≤ k ≤ n -1 .
Proof. From Lemma 7 and Theorems 3 and 6, we readily see that the pair (T, L RW (T )) produced by the random walkers model has the same distribution as (T SC , L SC ).

Size-biased percolation

We introduce a model of percolation on a tree that we call size-biased percolation. It will be seen to be a time-reversal of the random walker process. Take a tree T rooted at r in F 1,n . We define a sequence (Perc k (T ), 0 ≤ k ≤ |T | E ) which will represent the percolated cluster at each time.

-At time k = 0, the cluster Perc k (T ) is reduced to r.

-For 0 ≤ k ≤ |T | E -1, add to the cluster Perc k (T ) the edge e adjacent to it with probability proportional to the size of the subtree hanging out of e, that is proportional to the number of nodes in the subtree of T \ Perc k (T ) which is adjacent to e. Observe that each Perc k (T ) is a subtree of T containing the root. Also, k → Perc k (T ) is increasing for the inclusion order. For 0 As before, we introduce an edge-labelling L Perc (T ) of T by putting a label nk to the unique edge e in Perc k (T )

≤ k ≤ |T | E , let T Perc
\ Perc k-1 (T ), 1 ≤ k ≤ |T | E .
It is easy to see that L Perc (T ) belongs to DL(T ), the set of decreasing edge-labellings of T . Proposition 9. For any rooted tree T we have

L Perc (T ) ∼ Uniform (DL(T )). If T uniform in F 1,n , then Π Perc(T ) n-1-k , 0 ≤ k ≤ |T | E (d) = Π SC k , 0 ≤ k ≤ |T | E ; ( 10
)
as a consequence, Π Perc(T ) n-1-k , 0 ≤ k ≤ n -1 is the additive coalescent.
Proof. The proof is similar to the one of Lemma 7; we omit the details.

A tree-shaped parking scheme

We claim that for any fixed T ∈ F 1,n , the process (Perc k (T ), 0 ≤ k ≤ n -1) may be represented as a tree-shaped parking scheme (TSPS). In the usual "linear" parking scheme, the places are arranged along the line (see Section 2.5). The cars successively choose a place c and then park at the first free place among c, c + 1, c + 2, • • • . In the tree-shaped parking scheme, the cars choose a node, and then parks at a free place in the direction to the root. We will need this free place to be the one nearest to the root. More precisely, there are two equivalent versions:

A) Consider a sequence (V i , i ≥ 1) of i.i.d. random variables uniformly distributed among the nodes of T . We will define the places chosen by the successive cars based on this sequence.

In words: a car choose a place c uniformly in the tree and look for unoccupied nodes in the path from c to the root; if such nodes exist, it parks at the one nearest to the root.

If no more place is available, it chooses a new uniform place c, and proceeds as before. Formally: assume that at time 0, the root r of T is the only occupied node. Set k 0 = 0 and TPS 0 (T ) = {r} (the tree reduced to the root); more generally for 1

≤ j ≤ n -1, let k j = min{i > k j-1 : V i / ∈ TPS j-1 (
T )} and denote by V j the node on the path r, V k j which is nearest to r and not contained in TPS j (T ); then define TPS j+1 (T ) as the smallest tree containing TPS j (T ) and V j . Clearly, (TPS j (T ), 0 ≤ j ≤ n -1) is an increasing sequence of subtrees of T . In this version a place is a node.

B)

In this second version, a place is an edge instead of being a node. Start from a tree T whose edges are painted in white. Each time, one picks uniformly at random a white edge e in T , and color in red the last white edge on the path from e to the root (note that there is an obvious correspondence between choosing a uniform node distinct from the root and choosing an uniform edge). In this way, we obtain a sequence of subtrees formed by the red edges (see Fig. 2). It is clear that this sequence has the same distribution as (TPS j (T ), 0 ≤ j ≤ n -1) as defined above.

Once again, one may attribute a labelling L TPS (T ) to the edges according to their entrance in TPS(T ): put a label L TPS e (T ) = nk to the kth added edge. This labelling belongs to DL(T ). Moreover, we have the following.

Proposition 10. For any rooted tree T , the following identities in distribution hold

L TPS (T ) (d) = L Perc (T ) ; (11)
(TPS k (T ), 0 ≤ k ≤ |T | E ) (d) = (Perc k (T ), 0 ≤ k ≤ |T | E ) . (12)
Proof. To choose a subtree τ of T \ Perc k (T ) with probability proportional to its size, one can take a sequence of i.i.d. uniform variables (U i , i ≥ 1) taking values in the vertex set of T , and keep the first U i that falls in T \ Perc k (T ). The subtree τ of T \ Perc k (T ) which contains this first U i has the right distribution.

Linear parking scheme representation revisited, and asymptotics

Parking scheme and its relation with additive coalescence is the essence of the paper [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF] by Chassaing & Louchard. Here, in contrast with Section 2.4, parking scheme refers to linear/circular parking scheme.

Let us explain some of their considerations before proposing an enriched version of their construction, which will allow us to unify the parking representation with the model of coalescent forests of Pitman and our decreasing trees. The parking contains n places labelled from 1 to n. The parking is circular so that place n + 1 and 1 coincide: Here, for x ∈ Z, x stands for the integer in [n] equaling x modulo n. The parking scheme can be presented as an algorithm taking as entry some data, and producing a sequence of parking occupations. The "data" is a vector

(C i , 1 ≤ i ≤ n -1) taking values in [n] n-1 .
At the begining all places are free, and a total of n -1 cars will park, successively.

Parking algorithm.

At time i, the car i enters in the parking (and i varies from 1 to n -1). The variable C i is the choice of car i. Upon the arrival of the car i, the places already occupied in the parking are P 1 , . . . , P i-1 . The car i parks at P i , the first free place among C i , C i + 1, C i + 2, .... We may restate the previous condition as: car i parks at P i := C i + l * , where l * := min{l ∈ {0, 1, . . . , n -1} : C i + l / ∈ {P 1 , . . . , P i-1 }}. In the sequel we will consider the case that the C 1 , • • • , C n-1 are random variables, i.i.d. and uniform in [n].

Note 11. It will be useful to consider that the C i s are random variables defined on the probability space (Ω Par , A Par , P Par ) where Ω Par = [n] n-1 , A Par = Powerset(Ω Par ), and P Par , the uniform distribution on Ω Par . On this space, the functions C i are defined by C i (ω) = π i (ω) (the extraction of the ith coordinate). The parking process (P i , 1 ≤ i ≤ n -1), as well as the quantities that will be defined in this section, are random variables on this space. For sake of shortness, we will mix considerations for which the (C i , 1 ≤ i ≤ n)'s are random variables or just elements of Ω Par = [n] n-1 .

For any i, j ∈ [n], denote by [i, j] the circular interval formed by i, i + 1,

• • • , i + k where k = j -i.
Define a block in the parking as a circular interval [x, x + k], maximal for the inclusion partial order, so that x + i is occupied for 0 ≤ i < k, and x + k is not occupied. With this definition, we have the following description of the parking. • In the beginning, the blocks are the n trivial blocks I[0] := (I 0 j , 1 ≤ j ≤ n) where I 0 j = [j, j]; • At all times, the number of blocks is given by the number of empty places. Thus, for 0 ≤ m ≤ n-1, when m cars parked, there are exactly n-m blocks which we denote by I[m] := (I m j , 1 ≤ j ≤ n-m). Notice that I[m] forms a partition of [1, n]: the total block sizes sum to n for any m, since at each step an empty place is replaced by an occupied one. Write now

|I[m]| for the multiset {|I m j |, 1 ≤ j ≤ n -m}.
There is some slight difference between the above definition and the original one in [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF]. Namely, here the block size is 1 plus the number of the cars in it. Thanks to this small modification, we have an exact correspondence between the parking scheme and the additive coalescent (this point is also discussed in [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF]Section 8].) To state the correspondence, we need the following notation. For a partition π

= (π 1 , • • • , π k ) of [n], denote by |π| the multiset {|π j |, 1 ≤ j ≤ k}.
Proposition 12. [Chassaing & Louchard [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF]] The block sizes in the parking scheme evolve in the same way as the cluster sizes in the additive coalescence:

(|I[k]| , 0 ≤ k ≤ n -1) (d) = Π + k , 0 ≤ k ≤ n -1 . (13)
Let us mention that the proof we propose for Proposition 17 also uses ideas from Chassaing & Louchard [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF].

Remark 13. An alternative description for the evolution of the block sizes can be given as follows.

For m varying from 0 to n -2, • let j ∈ {1, . . . , n -m} be the index such that C m+1 ∈ I m j and let I be the interval which is at the right of I m j on the circle; • merge I m j and I and relabel the intervals from 1 to nm -1.

Chassaing & Louchard remarked a connection between their parking scheme with Pavlov forests. Let us briefly explain this connection. For 1 ≤ m ≤ n -1 and 1 ≤ i ≤ n, let

C m i = {j : C j = i, 1 ≤ j ≤ m} (14)
be the set of cars among the first m ones that have chosen the place i (and then parked at some position after i on the circle). By construction, the distribution of (#C m i ,

1 ≤ i ≤ n) is multinomial: for a vector of non negative integers (c i , 1 ≤ i ≤ n) satisfying 1≤i≤n c i = m, P(#C m i = c i , 1 ≤ i ≤ n) = m c 1 , • • • , c n /n m . (15)
Set

S m k := k i=1 (#C m i -1) , for 0 ≤ k ≤ n, (16)
which is a "bridge" process with exchangeable increments. This is reminiscent of the Lukasiewicz walk for Poisson Galton-Watson forests. Indeed, under the "excursion condition" (ExcCond) :

S n-1 k ≥ 0, for 0 ≤ k ≤ n -1 and S n-1 n = -1, (17)
(S n-1 k , 0 ≤ k ≤ n)
has the same distribution as the Lukasiewicz walk of a Poisson Galton-Watson tree conditioned to have size n.

On the other hand, by employing a cyclic permutation (see Remark 16 below for more details), we have the following. Proposition 14 (Chassaing & Louchard [13]). ( 13) also holds true conditionally on (ExcCond).

One may associate bijectively a tree with the state of the parking at time n -1, as follows. The root of the tree is a node labelled 0. For 1 ≤ i ≤ n, C n-1 i is the set of the labels for the children of the ith node (in depth-first order); so in particular, the ith node has #C n-1 i children. See Fig. 3 for an example. In a similar way, when only m cars have parked, the sequence (C i , 1 ≤ i ≤ m) In the first picture, the numbers above the interval i, from bottom to top, are the successive labels of the cars which have chosen place i upon arrival (e.g. the cars 1, 3 and 8 arrive successively at place 4). The middle one is an illustration of the different tries of each car before finding a free place. The blue cases correspond to the state of the system when the first 5 cars have parked. The corresponding Pavlov forest is depicted in blue on the left in the last line, while the right tree is the final tree in correspondence with the parking scheme.

encodes a Pavlov forest with nm components (which is a forest of nm trees whose roots are labelled by r 1 , • • • , r n-m and whose non-root nodes are labelled by [m]), 1 ≤ m ≤ n -1 (see also Fig. 3).

Even if the combinatorial correspondence explained above is exact, one may say it is not really satisfactory in the sense that in the additive coalescent, what we add as time passes are edges, and not nodes ! For this reason, one might expect (C i ) to encode rather edges than nodes. In what follows we explain how to realize this combinatorial encoding.

A new connection via an enriched parking process

The number of different parking histories is given by the number of vectors (C i , 1 ≤ i ≤ n), which is n n-1 . A simple counting argument shows that standard parkings can not faithfully encode the process (

F PF k , 1 ≤ k ≤ n -1), nor ((F SC k , L SC k ), 1 ≤ k ≤ n -1)
. Indeed, the number of different forest histories is :

• n n-1 (n -1)! for (F PF k , 1 ≤ k ≤ n -1)
since this is the number of different choices for the directed added edges,

• n!(n -1)! for ((F SC k , L SC k ), 1 ≤ k ≤ n -1)
for the same reason, • to encode the additive coalescent, the pairs of blocks that merge at each moment need to be encoded, so that the number of histories is n!(n -1)!/(2 n-1 ).

Therefore, we need to enrich the parking structure in order to encode the forests processes or the coalescent. We opt for an encoding which brings an extra factor (n -1)! compared to the usual parking scheme. This richness is needed to encode Pitman's forests process. It is also sufficient to encode not only the ((F SC k , L SC k ), 1 ≤ k ≤ n -1) structure but also the randomness needed to build it. To be more precise, we will consider some enriched parking schemes which bring an extra factor n!; the superfluous factor n is then taken care of by considering the rotation equivalence classes of the parkings (see Remark 16).

Encoding of additive coalescent by an enriched parking process

To produce an enriched parking process, we take here as data a pair (σ, (C i , 1 ≤ i ≤ n -1)) where as previously (C i , 1 ≤ i ≤ n -1) is a vector taken in [n] n-1 and σ is a permutation taken in S[n], the symmetric group over [n].

Enriched parking algorithm.

-Run the parking algorithm defined in Section 2.5 using the sequence

(C i , 1 ≤ i ≤ n -1) and obtain a sequence (I[m], 0 ≤ m ≤ n -1) of partitions of [n]. -For 0 ≤ m ≤ n -1, define CC m j := {σ i , i ∈ I m j } and CC[m] = {CC m j , 0 ≤ j ≤ n -m}, (18)
the connected components at time m.

For each m, CC[m] is a partition of [n].
In the enriched parking, I[m] encodes the connected components but are not themselves connected components, this being taken by CC[m]: the parking places are still labelled from 1 to n, but the ith place of the parking corresponds to the element/node σ i . For those CC m j defined in ( 18), we will sometimes say that CC m j is above I m j . In the sequel we will consider the case that the C 1 , • • • , C n-1 are i.i.d. random variables uniformly distributed in [n], and that σ ∼ Uniform (S[n]) and independent from the C i 's. In particular, this will ensure the exchangeability of the parking blocks in our construction.

Note 15. As in Note 11, it is convenient to consider that (σ, (C 1 , • • • , C n-1 )) are defined on a probability space (Ω EPar , A EPar , P EPar ) where Ω EPar = [n] n-1 × S[n], A EPar = Powerset(Ω EPar ), and P EPar is the uniform distribution on Ω EPar . On this space, the functions C i are defined by

C i (ω × ω ) = π i (ω) (the extraction of the ith coordinate "of the [n] n-1 component"), σ(ω × ω ) = ω .
Hence, the C i 's and σ are random variables on this space, and the other quantities defined in the algorithms (for example CC[m]) are also random variables defined on this probability space.

Remark 16. [Equivalence classes of enriched parkings] Let us say that two pairs of data (σ, (C

i , 1 ≤ i ≤ n -1)) and ( σ, ( C i , 1 ≤ i ≤ n -1)) are equivalent if there exists some k ∈ [n] such that σ k + j = σ(j), for any j ∈ [n], k + C j = C j , for all 1 ≤ j ≤ n -1. ( 19
)
Then each equivalence class contains exactly n elements. To distinguish, we add a to the variables CC[m], C m i and S m i which are defined using ( σ, ( C j , 1 ≤ j ≤ n -1)). It is clear that

CC[m] = CC[m], for 0 ≤ m ≤ n -1.
Namely, equivalent data produces same connected component processes, since their enriched parking processes are equal up to a rotation. Moreover, by taking k = min{j ∈ {1, • • • , n} : S n-1 j = min S n-1 }, we find exactly one pair of (σ, (C j , 1 ≤ j ≤ n -1)) in each equivalence class for which (ExcCond) is obeyed. This trick is classical and sometimes referred to as the rotation principle or the cyclic lemma in the literature (see Dvoretzky & Motzkin [15]). In particular, conditioning on (ExcCond) does not change the distribution of (CC[m], 0 ≤ m ≤ n -1) by the previous argument (a parking under condition (ExcCond) is called "confined parking sequence" in [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF].)

Notice that the block sizes (|I[m]|, 0 ≤ m ≤ n -1) are the same for the parking algorithm and for the enriched version, so that Propositions 12 and 14, as well as the representation provided by Remark 13 hold for the enriched version. In contrast to |I[m]|, which are just some interval lengths, CC[m] are partitions, with exchangeable elements. As a consequence, we have the following, which reinforces Propositions 12 and 14.

Proposition 17. The following distributional equality holds

(CC[m], 0 ≤ m ≤ n -1) (d) = (Π + m , 0 ≤ m ≤ n -1). ( 20
)
Further, (20) also holds conditionally on (ExcCond). . By the definition of Π + , this will entail [START_REF] Kaigh | An invariance principle for random walk conditioned by a late return to zero[END_REF]. Intuitively, the proof is the same as that of Proposition 12 since its relies on an exchangeability property in the parking. In [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF], a counting argument in provided. Here, we will instead, detail a symmetry argument.

First, notice that the sequence of connected components (CC m j , 1 ≤ j ≤ n-m) may be equipped with a total order inherited from the order between their minimal elements: CC m j < CC m i ⇔ min(CC m j ) < min(CC m i ). Up to a relabelling of the CC[m], we may and will assume that the index j in (CC m j , 1 ≤ j ≤ nm) corresponds to the rank in this order. Recall that the CC m j 's correspond to some intervals I m j 's (we said the CC m j were above them). For any [1, n], and such that |I j | = s j for any j. The formula,

s 1 , • • • , s k positive integers summing to n, let X[s 1 , • • • , s k ] be the set of k-tuples (I 1 , • • • , I k ) of intervals that forms a partition of
#X[s 1 , • • • , s k ] = nk!/k = n(k -1)! ( 21
)
comes from the fact that given the sizes of the intervals, their respective order around the circle is given by a permutation considered up to a rotation (this provides the factor (k -1)!), and then their position along the circle is specified by fixing the position of the first one, which gives the additional factor n. Now, we claim that the distribution of

I[m] := (I m j , 1 ≤ j ≤ m) conditionally on CC[m] is uniform in X |CC m 1 |, • • • , |CC m n-m | : for any element I [n-m] := (I j , 1 ≤ j ≤ n -m) in this set P I[m] = I [n-m] CC[m] = 1 n(n -m -1)! . ( 22
)
This can be proved by computing the number of pairs (σ, (C j , 1 ≤ j ≤ m)) for which the partitions above a sequence of intervals

I [n-m] ∈ X |CC m 1 |, • • • , |CC m n-m
| are exactly the CC m j 's, and to see that this number is the same for any [START_REF] Gall | The uniform random tree in a Brownian excursion[END_REF], we can just show that the number of pairs (σ, (C j , 1

I [n-m] in this set. But since (σ, (C j , 1 ≤ j ≤ m)) is uniformly distributed on S[n] × [n] m , to prove
≤ j ≤ m)) ∈ S[n] × [n] m which produce CC[m] above I [n-m] are above I [n-m] are the same for any I [n-m] , I [n-m] ∈ X |CC m 1 |, • • • , |CC m n-m | .
A symmetry argument suffices: -first, σ and (C j , 1 ≤ j ≤ m) are both invariant by translation:

((σ i , 1 ≤ i ≤ n), (C i , 1 ≤ i ≤ n)) (d) = (1 + σ i , 1 ≤ i ≤ n), (1 + C i , 1 ≤ i ≤ n) .
-second, the probability of an interval configuration is unchanged if we permutate two adjacent intervals: consider two consecutive intervals

I = [a, b -1], I = [b, c] and the map f defined by f (x) = x if x / ∈ I ∪ I , f (x) = a + x -b if x ∈ I , f (x) = x + c -b if x ∈ I, then again ((σ i , 1 ≤ i ≤ n), (C i , 1 ≤ i ≤ n)) (d) = (σ f (i) , 1 ≤ i ≤ n), (C f (i) , 1 ≤ i ≤ n) .
These two properties ensure that the intervals below the CC[m] are exchangeable, and invariant by translation.

Next, in the enriched parking algorithm, two blocks CC m j and CC n i will be merged if the corresponding intervals I m i and I m j are neighbors and if C m+1 falls in the first one (around the circle). Since [START_REF] Gall | The uniform random tree in a Brownian excursion[END_REF] implies that I m j being next to I m i takes place with probability 1/(nm -1). Taking into account that I m j can be to the left or to the right of I m i , we find that C m+1 will produce a merging of I m j and

I m i with probability (|I m j | + |I m i |)/(n(n -m -1)), that is, proportional to (|I m j | + |I m i |).
Finally, (20) also holds conditionally on (ExcCond), since we have seen in Remark 16 that the conditioning does not change the distribution of (CC[m], 0 ≤ m ≤ n -1). Now, we introduce two constructions of graphs where CC[m] will appear as vertex sets of the connected components there. In consequence, we obtain, on the probability space where (C i , 1 ≤ i ≤ n -1) and σ are defined, a coupling between the enriched parking process, Pitman's forests (F PF k , 0 ≤ k ≤ n -1) and the forests with decreasing labelling ((

F SC k , L SC k ), 0 ≤ k ≤ n -1).

Encoding of Pitman forest

For 0 ≤ m ≤ n -1, we associate with the partition CC[m] defined in [START_REF] Fournier | Well-posedness of Smoluchowski's coagulation equation for a class of homogeneous kernels[END_REF] a forest belonging to F n-m,n , whose tree components induce the same partition of [n] as CC[m]. We then show that the sequence of the forests is distributed as

(F PF k , 0 ≤ k ≤ n -1). Recall that σ ∼ Uniform (S[n]) and C i , 1 ≤ i ≤ n -1, are i.i.d. uniformly distributed in [n]
. For a circular interval I, set L(I) to be its leftmost element of I, which is the element ∈ I such that -1 ∈ I. At the beginning the intervals I 0 j 's are the trivial intervals [j, j] for 1 ≤ j ≤ n.

Algo 1.

For m varying from 0 to n -2, do the following:

-Let j ∈ {1, . . . , n -m} be the index such that C m+1 ∈ I m j and let I be the next one on the circle.

-Add an edge from σ L(I ) to σ C m+1 and label it m + 1 (see the second line in Fig. 4 for an example).

-Relabel the intervals from 1 to nm -1.

= C 3 = C 8 = 4, C 2 = 3, C 4 = 5, C 5 = C 6 = 1, C 7 = 7.
In the second line, an illustration for constructing Pitman's forest: add an edge between σ Cm+1 and the left endpoint of the next interval. Turn the picture clockwise by π/2 degrees and obtain the final tree of Pitman's forest. Discarding the edges with labels > m gives the forest after m coalescences. In the third line, the illustration for the construction of T SC : add an edge between the right endpoint of the connected component containing σ Cm+1 and the right endpoint of the next interval. Turn the picture clockwise by π/2 degrees and obtain the canonical planar embedding of a rooted tree equipped with decreasing edge-labels. Discarding the edges with labels > m gives the corresponding forest after m coalescences. The left-depth first traversal of the tree is given by (σ 9 , σ 8 , . . . , σ 1 ). Observe that the connected components of both constructions induce the same partitions of the nodes.

It is easy to see that Algo 1 produces an increasing sequence of forests, since the edges go from right to the left and only at most one outgoing edge comes out at each position. Proposition 18. Algo 1 produces a sequence of labelled forests which has the same distribution as (F PF k , 0 ≤ k ≤ n -1) introduced just above Theorem 2[[29], Theorem 4]. Denote this sequence of forests also by (F PF k , 0 ≤ k ≤ n -1). If we write CC(F PF k ) for the partitions induced by the connected components of

F PF k , we get (CC(F PF k ), 0 ≤ k ≤ n -1) = (CC[k], 0 ≤ k ≤ n -1).
Proof. This is an immediate consequence of the fact that Algo 1 encodes exactly Pitman construction of (F PF k , 0 ≤ k ≤ n -1) using a linear parking. To figure out this fact, observe Fig. 4. At time 0, no edge is present, each node σ j is considered alone. The addition of edges produces block mergings, but at any time m, each block b corresponds to a tree t, and the leftmost node u of b is the root of t. Step 2 of Algo 1 conserves this property all along the construction. Now let us work only on the set of trees f m = {t 1 , • • • , t n-m } present at time m, and consider an edge addition. The node σ C m+1 is uniform on the set of nodes. It corresponds then to the choice of the uniform node α PF m+1 in the Pitman forest. Now, [START_REF] Gall | The uniform random tree in a Brownian excursion[END_REF] in the proof of Proposition 17 implies that σ L(I ) , which is the tail of the edge to be added, is distributed as the root of a uniform tree in the remaining forest, namely, it has the same distribution as β PF m+1 .

Encoding of the forests with decreasing labellings

Recall that (CC[k], 0 ≤ k, ≤ n -1) has been defined in Section 2.6.1 using σ ∼ Uniform (S[n]) and C i , 1 ≤ i ≤ n -1, i.i.d. and uniformly distributed in [n]. We construct a sequence of forests such that CC[k] appear as the vertex sets of the connected components in the kth forest. And we will see that the sequence coincides in distribution with ((

F SC k , L SC k ), 0 ≤ k ≤ n -1) as defined in Section 2.1.
For a circular interval I, let R(I) be its rightmost element, i.e. the element r ∈ I such that r + 1 ∈ I. At the beginning the intervals I 0 j are the trivial intervals [j, j] for 1 ≤ j ≤ n.

Algo 2.

For m varying from 0 to n -2 do the following:

-Let j ∈ {1, . . . , n -m} be the index such that C m+1 ∈ I m j , and let I be the next one around the circle.

-Add an edge from σ R(I m j ) to σ R(I ) and label the edge m + 1. -Relabel the intervals from 1 to nm -1.

Again, it is easy to see that Algo 2 produces an increasing sequence of forests, since the edges go from left to the right and only at most one outgoing edge comes out at each position. Further, since added edges are labelled from the first one 1 to the last one n -1, the forests constructed are at each moment equipped with a decreasing edge-labelling. Proposition 19. Algo 2 produces a sequence of labelled forests which has the same distribution as ((F SC k , L SC k ), 0 ≤ k ≤ n -1) described in Section 2.1. Denote this sequence of forests also by

((F SC k , L SC k ), 0 ≤ k ≤ n -1
). If we write CC(F SC k ) for the partitions induced by the connected components of F SC k , we get (CC(

F SC k ), 0 ≤ k ≤ n -1) = (CC[k], 1 ≤ k ≤ n -1).
Proof. Again this is a consequence of the fact that Algo 2 is just a linear encoding of the construction of (F SC k , 0 ≤ k ≤ n -1). As in the proof of Proposition 18, observe Fig. 4. All along the construction, each block I in the parking corresponds to a tree. The set {σ i , i ∈ I} coincides with the vertex sets of the corresponding tree, and moreover, σ R(I) , "the right most node of each block" is the root of the corresponding tree (this property is guarantied by the second point of Algo 2). The rest of the proof can be easily adapted from that of Proposition 18.

Trees with decreasing labellings and canonical orderings

We may define several orders on a Cayley tree equipped with a decreasing edge-labelling (T, L). Using the edge labelling, we may order the edge-children of each node. This induces an order on the nodes, that we call, canonical order. Using this order, we can "draw" a tree in the plane, drawing the in-going edges of each node in such a way that the edge labels are increasing from left to right. Call this the canonical embedding of T and denote it by Can(T, L). Then the depth-first search of Can(T, L) defines a linear order on the nodes of T which we call the left-depth first traversal of T . Algo 2 produces a decreasing tree with a given left-depth first traversal. Indeed, using the fact that in Algo 2 edges are always added between the right endpoints of two neighboring intervals, one can readily check that the left-depth first traversal of the tree T SC defined by Algo 2 is given by (σ j 0 +1-j , 1 ≤ j ≤ n), where σ j 0 is the root of T SC (see the last line in Fig. 4). This leads to the following.

Proposition 20. Let T ∈ F 1,n and L ∈ DL(T ). The number of elements (σ, (C j , 1 ≤ j ≤ n -1)) ∈ Ω Epar (see Note 15) which produces (T, L) in Algo 2 is given by n u∈T \{r(T )} |Sub u (T )|.

Notice that the arguments in Remark 16 also entail that elements in the same rotation class produce the same sequence ((F SC k , L SC k ), 0 ≤ k ≤ n -1) in Algo 2 . Thus, the number of rotation classes that are sent onto (T, L) by Algo 2 is u∈T \{r(T )} |Sub u (T )|. This is consistent with Lemma 5 which says that #DL(T ) = (n -1)!/ u∈T \r(T ) |Sub u (T )| so that the total number of rotation classes is indeed (n -1)!n n-1 as expected.

Proof. Since elements in the same rotation class produce the same (T SC , L SC ) by Algo 2, consider the unique element (σ, (C i , 1 ≤ i ≤ n)) of the rotation class such that the root of T SC is σ n . In this case, Algo 2 produce (T, L) from (σ, (C i , 1 ≤ i ≤ n)) if and only if σ C j ∈ Sub u j (T ) where u j is the node from which the edge labelled j is directed, for 1 ≤ j ≤ n -1. As each non-root node of T appears once in (u j , 1 ≤ j ≤ n -1), we easily conclude.

We may explain a bit further, the link between (T SC , L SC ) and (σ, (C j , 1 ≤ j ≤ n)), in describing precisely where the (m + 1)th edge is added. Recall that C m j = {j :

C j = i, 1 ≤ j ≤ m} and that S m k = k i=1 (#C m i -1)
. We further suppose (ExcCond). We recognize (S m k , 0 ≤ k ≤ n) as the Lukasiewicz walk for Pitman's forest F PF m . Under the condition (ExcCond), the partition I[m], which encodes the connected components of F PF m , corresponds to the excursion intervals of S m -S m , where S m j := min{S m i : i ≤ j}. But F PF m and F SC m share the same connected components by construction. It follows that the rightmost node of the block which contains C m+1 is σ R m+1 where R m+1 := min{j ≥ C m+1 : S m j = S m j }. Similarly, the rightmost node of the next block is given by σ R m+1 , where

R m+1 := min{j ≥ R m+1 + 1 : S m j = S m j }.
Then the edge labelled m + 1 is from σ R m+1 to σ R m+1 .

Coupling between

(F PF k , 0 ≤ k ≤ n -1) and ((F SC k , L SC ), 0 ≤ k ≤ n -1)
Everything has already been said on this point. We collect in this section some simple facts spread throughout the paper.

In Sections 1.1 and 1.2, the two processes

F PF [n -1] = (F PF k , 0 ≤ k ≤ n -1) and F L SC [n -1] = ((F SC k , L SC k ), 0 ≤ k ≤ n -1
) have been defined using respectively (α SC k , β SC k ) and (α PF k , β PF k ). In Sections 2.6.2 and 2.6.3, relying on the enriched parking scheme and using as data (σ, (C i ) 1≤i≤n-1 ) ∼ Uniform(S[n] × [n] n-1 ), we obtain an alternative construction of

F PF [n -1] (resp. of F L SC [n -1]).
It follows that both F PF [n -1] and F L SC [n -1] are defined on the same probability space where (σ, (C i ) 1≤i≤n-1 ) is defined. Observe that this coupling between F PF [n-1] and

F L SC [n-1] amounts to -taking α SC k = α PF k , -taking β SC
k to be the root of the tree in F SC k which contains the node with label β PF k . We assume from now on that F PF [n -1] and F L SC [n -1] are coupled in this way. Observe that at each instant, the partitions induced by the both forests coincide, and new edges are added between the same pairs of connected components.

The information contained in F L SC [n -1] is not sufficient to reconstitute the rotation class of (σ, (C j , 1 ≤ j ≤ n -1)). The reason is that since we add the edge between the roots of trees, then the α SC k 's (which corresponds to the C i 's) can not be recovered from F L SC [n -1]. Notice that F PF [n -1] is a sequence of forests without edge-labelling. On the other hand, since the difference between F PF k and F PF k-1 is the added edge at time k, this process allows one to recover the sequence

((α SC k , β SC k ), 1 ≤ k ≤ n -1). Hence, F PF [n -1] characterizes F L SC [n -1]
, but the converse is false. Nevertheless, the distribution of F PF [n-1] knowing F L SC [n-1] can be described : assume that we have been able to construct a sequence of forests (F PF k , 0 ≤ k ≤ m) thanks to ((F SC k , L SC k ), 0 ≤ k ≤ m) for some m, such that both forests have the expected distribution. Assume moreover that the partition induced on [n] by these forests coincides at time m (at time 0, the property is clear). Now, observe in (F SC m+1 , L SC m+1 ) the edge labelled m + 1. Its goes from the root u k of a tree to the root v k of another tree. By construction, we know that u k = r(α SC k ), and v k = β SC k . Consider in F PF m the trees t k which contains u k , and t k which contains v k (recall that the nodes are labelled). To construct F PF m+1 , add an edge from the root of t k to the node w k chosen uniformly in t k .

Asymptotics

The asymptotic of additive coalescent processes is known to be described by the Brownian excursions as follows. Let e = (e(x), 0 ≤ x ≤ 1) be the normalized Brownian excursion of length 1, and consider the operator

Ψ : C[0, 1] -→ C[0, 1] f -→ Ψ(f ) : [0, 1] -→ R + x -→ f (x) -min{f (y), y ≤ x} . (23)
For any λ ≥ 0, let e λ be the process

e λ (x) = e(x) -λx, x ∈ [0, 1]. ( 24
) Let f ∈ C[0, 1]. An interval I = [a, b] with b > a is said to be an excursion of f above its minimum if b = inf{t > a, f (t) = f (a)} and if f (a) = f (b) = min{f (t), t ≤ b}.
Let EL ↓ (f ) be the sequence of excursion lengths of f above its minimum, sorted in decreasing order, and completed by an infinite list of zeros (if the number of excursions is finite). Denote by γ + (λ) the sequence of lengths of excursions of Ψ(e λ ) sorted in decreasing order so that γ + (λ) ∈ 1 ↓ , defined in [START_REF] Aldous | The standard additive coalescent[END_REF]. Consider for n fixed and for any λ > 0, the sequence γ n (λ) defined as the rearrangement of CC n-λ √ n j /n, 1 ≤ j ≤ λ √ n in decreasing order. This finite sequence completed by a sequence of zeros, is considered as an element of 1 ↓ .

Theorem 21. The following convergence holds in

D [0, +∞), 1 ↓ (γ n (λ), λ ≥ 0) (d) ---→ n→∞ γ + (λ), λ ≥ 0 . (25)
Several proofs of this theorem already exist in the literature. Evans & Pitman [START_REF] Evans | Construction of Markovian coalescents[END_REF] showed that the additive coalescent process is a Feller Markov process. Aldous & Pitman [START_REF] Aldous | The standard additive coalescent[END_REF] gave a description of the fragmentation associated with the additive coalescent by studying the fragment sizes of a cutting process on the Brownian CRT (however, no connection was made yet with e λ ). The above representation of the standard additive coalescent in terms of the excursion lengths of (e λ , λ ≥ 0) first appear in two almost simultaneous papers : Bertoin [START_REF] Bertoin | A fragmentation process connected to brownian motion[END_REF] who discusses only the continuous case, and Chassaing & Louchard [START_REF] Chassaing | Phase transition for parking blocks, brownian excursion and coalescence[END_REF] already discussed in the paper, who deals with the parking scheme and prove a limit theorem (but only for the finite dimensional distribution).

In Broutin & Marckert [START_REF] Broutin | A new encoding of combinatorial coalescent processes[END_REF], the edges (e ∈ E(T )) of a uniform Cayley tree T are labelled by some i.i.d. uniform random variables U [T ] = (U e , e ∈ E(T )) on [0, 1]. Denote the forest F n (t) obtained by discarding the edges with label greater than t. The process (F n (t), t ∈ [0, 1]) coincides with the additive coalescent, up to a time change. In [START_REF] Broutin | A new encoding of combinatorial coalescent processes[END_REF], it is explained that the Prim order on the tree T equipped with U [T ] can be used to defined a traversal of T , and further a parking process. The block sizes in the parking is then a faithful encoding of the tree sizes in the forest process F n (t), and the coalescence coincides with the coalescence of adjacent parking blocks.

In Propositions 18 and 19, we observed that each of PF Algo and SC Algo provides a coupling between a parking process and some process of coalescing forests. The three processes, in turn, encode the additive coalescent. However, the fact that the parking/forest constructions do not need a pre-labelling of the edges of T makes of our present construction a structure a bit more easy to handle than that in [START_REF] Broutin | A new encoding of combinatorial coalescent processes[END_REF], at least for the asymptotic behavior. For sake of completeness, but also to illustrate the advantage obtained in terms of argument concision, we provide a short proof of Theorem 21 below.

Consider again the random walk (S n-1 k , 0 ≤ k ≤ n) defined in [START_REF] Evans | Construction of Markovian coalescents[END_REF], conditional on (ExcCond).

Remark 22. In fact, the condition (ExcCond) is needed here contrary to most of the places in the paper, because under this condition, the excursions length of S m above its current minimum coincide with the connected component sizes, while it would be false -because of the first and last excursion -without this condition.

First, recall the following classical result due originally to Kaigh [START_REF] Kaigh | An invariance principle for random walk conditioned by a late return to zero[END_REF]. Conditional on (ExcCond):

1 √ n S n-1 nt t∈[0,1] (d) ---→ n→∞ e in C([0, 1], R), (26)
where S n-1 , as well as the other processes S m that will be considered below, is interpolated between integer points. Recall that C m j = {i :

C i = j, 1 ≤ i ≤ m}. Clearly, #C m j is non decreasing in m for any j. Let D m j = j i=1 #C n-1 i -#C m i , for any j ∈ {0, • • • , n},
Notice that D m j , conditional on {C n-1 i , 1 ≤ i ≤ n} is hypergeometrically distributed :

P D m j = k | #C n-1 i , 1 ≤ i ≤ n = j+S n-1 j k n-1-j-S n-1 j n-m-k n-1 n-m . ( 28
)
The formula comes from the fact that j+S n-1 j = j i=1 #C n-1 i and n-1-j-S n-1 j

= n i=j+1 #C n-1 i . Set s n,λ (t) := 1 √ n S n-λ √ n nt , λ ≥ 0, t ∈ [0, 1]. ( 29
)
where the discrete process (S y x , 0 ≤ x ≤ m, 0 ≤ y ≤ n -1) is obtained by interpolating S m k , first "in k" between integer points, and then in m between integer points, in order to get a process continuous at the end.

There are two arguments: -First, since t → D n-λ √ n nt is non decreasing, the convergence in the uniform topology will follow from the pointwise convergence (this is a consequence of Dini's theorem).

-For fixed t, the convergence (in distribution) of D n-λ √ n nt to λt is a combined consequence of the hypergeometric representation [START_REF] Panholzer | Cutting down very simple trees[END_REF] and the tightness of S n-1 nt / √ n (implied by ( 26)). By ( 26), ( 27) and ( 31

On the probability space we are working in, the limit depends only on the limit e, the a.s. limit of s n,0 . In other words, conditional to this limit, the limit of s n,λ is deterministic, so that the uni-dimensional a.s. convergence stated in [START_REF] Smoluchowski | Drei Vortrage uber Diffusion, Brownsche Bewegung und Koagulation von Kolloidteilchen[END_REF] implies the following joint convergence: for any 0 = λ 0 ≤ λ 1 ≤ • • • ≤ λ k one has s n,λ j (t) t∈[0,1] , 0 ≤ j ≤ k (as.)

---→ n (e λ (t)) t∈[0,1] , 0 ≤ j ≤ k .

This time, using the continuity and monotonicity of the limit in λ, we conclude.

Proof of Theorem 21. The sizes of the excursions of s n,λ (t) above its running minimum do not exactly correspond to the component sizes of (|CC We denote by EL ↓ n (f ) be the list of excursion lengths of f above its minimum, for this definition, sorted in decreasing order.

Consider again the convergence stated in [START_REF] Pitman | Combinatorial stochastic processes[END_REF] and assume that we are still working on a probability space on which this convergence holds a.s.. For any λ ≥ 0, let

This convergence is a bit weaker than the conclusion of Theorem 21. It is somehow similar to the convergence of finite dimensional distributions, even if the set of λ ∈ [0, a] for which the condition removing all the edges with labels > k. Let us mention that the construction in Section 2.3 implies that (F SC n-1-k , 0 ≤ k ≤ n -1) is a Markov chain. However, this fact is not used in the rest of this part. What is useful here is the following simple observation. During the fragmentation process (F SC n-1-k , 0 ≤ k ≤ n -1), along each branch B of T SC , edges are removed in the same order, that is, independently of the choice of L SC : among the set of edges of B, the first removed edge is incident to the root, then the edge incident to this edge, etc. In analogy to the random cutting problem, let us define for each vertex v ∈ [n],

X SC (v) := # k ∈ {1, . . . , n -1} :

π SC n-1-k (v) = π SC n-k (v) , (39)
where π SC k (v) is the vertex set of the tree component of F SC k (v) which contains v, 0 ≤ k ≤ n -1. We have the following.

Lemma 24. For the coalescent forests (F SC n-1-k , 0 ≤ k ≤ n-1) defined by the SC Algo and X SC (v) defined in (39), we have for all v ∈ [n],

X SC (v) = H SC (v) + D SC (v), ( 40
)
where H SC (v) denotes the height of v in T SC , namely, the number of edges on the unique path of T SC from the root to v, and D SC (v) denotes the in-degree of v in T SC . Moreover, under the coupling in Section 2.8, we have

X PF (v) = X SC (v), for all v ∈ [n]. (41)
Proof. For the first statement, observe that in the sequence (F SC n-1-k , 0 ≤ k ≤ n -1), the vertex v is isolated after each edge on the path between the root and v is removed (in the order from the root towards v) and also all the in-going edges of v are removed (in the order determined by L SC ). This easily leads to (40). Next, in the coupling of Section 2.8, we have (Π PF k , 0 ≤ k ≤ n -1) = (Π SC k , 0 ≤ k ≤ n -1). Then comparing the definitions (37) and (39), we get (41).

From Lemma 24, we deduce the convergence of the number of cuts.

Proposition 25. For the coalescent forests (F SC n-1-k , 0 ≤ k ≤ n -1) defined by the SC Algo and X SC (v) defined in (39), we have

max v∈T SC n -1 2 X SC (v) -H SC (v) P ---→ n→∞ 0. ( 42
)
Moreover, for the coalescent forests (F PF n-1-k , 0 ≤ k ≤ n -1) defined by PF Algo and X PF (v) defined in (37), let V n ∼ Uniform([n]) for each n ≥ 1; we have

n -1 2 • X PF (V n ) (d) ---→ n→∞ R, ( 43
)
where R is a Rayleigh variable defined by P(R > r) = exp(-r 2 /2), for r ∈ (0, ∞).

  do the following three steps. (a) Choose a uniform node α PF k in F PF k-1 . Let t k be the tree which contains α PF k . (b) Choose a tree t PF k in F PF k-1 uniformly among the trees different from t k . Denote by β PF k the root of t PF k . (c) Add the directed edge β PF k → α PF k .

Figure 1 :

 1 Figure 1: An example of progressive labelling of the edges by the random walkers. The first edge

k

  be the graph obtained from T by removing the edges of Perc k (T ) (the nodes are kept), and let Π Perc(T ) k be the partition of [n] induced by the vertex sets of the components of T Perc k (see Fig. 2).

Figure 2 :

 2 Figure 2: construction of (Perc k (T ), 0 ≤ k ≤ |T | E ) by successively adding edges to the present cluster (drawn in red). Each time, choose a uniform white edge e and color in red the white edge on the path from e to the root which is nearest to the root.

Figure 3 :

 3 Figure 3: An example of Chassaing & Louchard's construction. In the first picture, the numbers above the

Proof.

  For m ∈ [n -2], let us show that conditional on CC[j], j ≤ m, two blocks CC m j and CC m i of CC[m] merge at time m with probability (|CC m j | + |CC m i |)/(n(n -m -1))

9 Figure 4 :

 94 Figure 4: In the first line, the numbers above σ k are the labels of cars which have chosen the place k. In this example, C 1= C 3 = C 8 = 4, C 2 = 3, C 4 = 5, C 5 = C 6 = 1, C 7 = 7.In the second line, an illustration for constructing Pitman's forest: add an edge between σ Cm+1 and the left endpoint of the next interval. Turn the picture clockwise by π/2 degrees and obtain the final tree of Pitman's forest. Discarding the edges with labels > m gives the forest after m coalescences. In the third line, the illustration for the construction of T SC : add an edge between the right endpoint of the connected component containing σ Cm+1 and the right endpoint of the next interval. Turn the picture clockwise by π/2 degrees and obtain the canonical planar embedding of a rooted tree equipped with decreasing edge-labels. Discarding the edges with labels > m gives the corresponding forest after m coalescences. The left-depth first traversal of the tree is given by (σ 9 , σ 8 , . . . , σ 1 ). Observe that the connected components of both constructions induce the same partitions of the nodes.

  which counts the number of cars which have chosen a place left to j after time m. Then, j ∈ {0, • • • , n}.

Theorem 23 .(

 23 Take some a ∈ (0, ∞) and Λ = [0, a]. Conditionally on (ExcCond),(s n,λ (t)) (t,λ)∈[0,1]×Λ (d) ---→ n→∞ (e λ (t)) (t,λ)∈[0,1]×Λ , (30) in C([0, 1] × Λ, R).Proof. Let us work on a probability space where the convergence in[START_REF] Meir | Cutting down random trees[END_REF] holds almost surely, in other words on this space, s n,0 This space exists thanks to the Skorokhod representation theorem. We claim that, for λ > 0 fixed, in C[0, 1],

  ), we deduce that for a fixed λ, in C[0, 1],(s n,λ (t)) t∈[0,1] (d) ---→ n→∞ (e λ (t)) t∈[0,1] .

  , 1 ≤ j ≤ λ √ n). A slight adjustment has to be made : we say that I = [a, b] is an excursion of s n above its minimum if a, b ∈ {0, 1/n, • • • , n/n}, and if b = inf{t > a, s n (t) = s n (a) -1/ √ n}.

  locm(λ) = {x ∈ [0, 1], e λ has a local minima at x}. (34) If the values of e λ on the set of local minima are different (for x = x ∈ locm(λ), e λ (x) = e λ (x )), then one can prove using the arguments of Aldous [4, Section 2.3] that s n,λ -→ n→∞ e λ ⇒ EL ↓ n (s n,λ ) -→ n→∞ EL ↓ (e λ ) .

The research has been supported by ANR-14-CE25-0014 (ANR GRAAL).

stated above on the local minima, has a.s. Lebesgue measure a. As discussed in Broutin & Marckert [START_REF] Broutin | A new encoding of combinatorial coalescent processes[END_REF]Section 7], to end the proof we may proceed as follows: denote by F k n (λ) the sum of the k largest excursion sizes in s n,λ and F k (λ) the sum of the k largest excursion sizes of e λ . The process F k n (λ) converges simply almost everywhere to F k (λ), and the process λ → F k (λ) is non increasing, càdlàg, which is also the case for λ → F k n (λ). For this class of processes, simple convergence implies convergence in D([0, 1], R), so that

in D([0, a], R K ). The property stated in (35) allows us to conclude.

Dual fragmentation processes and numbers of cuts

In this part, we are interested in the time-reversal of the two forest coalescent processes:

) is a Markov chain whose evolution can be described as follows:

n-k and remove it. This process also comes under the name random cutting problem of uniform Cayley trees, whose study is initiated by Meir & Moon [START_REF] Meir | Cutting down random trees[END_REF]. In this terminology, each edge removal is referred to as a cut on the initial tree F PF n-1 , which reduces

into finer and finer fragments. In [START_REF] Meir | Cutting down random trees[END_REF], Meir & Moon are interested in the number of cuts necessary to isolate a vertex v. More precisely, recall that Π PF k is the partition of [n] induced by the vertex sets of the tree components of

Then the number of cuts necessary to isolate v is the number of cuts which have reduced the tree components containing v during the process

Nowadays, it is well-known from the works [START_REF] Panholzer | Cutting down very simple trees[END_REF][START_REF] Janson | Random cutting and records in deterministic and random trees[END_REF][START_REF] Bertoin | Fires on trees[END_REF], 1] that if we take a random vertex

where R is a Rayleigh variable, i.e. P(R > r) = exp(-r 2 /2), for r ∈ (0, ∞). Here, we propose a simple proof of this fact based on the process (

as explained in Section 2.8. Recall from Section 2.1 the sequence of forests (F SC k , 0 ≤ k ≤ n-1) and the (random) decreasing edge-labelling L SC which encodes the coalescent history. By Theorem 6, the time-reversal process (F SC n-1-k , 0 ≤ k ≤ n -1) can be described as follows: take T SC ∼ Uniform(F 1,n ) and a decreasing edge-labelling L SC ∼ Uniform(DL(T SC )); for 0 ≤ k ≤ n -1, the forest F SC k is obtained from T SC by Proof. Recall from Theorem 6 that T SC is distributed as a uniform Cayley tree of size n. By (40), (42) amounts to saying that

This follows from a result due to Moon [START_REF] Moon | On the maximum degree in a random tree[END_REF], who shows that (log n/ log log n) -1 max v∈T SC D SC (v) converges in probability to 1 (so actually (44) also holds with (log n) -1 instead of n -1/2 ). Now, for the uniform vertex V n , (42) implies that

On the other hand, by Theorem 6, T SC ∼ Uniform(F 1,n ). Then by Aldous [START_REF] Aldous | The continuum random tree. I[END_REF] (see also Le Gall [START_REF] Gall | The uniform random tree in a Brownian excursion[END_REF]), H SC (V n )/ √ n converges in distribution to R. Therefore, X SC (V n )/ √ n also converges to the Rayleigh distribution. Combined with (41) which says that

= X PF (V n ) for all n, this completes the proof of (43).

Finally, let us briefly explain the relation between T SC and the (finite) cut trees, a notion first introduced by Bertoin & Miermont in [START_REF] Bertoin | The cut-tree of large galton-watson trees and the brownian crt[END_REF]. For this, write T PF := F PF n-1 and let the pair (T PF , T SC ) be defined using the coupling in Section 2.8. Then, T SC is slightly different from cut(T PF ), the finite cut tree defined in [START_REF] Bertoin | The cut-tree of large galton-watson trees and the brownian crt[END_REF], which is a 3-regular tree with n leaves. (It is also different from the cut trees defined in [START_REF] Broutin | Cutting down p-trees and inhomogeneous continuum random trees[END_REF], where vertex-cutting rather than edge-cutting is considered.)

On the other hand, for all these different notions of finite cut trees, we find the same limit object (namely, the cut tree of the Brownian CRT) as n → ∞. To be more precise, let T be Aldous' Brownian CRT, which we recall from [START_REF] Aldous | The continuum random tree. I[END_REF][START_REF] Aldous | The continuum random tree. III[END_REF]. Recall from Bertoin & Miermont [START_REF] Bertoin | The cut-tree of large galton-watson trees and the brownian crt[END_REF] the definition of its cut tree, denoted by cut(T ), which is a CRT depending in a measurable way on T and has the same (marginal) distribution as T . Recall from [START_REF] Evans | Probability and real trees[END_REF] the notion of Gromov-Hausdorff topology for compact metric spaces. If (E, d) is a metric space, then for c ∈ (0, ∞), we write cE for the rescaled metric space (E, c • d).

Theorem 26. For each n ≥ 1, let the pair (T PF , T SC ) be defined using the coupling in Section 2.8. Let (T , cut(T )) be the pair of the Brownian CRT and its cut tree. Then,

where the convergence is with respect to the Gromov-Hausdorff topology.

Sketch of proof. For each n ≥ 1, let V n k , k ≥ 1 be an i.i.d. sequence of r.v. distributed as Uniform([n]). Similarly, let V k , k ≥ 1 be an i.i.d. sequence of uniform points of T sampled according to the mass measure of T . Write H n (v) (resp. H(v) and H cut (v)) for the height of a vertex v in T PF (resp. height of a point v in T and the height of a point v in cut(T ).) Then by [START_REF] Bertoin | The cut-tree of large galton-watson trees and the brownian crt[END_REF], we have for each k ≥ 1,

Combined with (42), this then entails that for all k ≥ 1,

where H SC (V n i ) stands for the height of the vertex V n i in T SC . Following the arguments in [START_REF] Bertoin | The cut-tree of large galton-watson trees and the brownian crt[END_REF], we can deduce from this the following convergence:

where the convergence is with respect to the Gromov-Prokhorov convergence (see for example Section 1.4 in [START_REF] Bertoin | The cut-tree of large galton-watson trees and the brownian crt[END_REF] for a definition). Next, we observe that both T PF and T SC are uniformly distributed in F 1,n . By Aldous' Theorem [START_REF] Aldous | The continuum random tree. I[END_REF], both ( 1 √ n T PF , n ≥ 1) and ( 1√ n T PF , n ≥ 1) are tight with respect to the Gromov-Hausdorff topology. If follows that the pairs ( 1√ n T PF , 1 √ n T SC ), n ≥ 1, also form a tight sequence. Combined with (47), this then entails (46) (we refer to [START_REF] Voisin | Convergence of bi-measure R-trees and the pruning process[END_REF] for more details).


Sabra Hamza

Floriane Anstett-Collin

A Birouche

Dynamic sensitivity

come

Context

A dynamic vehicle depends on various subsystems which characterize the vehicle behavior. Each subsystem is described by a mathematical model depending on a significant number of parameters. These parameters are very often uncertain due to a lack of measurements, knowledge due to expert judgment. The uncertainty in the parameters propagates through the model and manifests itself at the model output. In order to understand the vehicle behavior, it is essential to know the parameters responsible for the model output variation. Uncertainty and sensitivity analysis can help to evaluate the impact of this lack of knowledge on the model response ( [START_REF] Saltelli | Sensitivity analysis[END_REF][START_REF] De Rocquigny | Uncertainty in industrial practice[END_REF]). In the literature, sensitivity analysis for dynamical models is not straightforward. In this context, the work presented in this paper investigates a novel technique of global sensitivity analysis for dynamical models. The originality of the method is to use control theory tools for sensitivity analysis purposes. Methodology Consider a dynamical linear system presented in state space form given by:

SY S : ẋ(t) = A(θ)x(t) + B(θ)u(t) y(t) = C(θ)x(t) + D(θ)u(t) (1)
where x(t) ∈ R nx is the state vector, y(t) ∈ R np the output vector, u(t) ∈ R nm the input vector and t ∈ R + refers to the time. A(.) ∈ R nx×nx is the state matrix, B(.) ∈ R nx×np the input matrix, C(.) ∈ R l×nx the output matrix and D(.) ∈ R l×np the feedforward matrix. The vector θ = [θ 1 , . . . , θ n θ ] represents the n θ uncertain parameters. As the parameters θ i are uncertain, they are considered as random variables defined by their probability density function (uniform,Gaussian, etc.). The uncertainty of the parameters is propagated through the model on the output y(t) which becomes also uncertain. The aim is to determine the most influential parameters θ i on the output uncertainty.

The proposed method is based on the analysis of the system energy required to drive a state to a final one by the input. If this energy is minimal, the system is said controllable. Controllability means that the system dynamics can be modified when acting on the input signal u(t). The system energy depends on the uncertain parameters θ. Intuitively, if the parameter variation leads to a significant variation of the energy, it means that this parameter variation acts on the system dynamics and leads to a system that is more or less controllable. In this case, the system controllability is sensitive to this parameter variation and thus this parameter is influential on the system states.

The system energy can be determined through the reachability Gramian ( [START_REF] Moore | Principal component analysis in linear systems : Controllability, observability, and model reduction[END_REF]).

The infinite time reachability Gramian, denoted for short W R (θ), when t f → ∞ is given by:

W R (θ) = lim t→∞ W R (θ, t 0 , t f ) = ∞ 0 e A(θ)t B(θ)B(θ) T e A(θ) T t dt (2)
and it is obtained by solving the continuous-time Lyapunov equation :

A(θ)W R (θ) + W R (θ)A(θ) T + B(θ)B(θ) T = 0 (3)
8th International Conference on Sensitivity Analysis of Model Output, 30 Nov-3 Dec 2016, Reunion Island

The minimal energy allowing to bring a system to a final state x f , since x(t 0 ) = 0, is given by:

u 2 = ∞ 0 u T (t)u(t)dt = x T f W R (θ) -1 x f (4)
The quantity x T f W -1 R x f in (4) represents an hyperellipsoid which includes all the reachable states obtained from the optimal input sequence u opt . This quantity depends on the inverse of the reachability Gramian W -1 R (θ). Each eigenvalue of W -1 R (θ), denoted λ i , corresponds to one system state. In fact, these eigenvalues determine the size of the axes of the hyperellipsoid and the eigenvectors determine its directions. Intuitively, the variation of an influential parameter will lead to a significant change of the dimension of the hyperellipsoid axes (see FIGURE 1). According to (2) and (4), the eigenvalues of W -1 R provide information on how controllable the system is. Higher the eigenvalues are, lower the required energy is and thus more controllable the system is ( [START_REF] Moore | Principal component analysis in linear systems : Controllability, observability, and model reduction[END_REF]). If any λ i = 0, the system is not controllable. In fact, each eigenvalue λ i is a function of the system parameters θ. The eigenvalues represent a measure of the controllability, that is the sensitivity of the system dynamics to variation. In this way, the parameters involved in the expression of the eigenvalues are influential on the system states. If the eigenvalue does not depend on a given parameter, this parameter is not influential on the state variation. From the structural expression of W -1 R (θ), the qualitative influence of the parameters can be deduced. Then, to quantify the individual contribution of each parameter to the variance of the energy u 2 , the Sobol' indices can be computed. The advantage of the proposed approach is that the system energy does not depend on time and is thus scalar. Furthermore, it takes into account the global model behavior. The approach is applied on a bicycle model describing dynamic behavior of the vehicle.

v 2 λ 2 v 1 λ 1 x T W R (θ) -1 x x T W R (θ ± ∆θ) -1 x ±∆θ

Figure 1 -

 1 Figure 1 -Example of second-order system energy variation according to parameters variation.