is still a renewal process as it is obtained by thinning. Moreover, $\mathcal{S}^I$ is stationary and ergodic (with respect to $\theta$) and has positive rate. Hence $\mathcal{S}^I$ is a random subset of $\mathbb{Z}$ that is infinite in both directions. Let $\Gamma_k^I, k \in \mathbb{Z}$, be an enumeration of the elements of $\mathcal{S}^I$ with $\Gamma_k^I < \Gamma_{k+1}^I$ for all $k \in \mathbb{Z}$, and $\Gamma_0^I \le 0 < \Gamma_1^I$. Then, as in the Barak-Erdős case (see Lemma 6.1) is we let $\overline{G}_k$ be the induced subgraph of $\overline{G}(\mathbb{Z} \times I, p)$ on $\{(u, i) \in \mathbb{Z} \times I : \Gamma_k^I \le u \le \Gamma_{k+1}\}$, we have that, conditional on $\{0 \in \mathcal{S}^I\}$, the $\overline{G}_k, k \in \mathbb{Z}$, are i.i.d. Therefore, a maximal-length path on $\{0, \dots, n\} \times I$ is necessarily a path from $(0, 1)$ to $(n, M)$ such that if $0 \le \Gamma_k^I \le n$ then such a path passes via a vertex whose horizontal coordinate is $\Gamma_k^I$; see Figure 8. Using this and breaking $\ell_n(t)$ as in (6.13),

<figure><img src="image_8.png" /><figcaption>Figure 8: A maximal length path on $[0, n] \times I$ passes through all intermediate skeleton points and switches line at some of them.</figcaption></figure>

we arrive at the result by using Donsker's theorem. Details can be found in [39]. □

<figure><img src="image_9.png" /></figure>

## 7.2 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, \leq)$ with a bottom element called 1 and a top element called $M$. We then equip $\mathbb{Z} \times I$ with a strict partial order $\ll$ defined by

$$ (u, i) \ll (v, j) \text{ if } (u, i) \neq (v, j) \text{ and } u \leq v, i \leq j. $$

A pair of vertices $(u, i)$, $(v, j)$, with $(u, i) \ll (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:

$$ \forall i \in I \ r_{n,i,i} := p_n, \quad 0 < p_1 < 1, \quad \sum_{n=1}^{\infty} n \prod_{m=1}^{n} (1 - p_m) < \infty. \qquad (7.2) $$

Let as denote by $\overline{G}(\mathbb{Z} \times I, (r_{n,i,j}))$ the resulting random graph on $\mathbb{Z} \times I$ and let $L_{0,n}^*$ be the maximum length of all paths with endpoints in $[0, n] \times 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 $\mathbb{H}(I)$ of the partially ordered set $(I, \leq)$, which is the directed graph on $I$ obtained by declaring there is an edge from $i$ to $j$ if

$$ i \leq j \text{ and there is no } k, \text{ distinct from } i \text{ and } j, \text{ such that } i \leq k \leq j. $$

See [37]. Let $B^{(i)}$, $i \in I$, be independent standard Brownian motions. For any path $\iota = (\iota_0, \dots, \iota_r)$ in $\mathbb{H}(I)$ we write

$$ Z^{(\iota)}(t) := \max_{0=t_0 \le t_1 \le \cdots \le t_r = t} \{B^{(\iota_0)}(t_1) + [B^{(\iota_1)}(t_2) - B^{(\iota_1)}(t_1)] + \cdots + [B^{(\iota_r)}(t_r) - B^{(\iota_r)}(t_{r-1})]\}, $$

and then let

$$ Z_I(t) := \max_{\iota} Z^{(\iota)}(t), \qquad (7.3) $$
where the maximum is taken over all paths $\iota$ in $\mathbb{H}(I)$ from 0 to $M$. Then $Z_I$ is the limit of the sequence of normalized processes.

## 7.3 Convergence to the Tracy-Widom distribution

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

$$ (Z_I(ct))_{t \ge 0} \stackrel{d}{=} c^{1/2} (Z_I(t))_{t \ge 0}, $$

for any $c > 0$. In particular, the process $Z_M$ of (7.1) is a special case of (7.3), when $I = \{1, \dots, M\}$, has well-known connection with random matrix theory; see below.

**Queueing theory.** Glynn and Whitt [55] 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 $\sigma_{m,n}$ the service time of customer $m$ in queue $n$. It is assumed that the $\sigma_{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}) + \sigma_{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} + \sigma_{m,n}$; and if it finds the queue empty then $L_{m,n} = L_{m,n-1} + \sigma_{m,n}$. We can easily solve the recursion and express it as follows. Consider $\mathbb{N} \times \mathbb{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) \in \mathbb{N} \times \mathbb{N}$ with weight $\sigma_{i,j}$. Let $\pi$ be a path in this graph. Then $w(\pi)$ is the sum of the weights of the vertices of this path. We obtain

$$ L_{m,n} = \max\{w(\pi) : \pi \text{ is path from } (1,1) \text{ to } (m,n)\}, \quad (m,n) \in \mathbb{N} \times \mathbb{N}. $$

Consider now the normalized departure times,

$$ \ell_m^{(n)} := \frac{L_{m,n} - n\mathbb{E}\sigma}{\sqrt{n \mathrm{var}\sigma}}, $$

where $\sigma$ has the same law as (any of) the $\sigma_{m,n}$. Then [55] show that

$$ \ell_M^{(n)} \to Z_M(1), \text{ as } n \to \infty, \text{ in distribution,} $$

where $Z_M$ is as in (7.1). For subsequent work on the symmetry, duality, and other quantities of interest, see [9].

**The GUE.** Let $H$ be an $M \times M$ GUE (Gaussian Unitary Ensemble) random matrix [84]. This is a random element of the set of complex Hermitian $M \times 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 + \sqrt{-1}Y$ where $X, Y$ are i.i.d. Gaussian random variables with $\mathbb{E}X = \mathbb{E}Y = 0$, $\mathbb{E}X^2 = \mathbb{E}Y^2 = 1/2$.) Moreover, all elements $H_{k,\ell}$, $k \le \ell$, are independent (and $H_{\ell,k} = \bar{H}_{k,\ell}$ for $k \le \ell$). The eigenvalues of $H$ are real random variables and the largest of them is denoted by $\lambda_M$. It is clear that $H$ satisfies $H \stackrel{d}{=} UHU^{-1}$ for any unitary ($U^{-1} = U^*$) complex matrix $U$. It was shown independently by Baryshnikov [11] and Gravner et al. [56], thus answering an open question by Glynn and Whitt [55], that $Z_M(1)$ satisfies

$$ Z_M(1) \stackrel{d}{=} \lambda_M, \qquad (7.4) $$

thus establishing a connection between Brownian last passage percolation and random matrix theory.
**CLT for the largest GUE eigenvalue.** The law of $\lambda_m$ satisfies $\lambda_m/\sqrt{m} \to 2$. The CLT for $\lambda_m$ is

$$m^{1/6}(\lambda_m - 2\sqrt{m}) \xrightarrow{d} F_2, \qquad (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) = \frac{\mathrm{Ai}(x) \mathrm{Ai}'(y) - \mathrm{Ai}'(x) \mathrm{Ai}(y)}{x - y},$$

and where $\mathrm{Ai}(x)$ is the principal Airy function, defined as the solution $y = \mathrm{Ai}(x)$ to the linear ODE $y'' - xy = 0$ with boundary condition $y \to 0$ as $x \to \infty$. Fourier-transforming the ODE, at least formally, easily yields that $\mathrm{Ai}(x) := \pi^{-1} \int_{0}^{\infty} \cos(\frac{1}{3}\omega^3 + \omega x)d\omega = \pi^{-1} \lim_{\Omega \to \infty} \int_{0}^{\Omega} \cos(\frac{1}{3}\omega^3 + \omega x)d\omega$. Note that $K(x, x)$ is defined as a limit when $y \to 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 [96] and the distribution $F_2$ is known as the Tracy-Widom law, see also Anderson, Guionnet and Zeitouni [7].

**Barak-Erdős graph on $N \times N$.** Consider the graph $\vec{G}(N \times N, p)$, with $0 < p < 1$. We equip $N \times N$ with the natural partial order; $(i, j)$ is before $(i', j')$ if $i \le i'$, $j \le j'$ and $(i, j) \ne (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 $\vec{G}(N \times N, p)$ on any horizontal line is a $\vec{G}(N, p)$. Consider the $m$-th line and apply Theorem 6.10. We obtain

$$\left( \frac{L_{[nt].m} - Cnt}{\sigma \sqrt{\lambda n}} \right)_{t \ge 0} \xrightarrow{d} Z_m, \text{ as } n \to \infty.$$

On the other hand, by self-similarity and (7.4), we have

$$Z_m(t) \stackrel{d}{=} \sqrt{t}\lambda_m,$$

and $m^{1/6}(\lambda_m - 2\sqrt{m}) \xrightarrow{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} \left( \frac{Z_m(t)}{\sqrt{t}} - 2\sqrt{m} \right) \xrightarrow{d} F_2, \text{ as } m \to \infty.$$

A statement of the form $X(t, m) \xrightarrow{m \to \infty} X$, where the distribution of $X(t, m)$ does not depend on the choice of $t > 0$, implies the statement $X(t, m(t)) \xrightarrow{d} X$, for any function $m(t)$ such that $m(t) \xrightarrow{t \to \infty} \infty$. Hence, upon setting $m = [t^a]$, we have

$$t^{a/6} \left( \frac{Z_{[t^a]}(t)}{\sqrt{t}} - 2\sqrt{t^a} \right) \xrightarrow{d} 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} \left( \frac{L_{n, [n^a]} - c_1 n}{c_2 \sqrt{n}} - 2\sqrt{n^a} \right) \xrightarrow{d} F_2, \qquad (7.6)$$

where $c_1, c_2$ are appropriate constants. Indeed, (7.6) holds, with $c_1 = C = C(p)$ and $c_2 = \lambda\sigma^2$ and $a$ sufficiently small. This was proved in [72, Theorem 6.1] for the more general case of graphs
where the edge probabilities may not be constant, as in Section 6. The smallness of a depends on a condition that involves the edge probabilities.

That paper used the idea of strong coupling with Brownian motions (Komlós-Major-Tusnády [70, 71, Theorem 4]), as in [17], a paper dealing with last passage percolation on $N \times N$ with random weights on the vertices. The difficulty in the proof of the main theorem in [72] 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 [63] for last passage percolation on a lattice (with i.i.d. exponential weights on vertices). There are also exciting connections with processes fundamental to modern probability theory and mathematical physics, such as the Kardar-Parizi-Zhang (KPZ) universality class. We refer to the recent works by Dauvergne et al [35, 36] on the convergence of the Brownian last passage percolation to the central object in the KPZ class, namely the directed landscape.

