Sergey Foss

Takis Konstantopoulos

Bastien Mallein

Sanjay Ramassamy

Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models

We consider directed random graphs, the prototype of which being the Barak-Erdős graph -→ G (Z, p), and study the way that long (or heavy, if weights are present) paths grow. This is done by relating the graphs to certain particle systems that we call Infinite Bin Models (IBM). A number of limit theorems are shown. The goal of this paper is to present results along with techniques that have been used in this area. In the case of -→ G (Z, p) the last passage percolation constant C(p) is studied in great detail. It is shown that C(p) is analytic for p > 0, has an interesting asymptotic expansion at p = 1 and that C(p)/p converges to e like 1/(log p) 2 as p → 0. The paper includes the study of IBMs as models on their own as well as their connections to stochastic models of branching processes in continuous or discrete time with selection. Several proofs herein are new or simplified versions of published ones. Regenerative techniques are used where possible, exhibiting random sets of vertices over which the graphs regenerate. When edges have random weights we show how the last passage percolation constants behave and when central limit theorems exist. When the underlying vertex set is partially ordered, new phenomena occur, e.g., there are relations with last passage Brownian percolation. We also look at weights that may possibly take negative values and study in detail some special cases that require combinatorial/graph theoretic techniques that exhibit some interesting non-differentiability properties of the last passage percolation constant. We also explain how to approach the problem of estimation of last passage percolation constants by means of perfect simulation.

Introduction

The well-known Erdős-Rényi graph [START_REF] Bollobás | Random graphs[END_REF] admits a loopless directed version where an edge is oriented according to an a priori order on the set of vertices. We call this a Barak-Erdős graph due to the 1984 paper [START_REF] Barak | On the maximal number of strongly independent vertices in a random acyclic directed graph[END_REF] by Anton Barak and Paul Erdős that studied the size of the maximal subset of vertices with the property that no two of them are connected by a directed path and showed that it grows like the square root of the number of vertices of the graph. One of the most well-studied questions regarding of the Barak-Erdős graph and related models is the maximum path length or the maximum path weight if edges and vertices are given random weights. As such, the question is closely related to last passage percolation (LPP) problems appearing in statistical physics dealing with maximum weight paths in random environments. Motivations for such a quantity come from performance evaluation of computer systems [START_REF] Gelenbe | An approximation of the processing time for a random graph model of parallel computation[END_REF][START_REF] Isopi | Speed of parallel processing for random task graphs[END_REF], from biology [START_REF] Newman | A stochastic theory of community food webs: IV; theory of food chains in large webs[END_REF][START_REF] Cohen | Community area and food chain length: theoretical predictions[END_REF][START_REF] Cohen | Community Food Webs: Data and Theory[END_REF] and from physics [START_REF] Itoh | Continuum Cascade Model: Branching Random Walk for Traveling Wave[END_REF][START_REF] Itoh | Continuum cascade model of directed random graphs: traveling wave analysis[END_REF].

This paper offers a survey of results on the Barak-Erdős graph and related models. Starting from a relatively simple static model, we will see how it relates to discrete and continuous time particle systems and Markov processes and, in particular, to the Infinite Bin Model (introduced in [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF]) that has also appeared in several papers, often in disguise [START_REF] Aldous | The asymptotic speed and shape of a particle system[END_REF], and often arising as a byproduct of other random models. We shall also explore connections with branching processes and random walks. In particular, we will see the emergence of a continuous time branching random walk that is often known as a Poisson-weighted infinite random tree [START_REF] Aldous | The objective method: Probabilistic combinatorial optimization and local weak convergence[END_REF] or Poisson cascade model [START_REF] Itoh | Continuum cascade model of directed random graphs: traveling wave analysis[END_REF] in the statistical physics literature. The growth of the longest path will be explained and various analytical properties of it will be studied. In particular, we will see how the rate of convergence relates to questions around the F-KPP equation [START_REF] Brunet | Shift in the velocity of a front due to a cutoff[END_REF].

We will deal with several stochastic models and notation will be introduced little by little. For now, given an ordered (or partially ordered) set V , let us define -→ G (V, p) to be a random graph on a set of vertices V such that each edge (i, j), where i is smaller than j in the order of V , exists with probability p, independently from edge to edge. Having said that, we shall have the occasion to make p depend on the edge and we shall discuss situations where independence is replaced by invariance under translations.

The paper offers a survey of results aiming at exposing the main ideas. We often (but not always) give proofs, sometimes sketches of them. Our aim is not to provide an exhaustive bibliographical survey but rather an exposition of results, ideas, and main proof techniques, sometimes compromising with a simpler than a more general model.

The first part of Section 2 deals with a random directed graph on Z where the edge probabilities are not even independent but, rather, stationary and ergodic, in some sense. The aim is to show right from the start that the maximum length of all paths from 1 to n satisfies a law of large numbers (LLN), that is, it has a deterministic linear growth rate, denoted by the letter C, and referred to as the last passage percolation constant; this is due to a subadditive ergodic theorem. Throwing in some independence assumptions (but still remaining at a level more general than that of -→ G (Z, p)) shows that a regenerative structure can be obtained: the random graph can be split into independent pieces that occur at a computable rate. The set of the end-vertices of these pieces is called skeleton of the graph. For -→ G (Z, p), the rate λ(p) of the skeleton (plotted in Figure 1) equals ϕ(1 -p) 2 , where ϕ(x) = (1 -x)(1 -x 2 ) • • • , a well-known function that bears Euler's name and has a wealth of combinatorial and number-theoretic interpretations.

The second part of Section 2 explains how to grow -→ G (Z, p) little by little. If we let -→ G n be -→ G ({1, . . . , n}, p) then the sequence ( -→ G n ) is mapped into a Markovian particle system (X n ), where X n can be thought of as a configuration of particles on Z (a balls-in-bins model) that we call Infinite Bin Model (IBM). This was introduced in [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF] where it was shown that it converges in distribution to a stationary state, say X ∞ , a particle configuration supported on the whole of Z. Paper [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF] was mostly concerned with an extension of Borovkov's theory of renovating events [START_REF] Borovkov | Ergodicity and stability theorems for a class of stochastic equations and their applications[END_REF][START_REF] Borovkov | Asymptotic Methods in Queueing Theory[END_REF][START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Foss | On ergodicity conditions in multi-server queues[END_REF]. This approach enabled facilitate good explicit bounds for C = C(p), the LPP constant for -→ G (Z, p).

Rather than repeating the arguments of [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF] we use the IBM derived from -→ G (Z, p) as a motivation for the more general IBM(µ) that is introduced in Section 3: particles are placed on integers so that there is always a front, that is, a largest bin after which there are no particles. A particle is selected according to the distribution µ and the configuration changes by placing a daughter particle one position to its right. This simple particle system and was introduced and studied in detail in [START_REF] Mallein | Barak-Erdős graphs and the infinite bin model[END_REF][START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF]. The techniques and results of these papers are exposed in Sections 3, 4 and 5. A particular instance of the general IBM was considered by Aldous and Pitman [START_REF] Aldous | The asymptotic speed and shape of a particle system[END_REF]. The IBM(µ) travels to the right at asymptotic speed v µ and this is shown in Section 3. If µ is geometric random variable with parameter p then v µ = C(p). The view of the IBM in this part of the survey is that of a symbolic dynamical system. Successive draws of integers from µ are viewed as words from the alphabet of positive integers. Such words can be "k-coupling" in that the content of the k rightmost bins forgets the initial configuration. These are used to show, by coupling, the existence of a stationary version of the IBM(µ). By delving into the structure of specific sets of words, new expressions for v µ can be obtained. Specializing to the µ=geometric(p) case, Section 4 uses these expressions to obtain sharp upper and lower bounds for C(p), which are sequences rational functions that converge to C(p) uniformly over ε ≤ p ≤ 1 for all ε > 0. Moreover, it is shown that C(p) is analytic away from p = 0 and its power series expansion at p = 1 has integer coefficients that admit some combinatorial interpretation.

We then examine the behavior of C(p) in a neighborhood of 0. One one hand, we have that C(p)/p → e, as p → 0, that is C (0) = e. On the other hand, C (0) does not exist. In fact, the convergence of C(p)/p to e is very slow. It was shown in [START_REF] Mallein | Barak-Erdős graphs and the infinite bin model[END_REF] that C(p)/p = e - 1 2 π 2 e(log p) -2 (1 + o(1)), as p → 0. This is explained in Section 5 using somewhat different proofs. We refer to this as "Brunet-Derrida behavior" as this slow convergence phenomenon appeared in the physics literature [START_REF] Brunet | Shift in the velocity of a front due to a cutoff[END_REF] in the following form. Consider the classical F-KPP partial differential equation [START_REF] Fisher | The wave of advance of advantageous genes[END_REF][START_REF] Kolmogorov | Étude de l'equation de la diffusion avec croissance de la quantité de la matière et son application a un problème biologique[END_REF] arising in the modeling of reaction-diffusion systems. This has a traveling wave solution with asymptotically constant speed v ∞ , say. An N -particle stochastic approximation to it is described by a certain model that moves with constant speed v N , say. It was first observed in [START_REF] Brunet | Shift in the velocity of a front due to a cutoff[END_REF] that v N ≈ v ∞ -c(log N ) -2 , and this was later proved rigorously in [START_REF] Bérard | Brunet-Derrida behavior of branching-selection particle systems on the line[END_REF]. The similarity of the two results is not fortuitous. Indeed, the IBM is compared to a branching random walk with selection, that is, by killing particles. Results for the speed and rate of convergence were obtained in [START_REF] Bastien Mallein | N -branching random walk with α-stable spine[END_REF] and these can be used to establish the rate of convergence of C(p)/p → e. We use the so-called Poisson-weighted infinite tree (PWIT) of Aldous and Steele [START_REF] Aldous | The objective method: Probabilistic combinatorial optimization and local weak convergence[END_REF] which, if interpreted time-wise, is a Markovian branching process of immortal particles that reproduce in continuous time. We then produce a novel embedding of the IBM in the PWIT (or, rather, a coupling between the two) which is used to obtain the rate of convergence. In the last part of Section 5 we also take a first look at LPP on random graphs with geometry and present, in passing, some results on shortest paths as well for -→ G ({1, . . . , n}, p n ). We also note that [START_REF] Newman | Chain lengths in certain random directed graphs[END_REF] proved among other results, using branching processes, that if L n is the maximum length of all paths in -→ G ({1, . . . , n}, p n ) with p n → 0 and np n → ∞, then L n /np n → e, as n → ∞, in probability.

In Section 6 we move on to graphs -→ G (Z, p k ) where the probability that an edge between i and i + k exists equals p k , k ∈ N. We take a closer look at the skeleton S and the regeneration properties, exhibiting a construction of elements of S that allows us to study moment properties. In particular, we show that the distance between successive points has a p-th moment if and only if

∞ k=1 k p Q k < ∞, where Q k = (1 -p 1 ) • • • (1 -p k ).
We thus obtain necessary and sufficient conditions for a central limit theorem for the quantity L n in terms of the p k . In particular, a CLT always holds when the p k are identical. The results of 6 have been obtained in [START_REF] Denisov | Limit theorems for a random directed slab graph[END_REF].

Disclaimer: the term CLT (Central Limit Theorem) in this article will refer to a limit obtained by considering deviations from an average behavior of a random sequence, regardless of whether the limit is Gaussian or not.

In Section 7 we consider the graph -→ G (Z × I, p), where I is a partially ordered set, say a finite set I = {1, . . . , M }. Then order Z × I in component-wise fashion and place an edge directed from (u, i) to (v, j) with probability p if (u, i) is below (v, j). More general conditions are studied in [START_REF] Denisov | Limit theorems for a random directed slab graph[END_REF]. We show, in particular, that if L n is the maximum of all paths in [1, n] × I then a CLT holds but the limit is not Gaussian if I has at least 2 points. A functional central limit theorem for the sequence (L [nt] , t ≥ 0 ) of processes establishes convergence to the Brownian LPP process whose marginal has a distribution proportional to the largest eigenvalue of a random M × M GUE matrix. When M = ∞, we have, in particular, the graph -→ G (Z × Z, p). It was shown in [START_REF] Konstantopoulos | Convergence to the Tracy-Widom distribution for longest paths in a directed random graph[END_REF] that a certain scaling of L [nt] yields convergence, in distribution to the Tracy-Widom law F 2 . The proofs here are technical and we only outline the results and refer the reader to [START_REF] Konstantopoulos | Convergence to the Tracy-Widom distribution for longest paths in a directed random graph[END_REF] for details. We point out that in the finite I case there is a way to obtain a skeleton for the graph (by taking the intersection of |I| skeleton sets), whereas in the infinite I case this is not possible.

Section 8 takes a look at a version of the Barak-Erdős graph when random weights are introduced. The material is taken from [START_REF] Foss | Long-range last-passage percolation on the line[END_REF] and [START_REF] Foss | Limiting Properties of Random Graph Models with Vertex and Edge Weights[END_REF]. Even though negative weights on both edges and vertices can be allowed, we focus only in the positive weights case in order to make ideas clear. We measure the weight of a path by the sum of the weights of its edges (and, if vertices have weights too, we add those weights as well; see [START_REF] Foss | Limiting Properties of Random Graph Models with Vertex and Edge Weights[END_REF]). If u is a random variable representing an edge weight, then we show that Eu 2 is required for the law of large numbers, that is, the convergence of W n /n, where W n is the maximum weight of all paths from 1 to n, to a constant C = C(F ) that depends on the distribution F of u. For the CLT, we need Eu 3 < ∞. When Eu 2 = ∞ some new phenomena occur because W n grows faster than linearly. When we put the graph on (1/n)Z we show convergence to a certain random graph whose vertices are constructed by means of i.i.d. uniform random variables.

When weights are introduced one can ask the question of the behavior of C(F ). Deep properties of it have been investigated when F = δ p + (1 -p)δ -∞ . (the case of the standard Barak-Erdős graph) and exposed in earlier sections. Continuity of C(F ) for a large set of distributions F has been investigated in a recent paper by Terlat [START_REF] Terlat | Regularity of the time constant for last passage percolation on complete directed acyclic graphs[END_REF]. In this section we focus exclusively on very simple weight distributions with 2 atoms: F = pδ 1 + (1 -p)δ x . That is, every pair (i, j), with i < j, of integers is given a weight that has distribution F , independently. What can we say about C(p, x) ≡ C(pδ 1 + (1 -p)δ x ) as a function of x? We refer to this graph as "random charged graph" because we allow x to be negative (and hence a charge rather than weight). We still want to maximize total charge. Paths with negative charge exist, however, C(p, x) > 0. The results in this section have been obtained in [START_REF] Foss | Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph[END_REF] and show some interesting behavior: whereas C(p, x) is a convex increasing function of x, it is not everywhere differentiable. A number of combinatorial arguments allow us to establish that C(p, x) is nondifferentiable if and only if x is a negative rational or equal to n or 1/n for some positive integer n ≥ 2. Due to lack of space, the section only offers an outline of the results.

In Section 10 we ask how to obtain more information about C(F ) experimentally, that is, by simulation. When F = δ p + (1 -p)δ -∞ (the standard Barak-Erdős graph) we can employ Markovian methods (MCMC). But we want to do better and devise a perfect simulation method, that is, a way to perfectly (and not approximately) simulate a random variable whose expectation is C(F ). To deal with the general F case, we first assume that that F is supported on a semi-infinite interval (-∞, 1], say, such that it places positive mass to any left neighborhood of 1. Using this assumption, we generalize the IBM particle system to something that we call Max Growth System (MGS) that is a Markovian process in a space of point measures (configurations of particles) on the real line. We then construct renovation events, use them to construct a stationary process, and then extract a random variable that can be perfectly simulated and which has expectation C(F ). Based on this, we offer a method for experimenting with various weight distributions. We only ran simulations in a simple case, and even present the algorithm for it.

We conclude the paper by an overview and some open problems.

From the Barak-Erdős graph to the infinite bin model

Consider a loopless directed graph -→ G on the set Z of integers whose edges are oriented in a way compatible with the ordering of the integers: if {i, j} is an edge then it is oriented from min(i, j) to max(i, j).

Fix two integers i, j such that j -i = n > 0. There are four maximal quantities of interest:

L L,R
i,j := the maximal length of all paths from i to j ; L L i,j := the maximal length of all paths from i to some j ≤ j; L R i,j := the maximal length of all paths from some i ≥ i to j; L i,j := the maximal length of all paths from some i ≥ i to some j ≤ j.

(2.1) (Superscripts L, R indicate left-tied, right-tied paths, respectively.) Clearly, the first quantity is the smallest and the last the largest, while the other two are in-between.

Ergodic arguments

If -→ G is the Barak-Erdős graph -→ G (Z, p), it will be seen that all these quantities satisfy the same strong law of large numbers (SLLN). But it is easier to see that the largest of these quantities satisfies a SLLN, as a consequence of Kingman's subadditive ergodic theorem [START_REF] Kingman | Subadditive ergodic theory[END_REF]. This has nothing to do with independence per se and this becomes more general in the context of the following lemma. Instead of insisting that the edge-defining random variables are i.i.d. we merely assume stationarity and ergodicity. In what follows, we shall consider a collection α of random variables α i,j , indexed by pairs (i, j) of integers with i < j, and taking values in {1, -∞}. We shall then speak of the random graph -→ G (Z, α) with whose set edges is {(i, j) : i < j, α i,j = 1}.

(2.2)

Choosing -∞ rather than 0 is convenient because if we take any sequence i 0 < i 1 < • • • < i of integers, for some ∈ N, then the quantity (α i0,i1 + α i1,i2 + • • • + α i -1 ,i ) + takes values 0 or ; it takes value if and only if (i 0 , i 1 , . . . , i ) forms a path in -→ G (Z, α). Using this trick, we can easily express the maximal lengths (2.1) as maxima of these quantities over deterministic increasing sequences of integers. For example, L L,R 1,3 = max{α + 1,3 , (α 1,2 + α 2,3 ) + }. By saying that a probability measure P is defined on the canonical space Ω we mean that P is defined on the set Ω consisting of all collections α = (α i,k ) i,k∈Z . Lemma 2.1. Let α = (α i,j , i < j, i, j ∈ Z), be a collection of random variables with values in {1, -∞} with distribution P on its canonical space Ω. Define θ : Ω → Ω by 1(θα) i,j = α i+1,j+1 .

(2.3)

Assume that (θ, P) is stationary and ergodic. Let

L i,j := max i≤i0<i1<•••<i ≤j ∈N (α i0,i1 + α i1,i2 + • • • + α i -1 ,i ) + .
Then there is a deterministic C such that

C = lim n→∞ L 0,n /n as n → ∞ P-a.s. and in L 1 , C = inf n EL 0,n /n.
Proof. Noticing that L i,j is the maximum length of all paths in -→ G (Z, α) with endpoints between i and j (consistent with the last of (2.1)) we have

L i,k ≤ L i,j + L j,k + 1, i < j < k,
for if we consider a maximum length path between two vertices on [i, k] then its length is at most the length of its restriction on [i, j] plus the length of its restriction on [j, k] plus 1 if j is not a vertex of the maximum length path. The stationarity and ergodicity of (θ, P) together with the last inequality shows that the L i,j + 1 satisfy the assumptions of Kingman's subadditive ergodic theorem [START_REF] Kingman | Subadditive ergodic theory[END_REF] and so lim n→∞ L i,i+n /n exists P -a.s. and in L 1 and equals C = inf n EL 0,n /n. Remark 2.2. It will turn out that all four quantities in (2.1) have the same growth rate as the largest of them. This is not entirely obvious at this moment because, for example, attempting to establish that lim n→∞ L L,R 0,n /n exists a.s., one might be tempted to use the obvious superadditivity

L L,R i,k ≥ L L,R i,j + L L,R j,k ,
But, according to the extension of the subadditive ergodic theorem of Liggett, see [START_REF] Liggett | Interacting Particle Systems[END_REF]Theorem 2.6] this would require that EL - i,j < ∞ which is false here. The fact that

C L,R = C L = C R = C is discussed below; see Corollary 2.8.
Returning to the graph -→ G (Z, α), whose edge set is as in (2.2), let us define

i j ⇐⇒ there is a path in - → G (Z, α) from i to j
and identify a certain random subset of Z, that we shall refer to as the skeleton of the graph, as follows. For each j ∈ Z let

A j = {α ∈ Ω : for all i ∈ Z there is a path in - → G (Z, α) from min(i, j) to max(i, j)}. (2.4)
The skeleton S is the random set of all j such that A j occurs:

S = S (α) = {j ∈ Z : α ∈ A j }. (2.5)
The elements of S are called skeleton points or skeleton vertices of the graph -→ G (Z, α). Notice that θA j = A j+1 for all j ∈ Z. Hence, if (θ, P) is stationary we have P(A 0 ) = P(A n ) for all n ∈ Z and the random sets S •θ n have all the same law.

Definition 2.3 (rate of skeleton). Assume that (θ, P) is stationary. Then the quantity

λ := P(A 0 ) (2.6)
is referred to as the rate or density of the skeleton S .

Lemma 2.4. Assume that (θ, P) is stationary and ergodic. Then S + := S ∩ [0, ∞) and S -:= S ∩ (-∞, 0] are both infinite sets P-a.s. if and only if λ > 0. Moreover, conditional on A 0 , the expected distance between two successive elements of S is 1/λ.

Sketch of proof.

The first claim is due to the Poincaré recurrence lemma [?]. The second claim is from basic properties of stationary point processes.

Remark 2.5. If S + and S -are both infinite then any two far apart vertices i and j will contain a skeleton point between them. This implies that the there is at least one path from i to j (and this path passes through the skeleton point).

The following is taken from [START_REF] Denisov | Limit theorems for a random directed slab graph[END_REF].

Lemma 2.6. Consider -→ G (Z, α) and assume that α i,j , i < j, i, j ∈ Z, are all independent with P(α i,j = 1) = p j-i ,

where p n , n ∈ N, is a sequence of probabilities such that ∞ n=1 (1 -p 1 ) • • • (1 -p n ) < ∞. (2.7)
Then the rate λ, defined by (2.6), of the skeleton S is positive and given by

λ = j>0 (1 -(1 -p 1 ) • • • (1 -p j )) 2 . (2.8)
Proof. The independence assumption implies that (θ, P) is stationary and ergodic, where θ is as in (2.3). We will argue that the summability assumption (2.7) implies that λ > 0 which, by Lemma 2.4, will imply that S -is an infinite set.

Consider the random variables

(j) := max{k > 0 : α j-k,j = 1}, j ∈ Z,
which have the same distribution:

P( (j) > k) = (1 -p 1 ) • • • (1 -p k ).
Condition (2.7) implies that (j) < ∞ a.s. Consider also the event A + 0,m = {0 j, for all j = 1, . . . , m}, noticing that

A + 0,m = m j=1 j-1 i=0 {i j} = m j=1 { (j) ≤ j}.
Therefore,

A + 0 := {0 1, 0 2, . . .} = ∞ j=1 { (j) ≤ j},
and so

P(A + 0 ) = ∞ j=1 (1 -(1 -p 1 ) • • • (1 -p j )) > 0.
Similarly,

A - 0 := {-1 0, -2 0, -3 0, . . .}
has the same probability as A + 0 . Noticing that the event A 0 , defined by (2.4), is the intersection of A + 0 and A - 0 , two independent events, we obtain

λ = P(A 0 ) = P(A + 0 )P(A - 0 ) = j>0 (1 -(1 -p 1 ) • • • (1 -p j )) 2 .
Remark 2.7. If one of the p j equals 1 then letting k = min{j :

p j = 1} we have λ = k-1 j=1 (1 -(1 - p 1 ) • • • (1 -p j )) 2 . The case p 1 = 1 is uninteresting.
Combining all of the above we conclude that the length of longest paths in Barak-Erdős graphs grows linearly, a result first observed by Newman [START_REF] Newman | Chain lengths in certain random directed graphs[END_REF].

lim n→∞ L 0,n n = lim n→∞ L L 0,n n = lim n→∞ L R 0,n n = lim n→∞ L L,R 0,n n = C(p) a.s.

Sketch of proof.

If p = 0 then the graph has no edges and the above limits hold trivially with C(0) = 0. Assume p > 0 and note that condition (2.7) of Lemma 2.6 holds because (2.7) holds:

∞ n=1 (1 -p) n < ∞.
We thus have λ > 0. By Lemma 2.4, the random sets S + , S -are a.s. infinite with positive rate λ. We can easily see that

L 0,n = L L,R 0,n + o(n), as n → ∞, a.s.
The conclusion now follows from Lemma 2.1.

Remark 2.9. For a -→ G (Z, p) with 0 ≤ p ≤ 1, we have that the rate of its skeleton is given by

λ = ∞ j=1 (1 -(1 -p) j ) 2 (2.9)
This follows from (2.8). We now give a number-theoretic interpretation. Consider Euler's function

ϕ(q) := ∞ k=1 (1 -q k ), |q| < 1.
Clearly,

λ(p) = ϕ(1 -p) 2 .
It is easy to see that 1/ϕ(q) is the generating function of the sequence p(n) of integer partitions of the positive integer n, that is,

∞ n=1 p(n)q n = 1 ϕ(q) .
To see this, recall that p(n) is defined as the number of ways to write n

= 1 + 2 2 + 3 3 + • • • , where the i are nonnegative integers. So ∞ n=1 q n p(n) = ∞ n=1 q n 1, 2 ,... 1 n= 1+2 2+••• = 1 q 1 2 q 2 2 • • • = (1 -q) -1 (1 -q 2 ) -2 • • • = 1/ϕ(q).
Euler's pentagonal number theorem relates Euler's function to pentagonal numbers, that is numbers of the form (3n 2 -n)/2 (pentagonal numbers are "Pythagorean" numbers in the sense that they can be represented using pentagons, analogously to triangular and square numbers that were actually known by Pythagoras). The theorem says that

ϕ(q) = ∞ n=-∞ (-1) n q 3n 2 -n 2 , |q| < 1.
A beautiful bijective proof of this is due to Franklin (1881) [START_REF] Franklin | Sur le développement du produit infini (1 -x)(1 -x 2 )(1 -x 3 ) • •[END_REF]; see Andrews [START_REF] Andrews | The Theory of Partitions[END_REF] for a more modern account. Other algebraic proofs are due to Jacobi, Euler, and others; see Pólya and Szegő [86, §4, 50-54] for these proofs.

Remark 2.10. It is interesting to see that for a sparse -→ G (Z, p) graph, the average distance between two successive skeleton points is huge, whereas for a dense graph every second point is a skeleton point. For the symmetric p = 0.5 case, roughly every 12th point is a skeleton point.

(p) = ∞ n=-∞ (-1) n (1 -p) 3n 2 -n 2 2
to perform these computations, since the series converges much faster than the product. This, together with the regenerative properties (Section 6) provides a method for constructing an accurate picture of -→ G (Z, p).

The infinite bin model corresponding to the Barak-Erdős graph.

The general Infinite Bin Model (IBM) is a particle system that will be introduced in Section 3. In the current section, we will motivate the need to study it by explaining how to obtain an IBM by growing a Barak-Erdős -→ G (Z, p) graph dynamically. For the construction, we shall keep in mind that we are interested in longest paths.

Suppose that we have created

- → G n = - → G ({1, . . .

, n}, p).

To construct -→ G n+1 we need to add all edges (i, n + 1) for which α i,n+1 = 1. Conditional on -→ G n , the distribution of -→ G n+1 will not change if we permute the variables α 1,n+1 , . . . , α n,n+1 . We choose to order the variables α 1,n+1 , i = 1, . . . , n by ordering the vertices i = 1, . . . , n, according to decreasing values of (L R 1,i ) 1≤i≤n :

j i ⇐⇒ L R 1,j ≥ L R 1,i ,
with ties resolved arbitrarily. Introduce a state (or configuration) vector X n = (X n (0), X n (1), . . .) for -→ G ({1, . . . , n}, p) by letting

X n ( ) := |{1 ≤ i ≤ n : L R 1,i = }|.
In particular, X n (0) is the number of vertices j for each none of the edges (i, j) exist, for any 1 ≤ i < j, and X n (1) is the number of vertices j such that there exists an edge (i, j) for some i that is counted in X n (0) and there are no other incoming edges to j. We now let

L n := max 1≤j≤n L R 1,j , for notational convenience. Hence X n (L n ) is the number of vertices 1 ≤ i ≤ n such that L R 1,i is maximal.
For technical reasons, we shall extend X n ( ) on negative integers too and let X n ( ) = ∞ if < 0. Therefore, our state vector is of the form

X n = [. . . , ∞, ∞, X n (0), X n (1), . . . , X n (L n ), 0, 0, . . .].
(2.10)