# 8 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 [49] and [45] for details. Recall that existence of an edge $(i, j)$ is encoded by a random variable $\alpha_{i,j}$ that takes value 1 with probability $p$ or $-\infty$ with probability $1-p$. Let $u$ be a positive random variable with distribution function $F(x) = P(u \le x)$, and let $u_{i,j}$, $i < j$, be a collection of i.i.d. copies of $u$. If $\alpha_{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 $\vec{G}(\mathbb{Z}, p, u)$. A path from $i$ to $j$ of length $\ell$ and weight $w$ is a sequence $(i = i_0 < i_1 < \dots < i_{\ell-1} < i_{\ell} = j)$ such that $\alpha_{i_0, i_1} = \dots = \alpha_{i_{\ell-1}, i_{\ell}} = 1$ and $u_{i_0, i_1} + \dots + u_{i_{\ell-1}, i_{\ell}} = w$. A geodesic from $i$ to $j$ is a maximum weight path from $i$ to $j$.

Different phenomena appear depending on whether $\mathbb{E}u^2$ is finite or not.

## 8.1 Finite variance weights

Assume that $\mathbb{E}u^2 < \infty$. We study

$$W_{i,j} := \max_{i=i_0<i_1<\dots<i_\ell=j} \left( \sum_{k=1}^{\ell} \alpha_{i_{k-1},i_k} u_{i_{k-1},i_k} \right)^+,$$