Note that X 1 = [. . . , ∞, ∞, 1, 0, 0, . . .], that is, X 1 (0) = 1, X 1 ( ) = ∞ for < 0, and X 1 ( ) = 0 for > 0.
We observe that the sequence (X n ) of state vectors is a Markov chain. Indeed, changing the point of view, we shall think of X n as a configuration of a number of identical balls (corresponding to the vertices) into labeled bins, so that X n (k) is the number of balls in bin k. The Markovian evolution is then easily obtained. When we add a new vertex n + 1 then the state will change by the addition of a new ball into a bin. Recalling the ordering ≺ of the vertices of -→ G n , we remark that the balls are placed in the bin in an increasing fashion. In other words, for all i < j, if the ball corresponding to vertex i is a bin to the left of the ball corresponding to vertex j, then i ≺ j.

To construct X n+1 we only need to monitor the largest vertex i, for that order, such that α i,n+1 = 1. We then add a new ball to the bin immediately to the right of the bin containing ball i. If such an i does not exist we are in the situation that vertex n + 1 is not the endpoint of a path starting from vertex 1 and, in this case, a ball is added in bin 0: X n+1 (0) = X n (0) + 1. Thus, first let B n be the nonnegative integer uniquely specified by

X n (B n + 1) + • • • + X n (L n ) ≤ I < X n (B n ) + X n (B n + 1) + • • • + X n (L n ), (2.11)
where I is the rank of the largest vertex i for ≺ such that α i,n+1 = 1, or I = n + 1 if there is no such vertex. Then, we construct X n+1 as X n + δ Bn , where δ k is the configuration with a single ball in bin k, so that δ k ( ) = 1 {k= } .

Noting the form of the state (2.10) we see that such a B n always exists and, because negative bins contain an infinite number of balls we have B n ≥ 0.

We can equivalently describe the transition from X n to X n+1 by the stochastic recursion

X n+1 = X n + δ B(Xn,ξn+1)+1 , (2.12)
where ξ n+1 is a geometric random variable with parameter p, i.e. P(ξ [START_REF] Baryshnikov | GUEs and queues[END_REF] with ξ n+1 in place of I. The stochastic recursion (2.12) then proves that (X n ) is a Markov chain. The process (X n ) is a particular case of an infinite bin model that will be studied in more detail in the next section. This bin model was introduced in [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF] even under more general stationary and ergodic assumptions. It was shown that a stationary version of a spatially-shifted version of it exists. Under independence assumptions, it was possible to write balance equations for the stationary version. These led to sharp bounds on C(p) showing, in particular, the asymptotics of C(p) as p → 0 that had previously obtained by Newman [START_REF] Newman | Chain lengths in certain random directed graphs[END_REF]. Moreover, it became possible to obtain analytically expressible upper and lower bounds for the whole function p → C(p).

n+1 = i) = (1 -p) i-1 p, i ∈ N, independent of X n and B(X n , z) = inf    k ∈ Z : ∞ p=k+1 X n (p) ≤ z    , i.e. B(X n , ξ n+1 ) is the B n satisfying (2.
We study in the next section the infinite bin model as a stochastic process per se, dropping the geometric distribution assumption. This allows us to obtain general formula for the speed at which the index of the rightmost occupied bin is growing. Specifying these formulas for the geometric distribution will allow us to obtain the precise analytic properties of the function C in Section 4.

The general infinite bin model

We consider in this section the infinite bin model as a "ball in bins" process. It can be constructed as a Markov chain in which at each step, a new ball is added in one of the bins similarly to the process defined in Section 2.2, but with an arbitrary law for the placement of the new ball. This model has appeared in different forms in several areas of probability. Among others, Aldous and Pitman [START_REF] Aldous | The asymptotic speed and shape of a particle system[END_REF] took interest in an infinite bin model in which at each step, a new ball is added to the right of one of the N rightmost balls, chosen uniformly at random. The present general setting was introduced by Foss and Konstantopoulos [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF], however in this article a stationary version of the process (defined in Section 3.4) is considered.

This section is organized as follows: we first introduce a formal definition of the generalized infinite bin model in Section 3.1 as a Markov chain on the space of functions Z → Z + with support of the form {n ≤ a} for some a ∈ Z. In Section 3.2, we show that the index of the rightmost occupied bin in an infinite bin model grows linearly over time, at a certain speed v. The rest of the section is devoted to various ways to compute this constant.

We introduce the notion of coupling words in Section 3.3, which allows us to introduce renewal events in the evolution of infinite bin model. Thanks to these renewal events, we can define a stationary version of the infinite bin model in Section 3.4, which allows us to obtain several analytic formulas for its speed in Section 3.5.

Definition and first properties of the infinite bin model

In order to give a general description of infinite bin models, we first describe the state space on which this Markov chain will evolve. A configuration (or state) X is a map k → X(k) from Z (the set of bins) into

Z + := {0, 1, 2, . . .} ∪ {∞}
such that X(k) = 0 eventually. We let

S := X ∈ Z Z + : there is f ∈ Z such that (X(k) = 0 iff k > f )
be the set of configurations. We think of k ∈ Z as a bin and of X(k) as a number of indistinguishable balls placed in this bin. Given X ∈ S we let

F (X) = max {k ∈ Z : X(k) > 0} ,
a quantity called the front (bin) of X. Thus, each bin contains some balls (either no ball or a positive finite number of balls or an infinite number of balls) such that every bin to the right of F (X) is empty and every bin to the left of F (X) is nonempty. 2 .

System dynamics. Consider a configuration X and a positive integer ξ that we will refer to as the selection number. The rightmost nonempty bin is F (X). Enumerate the balls in the nonempty bins of X starting from the right and moving to the left, select the ξ-th ball, and let B(X, ξ) be the bin containing it. The next state is obtained by simply adding a single ball to the bin to its right, indexed B(X, ξ) + 1. For technical reasons, we will also allow for the possibility that ξ = 0 or ξ = ∞. If ξ = ∞, the bin that contains the ξ-th ball is formally at -∞, so no ball is added. If ξ = 0, the new configuration is obtained by shifting the position of every ball in the configuration one step to its right, i.e. replacing X by k → X(k -1).

In symbols, we let

B(X, ξ) := inf k ∈ Z : j>k X(j) < ξ , ( 3.1)
writing B(X, ∞) = -∞ by convention. Then, for ξ ∈ N ∪ {∞}, we define Φ ξ : S → S by

Φ ξ (X) := X + δ B(X,ξ)+1 , ( 3.2)
similarly to (2.12), where δ k is the element of Z Z + with δ k (i) = 1 if i = k and 0 otherwise, so that δ -∞ ≡ 0 (in particular Φ ∞ (X) = X). We also define Φ 0 via Φ 0 (X)(k) := X(k -1), k ∈ Z, corresponding to shifting X by a unit step to the right. We notice that B = B(X, ξ) is uniquely specified by the inequality

X(B + 1) + • • • + X(F ) < ξ ≤ X(B) + X(B + 1) + • • • + X(F ), where F = F (X).
We also have, for all 1 ≤ ξ ≤ ∞,

F (X) -ξ + 1 ≤ B(X, ξ) ≤ F (X) = B(X, 1).

Definition 3.2 (infinite bin model).

Given a probability measure µ on Z + = {0, 1, 2, . . . , ∞}, and an i.i.d. random sequence (ξ n ) n≥1 with common law µ, we define IBM(µ) to be the Markov process (X n ) with values in S given by

X n+1 = Φ ξn+1 (X n ).
We leave the initial configuration X 0 unspecified.

Remark 3.3. In Section 3.3 we will write Φ ξ (X) simply as ξX or ξ(X) for reasons that will become apparent there. Keeping this in mind, we refer the reader to the Example 3.14 below.

Note that X 0 does not reflect in the notation IBM(µ). This is justified by the fact that the asymptotic properties of the IBM that we are interested in are independent of the choice of X 0 . In relation with the Barak-Erdős graphs, we will be mostly interested in the case when µ is a geometric random variable on N, but it will be useful to consider more general measures on Z + in order to obtain estimates on some quantities of interest. However, as several lemmas are easier to prove under the assumption that µ is supported on N, let us first remark that this condition is usually enough to study the asymptotic properties of the infinite bin model. Lemma 3.4. Let µ be a probability distribution on Z+ with µ(N) > 0. We denote by ν the law µ conditioned to be on N, i.e.

∀k ∈ N, ν({k}) = µ({k}) µ(N) .

There exists a coupling between the IBM(µ)

(X n ) and a couple (Y n , (A n , B n ))
, where (Y n ) is an IBM(ν) started from X 0 and (A n , B n ) is an independent Z 2 -valued random walk with step distribution

P(A n+1 = A n + 1, B n+1 = B n ) = µ(0), P(A n+1 = A n , B n+1 = B n + 1) = µ(∞) and P(A n+1 = A n , B n+1 = B n ) = µ(N) such that ∀n ∈ Z + , ∀k ∈ Z, X n (k) = Y n-An-Bn (k -A n ) a.s.
Proof. Letting (ξ n , n ≥ 0) be a sequence of i.i.d. random variables with law µ, we set

A n = n k=1 1 {ξ k =0} and B n = n k=1 1 {ξ k =∞} ,
and observe that (A n , B n ) is the same random walk as defined in the lemma. Moreover, if we relabel (ζ n ) the random sequence (ξ n ) removing all terms equal to 0 or ∞, in increasing order of their indices. We observe that (ζ n ) is a sequence of i.i.d. random variables with law ν, independent from (A n , B n ). We define X n and Y n by setting Y 0 = X 0 and

X n+1 = Φ ξn+1 (X n ) = Φ ξn+1 • • • • • Φ ξ1 (X 0 ) and Y n+1 = Φ ζn+1 (Y n ) = Φ ζn+1 • • • • • Φ ζ1 (X 0 ).
Observing that Φ 0 and Φ ∞ both commute with all Φ k for k ∈ N, we can rewrite

X n = Φ An 0 Φ ζ n-An -Bn • • • • • Φ ζ1 (X 0 ) = Y n-An-Bn (k -A n ),
using that there are exactly A n elements of (ξ 1 , . . . , ξ n ) equal to 0 and B n equal to -∞, the rest being given, in the same order, by (ζ 1 , . . . , ζ n-An-Bn ), which completes the proof.

Theorem 3.5 (Speed of the IBM [ [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF][START_REF] Mallein | Barak-Erdős graphs and the infinite bin model[END_REF]). Let µ be a probability measure on Z+ . Let (X n ) be an IBM(µ) with initial configuration X 0 . Then there exists a constant 0

≤ v µ ≤ 1, not dependent of X 0 , such that lim n→∞ F (X n ) n = v µ a.s.
The quantity v µ is called the speed of the IBM(µ). This theorem is proved in Section 3.2 by bounding the IBM(µ) by two sequences of IBMs with laws having finite supports and using an increasing coupling between these processes. Remark 3.6. Applying Lemma 3.4, we observe that if µ is a probability distribution on Z+ with µ(N) > 0, then setting ν = µ(•|N), we have (by law of large numbers)

v µ = µ(0) + µ(N)v ν .
In particular, it is enough to prove Theorem 3.5 for measures supported by N.

Beyond the position of the front, we will generally be interested in the content of a finite number of bins at a fixed distance from the front. In the case of an IBM(µ) where µ has finite support, one can reduce the study of the IBM to a finite state space Markov chain having a stationary distribution, by considering some finite-dimensional projection of the process, see Section 3.2. For a general µ the content of the rightmost K non-empty bins also has a stationary distribution but the arguments are more involved, see Section 3.4. Definition 3.7 (partial order on S). For any X, Y ∈ S, we set X Y if for every ξ ∈ N, B(X, ξ) ≤ B(Y, ξ), that is, if for every ξ the ξ-th ball of X is to the left of the ξ-th ball of Y . Lemma 3.8. The relation is a partial order that is preserved by addition. Moreover,

if 0 ≤ ξ ≤ ξ ≤ ∞ and X Y then Φ ξ (X) Φ ξ (Y ). (3.3) Proof. Simply notice that X Y ⇐⇒ ∞ k= X(k) ≤ ∞ k= Y (k) for all ∈ Z.
This implies that X Y and X Y implies X + X Y + Y . For the second assertion, assume first that 1 ≤ ξ ≤ ξ ≤ ∞. We then have, by (3.1), B(X, ξ ) ≤ B(X, ξ) and so δ B(X,ξ )+1 δ B(X,ξ)+1 ; and if X Y then X + δ B(X,ξ )+1 Y + δ B(X,ξ)+1 , and so Φ ξ (X) Φ ξ (Y ) by (3.2).

The case ξ = ξ = 0 being straightforward, we are left with the case ξ = 0 < ξ ≤ ∞. Assume again X Y . Then, by the argument above, and since ξ ≥ 1, we have Φ

ξ (X) ≤ Φ ξ (Y ) ≤ Φ 1 (Y ) and we can easily see that Φ 1 (Y ) ≤ Φ 0 (Y ).
This partial order can be used to define an increasing coupling between two IBMs when the step distribution of the first IBM is dominated by the step distribution of the second IBM. Proposition 3.9 (increasing coupling). Let µ and ν be two probability measures on Z + such that for every i ≥ 0 we have µ([0, i]) ≤ ν([0, i]). Then if X 0 Y 0 are two configurations in S, we can construct a coupling of (X n ) ∼ IBM(µ) and (Y n ) ∼ IBM(ν) such that X n Y n for every n ≥ 0 a.s.

Proof. The assumption that µ([0, i]) ≤ ν([0, i]) for all i allows us to define random ξ, ξ , with laws µ, ν, respectively, such that ξ ≤ ξ a.s. Hence we can build an i.i.d. sequence of pairs (ξ n , ξ n ) n≥1 such that ξ n has law µ, ξ n has law ν and ξ n ≤ ξ n for all n ≥ 1. Defining the IBM(µ) (X n ) using (ξ n ) and the IBM(ν) (Y n ) using (ξ n ), we obtain that X n Y n for every n ≥ 0 a.s. by applying (3.3) inductively.

The speed of the general infinite bin model

This section is devoted to the proof of Theorem 3.5 for the existence of the speed v µ for IBM(µ). We first examine the case where µ has finite support and then develop a coupling technique to deal with the general case.

The finite support case. Let ξ be a random element of Z+ , distributed according to the law µ. Assume there is an integer k such that ξ ∈ {0, 1, . . . , k} ∪ {∞} a.s.

(3.4)

If k = 1 then, by the definition of Φ ξ , the front of Φ ξ (X) is one unit to the front of X iff ξ ∈ {0, 1}. Hence, in this case,

F (X n ) -F (X 0 ) = n m=1 1 ξm∈{0,1} and so v µ = µ(0) + µ(1) = 1 -µ(∞).
We now assume in the rest of the section that there exists k ≥ 2 such that µ(k) > 0.

Given a configuration X define Π k (X) := X(B(X, k) + 1), . . . , X(F (X)) , (3.5) which is interpreted as a finite word 3 in N. Let | Π k (X)| be its length and Π k (X) its content, that is, the total number of balls, corresponding to the sum of the letters of that word. We have

0 ≤ | Π k (X)| = F (X) -B(X, k) ≤ k -1, 0 ≤ Π k (X) = F (X) j=X(B,k)+1 X(j) ≤ k -1, and | Π k (X)| = 0 if and only if Π k (X) = 0. The set Π k (S) = { Π k (X) : X ∈ S} = {∅} ∪ {[a 1 , . . . , a ] : 1 ≤ ≤ k -1, a 1 , . . . , a ≥ 1, a 1 + • • • + a ≤ k -1} is finite 4 .
We think of Π k as a projection of S on Π k (S) a set of finite cardinality. We observe that an IBM X with step distribution satisfying (3.4) is compatible with this projection, in the sense that Π k (X) remains a Markov chain. Lemma 3.10. Let k ≥ 2 be an integer, and assume that the law µ is supported in {0} ∪ {1, . . . , k} ∪ {∞} with µ({k}) > 0. Consider the IBM defined by X n+1 = Φ ξn+1 (X n ), where the (ξ n ) are i.i.d. random variables with law µ. Then Z n = Π k (X n ), n ≥ 0, is an irreducible Markov chain with values in the set Π k (S). In particular, the chain is positive recurrent and has a unique stationary probability measure.

Intuition of the proof. The reason that the function Π k preserves the Markov property is because each of the states a ∈ Π k (S) conveys just enough information about the state X ∈ S with a = Π k (X) that is enough to decouple the past from the future.

For example, if a = ∅ then we know that any X ∈ S with a = Π k (X) must satify B(X, k) = F (X) (because a has length 0) and so the front bin F (X) contains at least k balls. This means that regardless of the value of ξ, 1 ≤ ξ ≤ k, we have Φ ξ (X) is X together with a single ball in the bin to the right of F (X). So Φ ξ (X) has a front at F (X) + 1 with a single ball and so Π k (Φ ξ (X)) = [START_REF] Addario-Berry | Poisson-Dirichlet branching random walks[END_REF]. On the other hand, if ξ = 0 or ∞ then the next state remains a. A complete proof of this fact being available in [START_REF] Mallein | Barak-Erdős graphs and the infinite bin model[END_REF]Lemma 3.1], it is perhaps best to work out two examples and leave the formal details to the reader.

It is easy to see that the Markov chain Π k (X n ) has an irreducible class connected to the state ∅ (by producing a sequence of moves that takes the chain from any state to ∅; the assumption that P(ξ = k) > 0 is required at this step). Since the state space is finite, the chain is positive recurrent and has a unique invariant probability measure.

Given a = [a 1 , . . . , a ] ∈ Π k (S) let L(a) = a with the convention that L(a) = k if a = ∅. So if Z n = Π k (X n ) then L(Z n ) corresponds
to the number of balls in the front bin of X n (or k if this number is larger than k). 3 A finite word in an alphabet A is a finite (possibly empty) sequence of elements of A. We denote by A * = ∞ =0 A the set of finite words in A, with the convention A 0 = {∅}. We denote by |w| the length of the word w ∈ A * , defined as the unique ∈ Z + such that w ∈ A . In particular, ∅ is the only word with length 0.

4 More precisely | Π k (S)| = 2 k-1 . Indeed, recall that the set of -tuples (a 1 , . . . , a ) of strictly positive integers summing to m has cardinality m-1 -1 . Thus the number of -tuples of positive integers summing at most to k -1 is given by

k-1 m= m-1 -1 = k-1 .
Summing over all possible values of yields that Π k (S) has cardinality The integers over the directed edges represent the values of ξ corresponding to the transitions. For example, if µ is the law of ξ, the transition probability for state [START_REF] Addario-Berry | Poisson-Dirichlet branching random walks[END_REF] to state [START_REF] Addario-Berry | Minima in branching random walks[END_REF] on right equals µ(2) + µ [START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF]. The thick arrows represent transitions that move the front by one unit. Note that if ξ ∈ {0, ∞}, the projected Markov chain remains at the same state, moving the front by 1 if and only if ξ = 0. Proposition 3.11. Let (X n ) be an IBM(µ) where µ is supported on {0} ∪ {1, . . . , k} ∪ {∞} where k ≥ 2 and µ(k) > 0. Then there exists a constant v µ ∈ [0, 1], that does not depend on X 0 , such that

k-1 =0 k-1 = 2 k-1 . ∅ [1] 1, 2 1 2 ∅ [1] [2] [1, 1] 1, 2, 3 2, 3
lim n→∞ F (X n ) n = v µ a.s. Proof. Let Z n = Π k (X n ). Notice that F (X j ) > F (X j-1 ) ⇐⇒ F (X j ) -F (X j-1 ) = 1 ⇐⇒ L(X j-1 ) ≥ ξ j , (3.6)
using that a ball is added in the leftmost empty bin if ξ is either equal to 0 or smaller than the number of balls in the rightmost bin, see Figure 3. Setting b j for the indicator of the event on the right of the last equivalence, we have

F (X n ) -F (X 0 ) = n j=1 b j .
By the ergodic theorem 1 n n j=1 b j converges to a constant v µ a.s. which completes the proof. Remark 3.12. Observe that v µ can be computed from the knowledge of the invariant distribution π of the Markov chain Π k (X n ). More precisely, writing Z for a random word distributed according to π and ξ an independent random variable with law µ, we have 2)); see Figure 3. However, since the size of Π k (S) grows exponentially with k, this exact formula can be computed for small values of k only.

v µ = P(L(Z) ≥ ξ). For example, if k = 2, we have v µ = π(∅)µ({0, 1, 2})+π([1])µ({0, 1}) = (µ(1)+µ(2)) 2 /(µ(1)+2µ(
The general µ case. In order to extend the existence of the speed to the case when µ may have infinite support, we compare µ to three distributions with finite supports and use the increasing coupling of Proposition 3.9. Let ξ be a random element of Z + with distribution µ. Fix k ≥ 1 and define ξ j k := ξ1 ξ≤k + j1 ξ>k , and let µ j k be the distribution of ξ j k . We are only interested in the cases where

j = 0, k or ∞ (noticing that ξ ∞ k = ξ when ξ ≤ k or ∞ when ξ > k). Clearly, ξ 0 k ≤ ξ k k ≤ ξ ≤ ξ ∞ k . Let (ξ 0 k,n , ξ k k,n , ξ n , ξ ∞ k,n ), n ∈ N, be i.i.d. copies of (ξ 0 k , ξ k k , ξ, ξ ∞ k ). Define 4 coupled IBMs, (X 0 k,n ), (X k k,n ), (X n ) and (X ∞ k,n ),
≥ 0 X ∞ k,n X n X k k,n X 0 k,n a.s. (3.7) We next observe that Π k (X ∞ k,n ) = Π k (X 0 k,n ) for all n ≥ 0, (3.8)
where Π k was defined in (3.5).

Proof of (3.8). It follows immediately from its definition that Φ 0 commutes with Φ k for all k ∈ Z+ .

Using that ξ ∞ k,n = ξ 0 k,n if and only if ξ k ∈ (k, ∞), in which case the former takes value ∞ while the latter take value 0, we have

X 0 k,n = Φ ξ 0 k,n • • • • • Φ ξ 0 1,n (X 0 ) = Φ In 0 • Φ ξ ∞ k,n • • • • • Φ ξ ∞ 1,n (X 0 ) = Φ In 0 X ∞ k,n ,
where

I n = n-1 j=0 1 {ξ k ∈(k,∞)} . Consequently, X 0 k,n ( ) = X ∞ k,n ( -I n ) for all ∈ Z, from which we deduce that Π k (X ∞ k,n ) = Π k (X 0 k,n ), completing the proof.
We are now able to complete the proof of Theorem 3.5.

Proof of Theorem 3.5. Let k ≥ 1 be an integer. By Proposition 3.11, there exist

v µ ∞ k and v µ 0 k in [0, 1] such that lim n→∞ F (X ∞ k,n ) n = v µ ∞ k , lim n→∞ F (X 0 k,n ) n = v µ 0 k a.s. Using that F (X 0 k,n ) = F (X ∞ k,n ) + I n ,

as observed above, and that

I n /n → µ([k + 1, ∞)) a.
s. by law of large numbers, we conclude that

v µ 0,k = v µ ∞,k + µ([k + 1, ∞)).
(3.9)

Furthermore, we have that for every n ≥ 1,

F (X ∞ k,n ) ≤ F (X n ) ≤ F (X 0 k,n ) a.s. ( 3.10)
Combining (3.9) and (3.10) we deduce that

v µ ∞ k ≤ lim n→∞ F (X n ) n ≤ lim n→∞ F (X n ) n ≤ v µ ∞ k + µ([k + 1, ∞)) a.s. (3.11) Since for every i ≥ 0 and k ≥ 1, we have µ ∞,k ([0, i]) ≤ µ ∞,k+1 ([0, i]), we have by Proposition 3.9 that X ∞,k n X ∞,k+1 n thus the sequence (v µ ∞,k ) k≥1 is nondecreasing. Since it is upper-bounded by 1, we have that lim k→∞ v µ ∞,k = v µ , for some v µ ∈ [0, 1]. Letting k go to infinity in (3.11) we conclude that lim n→∞ F (X n ) n = v µ a.s. Remark 3.13. If ν is another probability distribution on Z+ such that ν([0, i]) ≤ µ([0, i]
) for all i ≥ 0, then it follows from Proposition 3.9 that v ν ≤ v µ .

Coupling words

We assume, throughout this section, that µ is a probability measure on the set N of positive integers, in other words that µ({0}) = µ({∞}) = 0. The IBM(µ) is the Markov process introduced in Definition 3.2 and aims to describe a stationary version of this process5 . Since F (X n+1 )-F (X n ) ≥ 0, and is positive with positive probability, it is easy to see that (X n ) has no stationary version. But this is an illusion! To remedy it, we simply modify X n by shifting the origin of space to the front bin F (X n ). This will be done in Section 3.4.

Recalling that X n is defined by the repeated application of maps of type Φ ξ several times. To simplify notation, we write ξX instead of Φ ξ (X), so that ηξX corresponds to Φ η (Φ ξ (X)). Applying a finite number of these maps is thus identified by a "selection word".

Let N * be the set of words from N. A selection word (or, simply, word when no confusion arises) is a nonempty word in

N. Let U = n≥1 N n = N * \{∅}
If α ∈ U then we write it, rather uncoventionally, from right to left

α = α • • • α 1
(or (α , . . . , α 1 ) when confusion arises) as we made the identification

Φ α • • • • •Φ α1 ≡ α • • • α 1 . (3.12)
Example 3.14. Take X = [. . . , 5, 3, 2, 1, 2, 0, 0, . . .], with F (X) = 0, and consider the selection word α = (2, 4, 5, 1). To compute α(X) we first apply 1 (that is, Φ 1 ), then 5, then 4 and then 2. We have

1(X) = Φ 1 (X) = X + δ 1 = [. . . , 5, 3, 2, 1, 2, 1, 0, . . .], 5(1X) = Φ 5 •Φ 1 (X) = X + δ 1 + δ -1 , 4(5(1X)) = Φ 4 •Φ 5 •Φ 1 (X) = X + δ 1 + δ -1 + δ 0 , and, finally, α(X) = 2(4(5(1(X)))) = X + 2δ 1 + δ -1 + δ 0 .
Recall that we denote by |α| the length of the word α. An element of a selection word is a selection number and is sometimes referred to as a letter. There is only one word of length 0, the empty word ∅, which is not considered as a selection word. However, we can formally define Φ ∅ as the identity on S.

If α = α • • • α 1 is a selection word and k ≤ then α k • • • α 1 is a prefix of α, while α • • • α k is a suffix.
The number of occurrences of letter n in a word α is written

ϑ n (α) := |{1 ≤ k ≤ |α|, α k = n}|. The concatenation of α = α • • • α 1 with β = β k • • • β 1 is the word βα = β k • • • β 1 α • • • α 1 ,
again keeping in mind the right-to-left convention. Of course, ∅α = α∅ = α. For m, ∈ N, the word m is the length-word whose letters are all equal to m.

For k ∈ N define

Π k : S -→ N k X -→ (X (F (X) -k + 1) , . . . , X (F (X)))
which isolates the content of the rightmost k non-empty bins. The definition can be extended to k = 0 by setting Π 0 (X) to be the empty vector.

Definition 3.15 (k-coupling words)

. We say that a selection word

α is k-coupling if ∀X, Y ∈ S Π k (αX) = Π k (αY ).
Let C k be the set of all k-coupling words. A word α is called coupling if it is k-coupling for some positive integer k.

In other terms, a word α is said to be k-coupling if the action of α on any configuration always give the same values in the k rightmost non-empty bins. For example, 1 is a 1-coupling word, as the rightmost non-empty bin in 1X always contain exactly one ball. More generally, for k ∈ N, the word 1 k is a k-coupling word.

Note that

C 1 ⊃ C 2 ⊃ • • • . Hence C 1
is the set of all coupling words. Note that C 1 is the set of all words α such that the number of balls in the bin at the front of αX is the same as for αY for any other configuration Y . The words in U \ C 1 are non-coupling. Definition 3.16 (Coupling number). The coupling number of α is defined by

K(α) = sup{k ≥ 0 : ∀X, Y ∈ Π k (αX) = Π k (αY )}.
In particular, for a word α, K(α) = 0 is equivalent to α ∈ U \ C 1 , i.e. to the fact that α is non-coupling. More generally, for k ≥ 1, we have

K(α) = k ⇐⇒ α ∈ C k \ C k+1 . Hence, α is k-coupling if and only if K(α) ≥ k. We naturally let K(∅) = 0.
Example 3.17. We have that K(1) = 1, K(1, 1) = 2, and more generally, if 1 = (1, . . . , 1) is the word consisting of letters all equal to 1, then K(1 ) = . Indeed, as previously observed, 1 is an -coupling word. But 1 ∈ C +1 because the + 1st rightmost nonempty bins contains the number of balls in the rightmost non-empty bin of X.

Consider next the word (2, 2, 1). We see that, for any X, we have Π 2 ((2, 2, 1)X) = (2, 1); but the three rightmost bins of (2, 2, 1)X depend on the content of the front of X. Hence (2, 2, 1) ∈ C 2 \ C 3 . As a third example, one can check that (2, 2) is a non-coupling word.

We now define a class of words which will provide useful examples of coupling words.

Definition 3.18 (Triangular words). A word

α = (α , . . . , α 1 ) ∈ U is called triangular if for every 1 ≤ i ≤ we have α i ≤ i.
We denote by T the set of triangular words. An infinite sequence (. . . , α 3 , α 2 , α 1 ) of positive integers is called an infinite triangular word if α i ≤ i for all i. Let T ∞ be the set of infinite triangular words.

We claim that every triangular word is a coupling word. More precisely, if α is a triangular word with k occurrences of the letter 1, we show that α is k-coupling. Lemma 3.19. Let k ≥ 1 and let α be a triangular word with ϑ 1 (α) = k. Then α is k-coupling.

Proof. Write α = (α , . . . , α 1 ) ∈ T and let X 0 , Y 0 ∈ S. Without loss of generality, we assume that

F (X 0 ) = F (Y 0 ) = 0. For every 1 ≤ i ≤ n, define X i = α i • • • α 1 (X 0 ) and Y i = α i • • • α 1 (Y 0 ).
We show by induction on 0 ≤ i ≤ that X i and Y i coincide for all bins of positive indices and have i balls in these bins. In other words, we show that for every

k ≥ 1, X i (k) = Y i (k) and j≥1 X i (j) = j≥1 Y i (j) = i. This is trivially true when i = 0.
If 1 ≤ i ≤ , by induction hypothesis, we know that X i-1 and Y i-1 have i -1 balls in the same positions in bins of positive indices and at least one ball in the bin of index 0, thus

B(X i , α i ) = B(Y i , α i ) ≥ 0. Hence Φ αi adds a ball to X i-1 and Y i-1 in the same bin of positive index, completing the proof of that statement. Next, setting f := F (X ) = F (Y ), we have f ≥ 1 (since α 1 = 1). As X |Z+ = Y |Z+ , we have Π f (α(X 0 )) = Π f (α(Y 0 )), so K(α) ≥ f . Since each transition Φ 1 adds a balls to a previously empty bin, we have that f ≥ ϑ 1 (α) = k, which shows that α ∈ C k .
More generally, an infinite triangular word allows the coupling of IBM with arbitrary initial conditions.

Lemma 3.20. Let α ∈ T ∞ and let X 0 , Y 0 ∈ S 0 . For every n ≥ 1, denote by X n = α n • • • α 1 (X 0 ) and by Y n = α n • • • α 1 (Y 0 ). Then for every n ≥ 0 we have X n|N = Y n|N (

both configurations have identical contents in all bins with positive indices).

The proof follows from an induction similar to the one used above in the proof of Lemma 3.19.

Construction of a stationary version and coupling

In order to construct a stationary version of the infinite bin model, we first define a variant of the IBM where the front is pinned at position 0.

Denote by S 0 the set of all X ∈ S such that F (X) = 0. For X ∈ Z Z and u ∈ Z, we introduce the map

Θ u X(k) := X(k -u).
In other words, Θ u shifts X to the right by u. We remark immediately that Θ u = (Φ 0 ) u .

Next, let ΘX :

S → S 0 X → Θ -F (X) X
be the projection S → S 0 which "pins the front" at position 0.

Definition 3.21 (Pinned infinite bin model). Given a probability measure µ on N, and a sequence (ξ n ) n≥1 of i.i.d. random variables with law µ, we define the pinned IBM(µ) to be the Markov process ( X n ) with values in S 0 given by

X n+1 = Θ • Φ ξn+1 ( X n ), n ≥ 0.
We leave the initial configuration X 0 ∈ S 0 unspecified.

Let ( X n ) be the pinned IBM as above. Using the same sequence of selection numbers, and recalling the convention (3.12), we define an unpinned IBM by setting X 0 = X0 and

X n = ξ n • • • ξ 1 X 0 for n ≥ 1.
We observe that for any selection word α and X ∈ S, we have Θ(αX) = Θ(α(ΘX)). Therefore, for each n ∈ N, we have

X n = ΘX n .
As a result, X n can be thought of as the pinned version of the IBM X.

Definition 3.22 (Stationary pinned IBM)

. Given a stationary sequence (ξ n ) n∈Z we say that (Y n ) n∈Z is a stationary pinned IBM if

Y n+1 = Θ(ξ n+1 Y n ), n ∈ Z. (3.13)
If (ξ n ) n∈Z is an i.i.d. sequence with common law µ then we refer to (the law) of (Y n ) as a stationary version of IBM(µ).

We show the existence and uniqueness of this stationary version under a first moment condition on µ. (3.14)

Let (ξ n ) n∈Z be a sequence of i.i.d. random variables with law µ. Write F n := σ(ξ k , -∞ < k ≤ n).
Then a.s. there exists a unique process (Y n ) n∈Z on S 0 satisfying the recursion (3.13) and such that Y n is F n -measurable for all n ∈ Z.

We observe that the condition sup k∈N µ(k) < 1 is only here to avoid considering the case when µ is a Dirac mass δ k for some k ≥ 1. In that case, there would be k processes (Y j n ) n∈Z,1≤j≤k on S 0 satisfying (3.13), given by

Y k n ( ) =      k if ≤ -1 0 if ≥ 1 ((j + n) mod k) + 1 if = 0 .
The proof of Theorem 3.23 relies on the existence of infinitely many ∞-coupling words embedded in the bi-infinite sequence (ξ n ) n∈Z . These words induce renewal events for the stationary IBM(µ).

In order to avoid unnecessary technicalities, we prove Theorem 3.23 under the additional condition µ(1) > 0. Under this condition, we prove the existence of infinitely many infinite triangular words in Lemma 3.25. These triangular words induce renovation events for the IBM(µ), in the sense that conditionally on their realisation at time k, the only algebraic dependence of the future (starting from time k) on the past (before time k) is given by the position of the front at time k. For the concept of renovation events see [START_REF] Borovkov | Ergodicity and stability theorems for a class of stochastic equations and their applications[END_REF][START_REF] Borovkov | Ergodicity and Stability of Stochastic Processes[END_REF][START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF].

Remark 3.24. To extend Theorem 3.23 to measure µ such that µ(0) = 1, one can use [START_REF] Chernysh | Coupling any number of balls in the infinite bin model[END_REF] in which for all a = b ∈ N, a coupling word α with letters in {a, b} with arbitrary K(α) is constructed. An analogue of Lemma 3.25 can be stated replacing a triangular word by α followed by an infinite coupling word β.

The rest of the proof would follow straightforwardly; see [START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF].

With Lemma 3.20 in mind, we show almost surely, there exist infinitely many triangular words in the infinite sequence (ξ n , n ∈ Z). This result (and its proof) should be compared and contrasted with Lemma 2.4.

Lemma 3.25. Let (ξ n ) n∈Z be an i.i.d. sequence with Eξ 0 < ∞.
Then the law of the random set

R = {k ∈ Z : (• • • ξ k+2 ξ k+1 ξ k ) ∈ T ∞ }. (3.15) is invariant under translations and R ∩ [0, ∞) and R ∩ (-∞, 0] are infinite sets a.s.
Proof. The invariance by translation is obvious. Observe that

P((• • • ξ k+2 ξ k+1 ξ k ) ∈ T ∞ ) = P(ξ k ≤ 1, ξ k+1 ≤ 2, ξ k+2 ≤ 3, . . .) = ∞ j=1 (1 -P(ξ 0 > j)).
According to the assumptions (3.14) we have P(ξ 0 = 1) > 0 and hence all terms in this product are positive. We also have ∞ j=0 P(ξ 0 > j) = Eξ 0 < ∞ and so the whole product is positive. As a result, R possesses a positive density on Z. Just as in Lemma 2.4 we conclude that R contains infinitely many positive and infinitely many negative integers a.s.

We write R = {T 0 , T ±1 , T ±2 , . . .} and arrange the indexing so that

• • • < T -1 < T 0 ≤ 0 < T 1 < • • • For each n in Z, let s(n) be the unique (random) integer such that T s(n) ≤ n < T s(n)+1 . Proof of Theorem 3.23. We shall construct (Y n ) as a measurable function of (ξ n ) by constructing Π k (Y n ) for all k. Fix n ∈ Z and k ≥ 1. Consider the selection word ξ n • • • ξ T s(n)-k+1 . Since T s(n)-k+1 ∈ R, the word ξ n • • • ξ T s(n)-k+1 is triangular. Note that the number of elements of R in the interval [T s(n)-k+1 , T s(n) ] is k. For each T j we have ξ Tj = 1, by the definition of R. Hence the selection word ξ n • • • ξ T s(n)-k+1 contains at least k letters equal to 1. Thus by Lemma 3.19 it is k-coupling. Hence the vector Π k (ξ n • • • ξ T s-k+1 (X)) is the same for all X ∈ S.
Fix an X and define the rightmost k bins of Y n to be equal to this vector. This definition is consistent for different values of k, hence defines Y n up to a global shift. Requiring F (Y n ) = 0 yields a unique definition of Y n a.s. By construction, for every n ∈ Z, Y n ∈ F n and the sequence (Y n ) n∈Z satisfies (3.13). Conversely, any sequence of configurations in S 0 satisfying (3.13) has to coincide with the sequence (Y n ) constructed above.

It follows from Theorem 3.23 that every finite-dimensional marginal of the pinned IBM started at time 0 converges and even gets coupled to the corresponding marginal of the stationary version.

Corollary 3.26 (Coupling-convergence).

Let (ξ n ) n∈Z be an i.i.d. sequence of law µ satisfying conditions (3.14). Let X 0 ∈ S 0 and let ( X n ) n≥0 be a pinned IBM(µ) constructed using the variables ξ n , n ≥ 1. Let (Y n ) be the stationary version of the pinned IBM. Then for every k ≥ 1, there exists n k ≥ 1 such that for every n ≥ n k , we have

Π k ( X n ) = Π k (Y n ).
(3.16)

Proof. Let k ≥ 1 and set n k = T k which is finite a.s. If n ≥ n k , we have ϑ 1 (ξ n • • • ξ 1 ) ≥ k and (3.16) follows from Lemma 3.19.
A second consequence of Theorem 3.23 is a simple expression for the speed v µ in terms of the stationary version of the pinned IBM(µ).

Corollary 3.27. Let (Y n ) be the stationary version of the pinned IBM constructed using the i.i.d. variables (ξ n ) n∈Z of law µ satisfying conditions (3.14). Then

v µ = P(ξ 1 ≤ Y 0 (0)).
(3.17)

Proof. Let (X n ) be an IBM constructed using the random variables (ξ n , n ≥ 0) such that X 0 = Y 0 (0) a.s. We recall that

v µ = lim n→∞ F (X n ) n a.s.
Therefore, using the dominated convergence theorem, we have

v µ = lim n→∞ E(F (X n )) n = lim n→∞ 1 n n j=1 E (F (X j ) -F (X j-1 )) = lim n→∞ 1 n n j=1 P(ξ j ≤ L(X j-1 )), using (3.6) (recall that L(X) is the number of balls in the rightmost non-empty bin of X). Then, as L(X n ) = L(Y n ) = Y n (0) a.
s. for all n ∈ N, we have

P(ξ j ≤ L(X j-1 )) = P(ξ j ≤ Y j-1 (0)) = P(ξ ≤ Y 0 (0)),
using that Y is a stationary adapted sequence. This result immediately implies (3.17).

New expressions for the speed

Using Corollary 3.27, we deduce in this section new formulas for the speed v µ as infinite sums over some special classes of selection words. In constructing the stationary regime, we were interested in renovation events, that is events that resulted in decoupling the future from the past.

In computing the speed, we are merely interested in whether the front advances or not at time 1.

Words that manage to advance the front of any configuration at their last selection index are called good. Words that never do this are called bad. Bad is not the opposite of good: there are selection words that sometimes move the front at the last step and sometimes do not. In what follows recall that, for integers ξ, η, . . . and X ∈ S, the symbol ηξX stands for Φ η (Φ ξ (X)). Definition 3.28 (Good/bad words). Define the following sets of selection words:

G := {α • • • α 1 ∈ U : ∀X ∈ S F (α α -1 • • • α 1 X) = F (α -1 • • • α 1 X) + 1}, B := {α • • • α 1 ∈ U : ∀X ∈ S F (α α -1 • • • α 1 X) = F (α -1 • • • α 1 X)}, and A := U \ (G ∪ B).
We call the words in G good, those in B bad, and those in A ambivalent.

Example 3.29. The word 1 is good. More generally every word α • • • α 1 ending with α = 1 is good.

The word (2, 1) is bad. To see this, let X have F (X) = 0. We observe that 1X = X + δ 1 and 2(1X) = X + 2δ 1 as the second ball of 1X is at bin 0. Hence, F (2(1X)) = F (1X) = 1. As this relation holds regardless of X, the word (2, 1) is bad.

The word 2 is ambivalent. Indeed, if X has F (X) = 0 and X(0) = 1 then 2X = X + δ 0 , so

F (2X) = 0, but if X(0) ≥ 2 then 2X = X + δ 1 , so F (2X) = 1.
Coupling words can be used to generate a large class of good and bad words. More precisely, the following result holds. To apply Corollary 3.27 to compute the speed v µ of the IBM(µ), we have to detect, based on the sequence (ξ n , n ≤ 1), if the front of Y will increase at time 1. To this end, we introduce the notion of minimal good and bad words. Definition 3.31 (V-minimal words). For every V ⊂ U define the set of V-minimal words as the set of words in V with no strict suffix belonging to V, i.e.

V min := {α = α • • • α 1 ∈ V : α • • • α i ∈ V, i = 2, . . . , }. Observe that if α ∈ V satisfies |α| = min{|β|, β ∈ V}, then α ∈ V min .
Example 3.32. First consider V = T the set of triangular words. We see that (2, 2, 1) ∈ T min (because (2, 2, 1) is in T but (2, 2) and (2) are not in T ). On the other hand, the triangular word (2, 2, 1, 3, 2, 1) is not in T min because its suffix (2, 2, 1) is triangular.

Let us now consider minimal good and bad words. We have obviously 1 ∈ G min , but (1, 1) ∈ G min . Similarly, we observe that (3, 2, 1) ∈ B as 3(2(1X)) = X + 3δ 1 and 2(1X) = X + 2δ 1 , but both (3) and (3, 2) are ambivalent words (hence not bad). Therefore (3, 2, 1) ∈ B min .

We next observe that (G ∪ B) min = G min ∪ B min . (3.18) This follows from the fact that a suffix of a good word cannot be bad and a suffix of a bad word cannot be good.

Definition 3.33 (Weight of a word). The weight of α = (α , . . . , α 1 ) ∈ U under the probability measure µ is defined to be

w µ (α) := i=1 µ(α i ).
We are now ready to explain how to get new formulas for the speed v µ .

Proposition 3.34. Let µ be any probability measure on N and (ξ n ) n∈Z a sequence of i.i.d. random variables with law µ. Let V be a class of selection words (recalling that ∅ is not a selection word) and define

T * V := sup{-∞ < ≤ 1 : ξ 1 ξ 0 • • • ξ ∈ V}. Assume that (i) V ⊂ G ∪ B (V contains no ambivalent words) (ii) P(T * V > -∞) = 1. Then v µ = α∈Vmin∩G w µ (α) = 1 - α∈Vmin∩B w µ (α). ( 3
= P(ξ 1 ≤ Y 0 (0)). Observe that {ξ 1 ≤ Y 0 (0)} = {F (ξ 1 ξ 0 • • • ξ T Y T -1 ) -F (ξ 0 • • • ξ T Y T -1 ) = 1}. (3.20) Since ξ 1 ξ 0 • • • ξ T ∈ A, it follows that F (ξ 1 ξ 0 • • • ξ T Y T -1 ) -F (ξ 0 • • • ξ T Y T -1 ) = F (ξ 1 ξ 0 • • • ξ T X) -F (ξ 0 • • • ξ T X) for all X ∈ S.
And so the event of (3.20) is equal to

{ξ 1 ξ 0 • • • ξ T ∈ G}.
On the other hand,

ξ 1 ξ 0 • • • ξ T ∈ V but ξ 1 ξ 0 • • • ξ T +j ∈ V if j > 0.
Hence

ξ 1 ξ 0 • • • ξ T ∈ V min a.s.
We conclude that

v µ = P(ξ 1 ξ 0 • • • ξ T ∈ V min ∩ G) = α∈Vmin∩G P(ξ 1 ξ 0 • • • ξ T = α). (3.21)
The length of the word

ξ 1 ξ 0 • • • ξ T is 2 -T , so P(ξ 1 ξ 0 • • • ξ T = α) = P(ξ 1 ξ 0 • • • ξ 2-|α| = α, T = 2 -|α|) = P(ξ 1 ξ 0 • • • ξ 2-|α| = α) = P(ξ 1 • • • ξ |α| = α) = µ(α 1 ) • • • µ(α |α| ) = w µ (α),
where the second equality follows from the fact that we calculate this probability for α ∈ V min . Thus the first identity in (3.19) is proved. The second identity follows from

V min \(V min ∩G) = V min ∩B.
By taking special choices for the class V we obtain the following useful formulas when µ satisfies assumptions (3.14): Theorem 3.35 (speed as a sum over words, [START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF]). Let µ be a probability measure on N satisfying assumptions (3.14). Then

v µ = α∈Tmin∩G w µ (α) (3.22) v µ = α∈Gmin w µ (α). (3.23)
Remark 3.36. As observed in Proposition 3.34, the number of possible formulas for the speed v µ is equal to the number of subset of V ⊂ G ∪B such that T * V > -∞ a.s. However, the two formulas (3.22) and (3.23) will be the more useful for our purpose. It should be apparent that setting V = G ∪ B gives a formula such that |T * V | is minimal. However, for an algorithmic purpose, it is much easier to verify that a word is triangular than to verify that it is not ambivalent. Therefore, (3.22) is particularly efficient when estimating v µ via Monte-Carlo methods, see forthcoming Section 10.

Proof. We first apply Proposition 3.34 with V = T and make sure that (i) and (ii) in that proposition hold. By Lemma 3.30 we have T ⊂ G ∪ B, so (i) holds. Recall that

T * T = sup{ ≤ 1 : (ξ 1 ξ 0 ξ -1 • • • ξ +1 ξ ) ∈ T }. By Lemma 3.25 all the points of R are finite in absolute value a.s. Hence there are points -∞ < ≤ 0 such that (• • • ξ +1 ξ ) ∈ T ∞ . Any such point certainly satisfies (ξ 1 ξ 0 • • • ξ +1 ξ ) ∈ T , so T *
T > -∞ a.s., therefore (ii) holds as well. As a consequence (3.22) follows from (3.19).

We next apply Proposition 3.34 with V = G ∪ B, so (i) holds immediately. Moreover, we have

T * G∪B = sup{ ≤ 1 : ξ 1 • • • ξ ∈ G ∪ B} ≥ T * T as ξ 1 ξ 0 • • • ξ T * T ∈ G ∪ B, hence T * G∪B > -∞ a.s. Additionally, thanks to (3.18) we have (G ∪ B) min ∩ G = (G min ∪ B min ) ∩ G = (G min ∩ G) ∪ (B min ∩ G) = G min ∪ ∅ = G min ,
which yields to (3.23), by using the first equality of (3. [START_REF] Borovkov | Ergodicity and stability theorems for a class of stochastic equations and their applications[END_REF]) with V = G ∪ B. Remark 3.37. Note that there is no inclusion relation between T min ∩ G and G min . For example (2, 4, 2, 1) ∈ G min \ (T min ∩ G) and (2, 4, 2, 1, 1) ∈ (T min ∩ G) \ G min . Remark 3.38. In [START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF], Theorem 3.23 is showed to hold for any infinite bin model, under the condition that µ is not a Dirac mass. As a result, Corollary 3.27 also holds without any assumption on the first of µ. In fact, [START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF]Theorem 1.2] states that (3.23) holds for any non-degenerated measure µ. However, observe that (3.22) does not necessarily holds, as E(ξ) < ∞ is a necessary condition for the existence of infinite triangular words.

Analytic properties of the asymptotic length of the longest path

In this section we use the results of the previous section on the infinite bin model to derive properties of the asymptotic length of the longest path in Barak-Erdős graphs by coupling the latter to an infinite bin model in the case when µ is a geometric distribution. Let

µ p (k) = (1 -p) k-1 p, k ∈ N. Let (X n ) be the Markov process constructed in Section 2.2 from - → G (Z, p). Then (X n ) is an IBM(µ p ). Looking at (2.10) we see that F (X n ) = L n , (4.1)
where L n is the maximum of all paths in -→ G (Z, p) with endpoints in [1, n]. By Corollary 2.8, we have that

L n /n → C(p) a.s. whereas Theorem 3.5 shows that F (X n )/n → v µp a.s. We conclude that C(p) = v µp . ( 4.2)
We now make use of the results and formula obtained in Section 3.5 to prove the analyticity of C on (0, 1] in Section 4.2, and to express its power series expansion in Section 4.3. But first, we rephrase the results of Section 3.5 for a geometrically distributed infinite bin model.

First formulas for C

Using Corollary 3.27 and the geometric distribution of ξ, we observe that C(p) can be computed rather explicitly in terms of the stationary version Y of the IBM(µ p ).

Corollary 4.1. Let 0 < p ≤ 1, we denote by R p a random variable distributed as the content of the front bin in the stationary IBM(µ p ). Then

C(p) = 1 -E (1 -p) Rp . (4.3)
Proof. Let ξ be a random variable with geometric distribution µ p which is independent of the stationary IBM(µ p ) Y . It follows from Corollary 3.27 that

v µp = P(ξ ≤ Y 0 (0)) = 1 -P(ξ > R p ).
Conditioning on the value of R p and using formula (4.2) yields formula (4.3).

We also apply Theorem 3.35 to obtain formulas for C(p) as the sum of weights of well-chosen set of words. To this end we need the notion of height of a word.

Definition 4.2 (Height). The height of

α = α • • • α 1 ∈ U is defined as H(α) := i=1 (α i -1) = i=1 α i -|α|.
With this notation, we observe that

w µp (α) = α j=1 µ p (α j ) = p |α| (1 -p) H(α) .
We immediately obtain the following restatement of Theorem 3.35 for the special case µ = µ p .

Theorem 4.3. Let 0 < p ≤ 1. Then C(p) = α∈Tmin∩G p |α| (1 -p) H(α) (4.4) C(p) = α∈Gmin p |α| (1 -p) H(α) . ( 4
∈ [0, 1], C k (p) ≤ C(p) ≤ C k (p). (4.6)
As the IBM(µ ∞ p,k ) and the IBM(µ k p,k ) can be constructed using Markov chains on a finite state space, with transition probabilities that are polynomial functions of p, their speeds C k (p) and C k (p) are rational functions in p that can be computed explicitly. For example, with k = 3, performing such computations yields

C 3 (p) = p(p 2 -3p + 3) 2 (p 4 -6p 3 + 14p 2 -16p + 8) 3p 6 -26p 5 + 96p 4 -196p 3 + 235p 2 -158p + 47 C 3 (p) = p 3 -2p 2 + p -1 p 5 -4p 4 + 8p 3 -9p 2 + 6p -3 .
It is worth noting that (3.9) implies that

0 ≤ C k (p) -C k (p) ≤ (1 -p) k ,
therefore the sequences of functions (C k (p)) k≥1 and (C k (p)) k≥1 converge exponentially fast to C(p), uniformly on every interval of the form [ε, 1] with ε > 0. As we will see in Section 4.3, this convergence is so fast when p is close to 1 that they provide many coefficients of the power series expansion of C(p) at p = 1. In fact, comparing the asymptotic expansions of C 3 and C3 around p = 1 already give

C(p) = 1 -(1 -p) + (1 -p) 2 -3(1 -p) 3 + 7(1 -p) 4 + O((1 -p) 5 ) as p → 1.
Remark 4.4. Writing the balance equations for the stationary version Y of the IBM(µ p ), Foss and Konstantopoulos [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF] obtained a different upper and lower bound for C(p). This result on a more precise upper bound for C(p) for p close to 0, however this bound still does not allow the capture of the asymptotic behavior of C as p → 0.

Analyticity of C

Using the formulas obtained above for the function C resulting from the coupling with the infinite bin model, we can show that the function C is analytic on (0, 1]. Observe that if these bounds appear very sharp for p close to 1, the approximation (in particular the upper bound) remains quite crude for p close to 0.

Proof. For every p, q ≥ 0 define

D(p, q) = α∈Tmin∩G p |α| q H(α) . (4.7)
By formula (4.4), we have that C(p) = D(p, 1 -p) for every 0 < p ≤ 1. Let 0 < p 0 ≤ 1. The rest of the proof consists in the construction of (p , q ) such that p > p 0 , q > 1 -p 0 and the series (4.7) for D(p , q ) converges. This will imply the normal convergence of the series of derivatives of (4.4) around p 0 , which in turn will imply the analyticity of C in a neighborhood of p 0 . Let 0 < p ≤ 1 and let (ξ n ) n∈Z be i.i.d. of law µ p . We claim that, for all r > 1,

D(rp, 1 -p) ≤ E(r 2-T0 ),
where T 0 is the largest nonpositive point of the set R defined in (3.15). To see this, recall the time

T * T = sup{-∞ ≤ t ≤ 1 : ξ 1 ξ 0 • • • ξ t ∈ T }
E(r 2-T0 ) ≥ E(r 2-T ) ≥ E r 2-T ; ξ 1 ξ 0 • • • ξ T ∈ T min ∩ G = α∈Tmin∩G E r 2-T ; ξ 1 ξ 0 • • • ξ T = α = α∈Tmin∩G E r |α| ; ξ 1 ξ 0 • • • ξ 2-|α| = α, 2 -T = |α| = α∈Tmin∩G r |α| P ξ 1 ξ 0 • • • ξ 2-|α| = α = α∈Tmin∩G r |α| p α1 (1 -p) α1-1 • • • p α (1 -p) α -1 = D(rp, 1 -p).
We now observe that |T 0 | has some finite exponential moments. Indeed, |T 0 | can be seen as the first return time to 1 of the Markov chain defined by Z 0 = 1 and

Z n+1 = max(Z n -1, ξ 1-n ).
This Markov chain can straightforwardly be dominated by a downward-skip free random walk with negative drift, yielding the existence of these exponential moments. We refer to [77, p14, proof of Theorem 1.1] for extra details on this proof.

As a consequence, there exists r > 1 such that for all p0 2 < p < 1, we have

E(r |T0 |) < ∞. Choose p such that max p0 2 , p0 r < p < p 0 .
Then setting p = rp and q = 1 -p we have that p > p 0 , q > 1 -p 0 and the series (4.7) for D(p , q ) converges. Remark 4.6. We observe that C (0) = e and C (0) = ∞ (see forthcoming Section 5). Therefore the analyticity of C cannot be extended up to p = 0,

Power series expansion of C(p) around p = 1

We use in this section Formula (4.5) to prove that the power series expansion of p → C(p) around p = 1 only consists of integer coefficients. We write q = 1 -p, and expand C(1 -q) as a power series in the variable q. Recall that H(α) = |α| i=1 (α i -1) is the "height" of the word α. We begin with the following observation. Proof. Let us assume that there exists α ∈ G min such that |α| > H(α)+1. We obtain a contradiction by showing that α will possess a strict suffix in T (hence in G ∪ B), which violates the assumption that α is G-minimal.

Let S(k

) := k i=1 (α i -2), 1 ≤ k ≤ |α|, we remark that S(|α|) = H(α) -|α| < -1.
We denote by n = max{1 ≤ k ≤ |α| : S(k) < -1}, and remark that S(k) ≤ -2 for all n ≤ k ≤ |α|. In particular, as

S(1) = α 1 -2 ≥ -1, we have n ≥ 2.
As

α k ≥ 1, we have S(k) -S(k -1) ≥ -1 for all 2 ≤ k ≤ |α|. Therefore, S(n) = -2 and for all k ≤ n -|α|, we have S(n + k) ≥ -k -2. As a result, α n+k = 2 + S n+k -S n+k-1 ≤ 2 -2 -(-(k -1) -2) ≤ k + 1.
As a result, we now have proved that α |α| • • • α n is a triangular word which is a strict suffix of α, completing the proof by contradiction as mentioned above.

We adopt the convention that for ∈ N and k ∈ Z, the binomial coefficient k vanishes whenever k < 0 or k > . We now use (4.5), and show that the power series expansion obtained around p = 1 by rearranging its terms has positive radius of convergence, which completes the proof of the main result of the section. Theorem 4.8 ([76]). For every n ≥ 0, define

a n := α∈Gmin |α| n -H(α) (-1) H(α) . (4.8)
Then for every 0 ≤ q < √ 2-1 2

we have

C(1 -q) = n≥0 (-1) n a n q n . ( 4.9)
The fact that a n introduced in (4.8) is well-defined for all n ∈ Z + is a consequence of Lemma 4.7. Indeed, for every h ≥ 0 and ≥ 1 define

U h := {α ∈ U, |α| = and H(α) = h}.
We can consider this as the number of arrangements of h unlabelled balls into labelled boxes. Therefore, its cardinal is given by

|U h | = h + -1 -1 . ( 4
a n = n h=0 n+1 =1 (-1) h n -h |G min ∩ U h | (4.11)
which is in particular clearly finite.

Proof of Theorem 4.8. Let n ≥ 0 and let 0 ≤ q < 1. Rewrite formula (4.5) as

C(1 -q) = h≥0 h+1 =1 α∈Gmin∩U h q h (1 -q) = h≥0 h+1 =1 |G min ∩ U h | i=0 i (-1) i q i+h = h≥0 n≥0 h+1 =1 |G min ∩ U h | n -h (-1) n-h q n , (4.12)
For all q such that (4.12) absolutely converges, we can apply Fubini's theorem to obtain that (4.9) holds, where a n given by (4.11) or equivalently by (4.8). Taking absolute values inside the sums of (4.12) we obtain

I q := h≥0 n≥0 h+1 =1 |G min ∩ U h | n -h q n = h≥0 h+1 =1 |G min ∩ U h |q h (1 + q) . (4.13)
By (4.10), we have

I q ≤ (1 + q) h≥0 h =0 h + q h (1 + q) .
We use a random walk representation to find some values of q for which this is finite. Let (S N ) N ≥0 be a random walk on Z starting at 0 and taking a step +1 (resp. -1) with probability q 1+2q (resp. 1+q 1+2q ). Performing the change of variables N = h + , we have

h≥0 h =0 h + q h (1 + q) = N ≥0 (1 + 2q) N P(S N ≤ 0). (4.14)
Applying Chernoff's bound, we get

P(S N ≤ 0) ≤ inf t≥0 E(e -tS1 ) N ≤ inf t≥0 qe t + (1 + q)e -t 1 + 2q N ≤ 2 q(1 + q) 1 + 2q N . Thus, when 0 ≤ q < √ 2-1
2 , the series in (4.14) converges and the series in (4.12) converges absolutely.

Remark 4.9. Lemma 4.7 and Theorem 4.8 hold true with the same proofs if one replaces G min by T min ∩ G, thus for every n ≥ 0 we also have the formula

a n = α∈Tmin∩G |α| n -H(α) (-1) H(α) . (4.15)
The power series expansion being unique, we observe that (4.8) and (4.15) give the same values. n , it is reasonable to expect that the radius of convergence of this power series is greater than 0.5, but strictly smaller than 1.

In order to compute the first terms of the sequence (a n ), two methods have mainly been used so far. The first method is to use the bounds (4.6) for some small values of k. Both C k (p) and C k (p) arise as speeds of infinite bin models associated to probability measures supported on [0, k] ∪ {∞}, which are Markov chains on finite state spaces with a stationary distribution that can be computed explicitly. A finite number of coefficients of the Taylor expansion of C k (p) and C k (p) at p = 1 coincide, hence are coefficients of the Taylor expansion of C(p) at p = 1. The first 17 values of a n are computed in [START_REF] Mallein | Barak-Erdős graphs and the infinite bin model[END_REF]. However, the size of the state space of the Markov chain grows exponentially fast with k, and the computations have to be made analytically, this method quickly becomes computationally challenging.

The second method to compute a n consists in constructing the sets U h for small values of h then using formula (4.11). One may combine both methods, using a formula analogous to (4.11) to obtain the beginning of the power series expansions C k (p) and C k (p). They are expressed as sums over words constrained to have letters at most equal to k. Retaining the terms that coincide for the lower and upper bounds give terms for C(p). This last method was used in [START_REF] Terlat | Regularity of the time constant for last passage percolation on complete directed acyclic graphs[END_REF] to obtain the first 24 values of a n . See Table 2 for the first few values of a n . This sequence is referenced as A321309 in the On-Line Encyclopedia of Integer Sequences [START_REF] Sloane | The online encyclopedia of integer sequences[END_REF].

From the observation of the first terms of the sequence arises the following conjecture:

Conjecture 4.11. Removing the first two terms, the sequence (a n ) n≥2 is strictly increasing. In this section we explore the asymptotic properties of the length of long paths in a Barak-Erdős graph -→ G (N, p) in the sparse graph limit, that is, when p → 0. It can be seen that, in this limit, -→ G (N, p) is well-approximated by a branching random walk, a discrete-time particle system on the positive half-line R + . Throught this section, we will let G denote the -→ G (N, p).

Let L n (p) be the maximum length of all paths in -→ G (N, p) from 1 to n. Using branching random walk approximation, Newman [START_REF] Newman | Chain lengths in certain random directed graphs[END_REF] obtained the lead order of the asymptotic behavior of L n (p n ) when p n → 0 as n → ∞. He showed in particular that

lim n→∞ L n (p n ) np n = e in probability, (5.1)
as long as p n → 0 and np n → ∞. He also obtained the asymptotic behavior of the overall longest path in that graph (L 0,n with the notation of (2.1)).

Recalling that C(p) is the limit of L n (p)/n as n → ∞, Mallein and Ramassamy [START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF] obtained the precise asymptotic behavior of C(p) as p → 0 by comparing IBM(ν p ) (the infinite bin model with geometric distribution ν p with small p) to a continuous-time branching random walk with selection. Precisely, [START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF] states that

C(p) p = e - π 2 e 2 (log p) -2 (1 + o(1)), as p → 0, (5.2)
using the so-called Brunet-Derrida behavior [START_REF] Brunet | Shift in the velocity of a front due to a cutoff[END_REF][START_REF] Bérard | Brunet-Derrida behavior of branching-selection particle systems on the line[END_REF] of the speed of branching random walks with selection that we now describe.

A branching-selection process is a particle system in which each particle moves and reproduces independently, but an exterior selection mechanism keeps the size of the total population close to N by killing particles. 6 Brunet and Derrida [START_REF] Brunet | Shift in the velocity of a front due to a cutoff[END_REF] conjectured, through numerical simulations and the study of exactly solvable models, that for a large class of branching-selection processes, the speed of the cloud of particles v N converges to its limit v ∞ at a slow rate, such that

v ∞ -v N = C(1 + o(1)) (log N ) 2 .
(5.3) Remark 5.1. Belief in this conjecture was increased by the study of an exactly solvable model [START_REF] Brunet | Effect of selection on ancestry: an exactly soluble case and its phenomenological generalization[END_REF][START_REF] Cortines | A N -branching random walk with random selection[END_REF]. This type of behavior was observed by Berestycki, Berestycki and Schweinsberg [START_REF] Berestycki | The genealogy of branching Brownian motion with absorption[END_REF] for branching Brownian motions with absorption, Bérard and Gouéré [START_REF] Bérard | Brunet-Derrida behavior of branching-selection particle systems on the line[END_REF] for branching random walks, and for noisy F-KPP 7 equations modeling e.g. directed polymers [START_REF] Mueller | Effect of noise on front propagation in reactiondiffusion equations of KPP type[END_REF] among many other examples. 6 The most classical model is the N -branching Brownian motion (N-BBM) defined as follows. At each time t > 0, there are N particles on the real line. The particles move according to i.i.d. Brownian motions. At independent exponential times of parameter N , the leftmost particle is killed and one of the N -1 other particles gives birth to a new particle at at its currently occupied position. This model was notably studied in [START_REF] Maillard | Speed and fluctuations of N -particle branching Brownian motion with spatial selection[END_REF] in which the speed and fluctuation of the cloud if particles as N → ∞ is obtained. 7 Equations of this type are partial differential equations of the form vt = vxx + F (v) were introduced by Kolmogorov, Petrovsky and Piscounov [START_REF] Kolmogorov | Étude de l'equation de la diffusion avec croissance de la quantité de la matière et son application a un problème biologique[END_REF] as models for a reaction-diffusion systems. The name Fisher was added to these three names, whence the acronym F-KPP, owing to Fisher's infamous work [START_REF] Fisher | The wave of advance of advantageous genes[END_REF], a paper cited in [START_REF] Kolmogorov | Étude de l'equation de la diffusion avec croissance de la quantité de la matière et son application a un problème biologique[END_REF] also. A duality relationship between the F-KPP equation, in the F (v) = v(1 -v) case, and the branching Brownian motion was established by McKean [START_REF] Mckean | Application of Brownian motion to the equation of Kolmogorov-Petrovskii-Piskunov[END_REF]. Connections between the noisy F-KPP equation and the branching Brownian motion with selection were obtained in [START_REF] Durrett | Brunet-Derrida particle systems, free boundary problems and Wiener-Hopf equations[END_REF][START_REF] Masi | Hydrodynamics of the N -BBM process. Stochastic dynamics out of equilibrium[END_REF].

We present in the current paper an alternative, possibly simpler, construction of the coupling used by Mallein and Ramassamy [77] between the IBM(ν p ) and an N -branching random walk, a discrete analog of the N -BBM. We give in Section 5.1 some heuristics motivating the kind of limit that sparse Barak-Erdős graph has. This limit, being interpreted as a particular branching random walk sometimes called PWIT (Poisson-weighted infinite tree) is discussed in Section 5.2. In Section 5.3 we introduce a coupling between the Barak-Erdős graph, and the PWIT. This enables us to explain and describe the results of [START_REF] Newman | Chain lengths in certain random directed graphs[END_REF] and [START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF] We also extend these results to some other stochastic ordered graphs in Section 5.5. We then turn to computations of the length of the longest path of the Barak-Erdős graph in Section 5.6 and the shortest path in Section 5.7.

Heuristics on the sparse limit

It is now commonly known that the neighborhoods in many sparse random graphs, among which Erdős-Rényi graphs and configuration models, are well-approximated by branching processes. See [START_REF] Van Der | Random Graphs and Complex Networks[END_REF] and references therein. For example, let G(n, λ/n) be an Erdős-Rényi random graph. That is, on the set {1, . . . , n} a pair of points forms an indirected edge with probability λ/n, independently from pair to pair. Using the graph distance of the Erdős-Rényi random graph, we can observe that the set of points within finite distance from any fixed vertex converges weakly, as n → ∞, to a Galton-Watson tree with Poisson(λ) offspring distribution; see e.g. [START_REF] Curien | Erdős-Rényi Poissonized[END_REF].

Indeed, the number of neighbors of a given vertex v * is given by a binomial distribution with parameters n and λ/n that converges to a Poisson(λ) distribution as n → ∞. In turn, the number of neighbors of a given neighbor, excluding the vertex v * , is given by an independent binomial distribution with parameters n -1 and λ/n, which also converges to a Poisson(λ) distribution. Moreover, as there is with large probability a bounded number of vertices in the ball of radius k of the vertex v * , the probability of observing a non-trivial cycle of bounded size goes to 0 as n → ∞. This proves that any finite neighborhood of the vertex v * converges in distribution to a Galton-Watson tree.

Consider now a Barak-Erdős graph on N rather than on Z, as we are interested in paths from fixed root, the vertex 1 in this case. Denote this by

G := - → G (N, p),
letting E(G) be the random set of its edges. Assume that it is sparse; that is, we are interested in the limit as p → 0. We are able to obtain a similar description of the neighborhoods of the vertex 1 in terms of a branching process. However, to take into account the directed structure of the graph, we have to record in the limiting branching process the label of the vertices we consider.

To achieve this, consider instead the graph -→ G (pN, p), where pN := {pk : k ∈ N}. Think of the immediate neighbors of the root as a point process on (0, ∞) and let N be a standard Poisson point process on (0, ∞). We then have k∈N

1 (1,k)∈E(G) δ pk d -→ N, as p → 0.
where d -→ denotes convergence in distribution. Similarly, for any x > 0, the set of immediate neighbors of vertex x/p p, considered as a point process, also converges to N in distribution. It was shown in [START_REF] Gabrysch (née Trinajstić | Convergence of directed random graphs to the Poissonweighted infinite tree[END_REF][START_REF] Foss | Limiting Properties of Random Graph Models with Vertex and Edge Weights[END_REF] that the connected component of the root converges weakly, as p → 0, to the Poisson-weighted infinite tree (PWIT). This process is a branching random walk in which at each generation, all particles in the system give birth to children independently, such that the children of a particle at position x are positioned according to a Poisson point process with unit intensity on [x, ∞).

The PWIT and some of its properties

The terminology PWIT was introduced by Aldous and Steele [START_REF] Aldous | The objective method: Probabilistic combinatorial optimization and local weak convergence[END_REF]. We describe it as a Markovian particle system that we call immortal particles process. At time 0 an immortal particle is born. The particle produces a child at each epoch of a standard Poisson process; and, recursively, each of the offspring has the same reproduction law, independently. A convenient way to capture the system, together with all connection information, is by letting

N * := ∞ n=0 N n ,
where N 0 = {∅} be the vertex set of a tree with edges (u, v) ∈ N * × N * only when v = uk, the concatenation of u with a single integer k. Recall that N * is the set of words (=finite sequences) of positive integers equipped with the concatenation operation. The trivial word ∅ is the identity of the concatenation operation. We do not give a special symbol to the edges of N * as they are immediately fixed through N * . The resulting object is a tree that is now known as the Ulam-Harris tree. To encode the PWIT, simply add weights to the edges by letting,

X(∅) = 0, and then, for each u ∈ N * , 0 < X(u1) -X(u) < X(u2) -X(u) < X(u3) -X(u) < • • •
be the epochs of an independent copy of a Poisson(1) point process on (0, ∞). In our immortal particles interpretation, N * is the set of (names of) all particles that are born to the end of time and X(u) is simply the time at which particle u is born. Thus, for example, X [START_REF] Addario-Berry | Minima in branching random walks[END_REF][START_REF] Aldous | The objective method: Probabilistic combinatorial optimization and local weak convergence[END_REF][START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF] is the time at which the 3d offspring of the 5th offspring of the 2nd offspring of ∅ is born, and has the distribution of the sum of 2 + 5 + 3 = 10 i.i.d. exponential random variables. If we let |u| be the length of the word u and u the sum of its elements as integers then particle u is born at generation |u| and has Gamma( u ) distribution. 8 9 Let Π = (N * , X) denote the standard (unit rate) PWIT. Note that for any particle u ∈ N * the subtree rooted at u is also a PWIT after relabeling and time-shifting. We let

V t := {u ∈ N * : X(u) ≤ t}, X t := {X(u) : X(u) ≤ t}, Π t = (V t , X t ),
be the induced subgraph of Π on the set of vertices u with X(u) ≤ t. Hence Π t describes the immortal particles process up to time t. Note that Π t , t ≥ 0, is Markovian. If we forget the connections between particles and only keep the information of the lengths of their labels, then we obtain an IBM-type of model. Indeed, letting

Z t ( ) := |{u ∈ N * : X(u) ≤ t, |u| = }|, (5.4)
then Z t = (Z t (0), Z t (1), . . .), t ≥ 0, is a continuous-time IBM model whose evolution is as follows. Let, for each t, each of the particles u in Π(t) possess an independent exponential(1) clock. One of the clocks expires first; say that this 8 There are other ways to visualize the PWIT. First, recall that a branching random walk BRW(N ) in discrete time with parameter (the distribution of) a (finite or infinite) point process N on the real line, is created by letting a single particle at stage 0, located at point x, die at stage 1 and immediately be replaced by children located at the points of N + x (that is, the set of points of N all translated by x. All children behave exactly in the same manner, independently. If N is a standard Poisson process (whose points are interpreted as spatial points here) is the parameter of a branching random walk, then this branching random walk is the PWIT; this is the first interpretation. In this interpretation, X(u) is the spatial location of particle u. The second interpretation of a PWIT is as a so-called "Poisson cascade" in the physics literature [START_REF] Itoh | Continuum cascade model of directed random graphs: traveling wave analysis[END_REF]: Let Nt, t ≥ 0, be a collection of i.i.d. standard Poisson processes. Interpreting N as a set of points, we let V = t≥0 Nt be a set of vertices, letting (s, t) be an edge if t ∈ Ns + s. The corresponding graph is a random forest and the connected component of 0 is distributed like the PWIT. A third interpretation [START_REF] Aldous | The objective method: Probabilistic combinatorial optimization and local weak convergence[END_REF] is as a random metric space (N * , d) where the metric d is as follows. First let d(u, uk) = X(uk) -X(u) and then, for each u, v ∈ N * , let u = w 0 , w 1 , . . . , w = v be the necessarily unique path between u and v, and let d(u, v) = i=1 d(w i-1 , w i ). 9 The reason that we discuss different interpretations of the PWIT is because there exist results in the literature referring to seemingly different , but in essence identical stochastic models around the PWIT. For instance, if we consider the continuous-time Markovian branching process with offspring distribution δ 2 (the Yule process) then we can construct the PWIT as a deterministic function of it. We shall not explain this here.

clock is possessed by a particle in bin ; then we add a new particle in bin + 1. Note that Z t , t ≥ 0, is also Markovian. This process is an Uchiyama-type continuous-time branching random walk [START_REF] Uchiyama | Spatial growth of a branching process of particles living in R n[END_REF] on Z + , initiated from a single particle at position 0 at time 0. Also note that

|V t | := |{u ∈ N * : X(u) ≤ t}| = ≥0 Z t ( ), t ≥ 0,
is also Markovian with state space {1, 2, . . .} and transition rate y from state y to y + 1 (the Yule-Furry pure birth process). Finally note that there is a front bin, namely

F t = max{|u| : X(u) ≤ t} = max{ ∈ Z + : Z t ( ) > 0}, (5.5)
which is the largest generation particle present in Π t . 10 So Z t ( ) = 0 for all > K t . We use the abbreviation PWIT-IBM for Z t , t ≥ 0 and note that it differs from Π t , t ≥ 0, only by the absence of the connections information.

The total number of particles in every bin , with ≥ 1, of the PWIT-IBM at time t grows exponentially fast.

Lemma 5.2. Let f be a nonnegative measurable function on R. Then, for all

∈ N, E |u|= f (X(u)) = E |v|= -1 ∞ 0 f (X(v) + t)dt = ∞ 0 f (x)
x -1 ( -1)! dx.

Proof. Let u ∈ N . Then u = vk for some v ∈ N -1 and some k ∈ N. So

E |u|= f (X(u)) = E |v|= -1 E[f (X(v) + X(vk) -X(v))|X(v)] = E |v|= -1 E ∞ 0 f (X(v) + t)N (dt) X(v) = E |v|= -1 ∞ 0 f (X(v) + t)dt,
where the N above is a Poisson(1) point process on (0, ∞), independent of X(v). Iterating this we obtain

E |u|= f (X(u)) = [0,∞) f (t 1 + • • • + t ) dt 1 • • • dt ,
and the last expression follows by a change of variables.

Corollary 5.3. We have the following formulas for the expected number EZ t ( ) of particles in bin as well as the total number E|V t | of the PWIT-IBM at time t:

EZ t ( ) = t ! , E|V t | = e t .
Proof. From (5.4) and Lemma 5.2 with f (x) = 1 x≤t we have

EZ t ( ) = t 0 x -1 ( -1)! dx = t ! .
The second claim follows by summation or by remembering that |V t |, t ≥ 0, is the Yule-Furry process.

We are interested in the PWIT since, as motivated in Section 5.1, the PWIT appears as the limit of a sparse Barak-Erdős graph. We thus proceed in outlining some results concerning the PWIT. In Section 5.3 we will couple the PWIT together with the Barak-Erdős graph for all p (or more specifically with an appropriate spanning tree of the connected component of the root of G). This coupling will be such that M = inf |u|= X(u), (5.6) the first time that bin of the PWIT-IBM becomes nonempty, will give a lower bound for the index of any vertex of G linked to the vertex 1 by a path of length . It will be enough to obtain the upper bound for (5.1). This lower bound will be sharp enough in very sparse graphs, but some additional approximations will be needed when the density of edges becomes too large, yielding the estimate (5.2). In terms of the BRW(N ) interpretation-see footnote 8-the quantity M is the minimal displacement (position of the leftmost particle) at stage and this has been the subject of a large body of work. These asymptotic properties of the minimal displacement for a BRW(N ) depend on the quantity

κ(θ) := log R e -θx EN (dx)
the logarithm of the Laplace transform of the mean measure of N . The speed v of BRW(N ) is then expressed as

v = sup θ>0 -κ(θ) θ .
Indeed, Hammersley [START_REF] Hammersley | Postulates for subadditive processes[END_REF], Kingman [START_REF] Kingman | The first birth problem for an age-dependent branching process[END_REF] and Biggins [START_REF] Biggins | The first-and last-birth problems for a multitype age-dependent branching process[END_REF] proved under increasing generality that lim n→∞ M n n = v a.s. and in L 1 .

(5.7)

In our case, N being standard Poisson process, we have

κ(θ) = log ∞ 0 e -θx dx = -log θ, v := sup θ>0 log θ θ = 1 e ,
This is the same 1/e that appears in the limit (5.1). Addario-Berry and Reed [START_REF] Addario-Berry | Minima in branching random walks[END_REF] and Hu and Shi [START_REF] Hu | Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees[END_REF] independently proved that M n -n/e increases at logarithmic rate; more precisely in our case that

lim n→∞ M n -n/e log n = 3 2e
, in probability, (

with almost sure fluctuation occurring on that logarithmic scale. The convergence in distribution of the minimal displacement of a branching random walk, when centered around its median, was then obtained by Aïdékon [START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF]. Using that

D n = |u|=n (n/e -X(u))e -eX(u)
is a non-uniformly integrable signed martingale that converges almost surely to a positive limit D ∞ , he proved that there exists c > 0 such that for all x ≥ 0,

P(M n ≥ n/e + 3 2e log n + x) = E (exp (-c D ∞ e ex ))
(5.9)

The result was independently obtained in [START_REF] Addario-Berry | Poisson-Dirichlet branching random walks[END_REF] in the specific case of the PWIT.

Recalling the PWIT-IBM interpretation of Z t , t ≥ 0, we note that the functions t → K t and → M , defined in (5.5) and (5.6), respectively, are generalized inverses of one another. Indeed, it is clear that, for all t ≥ 0 and all ∈ Z + ,

Z t ( ) > 0 ⇐⇒ ∃u ∈ N X(u) ≤ t ⇐⇒ M ≤ t,
which implies that the front bin F t in the PWIT-IBM, as defined by (5.5), satisfies

F t = max{ ∈ Z + : M ≤ t}.
(5.10)

Hence, from the asymptotic behavior of M as → ∞ we are able to obtain the asymptotic behavior of F t as t → ∞. This method as already been used by Corre in [START_REF] Corre | Oscillations in the height of the Yule tree and application to the binary search tree[END_REF] in this purpose. However, note that in his description of the Yule process, at each birthing event particles were dying giving birth to two new children. Therefore our result does not align exactly with the one of Corre.

Lemma 5.4 (Corre [31]). For all t ≥ 1, we set

n t = et - 3 2 log t ∈ N and y t = et - 3 2 log t -n t ∈ (0, 1).
For all k ∈ Z, we have

lim t→∞ P(F t ≤ n t + k) -E exp -c D ∞ e yt-k-1 = 0.
Remark 5.5. Lemma 5.4 shows that as t → ∞, F t remains tight around its median but does not converge in distribution, due to the fluctuations of log t -log t .

Proof of Lemma 5.4. By definition of F t , and the fact that M is atomless and increases as increases, we have

.P(F t ≤ n t + k) = P (M nt+k+1 > t) = P (M nt+k+1 ≥ t) , k ∈ N.
In addition, since x → P(M n ≥ n/e + 3 2e log n + x) converges pointwise to a monotone decreasing continuous function from R into [0, 1], we deduce from Dini's theorem that this convergence is uniform. In particular, for any bounded sequence (x n ), we have As a result we obtain that, for all k ∈ Z,

lim n→∞ P(M n ≥ n/e + 3 2e log n + x n ) -E (exp (-c D ∞ e exn )) = 0. Fix k ∈ Z and
lim t→∞ P(M nt+k+1 ≥ t) -E exp -c D ∞ e yt-k-1 = 0,
which completes the proof.

Coupling of the PWIT and the Barak-Erdős graph

We construct a coupling between the PWIT and the Barak-Erdős graph such that the heuristic convergence of neighborhoods of vertex 1 described in Section 5.1 is more explicit as p → 0. Recall that G denotes the -→ G (N, p) Barak-Erdős graph. We will describe the laws of two random subraphs, the connected component C of vertex 1 (the root of G) and a special spanning tree B of C that has the property that the path from every of its vertices to the root has maximal length. We will then change the vertex set of C and, in a sense, put C in continuous time, explaining the "correct" time scale. Having done this, we will explain how to construct B and the PWIT on the same probability space. We will embed B into the PWIT making sure that the edge-relationships are preserved and that the locations (in continuous time) of vertices are also correct.

The law of the set of vertices of C

Let q = 1 -p. Define C as the subgraph of G containing the root, i,e. vertex 1, and all vertices k ≥ 1 such that 1 k (i.e. there is a path in G between 1 and k). We define these vertices recursively, letting κ 0 = 1,

κ i = min{k > κ i-1 : 1 k}, i ∈ N.
Clearly, κ 1 -κ 0 , κ 2 -κ 1 , . . . are independent, (5.11) and, for all i ∈ N

κ i -κ i-1 is geometric(1 -q i ); P (κ -i -κ i-1 > m) = (q i ) m , m ≥ 0. (5.12)
This describes the law of the random set

K = {κ 0 , κ 1 , κ 2 , . . .} = V (C)
of vertices of C (and hence of any spanning tree of C). We can think of K as an inhomogeneous renewal process on N that quickly converges to a homogeneous one. Indeed, q i → ∞ as i → ∞, so fast that the Borel-Cantelli lemma ensures that, eventually, K contains all positive integers. This is another manifestation of the existence of skeleton points, as described in Section 2.1. Note that the rates of the above geometric random variables are increasing with i, indicating that, initially, K is a sparse set (the smaller the p the sparser the K is initially).

The spanning tree B and its law

Let L k = L L,R 1,k , the maximum length of all paths from 1 to k in G. A spanning tree of C is a tree whose set of vertices is K. We say that a spanning tree of C is a maximal length spanning tree if for all κ i ∈ K, the length of the (necessarily unique) path from 1 to κ i equals L κi . To define the special maximal length spanning tree B we need a definition of ordering on the set

K i-1 := {κ 0 , . . . , κ i-1 }
of the first i vertices of C. Roughly speaking, we order the elements of K i-1 in decreasing length, breaking ties in some way. Note that (K i-1 , ) is a totally ordered set and that depends on i (that is, the order on K i is different from the order on K i-1 ). Let now σ : {1, . . . , i} → {0, . . . , i -1} be the unique bijection so that

κ σ(1) κ σ(2) • • • κ σ(i) .
The domain of σ is the set of ranks and κ σ(1) is the vertex of rank 1, κ σ(2) the vertex of rank 2, etc. We always have κ σ(i) = κ 0 and κ σ(i-1) = κ 1 . We also let

ρ := σ -1
denote the inverse function.

Definition 5.7 (Special spanning tree B). The special spanning tree B of C is defined as being the maximal-length spanning tree with the property that, for all i, the unique parent of κ i in B is the minimal element κ j for the order among the elements such that (κ j , κ i ) is an edge in G.

Figure 5 gives an example of the definitions.

To describe the law of the edges of B, we let, for each i ∈ N, the index π(i) be such that κ π(i) is the parent of κ i in B. For any A ⊂ N let G(A) denote the induced subgraph of G on the set A (i.e. the graph that contains as vertices the elements of A and edges only those edges with endpoints in A). Lemma 5.8. With κ π(i) denoting the parent of κ i in B we have q 8 q 7 q 6 q 5 q 3 q 2 1 q 4 q

P(π(i) = σ(r)|G(K i-1 )) = q r-1 (1 -q) 1 -q i ,

Sketch of proof.

To understand this, first note that σ depends only on G(K i-1 ), where K i-1 = {κ 0 , . . . , κ i-1 }. Second, this formula says that the parent of κ i is the least ranked vertex κ j , say, in K i-1 such that (κ j , κ i ) is an edge in G. The denominator 1 -q i expresses the probability that κ i connects to one of the vertices in K i-1 .

Figure 5 shows these probabilities in an example with i = 9.

Remark 5.9. Note that (5.11), (5.12) and (5.13) provide a complete characterization of the law of the special spanning tree B.

The special tree B in continuous time

Putting B in continuous time means replacing its vertex set K by a possibly random subset of (0, ∞) in a way allowing its coupling with the PWIT. Let us start by recalling the clockwork lemma: consider a finite set of positive numbers, say a 1 , . . . , a i . To simulate a random variable that takes value j ∈ {1, . . . , i} with probability proportional to a i , we can use τ 1 , . . . , τ i independent exponential random variables with parameters a 1 , . . . , a i . Then the minimum of these random variables equals τ j with probability a j / i k=1 a k . Fix i and the set K i-1 = {0, 1, . . . , i -1}. We imagine that this set, along with the edges from B, has been constructed at time t. Equip each vertex κ j ∈ K i-1 with an independent exponential random variable τ j , corresponding to the elapsed time after time t at which κ j wishes to connect to a new vertex κ i . We declare that this takes place at time t + τ , where τ = min(τ 1 , . . . , τ i ) and if τ = τ j then it is vertex κ j that will connect to κ i . Let ρ(j) be the rank of κ j , i.e. the the inverse of σ defined in Definition 5.6. We should assign rate q ρ(j)-1 to τ j , as then

P(τ j = τ ) = q ρ(j)-1 1 + q + • • • + q i-1 = q ρ(j)-1 (1 -q) 1 -q i , 0 ≤ j ≤ i -1,
which precisely equal to the probability (5.13). If then we let T (κ i ) be the time of appearance of κ i then we must have

T (κ i ) -T (κ i-1 ) d = τ ∼ exponential(1 + q + • • • + q i-1 ), (5.14)
that is,

T (κ i ) -T (κ i-1 ) ∼ exponential 1 -q i 1 -q .
Hence we can obtain T (κ i ) by an appropriate thinning of a Poisson process.

Lemma 5.10. Let ξ 1 = 0 and 0 < ξ 2 < ξ 3 < • • • be the points of a Poisson(1) point process, independent of the vertex set K = {κ 0 , κ 1 , . . .} of C. Then

pξ κi d = T (κ i ), i = 0,
= n) = (1 -α) n-1 α, n ∈ N), then τ 1 + τ 2 + • • • + τ ν is
exponential with rate αλ, by the standard Poisson thinning theorem. Recall, from eq. (5.12), that κ i -κ i-1 is geometric(1 -q i ). Applying the above thinning theorem we have that ξ κi -ξ κi-1 is exponential with rate (1 -q i ) and so pξ κi -pξ κi-1 is exponential with rate (1 -q i )/p. Hence, from (5.14),

pξ κi -pξ κi-1 d = T (κ i ) -T (κ i-1 )
and the claim follows by independent increments of both sides.

Remark 5.11. This shows that the correct set of vertices of B, if we are to put it in continuous time and create a Markov process, is the set

0 = pξ κ0 < pξ κ1 < pξ κ2 < • • •
To spell out the construction explicitly, we identify every integer vertex κ i with the real number pξ κi and keep the edges intact. Let now B t be the induced subgraph of B on the set of new vertices pξ κi that do not exceed t. Then B t , t ≥ 0, is Markovian.

The coupling

The quantities defined above allow us to give a constructive proof of the following theorem.

Theorem 5.12. Let B be the special spanning tree of G and Π a standard PWIT. Then there is a probability space on which (Π, B) is defined in such a way that there is an injection

Φ : K → N * ,
preserving edges and having the property that

|Φ(κ i )| = L κi , (5.15)
for all κ i ∈ K.

Informal construction of the coupling. We simultaneously construct B t together with Π t at times t. Observe that every particle in Π t gives birth to offspring at unit rate, while a particle pξ j in B t are connected to newly discovered vertex at slower rate 1 -q k , where k is the rank of pξ j for the order . We construct the coupling by strategically selecting the particles in Π corresponding to the vertices in B. For sake of illustration, we think of particles in Π as being blue, unless they correspond to vertices of B via Φ, in which case they are red. We informally refer to particle Φ(κ i ) as vertex κ i .

At time t = 0 the situation is trivial, there is a single red particle in Π 0 corresponding to vertex 1 in B 0 . Fix t > 0, let i be the number of red particles in Π t , corresponding to vertices κ 0 , . . . , κ i-1 in B t . The remaining particles in Π t are blue. We associate to each blue particle an independent blue exponential clock with parameter 1, and to each red particle a pair of independent exponential clocks, such that the rate of the red clock associated to the red particle ranked r is taken to be q r , and the blue clock is 1 -q r . These clocks correspond to the times at which each particle creates a child, with the color of the clock corresponding to the color of the newborn particle.

We consider the time τ corresponding to the smallest of these exponential clocks. At time t + τ , if the clock is blue we add a new blue particle to Π t with position t + τ , which is born from the particle associated to this exponential clock. If the clock at time t + τ is red, we add a new red particle to Π t with position t + τ , connected to the (red) parent particle Φ -1 (κ j ). Simultaneously, we add to B t+τ the vertex κ i , which is connected to the newborn particle in Π t+τ via Φ.

Since red clocks have rate 1, q, . . . , q i-1 , it follows that the particle corresponding to the new vertex will be added after an exponential time of parameter 1 + • • • + q i-1 . Therefore, this time corresponds to pξ κi in distribution, so we set ξ κi = X(Φ -1 (κ i ))/p. It then should be clear, by construction that (Π t ) is the PWIT, B has the law of the special spanning tree, and (5.15) holds, since every edge in B correspond to a parent-child relationship in the PWIT.

As Barak-Erdős graphs with any connecting constant can be associated to the same branching random walk, this coupling also yields a coupling of Barak-Erdős graphs with different constants. It is worth noting that with this coupling, the set of red "coding" particles is decreasing with p. It is also worth observing that typically, the position of the leftmost blue descendant of a red particle tend to be of orderlog p, as newborn red particle occur at rate 1, and the rate at which new blue particle occur can be bounded from above by 1 -(1 -p) n with n the number of red particles born after that particle. The little triangle at the end of blue particles symbolize the blue descendants produced by each blue particle, which play no role in the coupling, hence do not interact with Φ or the times at which the red particles appear. However, the blue particles represented here play a role, as they influence the label given to each of the red particle.

Example 5.13. We refer to the example drawn in Figure 6. We start with κ 0 as a root particle of the PWIT. Since κ 0 is red and has rank 1 its red clock has rate q 1-1 = 1, so its blue clock has rate 1 -1 = 0. That is, κ 0 , at this stage, produces red offspring. The first offspring, κ 1 , appears at an exponential time with parameter 1 + q + • • • + q i-1 with i = 1, hence at an exponential(1) time, that can be taken to be pξ κ1 . We set Φ(κ 1 ) = 1. At this time, κ 1 has rank 1 and κ 0 has rank 2. Therefore the red and blue clocks of κ 1 have rates 1, 0, respectively, while the red and blue clocks of κ 0 have rates q, 1 -q respectively. Hence κ 2 is appears at time differing from pξ κ1 by an exponential(1 + q) random variable, that is, at time pξ κ2 . Moreover, κ 2 has parent κ 1 with probability 1/(1 + q) = (1 -q)/(1 -q 2 ) or κ 0 with probability q/(1 + q) = q(1 -q)/(1 -q 2 ). Suppose the latter happens. If κ 0 had produced 2 blue offspring then Φ(κ 2 ) = 4, as it is its third offspring. Once κ 2 is added we have that κ 2 has rank 1 so has no blue clock, κ 1 has rank 2 so it has a red clock at rate q and a blue at rate 1 -q, while κ 0 has the least rank, 3, and has a red clock at rare q 2 and a blue at rate 1 -q 2 . At time pξ κ3 the new particle κ 3 is added and if it chooses κ 2 as parent then its label is Φ(κ 2 )1 = 41, since κ 2 produced no offspring, so κ 3 is its first one.

We may call the times pξ κi at which a new vertex of B appears in Π as embedded times. We define for ∈ Z + M = inf{X(u) : u red particle with |u| = } and for t ≥ 0 Ft = max{ ∈ Z + : M ≤ t}, which are the analogue of (M ) and (F t ) defined in (5.10), restricted to the set of red particles from the coupling.

Corollary 5.14. The process ( Ft , t ≥ 0) and (L k , k ≥ 0) where L k = L L,R k , are related by

F pξκ i = max 0≤j≤i L κj .

Longest chain issued from the initial vertex

The length of the longest path issued from the vertex 1 is studied using the branching random walk coupling described above. This coupling was introduced by Newman [START_REF] Newman | Chain lengths in certain random directed graphs[END_REF] for this purpose. In particular, using this coupling, he obtained the following result for the asymptotic behavior of L n as a function of p. Theorem 5.15 (Newman [83]). Let (p n ) be a null sequence.

1. If lim n→∞ np n = t ∈ (0, ∞), then lim n→∞ L (1) n (p n ) = F t in distribution. 2. If lim n→∞ np n = ∞, then lim n→∞ L (1) n (p n )/np n = e in probability.
Proof. We first assume that np n → t ∈ (0, ∞). In this situation, the connected component of the vertex 1 in the Barak-Erdős graph G(n, p n ) converges, as n → ∞ to (X(u), u ∈ U : X(u) ≤ t), using the branching random walk coupling.

Indeed, the number of vertices in this connected component remains tight as n → ∞, the probability of observing one extra edge between two vertices in the component goes to 0. Therefore, C (pn) ∩[1, . . . n] is a tree with high probability for n large enough, hence B (pn) ∩[0, n] = C (pn) ∩[0, n] with high probability, which completes the proof using Theorem 5.12.

We deduce that the length of the longest path in this connected component is the same as the length of the longest path in the tree. This longest path is given by the largest generation F t at which there is at least one individual to the left of t, completing the proof.

We now assume that np n → ∞, and we use once again the coupling describe in Theorem 5.12. By law of large numbers, the position ξ κn of the nth vertex in the coupling satisfies p n ξ κn /np n → 1 a.s. as n → ∞. Then, using (5.9), for all ε > 0, for n large enough we have M enpn(1+ε) ≥ np n (1 + ε/2). Therefore, almost surely for n large enough, the longest path issued from 1 will be shorter than en(1 + ε), i.e. lim n→∞ L n np n ≤ e a.s.

For the lower bound, we fix t > 0, and we consider in a first time the length of the longest path in the restriction of the Barak-Erdős graph to the set {1, . . . , t/p n }. Thanks to the previous case, we know that the length of this path converges to F t . Moreover, the smallest vertex with index larger than t/p n connected to this path is positioned at geometric distance with parameter p n from t/p n . Therefore, with high probability, there exists a path of length at least F t (1 -ε) starting from vertex 1 and ending at a vertex of index between (t + 1/2)/p n , (t + 2)/p n .

Chaining this argument, we obtain that with high probability,

L (n) 1 (p n ) is larger than the sum of np n /(t + 2) independent copies of F t . Letting n → ∞, then ε → 0, we obtain lim n→∞ L n np n ≥ E(F t ) t .
Then using (5.7), we have lim t→∞

E(Ft) t
= e, which completes the proof.

Theorem 5.15 gives the precise asymptotic behavior of L n (p n ) as long as lim n→∞ np n < ∞. However, when np n → ∞, it only gives the first order of its asymptotic expansion. Using the coupling described in Theorem 5.12, Itoh [START_REF] Itoh | Continuum Cascade Model: Branching Random Walk for Traveling Wave[END_REF] showed that the asymptotic behavior of the branching random walk applies to the sparse Barak-Erdős settings, and that as long as np n → ∞ "slowly enough", we have lim

n→∞ sup k∈N |P(L n (p n ) = k) -P(F npn = k)| = 0, (5.16)
showing that the law of L n has the same asymptotic behavior as F npn in this regime, described in Lemma 5.4. In particular, this results states that (L n (p n ) -np n e -3 2e log np n ) remains tight. However, this asymptotic behavior fails to hold when p n decays too slow. The branching random walk associated to the Barak-Erdős graph gives a good description of the connected component of 1 as long as the number of blue balls below position np n remains small. This is for example true assuming np n converges to a constant, under which conditions the number of blue balls before np n go to 0 as n → ∞. On the opposite end of the spectrum, if p remains constant, the asymptotic behavior of L n differs sharply from the one of F np . Indeed the leftmost particle will tend to be blue with high probability.

The behavior of red particles in the branching random walk can be compared to a branching random walk with selection. Indeed, when considering dynamically their behavior, we observe that the kth largest red ball produces a red offspring at rate q k . In particular, if k -log p, particles branch at a rate close to 1, similarly to the usual branching random walk, while if k -log p, the branching rate of that particle is close to 0. The set of red balls can therefore be closely estimated by the set of surviving particles in the branching random walk with selection of the N ≈ -log p rightmost particles.

The branching random walk with selection of the N rightmost particles evolves according to the following procedure. At each generation, all particles reproduce independently, a particle at position x giving birth to a Poisson point process with unit intensity on [x, ∞). Among all children of these particles, only the N leftmost are selected to constitute the new generation of the process.

It is worth observing that this process can be straightforwardly embedded in the branching random walk. We write D N for the set of particles in the branching random walk that form the branching random walk with selection of the N rightmost generation, i.e. such that for all n ∈ N,

D N ∩ {|u| = n} is the set of the N leftmost children of the particles in D N ∩ {|u| = n -1}.
Bérard and Gouéré [START_REF] Bérard | Brunet-Derrida behavior of branching-selection particle systems on the line[END_REF] first proved the Brunet-Derrida behavior for a branching random walk with binary branching and selection of the N rightmost individuals. This result was extended by Mallein [START_REF] Bastien Mallein | Branching random walk with selection at critical rate[END_REF] to more general reproduction laws covering the present case. From Kingman's subadditive theorem, we know the existence of a sequence (v N ) such that for each N ∈ N,

lim n→∞ 1 n max u∈D N ,|u|=n = v N a.s.
The Brunet-Derrida behavior of this branching random walk can be stated as follows

v N = e - π 2 e(1 + o(1)) 2(log N ) 2
as N → ∞.

(5.17)

Using the coupling between the branching random walk and the Barak-Erdős graph, and the fact that the set of red particles is well-approximated by the set D (-log p) 2 , we obtain the following result.

Theorem 5.16 (Mallein and Ramassamy [77]). We have

C(p) = pe-π 2 e 2 p(-log p) -2 +o p(-log p) -2 .
This asymptotic behavior extends to sparse Barak-Erdős graphs, as long as p n decays to 0 slowly enough, we have

L n np n = e - π 2 e 2(-log p n ) 2 (1 + o(1)).
(5.18)

The question of distinguishing sequences p n for which L n exhibit a behavior similar to (5.16) or (5.18), or do distinguish an intermediate behavior remains open. In order to obtain a proper insight on this question, we begin by giving a proof scheme for Theorem 5.16.

Scheme of proof of Theorem 5.16. Observing that typically, the leftmost blue particle born from a given red particle is produced at a time when the particle at a distance of orderlog p of the position of the leftmost current red particle in the system, we observe that for any δ > 0, the set of red particles alive at a large generation n is included in D (1+δ) -log p , and contains all particles alive at generation n in D (1-δ) -log p for all p large enough. Using (5.17), we deduce that the leftmost red particle at a large generation n is situated in [nv (1-δ) -log p , nv (1+δ) -log p ]. Then, using Corollary 5.14, we deduce that with high probability,

L n p ∈ [nv (1-δ) -log p , nv (1+δ) -log p
Letting n → ∞, then δ → 0 and finally p → 0, Theorem 5.16 will hold.

We observe that in the proof of Theorem 5.16, we used the coupling with the branching random walk to compare the connected component of the vertex 1 with the set of particles in the branching random walk staying at all time within distancelog p from the position of the leftmost particle. Note also that we are interested in the position of the minimal displacement at time np n .

Chen [START_REF] Chen | Scaling limit of the path leading to the leftmost particle in a branching random walk[END_REF] proved that in a branching random walk, the trajectory yielding to the minimal position at time n can be scaled in time by a factor n and in space by a factor √ n to converge to a standard Brownian excursion. In particular, we know that typical trajectory yielding to the minimal position at time n remains at all time within distance √ t from the leftmost position. As a result, it is expected that as long aslog p n √ np n , the asymptotic behavior of the position of the minimal displacement at time n is similar in the branching random walk and in thelog p n -branching random walk. On the opposite, iflog p n (-log p n ), similar techniques as the ones used in [START_REF] Bastien Mallein | Branching random walk with selection at critical rate[END_REF] show that the minimal displacement becomes more similar to the branching process with selection.

As a result, we formulate the following conjecture for the asymptotic behavior of the length of the longest path starting from 1 in sparse Barak-Erdős graphs.

Conjecture 5.17. Let (p n ) be a null sequence with np n = ∞.

1. If lim n→∞ np n / log n 2 = 0, then (5.16) holds.

2. If there exists δ > 0 such that lim n→∞ np n /(log n) 2+δ = ∞, then (5.18) holds.

Extension to stochastic ordered graphs with geometry

In this section, we consider the two following planar extensions of the Barak-Erdős graph. In both cases, the set of vertices of the graph is N 2 . In the first model, for all pair of distinct vertices (i, j) and (k, l) a directed edge between (i, j) and (k, l) is present with probability p independently on any other edges if and only if i ≥ k and j ≥ l (and (i, j) = (k, l)). This random graph is written G (1) (p). In the second model, a directed edge is present with probability p between (i, j) and (k, l) if and only if i = k and j > l, or j = l and i > k. We denote by G (2) (p) this random graph. We also write G (1) (n, m, p) (respectively G (2) (n, m, p)) the restriction of G (1) (p) (resp. G (2) (p)) to the vertex set {1, . . . n} × {1, . . . , m}.

Similarly to the Barak-Erdős graph, the connected component of the vertex (1, 1) can be described, in the sparse limit p → 0 as a branching random walk. More precisely, in the graph G (1) (p), rescaling the vertex indices by p 1/2 , the connected component of (1, 1) converges to a branching random walk X (1) on R 2 + , in which a particle at position (x, y) gives birth to a Poisson process of offspring on [x, ∞) × [y, ∞) with unit intensity. This branching random walk provides an example of stable branching process as defined in [START_REF] Bertoin | Branching-stable point measures and processes[END_REF].

When scaling the vertex indices by p, the connected component of the vertex (1, 1) converges, as p → ∞ to a branching random walk X (2) on R 2 + in which a particle at position (x, y) gives birth to a Poisson process of offspring on {x} × [y, ∞) and an independent Poisson process of offspring on [x, ∞) × {y} with unit intensity.

Using similar methods as the ones used in the Barak-Erdős graph, we can obtain the following results. First, observing that the law of X (1) is stable by the transformation (x, y) → (x/a, ay), and that lim

n→∞ 1 n min X (1) (u) ∞ = 2 e a.s.
and applying the same proof as in [START_REF] Newman | Chain lengths in certain random directed graphs[END_REF], we obtain the following estimate for the length of the longest path starting from vertex 1.

Theorem 5.18. We denote by L n,m (p) the length of the longest path issued from (1, 1) in G (1) (n, m, p).

1. If p → 0 with mnp → t, then L n,m (p) converges in law to K(t) = max{|u| : X (1) (u) ∈ [0, √ t] 2 }. 2. If p → 0 with mnp → t, then L n,m (p)/ √ mnp → e/2 in probability.
Similarly, we can obtain the following estimate for the asymptotic behavior of the length of the longest path issued from 1 in the graph G (2) (n, n, p). Theorem 5.19. We denote by L n (p) the length of the longest path issued from (1, 1) in G (2) (n, n, p).

1. If p → 0 with np → t, then L n (p) converges in law to K(t) = max{|u| : X (1) (u) ∈ [0, t] 2 }. 2. If p → 0 with np → t, then L n (p)/np → e/(1 -log 2) in probability.

Longest path in the Barak-Erdős graph

We now turn to the length of the longest path in the Barak-Erdős graph in the sparse regime. Again, Newman [83, Theorem 2] obtained a completed description of the asymptotic behavior of L n (p n ) as long as np n = O(log n). Moreover, he proved that as long as np n log n, then the asymptotic behavior of L n (p n ) and L [START_REF] Addario-Berry | Poisson-Dirichlet branching random walks[END_REF] n (p n ) are similar. We decompose the asymptotic behavior of the length of the longest path in the Barak-Erdős graph along the following lines. We first assume that p n = o(n 1-ε ) for some ε > 0. In this situation, the support of the length of the longest path in the Barak-Erdős graph converges to one or two points, depending on the exact asymptotic behavior of p n . Remark that with high probability 1 will not be connected to any other vertex in the graph, so L [START_REF] Addario-Berry | Poisson-Dirichlet branching random walks[END_REF] n (p n ) converges to 0 in probability. Theorem 5.20 (Newman [83], Theorem 2). Let (p n ) be a null sequence such that lim n→∞ n 1+ε p n = 0 for some ε > 0. 3. If there exists θ ∈ (0, ∞) and m ∈ N such that

1. If lim n→∞ n 2 p n = 0, then lim n→∞ L n (p n ) = 0 in probability.
lim n→∞ p n n 1+1/m = θ, then lim n→∞ P(L n (p n ) = m -1) = 1 -lim n→∞ P(L n (p n ) = m) = e -θ m (m+1)! .
Proof. This result is obtained using first and second moment methods, computing the first and second moment of the number Z k (n, p) of paths of length k. Then, using the Markov inequality from one part and the Cauchy-Schwarz inequality for the second, we have

E(Z k (n, p)) ≥ P(Z k (n, p) ≥ 1) ≥ E(Z k (n, p)) 2 /E(Z k (n, p) 2 ).
We first note that in the complete graph on the vertex set {1, . . . , n}, there is n k+1 increasing paths, each of which having probability p k to be open in the Barak-Erdős graph. Therefore,

E(Z k (n, p)) = n k + 1 p k ≈ n k+1 p k k! .
With similar computations, we have that

E(Z k (n, p) 2 ) =
{i1,...,i k+1 }⊂{1,...,n} {j1,...,j k+1 }⊂{1,...,n}

P((i 1 , i 2 ), . . . (j k , j k+1 ) ∈ E(G)).
Observing that if two paths have r vertices in common, they have at most r -1 edges in common, we obtain

E(Z k (n, p) 2 ) ≤ n k + 1 n -k -1 k + 1 p 2k + k+1 r=1 n k + 1 n -k -1 k -r + 1 p 2k-r-1 ≈ (n k+1 p k ) 2 + k+1 r=1 n 2k+2-r p 2k-r-1 .
If n 2 p n → 0 as n → ∞, we have

P(L n (p n ) ≥ 1) = P(Z 1 (n, p n ) ≥ 1) ≤ n(n -1) 2 p n . Therefore lim n→∞ P(L n (p n ) = 0) = 1, showing that L n (p n ) → 0 in probability.
We now assume that there exists m ∈ N such that

lim n→∞ p n n 1+1/m = ∞ and lim n→∞ p n n 1+1/(m+1) = 0.
We observe that

P(L n (p n ) ≥ m + 1) = P(Z m+1 (n, p n ) ≥ 1) ≤ E(Z m+1 (n, p n )) n m + 1 p m n .
Then, as lim n→∞ n m+1 p m n = 0, we deduce that lim n→∞ P(L n (p n ) ≥ m + 1) = 0. Similarly, we have

P(L n (p n ) ≥ m) = P(Z m (n, p n ) ≥ 1) ≥ E(Z m (n, p n )) 2 /E(Z m (n, p n ) 2 ) ≥ 1 1 + m+1 r=1 ( n-k-1 k-r+1 ) ( n-k-1 k+1 ) p -r-2 n .
But as lim n→∞ n -r p -r-2 n = 0 for all r ≤ m + 1 by assumption, we obtain that lim n→∞ P(L n (p n ) ≥ m) = 1, completing the proof that L n (p n ) → m in probability in that case.

Next, assuming that p m n n m+1 → θ m , we show that Z m (n, p n ) converges to a Poisson random variable with parameter θ m /(m + 1)!. Indeed, Z m (n, p n ) is the sum of n m+1 Bernoulli random variables with parameter θ m /n m+1 . We then observe that the sum of the covariances of these Bernoulli random variables converges to 0 as n → ∞, proving this convergence. As a result, we obtain lim

n→∞ P(L n (p n ) ≥ m) = lim n→∞ P(Z m (n, p n ) ≥ 1) = 1 -e -θ m /m! ,
and as P(L n (p n ) ≥ m -1) → 1 using the same computations as above, we have obtained the convergence in law of L n (p n ).

We then consider the asymptotic behavior of L n (p n ) assuming that np n = o(log n). In this regime, recall that the length of the longest path issued from vertex 1 is of order enp n = o(log n). The following result holds. Theorem 5.21. Let (p n ) be a null sequence such that lim n→∞ n 1+ε p n = ∞ for all ε > 0 with lim n→∞ np n / log n = 0. We set

n = sup k ∈ N : n k p k n ≤ 1 , then lim n→∞ L n (p n )/ n = 1 in probability.
This result is obtained in the same way as Theorem 5.20, using first and second moment methods to bound the probability of existence of a path of length n (1 ± ε). Using similar methods again, one can turn to the case p n ∼ γ log n/n. In this situation, L [START_REF] Addario-Berry | Poisson-Dirichlet branching random walks[END_REF] n (p n ) ∼ γe log n, and the longest path also is of order log n, but with a larger constant. Theorem 5.22. Let (p n ) be a sequence such that p n ∼ γ log n/n as n → ∞ for some γ ∈ (0, 1).

Then lim n→∞ L n (p n )/np n = eA(γ) in probability,
where A(γ) is the only solution larger than 1 of x log x = (eγ) -1 .

Finally, when np n log n, the length of the longest path and the longest path starting from 1 have similar orders of magnitude.

Theorem 5.23. Let (p n ) be a null sequence such that lim n→∞ np n / log n = ∞, then lim n→∞ L n (p n )/np n = e.
To bound L n (p n ) from above, we use again first moment estimates, showing that

lim n→∞ P(L n (p n ) > np n e) = 0. Using that L n (p n ) ≥ L (1)
n (p n ) on the other hand and Theorem 5.15, we conclude to Theorem 5.23.

Shortest path

Based on similar computations with the previous section, we are able to compute the asymptotic behavior of the length of the shortest path between 1 and n in the Barak-Erdős graph -→ G (n, p). The results in this section are based on [START_REF] Mallein | On the length of the shortest path in a sparse Barak-Erdős graph[END_REF]. In this section, we write

S n (p) = min k ∈ N : ∃i 1 < • • • < i k-1 : (1, i 1 ), . . . , (i k-1 , n) ∈ E( - → G (n, p)) .
the length of the shortest path linking 1 and n. By convention, S n = ∞ if there is no path between 1 and n.

Observe that for a fixed value of p, the edge (1, n) is present with probability p, and if this edge is not present, the events

({(1, k), (k, n) ∈ E( - → G (n, p))}, 2 ≤ k ≤ n)
are independent of one another, and with same probability p 2 of occurrence. As a result, we have

P(S n (p) = 1) = p, P(S n (p) = 2) = (1 -p)(1 -(1 -p 2 ) n-2 ).
Therefore, S n (p) converges in distribution, as n → ∞, to a random variable S ∞ (p) with P(S

∞ (p) = 1) = 1 -P(S ∞ (p) = 2) = p. With similar computations, it appears that if p n → 0 with np 2 n → ∞, then S n (p n ) → 2 in probability as n → ∞.
The above computation extends to larger paths, and we obtain the following extension of the results of Section 5.6. Theorem 5.24. Let (p n ) be a null sequence.

If there exists an integer

m ∈ N such that lim n→∞ p n n 1-1/(m+1) = ∞ with lim n→∞ p n n 1-1/m = 0, then S n (p n ) → m + 1 in probability.
2. If there exists an integer m ∈ N such that

lim n→∞ p n n 1-1/m = θ ∈ R + , then lim n→∞ P(S n (p n ) = m) = 1 -lim n→∞ P(S n (p n ) = m + 1) = e -θ m /(m-1)! 3. If lim n→∞ n 1-ε p n = ∞ for all ε > 0, then lim n→∞ S n (p n )/ n = 1 in probability,
where n is the same quantity as in Theorem 5.20.

For a graph with too small value of p, the vertices 1 and n will no longer be connected with high probability. It is well-known for Erdős-Rényi graphs that as long as p n > (1 + ε)/n, vertices 1 and n will be in the same connected component with positive probability. However, this does not implies the existence of a directed path from 1 to n in the graph, and in fact the coupling with the branching random walk shows that as long as lim n→∞ np n < ∞, the probability that 1 and n are in the same connected component goes to 0 as n → ∞.

The critical decay rate at which the probability that 1 and n are connected in -→ G (n, p n ) with positive probability is currently unknown, as well as the asymptotic behavior of S n (p n ) for p n ∼ (log n) α /n for some α > 0.

Regenerative properties of directed random graphs

We now return to the setup of Section 2.1 and consider the case where we are given a sequence p 1 , p 2 , . . . of numbers in [0, 1] such that 0 < p 1 < 1.

The case p 1 = 1 is excluded because it uninteresting. We assume that p 1 > 0 so that the regenerative methods work: as will be shown in Section 6.1, we can then break the graph into i.i.d. pieces. For the p 1 = 0 case see Remark 6.10 below.

We then consider the random graph on Z such that the pair (i, j) ∈ Z × Z is a vertex if i < j and with probability p j-i , independently from pair to pair. Let us denote this graph by -→ G (Z, (p j )). The reason for introducing probabilities that depend on the physical distance between vertices is twofold: from the point of view of applications, it is more natural; mathematically, the case of constant p j , insofar as regenerative properties are concerned, is not much different from the more general case. Let

q j := 1 -p j , Q j := q 1 • • • q j , Q 0 := 1.
Our goal is to proved a functional central limit theorem for the quantity L 0,n , the maximum length of all pathr in -→ G (Z, (p j )) with endpoints between 0 and n. This is Theorem 6.8. To do this, we first exhibit some regenerative properties of the graph and then estimate moments of the distances between two typical skeleton points.

Breaking the graph into independent cycles

We showed in Lemma 2.6, that if the sequence p j does not convergence to 0 too fast, in the sense that condition (2.7) of Lemma 2.6,

∞ n=1 Q n < ∞,
holds, then the skeleton set S of all vertices v such that u v w for all u < v < w (where i j stands for "there is a path from i to j") is infinite in both directions a.s. and has strictly positive rate

λ = ∞ j=1 (1 -Q j ) 2 > 0, (6.1)
as in (2.8). We label the elements of S by random integers Γ k , k ∈ Z, so that

• • • < Γ -1 < Γ 0 ≤ 0 < Γ 1 < Γ 2 < • • • (6.2)
We therefore know that P(0 ∈ S ) = λ > 0 and

E(Γ k+1 -Γ k |0 ∈ S ) = E(Γ k+1 -Γ k |Γ 0 = 0) = 1/λ < ∞, k ∈ Z.

Moments of auxiliary stopping times

We aim at studying the moments of the auxiliary random vertices µ and ν, defined in (6.5) and (6.8), respectively. These random vertices are positive integers and stopping times with respect to the filtration, in the index n, generated by the (α (k) , k ≤ n). The stopping time property is crucial in constructing, in Section 6.3, certain iterates of µ and ν, used for identifying the least positive skeleton point of the graph.

We need some notation, partially introduced in the proof of Lemma 2.6. Recalling that i j means that there is a path in -→ G (Z, α) from i to j, we let J ⊂ Z and write i J if i j for all j ∈ J. Similarly, J i means j i for all j ∈ J. We will need the events

A + u,v = {u [u + 1, v]}, A - u,v = {[u, v -1] v}, (6.4)
where u < v are integers. By [a, b] when a, b are integers, a < b, we mean the set {a, a + 1, . . . , b}.

We have (j) = max{k > 0 : α j-k,j = 1} and r(j) = min{k > 0 : α j,j+k = 1} for all j ∈ Z. Hence j -(j) is the first predecessor of j in -→ G (Z, (p j )) and j + r(j) its first successor. The (j), j ∈ Z are i.i.d. with common distribution determined by

P( (0) > k) = Q k = P(r(0) > k). In particular, E (0) = Er(0) = ∞ k=0 Q k . A few moments of reflection show that, for d ∈ N, A + u,u+d = { (u + 1) ≤ 1, . . . , (u + d) ≤ d} A - u-d,u = {r(u -1) ≤ 1, . . . , r(u -d) ≤ d}.
Both events decrease as d increases. Define the random variable

µ := inf{k ∈ N : A + 0,k fails} (6.5)
(where "A fails" stands for "A c occurs", that is, 1 A c = 1 a.s.) Since A + 0,k decreases as k increases, we have

P(µ > k) = P(A + 0,k ) = P( (1) ≤ 1, . . . , (k) ≤ k) = (1 -Q 1 ) • • • (1 -Q k )
, and this implies that µ is defective:

P(µ = ∞) = lim k→∞ (1 -Q 1 ) • • • (1 -Q k ) = √ λ > 0.
We also have

P(n < µ < ∞) = P A + 0,n ∩ ∞ k=1 (A + 0,k ) c = P A + 0,n ∩ ∞ k=n+1 (A + 0,k ) c = P A + 0,n ∩ ∞ k=n+1 A + 0,k c = P( (1) ≤ 1, . . . , (n) ≤ n; { (1) ≤ 1, . . . , (n) ≤ n, (n + 1) ≤ n + 1, . . .} c ) = P( (1) ≤ 1, . . . , (n) ≤ n; { (n + 1) ≤ n + 1, (n + 2) ≤ n + 2, . . .} c ) = P( (1) ≤ 1, . . . , (n) ≤ n) P(∃k > n (k) > k) (6.6) = P( (1) ≤ 1, . . . , (n) ≤ n) [1 -P( (n + 1) ≤ n + 1, (n + 2) ≤ n + 2, . . .)] = (1 -Q 1 ) • • • (1 -Q n ) [1 -(1 -Q n+1 )(1 -Q n+2 ) • • • ] (6.7) = (1 -Q 1 ) • • • (1 -Q n ) - √ λ.
We obtain an upper bound of this easily from (6.6):

P(n < µ < ∞) ≤ P(∃k > n (k) > k) ≤ ∞ k=n+1 P( (k) > k) = ∞ k=n+1 P( (0) > k) = ∞ k=n+1 Q k ,
and this upper bound converges to 0 as n → ∞ by the assumption that the sequence (Q n ) is summable. We also have an asymptotic lower bound by using (6.7), the inequality (1

-Q 1 ) • • • (1 - Q n ) ≥ √
λ, for all n, and the fact that (1 -e -x )/x decreases as x increases:

P(n < µ < ∞) ≥ √ λ 1 -e -(Qn+1+Qn+2+••• ) ≥ √ λ 1 -e -E (0) E (0) ∞ k=n+1 Q k .
We have thus proved

Lemma 6.3. √ λ 1 - √ λ 1 -e -E (0) E (0) ∞ k=n+1 Q k ≤ P(µ > n|µ < ∞) ≤ 1 1 - √ λ ∞ k=n+1 Q k .
Since Q k = P( (0) > k), the above inequality says that the tail of the distribution of µ conditional on it being finite is comparable to the "integrated" tail of the distribution of (0). We say that a positive random variable Z has p-moment, for p ≥ 1, if EZ p < ∞; we say that it has an exponential moment of Ee θZ < ∞ for some θ > 0. From the above lemma we conclude the following. Corollary 6.4. Conditional on {µ < ∞}, µ has a p-moment (respectively, exponential moment) if and only if (0) has a (p + 1)-moment (respectively, exponential moment).

We similarly wish to examine the moments of the random variable

ν := inf{k ∈ N : A - 0,k occurs}. ( 6.8)
Since A - 0,k is not monotonic in k, we need to use an argument different than before. First observe

that ν = inf{k ∈ N [0, k -1] k} = inf{k ∈ N : r(k -1) ≤ 1, . . . , r(0) ≤ k}.
Define a sequence of nonnegative integer-valued random variables x n , n = 0, 1, . . ., by x 0 = 0 and

x n = max{r(0) -n, r( 1) -(n -1), . . . , r(n -1) = 1}.

Then ν = inf{n ∈ N : x n = 0}.

But the x n satisfy x n+1 = max(x n , r(n)) -1, n ≥ 0, and since the r(n) are i.i.d., the sequence (x n ) is Markovian. For any integer K > 0, if x n ≥ K, then

x n+1 -x n = (r(n) -x n ) + -1 ≤ (r(n) -K) + -1.
Since r(0) has finite expectation, we have that E(r(0) -K) + < 1, for K large enough. Therefore, after the Markov chain leaves the interval [0, K], it is upper-bounded by a random walk with increments distributed like (r(0) -K) + -1 whose mean is negative. By standard properties of random walks this implies that the finiteness of the p-th moment of the return time T K to the set [0, K] is eqiuvalent to the finiteness of the p-th moment of the positive part of the increments and, in turn, to the finiteness of the p-th moment of r(0) which is the same as the p-th moment of (0). Similar conclusions are made for exponential moments. We have thus proved: Lemma 6.5. ν has a p-moment (respectively, exponential moment) if and only if (0) has a p-moment (respectively, expomential moment). Remark 6.6. Since P( (0) > k) = Q k , k ≥ 0, we see that (0) has p-th moment if and only iff

∞ k=1 k p-1 Q k < ∞
. and (0) has an exponential moment if and only if

∞ k=1 z k Q k < ∞ for some z > 1.
In particular, these conditions hold if p j = p ∈ (0, 1) for all j,

The results above are used in the proof of the following functional central limit theorem. Theorem 6.9. Consider the random graph -→ G (Z, (p j )), assuming 0 < p 1 < 1, and

∞ k=1 k 2 (1 -p 1 ) • • • (1 -p k ) < ∞.
For integers i < j, let L i,j be the maximum length of all paths with endpoints between i and j. Let Γ k , k ∈ Z, be the skeleton points, assuming Γ 0 ≤ 0 < Γ 1 , and C the constant appearing in the law of large numbers for L 0,n as in Lemma 2.1. Then

0 < σ 2 := var(L Γ1,Γ2 -C(Γ 2 -Γ 1 )) < ∞ (6.12) Define n (t) := L 0,[nt] -Cnt σ √ λn , t ≥ 0, n ∈ N.
Considering the sequence n , n ∈ N, as a sequence of random elements of the Skorokhod space D[0, ∞) (see [START_REF] Billingsley | Convergence of Probability Measures[END_REF]), equipped with the topology of local uniform convergence, converges in distribution to a standard Brownian motion.

Sketch of proof. We have λ > 0 because p 1 > 0. It is clear that σ 2 > 0. The reason that σ 2 is finite follows L Γ1,Γ2 ≤ Γ 2 -Γ 1 and Theorem 6.8 which guarantees that

E[(Γ 1 -Γ 2 ) 2 ] = E[(Γ 1 -Γ 0 ) 2 |Γ 0 = 0] < ∞.
From Remark 6.2 we also have that EΓ 1 < ∞. Let N n = max{j ≥ 1 : Γ j ≤ n}. By the definition of S , if v ∈ S then the maximal path from some u < v to some w > v must necessarily include v. Hence

L 0,n = L 0,Γ1 + L Γ1,Γ2 + • • • + L Γ Nn ,n .
We can then write

n (t) = L 0,Γ1 -CΓ 1 σ √ λn + 1 σ √ λn Nnt i=2 L Γi-1,Γi -C(Γ i -Γ i-1 ) + L Γnt,nt -C(nt -Γ Nnt ) σ √ λn (6.13)
Define also

n (t) := 1 σ √ λn nt i=2 L Γi-1,Γi -C(Γ i -Γ i-1 ) , ϕ n (t) := N nt n .
The first and third terms of (6.13) converge to 0 in distribution, as random elements of D[0, ∞).

The middle term is simply equal to n •ϕ n . Hence the limit of n exists if and only if the limit of n •ϕ n exists, in which case the limits are equal. But n converges in distribution to 1 √ λ B, where B is a standard Brownian motion, and ϕ n converges in distribution to the function ϕ, where ϕ(t) = λt. Therefore, by the continuity in D[0, ∞), of the composition operator, we have n •ϕ n converges in distribution to the process 1 √ λ B(λt), t ≥ 0, which is equal in distribution to B. Hence n converges in distribution to B. Remark 6.10. We made the assumption that p 1 > 0 in order that the set S serve as a skeleton set over which the graph regenerates, that is, we have independent pieces. If p 1 = 0 then S is useless; for example, λ = 0 in this case. However, if p 1 = • • • = p j = 0 but p j+1 > 0 then we can establish a 1-dependent structure. 11 One can still deal with this case, but one needs a somewhat different technique based on weakly regenerative processes. Remark 6.11. At this stage, we have no estimate for the variance (6.12). Estimating this is probably a complex problem even for the case when all the p j are equal. Remark 6.12. Observe that in -→ G (Z, p), with positive probability, there are many maximal length paths between successive skeleton points. Since λ > 0, this implies that the number of linear extensions of the random partial order induced by the edges on n vertices increases exponentially fast, and this allows one to obtain directly the CLT for the logarithm number of linear extensions [START_REF] Alon | Linear extensions of a random partial order[END_REF]. Remark 6.13. Note that the events appearing in the definition of S depend on the entire random sequence of edges but, nevertheless, produce a regenerative structure. This phenomenon, in a more general context, has been studied in [START_REF] Foss | Stochastic sequences with a regenerative structure that may depend both on the future and on the past[END_REF].

Directed random graphs on partially ordered sets

A direction towards generalizations of the Barak-Erdős graph on the set of integers, is to consider a set of vertices V equipped with a partial order. The directed random graph must respect the partial order of V . We will consider two cases below, that of V = Z × I where I is a finite set and that of V = Z × Z. We shall deal with law of large numbers and functional central limit theorems and see that asymptotic normality fails. There is an interesting connection with Brownian last passage percolation [START_REF] Gravner | Limit theorems for height fluctuations in a class of discrete space and time growth models[END_REF][START_REF] Baryshnikov | GUEs and queues[END_REF]. The Brownian last passage percolation process is the one defined by (7.1) below. The results of this section are taken from [START_REF] Denisov | Limit theorems for a random directed slab graph[END_REF] and [START_REF] Konstantopoulos | Convergence to the Tracy-Widom distribution for longest paths in a directed random graph[END_REF].

Brownian last passage percolation

Consider V = Z × I where, for simplicity, let I = {0, 1, . . . , M } for a positive integer M . Elements of V are denoted by (u, i), (v, j), etc. Define the standard partial order on V , denoted by by

(u, i) (v, j) if (u, i) = (v, j) and u ≤ v, i ≤ j.
Consider the random graph -→ G (V, p), with 0 < p < 1 with edges defined as follows. A pair of vertices (u, i), (v, j), with (u, i) (v, j), form an edge directed from (u, i) to (v, j) with probability p, independently from pair to pair. We consider all directed paths from (u, i) to (v, j) and denote by L (u,i),(v,j) the maximum length of all such paths. We also let

L * u,v = maximum length of all paths with endpoints in the [u, v] × I, L * n := L * n .
We are interested in the LLN and CLT for L * 0,n as n → ∞. Regarding the LLN the ergodic arguments of Section 2.1 go through, provided we consider the shift θ that acts in the horizontal direction only. We can then easily obtain that, for the same constant C = C(p) corresponding to the Barak-Erdős graph -→ G (Z, p), we have

L * n /n → C, as n → ∞, a.s. and in L 1 ,
where C is the constant for the Barak-Erdős graph -→ G (Z, p). The CLT is more interesting. It involves a process that appears e.g. in [START_REF] O'connell | A representation for non-colliding random walks[END_REF].

Theorem 7.1. Consider the random graph -→ G (Z×I, p), I = {1, . . . , M } and let L * n be the maximum length of all paths in {0, 1, . . . , n} × I. Then, with C, σ as in Theorem 6.9,

n (t) := L * [nt] -Cnt σ √ λn , t ≥ 0, n ∈ N,
as a sequence of random elements of D[0, ∞) with the local uniform topology, converges in distribution to the process

Z M (t) := max 0=t0≤t1≤...≤t M =t M i=1 B (i) (t i ) -B (i) (t i-1 ) , (7.1)
where B (1) , . . . , B (M ) are independent standard Brownian motions.

Sketch of proof. If S (i) denotes the set of skeleton points of the restriction of -→ G (Z × I, p) on the line Z × {i}, we have that the S (i) are independent and all equal in distribution to the set of skeleton points of the Barak-Erdős graph -→ G (Z, p). Hence all the S (i) are stationary renewal processes on Z and also aperiodic (in the sense that the greatest common divisor of the positive integers in the support of the distance between successive skeleton points is 1). Therefore the set ∩ i∈I S (i) is also a renewal process with positive rate [START_REF] Lindvall | Lectures on the Coupling Method[END_REF] and the even smaller set i) : for all i, j ∈ I, i < j, there is an edge between (x, i) and (x, j) is still a renewal process as it is obtained by thinning. Moreover, S I is stationary and ergodic (with respect to θ) and has positive rate. Hence S I is an random subset of Z that is infinite in both directions. Using this and breaking n (t) as in (6.13), we arrive at the result by using Donsker's theorem. Details can be found in [START_REF] Denisov | Limit theorems for a random directed slab graph[END_REF].

S I = x ∈ i∈I S (

Generalization to partially ordered vertex sets and distance-dependent probabilities

In the above, we can take I to be a finite partially ordered set (I, ) with a bottom element called 1 and a top element called M . We then equip Z × I with a strict partial order defined by

(u, i) (v, j) if (u, i) = (v, j) and u ≤ v, i j.
A pair of vertices (u, i), (v, j), with (u, i) (v, j), form an edge directed from (u, i) to (v, j) with probability r v-u,i,j , independently from pair to pair. As before, we let L (u,i),(v,j) the maximum length of paths from (u, i) to (v, j). A convenient set of assumptions for the probabilities r n,i,j is:

∀i ∈ I r n,i,i =: p n , 0 < p 1 < 1, ∞ n=1 n n m=1 (1 -p m ) < ∞. (7.2)
Let as denote by -→ G (Z × I, (r n,i,j )) the resulting random graph on Z × I and let L * 0,n be the maximum length of all paths with endpoints in [0, n] × I.

Then Theorem 7.1 remains the same in form, that is, we normalize L * 0, [nt] in the same way and obtain that the normalized sequence of processes converge in distribution to a process akin to (7.1) but with an additional maximization since the presence of partial order allows for more flexibility.

To express the limiting process we need the Hasse diagram H(I) of the partially ordered set (I, ), which is the directed graph on I obtained by declaring there is an edge from i to j if i j and there is no k, distinct from i and j, such that i k j.

See [START_REF] Davey | Introduction to Lattices and Order[END_REF]. Let B (i) , i ∈ I, be independent standard Brownian motions. For any path ι = (ι 0 , . . . , ι r ) in H(I) we write

Z (ι) (t) := max 0=t0≤t1≤•••≤tr=t B (ι0) (t 1 ) + [B (ι1) (t 2 ) -B (ι1) (t 1 )] + • • • + [B (ιr) (t r ) -B (ιr) (t r-1 )] ,
and then let Z I (t) := max ι Z (ι) (t), (7.3) where the maximum is taken over all paths ι in H(I) from 0 to M . Then Z I is the limit of the sequence of normalized processes.

Convergence to the Tracy-Widom distribution

Self-similarity. It is clear that the process Z I of (7.3) is not Gaussian, but is is continuous and self-similar:

(Z I (ct)) t≥0 d = c 1/2 (Z I (t)) t≥0 ,
for any c > 0. In particular, the process Z M of (7.1) is a special case of (7.3), when I = {1, . . . , M }, has well-known connection with random matrix theory; see below.

Queueing theory. Glynn and Whitt [START_REF] Glynn | Departures from many queues in series[END_REF] Consider N × N as a directed graph where each vertex (i, j) has two outgoing edges, one to (i, j + 1) and one to (i + 1, j). Equip each (i, j) ∈ N × N with weight σ i,j . Let π be a path in this graph. Then w(π) is the sum of the weights of the vertices of this path. We obtain

L m,n = max{w(π) : π is path from (1, 1) to (m, n)}, (m, n) ∈ N × N.
Consider now the normalized departure times,

(n) m := L m,n -nEσ √ n var σ ,
where σ has the same law as (any of) the σ m,n . Then [START_REF] Glynn | Departures from many queues in series[END_REF] show that

(n) M → Z M (1), as n → ∞, in distribution,
where Z M is as in (7.1). For subsequent work on the symmetry, duality, and other quantities of interest, see [START_REF] Baccelli | Asymptotic results on infinite tandem queueing networks[END_REF].

The GUE. Let H be an M × M GUE (Gaussian Unitary Ensemble) random matrix [START_REF] Mehta | Random matrices[END_REF]. This is a random element of the set of complex Hermitian M × M matrices such that each diagonal element has standard complex Gaussian distribution and each off-diagonal element has standard real Gaussian distribution. (A standard complex Gaussian distribution is the law of Z = X + √ -1Y where X, Y are i.i.d. Gaussian random variables with EX = EY = 0, EX 2 = EY 2 = 1.) Moreover, all elements H k, , k ≤ , are independent (and H ,k = H k, for k ≤ ). The eigenvalues of H are real random variables and the largest of them is denoted by λ M . It is clear that H satisfies H d = U HU -1 for any unitary (U -1 = U * ) complex matrix U . It was shown by Baryshnikov [11],

thus answering an open question by Glynn and Whitt [START_REF] Glynn | Departures from many queues in series[END_REF], that Z M (1) satisfies (7.4) thus establishing a connection between Brownian last passage percolation and random matrix theory.

Z M (1) d = λ M ,
CLT for the largest GUE eigenvalue. The law of λ m (as well as the joint law of all eigenvalues of an m × m GUE random matrix) satisfies λ m / √ m → 2. The CLT for λ m is

m 1/6 (λ m -2 √ m) d -→ F 2 , ( 7.5)
where the distribution function F 2 a determinantal form:

F 2 (x) = det(I -A K ) L 2 [0,x] ,
where A K is the operator on L 2 [0, x] with kernel K defined

K(x, y) = Ai(x) Ai (y) -Ai (x) Ai(y) x -y ,
and where Ai(x) is the principal Airy function, defined as the solution y = Ai(x) to the linear ODE y -xy = 0 with boundary condtion y → 0 as x → ∞. Fourier-transforming the ODE, at least formally, easily yields that Ai(x) := π -1 ∞ 0 cos( 1 3 ω 3 + ωx)dω = π -1 lim Ω→∞ Ω 0 cos( 1 3 ω 3 + ωx)dω. Note that K(x, x) is defined as a limit when y → x. The determinant above is to be understood as the Fredholm determinant of the operator A K acting on L 2 [0, x]. This was established by Tracy and Widom [START_REF] Tracy | Fredholm determinants, differential equations and matrix models[END_REF] and the distribution F 2 is known as the Tracy-Widom law. See also Anderson, Guionnet and Zeitouni [START_REF] Anderson | An Introduction to Random Matrices[END_REF]. The determinant can be computed explicitly and a semi-explicit formula for F 2 can be found.

Barak-Erdős graph on N × N. Consider the graph -→ G (N × N, p), with 0 < p < 1. We equip N × N with the natural partial order; (i, j) is before (i , j ) if i ≤ i , j ≤ j and (i.j) = (i , j ). If (i, j) is before (i, j ) we put and edge between them with probability p, independently from pair to pair of comparable vertices. Paths in this graph move in a "northeast" direction (including the north and the east). We let L n,m be the maximum length of all paths from (1, 1) to (n, m). The induced subgraph of -→ G (N × N, p) on any horizontal line is a -→ G (N, p). Consider the m-th line and apply Theorem 6.9. We obtain

L [nt].m -Cnt σ √ λn t≥0 d -→ Z m , as n → ∞.
On the other hand, by self-similarity and (7.4), we have

Z m (t) d = √ tλ m ,
and

m 1/6 (λ m -2 √ m) d -→ F 2 .
It is then natural to if we can obtain a limit for a normalized L n,m when n and m tend to infinity simultaneously. To see what kind of scaling we can expect, write (7.5) as

m 1/6 Z m (t) √ t -2 √ m d -→ F 2 , as n → ∞. A statement of the form X(t, m) (d) ----→ m→∞ X,
t a/6 Z [t a ] (t) √ t -2 √ t a d ---→ t→∞ F 2 .
Therefore, it is reasonable to guess that an analogous limit theorem holds for a centered scaled version of the largest length L n,[n a ] , namely that

n a/6 L n,[n a ] -c 1 n c 2 √ n -2 √ n a d ---→ t→∞ F 2 , ( 7.6)
where c 1 , c 2 are appropriate constants. Indeed, (7.6) holds, with c 1 = C = C(p) and c 2 = λσ 2 . This was proved in [START_REF] Konstantopoulos | Convergence to the Tracy-Widom distribution for longest paths in a directed random graph[END_REF]. That paper used the idea of strong coupling with Brownian motions (Komlós-Major-Tusnády [67, 68, Theorem 4]), as in [START_REF] Bodineau | A universality property for last-passage percolation paths close to the axis[END_REF], a paper dealing with last passage percolation on N × N with random weights on the vertices. The difficulty in the proof of the main theorem in [START_REF] Konstantopoulos | Convergence to the Tracy-Widom distribution for longest paths in a directed random graph[END_REF] is that if we consider the intersection of the sets of skeleton points corresponding to each line then their intersection is empty.

We also refer the reader to the seminal paper of Johansson [START_REF] Johansson | Shape fluctuations and random matrices[END_REF] for last passage percolation on a lattice (with i.i.d. exponential weights on vertices).

Weighted Barak-Erdős graphs

We now sketch results on last passage percolation on the Barak-Erdős graph with random weights on its edges; we refer to [START_REF] Foss | Long-range last-passage percolation on the line[END_REF] and [START_REF] Foss | Limiting Properties of Random Graph Models with Vertex and Edge Weights[END_REF] for details. Recall that existence of an edge (i, j) is encoded by a random variable α i,j that takes value 1 with probability p or -∞ with probability 1 -p. Let u be a positive random variable with distribution function F (x) = P(u ≤ x), and let u i,j , i < j, be a collection of i.i.d. copies of u. If α i,j = 1 then edge (i, j) exists and has weight u i,j . We now have a weighted random graph that we will denote as -→ G (Z, p, u). A path from i to j of length and weight w is a sequence

(i = i 0 < i 1 < • • • < i -1 < i = j) such that α i0,i1 = • • • = α i -1 ,i = 1 and u i0,i1 + • • • + u i -1 ,i = w. A geodesic from i to j is a maximum weight path from i to j.
Different phenomena appear depending on whether Eu 2 is finite or not.

Finite variance weights

Assume that Eu 2 < ∞. We study

W i,j := max i=i0<i1<•••<i =j ∈N k=1 α i k-1 ,i k u i k-1 ,i k + ,
the maximum weight of all paths from i and j. If we further define the larger quantity W i,j :=

max i≤i0<i1<•••<i ≤j ∈N k=1 α i k-1 ,i k u i k-1 ,i k +
, the maximum weight of all paths with endpoints between i and j we obtain the subadditive inequality

W i,k ≤ W i,j + W j,k + max i≤x≤j≤y≤k u x,y .
We can then see that lim n→∞ W 0,n /n exists iff the expectation of the latter maximum is finite which requires that the second moment of u be finite. Hence Eu 2 < ∞ is necessary and sufficient for the above limit to exist.

To understand this, and to prepare the ground for the central limit theorem, we consider two random subsets of the integers. The first is the usual skeleton set S and the second is the set R c of c-renewal points where c is a positive constant. To define this, we first define the events

A + i = {W i,i+n > cn for all n ≥ 1}, A - i = {W i-n,i > cn for all n ≥ 1}, A -+ i = {α i-m,i+n u i-m,i+n < c(m + n) for all m, n ≥ 1}, and then let R c = {i ∈ Z : A + i ∩ A - i ∩ A -+ i occurs}.
Clearly, R c is a stationary and ergodic random set with density

µ(c, p) = P(A + 0 ∩ A - 0 ∩ A -+ 0 ). Since R c ⊂ S .
we We remark that the equality of the two limits is because of the existence of the c-renewal points that have positive density. The CLT holds provided that the third moment of u is finite:

Theorem 8.3. Assume that Eu 3 < ∞ and 0 < p ≤ 1.
Then the sequence of processes

W 0,[nt] -Cnt √ λn , t ≥ 0
converges in distribution, as n → ∞, to a zero mean Brownian motion.

Theorems 8.2 and 8.3 may be complemented by a result describing the behavior of the weight of the heaviest edge on a geodesic path. Assuming that F is continuous ensures that there is a unique geodesic path from 0 to n. Then we can define h n := maximum weight of all edges on the geodesic path from 0 to n.

We also assume that the edge weight u is regularly varying with index s, in the sense that

1 -F (tx) 1 -F (x) → t -s , as x → ∞, for every t > 0. (8.1)
Of course, s > 2 is needed in order that Eu 2 be finite. When 2 < s < 3, one can deduce that the fluctuations of W 0,n are of order larger than √ n, and so the central limit theorem cannot be extended to this case. Theorem 8.4. Let the edge weight u be a continuous random variable that is also regularly varying with index s > 2 in the sense of (8.1). Then we have

log h n log n → 1 s -1 in probability as n → ∞. (8.2)
In particular, if 2 < s < 3 then var W 0,n n → ∞, and a central limit theorem such as that in Theorem 8.3 cannot hold.

The proof of this can be found in [START_REF] Foss | Long-range last-passage percolation on the line[END_REF].

Infinite variance weights

Assume now that Eu 2 = ∞. Under this condition, W 0,n grows faster than linearly. This can be seen by considering the contribution of the single heaviest edge in [0, n], and noting that the expectation of the maximum of n 2 i.i.d. random variables with infinite variance has expectation that grows faster than n. Since W 0,n is at least as large as the weight of this single edge, we have that EW 0,n /n → ∞ as n → ∞, and from Kingman's subadditive ergodic theorem we can conclude that in fact W 0,n /n → ∞ a.s.

As before, we assume that u is a continuous random variable such that the regular variation condition (8.1) holds. We need s < 2 in order that Eu 2 be infinite.

New phenomena occur in the infinite variance case. In order to describe them succinctly and avoid technicalities, we shall further assume that p = 1. That is, we only present results for the -→ G (Z, 1, u) case.

Finite model

Let - → G n be a graph on V n = 0, 1 n , . . . , n-1 n , 1 , edges E n = {(i/n, j/n) : 0 ≤ i < j ≤ n}, and weights u (n)
e , e ∈ E n , that are i.i.d. copies of u. We can think of a path π of -→ G n as a collection of edges e 1 , . . . , e where the ending point of e i is the starting point of e i+1 for all 1 ≤ i < . Let Π n be the set of all paths in -→ G n from 0 to n (a set of size 2 n-1 ). The maximum weight of all paths in Π n can be written as

W 0,n = max π∈Πn e∈π u (n) e .
The latter maximum will not increase if we throw in all admissible subsets of the set of edges E n , where we say that a set A ⊂ E n is admissible if every pair of elements of A are non-overlapping edges in the sense that the endpoints of one are ≤ the endpoints of the other. If we let C n be the set of all admissible sets of edges then

W 0,n = max π∈Cn e∈A u (n) e . ( 8.3)
We next introduce another way to construct -→ G n . This second construction can be used to define a corresponding model on a continuous set of vertices with an appropriately defined maximum path weight W in such a way that a scaled version of W 0,n converges to W in distribution. Note that E n has size

N = N n = n + 1 n .
Let E n = {e 1 , . . . , e N } be an enumeration of the edges. Let M

(n) e1 , M (n) e2 , . . . , M (n)
e N be the order statistics of the u A charged graph is a graph with possibly negative weights on its edges. We are interested in last passage percolation on random directed charged graphs. The charge of a path is the sum of the charges of its edges. We are interested in the maximum charge of all paths. If all charges are negative then the maximum of negative quantities is the negative of a minimum of positive quantities, so the problem becomes that of first passage percolation, In view of this, we shall assume that some charges are nonnegative.

(n) e1 , u (n) e2 , . . . , u (n) e N That is, {M (n) e1 , M (n) e2 , . . . , M (n) e N } = {u (n) e1 , u (n) e2 , . . . , u (n) e N } (as sets) and M (n) e1 > M (n) e2 > • • • > M (n) e N . Let Y (n) 1 , Y (n) 2 , . . . , Y (n) N
For the models of this and the next section we assume that the support of the charge distribution is not a subset of (-∞, 0). It will then turn out that the last passage percolation constant is positive, so it matters little if we take positive part of the charge of a path before maximization.

The two-weights model

Let x be a real number, possibly negative (which can be thought of as a penalty). To each pair (i, j) of positive integers with i < j we assign weight or, rather, charge (since x is allowed to be negative)

w x i,j =
1, with probability p x, with probability 1 -p .

Let Π i,j be the set of strictly increasing finite sequences of integers, i 0 < i 1 < • • • < i such that i 0 = i and i = j. An element π ∈ Π i,j is a finite path in the complete directed graph on Z (that is, a graph such that every (i, j) with i < j is an edge directed from i to j). So Π i,j is a deterministic set of size 2 j-i -1. Define

w x (π) = k=1 w x i k-1 ,i k , if π = (i 0 , . . . , i ) ∈ Π i,j ,
and call w x (π) the charge or weight of π. We are interested in

W x i,j = max π=(i0,...,i )∈Πi,j k=1
w x i k-1 ,i k . (9.1)
We will use the notation -→ G (Z, p, x) to denote the directed charged random graph on Z that contains as edges all (i, j) ∈ Z × Z with i < j and which has with i.i.d. edge charges distributed as w x i,j . We study the asymptotic growth rate C(p, x) of W x i,j ; see (9.2) below. The Barak-Erdős graph is still denoted by -→ G (Z, p) and, as usual, C(p) is the maximal path growth rate. The parameter p is fixed throughout this section. We shall be interested in the behavior of the model when x varies.

We may extend the model by letting x range in R∪{-∞, +∞}. The case x = +∞ is uninteresting as being trivial. The case x = -∞ formally corresponds to the Barak-Erdős graph, the reason being as follows. The charge of i 0 , i 1 , . . . , i equals -∞ iff w x i k ,i k+1 = -∞ for some k, and this is equivalent to i

0 , i 1 , . . . , i not being a path in - → G (Z, p). Hence (W -∞ i,j ) + = L L,R i,j and - → G (Z, p, -∞) = - → G (Z, p).
An alternative way to think of -→ G (Z, p, x) is by letting all edges of -→ G (Z, p) be blue and all non-edges be red. Blue edges have charge 1; red edges have charge x. Theorem 9.1. For -∞ < x < ∞ we have

lim n→∞ W x 0,n n = lim n→∞ (W x 0,n ) + n = inf n∈N E(W x 0,n ) + n =: C(p, x), ( 9.2)
a.s. and in L 1 .

The constant C(p, x) is defined through this theorem. The theorem is proved by using ergodic arguments and Kingman's theorem, thanks to the superadditive inequality

W x i,k ≥ W x i,j + W x j,k , i < j < k.
Further properties of C(p, x) are in Theorem 9.2 below. We shall use the following notations. (iii) Convexity. C(p, x) is increasing convex over x ∈ R and strictly positive.

X C := {x ∈ R : C(p, •) is not differentiable at x} Q * := Q \ Z Y := {q ∈ Q * : q < 0} ∪ {0} ∪ { 1 2 , 1 3 , . . .} ∪ {2, 3
(iv) Asymptotic growth.

lim x→∞ C(p, x)/x = C(1 -p, 0) = ∞ n=1 p 1 2 n(n-1) -1 . (v) Nondifferentiability. X C = Y.
The proof of (v) is the most complex and shall only be sketched below. Property (i) follows from by comparing -→ G (Z, p, x) with -→ G (Z, 1 -p, 1/x). Property (iii) follows from the fact that W x i,j is an increasing convex function of x. Strict positivity is due to C(p, x) > C(p) > 0 for all x. The first part of Property (iv) is a consequence of continuity of the convex function and the scaling property (i). The last formula of (iv) is due to Dutta [START_REF] Dutta | On limit constants in last passage percolation in transitive tournaments[END_REF].

To deal with (v), we start by further elaborating on skeleton points.

Further structure of inter-skeleton pieces

As usual, [m, n] stands for the set of all integers k with m ≤ k ≤ n. That the set S of skeleton points of -→ G (Z, p) splits -→ G (Z, p, x) into independent parts is not a surprise; see Lemma 6.1. Hence, if (i 0 , . . . , i ) achieves the maximum in the right-hand side of the definition (9.1) for W x i,j , then {i 0 , . . . , i } contains all elements of S ∩ [i, j].

Enumerate the elements Γ k of S as in (6.2). Let -→ G (I, p) be the Barak-Erdős graph on the (possibly random) set of vertices I ⊂ Z.

Fix a positive integer n. Consider the event A + 0,n that there is a path in -→ G (Z, p) from 0 to every vertex in (1, n] and the event A - 0,n that there is a path from any vertex in [0, n -1) to n; see (6.4). In addition, let F 0,n := for all 0 < j < n there is 0 < i < n such that there is no path from min(i, j) to max(i, j) , and then set

H 0,n := A + 0,n ∩ A - 0,n ∩ F 0,n .
The following is an expression for the distribution of

- → G ([Γ 0 , Γ 1 ], p) conditional on {Γ 0 = 0}. Proposition 9.3. For any nonnegative deterministic functional ϕ - → G ([Γ 0 , Γ 1 ], p of - → G ([Γ 0 , Γ 1 ], p) we have E ϕ - → G ([Γ 0 , Γ 1 ], p Γ 0 = 0 = ∞ n=1 E ϕ - → G ([0, n], p ; H 0,n , (9.3)
In particular,

P(Γ 1 -Γ 0 = n|Γ 0 = 0) = P(Γ 2 -Γ 1 = n) = P(H 0,n ). (9.4) Furthermore, C(p, x) = λEW x Γ1,Γ2 = λ ∞ n=1 E(W x 0,n ; H 0,n ), (9.5)
where λ = λ(p) is as in (2.9).

For a proof see [START_REF] Foss | Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph[END_REF]. The intuition should be clear because, if, say, A + 0,n ∩ A - 0,n holds (in which case both 0 and n are in S ) but F 0,n fails, then there is an element of S strictly between 0 and n. The first equality of (9.5) is by standard renewal theory. The second follows from (9.3). Remark 9.4. From (9.4) we can obtain some values of the distribution of Γ 2 -Γ 1 :

P(Γ 2 -Γ 1 = n) =          p, if n = 1 0, if n = 2 p 4 (1 -p), if n = 3 p 7 (1 -p) 3 + 3p 5 (1 -p) 2 , if n = 4
The smallest value of Γ 2 -Γ 1 is 1. Suppose that Γ 2 -Γ 1 ≥ 2. Note that -→ G ([Γ 1 , Γ 2 ], p) must necessarily have the edges (Γ 1 , Γ 1 + 1) and (Γ 2 -1, Γ 2 ). If Γ 2 -Γ 1 were allowed to take value 2 then Γ 1 + 1 = Γ 2 -1 would have been a skeleton point strictly between Γ 1 and Γ 2 , which is impossible. This explains why P(Γ 2 -Γ 1 = 2) = 0.

Criticality and nondifferentiability

Let π = (i 0 , . . . , i ) be a finite strictly increasing sequence of integers. Let N (π) be the number of (i k-1 , i k ), k = 1, . . . , that are also edges of -→ G (Z, p). Thus, N (π) is the number of blue edges of π. Similarly, N (π) is the number of red edges. Then Definition 9.5 (the sets G n and H n ). Let G n be the set of all directed graphs on [0, n], that is, graphs whose edge directions compatible with the natural ordering of integers. Let H n ⊂ G n contain all G ∈ G n such that, for all 0 < j < n, (a) there is a path in G from 0 to n containing j;

w x (π) = k=1 w x i k-1 ,i k = N (π) + xN (π).
(b) for some i = j there is no path in G from min(i, j) to max(i, j)

For any path π in a graph G we let N G (π) be the number of edges of π that are also edges of G and we let N G (π) the number of edges of π that are not edges of G. Definition 9.6 (criticality). We say that x ∈ R is critical if there is a positive integer n and and a graph G ∈ H n possessing two paths π 1 , π 2 such that Criticality is a property of real numbers. We let

X crit = {x ∈ R : x is critical}.
Using Proposition 9.3 we can prove Lemma 9.8 (Corollary to Sturm's lemma [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]). Let N, n be positive integers, N ≥ n. Then there exists a unique finite sequence v = (v 1 , . . . , v N ) of elements of {0, 1} such that, for all 0 ≤ i < j ≤ N , the following hold:

i<k≤j v k ∈ (j -i) n N , (j -i) n N , i<k≤N v k = (N -i) n N , v 1 = 1.
We say that the sequence (v 1 , . . . , v N ) defined through this lemma is the (N, n)-balanced sequence. For example, with N = 7 n = 4 we find (v 1 , . . . , v 7 ) = (1, 1, 0, 1, 0, 1, 0) Next, given x < 0, x ∈ Q * , write Finally, 0 is connected by an edge to some vertices as show in the figure and some vertices are connected to n directly. For example, with x = -11/7 we have x = -2 + (3/7), that is, = 2, s = 3, t = 7, m = 31, n = 93. The (7, 4) balanced sequence is (v 1 , . . . , v 7 ) = (1, 1, 0, 1, 0, 1, 0). We also have a 0 = 31, a 1 -a 0 = + 1 + v 1 = 4, a 2 -a 1 = + 2 + v 2 = 5, a 3 -a 2 = 4, a 4 -a 3 = 5, a 5 -a 4 = 4, a 6 -a 5 = 5, a 7 -a 6 = 4. That this graph belongs to H n is not obvious, neither it is obvious that x ∈ X crit . The details are omitted.

X crit ⊂ Y

We will show that Y c ⊂ X c crit . Note that all irrationals are elements of Y c . First assume that x ∈ Y c is irrational. Since, by Proposition 9.7, X crit = X C , we show that x ∈ X c C . The set of points at which x → W x Γ1,Γ2 fails to be differentiable is included in the set of points x for which there are two paths π 1 , π 2 from Γ 1 to Γ 2 such that w x (π 1 ) = w x (π 2 ) with N (π 1 ) = N (π 2 ). This implies that (N (π 2 ) -N (π 1 ))x = N (π 1 ) -N (π 2 ), which means that x is rational. Hence W x Γ1,Γ2 is differentiable at rational points x and, by the dominated convergence theorem, the same is true for C(p.x). We thus proved that if x is irrational then x ∈ X c C . Next let x ∈ Y c but not irrational. Showing that x ∈ X c crit one proceeds by showing that for every n ≥ 3 and every G ∈ H n there is a unique (x, G)-maximal path or that every (x, G)-maximal path has the same N G (π) (=number of red edges).

If x = 1 then every edge and every non-edge of a graph G ∈ G n has charge 1. Hence the maximum length of all paths is n and this is achieved exactly one path, the path (0, 1, 2, . . . , n). So 1 ∈ X c crit . We know that negative rationals and the number 0 are critical. So assume that x > 0. We know that 1 is not critical. So assume that x ∈ (0, 1) ∪ (1, ∞). By the scaling property, we only need to consider x ∈ (0, 1). Since 1/2, 1/3, . . . are critical, we assume that x ∈ (0, 1) \ {1/2, 1/3, . . .}. Proposition 9.9. Every 0 < x < 1 that is not the reciprocal of an integer is not critical.

to approach this problem from an algorithmic view point, one that allows to draw conjectures by simulating the graph as accurately as possible.

As explained at the start of Section 9, we will assume that esssup w i,j > 0, else we are dealing with a first passage percolation problem. We will also assume, for convenience, that this essential supremum is finite so, without loss of generality, let esssup w i,j = inf{z : F ((z, ∞)) = 0} = 1.

(10.2) See Remark 10.8 below that explains that the finiteness of esssup w i,j is not a problem insofar as the perfect simulation is concerned. Comparing F with the distribution pδ 1/2 + (1 -p)δ -∞ with p = F ([1/2, 1]) we obtain that C(F ) > 0.

The goal of this section is the construction of a random variable whose expectation is C(F ) and such that this random variable can be perfectly simulated. A survey of perfect simulation can be found in [START_REF] Kendall | Notes on perfect simulation[END_REF]. Its relation to the so-called backwards-coupling was studied in [START_REF] Foss | Perfect simulation and backward coupling[END_REF]. It belongs to the broader area of coupling methods for stochastic recursions that may entirely lack the Markovian property [START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Comets | Processes with long memory: regenerative construction and perfect simulation[END_REF][START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF].

To do this we discuss an auxiliary Markovian particle system, called Max Growth System (MGS), that is an analog of the Infinite Bin Model. Our reference throughout this section is [START_REF] Konstantopoulos | Limit theorems for the maximal path weight in a directed grah on the line with random weights of edges[END_REF].

The Max Growth System (MGS)

The content of this subsection is purely deterministic. Consider point measures on the set R ∪ {-∞} that will be referred to as "space": N := {all locally finite point measures on R ∪ {-∞}}.

For example, ν = 2δ 1 + δ -1.5 + 3δ -4 + δ -∞ ∈ N . We think of ν as consisting of 7 particles, such that two of them are at 1, one at -1.5, three at -4 and one at -∞; so we can equivalently represent ν by the locations of its particles Composing these maps, for possibly different w each time, gives a trajectory in N . More precisely, the MGS starting at "time" T from state ν(T ) ∈ N and driving sequence w(t), t > T , is the sequence defined by ν(t) = Ψ w(t) ν(t -1), t > T, that is,

ν(t) = Ψ w(t) •Ψ w(t-1) • • • • •Ψ w(T +1) ν(T ).
Let N 0 consist of those ν ∈ N with ν 1 = 0. Define the map

σ : N → N 0 , σν = k≥1 δ ν k -ν1
that places the origin of space at ν 1 . We will need the following easily verified properties.

σΨ w = σΨ w σ, m(σν, w) = m(ν, w) -ν 1 .

We next consider an MGS ν(t), t ≥ 0, and show that under certain conditions on the driving sequence the quantity M(t) ≡ m(ν(t -1), w(t))

will eventually not depend on the choice of the initial state ν(0). Proof. We have ν 1 (0) = 0 ≥ -≥ ν 2 (0), by assumption. We will show by induction that, for all n ∈ N, if w(1), . . . , w(n) ≥ 1 -then

         M(n) = M(n) ν(n)| R+ = ν(n)| R+ ν(n)(R + ) = n + 1 ν n+2 (n) ≤ - (10.6)
Let n = 1 and assume that w(1) = w 1 (1) ≥ 1 -. We have M(1) = max{ν 1 (0) + w 1 (1), ν 2 (0) + w 2 (1), . . .} = w 1 (1) because ν 1 (0) + w 1 (1) = w 1 (1) ≥ 1 -and since 1 ≥ w j (1), -≥ ν j (0) for all j ≥ 2, we have w 1 (1) ≥ w j (1) + ν j (0) for all j ≥ 2 and so only the first term survives in the maximum. But then M(1) = w 1 (1) = M(1). Since ν(1) = ν(0) + δ M(1) we have that its restriction on R + equals δ 0 + δ w1(1) and ν 3 (1) = ν 2 (0) ≤ -. So (10.6) holds when n = 1.

Assume next (10.6) holds for some n. We show its veracity for n+1. Assume that w(1), . . . , w(n), w(n+ 1) ≥ 1 -. By (10.6) The reason that we dropped the second maximum is that max j≤n+1 {ν j (n -1) + w j (n)} ≥ max j≤n+1 w j (n) ≥ 1 -while max j>n+1 {ν j (n -1) + w j (n)} ≤ ν n+1 (n -1) + max j>n+1 w j (n) ≤ -+ 1. We also have ν(n + 1) = ν(n) + δ M(n+1) = ν(n) + δ M(n+1) so ν(n + 1)| R+ = ν(n + 1)| R+ and they have n + 2 particles on R + , while ν n+3 (n + 1) = ν n+2 (n) ≤ -. Remark 10.5. Let us make the reasonable ansatz that the quantity inside the last expectation converges in distribution to some random variable: m(σν(n -1), w(n)) + d -→ m+ as n → ∞. (10.11) Then a poor man's estimate of C(F ) would be to simply to compute sample means n -1 n j=1 Em(σν(j-1), w(j)) + for large n. But the sample means are not from i.i.d. copies of the limiting variable and thus the sampling is "not perfect". To achieve perfect sampling, we must first show that the non-Markovian process m(σν(n -1), w(n)), n = 1, 2, . . ., has a stationary version (we say that a process has a stationary version if it is eventually equal to a stationary process; the "eventually" means that there is a finite random time after which the two processes are equal a.s.) from which we can sample i.i.d. copies constructively.

Theorem 10.6. Suppose that F satisfies (10.2). Let ν be an MGS(Q F ) with driving sequence w(t), t ∈ Z, starting from an arbitrary state at an arbitrary, possibly random, time. Then there exists a stationary process ( m(t), t ∈ Z) such that m(σν(t -1), w(t)) = m(t) for t large enough, a.s.

In particular E( m(0) + ) = C(F ).

Proof. Let ∈ [0, 1) be such that p := F ([1 -, 1]) > 0, which is possible due to (10.2). For k ∈ Z, consider the event

R k := {w 1 (k) ≥ } ∩ ∞ j=1
max(w 1 (k + j), . . . , w j (k + j)) ≥ 1 -.

It is clear from its definition that (R k , k ∈ Z) is a stationary sequence of events with

P(R k ) = P(R 0 ) = F ([ , 1]) ∞ j=1 (1 -(1 -p) j ) > 0.
Consider the stationary random set J := {k ∈ Z : R k holds}. Since P(R k ) > 0, we have, by ergodicity (more specifically by the Poincaré recurrence theorem), inf J = -∞ and sup J = ∞ a.s. We enumerate the elements of J by

• • • < T -1 < T 0 ≤ 0 < T 1 < T 2 < • • •
Hence the R Ti are all events of probability 1. We define ν(t), t ∈ R, by letting, for all j, ν(T j ) = δ 0 , ν(t) = σ i∈Z

1 {Ti<t<Ti+1} Ψ t w(t) • • • • •Ψ Ti+1 w(Ti+1) δ 0 , t = T j .
On the other hand, thanks to Lemma 10.1, the process m(σν(t -1), w(t)), t > T i , is algebraically independent of ν(T i ). This shows, see [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF], that the stationary process m defined by m(t) = m(σν(t -1), w(t)), t ∈ Z, satisfies m(t) = m(σν(t -1), w(t)) for all t large enough, a.s. Next, using that

C(F ) = lim n→∞ E(M n ) n = lim n→∞ 1 n n j=1
E(m(σν(j -1), w(j)) + ) a.s., and using the eventual equality between m(σν(t -1), w(t)) and m(t), we have the construction of an array of i.i.d. random variables with common distribution F until the random variable T * can be constructed. To construct T * as well as m(0) from the sequence {w j (t), j ∈ N, t ∈ Z}, one only needs to consider a.s. finitely many elements of this set, as {T * = t} is a measurable function of {w 1 (t)} ∪ {w j (t + k), 1 ≤ j ≤ k ≤ |t|} and m(0) is a measurable function of {w 1 (T * )} ∪ {w j (T * + k), 1 ≤ j ≤ k ≤ |T * |}.

C(F ) = lim
Therefore, we can explore triangular arrays of the form {w 1 (t)} ∪ {w j (t + k), 1 ≤ j ≤ k ≤ |t|}, progressively decreasing t until time T * is detected. Once this random variable is known, we construct the random variable m(0) using the procedure described in Theorem 10.6 from the previously discovered random variables. A possible implementation is described in Algorithm 1. We show a graphical representation of a run of Algorithm 1 in Figure 9. We observe that this algorithm has a complexity of (T * ) 2 , as it is the number of steps needed to generate the variable m(0). It is worth noting that -T * can be constructed as the first hitting time of 0 of the Markov chain (X n ) with initial state X 0 = min{j ≥ 1, w j (0) ≥ 1 -} and with transition probabilities defined for all j ≥ 2 and i ≥ j by P (j, j -1) = 1 -(1 -p) j-1 and P (j, i) = p(1 -p) i-1

where p = P(w 1 (0) ≥ 1 -), with P (1, 0) = P(w 1 (0) ≥ ), P(1, 1) = P(1 -≤ w 1 (0) < ), P (1, j) = p(1 -p) j-1 for j ≥ 2.

The quantity X n corresponds to the value of the variable J at the end of the period when t = -n in Algorithm 1. In the example shown in Figure 9, we have (X 0 , X -1 , X -2 , X -3 , X -4 , X -5 , X -6 ) = (4, 3, 2, 1, 2, 1, 0). Note that T * has exponential tails.

The choice of the parameter may have an important effect on the behavior of the average complexity E((T * ) 2 ) of the algorithm. We plotted → E((T * ) 2 ) in Figure 10, when the charge

Corollary 2 . 8 .

 28 Consider the four quantities defined by (2.1) for a Barak-Erdős graph -→ G (Z, p). Then there is a constant C = C(p) such that

Figure 1 :

 1 Figure 1: Plot of the rate λ(p) of skeleton points against the connectivity probability p

Figure 3 :

 3 Figure 3: This figure describes the projected Markov chain, with k = 2 on the left picture, and k = 3 on the right one.The integers over the directed edges represent the values of ξ corresponding to the transitions. For example, if µ is the law of ξ, the transition probability for state[START_REF] Addario-Berry | Poisson-Dirichlet branching random walks[END_REF] to state[START_REF] Addario-Berry | Minima in branching random walks[END_REF] on right equals µ(2) + µ[START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF]. The thick arrows represent transitions that move the front by one unit. Note that if ξ ∈ {0, ∞}, the projected Markov chain remains at the same state, moving the front by 1 if and only if ξ = 0.

Theorem 3 . 23 .

 323 Let µ be a probability distribution on N such that k∈N kµ(k) < ∞ and sup k∈N µ(k) < 1.

Lemma 3 . 30 .

 330 If α ∈ C 1 and ξ ∈ N then either ξα ∈ G or ξα ∈ B. In particular, every triangular word is either good or bad. Proof. Since α is in C 1 , the front of αX contains exactly the same number of balls as the front of αY for any configuration Y ; see Definition 3.15 infra. Let b be this number of balls. Then F (ξαX) = F (αX) + 1 if and only if ξ ≤ b. Since neither ξ nor b depend on X, it follows that the word is good if ξ ≤ b, or bad otherwise. By Lemma 3.19 every triangular word is in C 1 . Hence the previous argument applies.

Theorem 4 . 5 .

 45 The function p → C(p) is analytic on ∈ (0, 1].

Figure 4 :

 4 Figure 4: Successive bounds on the function C (in red) by C k (in orange) and C k (in blue).Observe that if these bounds appear very sharp for p close to 1, the approximation (in particular the upper bound) remains quite crude for p close to 0.

  and recall that P(T * T > -∞) = 1 (as in the proof of Theorem 3.35) and that P(T * T ≥ T 0 ) = 1. For brevity, set T = T * T . Arguing as in (3.21) we have

Lemma 4 . 7 .

 47 For every α ∈ G min , we have |α| ≤ H(α) + 1.

Remark 4 . 10 . 2 -1 2 ≈

 41022 Note that the radius of convergence of √ 0.207 obtained in Theorem 4.8 is far from optimal, being obtained by the crude bound |G min ∩ U h | ≤ |U h |. Based on the numerical computation of the first few terms of an+1 an and a 1/n

Definition 5 . 6 (

 56 Vertex ranking). Fix i ∈ N and let a, b be distinct elements of {0, 1, . . . , i -1}. We say that κ a κ b (or κ b κ a ), if either L κa > L κ b or L κa = L κ b and a > b.

Figure 5 :

 5 Figure5: The first 9 vertices of C are shown, together with the edges between them. Vertices of G not connected to 1 via a path are not shown. The number above each vertex κj is the maximal path length Lκ i . The number below each vertex is its rank. The thick edges are the edges of the special spanning tree B. To explain this, consider, e.g., vertex κ6 and observe that is connected to κ4 with Lκ 4 = 2 and to κ3 with Lκ 3 = 1; so we choose κ4 as the parent of κ6 in B5. Consider vertex κ8. It is connected to vertices κ2 and κ1 with Lκ 2 = Lκ 1 = 2. Since κ2 has lower rank than κ1 we declare that κ2 is the parent of κ8 in B. Finally, the quantities on the lower line are proportional to the probability that κ9 chooses its parent among the existing vertices.

41 Figure 6 :

 416 Figure6: A possible evolution of the PWIT with the vertices of K embedded correctly. The little triangle at the end of blue particles symbolize the blue descendants produced by each blue particle, which play no role in the coupling, hence do not interact with Φ or the times at which the red particles appear. However, the blue particles represented here play a role, as they influence the label given to each of the red particle.

2 .

 2 If there exists m ∈ N such that lim n→∞ p n n 1+1/m = ∞ and lim n→∞ p n n 1+1/(m+1) = 0, then L n (p n ) → m in probability.

  Let Γ I k , k ∈ Z, be an enumeration of the elements of S I with Γ I k < Γ I k+1 for all k ∈ Z, and Γ I 0 ≤ 0 < Γ I 1 . Then, as in the Barak-Erdős case (see Lemma 6.1) is we let-→ G k be the induced subgraph of -→ G (Z × I, p) on {(u, i) ∈ Z × I : Γ I k ≤ u ≤ Γ k+1 }, we have that, conditional on {0 ∈ S I }, the -→ G k , k ∈ Z, are i.i.d.Therefore, a maximal-length path on {0, . . . , n} × I is necessarily a path from (0, 1) to (n, M ) such that if 0 ≤ Γ I k ≤ n then such a path passes via a vertex whose horizontal coordinate is Γ I k ; see Figure7.

Figure 7 :

 7 Figure 7: A maximal length path on [0, n] × I passes through all intermediate skeleton points and switches line at some of them.

  be a random ordering of {e 1 , . . . , e N } chosen uniformly from all the N ! possibilities. Assign weight M C n = A ⊂ {e 1 , . . . , e N } : for every pair {e i , e j } ⊂ A the Y(n) ei , Y (n) is equivalent (the same in distribution) to the previous definition of W 0,n in (8.3).

  Scaling. C(p, x) = xC(1 -p, x), for all x > 0. (ii) Continuity at -∞. lim x→-∞ C(p, x) = C(p).

Γ 1 ,Γ 2 NΓ 1 ,Γ 2 N

 1212 := {π ∈ Π i,j : w x (π) = W x i,j }, a random set of paths with maximal charge. Let D + denote right derivative with respect to x; similarly D -for left derivative. Using (9.5) and the dominated convergence theorem we obtainD + C(p, x) = λED + W x Γ1,Γ2 = λE max π∈Π x (π), D -C(p, x) = λED -W x Γ1,Γ2 = λE min π∈Π x (π).

  (a) N G (π 1 ) + xN G (π 1 ) = N G (π 2 ) + xN G (π 2 ) = max π∈Π0,n (N G (π) + xN G (π)) (b) N G (π 1 ) = N G (π 2 ).

  , s, t are positive integers, t > 1, gcd(s, t) = 1, s < t, and let (v 1 , . . . , v t ) be the (t, t -s)-balanced sequence. Construct a graph G on [0, n = 3m] where m := t( + 3) -(s + 1), by letting the first and last parts consist of edges joining consecutive integers and making the middle part as shown in the figure. The vetices a 0 , . . . , a t are defined by a 0 := m, a 1 := a 0 + ( + 1) + v 1 , a j := a j-1 + ( + 2) + v j , j = 2, . . . , t.

( 1 , 1 ,

 11 -1.5, -4, -4, -4, -∞) arranged in decreasing order. In general, we let ν 1 ≥ ν 2 ≥ • • • be the locations of the particles of ν. So the function N ν → ν k := location of kth largest particle of ν is well-defined for each k and ν = k≥1 δ ν k .We also letν := ν(R ∪ {-∞}), inf ν := ν ν , with inf ν = -∞ if ν = ∞. Next let W := w = (w 1 , w 2 , . . .) : sup k≥1 w k ≤ 1, w k ∈ R ∪ {-∞} for all k ,and define m(ν, w) := supk≥1 (ν k + w k ), ν = 0, w ∈ W.The map responsible for the dynamics of the MGS is defined by Ψ w ν := ν + δ m(ν,w) .

  we have ν(n)| R+ = ν(n)| R+ (containing n + 1 particles on R + ) and ν n+1 (n -1) ≤ -. So M(n + 1) = max j≥1 {ν j (n) + w j (n + 1)} = max j≤n+1 {ν j (n) + w j (n + 1)} ∨ max j>n+1 {ν j (n) + w j (n + 1)} = max j≤n+1 {ν j (n) + w j (n + 1)} ∨ max j>n+1 {ν j (n) + w j (n + 1)} = max j≤n+1{ν j (n) + w j (n + 1)} = M(n + 1).

E

  ( m(j) + ) = E( m(0) + ), by stationarity and ergodicity of the sequence.

Figure 9 :

 9 Figure 9: Illustration of the execution of Algorithm 1 on an example, in the case where < 1 -. The variables sampled until the Boolean variable Stopping becomes True are pictured by black/white squares and disks. One searches for the first time T * such that every line of index T * + 1 ≤ t ≤ 0 has at least one black disk between columns 1 and t -T * and such that there is a black square in position (T * , 1). The full triangular array of variables used in the construction of ν is enclosed by a red boundary.

Table 1 :

 1 Average distance between two successive skeleton points in the infinite Barak-Erdős graph with parameter p.

	p	0.01	0.1	0.3	0.5	0.6 0.8	0.9
	1/λ 10

139

6 × 10 11 558.46 11.99 4.9 1.

73 1.26

  Fix the set V ⊂ G ∪ B and let T = T * V for brevity. Let (Y n ) be the stationary version of the pinned IBM constructed from (ξ n ) n∈Z . From Corollary 3.27 we have v µ

.

[START_REF] Borovkov | Ergodicity and stability theorems for a class of stochastic equations and their applications[END_REF]

Proof.

  .5) Precise bounds. We use Theorem 3.35 to obtain precise bounds on C(p). Let k ≥ 1 and let 0 < p ≤ 1. Recalling the notation ξ j k = ξ1 ξ≤k + j1 ξ>k from Section 3.2, and assuming that ξ has geometric law µ p , we let µ j p,k be the law of ξ j k . Recall that IBM(µ ∞ p,k ) bounds IBM(µ) from below, and that IBM(µ k p,k ) bounds IBM(µ) from above, in the sense of (3.7). Denote by C k (p), C k (p), the speeds of the IBM(µ ∞

	p,k ), IBM(µ k p,k ),
	respectively. We then have
	∀p

Table 2 :

 2 The values of an for 0 ≤ n ≤ 12.

	n 0 1 2 3 4 5	6	7	8	9	10	11	12
	a n 1 1 1 3 7 15 29 54 102 197 375 687 1226
	5

Longest path of the Barak-Erdős graph in the sparse regime

  of G not connected to 1 via a path are not shown. The number above each vertex κj is the maximal path length Lκ i . The number below each vertex is its rank. The thick edges are the edges of the special spanning tree B. To explain this, consider, e.g., vertex κ6 and observe that is connected to κ4 with Lκ 4 = 2 and to κ3 with Lκ 3 = 1; so we choose κ4 as the parent of κ6 in B5. Consider vertex κ8. It is connected to vertices κ2 and κ1 with Lκ 2 = Lκ 1 = 2. Since κ2 has lower rank than κ1 we declare that κ2 is the parent of κ8 in B. Finally, the quantities on the lower line are proportional to the probability that κ9 chooses its parent among the existing vertices.

  1, 2, . . . Proof. If τ 1 , τ 2 , . . . are i.i.d. exponential random variables with rate λ and if ν is an independent geometric random variable with parameter α (i.e., P(ν

  considered an infinite number single-server FCFS infinite-buffer queues connected in series. At time 0 there are M customers in the first one and none in the others. Denote by σ m,n the service time of customer m in queue n. It is assumed that the σ m,n , are i.i.d. random variables with finite variance. One quantity of interest in queueing theory is the time L m,n that customer m departs from queue n. For this, we have an obvious recursion, namely,L m,n = max(L m-1,n , L m,n-1 ) + σ m,n ,because if customer m finds, upon arrival, queue n occupied, it has to wait until the previous customer departs from queue n at time L m,n-1 , so L m,n = L m,n-1 + σ m,n ; and if it finds the queue empty then L m,n = L m,n-1 + σ m,n . We can easily solve the recursion and express it as follows.

  have µ(c, p) ≤ λ(p), where λ(p) is the density of S ; see (2.9) and Remark 2.9. For the last assertion see[START_REF] Foss | Limiting Properties of Random Graph Models with Vertex and Edge Weights[END_REF] Lemma 3]. This lemma is responsible for the law of large numbers: Assume that Eu 2 < ∞ and 0 < p ≤ 1. Then there is a constant C depending on p and the law of u such that

	Lemma 8.1. Assume that Eu 2 < ∞ and 0 < c < (Eu)(EW Γ1,Γ2 ). Then µ(c, p) > 0. Moreover, -→ G (Z, p, u) regenerates over R c .
	Sketch of proof. We first observe that P(A + 0 ) = P(A -0 ). If we choose 0 < c < (Eu)(EW Γ1,Γ2 ) then P(A + 0 ) > 0. The finiteness of Eu 2 implies the positivity of P(A -+ 0 ). It can be shown that A + 0 , A -0 , A -+ 0 are independent and so µ(c, p) = P(A + 0 )P(A -0 )P(A -+ 0 ) > 0. For details see [42,
	Lemma 2 supra]. Theorem 8.2. lim n→∞	W 0,n n	= lim

n→∞ W 0,n n = C a.s. and in L 1 .

  Lemma 10.1 (Decoupling property). Fix ∈ [0, 1). Consider two MGSs, ν, ν, starting at time 0 with ν(0) ∈ N 0 and ν(0) = δ 0 . Assume that the driving sequence w(t), t > 0, is the same for both. Ifν 2 (0) ≤ -,(10.3) w(t) := max{w 1 (t), . . . , w t (t)} ≥ 1 -for all 1 ≤ t ≤ n,(10.4)

Let M(t) = m(ν(t -1), w(t)), M(t) = m(ν(t -1), w(t)). then M(t) = M(t) for all 1 ≤ t ≤ n. (

10.5)

Note that θ is a bijection from Ω onto itself with both θ and θ -1 measurable when Ω is given its natural product σ-algebra. Let θ 0 be the identity. Then θ n , n ∈ Z, is a group. We say that (θ, P) is stationary if P(θA) = P(A) for all measurable A. In this case, we say that it is ergodic if every set A such that θA = A a.s., actually has P(A) equal to 0 or 1.

This last assumption may be relaxed, allowing empty bins to the left of the front, in which case the proofs become more technical, with some absorbing states being created. However, the main results stated in this section still hold true under quite general conditions.

Observe that the restriction made in this section remains tame, as a selection number of 0 moves the whole configuration to the right by 1 while a selection number of ∞ leaves the configuration unchanged. A generic IBM(ν) X can thus be coupled with an IBM(µ) Y , where µ(•) = ν(•|N), in such a way that the configuration Xn is obtained as a random shift of Y Zn , where (Zn) is a random walk independent of Y . SeeLemma 3.4.

The word "generation" may be confusing, especially in the immortal particles process interpretation of the PWIT. To avoid confusion, simply interpret the phrase "generation of particle u" as |u|.

We say that a random sequence X i , i ∈ Z, is 1-dependent if, for each i ∈ Z, the sequences (X j , j < i) and (X j , j > i) are independent.

Consider now the random sequence α (0) := (α (0) 1 , α (0) 2 , . . .), consisting of independent entries with P(α (0) j = 1) = 1 -P(α (0) j = -∞) = p j , j ∈ N, and let α (n) , n ∈ Z, be i.i.d. copies of α (0) . Then we can construct -→ G (Z, (p j )) as the graph on Z with edge set {(i, j) ∈ Z × Z : i < j, α (i)

(Note that the random variable α (i) j-i was denoted by α i,j in (2.2).) We refer to the random object

as the kth "cycle", k ∈ Z. Let -→ G k be the induced subgraph of -→ G (Z, (p j )) on the set of vertices {v ∈ Z : Γ k ≤ v ≤ Γ k+1 }, that is, keep only those edges with endpoints in this set. The following was proved in [START_REF] Denisov | Limit theorems for a random directed slab graph[END_REF]. Lemma 6.1. Assume that (2.7) holds. Then, conditional on {0 ∈ S }, the cycles C k , k ∈ Z, are i.i.d. and the random graphs

Sketch of proof. It suffices to show that C 0 is independent of (C -1 , C -2 , . . .) conditional on 0 ∈ S . Let F + := σ(α (n) , n > 0), F -:= σ(α (n) , n < 0). As in the proof of Lemma 2.6, for each j ∈ Z, consider the largest of the vertices u < j such that (u, j) is an edge, letting (j) = j -u be its distance from j. Similarly, consider the smallest of the vertices v > j such that (j, v) is an edge, setting r(j) = v -j. Note that Whereas Γ -1 is not F --measurable, the random variable Γ -1 is. Also, Γ 1 is F + measurable. Similarly, each cycle C k with negative index k becomes equal to an F --measurable random object. This argument shows that C 0 is independent of (C -1 , C -2 , . . .), conditional on {Γ 0 = 0}. That all the C k , k ∈ Z, are identically distributed, under the same conditioning, follows from stationarity.

For the last claim observe that

Remark 6.2. Let α denote the map n → α (n) . For all k ∈ Z, denote by θ k α the map n → α (n+k) . Note that the probability measure P relates to P(•|0 ∈ S ) as follows. Let Φ(α) be a measurable bounded function of α. Denote by

For a simple proof of this, see [START_REF] Konstantopoulos | A discrete-time proof of Neveu's exchange formula[END_REF]. This implies that (without conditioning on 0 ∈ S ), the cycles C k , k ∈ Z \ {0}, are i.i.d. each with the same distribution as the conditional distribution of C 0 given 0 ∈ S . Moreover, C 0 is independent of the rest of the cycles, and its law can be found by the last formula. In particular,

1 |Γ 0 = 0) may be equal to ∞ unless a condition stronger that (2.7) is assumed.

Moments of skeleton points and a central limit theorem

We show that not only skeleton points exist but that they can also be constructed recursively and causally. This will be done by means of iterates of the the stopping times µ and ν. We define two interlaced sequences of stopping times

and, recursively, for k ≥ 2,

In fact, since µ is a defective random variable, with P(µ = ∞) = √ λ, it follow that the recursion terminates in finitely many steps. Let

Using the observation that ν[k] and µ[k] are stopping times with respect to the filtration (F - n ) n≥0 , where

where κ, ν Proof. From Lemma 6.5, we have that κ i=1 ν i has an exponential (respectively, p-th) moment if and only if (0) has an exponential (respectively, p-th) moment. From Corollary 6.5, we have that κ-1 i=1 µ i has an exponential (respectively, p-th) moment if and only if (0) has an exponential (respectively, (p + 1)-th) moment.

Proof. By the definition of ν and µ we easily see that

Hence, conditional on 0 being a skeleton point (Γ 0 = 0), we have that ν[K] is the next skeleton point:

We now use Lemma 6.7 and Remark 6.6 to conclude.

Infinite model

We next define a random weighted graph -→ G on countably infinite random set of vertices. Let W 1 , W 2 , . . . be a sequence of i.i.d. exponential random variables with mean 1 each. Set

. . be two sequences of i.i.d. uniform random variables in [0, 1]. We further assume that {U i }, {V i }, {W i } are independent. The edges of -→ G are taken to be

The i-th largest weight M i will be attached to the i-th edge Y i . In analogy to (8.4) we define

In analogy to to (8.5) we let

A priori the random variable W could be infinite, but Theorem 8.5 below guarantees that it is almost surely finite.

Convergence results

The intuition behind the approximation of the finite model by the infinite one is the following pair of convergence results. First, for any k ∈ N we have

as n → ∞, where we use the product topology on ([0, 1] 2 ) k .

Following [START_REF] Martin | Last-passage percolation with general weight distribution[END_REF][START_REF] Hambly | Heavy tails in last-passage percolation[END_REF], let b n = a Nn = F (-1) 1 -1

Nn

and put

(As an example, if F (x) = 1 -x -s for x ≥ 1, then b n grows like n 2/s . More generally, under assumption (8.1), lim n→∞ log bn log n = 2/s). Then from classical results in extreme value theory we have for any k ∈ N that

In this way both the locations and weights of the heaviest edges (i.e. edges with heaviest weights) in the discrete model above are approximated by their equivalents in the continuous model. It is shown in [START_REF] Foss | Long-range last-passage percolation on the line[END_REF] the heaviest edges, dominant contribution to the maximum weight. The precise convergence result is as follows.

Theorem 8.5. The random variable W in (8.6) is almost surely finite. If (8.1) holds with s ∈ (0, 2), then

For n large, the heaviest edge in the geodesic has length on the order of n. This is in contrast to the behavior in the case Eu 2 < ∞, where the important contribution to the maximal weight is given by edges of a lighter order, see e.g. Theorem 8.3 above.

Analytic properties of charged graphs

We now turn to some results concerning the behavior of the last passage percolation constant C of the Barak-Erdős graph as a function of edge weights. The problem is, in general, hard, so we consider here the simple model introduced in [START_REF] Foss | Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph[END_REF]. The next section will deal with a more general model. Theorem 9.7.

In view of this, Theorem 9.2(v) is equivalent to

which is a deterministic problem of graph-theoretic/combinatorial nature. Proving this is rather complicated. We shall sketch some aspects of it below.

Y ⊂ X crit

Let x ∈ R, G ∈ G n and π ∈ Π 0,n . Think of the common edges of π and G as blue and the remaining edges of π as red. There are N G (π) blue and

Showing that x ∈ X crit one proceeds by constructing a G ∈ H n possessing at least two (x, G)maximal paths with different number of red edges. Figure 8 summarizes how this is done for each element x of Y, except x = 2, 3, . . ., since if we know that 1/k ∈ X crit (k = 2, 3, . . .) then we also know that k ∈ X crit by the scaling property. For example, Figure 8(a) shows that 0 ∈ X crit . Indeed, consider the paths π 1 = (0, 1, 3) and π 2 = (0, 1, 2, 3). They both have weight 2 (which is maximal), however, the first has no red edges but the second has one red edge. This means that 0 satisfies the definition of criticality.

Each red edge (i.e. each non-edge) has charge 0. This graph shows that 0 ∈ X crit . The most complex case is that of the last line of Figure 8. We explain the construction of the graph.

We first need the following number-theoretic lemma that can be thought of as placing n balls in N bins "as uniformly as possible". Let x , x be the upper, lower, respectively, parts of x.

The proof of this is rather lengthy and relies on special properties of maximal paths that can be found in Lemmas 4.5, 4.6, 4.7, 4.8, 4.9 and 4.10 of [START_REF] Foss | Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph[END_REF].

To state them, we adopt some terminology. Call an edge short if its endpoints are successive integers; otherwise, call it long. Say that edge e = (i, j) is nested in e = (i , j ) if i ≤ i < j ≤ j and e = e . Let π, π ∈ Π 0,n . We say that the interval [i, j] ⊂ [0, n] is (π, π )-special if the set of vertices k ∈ [i, j] that belong to both π and π consists of i and j only. Lemma 9.10. If 0 < x < 2 then every maximal path contains all short blue edges. Lemma 9.11. If 0 < x < 2 then every long edge of a maximal path π is blue ( in other words, every red edge of π must be short). Lemma 9.12. If x > 0 then no blue edge of a maximal path can be nested in a different blue edge of another maximal path. Lemma 9.13. Let 0 < x < 2. Then for every pair π, π ∈ Π 0,n of maximal paths such that

The proof of the lemmas are omitted, but we give the proof of Proposition 9.9:

Proof of Proposition 9.9. We prove the contrapositive: if 0 < x < 1 is critical then x = 1/m for some integer m. So suppose that x is critical and 0 < x < 1. Then there is n ≥ 3 and G ∈ H n (edges of G are called blue and non-edges red) and two maximal paths π 1 , π 2 with different number of red edges:

. By the Lemma 9.13, there is a (π

and hence the reciprocal of a positive integer.

Remark 9.14. We considered here differentiability properties for a last passage percolation problem. Differentiability properties of a first passage percolation model were studied in [START_REF] Steele | Nondifferentiability of the time constants of first-passage percolation[END_REF].

Perfect simulation aspects of charged graphs

We now turn our attention to charged graphs with edge charge distribution F : to every pair of (i, j) of integers, with i < j, assign a charge w i,j with distribution F , independently. For a path π = (i 0 , . . . , i ), that is, a finite increasing sequence of integers, assign charge w(π) = w i0,i1 In Section 9 we studied C(p, x) ≡ C(pδ 1 + (1 -p)δ x ) as a function of x. To deal with C(F ) as a function of F analytically is beyond the scope of this survey. We will, however, explain how Remark 10.2. Lemma 10.1 and the conclusion (10.5) can easily be modified if we need to start the MGS from an arbitrary time T rather than T = 0. The quantity that replaces w(t) will be w(T ; t) := max{w 1 (T + t), . . . , w t (T + t)}. (10.7) This is needed in Theorem 10.6 below.

Remark 10.3. The decoupling property is essentially responsible for producing, in a stochastic version of the MGS, the so-called renovating events that constitute a nice way for exhibiting stability.

The original theory can be found in [START_REF] Borovkov | Ergodicity and stability theorems for a class of stochastic equations and their applications[END_REF][START_REF] Borovkov | Asymptotic Methods in Queueing Theory[END_REF][START_REF] Borovkov | Ergodicity and Stability of Stochastic Processes[END_REF][START_REF] Borovkov | Stochastically recursive sequences and their generalizations[END_REF][START_REF] Borovkov | Two ergodicity criteria for stochastically recursive sequences[END_REF] and its extension for functional of stochastic dynamical systems in [START_REF] Foss | Limiting Properties of Random Graph Models with Vertex and Edge Weights[END_REF].

The MGS of a random charged graph, coupling and stationarity

Definition 10.4. Given a probability measure Q on W define the random process MGS(Q) by ν(t) = Ψ w(t) ν(t -1), t ≥ 1, with w(1), w(2), . . . being independent with common law Q, with ν(0) ∈ N arbitrary. Clearly, MGS(Q) is Markovian. In the particular case where the components of w( 1) are i.i.d. with common distribution F we shall be using the notation MGS(Q F ).

Let -→ G (Z, F ) be a random charged graph with charge distribution F satisfying (10.2). Let

in the notation of (10.1). In particular,

where π is a permutation on {0, . . . , n -1} that puts W 0 , . . . , W n-1 in decreasing order.

) and so if we consider the MGS(Q F ) defined by

starting with ν(0) = δ 0 , we see that

not only component-wise, but also as processes.

Therefore, letting

which implies that M n /n is a sample mean:

where the last equality in distribution is at the level of sequences. Since

and since

Em(σν(j -1), w(j)) + .

Perfect simulation

Recall the quantity w defined by (10.7).

Theorem 10.7 (Perfect simulation). Define

Then |T * | < ∞ a.s., and

Proof. We recall that (T -j , j ∈ N) are the negative elements of the random set J, with T -1 > -∞.

We remark that

does not algebraically depend on the value of ν ∈ N 0 . As a result, it is equal to m(0). Fix t = 0 and J = 1; Generate the variable w 1 (0); Fix Stopping = False; while Stopping = False do while max 1≤j≤J w j (t) < 1 -do Increase J by 1; Generate the variable w J (t); while J > 1 do

Decrease J by 1 and t by 1; Generate w 1 (t), . . . w J (t); while max 1≤j≤J w j (t) < 1 -do Increase J by 1; Generate the variable w J (t); Decrease t by 1; Generate w 1 (t);

Algorithm 1: Construction of a variable of law m(0).

We now describe more precisely the perfect simulation algorithm. Let F be a probability distribution satisfying (10.2), we fix ∈ [0, 1) such that F ([1 -, 1]) ∈ (0, 1). The algorithm requires distribution is given by F (dx) = 1 {x≤1} e x-1 dx. Additionally, as p → 0, the quantity E((T * ) 2 ) grows to ∞. We estimated E((T * ) 2 ) for F = pδ 1 + (1 -p)δ -∞ and plotted this quantity as a function of p in Figure 11.

We observe in Figure 10 that different choices of the value can have a dramatic impact on the efficiency of Algorithm 1. Choosing a value too small has the effect of making the first appearance of a triangular event too late. On the other hand, if is too big then with high probability, one will have w 1 (T ) ≤ , and thus the first "successful" triangular event will appear much later. For the distribution F we chose, it appears that an optimal choice of seems to be around = 0.7, which balances between these two extremes. We observe in Figure 11 that if F puts a large mass on the negative half-line, the complexity of Algorithm 1 can become quite large. The function p → E(T * ) 2 grows at least exponentially in 1/p as p → 0 in the Barak-Erdős graph, but we were not able to obtain a good estimate of this rate of increase. Remark 10.8 (Perfect simulation when the charge distribution has an infinite essential supremum). We explained how to perfectly simulate the random variable m(0) + whose expectation is C(F ) under the assumption that the supremum of the support of F is 1 or any finite number for that matter.

To perfectly simulate a random variable whose expectation is C(F ) when the supremum of the support of F is ∞, we use an idea by Glynn and Rhee [START_REF] Glynn | Exact estimation for markov chain equilibrium[END_REF]. Denote by X n the variable m(0) + when F = F n has n as the supremum of its support and note that X n → X a.s. and in L 1 for some random variable X. Then C(F n ) = EX n → EX = C(F ), as n → ∞. We may not be able to perfectly simulate X. However, if we let ν be a positive random integer such that p n = P(ν = n) > 0 for all n and set Y = (X ν -X ν-1 )/p ν then Y can be perfectly simulated. Moreover, EY = C(F ). This is because EY =

Remark 10.9. For the special case of a Barak-Erdős graph, a simpler perfect simulation algorithm is explained in [START_REF] Foss | Extended renovation theory and limit theorems for stochastic ordered graphs[END_REF].

Additional remarks and open problems

The last passage percolation constant C(p) for -→ G (Z, p) has been one of the main concerns in this survey. We showed how very good approximations can be obtained analytically by relating -→ G (Z, p) to the IBM(p) model. The function C(p) is not convex. We conjecture however that C(p)/p is.

The passage to the IBM enables using branching processes techniques that help explain the slow rate of convergence of C(p)/p to e as p → 0 and its relation to the Brunet-Derrida behavior. Such phenomena should be present when the geometric(p), 0 < p < 1, distributions in the IBM are replaced by a family of more general distributions. The CLT's are generally available for the length of the longest or heaviest path but, as explained, some moment conditions are needed in case random weights are added to the edges. There is one thing that is not totally clear in the CLT's and this is the variance parameter. In, e.g., the case of -→ G (Z, p), we have that (L n -Cnt)/ √ σ 2 λn converges in distribution to a standard normal with σ 2 being equal to the variance of L Γ1,Γ2 -C(Γ 2 -Γ 2 ). This quantity is unknown and not even bounds are available. The situation becomes more complex in presence of weights.

CLT's are also available for the IBM and can take various forms. For example, for the IBM(p) model, it has been shown that

When considering random directed graphs on partially ordered vertex sets, the CLT limits are not necessarily Gaussian. The Brownian last passage percolation process Z(t) = max 0≤s≤t (X(s) + Y (t) -Y (s)) pops up in the case of the vertex set Z × {1, 2}. We know nothing about the random variable S = S(t) that achieves this maximum. This is of interest as it would related to the path that achieves the maximum.

Concerning longest paths of -→ G (Z × Z, p) on a window [0, n] × [0, m], as n, m = m(n) → ∞, the limit theorem of (7.6) is not optimal. We conjecture that the Tracy-Widom limit is also possible when m(n) grows with n linearly. One can of course ask for analogous results in the -→ G (Z d , p) case, when d ≥ 3. It is not clear at all what kind of laws would replace the Tracy-Widom distribution here.

The recent paper of Terlat [START_REF] Terlat | Regularity of the time constant for last passage percolation on complete directed acyclic graphs[END_REF] makes progress in the behavior of C(F ) when F is a distribution whose support may include negative numbers with a possible atom on -∞. Concerning however the type of limit theorems that one can obtain when F is heavy-tailed, such as those of Section (8.2), the field is open.

Concerning other types of behavior of maximal lengths or weights, e.g., in the large deviations sense, we mention that, when weights have a distribution supported on the integers, normal and moderate large deviations were obtained in [START_REF] Konstantopoulos | Limit theorems for the maximal path weight in a directed grah on the line with random weights of edges[END_REF]. In addition local limit theorems were obtained when the weight distribution is non-lattice.

Distributional results for maximal/heaviest weighted paths are not available beyond results around CLTs. However, in the sparse case, one can use the recursive nature of the (possibly weighted) PWIT to come up with functional equations for such quantities. See e.g. [42, eq. ( 13)].

Recall that C(p, x) of Section 9, is the last passage percolation constant when the weight law is pδ 1 + (1 -p)δ x for all edges (i, j) with i < j. There is only one solvable model we are aware of, that of C(p, 0) as in [START_REF] Dutta | On limit constants in last passage percolation in transitive tournaments[END_REF]. Can there be other ones?

If we replace pδ 1 + (1 -p)δ x above by F p,x = pQ + (1 -p)δ x where Q is a probability measure on (0, ∞) we expect that the behavior of p → C(F p,x ) can be obtained by techniques similar to those of [START_REF] Mallein | Barak-Erdős graphs and the infinite bin model[END_REF][START_REF] Mallein | Two-sided infinite bin models and analyticity for Barak-Erdős graphs[END_REF], so long as y 2 Q(dy) < ∞. As a function of x, the C(F p,x ) quantity is continuous and convex and it can be seen that C(F p,x ) is not differentiable at x iff Q has an atom y such that x/y ∈ X crit . See [START_REF] Foss | Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph[END_REF]Sec. 5].