the maximum weight of all paths from $i$ and $j$. If we further define the larger quantity $\tilde{W}_{i,j} := \max_{i\le i_0<i_1<\dots<i_\ell\le j} (\sum_{k=1}^\ell \alpha_{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

$$\tilde{W}_{i,k} \le \tilde{W}_{i,j} + \tilde{W}_{j,k} + \max_{i \le x \le j \le y \le k} u_{x,y}.$$

We can then see that $\lim_{n\to\infty} \tilde{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 $\mathbb{E}u^2 < \infty$ 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 $\mathcal{S}$ and the second is the set $\mathcal{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 \text{ for all } n \ge 1\}, \\ A_i^- = \{W_{i-n,i} > cn \text{ for all } n \ge 1\}, \\ A_i^{-+} = \{\alpha_{i-m,i+n} u_{i-m,i+n} < c(m+n) \text{ for all } m, n \ge 1\},$$

and then let

$$\mathcal{R}_c = \{i \in \mathbb{Z} : A_i^+ \cap A_i^- \cap A_i^{-+} \text{ occurs}\}.$$
Clearly, $\mathcal{R}_c$ is a stationary and ergodic random set with density

$$ \mu(c, p) = \mathbb{P}(A_0^+ \cap A_0^- \cap A_0^{-+}). $$

Since

$$ \mathcal{R}_c \subset \mathcal{S}, $$

we have $\mu(c, p) \le \lambda(p)$, where $\lambda(p)$ is the density of $\mathcal{S}$; see (2.9) and Remark 2.9.

**Lemma 8.1.** Assume that $\mathbb{E}u^2 < \infty$ and $0 < c < (\mathbb{E}u)(\mathbb{E}W_{\Gamma_1, \Gamma_2})$. Then $\mu(c, p) > 0$. Moreover, $\vec{G}(\mathbb{Z}, p, u)$ regenerates over $\mathcal{R}_c$.

*Sketch of proof.* We first observe that $\mathbb{P}(A_0^+) = \mathbb{P}(A_0^-)$. If we choose $0 < c < (\mathbb{E}u)(\mathbb{E}W_{\Gamma_1, \Gamma_2})$ then $\mathbb{P}(A_0^+) > 0$. The finiteness of $\mathbb{E}u^2$ implies the positivity of $\mathbb{P}(A_0^{-+})$. It can be shown that $A_0^+, A_0^-, A_0^{-+}$ are independent and so $\mu(c, p) = \mathbb{P}(A_0^+)\mathbb{P}(A_0^-)\mathbb{P}(A_0^{-+}) > 0$. For details see [45, Lemma 2]. For the last assertion see [45, Lemma 3]. □

This lemma is responsible for the law of large numbers:

**Theorem 8.2.** Assume that $\mathbb{E}u^2 < \infty$ and $0 < p \le 1$. Then there is a constant $C$ depending on $p$ and the law of $u$ such that

$$ \lim_{n \to \infty} \frac{W_{0,n}}{n} = \lim_{n \to \infty} \frac{\widetilde{W}_{0,n}}{n} = C \text{ a.s. and in } L^1. $$

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 $\mathbb{E}u^3 < \infty$ and $0 < p \le 1$. Then the sequence of processes

$$ \left\{ \frac{W_{0,[nt]} - Cnt}{\sqrt{\lambda n}}, t \ge 0 \right\} $$

converges in distribution, as $n \to \infty$, 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 := \text{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

$$ \frac{1 - F(tx)}{1 - F(x)} \to t^{-s}, \text{ as } x \to \infty, \text{ for every } t > 0. \quad (8.1) $$

Of course, $s > 2$ is needed in order that $\mathbb{E}u^2$ be finite. When $2 < s < 3$, one can deduce that the fluctuations of $W_{0,n}$ are of order larger than $\sqrt{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

$$ \frac{\log h_n}{\log n} \to \frac{1}{s-1} \quad \text{in probability as } n \to \infty. \quad (8.2) $$

In particular, if $2 < s < 3$ then

$$ \frac{\operatorname{var} W_{0,n}}{n} \to \infty, $$

and a central limit theorem such as that in Theorem 8.3 cannot hold.

The proof of this can be found in [49].
## 8.2 Infinite variance weights

Assume now that $\mathbb{E}u^2 = \infty$. 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 $\mathbb{E}W_{0,n}/n \to \infty$ as $n \to \infty$, and from Kingman's subadditive ergodic theorem we can conclude that in fact $W_{0,n}/n \to \infty$ 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 $\mathbb{E}u^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 $\vec{G}(\mathbb{Z}, 1, u)$ case.

**Finite model** Let $\vec{G}_n$ be a graph on $V_n = \{0, \frac{1}{n}, \dots, \frac{n-1}{n}, 1\}$, edges $E_n = \{(i/n, j/n) : 0 \le i < j \le n\}$, and weights $u_e^{(n)}, e \in E_n$, that are i.i.d. copies of $u$. We can think of a path $\pi$ of $\vec{G}_n$ as a collection of edges $e_1, \dots, e_\ell$ where the ending point of $e_i$ is the starting point of $e_{i+1}$ for all $1 \le i < \ell$. Let $\Pi_n$ be the set of all paths in $\vec{G}_n$ from 0 to $n$ (a set of size $2^{n-1}$). The maximum weight of all paths in $\Pi_n$ can be written as

$$W_{0,n} = \max_{\pi \in \Pi_n} \sum_{e \in \pi} u_e^{(n)}.$$

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 \subset E_n$ is admissible if every pair of elements of $A$ are non-overlapping edges in the sense that the endpoints of one are $\le$ the endpoints of the other. If we let $C_n$ be the set of all admissible sets of edges then

$$W_{0,n} = \max_{\pi \in C_n} \sum_{e \in A} u_e^{(n)}. \qquad (8.3)$$

We next introduce another way to construct $\vec{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 = \binom{n+1}{2}.$$

Let $E_n = \{e_1, \dots, e_N\}$ be an enumeration of the edges. Let $M_{e_1}^{(n)}, M_{e_2}^{(n)}, \dots, M_{e_N}^{(n)}$ be the order statistics of the $u_{e_1}^{(n)}, u_{e_2}^{(n)}, \dots, u_{e_N}^{(n)}$ That is, $\{M_{e_1}^{(n)}, M_{e_2}^{(n)}, \dots, M_{e_N}^{(n)}\} = \{u_{e_1}^{(n)}, u_{e_2}^{(n)}, \dots, u_{e_N}^{(n)}\}$ (as sets) and $M_{e_1}^{(n)} > M_{e_2}^{(n)} > \dots > M_{e_N}^{(n)}$.

Let $Y_1^{(n)}, Y_2^{(n)}, \dots, Y_N^{(n)}$ be a random ordering of $\{e_1, \dots, e_N\}$ chosen uniformly from all the $N!$ possibilities. Assign weight $M_{e_i}^{(n)}$ to $Y_i^{(n)}$. We then have

$$C_n = \{A \subset \{e_1, \dots, e_N\} : \text{ for every pair } \{e_i, e_j\} \subset A \text{ the } Y_{e_i}^{(n)}, Y_{e_j}^{(n)} \text{ are non-overlapping}\} \quad (8.4)$$

and

$$W_{0,n} = \max_{A \in C_n} \sum_{e_i \in A} M_{e_i}^{(n)} \qquad (8.5)$$

which is equivalent (the same in distribution) to the previous definition of $W_{0,n}$ in (8.3).
**Infinite model** We next define a random weighted graph $\vec{G}$ on countably infinite random set of vertices. Let $W_1, W_2, \dots$ be a sequence of i.i.d. exponential random variables with mean 1 each. Set

$$M_k = (W_1 + \dots + W_k)^{-1/s}, \quad k = 1, 2, \dots$$

Let $U_1, U_2, \dots$ and $V_1, V_2, \dots$ 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 $\vec{G}$ are taken to be

$$Y_i = (\min(U_i, V_i), \max(U_i, V_i)), \quad i = 1, 2, \dots$$

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

$$\mathcal{C} = \{A \subset \{1, 2, \dots\} : Y_i \cap Y_j = \emptyset \text{ for all pairs } \{i, j\} \subset A\}.$$

In analogy to (8.5) we let

$$W = \sup_{A \in \mathcal{C}} \sum_{i \in A} M_i. \qquad (8.6)$$

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 \in \mathbb{N}$ we have

$$(Y_1^{(n)}, Y_2^{(n)}, \dots, Y_k^{(n)}) \xrightarrow{d} (Y_1, Y_2, \dots, Y_k) \qquad (8.7)$$

as $n \to \infty$, where we use the product topology on $([0, 1]^2)^k$.

Following [82, 57], let $b_n = a_{N_n} = F^{(-1)}(1 - \frac{1}{N_n})$ and put

$$\tilde{M}_i^{(n)} = \frac{M_i^{(n)}}{b_n}.$$

(As an example, if $F(x) = 1 - x^{-s}$ for $x \ge 1$, then $b_n$ grows like $n^{2/s}$. More generally, under assumption (8.1), $\lim_{n \to \infty} \frac{\log b_n}{\log n} = 2/s$). Then from classical results in extreme value theory we have for any $k \in \mathbb{N}$ that

$$(\tilde{M}_1^{(n)}, \tilde{M}_2^{(n)}, \dots, \tilde{M}_k^{(n)}) \xrightarrow{d} (M_1, M_2, \dots, M_k) \text{ as } n \to \infty. \qquad (8.8)$$

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 [49] that the heaviest edges are the ones that bring 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 \in (0, 2)$, then $\frac{W_{0,n}}{b_n} \to W$ in distribution as $n \to \infty$.

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 $\mathbb{E}u^2 < \infty$, where the important contribution to the maximal weight is given by edges of a lighter order, see e.g. Theorem 8.3 above.

# 9 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 [47]. The next section will deal with a more general model.
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.

For the models of this and the next section we assume that the support of the charge distribution is not a subset of $(-\infty, 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.

## 9.1 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_{i,j}^x = \begin{cases} 1, & \text{with probability } p \\ x, & \text{with probability } 1-p. \end{cases}$$

Let $\Pi_{i,j}$ be the set of strictly increasing finite sequences of integers, $i_0 < i_1 < \dots < i_\ell$ such that $i_0 = i$ and $i_\ell = j$. An element $\pi \in \Pi_{i,j}$ is a finite path in the complete directed graph on $\mathbb{Z}$ (that is, a graph such that every $(i, j)$ with $i < j$ is an edge directed from $i$ to $j$). So $\Pi_{i,j}$ is a deterministic set of size $2^{j-i} - 1$. Define

$$w^x(\pi) = \sum_{k=1}^{\ell} w_{i_{k-1}, i_k}^x, \quad \text{if } \pi = (i_0, \dots, i_\ell) \in \Pi_{i,j},$$

and call $w^x(\pi)$ the charge or weight of $\pi$. We are interested in

$$W_{i,j}^x = \max_{\pi=(i_0, \dots, i_\ell) \in \Pi_{i,j}} \sum_{k=1}^{\ell} w_{i_{k-1}, i_k}^x. \quad (9.1)$$

We will use the notation $\vec{G}(\mathbb{Z}, p, x)$ to denote the directed charged random graph on $\mathbb{Z}$ that contains as edges all $(i, j) \in \mathbb{Z} \times \mathbb{Z}$ with $i < j$ and which has with i.i.d. edge charges distributed as $w_{i,j}^x$. We study the asymptotic growth rate $C(p, x)$ of $W_{i,j}^x$; see (9.2) below. The Barak-Erdős graph is still denoted by $\vec{G}(\mathbb{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 $\mathbb{R} \cup \{-\infty, +\infty\}$. The case $x = +\infty$ is uninteresting as being trivial. The case $x = -\infty$ formally corresponds to the Barak-Erdős graph, the reason being as follows. The charge of $i_0, i_1, \dots, i_\ell$ equals $-\infty$ iff $w_{i_k, i_{k+1}}^x = -\infty$ for some $k$, and this is equivalent to $i_0, i_1, \dots, i_\ell$ not being a path in $\vec{G}(\mathbb{Z}, p)$. Hence $(W_{i,j}^{-\infty})^+ = L_{i,j}^{\text{L,R}}$ and $\vec{G}(\mathbb{Z}, p, -\infty) = \vec{G}(\mathbb{Z}, p)$.

An alternative way to think of $\vec{G}(\mathbb{Z}, p, x)$ is by letting all edges of $\vec{G}(\mathbb{Z}, p)$ be blue and all non-edges be red. Blue edges have charge 1; red edges have charge $x$.

**Theorem 9.1.** For $-\infty < x < \infty$ we have

$$\lim_{n \to \infty} \frac{W_{0,n}^x}{n} = \lim_{n \to \infty} \frac{(W_{0,n}^x)^+}{n} = \inf_{n \in \mathbb{N}} \frac{\mathbb{E}(W_{0,n}^x)^+}{n} =: C(p, x), \quad (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_{i,k}^x \ge W_{i,j}^x + W_{j,k}^x, \quad i < j < k.$$
Further properties of $C(p, x)$ are in Theorem 9.2 below. We shall use the following notations.

$$X_C := \{x \in \mathbb{R} : C(p, \cdot) \text{ is not differentiable at } x\}$$

$$Q^* := Q \setminus \mathbb{Z}$$

$$Y := \{q \in Q^* : q < 0\} \cup \{0\} \cup \{\frac{1}{2}, \frac{1}{3}, \dots\} \cup \{2, 3, \dots\}$$

**Theorem 9.2.**

(i) Scaling. $C(p, x) = xC(1-p, x)$, for all $x > 0$.

(ii) Continuity at $-\infty$. $\lim_{x \to -\infty} C(p, x) = C(p)$.

(iii) Convexity. $C(p, x)$ is increasing convex over $x \in \mathbb{R}$ and strictly positive.

(iv) Asymptotic growth. $\lim_{x \to \infty} C(p, x)/x = C(1-p, 0) = \left(\sum_{n=1}^{\infty} p^{\frac{1}{2}n(n-1)}\right)^{-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 $\vec{G}(\mathbb{Z}, p, x)$ with $\vec{G}(\mathbb{Z}, 1-p, 1/x)$. Property (iii) follows from the fact that $W_{i,j}^x$ 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 [41].

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

## 9.2 Further structure of inter-skeleton pieces

As usual, $[m, n]$ stands for the set of all integers $k$ with $m \le k \le n$. That the set $\mathcal{S}$ of skeleton points of $\vec{G}(\mathbb{Z}, p)$ splits $\vec{G}(\mathbb{Z}, 1-p, 1/x)$ into independent parts is not a surprise; see Lemma 6.1. Hence, if $(i_0, \dots, i_\ell)$ achieves the maximum in the right-hand side of the definition (9.1) for $W_{i,j}^x$, then $\{i_0, \dots, i_\ell\}$ contains all elements of $\mathcal{S} \cap [i, j]$.

Enumerate the elements $\Gamma_k$ of $\mathcal{S}$ as in (6.2). Let $\vec{G}(I, p)$ be the Barak-Erdős graph on the (possibly random) set of vertices $I \subset \mathbb{Z}$.

Fix a positive integer $n$. Consider the event $A_{0,n}^+$ that there is a path in $\vec{G}(\mathbb{Z}, p)$ from 0 to every vertex in $(1, n]$ and the event $A_{0,n}^-$ that there is a path from every vertex in $[0, n-1)$ to $n$; see (6.4). In addition, let

$$F_{0,n} := \{\text{for all } 0 < j < n \text{ there is } 0 < i < n \text{ with no path from } \min(i,j) \text{ to } \max(i,j)\},$$

and then set

$$H_{0,n} := A_{0,n}^+ \cap A_{0,n}^- \cap F_{0,n}.$$

The following is an expression for the distribution of $\vec{G}([\Gamma_0, \Gamma_1], p)$ conditional on $\{\Gamma_0 = 0\}$.

**Proposition 9.3.** For any nonnegative deterministic functional $\varphi(\vec{G}([\Gamma_0, \Gamma_1], p))$ of $\vec{G}([\Gamma_0, \Gamma_1], p)$ we have

$$\mathbb{E} \{ \varphi(\vec{G}([\Gamma_0, \Gamma_1], p) | \Gamma_0 = 0) \} = \sum_{n=1}^{\infty} \mathbb{E} \{ \varphi(\vec{G}([0, n], p); H_{0,n}) \}, \quad (9.3)$$

In particular,

$$\mathbb{P}(\Gamma_1 - \Gamma_0 = n | \Gamma_0 = 0) = \mathbb{P}(\Gamma_2 - \Gamma_1 = n) = \mathbb{P}(H_{0,n}). \quad (9.4)$$

Furthermore,

$$C(p, x) = \lambda \mathbb{E} W_{\Gamma_1, \Gamma_2}^x = \lambda \sum_{n=1}^{\infty} \mathbb{E}(W_{0,n}^x; H_{0,n}), \quad (9.5)$$

where $\lambda = \lambda(p)$ is as in (2.9).
For a proof see [47]. The intuition should be clear because, if, say, $A_{0,n}^{+} \cap A_{0,n}^{-}$ holds (in which case both 0 and $n$ are in $\mathcal{S}$) but $F_{0,n}$ fails, then there is an element of $\mathcal{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 $\Gamma_2 - \Gamma_1$:

$$ \mathbb{P}(\Gamma_2 - \Gamma_1 = n) = \begin{cases} p, & \text{if } n = 1 \\ 0, & \text{if } n = 2 \\ p^4(1-p), & \text{if } n = 3 \\ p^7(1-p)^3 + 3p^5(1-p)^2, & \text{if } n = 4 \end{cases} $$

The smallest value of $\Gamma_2 - \Gamma_1$ is 1. Suppose that $\Gamma_2 - \Gamma_1 \ge 2$. Note that $\vec{G}([\Gamma_1, \Gamma_2], p)$ must necessarily have the edges $(\Gamma_1, \Gamma_1+1)$ and $(\Gamma_2-1, \Gamma_2)$. If $\Gamma_2 - \Gamma_1$ were allowed to take value 2 then $\Gamma_1+1 = \Gamma_2 - 1$ would have been a skeleton point strictly between $\Gamma_1$ and $\Gamma_2$, which is impossible. This explains why $\mathbb{P}(\Gamma_2 - \Gamma_1 = 2) = 0$.

## 9.3 Criticality and nondifferentiability

Let $\pi = (i_0, \dots, i_\ell)$ be a finite strictly increasing sequence of integers. Let $N(\pi)$ be the number of $(i_{k-1}, i_k)$, $k = 1, \dots, \ell$ that are also edges of $\vec{G}(\mathbb{Z}, p)$. Thus, $N(\pi)$ is the number of blue edges of $\pi$. Similarly, $\overline{N}(\pi)$ is the number of red edges. Then

$$ w^x(\pi) = \sum_{k=1}^{\ell} w_{i_{k-1}, i_k}^x = N(\pi) + x\overline{N}(\pi). $$

Define

$$ \Pi_{i,j}^x := \{ \pi \in \Pi_{i,j} : w^x(\pi) = W_{i,j}^x \}, $$

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 obtain

$$ D^+ C(p, x) = \lambda \mathbb{E} D^+ W_{\Gamma_1, \Gamma_2}^x = \lambda \mathbb{E} \max_{\pi \in \Pi_{\Gamma_1, \Gamma_2}^x} \overline{N}(\pi), $$

$$ D^- C(p, x) = \lambda \mathbb{E} D^- W_{\Gamma_1, \Gamma_2}^x = \lambda \mathbb{E} \min_{\pi \in \Pi_{\Gamma_1, \Gamma_2}^x} \overline{N}(\pi). $$

Remark 9.5. To justify the last equalities in these two displays we simply observe that, by (9.1), $W_{\Gamma_1, \Gamma_2}^x$ is the maximum of the affine functions $x \mapsto w^x(\pi) = N(\pi) + x\overline{N}(\pi)$, over all $\pi \in \Pi_{\Gamma_1, \Gamma_2}$ and there are finitely many such $\pi$. But if we fix $x$, we may further restrict the maximum over all $\pi \in \Pi_{\Gamma_1, \Gamma_2}^x$. More generally, if $T$ is an index set, and if $a_t, b_t, t \in T$, are real numbers, then the function $f(x) = \max_t(a_t + b_t x)$ is convex and thus has right and left derivatives for each $x$, given by $D^+ f(x) = \lim_{h \downarrow 0} (1/h)(f(x+h) - f(x)) = \sup_{t \in T^x} b_t$, where $T^x = \{t \in T : a_t + b_t x = f(x)\}$; and similarly for $D^- f(x)$. In the language of convex analysis [91], we say that set of affine functions $x \mapsto a_t + b_t x, t \in T^x$, are supporting lines of the function $f$ at the point $x$ (the remaining ones are irrelevant) and these are the only ones responsible for the right and left derivatives of $f$ at $x$.

**Definition 9.6** (the sets $\mathfrak{G}_n$ and $\mathfrak{H}_n$). Let $\mathfrak{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 $\mathfrak{H}_n \subset \mathfrak{G}_n$ contain all $G \in \mathfrak{G}_n$ such that, for all $0 < j < n$,

(a) there is a path in $G$ from 0 to $n$ containing $j$;

(b) for some $i \neq j$ there is no path in $G$ from $\min(i, j)$ to $\max(i, j)$

For any path $\pi$ in a graph $G$ we let $N_G(\pi)$ be the number of edges of $\pi$ that are also edges of $G$ and we let $\overline{N}_G(\pi)$ the number of edges of $\pi$ that are not edges of $G$.

**Definition 9.7** (criticality). We say that $x \in \mathbb{R}$ is critical if there is a positive integer $n$ and a graph $G \in \mathfrak{H}_n$ possessing two paths $\pi_1, \pi_2$ such that
$$ (a) \ N_G(\pi_1) + x\overline{N}_G(\pi_1) = N_G(\pi_2) + x\overline{N}_G(\pi_2) = \max_{\pi \in \Pi_{0,n}} (N_G(\pi) + x\overline{N}_G(\pi)) $$

$$ (b) \ \overline{N}_G(\pi_1) \neq \overline{N}_G(\pi_2). $$

Criticality is a property of real numbers. We let

$$ \mathcal{X}_{\text{crit}} = \{x \in \mathbb{R} : x \text{ is critical}\}. $$

Using Proposition 9.3 we can prove

**Theorem 9.8.**

$$ \mathcal{X}_C = \mathcal{X}_{\text{crit}}. $$

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

$$ \mathcal{X}_{\text{crit}} = \mathbb{Y}, \qquad (9.6) $$

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

**9.4** $\mathbb{Y} \subset \mathcal{X}_{\text{crit}}$

Let $x \in \mathbb{R}$, $G \in \mathfrak{G}_n$ and $\pi \in \Pi_{0,n}$. Think of the common edges of $\pi$ and $G$ as blue and the remaining edges of $\pi$ as red. There are $N_G(\pi)$ blue and $\overline{N}_G(\pi)$ red edges. The path $\pi$ is called $(x, G)$-maximal if it achieves the maximum in $\max_{\pi \in \Pi_{0,n}} (N_G(\pi) + x\overline{N}_G(\pi))$.

Showing that $x \in \mathcal{X}_{\text{crit}}$ one proceeds by constructing a $G \in \mathfrak{H}_n$ possessing at least two $(x, G)$-maximal paths with different number of red edges. Figure 9 summarizes how this is done for each element $x$ of $\mathbb{Y}$, except $x = 2, 3, \dots$, since if we know that $1/k \in \mathcal{X}_{\text{crit}}$ ($k = 2, 3, \dots$) then we also know that $k \in \mathcal{X}_{\text{crit}}$ by the scaling property. For example, Figure 9(a) shows that $0 \in \mathcal{X}_{\text{crit}}$. Indeed, consider the paths $\pi_1 = (0, 1, 3)$ and $\pi_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.

The most complex case is that of the last line of Figure 9. 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 $\lfloor x \rfloor$, $\lceil x \rceil$ be the lower, respectively upper, parts of $x$.

**Lemma 9.9** (Corollary to Sturm's lemma [75]). Let $N, n$ be positive integers, $N \ge n$. Then there exists a unique finite sequence $v = (v_1, \dots, v_N)$ of elements of $\{0, 1\}$ such that, for all $0 \le i < j \le N$, the following hold:

$$ \sum_{i<k \le j} v_k \in \left\{ \lfloor (j-i) \frac{n}{N} \rfloor, \lfloor (j-i) \frac{n}{N} \rfloor \right\}, \quad \sum_{i<k \le N} v_k = \lfloor (N-i) \frac{n}{N} \rfloor, \quad v_1 = 1. $$

We say that the sequence $(v_1, \dots, v_N)$ defined through this lemma is the $(N, n)$-balanced sequence. For example, with $N = 7, n = 4$ we find $(v_1, \dots, v_7) = (1, 1, 0, 1, 0, 1, 0)$

Next, given $x < 0$, $x \in \mathbb{Q}^*$, write

$$ x = -\ell + \frac{s}{t}, $$

uniquely, where $\ell, s, t$ are positive integers, $t > 1$, $\gcd(s, t) = 1$, $s < t$, and let $(v_1, \dots, v_t)$ be the $(t, t-s)$-balanced sequence. Construct a graph $G$ on $[0, n = 3m]$ where

$$ m := t(\ell + 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 vertices $a_0, \dots, a_t$ are defined by

$$ a_0 := m, $$

$$ a_1 := a_0 + (\ell + 1) + v_1, $$

$$ a_j := a_{j-1} + (\ell + 2) + v_j, \quad j = 2, \dots, t. $$
<figure><img src="image_10.png" /><figcaption>(a) Each red edge (i.e. each non-edge) has charge 0. This graph shows that $0 \in \mathbb{X}_{\text{crit}}$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b) Let $k \in \{2, 3, \dots\}$. Each non-edge has charge $1/k$. This graph shows that $1/k \in \mathbb{X}_{\text{crit}}$.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(c) Let $-\ell \in \{-1, -2, \dots\}$. Each non-edge has charge $-1/\ell$. This graph shows that $-\ell \in \mathbb{X}_{\text{crit}}$.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(d) Let $x < 0$, rational, but not an integer. Each non-edge has charge $x$. Write $x = -\ell+(s/t)$, $\ell, s, t \in \mathbb{N}$, $t > 1$, $\gcd(s, t) = 1$, $s < t$.</figcaption></figure>

Figure 9: Graphs exhibiting that $\mathbb{Y} \subset \mathbb{X}_{\text{crit}}$.

Finally, 0 is connected by an edge to some vertices as shown 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, $\ell = 2$, $s = 3$, $t = 7$, $m = 31$, $n = 93$. The (7, 4) balanced sequence is $(v_1, \dots, v_7) = (1, 1, 0, 1, 0, 1, 0)$. We also have $a_0 = 31$, $a_1 - a_0 = \ell + 1 + v_1 = 4$, $a_2 - a_1 = \ell + 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 $\mathfrak{H}_n$ is not obvious, neither it is obvious that $x \in \mathbb{X}_{\text{crit}}$. The details are omitted.

## 9.5 $\mathbb{X}_{\text{crit}} \subset \mathbb{Y}$

We will show that $\mathbb{Y}^c \subset \mathbb{X}_{\text{crit}}^c$. Note that all irrationals are elements of $\mathbb{Y}^c$.

First assume that $x \in \mathbb{Y}^c$ is irrational. Since, by Proposition 9.8, $\mathbb{X}_{\text{crit}} = \mathbb{X}_C$, we show that $x \in \mathbb{X}_C^c$. The set of points at which $x \mapsto W_{\Gamma_1, \Gamma_2}^x$ fails to be differentiable is included in the set of points $x$ for which there are two paths $\pi_1, \pi_2$ from $\Gamma_1$ to $\Gamma_2$ such that $w^x(\pi_1) = w^x(\pi_2)$ with $\bar{N}(\pi_1) \neq \bar{N}(\pi_2)$. This implies that $(\bar{N}(\pi_2) - \bar{N}(\pi_1))x = N(\pi_1) - N(\pi_2)$, which means that $x$ is rational. Hence $W_{\Gamma_1, \Gamma_2}^x$ 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 \in \mathbb{X}_C^c$.

Next let $x \in \mathbb{Y}^c$ but not irrational. Showing that $x \in \mathbb{X}_{\text{crit}}^c$ one proceeds by showing that for every $n \ge 3$ and every $G \in \mathfrak{H}_n$ there is a unique $(x, G)$-maximal path or that every $(x, G)$-maximal path has the same $\bar{N}_G(\pi) (=\text{number of red edges})$.

If $x = 1$ then every edge and every non-edge of a graph $G \in \mathfrak{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, \dots, n)$. So $1 \in \mathbb{X}_{\text{crit}}^c$.

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 \in (0, 1) \cup (1, \infty)$. By the scaling property, we only need to consider $x \in (0, 1)$. Since $1/2, 1/3, \dots$ are critical, we assume that $x \in (0, 1) \setminus \{1/2, 1/3, \dots\}$.

**Proposition 9.10.** Every $0 < x < 1$ that is not the reciprocal of an integer is not critical.
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 [47]. 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' \le i < j \le j'$ and $e \ne e'$. Let $\pi, \pi' \in \Pi_{0,n}$. We say that the interval $[i, j] \subset [0, n]$ is $(\pi, \pi')$-special if the set of vertices $k \in [i, j]$ that belong to both $\pi$ and $\pi'$ consists of $i$ and $j$ only.

**Lemma 9.11.** If $0 < x < 2$ then every maximal path contains all short blue edges.

**Lemma 9.12.** If $0 < x < 2$ then every long edge of a maximal path $\pi$ is blue (in other words, every red edge of $\pi$ must be short).

**Lemma 9.13.** 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.14.** Let $0 < x < 2$. Then for every pair $\pi, \pi' \in \Pi_{0,n}$ of maximal paths such that $\overline{N}_G(\pi) \ne \overline{N}_G(\pi')$ there is a $(\pi, \pi')$-special interval $I$ such that

$$ \overline{N}_G(\pi|_I) \ne \overline{N}_G(\pi'|_I) $$

and

$$ N_G(\pi|_I) - N_G(\pi'|_I) \in \{-1, 1\}. $$

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

*Proof of Proposition 9.10.* 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 \ge 3$ and $G \in \mathfrak{S}_n$ (edges of $G$ are called blue and non-edges red) and two maximal paths $\pi_1, \pi_2$ with different number of red edges: $\overline{N}_G(\pi_1) \ne \overline{N}_G(\pi_2)$. By the Lemma 9.14, there is a $(\pi_1, \pi_2)$-special interval $[i, j]$ such that $N_G(\pi_1|_I) - N_G(\pi_2|_I) \in \{1, -1\}$. Since

$$ 0 = w_G^x(\pi_1|_I) - w_G^x(\pi_2|_I) = (\overline{N}_G(\pi_1|_I) - \overline{N}_G(\pi_2|_I))x + (N_G(\pi_1|_I) - N_G(\pi_2|_I)), $$

it follows that

$$ x = \frac{1}{|\overline{N}_G(\pi_1|[i, j]) - \overline{N}_G(\pi_2|[i, j])|}, $$

and hence the reciprocal of a positive integer.

□

*Remark 9.15.* We considered here differentiability properties for a last passage percolation problem. Differentiability properties of a first passage percolation model were studied in [93].

# 10 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 $\pi = (i_0, \dots, i_\ell)$, that is, a finite increasing sequence of integers, assign charge $w(\pi) = w_{i_0, i_1} + \dots + w_{i_{\ell-1}, i_\ell}$, and let

$$ W_{i,j} = \sup\{w(\pi) : \pi \text{ is a path from } i \text{ to } j\}. \qquad (10.1) $$

We use the notation $\overrightarrow{G}(\mathbb{Z}, F)$ for this random charged graph. Thus, $\overrightarrow{G}(\mathbb{Z}, p\delta_1 + (1-p)\delta_x)$ is another notation the graph dealt with in Section 9, while $\overrightarrow{G}(\mathbb{Z}, p\delta_1 + (1-p)\delta_{-\infty})$ is another notation for the Barak-Erdős graph $\overrightarrow{G}(\mathbb{Z}, p)$. Superadditivity inequality implies that there is a deterministic $C(F)$ such that

$$ \frac{W_{0,n}}{n} \to C(F), \quad \text{a.s. as } n \to \infty. $$

In Section 9 we studied $C(p, x) \equiv C(p\delta_1 + (1-p)\delta_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 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

$$ \mathrm{esssup} \ w_{i,j} = \inf\{z : F((z, \infty)) = 0\} = 1. \qquad (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\delta_{1/2} + (1-p)\delta_{-\infty}$ 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 [64]. Its relation to the so-called backwards-coupling was studied in [48]. It belongs to the broader area of coupling methods for stochastic recursions that may entirely lack the Markovian property [22, 31, 44].

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 [46].

## 10.1 The Max Growth System (MGS)

The content of this subsection is purely deterministic. Consider point measures on the set $\mathbb{R} \cup \{-\infty\}$ that will be referred to as “space”:

$$ \mathcal{N} := \{\text{locally finite point measures } \nu \text{ on } \mathbb{R} \cup \{-\infty\} \text{ such that } \nu(\mathbb{R}_+) < \infty\}. $$

For example, $\nu = 2\delta_1 + \delta_{-1.5} + 3\delta_{-4} + \delta_{-\infty} \in \mathcal{N}$. We think of $\nu$ as consisting of 7 particles, such that two of them are at 1, one at -1.5, three at -4 and one at -$\infty$; so we can equivalently represent $\nu$ by the locations of its particles (1, 1, -1.5, -4, -4, -4, -$\infty$) arranged in decreasing order. In general, we let $\nu_1 \ge \nu_2 \ge \dots$ be the locations of the particles of $\nu$. So the function

$$ \mathcal{N} \ni \nu \mapsto \nu_k := \text{location of kth largest particle of } \nu $$

is well-defined for each $k$ and $\nu = \sum_{k \ge 1} \delta_{\nu_k}$. We also let

$$ \|\nu\| := \nu(\mathbb{R} \cup \{-\infty\}), \quad \inf \nu := \nu_{\|\nu\|}, $$

with $\inf \nu = -\infty$ if $\|\nu\| = \infty$. Next let

$$ \mathcal{W} := \{w = (w_1, w_2, \dots) : \sup_{k \ge 1} w_k \le 1, w_k \in \mathbb{R} \cup \{-\infty\} \text{ for all } k\}, $$

and define

$$ \mathfrak{m}(\nu, w) := \sup_{k \ge 1} (\nu_k + w_k), \quad \nu \ne 0, \quad w \in \mathcal{W}. $$

The map responsible for the dynamics of the MGS is defined by

$$ \Psi_w \nu := \nu + \delta_{\mathfrak{m}(\nu, w)}. $$

Composing these maps, for possibly different $w$ each time, gives a trajectory in $\mathcal{N}$. More precisely, the MGS starting at “time” $T$ from state $\nu(T) \in \mathbb{N}$ and driving sequence $w(t)$, $t > T$, is the sequence defined by

$$ \nu(t) = \Psi_{w(t)} \nu(t-1), \quad t > T, $$

that is,

$$ \nu(t) = \Psi_{w(t)} \circ \Psi_{w(t-1)} \circ \dots \circ \Psi_{w(T+1)} \nu(T). $$
Let $\mathcal{N}_0$ consist of those $\nu \in \mathcal{N}$ with $\nu_1 = 0$. Define the map

$$ \sigma: \mathcal{N} \to \mathcal{N}_0, \quad \sigma\nu = \sum_{k \ge 1} \delta_{\nu_k - \nu_1} $$

that places the origin of space at $\nu_1$. We will need the following easily verified properties.

$$ \begin{aligned} \sigma\Psi_w &= \sigma\Psi_w\sigma, \\ \mathfrak{m}(\sigma\nu, w) &= \mathfrak{m}(\nu, w) - \nu_1. \end{aligned} $$

We next consider an MGS $\nu(t)$, $t \ge 0$, and show that under certain conditions on the driving sequence the quantity

$$ \mathfrak{M}(t) \equiv \mathfrak{m}(\nu(t-1), w(t)) $$

will eventually not depend on the choice of the initial state $\nu(0)$.

**Lemma 10.1** (Decoupling property). Fix $\ell \in [0, 1)$. Consider two MGSs, $\nu$, $\tilde{\nu}$, starting at time 0 with $\nu(0) \in \mathcal{N}_0$ and $\tilde{\nu}(0) = \delta_0$. Assume that the driving sequence $w(t)$, $t > 0$, is the same for both. Let $\mathfrak{M}(t) = \mathfrak{m}(\nu(t-1), w(t))$, $\mathfrak{M}(t) = \mathfrak{m}(\tilde{\nu}(t-1), w(t))$. If

$$ \nu_2(0) \le -\ell, \qquad (10.3) $$

$$ \bar{w}(t) := \max\{w_1(t), \dots, w_t(t)\} \ge 1 - \ell \quad \text{for all } 1 \le t \le n, \qquad (10.4) $$

then

$$ \mathfrak{M}(t) = \tilde{\mathfrak{M}}(t) \quad \text{for all } 1 \le t \le n. \qquad (10.5) $$

*Proof.* We have $\nu_1(0) = 0 \ge -\ell \ge \nu_2(0)$, by assumption. We will show by induction that, for all $n \in \mathbb{N}$,

$$ \text{if } \bar{w}(1), \dots, \bar{w}(n) \ge 1 - \ell \text{ then } \left\{ \begin{array}{l} \mathfrak{M}(n) = \tilde{\mathfrak{M}}(n) \\ \nu(n)|_{\mathbb{R}_+} = \tilde{\nu}(n)|_{\mathbb{R}_+} \\ \nu(n)(\mathbb{R}_+) = n + 1 \\ \nu_{n+2}(n) \le -\ell \end{array} \right. \qquad (10.6) $$

Let $n = 1$ and assume that $\bar{w}(1) = w_1(1) \ge 1 - \ell$. We have $\mathfrak{M}(1) = \max\{\nu_1(0) + w_1(1), \nu_2(0) + w_2(1), \dots\} = w_1(1)$ because $\nu_1(0) + w_1(1) = w_1(1) \ge 1 - \ell$ and since $1 \ge w_j(1)$, $-\ell \ge \nu_j(0)$ for all $j \ge 2$, we have $w_1(1) \ge w_j(1) + \nu_j(0)$ for all $j \ge 2$ and so only the first term survives in the maximum. But then $\mathfrak{M}(1) = w_1(1) = \mathfrak{M}(1)$. Since $\nu(1) = \nu(0) + \delta_{\mathfrak{M}(1)}$ we have that its restriction on $\mathbb{R}_+$ equals $\delta_0 + \delta_{w_1(1)}$ and $\nu_3(1) = \nu_2(0) \le -\ell$. So (10.6) holds when $n = 1$.

Assume next (10.6) holds for some $n$. We show its veracity for $n + 1$. We work under the assumption that $\bar{w}(1), \dots, \bar{w}(n), \bar{w}(n+1) \ge 1 - \ell$. By (10.6) we have $\nu(n)|_{\mathbb{R}_+} = \tilde{\nu}(n)|_{\mathbb{R}_+}$ (containing $n + 1$ particles on $\mathbb{R}_+$) and $\nu_{n+1}(n-1) \le -\ell$. So

$$ \begin{aligned} \mathfrak{M}(n+1) &= \max_{j \ge 1} \{\nu_j(n) + w_j(n+1)\} \\ &= \max_{j \le n+1} \{\nu_j(n) + w_j(n+1)\} \vee \max_{j > n+1} \{\nu_j(n) + w_j(n+1)\} \\ &= \max_{j \le n+1} \{\tilde{\nu}_j(n) + w_j(n+1)\} \vee \max_{j > n+1} \{\nu_j(n) + w_j(n+1)\} \\ &= \max_{j \le n+1} \{\tilde{\nu}_j(n) + w_j(n+1)\} = \tilde{\mathfrak{M}}(n+1). \end{aligned} $$

The reason that we dropped the second maximum is that $\max_{j \le n+1}\{\tilde{\nu}_j(n-1) + w_j(n)\} \ge \max_{j \le n+1} w_j(n) \ge 1 - \ell$ while $\max_{j > n+1}\{\nu_j(n-1) + w_j(n)\} \le \nu_{n+1}(n-1) + \max_{j > n+1} w_j(n) \le -\ell + 1$. We also have $\nu(n+1) = \nu(n) + \delta_{\mathfrak{M}(n+1)} = \nu(n) + \delta_{\tilde{\mathfrak{M}}(n+1)}$ so $\nu(n+1)|_{\mathbb{R}_+} = \tilde{\nu}(n+1)|_{\mathbb{R}_+}$ and they have $n + 2$ particles on $\mathbb{R}_+$, while $\nu_{n+3}(n+1) = \nu_{n+2}(n) \le -\ell$. $\square$

*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 $\bar{w}(t)$ will be

$$ \bar{w}(T; t) := \max\{w_1(T+t), \dots, w_t(T+t)\}. \qquad (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 [19, 20, 21, 22, 23] and its extension for functional of stochastic dynamical systems in [45].

## 10.2 The MGS of a random charged graph, coupling and stationarity

**Definition 10.4.** Given a probability measure $Q$ on $\mathcal{W}$ define the random process MGS($Q$) by $\nu(t) = \Psi_{w(t)}\nu(t-1)$, $t \ge 1$, with $w(1), w(2), \dots$ being independent with common law $Q$, with $\nu(0) \in \mathcal{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 $\vec{G}(\mathbb{Z}, F)$ be a random charged graph with charge distribution $F$ satisfying (10.2). Let

$$W_n := W_{0,n},$$

in the notation of (10.1). In particular, $W_0 = 0$, $W_1 = w_{0,1}$, $W_2 = (w_{0,1} + w_{1,2}) \lor w_{1,2}$. Let

$$\nu^G(n) := \sum_{k=0}^{n} \delta_{W_k}, \quad n \ge 0. \qquad (10.8)$$

Then $\nu^G(n) \in \mathcal{N}$ and has $n+1$ particles. Clearly, $\nu^G(n) = \nu^G(n-1) + \delta_{W_n}$, with $W_n = \max_{0 \le k \le n-1} (W_k + w_{k,n}) = \max_k(\nu_k^G(n-1) + w_{\pi(k),n})$ where $\pi$ is a permutation on $\{0, \dots, n-1\}$ that puts $W_0, \dots, W_{n-1}$ in decreasing order. Hence $W_n \stackrel{d}{=} \max_k(\nu_k^G(n-1) + w_{k,n})$ and so if we consider the MGS($Q_F$) defined by

$$\nu(n) = \nu(n-1) + \delta_{\mathfrak{m}(\nu(n-1), w(n))},$$

starting with $\nu(0) = \delta_0$, we see that

$$\nu^G \stackrel{d}{=} \nu, \qquad (10.9)$$

not only component-wise, but also as processes. Therefore, letting

$$M_n = \max_{0 \le k \le n} W_k \qquad (10.10)$$

we have

$$(M_n - M_{n-1}, n \ge 1) \stackrel{d}{=} (\mathfrak{m}(\sigma\nu(n-1), w(n))^+, n \ge 1),$$

which implies that $M_n/n$ is a sample mean:

$$\frac{M_n}{n} = \frac{1}{n} \sum_{j=1}^{n} (M_j - M_{j-1}) \stackrel{d}{=} \frac{1}{n} \sum_{j=1}^{n} \mathfrak{m}(\sigma\nu(j-1), w(j))^+,$$

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

$$C(F) = \lim_{n \to \infty} \frac{W_n}{n} = \lim_{n \to \infty} \frac{M_n}{n} \quad \text{a.s.,}$$

and since $\int_0^\infty xF(dx) < \infty$, we have

$$C(F) = \lim_{n \to \infty} \frac{\mathbb{E}M_n}{n} = \lim_{n \to \infty} \frac{1}{n} \sum_{j=1}^{n} \mathbb{E}\mathfrak{m}(\sigma\nu(j-1), w(j))^+.$$

Remark 10.5. Let us make the reasonable ansatz that the quantity inside the last expectation converges in distribution to some random variable:

$$\mathfrak{m}(\sigma\nu(n-1), w(n))^+ \stackrel{d}{\to} \bar{\mathfrak{m}}^+ \text{ as } n \to \infty. \qquad (10.11)$$
Then, a poor man's estimate of $C(F)$ would be to simply to compute sample means

$$n^{-1} \sum_{j=1}^{n} \mathbb{E}\mathbf{m}(\sigma\nu(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 $\mathbf{m}(\sigma\nu(n-1), w(n))$, $n = 1, 2, \dots$, 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 $\nu$ be an MGS($Q_F$) with driving sequence $w(t)$, $t \in \mathbb{Z}$, starting from an arbitrary state at an arbitrary, possibly random, time. Then there exists a stationary process $(\bar{\mathbf{m}}(t), t \in \mathbb{Z})$ such that

$$\mathbf{m}(\sigma\nu(t-1), w(t)) = \bar{\mathbf{m}}(t) \text{ for } t \text{ large enough, a.s.}$$

$$\text{In particular } \mathbb{E}(\bar{\mathbf{m}}(0)^+) = C(F).$$

*Proof.* Let $\ell \in [0, 1)$ be such that $p := F([1 - \ell, 1]) > 0$, which is possible due to (10.2). For $k \in \mathbb{Z}$, consider the event

$$R_k := \{w_1(k) \ge \ell\} \cap \bigcap_{j=1}^{\infty} \{\max(w_1(k+j), \dots, w_j(k+j)) \ge 1 - \ell\}.$$

It is clear from its definition that $(R_k, k \in \mathbb{Z})$ is a stationary sequence of events with

$$\mathbb{P}(R_k) = \mathbb{P}(R_0) = F([\ell, 1]) \prod_{j=1}^{\infty} (1 - (1 - p)^j) > 0.$$

Consider the stationary random set $J := \{k \in \mathbb{Z} : R_k \text{ holds}\}$. Since $\mathbb{P}(R_k) > 0$, we have, by ergodicity (more specifically by the Poincaré recurrence theorem), $\inf J = -\infty$ and $\sup J = \infty$ a.s. We enumerate the elements of $J$ by

$$\dots < T_{-1} < T_0 \le 0 < T_1 < T_2 < \dots$$

Hence the $R_{T_i}$ are all events of probability 1. We define $\tilde{\nu}(t)$, $t \in \mathbb{R}$, by letting, for all $j$,

$$\tilde{\nu}(T_j) = \delta_0, \quad \tilde{\nu}(t) = \sigma \sum_{i \in \mathbb{Z}} \mathbb{1}_{\{T_i < t < T_{i+1}\}} \Psi_{w(t)}^t \circ \dots \circ \Psi_{w(T_i+1)}^{T_i+1} \delta_0, \quad t \ne T_j.$$

On the other hand, thanks to Lemma 10.1, the process $\mathbf{m}(\sigma\nu(t-1), w(t))$, $t > T_i$, is algebraically independent of $\nu(T_i)$. This shows, see [44], that the stationary process $\bar{\mathbf{m}}$ defined by

$$\bar{\mathbf{m}}(t) = \mathbf{m}(\sigma\tilde{\nu}(t-1), w(t)), \quad t \in \mathbb{Z},$$

satisfies $\bar{\mathbf{m}}(t) = \mathbf{m}(\sigma\nu(t-1), w(t))$ for all $t$ large enough, a.s. Next, using that

$$C(F) = \lim_{n \to \infty} \frac{\mathbb{E}(M_n)}{n} = \lim_{n \to \infty} \frac{1}{n} \sum_{j=1}^{n} \mathbb{E}(\mathbf{m}(\sigma\nu(j-1), w(j))^+) \quad \text{a.s.,}$$

and using the eventual equality between $\mathbf{m}(\sigma\nu(t-1), w(t))$ and $\bar{\mathbf{m}}(t)$, we have

$$C(F) = \lim_{n \to \infty} \frac{1}{n} \sum_{j=1}^{n} \mathbb{E}(\bar{\mathbf{m}}(j)^+) = \mathbb{E}(\bar{\mathbf{m}}(0)^+),$$

by stationarity and ergodicity of the sequence. $\square$
## 10.3 Perfect simulation

Recall the quantity $\bar{w}$ defined by (10.7).

**Theorem 10.7 (Perfect simulation).** Define

$$T^* := \sup\{t \le -1 : w_1(t) \ge \ell, \min_{1 \le j \le |t|} \bar{w}(t; j) \ge 1 - \ell\}.$$

Then $|T^*| < \infty$ a.s., and

$$\bar{m}(0) = m \left( \sigma \Psi_{w(T^*+1)}^{T^*+1} \circ \cdots \circ \Psi_{w(0)}^0 \delta_0; w(0) \right) \text{ a.s.}$$

*Proof.* We recall that $(T_{-j}, j \in \mathbb{N})$ are the negative elements of the random set $J$, with $T_{-1} > -\infty$. We remark that

$$w_1(T_{-1}) \ge \ell, \quad \bar{w}(T_{-1}; j) \ge 1 - \ell \text{ for all } j > 0,$$

therefore $T_* \ge T_{-1}$, proving its finiteness.

Moreover, since

$$w_1(T^*) \ge \ell, \min_{1 \le j \le |t|} \bar{w}(T^*; j) \ge 1 - \ell,$$

by Lemma 10.1, the quantity $m(\sigma\Psi_{w(T^*+1)}^{T^*+1} \circ \cdots \circ \Psi_{w(0)}^0 \nu; w(0))$ does not algebraically depend on the value of $\nu \in \mathcal{N}_0$. As a result, it is equal to $\bar{m}(0)$. $\square$

Fix $t=0$ and $J=1$;

Generate the variable $w_1(0)$;

Fix Stopping = False;

while Stopping = False do

while $\max_{1 \le j \le J} w_j(t) < 1 - \ell$ 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), \dots, w_J(t)$;

while $\max_{1 \le j \le J} w_j(t) < 1 - \ell$ do

Increase $J$ by 1;

Generate the variable $w_J(t)$;

Decrease $t$ by 1;

Generate $w_1(t)$;

Fix Stopping = {$w_1(t) \ge \ell$};

Fix $\nu = \delta_0$;

for $s$ from $t+1$ to $-1$ do

Generate the variables $w_1(s), \dots, w_{\|\nu\|}(s)$;

Set $\mathbf{m} = \max\{\nu_j + w_j(s) \text{ for } 1 \le j \le \|\nu\|\}$;

Add $\delta_m$ to $\nu$;

Set $\mathbf{m} = \max\{\nu_j + w_j(0) \text{ for } 1 \le j \le \|\nu\|\}$;

Return: $\mathbf{m} - \nu_1$;

**Algorithm 1:** Construction of a variable of law $\bar{m}(0)$.

We now describe more precisely the perfect simulation algorithm. Let $F$ be a probability distribution satisfying (10.2), we fix $\ell \in [0, 1)$ such that $F([1-\ell, 1]) \in (0, 1)$. The algorithm requires 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 $\bar{m}(0)$ from the sequence $\{w_j(t), j \in \mathbb{N}, t \in \mathbb{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)\} \cup \{w_j(t+k), 1 \le j \le k \le |t|\} $$

and $\bar{m}(0)$ is a measurable function of

$$ \{w_1(T^*)\} \cup \{w_j(T^* + k), 1 \le j \le k \le |T^*|\}. $$

Therefore, we can explore triangular arrays of the form

$$ \{w_1(t)\} \cup \{w_j(t+k), 1 \le j \le k \le |t|\}, $$

progressively decreasing $t$ until time $T^*$ is detected. Once this random variable is known, we construct the random variable $\bar{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 10.

<figure><img src="image_14.png" /><figcaption>Figure 10: Illustration of the execution of Algorithm 1 on an example, in the case where $\ell < 1-\ell$. 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 \le t \le 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 $\nu$ is enclosed by a red boundary.</figcaption></figure>

We observe that this algorithm has a complexity of $(T^*)^2$, as it is the number of steps needed to generate the variable $\bar{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 \ge 1, w_j(0) \ge 1-\ell\} $$

and with transition probabilities defined for all $j \ge 2$ and $i \ge j$ by

$$ P(j, j-1) = 1 - (1-p)^{j-1} \text{ and } P(j, i) = p(1-p)^{i-1} $$

where $p = \mathbb{P}(w_1(0) \ge 1-\ell)$, with

$$ P(1,0) = \mathbb{P}(w_1(0) \ge \ell), \quad \mathbb{P}(1,1) = \mathbb{P}(1-\ell \le w_1(0) < \ell), \quad P(1,j) = p(1-p)^{j-1} \text{ for } j \ge 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 10, 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 $\ell$ may have an important effect on the behavior of the average complexity $\mathbb{E}((T^*)^2)$ of the algorithm. We plotted $\ell \mapsto \mathbb{E}((T^*)^2)$ in Figure 11, when the charge distribution is given by $F(dx) = \mathbf{1}_{\{x \le 1\}}e^{-x}dx$. Additionally, as $p \to 0$, the quantity $\mathbb{E}((T^*)^2)$
<figure><img src="image_15.png" /><figcaption>Figure 11: Dependency in the parameter $\ell$ of the complexity of Algorithm 1 with a charge distribution $F(dx) = \mathbf{1}_{\{x \le 1\}}e^{-x-1}dx$. The figure was obtained with a Monte Carlo simulation of $N = 10^4$ copies of $T^*$ for 100 different values of $\ell$. For this charge distribution, the Monte Carlo simulations give $C(F) = 0.4432 \pm 0.0006$.</figcaption></figure>

grows to $\infty$. We estimated $\mathbb{E}((T^*)^2)$ for $F = p\delta_1 + (1-p)\delta_{-\infty}$ and plotted this quantity as a function of $p$ in Figure 12.

We observe in Figure 11 that different choices of the value $\ell$ can have a dramatic impact on the efficiency of Algorithm 1. Choosing a value $\ell$ too small has the effect of making the first appearance of a triangular event too late. On the other hand, if $\ell$ is too big then with high probability, one will have $w_1(T) \le \ell$, and thus the first “successful” triangular event will appear much later. For the distribution $F$ we chose, it appears that an optimal choice of $\ell$ seems to be around $\ell = 0.7$, which balances between these two extremes.

<figure><img src="image_16.png" /><figcaption>Figure 12: Dependency in the parameter $p$ of the complexity of Algorithm 1 applied to the detection of the longest path in the Barak-Erdős graph with parameter $p$. Figure obtained through Monte Carlo simulation of $N = 10^5$ copies of $T^*$ for 120 different values of $p$.</figcaption></figure>

We observe in Figure 12 that if $F$ puts a large mass on the negative half-line, the complexity of Algorithm 1 can become quite large. The function $p \mapsto \mathbb{E}(T^*)^2$ grows at least exponentially in $1/p$ as $p \to 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 $\bar{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 $\infty$, we use an idea by Glynn and Rhee [54]. Denote by $X_n$ the variable $\bar{m}(0)^+$ when $F = F_n$ has $n$ as the supremum of its support and note that $X_n \to X$ a.s. and in $L^1$ for some random variable $X$. Then $C(F_n) = \mathbb{E}X_n \to \mathbb{E}X = C(F)$, as $n \to \infty$. We may not be able to perfectly simulate $X$. However, if we let $\nu$ be a positive random integer such that $p_n = \mathbb{P}(\nu = n) > 0$ for all $n$ and set $Y = (X_\nu - X_{\nu-1})/p_\nu$ then $Y$ can be perfectly simulated. Moreover, $\mathbb{E}Y = C(F)$. This is because $\mathbb{E}Y = \sum_{n=1}^\infty p_n \mathbb{E}(Y|\nu = n) = \sum_{n=1}^\infty \mathbb{E}(X_n - X_{n-1}) = \lim_{n\to\infty} \mathbb{E}X_n = \mathbb{E}X$.

**Remark 10.9** For the special case of a Barak-Erdős graph, a simpler perfect simulation algorithm is explained in [44].
11 Additional remarks and open problems

The last passage percolation constant $C(p)$ for $\vec{G}(\mathbb{Z}, p)$ has been one of the main concerns in this survey. We showed how very good approximations can be obtained analytically by relating $\vec{G}(\mathbb{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 \to 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 CLTs 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 CLTs and this is the variance parameter. In, e.g., the case of $\vec{G}(\mathbb{Z}, p)$, we have that $(L_n - Cn)/\sqrt{\sigma^2\lambda n}$ converges in distribution to a standard normal with $\sigma^2$ being equal to the variance of $L_{\Gamma_1, \Gamma_2} - C(\Gamma_2 - \Gamma_2)$. This quantity is unknown and not even bounds are available. The situation becomes more complex in presence of weights.

CLTs are also available for the IBM and can take various forms. For example, for the IBM($p$) model, it has been shown that $\sqrt{n} (n^{-1} \sum_{k=0}^{[A_n t]} X_n(k) - t)$, $0 \le t \le 1$, converges in law to a Brownian motion if $A_n = nC$ and to a Brownian bridge if $A_n = L_n$. See [44, Thm. 9.2].

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 \le s \le t} (X(s) + Y(t) - Y(s))$ pops up for example in the case of the vertex set $\mathbb{Z} \times \{1, 2\}$. We know nothing about the random variable $S = S(t)$ that achieves this maximum. This is of interest as it would be related to the path that achieves the maximum.

Concerning longest paths of $\vec{G}(\mathbb{Z} \times \mathbb{Z}, p)$ on a window $[0, n] \times [0, m]$, as $n, m = m(n) \to \infty$, 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 $\vec{G}(\mathbb{Z}^d, p)$ case, when $d \ge 3$. It is not clear at all what kind of laws would replace the Tracy-Widom distribution here.

The recent paper of Terlat [94] makes progress in the behavior of $C(F)$ when $F$ is a distribution whose support may include negative numbers with a possible atom on $-\infty$. 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 [68]. 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. [45, eq. (13)].

Recall that $C(p, x)$ of Section 9, is the last passage percolation constant when the weight law is $p\delta_1 + (1-p)\delta_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 [41]. Can there be other ones?

If we replace $p\delta_1 + (1-p)\delta_x$ above by $F_{p,x} = pQ + (1-p)\delta_x$ where $Q$ is a probability measure on $(0, \infty)$ we expect that the behavior of $p \mapsto C(F_{p,x})$ can be obtained by techniques similar to those of [79, 80], so long as $\int y^2Q(dy) < \infty$. 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 \in \mathbb{X}_{\text{crit}}$. See [47, Sec. 5].

Acknowledgements

We thank the referees for their insightful suggestions that helped us improve the exposition.
References

[1] L. Addario-Berry and K. Ford. Poisson-Dirichlet branching random walks. *Ann. Appl. Probab.*, **23**, no. 1, 283–307, 2013.

[2] L. Addario-Berry and B. Reed. Minima in branching random walks. *Ann. Probab.*, **37**, no. 3, 1044–1079, 2009.

[3] Elie Aïdékon. Convergence in law of the minimum of a branching random walk. *Ann. Probab.*, **41**, no. 3A, 1362–1426, 2013.

[4] D. Aldous and J. Pitman. The asymptotic speed and shape of a particle system. In: *Probability Statistics and Analysis*, J. Kingman and G. Reuter, eds., 1–23. Cambridge University Press, 1983. London Math. Soc. Lecture Notes 79.

[5] D. Aldous and J. Michael Steele. The objective method: Probabilistic combinatorial optimization and local weak convergence. *Probability on Discrete Structures*, **110**, 1–72, 2004.

[6] N. Alon, B. Bollobás, G. Brightwell and S. Janson. Linear extensions of a random partial order. *Ann. Probab.*, **4**, 108–123, 1994.

[7] G.W. Anderson, A. Guionnet and O. Zeitouni. *An Introduction to Random Matrices*. Cambridge Univ. Press, Cambridge, 2010.

[8] G.E. Andrews. *The Theory of Partitions*. Addison-Wesley, 1976.

[9] F. Baccelli, A. Borovkov and J. Mairesse. Asymptotic results on infinite tandem queueing networks. *Probab. Th. Rel. F.*, **118**, no. 3, 365–405, 2000.

[10] A.B. Barak and P. Erdős. On the maximal number of strongly independent vertices in a random acyclic directed graph. *SIAM J. Algebr. Discr. Methods*, **5**, 508–514, 1984.

[11] Y. Baryshnikov. GUEs and queues. *Probab. Th. Rel. F.*, **119**, 256–274, 2001.

[12] Jean Bérard and Jean-Baptiste Gouéré. Brunet-Derrida behavior of branching-selection particle systems on the line. *Commun. Math. Phys.*, **298**, no. 2, 323–342, 2010.

[13] J. Berestycki, N. Berestycki and J. Schweinsberg. The genealogy of branching Brownian motion with absorption. *Ann. Probab.*, **41**, 527–618, 2013.

[14] Jean Bertoin, Aser Cortines, and Bastien Mallein. Branching-stable point measures and processes. *Adv. Appl. Probab.*, **50**, no. 4, 1294–1314, 2018.

[15] John D. Biggins. The first- and last-birth problems for a multitype age-dependent branching process. *Adv. Appl. Probab.*, **8**, 446–459, 1976.

[16] P. Billingsley. *Convergence of Probability Measures*. Wiley, New York, 1968.

[17] T. Bodineau and J. Martin. A universality property for last-passage percolation paths close to the axis. *Electron. Comm. Probab.* **10**, 105–112, 2005.

[18] B. Bollobás. Random graphs. Cambridge University Press, Cambridge, 2nd ed., 2001.

[19] A.A. Borovkov. Ergodicity and stability theorems for a class of stochastic equations and their applications. *Theory Probab. Appl.*, **23**, 227–258, 1978.

[20] A.A. Borovkov. *Asymptotic Methods in Queueing Theory*. Nauka, Moscow, 1980. (Revised English edition: Wiley, New York, 1984).

[21] A.A. Borovkov. *Ergodicity and Stability of Stochastic Processes*. Wiley, Chichester, 1998.

[22] A.A. Borovkov and S.G. Foss. Stochastically recursive sequences and their generalizations. *Sib. Adv. Math.*, **2**, no. 1, 16–81, 1992.
[23] A.A. Borovkov and S.G. Foss. Two ergodicity criteria for stochastically recursive sequences. *Acta Appl. Math.*, **34**, 125–134, 1994.

[24] Éric Brunet and Bernard Derrida. Shift in the velocity of a front due to a cutoff. *Physical Review E*, **56**, no. 3, 2597–2604, 1997.

[25] Éric Brunet, Bernard Derrida, Alfred H. Mueller and Stéphane Munier. Effect of selection on ancestry: an exactly soluble case and its phenomenological generalization. *Phys. Rev. E* (**3**) **76**, 2007.

[26] Constantin Carathéodory. Über den Wiederkehrsatz von Poincaré. *Berl. Ber.* 1919, 580–584 (1919).

[27] Xinxin Chen. Scaling limit of the path leading to the leftmost particle in a branching random walk. *Theory Probab. Appl.*, **59**, no. 4, 567–589, 2015.

[28] Ksenia Chernysh and Sanjay Ramassamy. Coupling any number of balls in the infinite bin model. *J. Appl. Probab.*, **54**, no. 2, 540–549, 2017.

[29] J.E. Cohen, F. Briand and C.M. Newman. Community Food Webs: Data and Theory. Springer-Verlag, New York. 1990.

[30] J.E. Cohen and C.M. Newman. Community area and food chain length: theoretical predictions. *Amer. Naturalist*, **138**, 1542–1554, 1991.

[31] Comets, F., Fernández, R., and Ferrari, P.A. Processes with long memory: regenerative construction and perfect simulation. *Ann. Appl. Probab.* **12**, 921–943, 2002.

[32] Pierre-Antoine Corre. Oscillations in the height of the Yule tree and application to the binary search tree. *Random Str. Algorithms*, **51**, no. 1, 90–120, 2017.

[33] Cortines, Aser and Mallein, Bastien. A *N*-branching random walk with random selection. *ALEA Lat. Am. J. Probab. Math. Stat.*, **14**, 117–137, 2017.

[34] Curien, Nicolas. Erdős-Rényi Poissonized. *C. R. Math. Acad. Sci. Paris*, **362**, 649–656, 2024.

[35] D. Dauvergne, J. Ortmann and B. Virág. The directed landscape. *Acta Math.* **229**, no. 2, 201–285, 2022.

[36] D. Dauvergne, B. Virág. The directed landscape from Brownian motion. arXiv:2405.00194, 2024.

[37] B.A. Davey and H.A. Piestley. *Introduction to Lattices and Order*. Cambridge University Press, Cambridge, 1990.

[38] Anna De Masi, Pablo A. Ferrari, Errico Presutti and Nahuel Soprano-Loto. Hydrodynamics of the *N*-BBM process. *Stochastic dynamics out of equilibrium*. Springer Proc. Math. Stat. **282**, 523–549, 2019.

[39] Denisov, D., Foss, S., and Konstantopoulos, T. Limit theorems for a random directed slab graph. *Ann. Appl. Probab.*, **22**, 702–733, 2012.

[40] D Durrett, Rick and Remenik, Daniel. Brunet-Derrida particle systems, free boundary problems and Wiener-Hopf equations. *Ann. Probab.* **39**, 2043–2078, 2011.

[41] Kunal Dutta. On limit constants in last passage percolation in transitive tournaments. arXiv:2005.09922, 2018.

[42] R.A. Fisher. The wave of advance of advantageous genes. *Ann. Eugen.*, **7**, 353–369, 1937.

[43] Foss, S. On ergodicity conditions in multi-server queues. *Sib. Math. J.* **34**, no. 6, 168–175, 1983.
[44] Foss, S. and Konstantopoulos, T. Extended renovation theory and limit theorems for stochastic ordered graphs. *Markov Proc. Rel. F.*, **9**, no. 3, 413–468, 2003.

[45] Foss, S. and Konstantopoulos, T. Limiting Properties of Random Graph Models with Vertex and Edge Weights. *J. Stat. Phys.*, **173**, 626–643, 2018.

[46] S. Foss, T. Konstantopoulos, B. Mallein, S. Ramassamy. Estimation of the last passage percolation constant in a charged complete directed acyclic graph via perfect simulation. *ALEA Lat. Am. J. Probab. Math. Stat.*, **20**, 547–560, 2023.

[47] S. Foss, T. Konstantopoulos, A. Pyatkin. Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph. *Ann. Appl. Probab.*, **33**, no. 2, 931–953, 2023.

[48] Foss, S. and Tweedie, R.L. Perfect simulation and backward coupling. *Stoch. Models*, **14**, nos. 1–2, 187–203, 1998.

[49] Foss, S., Martin, J., and Schmitt. P. Long-range last-passage percolation on the line. *Ann. App. Probab.*, **24**, no. 1, 198–234, 2014.

[50] S. Foss and S. Zachary. Stochastic sequences with a regenerative structure that may depend both on the future and on the past. *Adv. Appl. Probab.*, **45**, no. 4, 1083–1110, 2013.

[51] F. Franklin. Sur le développement du produit infini $(1-x)(1-x^2)(1-x^3)\dots$. *Comptes Rendus*, **82**, 448–450, 1881.

[52] Gabrysch (née Trinajstić), Katja. Convergence of directed random graphs to the Poisson-weighted infinite tree. *J. Appl. Probab.*, **53**, 463–474, 2016.

[53] Gelenbe, E., Nelson, R., Philips, T. and Tantawi, A. (1986). An approximation of the processing time for a random graph model of parallel computation. *In: Proceedings of 1986 ACM Fall Joint Computer Conference*, ACM86, 691–697, 1986. IEEE Computer Society Press, Los Alamitos, CA.

[54] P.W. Glynn and C-H Rhee. Exact estimation for markov chain equilibrium. *J. Appl. Probab.*, **51A**, 377–389, 2014

[55] P.W. Glynn and W. Whitt. Departures from many queues in series. *Ann. Appl. Probab.*, **1**, 546–572, 1991.

[56] J. Gravner, C.A. Tracy, and H. Widom. Limit theorems for height fluctuations in a class of discrete space and time growth models. *J. Stat. Phys.*, **102**, 1085–1132, 2001.

[57] Ben Hambly and James B. Martin. Heavy tails in last-passage percolation. *Probab. Th. Rel. F.*, **137**, no. 2, 227–275, 2007.

[58] J. M. Hammersley. Postulates for subadditive processes. *Ann. Probab.*, **2**, 652–680, 1974.

[59] Yueyun Hu and Zhan Shi. Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees. *Ann. Probab.*, **37**, no. 2, 742–789, 2009.

[60] Isopi, M. and Newman, C.M. Speed of parallel processing for random task graphs. *Comm. Pure and Appl. Math*, **47**, 261–276, 1994.

[61] Itoh, Yoshiaki. Continuum Cascade Model: Branching Random Walk for Traveling Wave, 2018. https://arxiv.org/pdf/1507.04379v1.pdf

[62] Itoh, Y. and Krapivsky, P.L. Continuum cascade model of directed random graphs: traveling wave analysis. *J. Phys. A*, no. 45, 455002, 10 pp., 2012.

[63] K. Johansson. Shape fluctuations and random matrices. *Comm. Math. Phys.*, **209**, no. 2, 437–476, 2000.
[64] Wilfrid Kendall. Notes on perfect simulation. In: *Markov chain Monte Carlo*, volume 7 of *Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap.*, pp. 93–146. World Sci. Publ., Hackensack, NJ, 2005.

[65] J. F. C. Kingman. Subadditive ergodic theory. *Ann. Probab.*, **1**, 883–909, 1973.

[66] J. F. C. Kingman. The first birth problem for an age-dependent branching process. *Ann. Probab.*, **3**, 790–801, 1975.

[67] A.N. Kolmogorov, I.G. Petrovskii and N.S. Piskunov. Étude de l'équation de la diffusion avec croissance de la quantité de la matière et son application à un problème biologique. *Moscow Univ. Bull. Math.* **1**, 1–25, 1937. Translated as "studies of the diffusion with the increasing quantity of the substance; its application to a biological problem", in I.G. Petrowsky, Selected Works, Part II: Differential Equations and Probability Theory, 106–132, CRC Press, 1996.

[68] T. Konstantopoulos, A.V. Logachov, A.A. Mogulskii and S. Foss. Limit theorems for the maximal path weight in a directed graph on the line with random weights of edges. *Probl. Inf. Transm.*, **57**, no. 2, 161–177, 2021.

[69] T. Konstantopoulos and M. Zazanis. A discrete-time proof of Neveu's exchange formula. *J. Appl. Probab.*, **32**, 917–921, 1995.

[70] János Komlós, Peter Major and Gábor Tusnády. An approximation of partial sums of independent rv's and the sample df. I. *Wahr. verw. Geb.*, **32**, 111–131, 1976.

[71] J. Komlós, P. Major, and Tusnády G. An approximation of partial sums of independent rv's and the sample df. II. *Z. Wahrsch. und Verw. Gebiete*, **34**, 33–58, 1976.

[72] Konstantopoulos, T. and Trinajstić, K. Convergence to the Tracy-Widom distribution for longest paths in a directed random graph. *ALEA, Lat. Am. J. Probab. Math. Stat.* **10**, no. 2, 711–730, 2013.

[73] T.M. Liggett. *Interacting Particle Systems*. Springer, 1985.

[74] T. Lindvall. *Lectures on the Coupling Method*. Wiley, New York, 1992.

[75] Lothaire, M. *Algebraic Combinatorics on Words*. Cambridge University Press, Cambridge, 2002.

[76] Maillard, Pascal. Speed and fluctuations of N-particle branching Brownian motion with spatial selection. *Probab. Th. Rel. F.*, **166**, 1061–1173, 2016.

[77] Bastien Mallein. Branching random walk with selection at critical rate. *Bernoulli*, **23**, no. 3, 1784–1821, 2017.

[78] Bastien Mallein. N-branching random walk with $\alpha$-stable spine. *Theory Probab. Appl.*, **62**, no. 2, 295–318, 2018.

[79] Mallein, B. and Ramassamy, S. Barak-Erdős graphs and the infinite bin model. *Ann. Inst. H. Poincaré*, **57**, no. 4, 1940–1967, 2021.

[80] Mallein, B. and Ramassamy, S. Two-sided infinite bin models and analyticity for Barak-Erdős graphs. *Bernoulli*, **25**, no. 4B, 3479–3495, 2019.

[81] Mallein, B. and Tesemnikov, P. On the length of the shortest path in a sparse Barak-Erdős graph. *Stat. Probab. Lett.*, **190**, no. 5, 0167-7152, 2022.

[82] J.B. Martin. Last-passage percolation with general weight distribution. *Markov Proc. Rel. F.*, **12**, 273–299, 2006.

[83] H.P. McKean. Application of Brownian motion to the equation of Kolmogorov-Petrovskii-Piskunov. *Comm. Pure Appl. Math.*, **28**, 323–331, 1975.
[84] M. Mehta. *Random matrices*, volume 142 of *Pure and Applied Mathematics*. Elsevier/Academic Press, Amsterdam, 3d edition, 2004.

[85] C. Mueller, L. Mytnik and J. Quastel. Effect of noise on front propagation in reaction-diffusion equations of KPP type. *Invent. Math.*, **184**, 405–453, 2011.

[86] Newman, C.M. Chain lengths in certain random directed graphs. *Random Str. Algorithms*, **3**, no. 3, 243–253, 1992.

[87] Newman, C.M. and Cohen,J.E. (1986). A stochastic theory of community food webs: IV; theory of food chains in large webs. *Proc. R. Soc. London Ser. B*, **228**, 355–377, 1986.

[88] N. O'Connell and M. Yor. A representation for non-colliding random walks. *Electron. Comm. Probab.*, **7**, 1–12, 2002.

[89] G. Pólya and G. Szegő. *Problems and Theorems in Analysis I*. Springer-Verlag, Grundl. Math. Wiss. Vol. 193, Heidelberg, 1978.

[90] Propp, J.G. and Wilson, D.B. Exact sampling with coupled Markov chains and applications to statistical mechanics. *Random Str. Algorithms* **9**, 223–252, 1996.

[91] R.T. Rockafellar. Convex Analysis. Princeton Univ. Press, Princeton, 1970.

[92] NJA Sloane. The online encyclopedia of integer sequences. *Published electronically at http://oeis.org*, 2021.

[93] Steele, J.M. and Zhang, Y. Nondifferentiability of the time constants of first-passage percolation. *Ann. Probab.*, **31**, no. 2, 1028-1051, 2003.

[94] B. Terlat. Regularity of the time constant for last passage percolation on complete directed acyclic graphs. arXiv:2303.11927, 2023.

[95] B. Terlat. Last passage percolation on complete directed acyclic graphs. PhD thesis, in preparation.

[96] C.A. Tracy and H. Widom. Fredholm determinants, differential equations and matrix models. *Comm. Math. Physics*, **163**, 33–72, 1994.

[97] Kohei Uchiyama. Spatial growth of a branching process of particles living in $\mathbb{R}^n$. *Ann. Probab.*, **10**, 896–918, 1982.

[98] Remco Van der Hofstad. *Random Graphs and Complex Networks*, Vol. 1. Cambridge Univ. Press, 2017.