# Fluid limit and gelation in the frozen Erdős-Rényi random graph

Bénédicte Haas, Vincent Viau

► To cite this version:

Bénédicte Haas, Vincent Viau. Fluid limit and gelation in the frozen Erdős-Rényi random graph. 2025. hal-05514333

HAL Id: hal-05514333

https://hal.science/hal-05514333v1

Preprint submitted on 25 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Fluid limit and gelation in the frozen Erdős-Rényi random graph

Bénédicte Haas * & Vincent Viau †

## Abstract

The frozen Erdős-Rényi random graph is a variant of the standard dynamical Erdős-Rényi random graph that prevents the creation of the giant component by freezing the evolution of connected components with a unique cycle. The formation of multicyclic components is forbidden, and the growth of components with a unique cycle is slowed down, depending on a parameter $p \in [0, 1]$ that quantifies the slowdown. At the time when all connected components of the graph have a (necessary unique) cycle, the graph is entirely frozen and the process stops. In this paper we study the fluid limit of the main statistics of this process, that is their functional convergence as the number of vertices of the graph becomes large and after a proper rescaling, to the solution of a system of differential equations. Our proofs are based on an adaption of Wormald's differential equation method. We also obtain, as a main application, a precise description of the asymptotic behavior of the first time when the graph is entirely frozen.

## Contents

<table><tr><td><b>1 Introduction and main results</b></td><td><b>3</b></td></tr><tr><td>1.1 Fluid limit of the gel</td><td>6</td></tr><tr><td>1.2 Fluid limit of the forest</td><td>9</td></tr><tr><td>1.3 Total gelation time and vicinity</td><td>11</td></tr><tr><td>1.4 Organization of the paper</td><td>13</td></tr><tr><td><b>2 Frozen Erdős-Rényi and uniform random forests</b></td><td><b>13</b></td></tr><tr><td>2.1 Background on uniform random forests</td><td>15</td></tr></table>

<footnote>* Université Sorbonne Paris Nord, LAGA, CNRS (UMR 7539) 93430 Villetaneuse, France
E-mail: haas@math.univ-paris13.fr</footnote>

<footnote>† Université Sorbonne Paris Nord, LAGA, CNRS (UMR 7539) 93430 Villetaneuse, France
E-mail: viau@math.univ-paris13.fr</footnote>
<table>
  <tbody>
    <tr>
      <td>2.2</td>
      <td>Asymptotics of expected conditional jumps</td>
      <td>16</td>
    </tr>
    <tr>
      <td>2.3</td>
      <td>Estimates on the jumps of G<sub>p,n</sub></td>
      <td>18</td>
    </tr>
    <tr>
      <td><b>3</b></td>
      <td><b>Properties of the fluid limit functions</b></td>
      <td><b>21</b></td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>The functions g<sub>p</sub>, d<sub>p</sub>, v<sub>p</sub>, e<sub>p</sub> and r<sub>p</sub></td>
      <td>22</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>Approximation</td>
      <td>24</td>
    </tr>
    <tr>
      <td>3.3</td>
      <td>The functions t<sub>p,k</sub></td>
      <td>27</td>
    </tr>
    <tr>
      <td><b>4</b></td>
      <td><b>Convergence to the fluid limit</b></td>
      <td><b>28</b></td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Preliminaries</td>
      <td>28</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>The gel just beyond the critical window</td>
      <td>31</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Differential equation method for the process beyond time (1/2 + ε)n</td>
      <td>37</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Proof of Theorem 1.2.</td>
      <td>44</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Proof of Theorem 1.6.</td>
      <td>46</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Largest and typical trees.</td>
      <td>48</td>
    </tr>
    <tr>
      <td><b>5</b></td>
      <td><b>A continuous version of the model</b></td>
      <td><b>49</b></td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Poissonization.</td>
      <td>49</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>Fluid limit in the continuous model.</td>
      <td>50</td>
    </tr>
    <tr>
      <td><b>6</b></td>
      <td><b>Total gelation time and vicinity</b></td>
      <td><b>52</b></td>
    </tr>
    <tr>
      <td>6.1</td>
      <td>On the number of trees of size k</td>
      <td>52</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>Asymptotics of A<sub>p,n</sub><sup>(k)</sup>, A<sub>p,n</sub><sup>(k+)</sup></td>
      <td>60</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>De-Poissonization.</td>
      <td>65</td>
    </tr>
    <tr>
      <td><b>7</b></td>
      <td><b>Concluding remarks and open questions</b></td>
      <td><b>66</b></td>
    </tr>
    <tr>
      <td colspan="2"><b>Acknowledgements</b></td>
      <td><b>67</b></td>
    </tr>
    <tr>
      <td colspan="2"><b>A Appendix</b></td>
      <td><b>67</b></td>
    </tr>
    <tr>
      <td>A.1</td>
      <td>The Borel-Tanner distribution.</td>
      <td>67</td>
    </tr>
  </tbody>
</table>
the current graph. Throughout the paper we will denote by $(ER_n(m), m \in \mathbb{Z}_+)$ a version of this standard model. We emphasize that various other variants of this standard model with different constraints preventing the formation of components, or destroying components, have been studied, see for example [9, 20, 27, 28] and the references therein, or [3, 6] for other models of frozen graphs.

Returning to the frozen model, the *forest part* of $F_{p,n}(m)$ is its subgraph corresponding to the set of trees. The *gel* of $F_{p,n}(m)$ is the set of all frozen vertices, that is the set of all vertices involved in a unicycle. A vertex of $F_{p,n}(m)$ is thus either in the *forest* or in the *gel*. We will call *total gelation time* the first time when all vertices are frozen: from this time the graph is completely frozen, i.e. it no longer evolves.

This paper addresses two main questions, namely 1) the existence of a *fluid limit*, or *law of large numbers*, for several statistics of the *p*-frozen model $F_{p,n}$, such as its number of frozen vertices, discarded edges, trees of a given size, etc., and 2) the asymptotic behavior of its total gelation time as well as the distribution and extinction of the number of trees of a given size in the neighborhood of the gelation time. In general, the *size* of a connected component refers to its number of vertices.

These questions have natural counterparts in the standard Erdős-Rényi graph, respectively the fluid limit for the size of the largest component and the time needed for the graph to be connected. Both questions have been deeply studied and it is well-known since the initial works of Erdős and Rényi [14, 15] that the size of the largest component in a graph with $n$ vertices exhibits a phase transition when the number of edges approaches $n/2$. This can be resumed as follows: the largest components of $ER_n(m)$ are of order $\ln(n)$ when $m/n \sim t < 1/2$ (subcritical regime), of order $n^{2/3}$ when $m/n \sim 1/2$ (critical regime) and there is a unique, giant, component of order $n$ when $m/n \sim t > 1/2$ (supercritical regime), the others being of order at most $\ln(n)$. Among their numerous results, Erdős and Rényi displayed the expression of the fluid limit of the size of the giant component in the supercritical regime, and proved that it is determined by the unique non-null function $g_{ER}$ verifying the following equation

$$g_{ER}(t) = 1 - e^{-2t g_{ER}(t)}, \quad t > 1/2.$$

Since then, the phase transition has been studied extensively. We refer e.g. to [24] for a study of the subcritical regime, to [2, 17, 21] for the critical regime and the emergence of the giant component, and to [5, 25, 26, 30] for the supercritical regime and especially for results on the fluctuations around the fluid limit. For an overview on Erdős-Rényi random graph, one could also refer to the books [4, 8, 32] which also address the connectedness of the graph. This last issue has been initially raised by Erdős and Rényi [14] and mostly investigated in the early papers on the subject [14, 15, 30]. Erdős and Rényi proved that the time needed for the graph to be connected, say $A_{ER,n}$, coincides in the limit with the vanishing time of isolated vertices, which enabled them to show that

$$\frac{A_{ER,n}}{n} - \frac{\ln(n)}{2} \underset{n \to \infty}{\stackrel{(d)}{\longrightarrow}} \frac{\text{Gu}}{2}, \qquad (1.1)$$

where Gu denotes a standard Gumbel distribution, $\mathbb{P}(\text{Gu} \le x) = e^{-e^{-x}}, x \in \mathbb{R}$.
For the frozen model $F_{p,n}$ a similar phase transition at $m/n \sim 1/2$ has been demonstrated in [12] for $p = 1/2$ and generalized in [34] for all $p \in [0, 1]$. This will be recalled later in more detail. The aim of this paper is to understand the effect of the gelation, and the induced slowdowns, in relation to the standard Erdős-Rényi graph, essentially in the supercritical regime when $m \gg n/2$.

**Remarks.** 1) In the frozen model, when $p = 1$, the tree components are systematically added to the gel when the selected edge connects to the gel. There is then an obvious coupling with the standard Erdős-Rényi model so that the forest part of the frozen model coincides with that of the standard Erdős-Rényi (and the gel coincides with the set of vertices in components with at least one cycle, namely the *cyclic components*, in the standard Erdős-Rényi). So, several results that we will state below retrieve similar results on the standard Erdős-Rényi.

2) In contrast, the tree components of the frozen model when $p = 0$ are never added to the gel when the selected edge connects to the gel.

3) Although there is no obvious monotonicity of the gel size in the parameter $p \in [0, 1]$, there is also an obvious coupling, for each $p$, so that the gel of the $p$-frozen model is included in the set of vertices in cyclic components of the standard Erdős-Rényi model: the gel process in $F_{1,n}$ is thus stochastically larger than the gel process in $F_{p,n}$, whatever $p \in [0, 1]$.

We present our main results in the three forthcoming subsections, focussing in this paper on the case

$$p \in (0, 1].$$

This is implicit in all statements. The case $p = 0$, where unicycles become unattractive as soon as they are created, shows partially different behavior and requires an adapted approach, although several of our intermediate steps for the implementation of the main results are still valid for $p = 0$. We discuss the expected results and open questions on this case in Section 7.

**Notation.** We will use the following notation throughout the paper, for $m \in \mathbb{Z}_+$:

- $G_{p,n}(m)$ is the size of the gel at time $m$, that is the number of frozen vertices

- $D_{p,n}(m)$ is the number of discarded edges at time $m$

- $V_{p,n}(m)$ is the number of vertices in the forest part of $F_{p,n}(m)$

- $E_{p,n}(m)$ is the number of edges in the forest part of $F_{p,n}(m)$

- $N_{p,n}^{(k)}(m)$ is the number of trees of size $k$ in $F_{p,n}(m)$, $k \in \mathbb{N}$.

Note the following obvious relations, which we will regularly use to pass from one quantity to the other,

$$V_{p,n}(m) + G_{p,n}(m) = n \quad \text{and} \quad E_{p,n}(m) + G_{p,n}(m) + D_{p,n}(m) = m. \qquad (1.2)$$
Of course, for $n$ fixed, the processes $G_{p,n}$ and $D_{p,n}$ are non-decreasing. Note also the trivial bound $G_{p,n}(m) \le \min(m, n)$.

**Remark.** As usual in dynamical random graph models, it may be easier in some situations to work with a continuous version of the model. In Section 5 we introduce a Poissonized counterpart of $F_{p,n}$. This will be useful for studying the total gelation time. In this introduction the main results are stated on the discrete model, their continuous counterparts will be given in the core of the paper.

**Remark.** Krapivsky’s paper [19] has related interests and was published in the physics literature while we were working on this project. He obtained, via a more intuitive approach, the expression and some properties of the fluid limits of the gel, of the number of trees of size $k \ge 1$ and of the average number of unicycles of size $k \ge 1$, by identifying the differential equations there are solutions to. He also develops heuristics for the total gelation time. Our paper confirms and completes his predictions.

## 1.1 Fluid limit of the gel

We start by defining the function that will describe the fluid limit of the gel (size) $G_{p,n}$. An equivalent definition, as a solution to a differential equation, is given in Section 3.

**Definition 1.1.** We call gel mass function the function $g_p : [0, \infty) \to [0, 1)$ which is null on $[0, 1/2]$ and defined on $[1/2, \infty)$ as the inverse of the function $f_p : [0, 1) \to [1/2, \infty)$ given for $t \in [0, 1)$ by

$$f_p(t) = \frac{1}{2} + \frac{t}{2p} \int_0^1 \frac{u_p^{\frac{1}{p}}}{1 - tu} du = \frac{1}{2} \sum_{n=0}^{\infty} \frac{t^n}{1 + pn}.$$

Note that $f_p$ is decreasing in $p$ and so $g_p$ is increasing in $p$. This monotonicity was a priori not obvious since there is no stochastic monotonicity in $p \mapsto G_{p,n}(m)$. However, as already observed, the gel size $G_{p,n}(m)$ is stochastically smaller (whatever $p$) than the total number of vertices involved in cyclic components at time $m$ of the standard Erdős-Rényi graph, which is distributed as $G_{1,n}(m)$. So the bound $g_p \le g_1$ was predictable.

We will work in detail on the function $g_p$ in Section 3, but already emphasize here that $g_p$ is infinitely differentiable on $(1/2, \infty)$, $g_p(1/2) = 0$, $g'_p(1/2^+) = 2(1 + p)$ and $g_p(t) = 1 - e^{-2pt} + o(e^{-2pt})$ as $t \to \infty$. When $p = 1$, the inverse function $f_1$ is particularly simple

$$f_1(s) = \frac{-\ln(1-s)}{2s}, \quad s \in [0, 1),$$

and we see that the gel mass function $g_1$ is indeed equal to the fluid limit $g_{ER}$ of the giant component in the classical Erdős-Rényi random graph.
We introduce simultaneously the function $d_p : [0, \infty) \to [0, 1)$ defined by

$$d_p(t) = t - g_p(t) - t(1 - g_p(t))^2. \qquad (1.3)$$

Note that $d_p(t) = 0$ for $t \in [0, 1/2]$, $d_p(1/2^+) = 0$ and $d_p(t) \sim t - 1 + O(e^{-2pt})$ when $t \to \infty$.

Our main result expresses the scaling limit of the processes $G_{p,n}$ and $D_{p,n}$ in terms of these deterministic functions. All other results of the paper rely on this one.

**Theorem 1.2.** As $n \to \infty$, for the topology of uniform convergence on compacts,

$$\left( \left( \frac{G_{p,n}(\lfloor nt \rfloor)}{n}, \frac{D_{p,n}(\lfloor nt \rfloor)}{n} \right), t \ge 0 \right) \xrightarrow{\mathbb{P}} \left( (g_p(t), d_p(t)), t \ge 0 \right).$$

<figure><img src="image_2.png" /><figcaption>(a) The functions $g_1$ (blue) and $g_{1/2}$ (red)</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) The functions $d_1$ (blue) and $d_{1/2}$ (red)</figcaption></figure>

**Remark.** When $t < 1/2$, the limits $g_p(t)$ and $d_p(t)$ are null. The phase transition at $t = 1/2$ for the frozen model $F_{p,n}$ was revealed by Contat and Curien [12] (generalized in [34] for $p \neq 1/2$). They proved that, as for the Erdős-Rényi graph, the sizes of the connected components of the frozen model behave in $n^{2/3}$ when $m$ is of order $n/2$, as well as the size of the gel, and more precisely that appropriately rescaled in the critical window $\lfloor n/2 + \lambda n^{2/3} \rfloor$, $\lambda \in \mathbb{R}$, the connected components converge, as a process in the variable $\lambda$, to a frozen multiplicative coalescent, generalizing thus the well-known result of Aldous [2] for the standard Erdős-Rényi model. This is completed by the paper [33], which studies the behavior of the gel at the exit of the critical window. Theorem 1.2 therefore completes these results by describing the asymptotics in the supercritical regime $t > 1/2$. Note that for $p = 1$, it gives the functional convergence of the rescaled number of vertices in cyclic components of the standard Erdős-Rényi graph towards the function $g_{ER}$.

**A word on the proof.** The approximation of trajectories of random processes by solutions to differential equations has been deeply studied. See e.g. Darling and Norris's survey [13] for background and references. The proof of Theorem 1.2 is based on the so-called differential equation method as
developed by Wormald [36, 37] for discrete-time processes (notably related to combinatorial structures) whose jumps are not too big and well approximated by sufficiently smooth functions. The implementation of this method will not be trivial here because the differential equations involving the limit functions $g_p$ and $d_p$ (see $(E_{(0)}), (\tilde{E}_{(0)})$ in Section 3) are not smooth enough around the critical time $t = 1/2$ to apply the method as is. Bypassing this flaw will require a detailed technical work based on approximations of the differential equations, which will be undertaken in Section 4. We also emphasize that to obtain the fluid limit of $G_{p,n}$ via this approach, we really need to consider the two-dimensional process $(G_{p,n}, D_{p,n})$ and apply the method to this bivariate process. The reason is that the expectation of the jump of $G_{p,n}$ at time $m$ given the past of the process $(G_{p,n}, D_{p,n})$ until then depends both on (and only on) $G_{p,n}(m)$ and $D_{p,n}(m)$.

At the heart of our approach there is a useful connection between the frozen Erdős-Rényi model and uniform random forests: conditionally on its number of vertices and edges at a given time, the forest part of the frozen model is a uniform random forest. This was highlighted by Contat and Curien [12] in the case $p = 1/2$, generalized without difficulty in [34] to any $p \in [0, 1]$, and called the free forest property. Let us state it formally and denote, for $N \in \mathbb{N}$ and $M \in \mathbb{Z}_+$, by $W(N, M)$ the set of unrooted unordered forests with $N$ labeled vertices $\{1, \dots, N\}$ and $M$ edges (hence $N - M$ trees).

**Proposition 1.3** (Free forest property, [12],[34]). For any $n \in \mathbb{N}, m \in \mathbb{Z}_+$, conditionally on $G_{p,n}(m)$ and $D_{p,n}(m)$, the forest part of $F_{p,n}(m)$ is uniformly distributed over $W(V_{p,n}(m), E_{p,n}(m))$ when $V_{p,n}(m) \ge 1$.

This property will be crucial at different steps of our study.

**Further results.** To complete the results of Theorem 1.2 and those of [12] and [34] in the critical window, we note that when $t < 1/2$, the gel $G_{p,n}(\lfloor nt \rfloor)$ is bounded in probability:

**Proposition 1.4.** For all $t < 1/2$, $G_{p,n}(\lfloor nt \rfloor) = O_{\mathbb{P}}(1)$.

Indeed, as previously mentioned, $G_{p,n}(\lfloor nt \rfloor)$ is stochastically smaller than the total number of vertices involved in cyclic components at time $\lfloor nt \rfloor$ of the standard Erdős-Rényi random graph, and it is known that for $t < 1/2$ this number converges in distribution as $n \to \infty$ (see e.g. Theorem 5 of [24]; in fact this theorem states the convergence in distribution of the total number of vertices involved in unicycles, but jointly with the well-known fact that at time $t < 1/2$ the number of vertices which are not involved in trees or unicycles converges in probability to 0, this gives the result).

Let us also emphasize the following corollary of Theorem 1.2, which identifies the asymptotic distribution of the first time a which a given vertex is frozen. It follows from the fact that the probability that a given vertex is frozen at time $\lfloor nt \rfloor$ is equal, by exchangeability, to $\mathbb{E}[G_{p,n}(\lfloor nt \rfloor)]/n$.

**Corollary 1.5.** Let $\tau_{p,n}^*$ be the time at which the vertex 1 is frozen in the p-frozen model, $p \in (0, 1]$. Then,

$$ \frac{\tau_{p,n}^*}{n} \xrightarrow{n \to \infty} \mathbf{X}_p, $$
where $X_p$ is a random variable with cumulative distribution function $g_p$.

Other consequences of Theorem 1.2 are developed in the next two sections.

## 1.2 Fluid limit of the forest

With the relations (1.2), the asymptotics of the number of vertices $V_{p,n}$ and edges $E_{p,n}$ of the forest part of the graph $F_{p,n}$ follow directly from Theorem 1.2, as well as that of the ratio

$$R_{p,n}(m) := \frac{E_{p,n}(m)}{V_{p,n}(m)}, \quad m \in \mathbb{Z}_{+},$$

where we use the convention $0/0 = 0$. Recalling the free forest property of Proposition 1.3, this ratio is a major source of information since there is also a phase transition for uniform random forests depending on the position of the ratio relative to 1/2, see Britikov [11] and Luczak-Pittel [22] (their results are summarized in Section 2). This point will e.g. lead to the forthcoming Corollary 1.7.

We complete these asymptotics with the behavior of the number of trees of a given size. In that aim, consider the functions $t_{p,k} : [0, \infty) \to [0, 1)$, $k \in \mathbb{N}$, defined for $t \ge 0$ by

$$t_{p,k}(t) = \frac{k^{k-2}}{k!} (2t)^{k-1} (1-g_p(t))^k e^{-2kt(1-g_p(t))}. \quad (1.4)$$

We emphasize that for each fixed $t \ge 0$, the weights

$$\frac{k \cdot t_{p,k}(t)}{1 - g_p(t)}, \quad k \ge 1$$

are those of a Borel distribution of parameter $2t(1 - g_p(t)) \in [0, 1]$, see the Appendix A.1 for background. Such a distribution is, among other things, the distribution of the total progeny of a subcritical Galton-Watson tree with Poisson offspring distribution with mean $2t(1 - g_p(t))$. Based on Theorem 1.2, we obtain:

**Theorem 1.6.** As $n \to \infty$, for the topology of uniform convergence on compacts,

$$\left( \left( \frac{V_{p,n}(\lfloor nt \rfloor)}{n}, \frac{E_{p,n}(\lfloor nt \rfloor)}{n}, R_{p,n}(\lfloor nt \rfloor) \right), t \ge 0 \right) \xrightarrow{\mathbb{P}} \left( (v_p(t), e_p(t), r_p(t)), t \ge 0 \right)$$

where

$$v_p(t) = 1 - g_p(t); \quad e_p(t) = t(1 - g_p(t))^2; \quad r_p(t) = t(1 - g_p(t)).$$

Moreover,

$$\left( \left( \frac{k \cdot N_{p,n}^{(k)}(\lfloor nt \rfloor)}{n} \right)_{k \ge 1}, t \ge 0 \right) \xrightarrow{\mathbb{P}} \left( (k \cdot t_{p,k}(t))_{k \ge 1}, t \ge 0 \right)$$

for the usual norm $\|x\|_1 := \sum_{k \ge 1} |x_k|$ on $\ell^1$, the space of summable sequences.
<figure><img src="image_4.png" /></figure>

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

Some properties of the functions $v_p, e_p, r_p$ and $t_{p,k}$ will be highlighted in Section 3, in connection with the functions $g_p$ and $d_p$. For example, their right-derivative at $t = 1/2$ are respectively $e'_p(1/2^+) = -1 - 2p$ and $r'_p(1/2^+) = -p$. We will also see that the ratio $r_p$ is increasing on $(0, 1/2]$, decreasing on $[1/2, 1)$, with a maximum equals to $1/2$ reached at $t = 1/2$ (whatever $p \in (0, 1]$). In particular,

$$r_p(t) < 1/2 \quad \text{for } t \neq 1/2.$$

This means that for $t \neq 1/2$ the forest part of the graph $F_{p,n}$ is in a subcritical regime. For $p = 1$, this is related to the facts that the complement of the giant in the standard Erdős-Rényi graph behaves as a standard Erdős-Rényi graph conditioned to have connected components smaller than the initial giant, and that $t(1 - g_{ER}(t)) < 1/2$ for $t \neq 1/2$. For general $p \in (0, 1]$, this subcriticality leads to:

**Corollary 1.7 (Largest trees).** Let $\#T_{p,n}^{(i)}(m)$ be the size of the $i$-th largest tree in $F_{p,n}(m)$. Then for all $i \in \mathbb{N}$:

1) When $t < 1/2$,

$$\frac{\#T_{p,n}^{(i)}(\lfloor nt \rfloor)}{\ln(n)} \xrightarrow[n \to \infty]{\mathbb{P}} \frac{1}{2t - 1 - \ln(2t)}.$$

2) When $t > 1/2$,

$$\frac{\#T_{p,n}^{(i)}(\lfloor nt \rfloor)}{\ln(n)} \xrightarrow[n \to \infty]{\mathbb{P}} \frac{1}{2t(1 - g_p(t)) - 1 - \ln(2t(1 - g_p(t)))}.$$

Informally, we have therefore, for large $n$,

$$\#T_{p,n}^{(i)}(\lfloor nt \rfloor) \underset{t \to 0}{\approx} \frac{\ln(n)}{|\ln(t)|}, \quad \text{while} \quad \#T_{p,n}^{(i)}(\lfloor nt \rfloor) \underset{t \to \infty}{\approx} \frac{\ln(n)}{2pt}.$$
**Remark.** To complete the above corollary, let us state the results of [12] and [34] in the critical window a little more precisely: if we let $\#U_{p,n}^{(i)}(m)$ be the size of the $i$-th largest unicycle in $F_{p,n}(m)$, then the process of couple of sequences

$$ \left( \left( \left( \frac{\#T_{p,n}^{(i)}(\lfloor \frac{n}{2} \rfloor + \lambda n^{2/3} \rfloor)}{n^{2/3}} \right)_{i \ge 1} \right), \left( \frac{\#U_{p,n}^{(i)}(\lfloor \frac{n}{2} \rfloor + \lambda n^{2/3} \rfloor)}{n^{2/3}} \right)_{i \ge 1} \right), \lambda \in \mathbb{R} $$

has a limit in distribution in $\ell^2 \times \ell^1$ towards a frozen multiplicative coalescent.

We finish this section with a corollary on the geometry of a typical tree.

**Corollary 1.8 (Typical tree).** Let $CC_{p,n}^*(m)$ denote the connected component of $F_{p,n}(m)$ containing the vertex 1, with vertices relabeled in increasing order from 1 to $\#CC_{p,n}^*(m)$. Then,

$$ CC_{p,n}^*(\lfloor nt \rfloor) | CC_{p,n}^*(\lfloor nt \rfloor) \text{ is a tree } \xrightarrow{n \to \infty} \text{GW}_{\text{Poi}(2t(1-g_p(t)))} $$

where $\text{GW}_{\text{Poi}(2t(1-g_p(t)))}$ designs a Galton-Watson tree whose offspring distribution is Poisson with mean $2t(1-g_p(t))$, equipped with uniform random labels from 1 to $\#\text{GW}_{\text{Poi}(2t(1-g_p(t)))}$ on its vertices, and where the original order is forgotten, as well as the root. In a related way,

$$ \mathbb{P}(CC_{p,n}^*(\lfloor nt \rfloor) \text{ is a tree of size } k) \xrightarrow{n \to \infty} k \cdot t_{p,k}(t). $$

As already mentioned, the function $t \mapsto 2t(1-g_p(t)) = 2r_p(t)$ is increasing on $(0, 1/2]$, decreasing on $[1/2, 1)$, with a maximum equal to 1 reached at $t = 1/2$. The Galton-Watson tree appearing in the limit above is therefore subcritical for $t \neq 1/2$ and critical for $t = 1/2$. When $t \in (0, 1/2]$, since $g_p(t) = 0$, it is simply a Galton-Watson tree with a Poisson offspring distribution with mean $2t$.

## 1.3 Total gelation time and vicinity

Theorem 1.2 also leads us to a precise asymptotic for the first time at which the $n$ vertices of $F_{p,n}$ are all frozen, as well as related quantities. We call this time the absorption time or total gelation time and denote it by

$$ A_{p,n} := \inf \{m \ge 0 : G_{p,n}(m) = n\}. $$

Similarly to what happens in the standard Erdős-Rényi model for the first time at which the graph is connected, we will see that $A_{p,n}$ is identical, with high probability, to the first time at which there are no more isolated vertices in the process. This is explained by the fact that larger trees aggregate more quickly to the gel and so disappear earlier. If we let $A_{p,n}^{(k)}$ denote the last time at which there are some trees of size $k \in \mathbb{N}$ in the process and $A_{p,n}^{(k+)}$ the last time at which there are some trees of size larger or equal to $k \in \mathbb{N}$ (so that $A_{p,n}^{(1+)} = A_{p,n}$), we will see that for $n$ large

$$ A_{p,n} \approx A_{p,n}^{(1)} \approx \frac{n \ln n}{2p} $$
and more generally that

$$A_{p,n}^{(k+)} \approx A_{p,n}^{(k)} \approx \frac{n}{2} \cdot \left( \frac{\ln(n)}{kp} + \frac{(k-1)}{kp} \cdot \ln \left( \frac{\ln(n)}{kp} \right) \right).$$

In the following we set

$$t_{p,n}^{(k)} = \frac{\ln(n)}{kp} + \frac{(k-1)}{kp} \cdot \ln \left( \frac{\ln(n)}{kp} \right), \quad (1.5)$$

and, to describe precisely the above asymptotics, introduce the following notation:

- $\gamma_E$ is Euler's constant

- $\psi$ is the digamma function, that is $\psi(x) = \frac{\Gamma'(x)}{\Gamma(x)}$, $x > 0$, with $\Gamma$ the gamma function

- Gu is a standard Gumbel random variable, that is with cumulative distribution function $e^{-e^{-x}}$, $x \in \mathbb{R}$.

We emphasize that the function $p \in (0,1] \to \psi(1/p) + \gamma_E$ is decreasing, equal to 0 when $p = 1$ and to 1 when $p = 1/2$, and that $\psi(1/p) + \gamma_E \sim -\ln p$ when $p \to 0$.

**Theorem 1.9.** For all $k \in \mathbb{N}$, as $n \to \infty$,

$$\mathbb{P}(A_{p,n}^{(k+)} = A_{p,n}^{(k)}) \underset{n \to \infty}{\longrightarrow} 1$$

and

$$\frac{A_{p,n}^{(k+)} - \frac{t_{p,n}^{(k)}}{2}}{n} \xrightarrow{n \to \infty} \frac{\text{Gu}}{2kp} - \frac{\psi(1/p) + \gamma_E}{2p} + \frac{\ln(k^{k-2}/k!)}{2kp}.$$

In particular, the absorption time $A_{p,n}$ behaves as

$$\frac{A_{p,n}}{n} - \frac{\ln(n)}{2p} \xrightarrow{n \to \infty} \frac{\text{Gu}}{2p} - \frac{\psi(1/p) + \gamma_E}{2p}.$$

The proof of Theorem 1.9 uses a continuous version of the $p$-frozen model. In this continuous framework, we obtain exact expressions of the factorial moments of the total number of vertices involved in a tree of size $k \in \mathbb{N}$ at any time $t \ge 0$, which depend on the (continuous version of the) gel process $G_{p,n}$. Theorem 1.2 will then give their asymptotic behaviors. As an intermediate and complementary result to Theorem 1.9, we obtain via this approach the behavior in distribution of the number of trees of size $k$ around the threshold times $n \cdot t_{p,n}^{(k)}/2$. More precisely, if we let $N_{p,n}^{(k)}([n \cdot (t_{p,n}^{(k)} + c)/2])$ be the number of trees of size $k$ at time $\lfloor n(t_{p,n}^{(k)} + c)/2 \rfloor$, for $c \in \mathbb{R}$, in the discrete model $F_{p,n}$, one then has:

**Proposition 1.10.** For all $k \in \mathbb{N}$ and all $c \in \mathbb{R}$

$$N_{p,n}^{(k)} \left( \lfloor \frac{n}{2} \cdot (t_{p,n}^{(k)} + c) \rfloor \right) \xrightarrow{n \to \infty} \mathcal{P} \left( \frac{k^{k-2} e^{-kpc} e^{-k(\psi(1/p) + \gamma_E)}}{k!} \right),$$

where the notation $\mathcal{P}(\lambda)$ refers to a Poisson distribution with expectation $\lambda > 0$.

Additionally, each positive moment of $N_{p,n}^{(k)}([n \cdot (t_{p,n}^{(k)} + c)/2])$ converges to the corresponding moment of the Poisson distribution.
**Remark.** When $p = 1$, using that the forest part of the frozen model is distributed as the forest part of the standard Erdős-Rényi graph, Proposition 1.10 recovers a result by Erdős and Rényi [15] for the number of trees of size $k$ in their model. When $k = 1$ this result is well known, but the cases $k \ge 2$ are perhaps less known. Regarding Theorem 1.9 again when $p = 1$, the case $k = 1$ corresponds to the asymptotic behavior of the connectedness time $A_{ER,n}$ in the standard Erdős-Rényi graph and retrieves (1.1). We are not aware if similar counterparts when $k \ge 2$ were investigated for the standard Erdős-Rényi model. In any case, Theorem 1.9 gives the asymptotics for this model of the last time at which there are some trees of size $k$ (say $A_{ER,n}^{(k)}$), and the last time at which there are some trees of size larger or equal to $k$ (say $A_{ER,n}^{(k+)}$), with $\mathbb{P}(A_{ER,n}^{(k+)} = A_{ER,n}^{(k)}) \xrightarrow{n \to \infty} 1$ and

$$ \frac{A_{ER,n}^{(k+)} - \frac{t_{1,n}^{(k)}}{2} \xrightarrow{d} \frac{Gu}{2k} + \frac{\ln(k^{k-2}/k!)}{2k}}{n} $$

## 1.4 Organization of the paper

In Section 2, the connections of the model $F_{p,n}$ with uniform random forests are used to obtain asymptotics on the jumps of the processes $G_{p,n}$ and $D_{p,n}$, which are preliminary results needed to establish the fluid limit results. Some properties of the functions $g_p, d_p, v_p, e_p$ and $r_p$ are then highlighted in Section 3. Section 4 is devoted to the proofs of the fluid limit results, Theorem 1.2 and Theorem 1.6, as well as Corollary 1.7 and Corollary 1.8. A continuous, Poissonized, version of the model is introduced and studied in Section 5. It is used in Section 6 to prove continuous counterparts of Theorem 1.9 and Proposition 1.10, and then these results themselves. Finally, in Section 7, we discuss the case $p = 0$ and some open questions concerning the sizes of unicycle components in the supercritical regime, for any $p$. The paper ends with an Appendix A recalling background on the Borel-Tanner distribution and Wormald's result on the differential equation method which we will use for the proofs of the fluid limit.

# 2 Frozen Erdős-Rényi and uniform random forests

As stated in Proposition 1.3, it turns out that conditionally on its number of vertices $V_{p,n}(m)$ and edges $E_{p,n}(m)$, the forest part of the frozen model $F_{p,n}(m)$ is a uniform random forest. This property is crucial for our study. We develop here several consequences.

A main point concerns the expressions of the distribution of the jumps of the processes $G_{p,n}$ and $D_{p,n}$ at time $m$, given their history until then. This will be fundamental to implement the results on the fluid limit. We use in the following proposition and throughout the paper the notation

$$ \Delta G_{p,n}(m) = G_{p,n}(m+1) - G_{p,n}(m), $$

and similarly for $D_{p,n}$, to denote the increments of these processes, and let $(F_{p,n}(m), m \ge 1)$ design the filtration generated by $(G_{p,n}, D_{p,n})$, or equivalently $(V_{p,n}, E_{p,n})$ recalling the relations (1.2). Recall
also that for $N \in \mathbb{N}$ and $M \in \mathbb{Z}_+$, with $M \le N - 1$, $W(N, M)$ denotes the set of unrooted unordered forests with $N$ labeled vertices $\{1, \dots, N\}$ and $M$ edges.

**Proposition 2.1.** For every $n \in \mathbb{N}$, $m \in \mathbb{Z}_+$ and $k \in [1; E_{p,n}(m) + 1]$,

$$ \mathbb{P}(\Delta G_{p,n}(m) = k \mid \mathbf{F}_{p,n}(m)) = \binom{V_{p,n}(m)}{k} \cdot k^{k-2} \cdot \frac{\#W(V_{p,n}(m) - k, E_{p,n}(m) - k + 1)}{\#W(V_{p,n}(m), E_{p,n}(m))} \cdot \left( \frac{k(k-1) + 2pkG_{p,n}(m)}{n(n-1)} \right), $$

with the conventions $\#W(0,0) = 1$, $\#W(N,N) = 0$ for any $N \in \mathbb{N}$, $\#W(-1,0) = 0$, and

$$ \mathbb{P}(\Delta D_{p,n}(m) = 1 \mid \mathbf{F}_{p,n}(m)) = 2(1-p) \cdot \frac{G_{p,n}(m)(n - G_{p,n}(m))}{n(n-1)} + \frac{G_{p,n}(m)(G_{p,n}(m) - 1)}{n(n-1)}. $$

**Proof.** Given that a tree of size $k$ is a connected component of $F_{p,n}(m)$, it will freeze at time $m + 1$

- either if the edge selected at time $m + 1$ involves two vertices of that tree, which happens with probability $\frac{k(k-1)}{n(n-1)}$

- or if the edge selected at time $m + 1$ involves a vertex of the tree and a vertex of the freezer and is retained, which happens with probability $p \cdot \frac{2kG_{p,n}(m)}{n(n-1)}$.

Next, with a set of $V_{p,n}(m) \ge 1$ vertices, one can build for $k \le V_{p,n}(m)$

$$ \binom{V_{p,n}(m)}{k} \cdot k^{k-2} \quad \text{different trees of size } k $$

(recall Cayley's formula: there are $k^{k-2}$ different trees on a fixed set of $k$ vertices). And since the forest part of $F_{p,n}(m)$, conditionally on $F_{p,n}(m)$, is a uniform random forest with $V_{p,n}(m)$ vertices and $E_{p,n}(m)$ edges, the probability that a given tree of size $k \le E_{p,n}(m) + 1$, $k \ge 1$, belongs to this forest is

$$ \frac{\#W(V_{p,n}(m) - k, E_{p,n}(m) - k + 1)}{\#W(V_{p,n}(m), E_{p,n}(m))}, $$

with the conventions of the statement when $E_{p,n}(m) = V_{p,n}(m) - 1$ or $E_{p,n}(m) = V_{p,n}(m) = 0$. Gathering these remarks gives the stated expression of $\mathbb{P}(\Delta G_{p,n}(m) = k \mid \mathbf{F}_{p,n}(m))$.

Regarding $D_{p,n}$, simply note that the edge selected at time $m + 1$ is discarded

- either if it involves two vertices of the freezer of $F_{p,n}(m)$, which, conditionally on $F_{p,n}(m)$, happens with probability $\frac{G_{p,n}(m)(G_{p,n}(m)-1)}{n(n-1)}$

- or if it involves a vertex of the forest and a vertex of the freezer and it is not retained, which, conditionally on $F_{p,n}(m)$, happens with probability $(1-p) \cdot 2 \cdot \frac{G_{p,n}(m)(n-G_{p,n}(m))}{n(n-1)}$.

□
In the rest of the section we recall some background on uniform random forests (Section 2.1) in order to evaluate the asymptotics for $n$ large of the above conditional distributions (Section 2.2) and to get estimates on the largest jump of $G_{p,n}$ (Section 2.3).

## 2.1 Background on uniform random forests

We gather here the information we need on the enumeration of uniform random forests, following Kolchin [18] and Britikov [11], and on the sizes of the largest connected components of the forest, following Luczak-Pittel [22] and Bernikovich-Pavlov [7]. A key point is that the sizes of the connected components of a uniform random forest can be interpreted as the increments of a conditioned random walk. For $x \in (0, e^{-1}]$ consider the probability measure

$$ \mu_x(k) = \frac{k^{k-2}}{k!} \cdot \frac{x^k}{T(x)}, \quad k \ge 1, \quad \text{with} \quad T(x) = \sum_{k \ge 1} \frac{k^{k-2}}{k!} x^k. \qquad (2.1) $$

Setting $x = \theta e^{-\theta}$ with $\theta \in (0, 1]$, one checks that $T(x) = \theta - \theta^2/2$, that the expectation of $\mu_x$ is $2/(2 - \theta)$ and its variance $2\theta/(1 - \theta)(2 - \theta)^2$ (see e.g. Lemma A.3 in the Appendix).

The following result dates back at least to Kolchin [18] and Britikov [11] and was formulated as is by Contat-Curien [12].

**Proposition 2.2** ([18],[11],[12]). Let $N \in \mathbb{N}$, $M \in \mathbb{Z}_+$ with $M \le N - 1$ and for $x \in (0, e^{-1}]$, ($S_i^{(x)}: 0 \le i \le N - M$) be a random walk with i.i.d. increments of law $\mu_x$, started from $S_0^{(x)} = 0$.

1) Whatever $x \in (0, e^{-1}]$, the cardinal of $W(N, M)$ is given by

$$ \#W(N, M) = \frac{N!}{(N - M)!} \cdot \frac{T(x)^{N - M}}{x^N} \cdot \mathbb{P}(S_{N - M}^{(x)} = N). $$

2) If $W(N, M)$ is a uniform random forest of $W(N, M)$ and $C_1, \dots, C_{N-M}$ denote the sizes of its connected components indexed in a uniform random order, then, whatever $x \in (0, e^{-1}]$, the vector $(C_1, \dots, C_{N-M})$ has the same law as the increments of $(S_i^{(x)}: 0 \le i \le N - M)$ conditioned on $S_{N-M}^{(x)} = N$. Moreover, conditionally on their sizes, the connected components are independent uniform Cayley trees.

Britikov [11] used the first point to estimate the asymptotic of $\#W(N, M)$ in different regimes, using for each of them an appropriate value of $x$ (depending possibly on $N, M$) to obtain relevant estimates. The case $x = e^{-1}$ is of particular interest in the critical regime: the resulting measure $\mu_{e^{-1}}$ is then heavy-tailed, in the domain of attraction of a 3/2-stable law, with $\mu_{e^{-1}}(k) \sim \sqrt{\frac{2}{\pi}}k^{-5/2}$ as $k \to \infty$, and its expectation is equal to 2. Let

$$ p_1(x) = \frac{1}{\pi} \int_0^{\infty} e^{-\frac{2}{3}t^{3/2}} \cos \left( xt + \frac{2}{3}t^{3/2} \right) dt $$

be the density of the corresponding 3/2-stable law. Britikov's result reads as follows.
**Proposition 2.3** (Britikov [11]). Let $\omega = (2M - N)/N^{2/3}$, with $N \in \mathbb{N}$, $M \in \mathbb{Z}_+$, $M \le N - 1$.

1) (Subcritical regime) When $\omega \to -\infty$,

$$ \#W(N, M) = (1 + o(1)) \cdot \frac{N^{2M}}{2^M M!} \cdot \left(1 - \frac{2M}{N}\right)^{1/2}. $$

2) (Near-critical regime) When $N \to \infty$ and $\omega$ is bounded,

$$ \#W(N, M) = (1 + o(1)) \cdot \frac{N^{N-1/6}}{2^{N-M}(N-M)!} \cdot \sqrt{2\pi} \cdot p_1(\omega). $$

3) (Supercritical regime) When $\omega \to \infty$,

$$ \#W(N, M) = (1 + o(1)) \cdot \frac{N^{N-2}}{2^{N-M-1}(N-M-1)!} \cdot \left(\frac{2M}{N} - 1\right)^{-5/2}. $$

Note that $\omega \to -\infty$ or $\omega \to \infty$ implies $N \to \infty$.

Using these estimates, Luczak and Pittel [22] studied the asymptotics of the largest components of uniform random forests in each of the three regimes, showing similar, yet different, behaviors to the Erdős-Rényi graph: a phase transition occurs according to whether $M/N < 1/2$ (with largest components of order $\ln(N)$), $M/N \sim 1/2$ (with largest components of order $N^{2/3}$) and $N/M > 1/2$ (where a giant component emerges); however in the supercritical regime, removing the giant tree results in a critical random forest, whereas removing the giant component in the Erdős-Rényi graph gives a subcritical Erdős-Rényi graph. We specify some of Luczak and Pittel's results in the subcritical regime – which themselves are based on results of Erdős and Rényi [15] in the subcritical regime of their model – as we shall need them later.

**Proposition 2.4** (Luczak-Pittel [22], Theorem 3.1 (ii)). For $i \in \mathbb{N}$, let $L_i(N, M)$ denote the size of the $i$-th largest tree in a uniform random forest with $N$ vertices and $M$ edges. Then, when $(N, M/N) \to (\infty, c)$, with $c \in (0, 1/2)$,

$$ \frac{L_i(N, M)}{\ln(N)} \xrightarrow{\mathbb{P}} \frac{1}{2c - 1 - \ln(2c)}. $$

## 2.2 Asymptotics of expected conditional jumps

Combining Proposition 2.3 with Proposition 2.1 gives the asymptotics of Corollary 2.5 below. In this statement, we specify the variable of the Landau notation $o(1)$ by writing $o_l(1)$ for a (deterministic) quantity that vanishes as $l$ is large (this function may differ in each assertion). Also, for all $n \in \mathbb{N}$, $m \in \mathbb{Z}_+$ such that $V_{p,n}(m) \ge 1$ and all $k \in \mathbb{N}$, $k < V_{p,n}(m)$, we set

$$ \Omega_{p,n}(m) = \frac{2E_{p,n}(m) - V_{p,n}(m)}{(V_{p,n}(m))^{2/3}}, \qquad \Omega_{p,n}^{(k)}(m) = \frac{2E_{p,n}(m) - V_{p,n}(m) - k + 2}{(V_{p,n}(m) - k)^{2/3}} $$

and $\Omega_{p,n}(m) = 0$ when $V_{p,n}(m) = 0$, $\Omega_{p,n}^{(k)}(m) = 0$ when $k \ge V_{p,n}(m)$.
**Corollary 2.5.** Let $\epsilon: \mathbb{Z}_+ \to \mathbb{R}$ denote a positive function that vanishes at infinity.

1) When $(\Omega_{p,n}(m), E_{p,n}(m)) \to (-\infty, \infty)$,

$$ \mathbb{P}(\Delta G_{p,n}(m) = k \mid \mathbf{F}_{p,n}(m)) = (1 + o_{(\Omega_{p,n}(m), E_{p,n}(m))}(1)) \cdot \frac{k^{k-1}}{k!} \cdot \left(\frac{2E_{p,n}(m)}{V_{p,n}(m)}\right)^{k-1} \\ \times e^{-2k \frac{E_{p,n}(m)}{V_{p,n}(m)}} \cdot \left(\frac{k-1+2pG_{p,n}(m)}{n}\right) \frac{n-G_{p,n}(m)}{n}, $$

where the function $o.(1)$ is uniform over all $k$ such that $1 \le k \le \epsilon(E_{p,n}(m))(E_{p,n}(m))^{1/2}$.

2) Let $c > 0$ be some arbitrary constant. When $|\Omega_{p,n}(m)| \le c$ and $V_{p,n}(m) \to \infty$,

$$ \mathbb{P}(\Delta G_{p,n}(m) = k \mid \mathbf{F}_{p,n}(m)) = (1 + o_{V_{p,n}(m)}(1)) \cdot \frac{2k^{k-1}}{k!e^k} \cdot \frac{V_{p,n}(m) - E_{p,n}(m)}{n} \cdot \left(\frac{k-1+2pG_{p,n}(m)}{n}\right) \cdot \frac{p_1(\Omega_{p,n}^{(k)}(m))}{p_1(\Omega_{p,n}(m))} $$

where the function $o.(1)$ is uniform over all $k$ such that $1 \le k \le \epsilon(V_{p,n}(m))(V_{p,n}(m))^{1/2}$.

3) When $\Omega_{p,n}(m) \to \infty$,

$$ \mathbb{P}(\Delta G_{p,n}(m) = k \mid \mathbf{F}_{p,n}(m)) = (1 + o_{\Omega_{p,n}(m)}(1)) \cdot \frac{2k^{k-1}}{k!e^k} \cdot \left(\frac{k-1+2pG_{p,n}(m)}{n}\right) \frac{V_{p,n}(m) - E_{p,n}(m) - 1}{n} $$

where the function $o.(1)$ is uniform over all $k$ such that $1 \le k \le \epsilon(V_{p,n}(m))(V_{p,n}(m))^{1/2}$.

**Remark.** A consequence of 2) and 3), together with Stirling's formula and the fact that the function $p_1$ is strictly positive on $\mathbb{R}$, is that for any $A > 0$ and any function $\epsilon$ that vanishes at infinity, there exists a constant $c_{A,\epsilon,p} > 0$ such that for every $V_{p,n}(m), E_{p,n}(m)$ verifying $2E_{p,n}(m) - V_{p,n}(m) \ge -AV_{p,n}(m)^{2/3}$ with $V_{p,n}(m)$ large enough, and then every $1 \le k \le \epsilon(V_{p,n}(m))(V_{p,n}(m))^{1/2}$,

$$ \mathbb{P}(\Delta G_{p,n}(m) = k \mid \mathbf{F}_{p,n}(m)) \ge \frac{c_{A,\epsilon,p}}{k^{3/2}} \cdot \frac{G_{p,n}(m)(V_{p,n}(m) - E_{p,n}(m) - 1)}{n^2}. \quad (2.2) $$

**Proof.** We shall repeatedly use the following consequence of Stirling's formula: as $l \in \mathbb{N} \to \infty$, uniformly for all integers $k \in [1, \epsilon(l)\sqrt{l}]$

$$ \frac{l!}{(l-k)!} = (1 + o_l(1)) \cdot l^k. $$

1) When $\Omega_{p,n}(m) \to -\infty$, one has $V_{p,n}(m) \to \infty$ and so $\Omega_{p,n}^{(k)}(m) = \Omega_{p,n}(m)(1 + o_{V_{p,n}(m)}(1))$, uniformly in $1 \le k \le (V_{p,n}(m))^{1/2}$. Applying the subcritical regime estimate of Proposition 2.3
together with Stirling's formula, we thus get

$$ \frac{\#W(V_{p,n}(m) - k, E_{p,n}(m) - k + 1)}{\#W(V_{p,n}(m), E_{p,n}(m))} = (1 + o_{\Omega_{p,n}(m)}(1)) \cdot 2^{k-1} \cdot \frac{(V_{p,n}(m) - k)^{2(E_{p,n}(m)-k+1)}}{V_{p,n}(m)^{2E_{p,n}(m)}} \\ \times \frac{E_{p,n}(m)!}{(E_{p,n}(m) - k + 1)!} \cdot \left( \frac{(2E_{p,n}(m) - V_{p,n}(m) - k + 2) V_{p,n}(m)}{(2E_{p,n}(m) - V_{p,n}(m))(V_{p,n}(m) - k)} \right)^{1/2} \\ = (1 + o_{(\Omega_{p,n}(m), E_{p,n}(m))}(1)) \cdot 2^{k-1} \cdot V_{p,n}(m)^{-2k+2} E_{p,n}(m)^{k-1} \\ \times e^{-2kE_{p,n}(m)/V_{p,n}(m)} $$

when $(\Omega_{p,n}(m), E_{p,n}(m)) \to (-\infty, \infty)$, uniformly for all $1 \le k \le \epsilon(E_{p,n}(m))(E_{p,n}(m))^{1/2}$. Together with Proposition 2.1 this leads to

$$ \mathbb{P}(\Delta G_{p,n}(m) = k | \mathbf{F}_{p,n}(m)) = (1 + o_{(\Omega_{p,n}(m), E_{p,n}(m))(1)}(1)) \cdot \frac{k^{k-1}}{k!} \cdot (2E_{p,n}(m))^{k-1} V_{p,n}(m)^{-2k+2} \\ \times e^{-2kE_{p,n}(m)/V_{p,n}(m)} \frac{V_{p,n}(m)!}{(V_{p,n}(m) - k)!} \cdot \left( \frac{k-1+2pG_{p,n}(m)}{n(n-1)} \right) \\ = (1 + o_{(\Omega_{p,n}(m), E_{p,n}(m))(1)}(1)) \cdot \frac{k^{k-1}}{k!} \cdot \left( \frac{2E_{p,n}(m)}{V_{p,n}(m)} \right)^{k-1} \cdot e^{-2kE_{p,n}(m)/V_{p,n}(m)} \\ \times \frac{(k-1+2pG_{p,n}(m))(n-G_{p,n}(m))}{n^2} $$

uniformly for all $1 \le k \le \epsilon(E_{p,n}(m))(E_{p,n}(m))^{1/2}$, where we used again Stirling's formula and that $V_{p,n}(m) = n - G_{p,n}(m)$.

2) The proof is similar. Observe that under the hypotheses we make here we have $|\Omega_{p,n}^{(k)}(m)| \le c + o_{V_{p,n}(m)}(1)$, uniformly in $1 \le k \le (V_{p,n}(m))^{1/2}$. We can thus apply the asymptotics in the critical regime of Proposition 2.3 to estimate both $\#W(V_{p,n}(m) - k, E_{p,n}(m) - k + 1)$ and $\#W(V_{p,n}(m), E_{p,n}(m))$, and then plug them in the first identity of Proposition 2.1 to get the result.

3) When $\Omega_{p,n}(m) \to \infty$, again $V_{p,n}(m) \to \infty$ and $\Omega_{p,n}^{(k)}(m) = \Omega_{p,n}(m)(1 + o_{V_{p,n}(m)}(1))$, uniformly in $1 \le k \le (V_{p,n}(m))^{1/2}$. So we now apply the asymptotics of the supercritical regime of Proposition 2.3, together with Proposition 2.1, to get the expected result. Note that here one may have $E_{p,n}(m) = V_{p,n}(m) - 1$, in which case the cardinal $\#W(V_{p,n}(m) - k, E_{p,n}(m) - k + 1)$ is null for each $k$, as well as the probability $\mathbb{P}(\Delta G_{p,n}(m) = k | \mathbf{F}_{p,n}(m))$. $\square$

## 2.3 Estimates on the jumps of $G_{p,n}$

We will also need to control the jumps of $G_{p,n}$, which, by Proposition 1.3, are related to the sizes of the trees in uniform random forests $W(V_{p,n}(m), E_{p,n}(m))$. In that aim, we settle here estimates on the size $L_1(N, M)$ of the largest tree in a uniform random forest with $N$ vertices and $M$ edges, in the
spirit of what has been done by Luczak-Pittel [22] and Bernikovich-Pavlov [7]. We refine slightly their results, relying on Proposition 2.2 and its notation. The first lemma below concerns the subcritical regime, and the second the supercritical regime.

**Lemma 2.6.** Fix $\varepsilon > 0$ and consider a function $B$ such that $B(N) \to \infty$ as $N \to \infty$. Then for $N$ large enough and all $M$ verifying $2M - N \le -\varepsilon N$,

$$ \mathbb{P}(L_1(N, M) \ge B(N)) \le \frac{C_\varepsilon \cdot N^2}{B(N)^2} \cdot \exp\left(-\frac{\varepsilon^2 B(N)}{2}\right) $$

where $C_\varepsilon \in (0, \infty)$ only depends on $\varepsilon$.

For the proof, we use the following local limit theorem stemming from Britikov [11]. Recall the notation $\mu_x$ (2.1) and $S^{(x)}$ from Proposition 2.2, and for $\theta \in (0, 1)$, set

$$ m(\theta) = \frac{2}{2 - \theta} \quad \text{and} \quad \sigma^2(\theta) = \frac{2\theta}{(1 - \theta)(2 - \theta)^2}. $$

**Lemma 2.7 (Britikov [11], Lemma 5).** Let $x = \theta e^{-\theta}$ for some $\theta \in (0, 1)$ which may depend on $N, M$. Assume that $N - M \to \infty$, $(N - M)\theta \to \infty$ and $(N - M)^{1/3}(1 - \theta) \to \infty$. Then, if $z = \frac{N - m(\theta)(N - M)}{\sigma(\theta)(N - M)^{1/2}}$ lies in some finite interval, one has

$$ \sigma(\theta)(N - M)^{1/2} \mathbb{P}(S_{N-M}^{(x)} = N) = (1 + o(1)) \frac{1}{\sqrt{2\pi}} e^{-z^2/2}. $$

**Proof of Lemma 2.6.** Throughout the proof we consider $M \ge B(N) - 1$ since otherwise $\mathbb{P}(L_1(N, M) \ge B(N))$ is null and the statement is trivially true. By Proposition 2.2, if $X_i^{(x)}$, $i \ge 1$, are i.i.d. random variables with law $\mu_x$, whatever $x \in (0, e^{-1}]$, one has

$$ \begin{aligned} \mathbb{P}(L_1(N, M) \ge B(N)) &= \sum_{r=B(N)}^{M+1} \mathbb{P}\left(\max_{1 \le i \le N-M} X_i^{(x)} = r \mid S_{N-M}^{(x)} = N\right) \\ &\le (N-M) \sum_{r=B(N)}^{M+1} \frac{\mu_x(r) \cdot \mathbb{P}(S_{N-M-1}^{(x)} = N-r)}{\mathbb{P}(S_{N-M}^{(x)} = N)} \\ &\le \frac{N-M}{\mathbb{P}(S_{N-M}^{(x)} = N)} \cdot \sum_{r=B(N)}^{M+1} \mu_x(r). \end{aligned} \quad (2.3) $$

Following Britikov [11], the strategy is then to choose wisely $x \in (0, e^{-1}]$. We take here $x = \theta e^{-\theta}$ with $\theta = 2M/N$. Note that under our hypotheses on $M$, one has $\theta \in (0, 1)$ and then $m(\theta) = N/(N - M)$. And also, $(N - M)\theta \ge M \to \infty$ (since $M \ge B(N) - 1$) and $(N - M)^{1/3}(1 - \theta) \ge \varepsilon (N - M)^{1/3} \to \infty$ as $N \to \infty$. Lemma 2.7 thus yields that for $N$ large enough and every $M \ge B(N) - 1$ verifying $2M - N \le -\varepsilon N$

$$ \mathbb{P}(S_{N-M}^{(x)} = N) \ge \frac{1}{2\sqrt{2\pi}} \cdot \frac{(N - M)^{1/2}(N - 2M)^{1/2}}{M^{1/2}N}. $$
Plugging this bound in (2.3), and using again that $2M - N \le -\epsilon N$, we get

$$ \begin{aligned} \mathbb{P}(L_1(N, M) \ge B(N)) &\le C_1 \cdot NM^{1/2} \sum_{r=B(N)}^{M+1} \frac{r^{r-2}}{r!} \cdot \frac{x^r}{T(x)} \\ &\le C_1 \cdot NM^{1/2} \sum_{r=B(N)}^{M+1} \frac{r^{r-2}}{r!} \left(\frac{2M}{N}\right)^r e^{-\frac{2Mr}{N}} \cdot \frac{N^2}{2M(N-M)}, \end{aligned} $$

with $C_1 \in (0, \infty)$ depending only on $\epsilon$. We used Lemma A.3 to obtain $T(x)$. Next, by Stirling's formula, still under our hypotheses on $M$, this leads to

$$ \begin{aligned} \mathbb{P}(L_1(N, M) \ge B(N)) &\le \frac{C_2 \cdot N^2}{B(N)^{1/2}} \sum_{r=B(N)}^{M+1} r^{-5/2} e^r \left(\frac{2M}{N}\right)^r e^{-\frac{2Mr}{N}} \\ &\le \frac{C_2 \cdot N^2}{B(N)^{1/2}} \sum_{r=B(N)}^{M+1} r^{-5/2} e^{-r(1-2M/N)^2/2} \end{aligned} $$

for some $C_2 \in (0, \infty)$ depending only on $\epsilon$, and all $N$ large enough, where for the second inequality we used that $e^x(1-x) \le e^{-x^2/2}$ for $x \in [0, 1]$. Finally we get

$$ \mathbb{P}(L_1(N, M) \ge B(N)) \le \frac{C_2 \cdot N^2}{B(N)^{1/2}} \exp \left( - \left(1 - \frac{2M}{N}\right)^2 \frac{B(N)}{2} \right) \sum_{r=B(N)}^{M} r^{-5/2} $$

which leads to the upper bound of the statement. $\square$

**Lemma 2.8.** Consider two functions $\omega, g$ such that, as $N \to \infty$, $\omega(N) \to \infty$, $\omega(N) = o(N^{1/3})$, $g(N) \to \infty$ and $g(N) = o(\omega(N))$. Then, for $N$ large enough and every $M$ verifying $2M - N = \omega(N)N^{2/3}$,

$$ \mathbb{P}(L_1(N, M) < g(N)N^{2/3}) \le C \cdot \omega(N)^{5/2} N^{2/3} \cdot \exp \left( - \frac{\omega(N)}{g(N)} \right), $$

for some $C \in (0, \infty)$ independent of $N$.

**Proof.** We use here Proposition 2.2 with the measure $\mu_{e-1}$ and let $X_i, i \ge 1$, be i.i.d. random variables with law $\mu_{e-1}$. The proof is inspired by [7] for similar results in the case of unlabelled forests. We recall that the expectation of $\mu_{e-1}$ is equal to 2 and introduce the centered random variables $Y_i = X_i - 2$, $i \ge 1$, as well as $\tilde{S}_N = \sum_{i=1}^N Y_i$ and $\tilde{S}_N^{(r-2)} = \sum_{i=1}^N Y_i^{(r-2)}$, with $Y_i^{(r-2)} = Y_i \mathbb{1}_{\{Y_i \le r-2\}}$, for $N, r \ge 1$. From Proposition 2.2, for any $r \in \mathbb{N}$:

$$ \begin{aligned} \mathbb{P}(L_1(N, M) \le r) &= \frac{\mathbb{P}\left(\max_{i \le N-M} Y_i \le r-2, \tilde{S}_{N-M} = \omega(N)N^{2/3}\right)}{\mathbb{P}\left(\tilde{S}_{N-M} = \omega(N)N^{2/3}\right)} \\ &\le \frac{\mathbb{P}\left(\tilde{S}_{N-M}^{(r-2)} = \omega(N)N^{2/3}\right)}{\mathbb{P}\left(\tilde{S}_{N-M} = \omega(N)N^{2/3}\right)}. \end{aligned} $$
The measure $\mu_{e^{-1}}$ being in the domain of attraction of a 3/2-stable law, the local limit theorem (see e.g. [16]) yields, under the assumption $2M - N = \omega(N)N^{2/3}$ with $\omega(N) \to \infty$ and $\omega(N) = o(N^{1/3})$,

$$ \mathbb{P}(\tilde{S}_{N-M} = \omega(N)N^{2/3}) = \frac{(1+o(1))}{\sqrt{2\pi}} \cdot \omega(N)^{-5/2}N^{-2/3}. \quad (2.4) $$

We now want to get an upper bound for $\mathbb{P}(\tilde{S}_{N-M}^{(r-2)} = \omega(N)N^{2/3})$ when $r = g(N)N^{2/3}$ with $g(N) \to \infty$ and $g(N) = o(\omega(N))$. Since $|r^{-1}Y_1^{(r-2)}| \le 1$ and $e^x \le 1+x+x^2$ for all $x \in [-1, 1]$, we have that

$$ \begin{aligned} \mathbb{P}(\tilde{S}_{N-M}^{(r-2)} = \omega(N)N^{2/3}) &\le e^{-r^{-1}\omega(N)N^{2/3}} \mathbb{E}[e^{r^{-1}Y_1^{(r-2)}}]^{N-M} \\ &\le e^{-r^{-1}\omega(N)N^{2/3}} \left(\mathbb{E}\left[1 + r^{-1}Y_1^{(r-2)} + (r^{-1}Y_1^{(r-2)})^2\right]\right)^{N-M}. \end{aligned} $$

The distribution of $Y_1$ yields the existence of $a, b \in (0, \infty)$ such that for every $r$ large enough

$$ \mathbb{E}[Y_1^{(r-2)}] \le \frac{-a}{\sqrt{r}} \quad \text{and} \quad \mathbb{E}[(Y_1^{(r-2)})^2] \le b\sqrt{r} $$

which then leads to

$$ \begin{aligned} \mathbb{P}(\tilde{S}_{N-M}^{(r-2)} = \omega(N)N^{2/3}) &\le e^{-r^{-1}\omega(N)N^{2/3}} (1+br^{-3/2})^{N-M} \\ &\le e^{-\omega(N)/g(N)} e^{bNr^{-3/2}/2}. \end{aligned} $$

Together with (2.4) and since $Nr^{-3/2} = g(N)^{-3/2} \to 0$ as $N \to \infty$, we get the expected upper bound for $\mathbb{P}(L_1(N, M) \le g(N)N^{2/3})$. $\square$

### 3 Properties of the fluid limit functions

In the Introduction, the function $g_p : [0, \infty) \to [0, 1)$, which will describe the fluid limit of the gel in the p-frozen model, was defined on $[1/2, \infty)$ in Definition 1.1 as the inverse of the function $f_p : [0, 1) \to [1/2, \infty)$ given for $t \in [0, 1)$ by

$$ f_p(t) = \frac{1}{2} + \frac{t}{2p} \int_0^1 \frac{u^\frac{1}{p}}{1-tu} du = \frac{1}{2} \sum_{n=0}^{\infty} \frac{t^n}{1+pn} \quad (3.1) $$

and for $t \in [0, 1/2]$ by $g_p(t) = 0$. All other functions $d_p, v_p, e_p, r_t$ and $t_{p,k}, k \ge 1$ were defined from this function $g_p$. We propose in Section 3.1 an alternative definition of $g_p$ and of the couple $(g_p, d_p)$ as solutions to a (system of) differential equation(s) and develop several properties of these functions. One difficulty when we will implement in the next section the differential equation method to determine the fluid limits of the processes $G_{p,n}$ and $D_{p,n}$ is that the differential equations characterizing $g_p$ and $(g_p, d_p)$ are not Lipschitz in the neighborhood of $t = 1/2$, which is the source of technical difficulties in the proof of Theorem 1.2. For this reason, we need to approximate these differential equations by smoother ones, which is done in Section 3.2. Last, Section 3.3 is devoted to a system of differential equations satisfied by the functions $t_{p,k}, k \ge 1$.
## 3.1 The functions $g_p, d_p, v_p, e_p$ and $r_p$

We will see in the forthcoming Lemma 3.3 and Lemma 3.4 (these lemmas are proved in a more general context and therefore postponed to the next section) that the function $g_p : [1/2, \infty) \to [0, 1)$ is the unique strictly increasing solution to the equation

$$g'(t) = \frac{2pg(t)(1-g(t))}{1-2t(1-g(t))}, \quad t > 1/2, \quad \text{with } g(1/2) = 0, \qquad (E_{(0)})$$

and that there is a unique solution of strictly increasing functions to the system of equations

$$\left\{ \begin{array}{l} g'(t) = \frac{2pg(t)(1-g(t))^2}{1-2t+g(t)+2d(t)}, \quad t > \frac{1}{2}, \quad \text{with } g(1/2) = d(1/2) = 0 \qquad (\tilde{E}_{(0)}) \\ d'(t) = 2(1-p)g(t)(1-g(t)) + g(t)^2 \end{array} \right. $$

which is denoted $(g_p, d_p)$, with $g_p$ as above. There is no conflict of notation here, since Proposition 3.1 below shows that $d_p$ indeed corresponds to its definition via $g_p$ in (1.3).

Given the relations (1.2), the functions $v_p, e_p, r_p$ are defined for $t \ge 0$ by

$$v_p(t) = 1 - g_p(t); \quad e_p(t) = t - g_p(t) - d_p(t); \quad r_p(t) = \frac{e_p(t)}{v_p(t)},$$

and, again, Proposition 3.1 shows that this corresponds to their definitions in the statement of Theorem 1.6.

**Proposition 3.1.** 1) For $t \in [0, 1/2]$, $g_p(t) = d_p(t) = 0$, $v_p(t) = 1$, $e_p(t) = r_p(t) = t$.

2) The functions $g_p, d_p, v_p, e_p, r_p$ are infinitely differentiable on $(1/2, \infty)$, with $g'_p(1/2^+) = 2(1+p) = -v'_p(1/2^+)$, $d'_p(1/2^+) = 0$, $e'_p(1/2^+) = -1-2p$, $r'_p(1/2^+) = -p$.

3) As $t \to \infty$, $1-g_p(t) = v_p(t) \sim e^{-2pt}$, $d_p(t) - t + 1 \sim e^{-2pt}$, $e_p(t) \sim te^{-4pt}$, $r_p(t) \sim te^{-2pt}$.

4) The ratio function rewrites $r_p(t) = t(1-g_p(t))$, and therefore $e_p(t) = t(1-g_p(t))^2$ and $d_p(t) = t - g_p(t) - t(1-g_p(t))^2$, for $t \ge 0$.

5) While the functions $g_p, d_p, v_p$ are monotonic on $(0, \infty)$ ($g_p$ and $d_p$ are increasing, $v_p$ is decreasing), the functions $r_p$ and $e_p$ are increasing on $(0, 1/2]$ and decreasing on $[1/2, \infty)$. In particular, $r_p(t) < 1/2$ for $t \ne 1/2$.

6) The function $g_p$ is concave on $[0, \infty)$. The function $d_p$ is convex on $[0, \infty)$.

**Proof.** Most assertions of this corollary are easy to check by using the differential equations defining $g_p$ and $d_p$ and the relations between the different functions. We leave their proof to the reader. We wish however to point out that the identity $r_p(t) = t(1-g_p(t))$, $t \ge 0$ stated in 4) is shown in the proof of the forthcoming Lemma 3.4, and we detail here the two following points:
5) The function $r_p$ is decreasing on $[1/2, \infty)$ (note that this implies that $e_p = r_p v_p$ is also decreasing on $[1/2, \infty)$). Indeed, to see this use that $r_p(t) = t(1 - g_p(t))$ and note that this function is decreasing on $[1/2, \infty)$ if and only if $t \mapsto f_p(t)(1 - t)$ is decreasing on $[0, 1)$. Using the series representation (3.1) of $f_p$, we get that

$$f_p(t)(1-t) = \frac{1}{2} - \frac{p}{2} \sum_{n=0}^{\infty} \frac{t^{n+1}}{(1+pn)(1+p(n+1))}$$

which is clearly decreasing.

6) The concavity of $g_p$ is a consequence of the convexity of $f_p$ on $[0, 1)$, which is an immediate consequence of the series representation of $f_p$. To see the convexity of $d_p$, note that $d_p'' = 2g_p'(1 - p + 2pg_p)$ on $[1/2, \infty)$ (and 0 otherwise), which is positive. □

Next, in order to establish the asymptotic behavior of the absorption times $A_{p,n}^{(k)}$, $A_{p,n}^{(k+)}$ stated in Theorem 1.9, we also emphasize the following identity.

**Lemma 3.2.** Recalling that $\gamma_E$ denotes Euler's constant and $\psi$ the digamma function, defined by $\psi(x) = \frac{\Gamma'(x)}{\Gamma(x)}$ with $\Gamma$ the gamma function, we have

$$(1-p) \int_{0}^{\infty} (1-g_p(t))dt = \frac{\psi(1/p) + \gamma_E}{2}.$$

The function $\psi(1/p) + \gamma_E$ is decreasing in $p$, equal to 0 when $p = 1$ and to 1 when $p = 1/2$, and $\psi(1/p) \sim -\ln p$ when $p \to 0$.

**Proof.** Using that $g_p(t) = 0$ for $t \in [0, 1/2]$ and that $(g_p(t))_{t \ge 1/2}$ is solution to $(E_{(0)})$, we have

$$\begin{align*}
\int_0^\infty (1-g_p(t))dt &= \frac{1}{2} + \int_{1/2}^\infty \frac{1-2t(1-g_p(t))}{2pg_p(t)}g'_p(t)dt \\
&= \frac{1}{2} + \int_0^1 \frac{1-2f_p(s)(1-s)}{2ps}ds \\
&= \frac{1}{2} + \frac{1}{2p}\int_0^1 \left(1-\sum_{n=1}^\infty \frac{s^{n-1}(1-s)}{1+pn}\right)ds \\
&= \frac{1}{2} + \frac{1}{2p} - \frac{1}{2p}\left(\sum_{n=1}^\infty \frac{1}{(1+pn)n} - \sum_{n=1}^\infty \frac{1}{(1+pn)(n+1)}\right).
\end{align*}$$

We then use that

$$\psi(x+1) = -\gamma_E + \sum_{n=1}^{\infty} \frac{x}{n(n+x)} \quad \text{for } x \ge 0,$$

(see e.g. [29]) and that $\psi(x+1) = \psi(x) + 1/x$ for $x > 0$ (a trivial consequence of the relation $\Gamma(x+1) = x\Gamma(x)$) to get

$$\begin{align*}
\int_0^1 (1 - g_p(t)) dt &= \frac{1}{2} + \frac{1}{2p} \left( \frac{1}{1-p} (\psi(1/p) + \gamma_E) - (\psi(1/p) + \gamma_E + p) \right) \\
&= \frac{\psi(1/p) + \gamma_E}{2(1-p)}.
\end{align*}$$
Last, the above series representation of $\psi$ shows that it is increasing, with $\psi(1) + \gamma_E = 0$ and $\psi(2) + \gamma_E = 1$. Moreover $\psi(x) \sim \ln(x)$ when $x \to \infty$, which gives the asymptotic behavior of the integral when $p \to 0$. $\square$

## 3.2 Approximation

In order to introduce more smoothness, we consider the following equation for any $\varepsilon \ge 0$, generalizing thus $(E_{(0)})$:

$$g'(t) = \frac{2pg(t)(1-g(t))}{1-2(t+\varepsilon)(1-g(t))}, \quad t > 1/2. \qquad (E_{(\varepsilon)})$$

For $a \in [0, 1)$, an increasing continuously differentiable function $g : [1/2, \infty) \to [a, 1)$ such that $g(1/2) = a$ and $g$ verifies $(E_{(\varepsilon)})$ is called a solution to $(E_{(\varepsilon)})$ starting from $a$. This implies in particular that $g(t) \to 1$ as $t \to \infty$ and that $1 - 2(t + \varepsilon)(1 - g(t)) > 0$ for all $t > 1/2$.

**Lemma 3.3.** 1) For $\varepsilon \ge 0$ and $a \in (\frac{2\varepsilon}{1+2\varepsilon}, 1)$, there exists a unique solution to $(E_{(\varepsilon)})$ starting from $a$. We denote it here by $g_p^{(\varepsilon,a)}$.

2) Let $\frac{2\varepsilon}{1+2\varepsilon} < a < b < 1$, then $g_p^{(\varepsilon,a)}(t) < g_p^{(\varepsilon,b)}(t)$ for all $t \ge \frac{1}{2}$ and

$$\sup_{t \ge 1/2} |g_p^{(\varepsilon,a)}(t) - g_p^{(\varepsilon,b)}(t)| \le |b-a|.$$

3) Take $0 < \varepsilon_1 < \varepsilon_2$ and $a > \frac{2\varepsilon_2}{1+2\varepsilon_2}$. Then $g_p^{(\varepsilon_1,a)}(t) < g_p^{(\varepsilon_2,a)}(t)$ for all $t \ge \frac{1}{2}$.

4) There exists a unique solution to $(E_{(0)})$ starting from 0, which is our function $g_p$ defined as the inverse of the function $f_p$ (3.1). In particular $g_p(\cdot + \varepsilon)$ is the solution to $(E_{(\varepsilon)})$ starting from $g_p(1/2 + \varepsilon)$.

**Proof.** 1) We could use the Cauchy-Lipschitz theorem but prefer to give here a direct proof "by hands", that gives explicitly the inverse of $g_p^{(\varepsilon,a)}$ and adapts immediately to prove the point 4) - for which Cauchy-Lipschitz does not apply. Assume that $g_p^{(\varepsilon,a)}$ exists and let $f_p^{(\varepsilon,a)} : [a, 1) \to [1/2, \infty)$ denotes its inverse. Then $f_p^{(\varepsilon,a)}$ is solution to the linear differential equation

$$f'(t) = \frac{1 - 2(f(t) + \varepsilon)(1 - t)}{2pt(1 - t)}, \quad t \in [a, 1]$$

and one easily checks that it writes

$$f_p^{(\varepsilon,a)}(t) = \frac{1}{2} - \varepsilon + \frac{\varepsilon a^{1/p}}{t^{1/p}} + \frac{1}{2pt^{1/p}} \int_a^t \frac{u^{1/p}}{1-u} du.$$
This shows that $g_p^{(\varepsilon,a)}$ is uniquely determined, if it exists. Its existence will be proved if we show that $f_p^{(\varepsilon,a)}$ is strictly monotone, that is $(f_p^{(\varepsilon,a)}(t) + \varepsilon)(1-t) < 1/2$ for all $t \in [a, 1)$. In that aim, note that

$$
\begin{align*}
f_p^{(\varepsilon,a)}(t) + \varepsilon &= \frac{1}{2} + \frac{\varepsilon a^{1/p}}{t^{1/p}} + \frac{t}{2p} \int_{a/t}^{1} \frac{u^{1/p}}{1-tu} du \\
&\le \frac{1}{2} + \frac{\varepsilon a^{1/p}}{t^{1/p}} + \frac{t}{2p(1-t)} \int_{a/t}^{1} u^{1/p} du \\
&\le \frac{1}{2} + \frac{\varepsilon a^{1/p}}{t^{1/p}} + \frac{t}{2p(1-t)} \cdot \frac{1-(a/t)^{1+\frac{1}{p}}}{1+1/p}
\end{align*}
$$

and then

$$
\begin{align*}
(f_p^{(\varepsilon,a)}(t) + \varepsilon)(1-t) &\le \frac{1-t}{2} + \varepsilon a^{1/p} t^{-1/p} (1-t) + \frac{t}{2(p+1)} (1 - (a/t)^{1+\frac{1}{p}}) \\
&= \frac{1}{2} + \frac{h(t)}{t^{1/p}}
\end{align*}
$$

with

$$
h(t) = \varepsilon a^{1/p} (1-t) - \frac{pt^{1+\frac{1}{p}}}{2(p+1)} - \frac{a^{1+\frac{1}{p}}}{2(p+1)}
$$

a decreasing function on $[a, 1)$. Consequently, for every $t \in [a, 1)$ we have $h(t) \le h(a) = a^{1/p} (\varepsilon - a (\varepsilon + 1/2))$ and thus $(f_p^{(\varepsilon,a)}(t) + \varepsilon)(1-t) < 1/2$ as soon as $a > \frac{2\varepsilon}{1+2\varepsilon}$.

2) The function $f_p^{(\varepsilon,a)}$ defined above is in fact well-defined for all $t \in (0,1)$, and for a fixed $t$, $a \in (\frac{2\varepsilon}{1+2\varepsilon}, 1) \mapsto f_p^{(\varepsilon,a)}(t)$ is decreasing. This implies that $g_p^{(\varepsilon,a)}(t) < g_p^{(\varepsilon,b)}(t)$ for $t \ge 1/2$. Then note that for $s > 1/2$, the function

$$
x \in \left(1 - \frac{1}{2s}, 1\right) \mapsto G(s, x) := \frac{2px(1-x)}{1 - 2s(1-x)}
$$

is positive, decreasing. Finally write for $t > 1/2$

$$
\begin{align*}
0 \le g_p^{(\varepsilon,b)}(t) - g_p^{(\varepsilon,a)}(t) &= b - a + \int_{1/2}^{t} G(s, g_p^{(\varepsilon,b)}(s)) - G(s, g_p^{(\varepsilon,a)}(s)) \, ds \\
&\le b - a.
\end{align*}
$$

3) Here we just use that for any $t \ge a$, the function,

$$
\varepsilon \in (0, \infty) \mapsto \frac{1}{2} - \varepsilon + \frac{\varepsilon a^{1/p}}{t^{1/p}} + \frac{1}{2pt^{1/p}} \int_a^t \frac{u^{1/p}}{1-u} du
$$

is decreasing.

4) We proceed as in point 1) and show similarly that $f_p(t)(1-t) < 1/2$ for every $t \in (0, 1)$ which leads to the result. $\square$
We now turn to an approximation of $(\tilde{E}_{(0)})$. For $\varepsilon \ge 0$ consider

$$ egin{cases} g'(t) = \frac{2pg(t)(1-g(t))^2}{1-2(t+\varepsilon)+g(t)+2d(t)}, & t > \frac{1}{2}. \\ d'(t) = 2(1-p)g(t)(1-g(t)) + g(t)^2 & t \le \frac{1}{2}. \end{cases} \quad (\tilde{E}_{(\varepsilon)}) $$

We call solution to $(\tilde{E}_{(\varepsilon)})$ starting from $(a, b) \in [0, 1) \times [0, \infty)$, a couple of strictly increasing continuously differentiable functions $(g, d) : [1/2, \infty) \to [a, 1) \times [b, \infty)$ such that $g(1/2) = a$, $d(1/2) = b$ and $(g, d)$ verifies $(\tilde{E}_{(\varepsilon)})$, which implicitly means that $1 - 2(t + \varepsilon) + g(t) + 2d(t) > 0$ for every $t > 1/2$.

For $\varepsilon \ge 0$ and $(a, b) \in [0, 1) \times [0, \infty)$, we set

$$ \delta_{(a,b)}(\varepsilon) = \frac{\varepsilon - b - a^2/2}{(1 - a)^2} $$

(which may be negative).

**Lemma 3.4.** Consider $\varepsilon \ge 0$ and $(a, b) \in [0, 1) \times [0, \infty)$ such that $\delta_{(a,b)}(\varepsilon) \ge 0$.

1) If $(g, d)$ is a solution to $(\tilde{E}_{(\varepsilon)})$ starting from $(a, b)$ then $g$ is a solution to $(E_{(\delta_{(a,b)}(\varepsilon))})$ starting from $a$.

2) If either $a > \frac{2\delta_{(a,b)}(\varepsilon)}{1+2\delta_{(a,b)}(\varepsilon)}$ or $a = 0$ and $b = \varepsilon$, there exists a unique solution to $(\tilde{E}_{(\varepsilon)})$ starting from $(a, b)$. In particular, there exists a unique solution to $(\tilde{E}_{(0)})$ starting from $(0, 0)$, denoted by $(g_p, d_p)$, with $g_p$ the inverse of $f_p$ (3.1).

**Proof.** 1) Consider $(g, d)$ a solution to $(\tilde{E}_{(\varepsilon)})$ starting from $(a, b)$ and set

$$ r(t) = \frac{t + \varepsilon - g(t) - d(t)}{1 - g(t)}, \quad t \ge 1/2. $$

The first part of $(\tilde{E}_{(\varepsilon)})$ rewrites for $t > 1/2$

$$ g'(t) = \frac{2pg(t)(1 - g(t))}{1 - 2r(t)}. $$

Our goal is to prove that $r(t) = (t + \delta_{(a,b)}(\varepsilon))(1 - g(t))$ for every $t \ge 1/2$ which will yield the claim. In that aim set for $t \ge 1/2$,

$$ h(t) = r(t) - (t + \delta_{(a,b)}(\varepsilon))(1 - g(t)). $$

By definition of $\delta_{(a,b)}(\varepsilon)$, $h(1/2) = 0$. Then, for $t > \frac{1}{2}$

$$ egin{aligned} h'(t) &= \frac{1 - g'(t) - d'(t)}{1 - g(t)} + \frac{g'(t)}{1 - g(t)}r(t) - (1 - g(t)) + (t + \delta_{(a,b)}(\varepsilon))g'(t) \\ &= -h(t)\frac{g'(t)}{1 - g(t)} \end{aligned} $$
which implies that $h$ is identically zero.

2) When $a > 2\delta_{(a,b)}(\varepsilon)/(1+2\delta_{(a,b)}(\varepsilon))$ or $a = \delta_{(a,b)}(\varepsilon) = 0$, Lemma 3.3 gives the existence of a solution $g$ to $(E_{(\delta_{(a,b)}(\varepsilon))})$ starting from $a$. Defining then $d$ from $g$ by

$$d(t) = b + \int_{1/2}^{t} (2(1-p)g(s)(1-g(s)) + g^2(s)) \, ds, \quad t \ge \frac{1}{2},$$

one sees that $(g, d)$ is a solution $(\tilde{E}_{(\varepsilon)})$ starting from $(a, b)$ (using the same strategy as above with the ratio function $r$).

To prove the uniqueness, we use 1) together with Lemma 3.3 which gives the uniqueness of a solution $g$ to $(E_{(\delta_{(a,b)}(\varepsilon))})$ starting from $a$ (this function being $g_p$ when $a = \delta_{(a,b)}(\varepsilon) = 0$). The function $d$ is then uniquely determined from $g$. □

### 3.3 The functions $t_{p,k}$

We now turn to the functions $t_{p,k}$ arising as the scaling limits of the number of trees of size $k$, $k \ge 1$, which are defined from the function $g_p$ by

$$t_{p,k}(t) = \frac{k^{k-2}}{k!} (2t)^{k-1} (1-g_p(t))^k e^{-2kt(1-g_p(t))}.$$

**Proposition 3.5.** The sequence of functions $(t_{p,k}, k \ge 1)$ is the unique solution to the following system of differential equations:

$$\left\{ \begin{array}{l} t'_{k}(t) = \sum_{i+j=k} i j t_{i}(t) t_{j}(t) - 2 k t_{k}(t) (1 - (1-p)g_{p}(t)), \quad t \ge 0, \\ t_{1}(0) = 1; \quad t_{k}(0) = 0 \quad \text{for } k \ge 2. \end{array} \right.$$

**Proof.** For the uniqueness of solutions to this system, note that if $(t_k, k \ge 1)$ is a solution to this equation, then $t_1$ is the solution to a linear differential equation of the first order, and so it is uniquely determined by its initial condition $t_1(0) = 1$. Then we proceed by induction on $k$, noticing that, given the functions $t_i, i \le k-1$, the function $t_k$ is also solution to a linear differential equation of the first order and so is uniquely determined by its value at $t = 0$.

To prove the existence, we just have to check that the functions $t_{p,k}, k \ge 1$ are solutions. Regarding the initial conditions, we clearly have that $t_{p,1}(0) = 1$ since $g_p(0) = 0$, and $t_{p,k}(0) = 0$ for $k \ge 2$. Then, setting $u_k(t) = t_k(t)/(t_1(t))^k$ for $k \ge 1$, we note that the system of equations rewrites

$$\left\{ \begin{array}{l} t'_{1}(t) = -2t_{1}(t)(1 - (1-p)g_{p}(t)), \quad t_{1}(0) = 1 \\ u'_{k}(t) = \sum_{i+j=k} i j u_{i}(t) u_{j}(t), \quad u_{k}(0) = 0 \quad \text{for } k \ge 2 \end{array} \right. \quad t \ge 0.$$
We immediately see from the definition of $t_{p,1}$ and $(E_{(0)})$ that $t'_{p,1}(t) = -2t_{p,1}(t)(1 - (1-p)g_p(t))$, $\forall t \ge 0$. Next, consider the functions

$$u_{p,k}(t) := \frac{t_{p,k}(t)}{(t_{p,1}(t))^k} = \frac{k^{k-2}}{k!} (2t)^{k-1}, \quad t \ge 0$$

and write for $k \ge 2$

$$\sum_{i+j=k} i j u_{p,i}(t) u_{p,j}(t) = (2t)^{k-2} \cdot \sum_{i=1}^{k-1} \frac{i^{i-1}}{i!} \cdot \frac{(k-i)^{k-i-1}}{(k-i)!} \\ = \frac{2k^{k-3}}{(k-2)!} \cdot (2t)^{k-2}. \quad (\text{by (A.1)})$$

The left-hand side is equal to $u'_{p,k}(t)$, which shows that the functions $t_{p,k}$, $k \ge 1$ are indeed solutions to the system of differential equations of the statement of the proposition. $\square$

# 4 Convergence to the fluid limit

This section is devoted to the proof of Theorem 1.2 and the ensuing results Theorem 1.6, Corollary 1.7 and Corollary 1.8. As announced in the Introduction, we will use the differential equation method as developed by Wormald (see Theorem A.4 in the Appendix) for processes with relatively small one-step jumps, which are approximated by sufficiently smooth functions. To this end, we start by implementing preliminary results in Section 4.1. Among other things, we recall there that the processes $G_{p,n}$ and $D_{p,n}$ are respectively of order $n^{2/3}$ and $n^{1/3}$ at time $\lfloor n/2 \rfloor$. So, immediately, these processes divided by $n$ and accelerated in time by a factor $n$ converge to 0 uniformly on the interval $[0, 1/2]$, and in the rest of the section we can focus on the interval $[1/2, \infty)$. Since the differential equations $(E_{(0)})$ and $(\tilde{E}_{(0)})$ involving $g_p$ and $d_p$ do not satisfy the necessary Lipschitz assumptions at the critical point $t = 1/2$, Wormald's theorem cannot be applied directly around that point. We will therefore start by proving the fluid limit for the processes beyond time $(1/2 + \varepsilon)n$, for $\varepsilon > 0$, see Section 4.3, after having setting up suitable estimates for the process $G_{p,n}$ at time $(1/2 + \varepsilon)n$ in Section 4.2. We will then proceed by approximation, letting $\varepsilon$ tends to 0, to conclude the proof of Theorem 1.2 in Section 4.4. Theorem 1.6 and Corollaries 1.7 and 1.8, are then proved in Sections 4.5 and 4.6 respectively.

We recall that $F_{p,n}$ denotes the filtration generated by the process $(G_{p,n}, D_{p,n})$.

## 4.1 Preliminaries

### 4.1.1 Approximating a process via its conditional jumps

A key point underlying our proofs and the differential equation method is to approximate a sequence of processes with small (in $n$) variations by its conditional jumps. Formally, we will need the following
consequence of Azuma-Hoeffding inequality.

**Lemma 4.1.** Let $(u_n)_{n \in \mathbb{N}}$ be a deterministic sequence of positive real numbers. For each $n \in \mathbb{N}$, let $(Y_n(m))_{m \in \mathbb{Z}_+}$ be a stochastic process starting from $Y_n(0) = 0$ and such that $|\Delta Y_n(m)| \le u_n$ for every $m \in \mathbb{Z}_+$. Let then $(G_n(m))_{m \in \mathbb{Z}_+}$ denote the filtration generated by the process $Y_n$, and consider $T_n$ a stopping time such that $T_n \le An$ almost surely, for some deterministic $A > 0$ independent of $n$. Then, for all $\varepsilon > 0$,

$$ \mathbb{P}\left(\left|Y_n(\lfloor An \rfloor) - Y_n(T_n) - \sum_{m=T_n}^{\lfloor An \rfloor-1} \mathbb{E}[\Delta Y_n(m) | \mathbf{G}_n(m)]\right| \ge \varepsilon\right) \le 2 \exp\left(-\frac{\varepsilon^2}{8Anu_n^2}\right). $$

In particular, when $u_n = o(n^{1/2})$,

$$ \frac{Y_n(\lfloor An \rfloor) - Y_n(T_n) - \sum_{m=T_n}^{\lfloor An \rfloor-1} \mathbb{E}[\Delta Y_n(m) | \mathbf{G}_n(m)]}{n} \xrightarrow[n \to \infty]{\mathbb{P}} 0. $$

**Proof.** For each $n \in \mathbb{N}$, introduce the process $M_n$ defined by $M_n(0) = 0$ and

$$ M_n(m) = \sum_{k=0}^{m-1} (\Delta Y_n(k) - \mathbb{E}[\Delta Y_n(k) | \mathbf{G}_n(k)]), \quad m \ge 1. $$

This defines a martingale (with respect to the filtration $G_n$) with bounded jumps: $|\Delta M_n(m)| \le 2u_n$, $\forall m \in \mathbb{Z}_+$. The stopped process defined by $M_n^{T_n}(m) = M_n(T_n \wedge m)$ is also a martingale, and so is $M_n - M_n^{T_n}$. The jumps of this last martingale are uniformly bounded by $2u_n$ and we conclude by applying Azuma-Hoeffding inequality to $M_n - M_n^{T_n}$ at time $\lfloor An \rfloor$. $\square$

### 4.1.2 The processes before time $n/2$

From [12, 34], the size of the gel $G_{p,n}$ and of the number of discarded edges $D_{p,n}$ are respectively of order $n^{2/3}$ and $n^{1/3}$ at time $\lfloor n/2 \rfloor$ (in the sense that appropriately normalized those random variables have a limit in distribution). Which we summarize roughly as

$$ \sup_{t \le 1/2} \frac{G_{p,n}(\lfloor nt \rfloor)}{n^{2/3}} = \frac{G_{p,n}(\lfloor n/2 \rfloor)}{n^{2/3}} = O_{\mathbb{P}}(1); \quad \sup_{t \le 1/2} \frac{D_{p,n}(\lfloor nt \rfloor)}{n^{2/3}} = \frac{D_{p,n}(\lfloor n/2 \rfloor)}{n^{2/3}} = o_{\mathbb{P}}(1). \quad (4.1) $$

### 4.1.3 The forest part of $F_{p,n}$ is never too supercritical

An important point in our approach is to evaluate the criticality of the forest part of the graphs $F_{p,n}(m)$, $m \in \mathbb{Z}_+$, with the vocabulary of uniform random forests of Section 2.1, see in particular Proposition 2.3 and the following paragraph. From the relations (1.2), the number of vertices $V_{p,n}(m)$ and number of edges $E_{p,n}(m)$ in the forest part of the graph $F_{p,n}(m)$ verify

$$ 2E_{p,n}(m) - V_{p,n}(m) = 2m - n - G_{p,n}(m) - 2D_{p,n}(m). \quad (4.2) $$
The sub/sur/criticality is determined by the asymptotic position of this quantity relatively to $(V_{p,n}(m))^{2/3}$. Clearly, the forest part of $F_{p,n}(m)$ is (sub)critical when $m \le n/2$ and truly subcritical when $m = \lfloor n(1/2 - \varepsilon) \rfloor$ for some $\varepsilon > 0$.

The lemma below shows that for $m \ge n/2$ also the forest part of the graph $F_{p,n}$ cannot be "too supercritical". It will be crucial in the proof of the key Proposition 4.3, which in turn implies that the forest part of the graph $F_{p,n}(m)$ is subcritical with high probability when $m = \lfloor n(1/2 + \varepsilon) \rfloor$ for some $\varepsilon > 0$. Heuristically, the idea of the proof of the lemma below is that if the forest were supercritical at some time, it would contain a giant tree, which would freeze quickly with high probability, which then would lower down the criticality.

**Lemma 4.2.** For every $A \in (1/2, 1)$, there exists $c_A > 0$ such that for $n$ large enough

$$ \mathbb{P} \left( \exists m \in [n/2, An] : 2E_{p,n}(m) - V_{p,n}(m) \ge \ln(n)^3 n^{2/3} \right) \le e^{-c_A \ln(n)^2}. $$

**Remark.** This lemma can in fact be extended to all $A > 1/2$. To do this, the proof should be refined. As we will only need the version with $A \in (1/2, 1)$ in the following, we will leave it as is.

**Proof.** Fix $A \in (1/2, 1)$. Consider the stopping time

$$ T_n := \inf \left\{ m \ge n/2 : 2E_{p,n}(m) - V_{p,n}(m) \ge \ln(n)^3 n^{2/3} \right\} $$

and the random time

$$ S_n := \inf \left\{ s \in [n/2, T_n] \cap \mathbb{Z}_+ : \frac{\ln(n)^3 n^{2/3}}{2} \le 2E_{p,n}(m) - V_{p,n}(m) < \ln(n)^3 n^{2/3} \quad \forall m \in [s, T_n) \right\} $$

(with the convention $\inf\{\emptyset\} = \infty$). Using that the positive jumps of the process $m \mapsto 2E_{p,n}(m) - V_{p,n}(m)$ are smaller or equal to 2, we see that for $n$ not too small $\{T_n < \infty\} \subset \{S_n < \infty\}$ and that when $T_n < \infty$, $2E_{p,n}(S_n) - V_{p,n}(S_n) \le \ln(n)^3 n^{2/3}/2 + 2$. This in turn implies that for all $m \in [S_n, S_n + n^{2/3}]$,

$$ \frac{\ln(n)^3 n^{2/3}}{2} \le 2E_{p,n}(m) - V_{p,n}(m) \le 2E_{p,n}(S_n) - V_{p,n}(S_n) + 2n^{2/3} \le \frac{\ln(n)^3 n^{2/3}}{2} + 2n^{2/3} + 2. $$

Consequently,

$$ \{T_n \le An\} \subset \bigcup_{s=\lceil \frac{n}{2} \rceil}^{\lfloor An \rfloor} A_n(s) \qquad (4.3) $$

with, for $s \in \mathbb{Z}_+$,

$$ A_n(s) = \left\{ \forall m \in [s, s + n^{2/3}], \frac{\ln(n)^3 n^{2/3}}{2} \le 2E_{p,n}(m) - V_{p,n}(m) \le \frac{\ln(n)^3 n^{2/3}}{2} + 2n^{2/3} + 2 \right\}. $$

Heuristically, on $A_n(s)$ the forest part of the graph is supercritical over the time interval $[s, s + n^{2/3}]$ and this supercriticality hardly varies. In particular, the vertices of a tree of size larger than $2n^{2/3} + 5$ at time $s$, if there are any, will not be frozen at time $\lfloor s + n^{2/3} \rfloor$.
Let $T_{p,n}^{(1)}(s)$ be the largest tree in the forest at time $s$ (if several trees have the largest size, we choose such a tree at random) and $\#T_{p,n}^{(1)}(s)$ its size. We use the splitting

$$A_n(s) \subset \left\{ \begin{array}{l} \#T_{p,n}^{(1)}(s) > \ln(n)n^{2/3}, \text{ the vertices of } T_{p,n}^{(1)}(s) \text{ are not frozen at time } \lfloor s + n^{2/3} \rfloor \\ \cup \left\{ \#T_{p,n}^{(1)}(s) \le \ln(n)n^{2/3}, \frac{\ln(n)^3 n^{2/3}}{2} \le 2E_{p,n}(s) - V_{p,n}(s) \le \ln(n)^3 n^{2/3} \right\} \end{array} \right\}$$

to obtain a relevant upper bound for $\mathbb{P}(A_n(s))$. Note that at each step in the process $F_{p,n}$, the probability that the new arriving edge creates a cycle in a given tree of size $k$ (sending therefore this tree in the gel) is $\frac{k(k-1)}{n(n-1)}$. Consequently,

$$\mathbb{P} \left( \#T_{p,n}^{(1)}(s) > \ln(n)n^{2/3}, \text{ the vertices of } T_{p,n}^{(1)}(s) \text{ are not frozen at time } \lfloor s + n^{2/3} \rfloor \right) \\ \le \left( 1 - \frac{\ln(n)^2 n^{4/3}}{n(n-1)} + \frac{\ln(n)n^{2/3}}{n(n-1)} \right)^{n^{2/3}} \underset{n \to \infty}{\sim} e^{-\ln(n)^2}.$$

Next, recalling that $L_1(N, M)$ denotes the size of the largest tree in a uniform random forest with $N$ vertices and $M$ edges, Proposition 1.3 yields

$$\mathbb{P} \left( \#T_{p,n}^{(1)}(s) \le \ln(n)n^{2/3}, \frac{\ln(n)^3 n^{2/3}}{2} \le 2E_{p,n}(s) - V_{p,n}(s) \le \ln(n)^3 n^{2/3} \right) \\ \le \mathbb{E} \left[ \mathbb{P} \left( L_1(V_{p,n}(s), E_{p,n}(s)) \le \frac{\ln(n)}{(1-A)^{2/3}} \cdot V_{p,n}(s)^{2/3}, \frac{\ln(n)^3}{2} \cdot V_{p,n}(s)^{2/3} \le 2E_{p,n}(s) - V_{p,n}(s) \le \frac{\ln(n)^3}{(1-A)^{2/3}} \cdot V_{p,n}(s)^{2/3} \mid \mathbf{F}_{p,n}(s) \right) \right]$$

where we used that $(1-A)n \le V_{p,n}(s) \le n$ for $s \le \lfloor An \rfloor$ and recall that $\mathbf{F}_{p,n}$ is the filtration generated by $(V_{p,n}, E_{p,n})$. Recall also that $A < 1$. Lemma 2.8, whose assumptions are clearly satisfied here, implies that the conditional probability above is smaller than $c_1(\ln(n))^{15/2}n^{2/3}e^{-c_2 \ln(n)^2}$ for deterministic constants $c_1, c_2 \in (0, \infty)$ (that depend on $A$) and all $n$ large enough, whatever $s \le \lfloor An \rfloor$. All in all, we have shown that

$$\mathbb{P}(A_n(s)) \le e^{-c_3 \ln(n)^2}$$

for some $c_3 \in (0, \infty)$ and all $n$ large enough, whatever $s \le \lfloor An \rfloor$.

Finally, applying the union bound to (4.3) gives the result. $\square$

## 4.2 The gel just beyond the critical window

The aim of this section is to provide the following bounds for the gel size just beyond the critical window. This will allow us to implement the stochastic differential method in the next section.
**Proposition 4.3.** For every $p \in (0,1]$, there are constants $c(p), C(p) \in (0, \infty)$ such that for $\varepsilon > 0$ small enough

$$ \mathbb{P}\left(G_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) \in \left[(2+c(p))\varepsilon n; C(p)\varepsilon n\right]\right) \underset{n\to\infty}{\longrightarrow} 1. $$

Observe with (4.2) that this implies that the forest part of the graph at time $\lfloor(1/2 + \varepsilon)n\rfloor$ verifies with high probability

$$ \begin{aligned} 2E_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) - V_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) &= 2\varepsilon n - G_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) - 2D_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) \\ &\le -c(p)\varepsilon V_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) \end{aligned} $$

which indicates that the forest is in the subcritical regime. Since the largest tree in a subcritical forest is "small" (Lemma 2.6), so are the jumps of $G_{p,n}$. This will help us to verify the boundedness hypothesis of the differential equation method (Theorem A.4).

The proof of Proposition 4.3 is quite involved and divided into several steps. The difficulty lies in proving the lower bound $(2+c(p))\varepsilon n$. For the upper bound, we can simply use a comparison with the standard Erdős-Rényi graph, which yields a constant $C(p)$ which could be any number larger than 4. So $C(p)$ does not depend on $p$ with our approach (we let however the notation depends on $p$ since in principle one could obtain the statement with any constant larger than $2(1+p)$).

### 4.2.1 Proof of the lower bound

Since $p > 0$ we can choose $c(p) > 0$ and define $\tilde{c}(p)$ such that:

$$ 2+c(p) < \frac{2(1+p)^2}{1+2p} \quad \text{and} \quad \tilde{c}(p) = \frac{2+c(p)}{2(1+p)} \in (0,1). $$

Our goal is to show that for $\varepsilon \in (0, 1/2)$ sufficiently small, the probability of the event

$$ A_n(\varepsilon) := \left\{ G_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) < (2+c(p))\varepsilon n \right\} $$

converges to 0 as $n \to \infty$.

**Heuristics and preparatory work.** Our aim is to approximate $G_{p,n}(\lfloor\frac{n}{2}+\varepsilon n\rfloor)$ by the sum of the conditional expectations of its jumps $\mathbb{E}[\Delta G_{p,n}(m)|\mathbf{F}_{p,n}(m)]$, using Lemma 4.1, and to evaluate these expectations with the help of Corollary 2.5. There are several obstacles on our way to implement this properly. We will therefore have to position ourselves a little beyond the exit of the critical window and consider only small jumps. Heuristically, we will use the approximation

$$ G_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) \approx G_{p,n}\left(\left\lfloor\frac{n}{2}+\tilde{c}(p)\varepsilon n\right\rfloor\right) + \sum_{m=\left\lfloor\frac{n}{2}+\tilde{c}(p)\varepsilon n\right\rfloor}^{\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor-1} \mathbb{E}\left[\Delta G_{p,n}(m)1_{\{\Delta G_{p,n}(m) \le n^{1/4}\}}\left|\mathbf{F}_{p,n}(m)\right.\right] $$
to get a lower bound for $G_{p,n}$ ($\lfloor \frac{n}{2} + \varepsilon n \rfloor$), using Lemma 4.2 to get a lower bound for $G_{p,n}$ ($\lfloor \frac{n}{2} + \tilde{c}(p)\varepsilon n \rfloor$) and Corollary 2.5 to estimate the conditional expectations of the jumps. Even if Lemma 4.2 only gives a crude lower bound, we will be able to show that the drift of the process over the time interval $[\frac{n}{2} + \tilde{c}(p)\varepsilon n, \frac{n}{2} + \varepsilon n]$ is large enough to compensate for this shortfall. We have chosen $\tilde{c}(p)$ in such a way that it is both sufficiently large to move away from the critical window, but also small enough so that the information about the drift over $[\frac{n}{2} + \tilde{c}(p)\varepsilon n, \frac{n}{2} + \varepsilon n]$ can provide the compensation. This will be detailed in the proof of Lemma 4.4, but we already observe here that

$$A_n(\varepsilon) \subset \{ \forall m \in [\frac{n}{2} + \tilde{c}(p)\varepsilon n, \frac{n}{2} + \varepsilon n], G_{p,n}(m) \le 2(1+p)\left(m - \frac{n}{2}\right) \}. \quad (4.4)$$

Let us now introduce a series of events that all have a probability converging to 1 as $n \to \infty$ and on which it will be easier to work:

$$\bullet B_n(\varepsilon) = \left\{ \left| \sum_{m = \left\lfloor \frac{n}{2} + \tilde{c}(p)\varepsilon n \right\rfloor}^{\left\lfloor \frac{n}{2} + \varepsilon n \right\rfloor - 1} \left( \Delta G_{p,n}(m) \mathbb{1}_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} - \mathbb{E} \left[ \Delta G_{p,n}(m) \mathbb{1}_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m) \right] \right) \right| \le \varepsilon^2 n \right\}$$

$$\bullet C_n(\varepsilon) = \left\{ \left| \sum_{m = \left\lfloor \frac{n}{2} + \varepsilon n \right\rfloor}^{\left\lfloor \frac{n}{2} + \varepsilon n \right\rfloor - 1} \left( \Delta D_{p,n}(m) - \mathbb{E} \left[ \Delta D_{p,n}(m) | \mathbf{F}_{p,n}(m) \right] \right) \right| \le \varepsilon^2 n \right\} \cap \left\{ D_{p,n} \left( \frac{n}{2} \right) \le \varepsilon^2 n \right\}$$

$$\bullet D_n(\varepsilon) = \left\{ \forall m \in \left[\frac{n}{2}, \frac{n}{2} + \varepsilon n\right], G_{p,n}(m) + 2D_{p,n}(m) \ge 2m - n - \ln(n)^3 n^{2/3} \right\}.$$

Lemma 4.1 and (4.1) imply that $\mathbb{P}(B_n(\varepsilon)) \to 1$, $\mathbb{P}(C_n(\varepsilon)) \to 1$ as $n \to \infty$, while Lemma 4.2 and the identity (4.2) imply that $\mathbb{P}(D_n(\varepsilon)) \to 1$. We can therefore focus on

$$\tilde{A}_n(\varepsilon) := A_n(\varepsilon) \cap B_n(\varepsilon) \cap C_n(\varepsilon) \cap D_n(\varepsilon)$$

to prove that $\mathbb{P}(A_n(\varepsilon)) \to 0$ as $n \to \infty$.

We finish this preparatory part by a few remarks. First, since we have taken $\varepsilon$ in $(0, 1/2)$, $V_{p,n}(m) \ge (1/2 - \varepsilon)n$, $\forall m \in [0, \frac{n}{2} + \varepsilon n]$, which improves on $A_n(\varepsilon)$ in

$$V_{p,n}(m) \ge (1 - (2 + c(p))\varepsilon)n, \quad \forall m \in \left[0, \frac{n}{2} + \varepsilon n\right]. \quad (4.5)$$

Next, since (by Proposition 2.1)

$$\mathbb{E} [\Delta D_{p,n}(m) | \mathbf{F}_{p,n}(m)] = 2(1-p) \frac{G_{p,n}(m)(n - G_{p,n}(m))}{n(n-1)} + \frac{G_{p,n}(m)(G_{p,n}(m) - 1)}{n(n-1)}, \quad \forall m \ge 0,$$

there exists $c_D \in (0, \infty)$ such that

$$D_{p,n} \left( \left\lfloor \frac{n}{2} + \varepsilon n \right\rfloor \right) \le c_D \varepsilon^2 n \quad \text{on } A_n(\varepsilon) \cap C_n(\varepsilon). \quad (4.6)$$
Then, using this upper bound (4.6), we see that for $n$ large enough and all $m \ge \frac{n}{2} + \tilde{c}(p)\epsilon n$,

$$ \frac{G_{p,n}(m)}{n} \geq 2\tilde{c}(p)\epsilon - (1 + c_D)\epsilon^2 \quad \text{on } A_n(\epsilon) \cap C_n(\epsilon) \cap D_n(\epsilon). \qquad (4.7) $$

Last, using the identity $E_{p,n}(m) = m - G_{p,n}(m) - D_{p,n}(m)$, we see that for $\epsilon > 0$ small enough, on the event $\tilde{A}_n(\epsilon)$

$$ E_{p,n}(m) \geq \frac{n}{2} + \tilde{c}(p)\epsilon n - (2 + c(p))\epsilon n - c_D\epsilon^2 n \geq \left(\frac{1}{2} - \sqrt{\epsilon}\right) n \qquad (4.8) $$

for all $m \in [\frac{n}{2} + \tilde{c}(p)\epsilon n, \frac{n}{2} + \epsilon n]$.

We now turn to the proof of the following lower bound for the conditional expectations of $\Delta G_{p,n}$ on $\tilde{A}_n(\epsilon)$, which will allows us to show that $\mathbb{P}(\tilde{A}_n(\epsilon)) \to 0$, and consequently $\mathbb{P}(A_n(\epsilon)) \to 0$, as $n \to \infty$, for sufficiently small $\epsilon > 0$.

**Lemma 4.4.** There exists $c \in (0, \infty)$ such that for $\epsilon > 0$ small enough, and then $n$ large enough and every $m \in [\frac{n}{2} + \tilde{c}(p)\epsilon n, \frac{n}{2} + \epsilon n]$,

$$ \mathbb{E} \left[ \Delta G_{p,n}(m) 1_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m) \right] 1_{\tilde{A}_n(\epsilon)} \ge (2(1+p) - c\epsilon) 1_{\tilde{A}_n(\epsilon)} $$

**Proof.** Fix $\epsilon \in (0, 1/2)$ small enough such that the conclusion of (4.8) holds on $\tilde{A}_n(\epsilon)$. Corollary 2.5 and its consequence (2.2) provide $A > 0$ (depending on $\epsilon$) such that for $n$ large enough (the threshold also depends on $\epsilon$) and all $m \in [\frac{n}{2} + \tilde{c}(p)\epsilon n, \frac{n}{2} + \epsilon n]$, on the event $\tilde{A}_n(\epsilon)$:

* for $m \ge 1$ such that $2E_{p,n}(m) - V_{p,n}(m) \le -AV_{p,n}(m)^{2/3}$ and every $k \in \{1, ..., V_{p,n}(m)^{1/4}\}$

$$ \mathbb{P}(\Delta G_{p,n}(m) = k | \mathbf{F}_{p,n}(m)) \ge (1-\epsilon) \frac{k^{k-1}}{k!} \left( \frac{2E_{p,n}(m)}{V_{p,n}(m)} \right)^{k-1} e^{-2k \frac{E_{p,n}(m)}{V_{p,n}(m)}} \frac{2pG_{p,n}(m)(n - G_{p,n}(m))}{n^2} \qquad (4.9) $$

* for $m \ge 1$ such that $2E_{p,n}(m) - V_{p,n}(m) > -AV_{p,n}(m)^{2/3}$ and every $k \in \{1, ..., V_{p,n}(m)^{1/4}\}$

$$ \mathbb{P}(\Delta G_{p,n}(m) = k | \mathbf{F}_{p,n}(m)) \ge \frac{c_A}{k^{3/2}} \cdot \frac{G_{p,n}(m)(V_{p,n}(m) - E_{p,n}(m))}{n^2} \qquad (4.10) $$

where $c_A \in (0, \infty)$ only depends on $A$.

Here we used that, on $\tilde{A}_n(\epsilon)$, $E_{p,n}(m)$ and $V_{p,n}(m)$ are deterministically large as soon as $n$ is large, thanks to (4.8) and (4.5), and also that $V_{p,n}(m) - E_{p,n}(m) - 1 \ge (V_{p,n}(m) - E_{p,n}(m))/2$ for $n$ large enough, since $V_{p,n}(m) - E_{p,n}(m) = n - m + D_{p,n}(m) \ge (1/2 - \epsilon)n$ when $m \le n/2 + \epsilon n$.

We will need the existence, ensured by Lemma A.2, of $\delta > 0$ and $N_0 \in \mathbb{N}$ (depending both on $\epsilon$) such
that:

$$S_{N_0}(2z) = \sum_{k=1}^{N_0} \frac{k^k}{k!} (2z)^{k-1} e^{-2kz} \geq \frac{1-\varepsilon}{1-2z}, \quad \forall z \in [0, \frac{1}{2}-\delta] \quad (4.11)$$

$$2p \cdot (1-\varepsilon) \cdot \tilde{c}(p)\varepsilon \cdot (1-(2+c(p))\varepsilon) \cdot S_{N_0}(2z) \geq 2(1+p), \quad \forall z \in [\frac{1}{2}-\delta, \frac{1}{2}] \quad (4.12)$$

$$\sum_{k=1}^{N_0} \frac{c_A}{\sqrt{k}} \left(\frac{1}{2} - \varepsilon\right) \tilde{c}(p)\varepsilon \geq 2(1+p). \quad (4.13)$$

We then distinguish three cases to show the expected inequality of the statement for $m \in [\frac{n}{2} + \tilde{c}(p)\varepsilon n, \frac{n}{2} + \varepsilon n]$:

**Case 1**, when $2E_{p,n}(m) - V_{p,n}(m) \leq -2\delta V_{p,n}(m)$: using (4.9) and (4.11) we get that for $n$ large enough, on $\tilde{A}_n(\varepsilon)$,

$$\begin{aligned} \mathbb{E} \left[ \Delta G_{p,n}(m) 1_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m) \right] &\ge (1-\varepsilon)^2 2p \frac{G_{p,n}(m) (n - G_{p,n}(m))}{(1 - 2E_{p,n}(m)/V_{p,n}(m)) n^2} \\ &= (1-\varepsilon)^2 2p \frac{G_{p,n}(m) (n - G_{p,n}(m))^2}{(n - 2m + G_{p,n}(m) + 2D_{p,n}(m)) n^2}. \end{aligned}$$

Observe that on $\tilde{A}_n(\varepsilon)$, by definition of $A_n(\varepsilon)$, $(1 - G_{p,n}(m)/n)^2 \ge (1 - (2 + c(p))\varepsilon)^2$, and then use (4.4) and (4.6) to see that the inequality above implies

$$\begin{aligned} \mathbb{E} \left[ \Delta G_{p,n}(m) 1_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m) \right] &\ge (1-\varepsilon)^2 (1-(2+c(p))\varepsilon)^2 2p \left( 1 + \frac{2m-n-2D_{p,n}(m)}{n-2m+G_{p,n}(m)+2D_{p,n}(m)} \right) \\ &\ge (1-\varepsilon)^2 (1-(2+c(p))\varepsilon)^2 2p \left( 1 + \frac{2m-n-2c_D\varepsilon^2n}{p(2m-n)+2c_D\varepsilon^2n} \right). \end{aligned}$$

Since $m \ge n/2 + \tilde{c}(p)\varepsilon n$, the desired inequality follows in this case for some well chosen constant $c \in (0, \infty)$, independent of $\varepsilon$ and $n$.

**Case 2**, when $-2\delta V_{p,n}(m) \le 2E_{p,n}(m) - V_{p,n}(m) \le -AV_{p,n}(m)^{2/3}$: (4.9) yields that for $n$ large enough, on $\tilde{A}_n(\varepsilon)$,

$$\mathbb{E} \left[ \Delta G_{p,n}(m) 1_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m) \right] \ge (1-\varepsilon) 2p \frac{G_{p,n}(m) (n - G_{p,n}(m))}{n^2} S_{N_0} \left( \frac{2E_{p,n}(m)}{V_{p,n}(m)} \right).$$

Assume now that $\varepsilon$ is small enough such that $(1+c_D)\varepsilon \le 1$. On $\tilde{A}_n(\varepsilon)$, one then has $G_{p,n}(m) \ge \tilde{c}(p)\varepsilon n$ and $n - G_{p,n}(m) \ge (1 - (2 + c(p))\varepsilon) n$ by (4.7) and the definition of $A_n(\varepsilon)$ respectively (taking $n$ larger if necessary). The above inequality therefore leads, together with (4.12), to the lower bound

$$\mathbb{E} \left[ \Delta G_{p,n}(m) 1_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m) \right] \ge 2(1+p).$$
Case 3, when $2E_{p,n}(m) - V_{p,n}(m) > -AV_{p,n}(m)^{2/3}$: (4.10) implies that for sufficiently large $n$, on $\tilde{A}_n(\varepsilon)$,

$$ \mathbb{E} \left[ \Delta G_{p,n}(m) \mathbb{1}_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m) \right] \ge \sum_{k=1}^{N_0} \frac{c_A}{\sqrt{k}} \frac{G_{p,n}(m)(V_{p,n}(m) - E_{p,n}(m))}{n^2} \\ \ge \sum_{k=1}^{N_0} \frac{c_A}{\sqrt{k}} \left( \frac{1}{2} - \varepsilon \right) \tilde{c}(p)\varepsilon $$

where we used that for $m \in [\frac{n}{2} + \tilde{c}(p)\varepsilon n, \frac{n}{2} + \varepsilon n]$, on $\tilde{A}_n(\varepsilon)$, $G_{p,n}(m) \ge \tilde{c}(p)\varepsilon n$ by (4.7) and $V_{p,n}(m) - E_{p,n}(m) = n - m + D_{p,n}(m) \ge (1/2 - \varepsilon)n$. We conclude using (4.13). $\square$

**End of the proof of the lower bound of Proposition 4.3.** We take $\varepsilon > 0$ small enough such that the conclusion of Lemma 4.4 holds. As announced in the heuristic introduction, we use that

$$ G_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) \geq \left( G_{p,n}\left(\left\lfloor\frac{n}{2}+\tilde{c}(p)\varepsilon n\right\rfloor\right)+\sum_{m=\left\lfloor\frac{n}{2}+\tilde{c}(p)\varepsilon n\right\rfloor}^{\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor-1} \Delta G_{p,n}(m) \mathbb{1}_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} \right) $$

to get, with the definition of $B_n(\varepsilon)$ and (4.7), that on $\tilde{A}_n(\varepsilon)$

$$ G_{p,n}\left(\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor\right) \geq \left( 2\tilde{c}(p)\varepsilon n + \sum_{m=\left\lfloor\frac{n}{2}+\tilde{c}(p)\varepsilon n\right\rfloor}^{\left\lfloor\frac{n}{2}+\varepsilon n\right\rfloor-1} \mathbb{E}\left[\Delta G_{p,n}(m) \mathbb{1}_{\{\Delta G_{p,n}(m) \le n^{1/4}\}} | \mathbf{F}_{p,n}(m)\right] - (2+c_D)\varepsilon^2 n \right) \\ \geq (2\tilde{c}(p)\varepsilon n + 2(1+p)(1-\tilde{c}(p))\varepsilon n - (2+c_D+C)\varepsilon^2 n) $$

with $C \in (0, \infty)$, where we used Lemma 4.4 to get the second inequality. Since $G_{p,n}(\lfloor\frac{n}{2}+\varepsilon n\rfloor) \le (2+c(p))\varepsilon n$ on $\tilde{A}_n(\varepsilon)$ by definition of $A_n(\varepsilon)$, this implies that

$$ (2+c(p)) \geq 2\tilde{c}(p) + 2(1+p)(1-\tilde{c}(p)) - (2+c_D+C)\varepsilon. $$

Now, note that by choice and definition of $c(p), \tilde{c}(p)$, one has $(2+c(p)) < 2\tilde{c}(p) + 2(1+p)(1-\tilde{c}(p))$. The above reasoning therefore implies that $\tilde{A}_n(\varepsilon) = \emptyset$ for $\varepsilon$ sufficiently small and all $n$ large enough. So finally, since $\tilde{A}_n(\varepsilon) = A_n(\varepsilon) \cap B_n(\varepsilon) \cap C_n(\varepsilon) \cap D_n(\varepsilon)$ and the events $B_n(\varepsilon), C_n(\varepsilon), D_n(\varepsilon)$ all have a probability that converges to 1 as $n \to \infty$, we have indeed that $\mathbb{P}(A_n(\varepsilon)) \to 0$ for small values of $\varepsilon$.

### 4.2.2 Proof of the upper bound

The proof of the upper bound is easier as we can used a comparison with the standard Erdős-Rényi model. Indeed, as already observed, for any $m$, $G_{p,n}(m)$ is stochastically smaller than $C_{ER,n}(m)$, the total number of vertices involved at time $m$ in cyclic components of the Erdős-Rényi random graph. For $t > 1/2$, with high probability as $n \to \infty$, the giant component of the Erdős-Rényi graph at time
$\lfloor nt \rfloor$ is a cyclic component and the number of vertices involved in other cyclic components is bounded (see e.g. [8, Theorem 6.11]). Consequently, one has

$$ \frac{C_{ER,n}((\lfloor nt \rfloor))}{n} \xrightarrow{\mathbb{P}} g_{ER}(t) = g_1(t). $$

Since $g_{ER}(1/2) = 0$ and $g'_{ER}$ is bounded on $[1/2, \infty)$ (by $g'_{ER}(1/2^+) = 4$), one has $g_{ER}(1/2 + \varepsilon) < C\varepsilon$ for some finite $C > 4$ and all $\varepsilon \in (0, 1]$. The result follows.

This proof has the advantage of being concise, but relies on results on the standard model. Alternatively it is possible to set up a self-contained proof, based on a similar approach to that used for the lower bound, with the additional difficulty of controlling potential large jumps.

## 4.3 Differential equation method for the process beyond time $(1/2 + \varepsilon)n$

Throughout this section we let $\varepsilon > 0$, $c(p), C(p)$ be such that Proposition 4.3 holds and keep a certain amount of flexibility with $\varepsilon$, allowing us to choose it arbitrarily small if necessary. Our aim is to prove, via Wormald's theorem (Theorem A.4), that the process

$$ \left( \frac{G_{p,n}(\lfloor nt + \varepsilon n \rfloor)}{n}, \frac{D_{p,n}(\lfloor nt + \varepsilon n \rfloor)}{n} \right)_{t \ge 1/2} $$

converges in probability to a fluid limit which will approximate, when $\varepsilon$ goes to 0, the couple of functions $(g_p, d_p)$, solution to $(\tilde{E}_{(0)})$. The convergence of $(G_{p,n}(\lfloor nt \rfloor)/n, D_{p,n}(\lfloor nt \rfloor)/n)_{t \ge 1/2}$ to $(g_p, d_p)$ as settled in Theorem 1.2 will mainly follow by using the triangular inequality, see the next section.

Here we will work on the event

$$ I_n(\varepsilon) = \left\{ (2 + c(p))\varepsilon n \le G_{p,n}\left(\left\lfloor \frac{n}{2} + \varepsilon n \right\rfloor\right) \le C(p)\varepsilon n \right\} \cap \left\{ \varepsilon^3 n \le D_{p,n}\left(\left\lfloor \frac{n}{2} + \varepsilon n \right\rfloor\right) \le (2C(p) + 1)\varepsilon^2 n \right\} \quad (4.14) $$

whose probability tends to 1 as $n$ goes to infinity (at least for $\varepsilon$ small enough) as a consequence of Proposition 4.3, together with (4.1), Proposition 2.1 and Lemma 4.1 (regarding the bounds on $D_n$, we proceed similarly as around (4.6)). We will see in Lemma 4.7 that on this event, provided that $\varepsilon$ is sufficiently small, the equation $(\tilde{E}_{(\varepsilon)})$ defined in Section 3.2, has a unique solution starting at time $t = 1/2$ from $(G_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)/n, D_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)/n)$, for all $n \ge 1$, which legitimates the following definition.

**Definition 4.5.** For $\varepsilon > 0$ small enough and all $n \ge 1$, we define the (random) couple of functions $(g_{p,n}^{(\varepsilon)}(t), d_{p,n}^{(\varepsilon)}(t))_{t \ge 1/2}$ as:

* the solution to $(\tilde{E}_{(\varepsilon)})$ starting from $\left( \frac{G_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)}{n}, \frac{D_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)}{n} \right)$ on $I_n(\varepsilon)$

* $(g_p(t + \varepsilon), d_p(t + \varepsilon))_{t \ge 1/2}$ on $I_n(\varepsilon)^c$.
With this definition, we have the following convergence.

**Proposition 4.6.** For $\varepsilon > 0$ small enough,

$$ \left( \left( \left| \frac{G_{p,n} (\lfloor nt + \varepsilon n \rfloor)}{n} - g_{p,n}^{(\varepsilon)}(t) \right|, \left| \frac{D_{p,n} (\lfloor nt + \varepsilon n \rfloor)}{n} - d_{p,n}^{(\varepsilon)}(t) \right| \right) \right)_{t \ge \frac{1}{2}} \xrightarrow[n \to \infty]{\mathbb{P}} 0 $$

for the topology of uniform convergence on compacts.

The proof of Proposition 4.6 consists in verifying the different hypotheses of Theorem A.4, which is done in Section 4.3.2. To achieve this, we start by setting up some preliminary steps.

### 4.3.1 Preliminaries

**Definition of the domain.** To start with, we need to introduce a domain where the target functions are confined and within which the increments of the process are well approximated by the derivatives of the target functions. Technically, to proceed directly with Theorem A.4, it is simpler to work with processes starting from 0, so we consider the shifted process defined for $t \ge 0$ by

$$ (\tilde{g}_{p,n}^{(\varepsilon)}(t), \tilde{d}_{p,n}^{(\varepsilon)}(t)) = (g_{p,n}^{(\varepsilon)}(t + 1/2), d_{p,n}^{(\varepsilon)}(t + 1/2)). $$

The following lemma lays the foundations.

**Lemma 4.7.** For $\varepsilon > 0$ sufficiently small:

1) For all $n \ge 1$, there exists on $I_n(\varepsilon)$ a unique solution to $(\tilde{E}_{(\varepsilon)})$ starting at time $t = 1/2$ from $(G_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)/n, D_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)/n)$, so the couples $(g_{p,n}^{(\varepsilon)}, d_{p,n}^{(\varepsilon)})$ of Definition 4.5 and its shifted version $(\tilde{g}_{p,n}^{(\varepsilon)}, \tilde{d}_{p,n}^{(\varepsilon)})$ are indeed well-defined.

2) There exists a deterministic constant $\bar{\kappa}_{\varepsilon} > 0$ and, for all $A > 0$, a deterministic constant $\bar{K}_{\varepsilon,A} \in (C(p)\varepsilon, 1)$ such that simultaneously for all $t \in [0, A+1]$ and all $n \ge 1$:

(a) $\tilde{g}_{p,n}^{(\varepsilon)}(t) < \bar{K}_{\varepsilon,A}$

(b) $\frac{1 - \bar{K}_{\varepsilon,A}}{2} < \frac{t + 1/2 + \varepsilon - \tilde{g}_{p,n}^{(\varepsilon)}(t) - \tilde{d}_{p,n}^{(\varepsilon)}(t)}{1 - \tilde{g}_{p,n}^{(\varepsilon)}(t)} < \frac{1}{2} - \bar{\kappa}_{\varepsilon}$.

**Proof.** We use Lemma 3.4. In that aim, introduce

$$ a_n(\varepsilon) = \frac{G_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)}{n}, \quad b_n(\varepsilon) = \frac{D_{p,n}(\lfloor \frac{n}{2} + \varepsilon n \rfloor)}{n} \quad \text{and} \quad \delta_n(\varepsilon) = \frac{\varepsilon - b_n(\varepsilon) - a_n(\varepsilon)^2/2}{(1 - a_n(\varepsilon))^2}. $$

1) By definition of $I_n(\varepsilon)$, it is clear that for $\varepsilon > 0$ small enough, $0 < \delta_n(\varepsilon) < a_n(\varepsilon)/2$ on $I_n(\varepsilon)$. The existence and uniqueness of a solution to $(\tilde{E}_{(\varepsilon)})$ follows from Lemma 3.4 2). Moreover Lemma 3.4 1)
says that $g_{p,n}^{(\varepsilon)}$ is the unique solution to $(E_{(\delta_n(\varepsilon))})$ (this equation is defined, as $(\tilde{E}_{(\varepsilon)})$, in Section 3.2) starting from $a_n(\varepsilon)$, which will be useful below.

2) First observe that for any $\varepsilon > 0$, the couple $(g_p(\cdot + 1/2 + \varepsilon), d_p(\cdot + 1/2 + \varepsilon))$ verifies the desired inequalities (a) and (b) for well-chosen constants $\bar{\kappa}_{\varepsilon}^0 > 0$, $\bar{K}_{\varepsilon,A}^0 \in (0, 1)$, see Proposition 3.1 for details.

Then observe that for $\varepsilon > 0$ small enough, $\delta_n(\varepsilon) < 2\varepsilon$ on $I_n(\varepsilon)$. Consequently, if $\hat{g}_{p,(\varepsilon)}$ denotes the (well-defined) unique solution to $(E_{(2\varepsilon)})$ starting from $C(p)\varepsilon$, since moreover, still on $I_n(\varepsilon)$, $g_{p,n}^{(\varepsilon)}$ is the solution to $(E_{(\delta_n(\varepsilon))})$ starting from $a_n(\varepsilon) \le C(p)\varepsilon$, we have by Lemma 3.3 that $\tilde{g}_{p,n}^{(\varepsilon)}(t) = g_{p,n}^{(\varepsilon)}(t + 1/2) \le g_{p,n}^{(\varepsilon)}(A + 3/2) \le \hat{g}_{p,(\varepsilon)}(A + 3/2)$ for all $t \in [0, A + 1]$. This yields the upper bound (a) with $\bar{K}_{\varepsilon,A} = \max(\bar{K}_{\varepsilon,A}^0, \hat{g}_{p,(\varepsilon)}(A + 1)) \in (0, 1)$.

Next, working again on $I_n(\varepsilon)$, we have seen in the proof of Lemma 3.4 (up to a time shift of $1/2$) that for every $t \ge 0$

$$ \frac{t + 1/2 + \varepsilon - \tilde{g}_{p,n}^{(\varepsilon)}(t) - \tilde{d}_{p,n}^{(\varepsilon)}(t)}{1 - \tilde{g}_{p,n}^{(\varepsilon)}(t)} = (t + 1/2 + \delta_n(\varepsilon))(1 - \tilde{g}_{p,n}^{(\varepsilon)}(t)) =: \tilde{r}_{p,n}^{(\varepsilon)}(t), $$

leading to the lower bound of (b). Moreover, observe that $\tilde{r}_{p,n}^{(\varepsilon)}$ verifies

$$ \tilde{r}_{p,n}^{(\varepsilon)}(0) \le \frac{1}{2} - \frac{c(p)\varepsilon}{2} \quad \text{and} \quad \left(\tilde{r}_{p,n}^{(\varepsilon)}\right)'(t) = \left(1 - \tilde{g}_{p,n}^{(\varepsilon)}(t)\right) \left(1 - (t + 1/2 + \delta_n(\varepsilon)) \frac{2p\tilde{g}_{p,n}^{(\varepsilon)}(t)}{1 - 2\tilde{r}_{p,n}^{(\varepsilon)}(t)}\right), \quad t > 0. $$

For $\varepsilon > 0$ small enough, by continuity of $\tilde{r}_{p,n}^{(\varepsilon)}$, the time $T := \inf\{t \ge 0 : \tilde{r}_{p,n}^{(\varepsilon)}(t) \ge 1/2 - \varepsilon^2\}$ (with the usual convention $\inf\{\emptyset\} = \infty$) is strictly positive. It $T$ were finite, there would exist $\eta \in (0, T)$ such that for every $t \in [T - \eta, T]$, $\tilde{r}_{p,n}^{(\varepsilon)}(t) \ge 1/2 - 2\varepsilon^2$. As $\tilde{g}_{p,n}^{(\varepsilon)}$ is increasing and verifies $\tilde{g}_{p,n}^{(\varepsilon)}(0) \ge (2+c(p))\varepsilon$, it is easy to see that for $\varepsilon > 0$ small enough, this would lead to $(\tilde{r}_{p,n}^{(\varepsilon)})'(t) \le 0$ for any $t \in [T - \eta, T]$, which would contradict the definition of $T$. Thus, $T = \infty$ on $I_n(\varepsilon)$ and the claim follows with $\bar{\kappa}_{\varepsilon} = \min(\bar{\kappa}_{\varepsilon}^0, \varepsilon^2)$. $\square$

Now set

$$ K_{\varepsilon,A} = \frac{1 + \bar{K}_{\varepsilon,A}}{2} \quad \text{and} \quad \kappa_{\varepsilon} = \frac{\bar{\kappa}_{\varepsilon}}{2}, $$

and consider the following domain.

**Definition 4.8.** For $\varepsilon > 0$ small enough and $A > 0$,

$$ D_{\varepsilon,A} = \left\{ (t, g, d) \in (-\varepsilon, A+1) \times (0, K_{\varepsilon,A}) \times (0, A+1) : \frac{1-K_{\varepsilon,A}}{2} < \frac{t+1/2+\varepsilon-d-g}{1-g} < \frac{1}{2}-\kappa_{\varepsilon} \right\}. $$

Additionally, define for $(t, g, d) \in D_{\varepsilon,A}$,

$$ F_{\varepsilon}(t, g, d) = \frac{2pg(1-g)^2}{1 - 2(t + 1/2 + \varepsilon) + g + 2d}. $$
**Some consequences.** This way, the process $((t, \tilde{g}_{p,n}^{(\varepsilon)}(t), \tilde{d}_{p,n}^{(\varepsilon)}(t)) : t \in [0, A])$ is confined in a compact subset of $D_{\varepsilon,A}$, according to Lemma 4.7 and the definition of the event $I_n(\varepsilon)$ (which gives strictly positive lower bounds for the processes $\tilde{g}_{p,n}^{(\varepsilon)}$, $\tilde{d}_{p,n}^{(\varepsilon)}$). The function $F_{\varepsilon}$ is chosen so that

$$g'(t + 1/2) = F_{\varepsilon}(t, g(t + 1/2), d(t + 1/2)), \quad t > 0$$

for any couple of functions $(g, d)$ solution to $(\tilde{E}_{(\varepsilon)})$. Moreover, observe that for all $(t, g, d) \in D_{\varepsilon,A}$ the denominator in $F_{\varepsilon}(t, g, d)$ belongs to the interval $[(1 - K_{\varepsilon,A})2\kappa_{\varepsilon}, K_{\varepsilon,A}] \subset (0, 1)$, so that $F_{\varepsilon}$ is well-defined, bounded and Lipschitz continuous on $D_{\varepsilon,A}$.

Let us now define, for $\varepsilon > 0$, the time-translated processes:

$$ 
\begin{array}{lll}
G_{p,n}^{(\varepsilon)}(m) = G_{p,n}(\lfloor m + (1/2 + \varepsilon)n \rfloor) & D_{p,n}^{(\varepsilon)}(m) = D_{p,n}(\lfloor m + (1/2 + \varepsilon)n \rfloor) & m \ge 0 \\
V_{p,n}^{(\varepsilon)}(m) = V_{p,n}(\lfloor m + (1/2 + \varepsilon)n \rfloor) & E_{p,n}^{(\varepsilon)}(m) = E_{p,n}(\lfloor m + (1/2 + \varepsilon)n \rfloor) & 
\end{array}
$$

and $(\mathbf{F}_{p,n}^{(\varepsilon)}(m))_{m \in \mathbb{Z}_+}$ be the associated filtration. Consider their modifications,

$$ (\tilde{G}_{p,n}^{(\varepsilon)}(m), \tilde{D}_{p,n}^{(\varepsilon)}(m)) := \begin{cases} (G_{p,n}(\lfloor m + (1/2 + \varepsilon)n \rfloor), D_{p,n}(\lfloor m + (1/2 + \varepsilon)n \rfloor)) & \text{on } I_n(\varepsilon) \\ n \cdot (g_p(\frac{m}{n} + 1/2 + \varepsilon), d_p(\frac{m}{n} + 1/2 + \varepsilon)) & \text{on } I_n(\varepsilon)^c, \end{cases} $$

as well as $\tilde{V}_{p,n}^{(\varepsilon)}(m) = n - \tilde{G}_{p,n}^{(\varepsilon)}(m)$, $\tilde{E}_{p,n}^{(\varepsilon)}(m) = \lfloor m + (1/2 + \varepsilon)n \rfloor - \tilde{G}_{p,n}^{(\varepsilon)}(m) - \tilde{D}_{p,n}^{(\varepsilon)}(m)$. Note that these processes are adapted to the filtration $\mathbf{F}_{p,n}^{(\varepsilon)}$. These modifications eliminates potential initialization issues since, as already observed, Lemma 4.7 and the definition of $D_{\varepsilon,A}$ imply that

$$ \left(0, \frac{\tilde{G}_{p,n}^{(\varepsilon)}(0)}{n}, \frac{\tilde{D}_{p,n}^{(\varepsilon)}(0)}{n}\right) \in D_{\varepsilon,A}. $$

Consider then the exit time

$$ H_{D_{\varepsilon,A}} := \inf \left\{ m \ge 0 : \left( \frac{m}{n}, \frac{\tilde{G}_{p,n}^{(\varepsilon)}(m)}{n}, \frac{\tilde{D}_{p,n}^{(\varepsilon)}(m)}{n} \right) \notin D_{\varepsilon,A} \right\}, \quad (4.15) $$

which is a stopping-time with respect to the filtration $\mathbf{F}_{p,n}^{(\varepsilon)}$. Note the following consequences of the definition of $D_{\varepsilon,A}$: for every $m \in [0, H_{D_{\varepsilon,A}})$

$$ \tilde{V}_{p,n}^{(\varepsilon)}(m) > (1 - K_{\varepsilon,A}) n \quad (A1) $$

and for $n$ small enough (depending on $\varepsilon$ and $A$)

$$ \frac{1 - K_{\varepsilon,A}}{3} < \frac{\tilde{E}_{p,n}^{(\varepsilon)}(m)}{\tilde{V}_{p,n}^{(\varepsilon)}(m)} < \frac{1}{2} - \kappa_{\varepsilon}, \quad (A2) $$
which implies that the forest part of $\tilde{G}_{p,n}^{(\varepsilon)}(m)$ is subcritical as long as $m \in [0, H_{D_{\varepsilon,A}})$, and more precisely that

$$ \tilde{\Omega}_{p,n}^{(\varepsilon)}(m) := \frac{2\tilde{E}_{p,n}^{(\varepsilon)}(m) - \tilde{V}_{p,n}^{(\varepsilon)}(m)}{\tilde{V}_{p,n}^{(\varepsilon)}(m)^{2/3}} \leq -2\kappa_{\varepsilon}(1 - K_{\varepsilon,A})^{1/3} \cdot n^{1/3}. \quad (A3) $$

Combining (A1) with the lower bound of (A2) also yields for $n$ small enough and any $m \in [0, H_{D_{\varepsilon,A}})$,

$$ \tilde{E}_{p,n}^{(\varepsilon)}(m) \geq \frac{(1 - K_{\varepsilon,A})^2}{3} \cdot n. \quad (A4) $$

**Approximation of the conditional jumps.** We have now the material to prove the following lemma, which is a key point of the proof of Proposition 4.6.

**Lemma 4.9.** As $n \to \infty$, uniformly over $m \in [0, H_{D_{\varepsilon,A}})$, one has

$$ \left| \mathbb{E} \left[ \Delta \tilde{G}_{p,n}^{(\varepsilon)}(m) | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right] - F_{\varepsilon} \left( \frac{m}{n}, \frac{\tilde{G}_{p,n}^{(\varepsilon)}(m)}{n}, \frac{\tilde{D}_{p,n}^{(\varepsilon)}(m)}{n} \right) \right| \leq \lambda(n) $$

for a deterministic function $\lambda(n)=o(1)$.

**Proof.** For $n \geq 1$ and $m \in [0, H_{D_{\varepsilon,A}})$, using the definition of $F_{\varepsilon}$, we have that

$$ \begin{aligned} & \left| \mathbb{E} \left[ \Delta \tilde{G}_{p,n}^{(\varepsilon)}(m) | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right] - F_{\varepsilon} \left( \frac{m}{n}, \frac{\tilde{G}_{p,n}^{(\varepsilon)}(m)}{n}, \frac{\tilde{D}_{p,n}(m)}{n} \right) \right| \\ & \leq \left| \mathbb{E} \left[ \Delta G_{p,n}^{(\varepsilon)}(m) | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right] - \frac{2pG_{p,n}^{(\varepsilon)}(m)(n - G_{p,n}^{(\varepsilon)}(m))}{n^2 (1 - 2E_{p,n}^{(\varepsilon)}(m)/V_{p,n}^{(\varepsilon)}(m))} \right| \mathbb{1}_{\{I_n(\varepsilon)\}} \\ & + \left| \frac{2pG_{p,n}^{(\varepsilon)}(m)(n - G_{p,n}^{(\varepsilon)}(m))^2}{n^3 (V_{p,n}^{(\varepsilon)}(m) - 2(m/n + 1/2 + \varepsilon) - G_{p,n}^{(\varepsilon)}(m) - D_{p,n}^{(\varepsilon)}(m))} - \frac{2pG_{p,n}^{(\varepsilon)}(m)(n - G_{p,n}^{(\varepsilon)}(m))^2}{n^3 (V_{p,n}^{(\varepsilon)}(m) - 2E_{p,n}^{(\varepsilon)}(m))} \right| \mathbb{1}_{\{I_n(\varepsilon)\}} \\ & + \left| n \left( g_p \left( \frac{m+1}{n} + \frac{1}{2} + \varepsilon \right) - g_p \left( \frac{m}{n} + \frac{1}{2} + \varepsilon \right) \right) - F_{\varepsilon} \left( \frac{m}{n}, g_p \left( \frac{m}{n} + \frac{1}{2} + \varepsilon \right), d_p \left( \frac{m}{n} + \frac{1}{2} + \varepsilon \right) \right) \right| \mathbb{1}_{\{I_n(\varepsilon)^c\}}. \end{aligned} \quad (4.16) $$

We will show that each of the three terms in the right-hand side of (4.16) is deterministically bounded by a function independent of $m$ that converges to 0 as $n \to \infty$.

1) We start by bounding from above the last term: since $(g_p(\cdot + \varepsilon), d_p(\cdot + \varepsilon))$ is a solution to $(\tilde{E}_{(\varepsilon)})$, one has for every $m \in [0, H_{D_{\varepsilon,A}})$,

$$ \begin{aligned} n \left( g_p \left( \frac{m+1}{n} + \frac{1}{2} + \varepsilon \right) - g_p \left( \frac{m}{n} + \frac{1}{2} + \varepsilon \right) \right) &= \int_m^{m+1} F_{\varepsilon} \left( \frac{s}{n}, g_p \left( \frac{s}{n} + \frac{1}{2} + \varepsilon \right), d_p \left( \frac{s}{n} + \frac{1}{2} + \varepsilon \right) \right) ds \\ &= F_{\varepsilon} \left( \frac{m}{n}, g_p \left( \frac{m}{n} + \frac{1}{2} + \varepsilon \right), d_p \left( \frac{m}{n} + \frac{1}{2} + \varepsilon \right) \right) + O \left( \frac{1}{n} \right) \end{aligned} $$
where the $O(1/n)$ is uniform over $m \in [0, H_{D_{\epsilon,A}})$, as a consequence of the Lipschitz continuity of $F_{\epsilon}$ over $D_{\epsilon,A}$ and the fact that the derivatives of $g_p$ and $d_p$ are bounded.

2) Regarding the middle term in the right-hand side of (4.16), we note, using e.g. (A3), that it is bounded from above by a constant times

$$ \frac{m/n + 1/2 + \epsilon - \lfloor m/n + 1/2 + \epsilon \rfloor}{n^2} \le \frac{1}{n^2} $$

for all $m \in [0, H_{D_{\epsilon,A}})$.

3) Last, on the event $I_n(\epsilon)$, for every $m \in [0, H_{D_{\epsilon,A}})$,

$$ \left| \mathbb{E} \left[ \Delta G_{p,n}^{(\epsilon)}(m) | \mathbf{F}_{p,n}^{(\epsilon)}(m) \right] - \frac{2p G_{p,n}^{(\epsilon)}(m) (n - G_{p,n}^{(\epsilon)}(m))}{n^2 (1 - 2E_{p,n}^{(\epsilon)}(m)/V_{p,n}^{(\epsilon)}(m))} \right| \\ \le \left| \mathbb{E} \left[ \Delta G_{p,n}^{(\epsilon)}(m) \mathbf{1}_{\{\Delta G_{p,n}^{(\epsilon)}(m) \le V_{p,n}^{(\epsilon)}(m)^{1/4}\}} | \mathbf{F}_{p,n}^{(\epsilon)}(m) \right] - \frac{2p G_{p,n}^{(\epsilon)}(m) (n - G_{p,n}^{(\epsilon)}(m))}{n^2} S_{V_{p,n}^{(\epsilon)}(m)^{1/4}} \left( \frac{2E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)} \right) \right| \\ + \mathbb{E} \left[ \Delta G_{p,n}^{(\epsilon)}(m) \mathbf{1}_{\{\Delta G_{p,n}^{(\epsilon)}(m) > V_{p,n}^{(\epsilon)}(m)^{1/4}\}} | \mathbf{F}_{p,n}^{(\epsilon)}(m) \right] \\ + 2p \left| \frac{1}{1 - 2E_{p,n}^{(\epsilon)}(m)/V_{p,n}^{(\epsilon)}(m)} - S_{V_{p,n}^{(\epsilon)}(m)^{1/4}} \left( \frac{2E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)} \right) \right| $$

where $S_N$ is defined in (A.3) for $N \in \mathbb{N}$. It remains to show that on the event $I_n(\epsilon)$ and uniformly over $m < H_{D_{\epsilon,A}}$, each of the three terms in the right-hand side of this inequality is smaller than a deterministic function of $n$ that converges to 0 as $n \to \infty$. In the lines below we implicitly work on $I_n(\epsilon)$ and with $m \in [0, H_{D_{\epsilon,A}})$.

• By (A4), $E_{p,n}^{(\epsilon)}(m)$ is greater than a constant times $n$, and by (A3), $\Omega_{p,n}^{(\epsilon)}(m)$ is smaller than a negative constant times $n^{1/3}$. Since moreover $V_{p,n}^{(\epsilon)}(m) \le n$, Corollary 2.5 1) applies and implies that uniformly in $1 \le k \le V_{p,n}^{(\epsilon)}(m)^{1/4}$,

$$ \left| \mathbb{P}(\Delta G_{p,n}^{(\epsilon)}(m) = k | \mathbf{F}_{p,n}^{(\epsilon)}(m)) - \frac{k^{k-1}}{k!} \left( \frac{2E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)} \right)^{k-1} e^{-2k \frac{E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)}} \left( \frac{2pG_{p,n}^{(\epsilon)}(m) (n - G_{p,n}^{(\epsilon)}(m))}{n^2} \right) \right| \\ \le \left( o_{(E_{p,n}^{(\epsilon)}(m), \Omega_{p,n}^{(\epsilon)}(m))}(1) + o_{(E_{p,n}^{(\epsilon)}(m), \Omega_{p,n}^{(\epsilon)}(m))}(1) \cdot \frac{n^{1/4}}{n} \right) \cdot \frac{k^{k-1}}{k!} \left( \frac{2E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)} \right)^{k-1} e^{-2k \frac{E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)}}. $$

There thus exists a deterministic $\lambda_1(n)$ (independent on $m \in [0, H_{D_{\epsilon,A}})$) that converges to 0 as $n \to \infty$ such that

$$ \left| \mathbb{E} \left[ \Delta G_{p,n}^{(\epsilon)}(m) \mathbf{1}_{\{\Delta G_{p,n}^{(\epsilon)}(m) \le V_{p,n}^{(\epsilon)}(m)^{1/4}\}} \left| \mathbf{F}_{p,n}^{(\epsilon)}(m) \right. \right] - \frac{2pG_{p,n}^{(\epsilon)}(m)(n - G_{p,n}^{(\epsilon)}(m))}{n^2} S_{V_{p,n}^{(\epsilon)}(m)^{1/4}} \left( 2 \frac{E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)} \right) \right| \\ \le \lambda_1(n) \cdot \sum_{k \ge 1} \frac{k^k}{k!} \left( \frac{2E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)} \right)^{k-1} e^{-2k \frac{E_{p,n}^{(\epsilon)}(m)}{V_{p,n}^{(\epsilon)}(m)}} \le \lambda_1(n) \cdot (2\kappa_{\epsilon})^{-1} $$
where we used (A.2) and the upper bound of the inequality (A2) to get the last line.

• As we just implicitly said, (A2) implies $2E_{p,n}^{(\varepsilon)}(m) - V_{p,n}^{(\varepsilon)}(m) \le -2\kappa_{\varepsilon}V_{p,n}^{(\varepsilon)}(m)$. Recall also that, by (A1), $V_{p,n}^{(\varepsilon)}(m)$ is deterministically bounded from below by a constant times $n$. Lemma 2.6 and the free forest property of Proposition 1.3 thus imply that for $n$ large enough

$$ 
\begin{aligned}
\mathbb{E} \left[ \Delta G_{p,n}^{(\varepsilon)}(m) 1_{\{\Delta G_{p,n}^{(\varepsilon)}(m) > V_{p,n}^{(\varepsilon)}(m)^{1/4}\}} | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right] &\le n \mathbb{P} \left( \Delta G_{p,n}^{(\varepsilon)}(m) > V_{p,n}^{(\varepsilon)}(m)^{1/4} | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right) \\
&\le c_1 n V_{p,n}^{(\varepsilon)}(m)^{3/2} \exp \left( -c_2 V_{p,n}^{(\varepsilon)}(m)^{1/4} \right) \\
&\le c_1 n^{5/2} \exp \left( -c_2 n^{1/4} \right),
\end{aligned} 
\quad (4.17) $$

where $c_1, c_2, c'_2$ belong to $(0, \infty)$ and only depend on $\varepsilon$ and $A$.

• Using again that the ratio $E_{p,n}^{(\varepsilon)}(m)/V_{p,n}^{(\varepsilon)}(m)$ belongs to the compact $[0, 1/2 - \kappa_{\varepsilon}]$, we can bound from above the last term by a deterministic function that converges to 0 as $n \to \infty$, thanks to Lemma A.2 1) and the fact, by (A1), that $V_{p,n}^{(\varepsilon)}(m) \ge (1 - K_{\varepsilon,A})n$. $\square$

### 4.3.2 Proof of Proposition 4.6

We have now the material to apply Theorem A.4 to the process $(\tilde{G}_{p,n}^{(\varepsilon)}, \tilde{D}_{p,n}^{(\varepsilon)})$ introduced in the preliminaries, working on the domain $D_{\varepsilon,A}$ of Definition 4.8 for some fixed $A > 0$. Let us check all the hypotheses of the theorem. First, both processes $\tilde{G}_{p,n}^{(\varepsilon)}, \tilde{D}_{p,n}^{(\varepsilon)}$ are uniformly bounded by $n$. Then, recall the definition of $F_{\varepsilon}$ (Definition 4.8) and set

$$ G(t, g, d) = 2(1-p)g(1-g) + g^2, \quad \text{for } (t, g, d) \in D_{\varepsilon,A}. $$

The functions $F_{\varepsilon}$ and $G$ are Lipschitz continuous on $D_{\varepsilon,A}$: this is obvious for $G$ and was discussed for $F_{\varepsilon}$ in the paragraph after Definition 4.8. Besides, by construction, $D_{\varepsilon,A}$ contains the closure of the set

$$ \{ (0, g, d) : \mathbb{P} \left( (\tilde{G}_{p,n}^{(\varepsilon)}(0), \tilde{D}_{p,n}^{(\varepsilon)}(0)) = n \cdot (g, d) \right) \neq 0 \text{ for some } n \}. $$

Next, recall the definition (4.15) of the exit time $H_{D_{\varepsilon,A}}$, and check:

• The boundedness hypothesis. Since $g'_p$ is bounded on $[1/2, A + 3/2]$, we have for $n$ large enough

$$ \mathbb{P} \left( \exists m \in [0, H_{D_{\varepsilon,A}}) : \Delta \tilde{G}_{p,n}^{(\varepsilon)}(m) > n^{1/4} \right) = \mathbb{P} \left( \exists m \in [0, H_{D_{\varepsilon,A}}) : \Delta G_{p,n}^{(\varepsilon)}(m) > n^{1/4}, I_n(\varepsilon) \right). $$

Consequently, proceeding in a similar way to (4.17), recalling also (A1), we deduce that

$$ 
\begin{aligned}
\mathbb{P} \left( \exists m \in [0, H_{D_{\varepsilon,A}}) : \Delta \tilde{G}_{p,n}^{(\varepsilon)}(m) > n^{1/4} \right) & \\
&\le \sum_{m=0}^{\lfloor (A+1)n \rfloor} \mathbb{E} \left[ \mathbb{P} \left( \Delta G_{p,n}^{(\varepsilon)}(m) > n^{1/4}, m < H_{D_{\varepsilon,A}} | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right) \mathbb{1}_{I_n(\varepsilon)} \right] \\
&\le c_1 n^{5/2} \exp \left( -c_2 n^{1/4} \right),
\end{aligned} 
$$
where $c_1, c_2$ belong to $(0, \infty)$ and only depend on $\varepsilon$ and $A$. Besides, $|\Delta \tilde{D}_{p,n}^{(\varepsilon)}(m)| \le 1$ for all $m \ge 0$. This therefore yields the boundedness hypothesis of Theorem A.4, with, keeping the notation introduced there, $\beta(n) = n^{1/4}$ and $\gamma(n) = c'_1 n^{5/2} \exp(-c'_2 n^{1/4})$.

* The trend hypothesis. By Lemma 4.9, for every $m \in [0, H_{D_{\varepsilon,A}})$

$$ \left| \mathbb{E} \left[ \Delta \tilde{G}_{p,n}^{(\varepsilon)}(m) | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right] - F_{\varepsilon} \left( \frac{m}{n}, \frac{\tilde{G}_{p,n}^{(\varepsilon)}(m)}{n}, \frac{\tilde{D}_{p,n}^{(\varepsilon)}(m)}{n} \right) \right| \le \lambda(n) $$

with $\lambda(n) = o(1)$. With a similar (but much simpler) approach, we get that simultaneously for all $m \in [0, H_{D_{\varepsilon,A}})$, thanks to Proposition 2.1 and the definition of $d_p$ via $(\tilde{E}_{(\varepsilon)})$,

$$ \left| \mathbb{E} \left[ \Delta \tilde{D}_{p,n}^{(\varepsilon)}(m) | \mathbf{F}_{p,n}^{(\varepsilon)}(m) \right] - G \left( \frac{m}{n}, \frac{\tilde{G}_{p,n}^{(\varepsilon)}(m)}{n}, \frac{\tilde{D}_{p,n}^{(\varepsilon)}(m)}{n} \right) \right| = O \left( \frac{1}{n} \right) $$

for a deterministic $O(1/n)$ independent of $m \in [0, H_{D_{\varepsilon,A}})$.

Finally recall from Definition 4.5 and Lemma 4.7 that $(\tilde{g}_{p,n}^{(\varepsilon)}, \tilde{d}_{p,n}^{(\varepsilon)})$ is the unique solution to equation $(\tilde{E}_{(\varepsilon)})$ starting from $(\tilde{G}_{p,n}^{(\varepsilon)}(0)/n, \tilde{D}_{p,n}^{(\varepsilon)}(0)/n)$ and that $((t, \tilde{g}_{p,n}^{(\varepsilon)}(t), \tilde{d}_{p,n}^{(\varepsilon)}(t)) : t \in [0, A])$ is confined in a compact subset of $D_{\varepsilon,A}$. All in all, all this implies that the conclusion (b) of Theorem A.4 holds with $\eta(n) = \max(\lambda(n) + n^{-1/2} + 2n\gamma(n); n^{-1/13}) = o(1)$ and $\sigma(n) = A$, yielding that, with high probability as $n \to \infty$,

$$ \tilde{G}_{p,n}^{(\varepsilon)}(m) = n \cdot \tilde{g}_{p,n}^{(\varepsilon)}(m/n) + o(n) \quad \text{and} \quad \tilde{D}_{p,n}^{(\varepsilon)}(m) = n \cdot \tilde{d}_{p,n}^{(\varepsilon)}(m/n) + o(n), $$

uniformly over $m \in [0, An]$. Since $(\tilde{G}_{p,n}^{(\varepsilon)}, \tilde{D}_{p,n}^{(\varepsilon)})$ coincides with $(G_{p,n}^{(\varepsilon)}, D_{p,n}^{(\varepsilon)})$ on $I_n(\varepsilon)$, whose probability tends to 1 as $n$ tends to infinity, and since $\tilde{g}_{p,n}^{(\varepsilon)}(|nt|/n) - \tilde{g}_{p,n}^{(\varepsilon)}(t) = O(1/n)$ uniformly on compact sets, this in turn yields that

$$ \left( \left( \left| \frac{G_{p,n}(|nt + (1/2 + \varepsilon)n|)}{n} - \tilde{g}_{p,n}^{(\varepsilon)}(t) \right|, \left| \frac{D_{p,n}(|nt + (1/2 + \varepsilon)n|)}{n} - \tilde{d}_{p,n}^{(\varepsilon)}(t) \right| \right) \right)_{t \ge 0} \xrightarrow{n \to \infty} 0 $$

for the topology of uniform convergence on compacts, which is equivalent to the statement of the proposition.

## 4.4 Proof of Theorem 1.2

*Convergence of the rescaled gel $G_{p,n}(|n \cdot|)/n$. Our goal is to prove that for any (large) $A > 0$ and any (small) $\delta > 0$,

$$ \mathbb{P} \left( \sup_{t \in [0, A]} \left| \frac{G_{p,n}(|nt|)}{n} - g_p(t) \right| > \delta \right) \xrightarrow{n \to \infty} 0. $$

Recall the definition of the event $I_n(\varepsilon)$ in (4.14) and that for $\varepsilon > 0$ sufficiently small $\mathbb{P}(I_n(\varepsilon)) \to 1$ as $n \to \infty$. It is therefore sufficient to prove that for a well-chosen, small, $\varepsilon > 0$ (that may depend on $A$
and $\delta$),

$$ \mathbb{P}\left(\sup_{t \in [0, A]} \left| \frac{G_{p,n}(\lfloor nt \rfloor)}{n} - g_p(t) \right| > \delta, I_n(\varepsilon)\right) \underset{n \to \infty}{\longrightarrow} 0. \quad (4.18) $$

In that aim, consider $g_{p,n}^{(\varepsilon)}$ as defined in Definition 4.5 and write

$$ \begin{aligned} \sup_{t \in [0, A]} \left| \frac{G_{p,n}(\lfloor nt \rfloor)}{n} - g_p(t) \right| &\le \sup_{t \in [0, \frac{1}{2}+\varepsilon]} \left| \frac{G_{p,n}(\lfloor nt \rfloor)}{n} - g_p(t) \right| + \sup_{t \in [\frac{1}{2}+\varepsilon, A]} \left| \frac{G_{p,n}(\lfloor nt \rfloor)}{n} - g_p(t) \right| \\ &\le \frac{G_{p,n}(\lfloor n(\frac{1}{2} + \varepsilon) \rfloor)}{n} + g_p\left(\frac{1}{2} + \varepsilon\right) + \sup_{t \in [\frac{1}{2}, A-\varepsilon]} \left| \frac{G_{p,n}(\lfloor n(t+\varepsilon) \rfloor)}{n} - g_{p,n}^{(\varepsilon)}(t) \right| \\ &\quad + \sup_{t \in [\frac{1}{2}, A-\varepsilon]} \left| g_{p,n}^{(\varepsilon)}(t) - g_p(t+\varepsilon) \right| \end{aligned} $$

where we used that the process $G_{p,n}$ and the function $g_p$ are non-decreasing.

On $I_n(\varepsilon)$, since $G_{p,n}(\lfloor n(1/2 + \varepsilon) \rfloor) \le C(p)\varepsilon n$ and $g_p$ is continuous on $[1/2, \infty)$, we have that for $\varepsilon$ (determinist and independent of $n$) small enough

$$ \frac{G_{p,n}(\lfloor n(\frac{1}{2} + \varepsilon) \rfloor)}{n} + g_p\left(\frac{1}{2} + \varepsilon\right) \le C(p)\varepsilon + g_p\left(\frac{1}{2} + 2\varepsilon\right) \le \frac{\delta}{4}. $$

(We will need the “+2$\varepsilon$" later on.) Besides, from Lemma 4.7 and its proof, we know that on $I_n(\varepsilon)$, for $\varepsilon$ (determinist, independent of $n$) sufficiently small, $g_{p,n}^{(\varepsilon)}$ is the unique solution to the equation $(E_{(\delta_n(\varepsilon))})$ starting from $g_{p,n}^{(\varepsilon)}(1/2) = G_{p,n}(\lfloor n(1/2 + \varepsilon) \rfloor)/n$, where

$$ 0 < \delta_n(\varepsilon) = \frac{\varepsilon - d_{p,n}^{(\varepsilon)}(1/2) - g_{p,n}^{(\varepsilon)}(1/2)^2/2}{(1 - g_{p,n}^{(\varepsilon)}(1/2))^2} \le 2\varepsilon $$

(with $d_{p,n}^{(\varepsilon)}(1/2) = D_{p,n}(\lfloor n(1/2 + \varepsilon) \rfloor)/n$). Since $g(\cdot + \delta_n(\varepsilon))$ is also a solution to $(E_{(\delta_n(\varepsilon))})$, Lemma 3.3.2) then yields

$$ \begin{aligned} \sup_{t \in [\frac{1}{2}, A-\varepsilon]} \left| g_{p,n}^{(\varepsilon)}(t) - g_p(t + \delta_n(\varepsilon)) \right| &\le \left| g_{p,n}^{(\varepsilon)}\left(\frac{1}{2}\right) - g_p\left(\frac{1}{2} + \delta_n(\varepsilon)\right) \right| \\ &\le \frac{G_{p,n}(\lfloor n(\frac{1}{2} + \varepsilon) \rfloor)}{n} + g_p\left(\frac{1}{2} + 2\varepsilon\right) \le \frac{\delta}{4}. \end{aligned} $$

To complete, the mean value theorem gives for $\varepsilon \in (0, 1]$,

$$ \sup_{t \in [\frac{1}{2}, A-\varepsilon]} |g_p(t + \delta_n(\varepsilon)) - g_p(t + \varepsilon)| \le \sup_{t \in [\frac{1}{2}, A+1]} |g'_p(t)|\varepsilon. $$

All in all, we have proved so far that on $I_n(\varepsilon)$, for $\varepsilon$ (determinist, independent of $n$) sufficiently small,

$$ \sup_{t \in [0, A]} \left| \frac{G_{p,n}(\lfloor nt \rfloor)}{n} - g_p(t) \right| \le \frac{3\delta}{4} + \sup_{t \in [\frac{1}{2}, A-\varepsilon]} \left| \frac{G_{p,n}(\lfloor n(t+\varepsilon) \rfloor)}{n} - g_{p,n}^{(\varepsilon)}(t) \right|. $$
By Proposition 4.6, the supremum in the right-hand side converges in probability to 0, leading to (4.18).

Convergence of the rescaled number of discarded edges $D_{p,n}(|n \cdot|)/n$. We proceed similarly. For fixed $A > 0$ and $\delta > 0$, our goal is to prove that for $\varepsilon$ small enough

$$ \mathbb{P} \left( \sup_{t \in [0, A]} \left| \frac{D_{p,n}(|nt|)}{n} - d_p(t) \right| > \delta, I_n(\varepsilon) \right) \xrightarrow{n \to \infty} 0. $$

As above, we use the triangular inequality to get

$$ \sup_{t \in [0, A]} \left| \frac{D_{p,n}(|nt|)}{n} - d_p(t) \right| \le \frac{D_{p,n}(|n(\frac{1}{2} + \varepsilon)|)}{n} + d_p\left(\frac{1}{2} + \varepsilon\right) + \sup_{t \in [\frac{1}{2}, A-\varepsilon]} \left| \frac{D_{p,n}(|n(t+\varepsilon)|)}{n} - d_{p,n}^{(\varepsilon)}(t) \right| \\ + \sup_{t \in [\frac{1}{2}, A-\varepsilon]} \left| d_{p,n}^{(\varepsilon)}(t) - d_p(t+\varepsilon) \right|. $$

Regarding the initialization at time $1+2+\varepsilon$, we proceed as with $G_{p,n}$, recalling that $D_{p,n}(1/2+\varepsilon)$ is smaller than a constant times $\varepsilon^2 n$ on $I_n(\varepsilon)$ and that $d_p(1/2) = 0$. Recall next that for $t \ge \frac{1}{2}$,

$$ d_p'(t+\varepsilon) = 2(1-p)g_p(t+\varepsilon)(1-g_p(t+\varepsilon)) + g_p^2(t+\varepsilon), \quad (d_{p,n}^{(\varepsilon)})'(t) = 2(1-p)g_{p,n}^{(\varepsilon)}(t)(1-g_{p,n}^{(\varepsilon)}(t)) + (g_{p,n}^{(\varepsilon)})^2(t). $$

Since we have seen that $\sup_{t \in [\frac{1}{2}, A-\varepsilon]} |g_{p,n}^{(\varepsilon)}(t) - g_p(t+\varepsilon)|$ can be made arbitrarily small on $I_n(\varepsilon)$ and since the functions $g_{p,n}^{(\varepsilon)}$, $g_p$ are positive and bounded from above by 1, we have that, on $I_n(\varepsilon)$, for $\varepsilon$ (determinist, independent of $n$) sufficiently small,

$$ \sup_{t \in [0, A]} \left| \frac{D_{p,n}(|nt|)}{n} - d_p(t) \right| \le \frac{3\delta}{4} + \sup_{t \in [\frac{1}{2}, A-\varepsilon]} \left| \frac{D_{p,n}(|n(t+\varepsilon)|)}{n} - d_{p,n}^{(\varepsilon)}(t) \right| $$

and we conclude with Proposition 4.6.

## 4.5 Proof of Theorem 1.6

Theorem 1.6 is a consequence of Theorem 1.2. The convergence of the triplet $(V_{p,n}(|n \cdot|)/n, E_{p,n}(|n \cdot|)/n, R_{p,n}(|n \cdot|))$ follows immediately from Theorem 1.2, together with the relations (1.2) and the properties of the functions $v_p, e_p, r_p$ highlighted in Proposition 3.1.

Regarding the number of trees $N_{p,n}^{(k)}$ of size $k$, $k \in \mathbb{N}$, we first note that since the process

$$ \sum_{k \ge 1} \frac{k N_{p,n}^{(k)}(|n \cdot|)}{n} = \frac{V_{p,n}(|n \cdot|)}{n} \xrightarrow{n \to \infty} v_p = 1 - g_p = \sum_{k \ge 1} k t_{p,k} $$

it is sufficient to prove separately the convergence for each $k \in \mathbb{N}$ of $kN_{p,n}^{(k)}(|n \cdot|)/n$ to $t_{p,k}$ to get the convergence of the sequence $(kN_{p,n}^{(k)}(|n \cdot|)/n, k \ge 1)$ for the norm $\| \cdot \|_1$ in $\ell^1$.
Then, note from the dynamic of the p-frozen model that for all $k \in \mathbb{N}$ and all $m \in \mathbb{N}$

$$ \mathbb{E} \left[ \Delta N_{p,n}^{(k)}(m) | \mathbf{F}_{p,n}^{(N)}(m) \right] = \sum_{i+j=k} ij \frac{N_{p,n}^{(i)}(m) N_{p,n}^{(j)}(m)}{n^2} - 2k \frac{N_{p,n}^{(k)}(m) (n - (1-p)G_{p,n}(m))}{n^2} + O \left( \frac{1}{n} \right) \quad (4.19) $$

where $\mathbf{F}_{p,n}^{(N)}$ denotes the filtration generated by the sequence $(N_{p,n}^{(k)})_{k \ge 1}$, for a deterministic $O(1/n)$ that only depends on $k$, not on $m$. We will proceed by induction on $k$ to get the convergence of $N_{p,n}^{(k)}([n \cdot]) / n$ to the function $t_{p,k}$, relying on an approximation of the gel $G_{p,n}$ by its fluid limit.

We prove in detail the initial step, when $k = 1$, the induction step will then proceed similarly. Fix $A > 0$ and define for any integer $m \in [0, An]$

$$ Y_n^{(1)}(m) = \frac{N_{p,n}^{(1)}(m)}{n} - t_{p,1} \left( \frac{m}{n} \right), $$

where we recall that

$$ t_{p,1}(t) = (1 - g_p(t)) e^{-2t(1-g_p(t))}, \quad t \ge 0. $$

It is easy to see, using that $g_p$ is solution to the equation $(E_{(0)})$, that $t'_{p,1}(t) = -2t_{p,1}(t)(1 - (1-p)g_p(t))$ for all $t \ge 0$ – which is bounded as well as its derivative since $g'_p$ is bounded – so we have for every $m \in \mathbb{N}$, by Taylor's expansion,

$$ t_{p,1} \left( \frac{m+1}{n} \right) - t_{p,1} \left( \frac{m}{n} \right) = -\frac{2}{n} \cdot t_{1,p} \left( \frac{m}{n} \right) \left( 1 - (1-p)g_p \left( \frac{m}{n} \right) \right) + O \left( \frac{1}{n^2} \right). \quad (4.20) $$

In particular the jumps of $Y_n^{(1)}$ are deterministically bounded by a $O(1/n)$. Then consider for $\delta > 0$ the event

$$ J_n(\delta) = \left\{ \sup_{0 \le m \le \lfloor An \rfloor} \left| \frac{G_{p,n}(m)}{n} - g_p\left(\frac{m}{n}\right) \right| \le \delta \right\} \cap \left\{ \sup_{0 \le m \le \lfloor An \rfloor} \left| Y_n^{(1)}(m) - \sum_{i=0}^{m-1} \mathbb{E} \left[ \Delta Y_n^{(1)}(i) | \mathbf{F}_{p,n}^{(N)}(i) \right] \right| \le \delta \right\}. $$

The convergence in probability of the rescaled process $G_{p,n}([n \cdot]) / n$ to $g_p$ and Lemma 4.1 imply that $\mathbb{P}(J_n(\delta)) \to 1$ as $n \to \infty$. Next, on $J_n(\delta)$, using (4.19) for $k = 1$ and (4.20), we see that for every $n$ deterministic large enough and every $m \in [0, An]$, we have

$$ \left| \mathbb{E} \left[ \Delta Y_n^{(1)}(m) | \mathbf{F}_{p,n}^{(N)}(m) \right] \right| \le \frac{2}{n} \left| Y_n^{(1)}(m) \right| + \frac{3\delta}{n}, $$

which in turn leads to

$$ |Y_n^{(1)}(i)| \le \frac{2}{n} \sum_{j=0}^{m-1} |Y_n^{(1)}(j)| + \delta(3A + 1). $$

We then conclude with the discrete version of Grönwall's Lemma that $\sup_{0 \le m \le \lfloor An \rfloor} |Y_n^{(1)}(m)| \le \delta(3A + 1)e^{2A}$. Since $\delta$ can be chosen arbitrarily small, this proves the convergence in probability to 0 of $\sup_{0 \le m \le \lfloor An \rfloor} |Y_n^{(1)}(m)|$, which in turn gives the convergence in probability of $N_{p,n}^{(1)}([n \cdot]) / n$ to
the function $t_{p,1}$ for the topology of uniform convergence on $[0, A]$, using that $\sup_{t \ge 0} |t_{p,1}(\lfloor nt \rfloor/n) - t_{p,1}(t)| = O(1/n)$.

The proof of the induction step to pass from $k$ to $k+1$ is similar, using that $(G_{p,n}/n, N_{p,n}^{(1)}/n, ..., N_{p,n}^{(k)}/n)$ is approximated by $(g_p(\cdot/n), t_{p,1}(\cdot/n), ..., t_{p,k-1}(\cdot/n))$, together with (4.19) and the definition and properties of the functions $t_{p,i}$, $i \ge 1$. Details are left to the reader.

## 4.6 Largest and typical trees

**Proof of Corollary 1.7.** Let $t \in [0, \infty) \setminus \{1/2\}$. By Theorem 1.6, $V_{p,n}(\lfloor nt \rfloor)/n$ converges in probability towards $1 - g_p(t) > 0$ and the ratio $R_{p,n}(t) = E_{p,n}(t)/V_{p,n}(t)$ converges in probability towards $r_p(t) = t(1 - g_p(t))$ which lies in $(0, 1/2)$ since $t \ne 1/2$, by Proposition 3.1. Together with the free forest property of Proposition 1.3 and Proposition 2.4, this implies that

$$ \frac{\#T_{p,n}^{(i)}(\lfloor nt \rfloor)}{\ln(n)} \underset{n \to \infty}{\mathbb{P}} \frac{1}{2t(1 - g_p(t)) - 1 - \ln(2t(1 - g_p(t)))}, \quad \forall i \in \mathbb{N}. $$

Hence the result, since $g_p(t) = 0$ when $t < 1/2$.

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

**Proof of Corollary 1.8.** Fix $t \ge 0$. From the exchangeability of the vertices of the model and Theorem 1.6 (using that $kN_{p,n}^{(k)}(\lfloor nt \rfloor)/n \le 1$ and $V_{p,n}(\lfloor nt \rfloor))/n \le 1$ to apply the Dominated Convergence Theorem), one has for any $k \in \mathbb{N}$,

$$ \mathbb{P}(\mathrm{CC}_{p,n}^*(\lfloor nt \rfloor) \text{ is a tree of size } k) = \mathbb{E} \left[ \frac{k N_{p,n}^{(k)}(\lfloor nt \rfloor)}{n} \right] \underset{n \to \infty}{\longrightarrow} k t_{p,k}(t). $$

and

$$ \mathbb{P}(\mathrm{CC}_{p,n}^*(\lfloor nt \rfloor) \text{ is a tree}) = \mathbb{E} \left[ \frac{V_{p,n}(\lfloor nt \rfloor)}{n} \right] \underset{n \to \infty}{\longrightarrow} 1 - g_p(t). $$

Then let $t$ be one of the $k^{k-2}$ trees with $k$ vertices labeled $1, \dots, k$. Recalling that the labels in $\mathrm{CC}_{p,n}^*(\lfloor nt \rfloor)$ are an increasing relabeling from 1 to $\#\mathrm{CC}_{p,n}^*(\lfloor nt \rfloor)$ of the initial labels of the connected component containing the vertex 1 at time $\lfloor nt \rfloor$, one sees from Proposition 2.2 that

$$ \mathbb{P}(\mathrm{CC}_{p,n}^*(\lfloor nt \rfloor) = t \mid \mathrm{CC}_{p,n}^*(\lfloor nt \rfloor) \text{ is a tree of size } k) = \frac{1}{k^{k-2}}. $$

Consequently,

$$ \begin{aligned} \mathbb{P}(\mathrm{CC}_{p,n}^*(\lfloor nt \rfloor) = t \mid \mathrm{CC}_{n,1}(\lfloor nt \rfloor) \text{ is a tree}) & \underset{n \to \infty}{\longrightarrow} \frac{kt_{p,k}(t)}{(1 - g_p(t))k^{k-2}} \\ & = \frac{(2t)^{k-1}(1 - g_p(t))^{k-1}e^{-2kt(1 - g_p(t))}}{(k - 1)!}. \end{aligned} $$

We conclude by recalling that a Galton-Watson tree with offspring distribution Poisson with mean $\lambda > 0$ – we denote $GW_{\mathrm{Poi}(\lambda)}$ such a tree – equipped with uniformly random labels from 1 to $\#GW_{\mathrm{Poi}(\lambda)}$
on its vertices and where the original order is forgotten, as well as the root, verifies for any tree t with k vertices labeled 1, ..., k,

$$ \mathbb{P}(\text{GW}_{\text{Poi}(\lambda)} = t) = \frac{e^{-k\lambda}\lambda^{k-1}}{\prod_{i=1}^{k} n_i!} \cdot \frac{1}{k!} \cdot \prod_{i=1}^{k} n_i! \cdot k = \frac{e^{-k\lambda}\lambda^{k-1}}{(k-1)!}, $$

where $n_i$ denotes the number of children of the vertex i (here $e^{-k\lambda}\lambda^{k-1}/\prod_{i=1}^{k} n_i!$ is the probability that the Galton-Watson tree, yet ordered and unlabeled, is equal to an ordered unlabeled version of t, $1/k!$ corresponds to adding the labels, $\prod_{i=1}^{k} n_i!$ to removing the order, and last k to forgetting the root). Taking $\lambda = 2t(1 - g_p(t))$, this corresponds to the above limit in distribution of $CC_{p,n}^*(\lfloor nt \rfloor)$ conditioned to be a tree. □

**Remark.** We could have proved this result by using the continuous model of Section 5.1 together with Lemma 6.1, and then de-Poissonizing with the help of (6.6). With this approach, one has to use the identity

$$ e^{2(1-p)} \int_{0}^{t} g_{p}(u) du = (1 - g_{p}(t)) e^{2tg_{p}(t)}, \quad \forall t \ge 0 $$

to conclude. This identity can be proved by verifying that the derivatives of the functions in the left and right hand sides are equal, using the equation ($E_{(0)}$) satisfied by $g_p$.

# 5 A continuous version of the model

We introduce in this short section a continuous version of the p-frozen Erdős-Rényi model, $p \in [0, 1]$, and then underline some of its properties in the fluid limit.

## 5.1 Poissonization

Starting with $n$ isolated vertices labelled 1, ..., $n$, we consider, on each of the $n(n-1)/2$ potential edges, independently, a Poisson point process (PPP in the following) with intensity $1/n$. When such a PPP rings, if the edge has not already been added to the graph:

- either the edge connects two tree-components of the current graph and we add it to the graph

- or it connects two vertices of unicycle-components and we discard it

- or it connects a tree-component and a unicycle-component and we add it with probability $p$ and discard it otherwise.

We let $\mathcal{F}_{p,n}(t)$ denote the graph at time $t \ge 0$ and emphasize that if $\mathcal{N}$ is a standard Poisson process (with intensity 1), independent of the discrete p-frozen model $F_{p,n}$, then,

$$ (\mathcal{F}_{p,n}(t), t \ge 0) \stackrel{(d)}{=} (F_{p,n}(\mathcal{N}((n-1)t/2)), t \ge 0). \qquad (5.1) $$
## 5.2 Fluid limit in the continuous model

We let $(G_{p,n}(t), t \ge 0)$ denote the gel size process in this continuous version of the model (that is the total number of vertices that belong to unicycle components) and state the following corollary of Theorem 1.2. Of course, the other results on the fluid limit of the discrete model also transfer easily to the continuous model, but we only highlight here what we will really need in the rest of the paper. Here $p \in (0, 1]$.

**Corollary 5.1.** As $n \to \infty$,

$$ \left( \frac{G_{p,n}(t)}{n}, t \ge 0 \right) \xrightarrow{\mathbb{P}} (g_p(t/2), t \ge 0) $$

for the topology of uniform convergence on compacts. Consequently, for each $A > 0$,

$$ \int_0^A \left(1 - \frac{G_{p,n}(t)}{n}\right) dt \xrightarrow{\mathbb{P}} \int_0^A \left(1 - g_p(t/2)\right) dt. $$

**Proof.** We write for $t \ge 0$, $G_{p,n}(t) = G_{p,n}(\mathcal{N}((n-1)t/2))$, where $G_{p,n}$ is a discrete version of the $p$-frozen model and $\mathcal{N}$ is the Poisson process involved in (5.1), independent of $G_{p,n}$, $\forall n$. Using that the derivative of $g_p$ is bounded on $\mathbb{R}_+$ and the convergence in probability of the rescaled process $\mathcal{N}(n\cdot)/n$ towards the identity function (for the topology of uniform convergence on compacts), we have that for all $A > 0$, as $n \to \infty$,

$$ \sup_{t \in [0,A]} \left| g_p \left( \frac{\mathcal{N}((n-1)t/2)}{n} \right) - g_p(t/2) \right| \xrightarrow{\mathbb{P}} 0. $$

Together with Theorem 1.2 and a standard use of the triangular inequality this leads to the announced convergence. □

The convergence of the integrals can be completed as follows:

**Corollary 5.2.** As $n \to \infty$,

$$ \int_0^\infty \left(1 - \frac{G_{p,n}(t)}{n}\right) dt \xrightarrow{\mathbb{P}} \int_0^\infty (1 - g_p(t/2)) dt = \frac{\psi(1/p) + \gamma_E}{1-p}. $$

Additionally, for any sequence of positive real numbers $(t_n)$ such that $t_n \to \infty$,

$$ \int_0^{t_n} \left(1 - \frac{G_{p,n}(t)}{n}\right) dt \xrightarrow{\mathbb{P}} \frac{\psi(1/p) + \gamma_E}{1-p}. $$

The proof of this corollary is partly based on the following lemma.

**Lemma 5.3.** Let $\sigma_n(1/2) := \inf\{t \ge 0 : G_{p,n}(t) \ge n/2\}$ and set for $t \ge 0$

$$ k_n(t) = \mathbb{E} \left[ 1 - \frac{G_{p,n}(t + \sigma_n(1/2))}{n} \right]. $$

Then, $k_n(t) \le e^{-pt/2}$ for all $t \ge 0$ and all $n \in \mathbb{N}$.
**Proof.** The dynamic of the continuous model implies that conditional on $\mathcal{G}_{p,n}(t + \sigma_n(1/2)) = \ell$ (for $\ell$ integer, $n/2 \le \ell \le n$), we have that $\mathcal{G}_{p,n}(t + \varepsilon + \sigma_n(1/2)) \ge \mathcal{G}_{p,n}(t + \sigma_n(1/2)) + 1$ with probability greater than

$$p(1 - \exp(-\varepsilon\ell(n - \ell)/n)) \ge p(1 - \exp(-\varepsilon(n - \ell)/2)), \quad \forall \varepsilon > 0.$$

Since the function $x \mapsto (1 - \exp(-x))/x$ is decreasing on $(0, \infty)$ and since $n - \ell \le n/2$ when $\ell \ge n/2$, the above inequality implies that

$$k_n(t + \varepsilon) - k_n(t) = \frac{\mathbb{E}[\mathcal{G}_{p,n}(t + \sigma_n(1/2)) - \mathcal{G}_{p,n}(t + \varepsilon + \sigma_n(1/2))]}{n} \le -2pk_n(t) \frac{1 - \exp(-\varepsilon n/4)}{n}.$$

Consequently, for all $t \ge 0$ and all $\varepsilon > 0$,

$$k_n(t) \le k_n\left(\varepsilon\left\lfloor\frac{t}{\varepsilon}\right\rfloor\right) \le k_n(0)\left(1 - 2p\frac{1 - \exp(-\varepsilon n/4)}{n}\right)^{\left\lfloor\frac{t}{\varepsilon}\right\rfloor} \underset{\varepsilon \to 0}{\longrightarrow} k_n(0)\exp(-pt/2),$$

which gives the upper bound $k_n(t) \le k_n(0) \exp(-pt/2) \le \exp(-pt/2)$ for all $t \ge 0$ and all $n \in \mathbb{N}$. $\square$

**Proof of Corollary 5.2.** Lemma 3.2 gives the identity $\int_0^\infty (1 - g_p(t/2)) dt = (\psi(1/p) + \gamma_E)/(1 - p)$. Then fix $\varepsilon > 0, \delta > 0$. We want to show that

$$\mathbb{P}\left(\left|\int_{0}^{\infty} \left(1 - \frac{\mathcal{G}_{p,n}(t)}{n}\right) dt - \int_{0}^{\infty} (1 - g_p(t/2)) dt\right| \ge \varepsilon\right) \le \delta \quad \text{for all } n \text{ large enough.} \quad (5.2)$$

In that aim fix $A > 0$ large enough so that $g_p(A/2) > 1/2$ and

$$\int_{2A}^{\infty} (1 - g_p(t/2)) dt \le \frac{\varepsilon}{3} \quad \text{and} \quad \frac{3}{\varepsilon} \int_{A}^{\infty} e^{-pt/2} dt \le \frac{\delta}{4}.$$

Then note that

$$\mathbb{P}\left(\left|\int_{0}^{\infty} \left(1 - \frac{\mathcal{G}_{p,n}(t)}{n}\right) dt - \int_{0}^{\infty} (1 - g_p(t/2)) dt\right| \ge \varepsilon\right) \\ \le \mathbb{P}\left(\int_{2A}^{\infty} \left(1 - \frac{\mathcal{G}_{p,n}(t)}{n}\right) dt \ge \frac{\varepsilon}{3}\right) + \mathbb{P}\left(\left|\int_{0}^{2A} \left(1 - \frac{\mathcal{G}_{p,n}(t)}{n}\right) dt - \int_{0}^{2A} (1 - g_p(t/2)) dt\right| \ge \frac{\varepsilon}{3}\right).$$

By Corollary 5.1, the last probability converges to 0 and is therefore smaller than $\delta/2$ for $n$ large enough. Besides, with the notation of Lemma 5.3,

$$\mathbb{P}\left(\int_{2A}^{\infty} \left(1 - \frac{\mathcal{G}_{p,n}(t)}{n}\right) dt \ge \frac{\varepsilon}{3}\right) \le \mathbb{P}(A < \sigma_n(1/2)) \\ + \mathbb{P}\left(\int_{2A-T_n(1/2)}^{\infty} \left(1 - \frac{\mathcal{G}_{p,n}(t + \sigma_n(1/2))}{n}\right) dt \ge \frac{\varepsilon}{3}, A \ge \sigma_n(1/2)\right) \\ \le \mathbb{P}(A < \sigma_n(1/2)) + \frac{3}{\varepsilon} \int_{A}^{\infty} k_n(t) dt,$$

where for the second inequality we used that $2A - \sigma_n(1/2) \ge A$ when $\sigma_n(1/2) \le A$ and then Markov's inequality. By Lemma 5.3 and the choice of $A$, $\frac{3}{\varepsilon} \int_{A}^{\infty} k_n(t) dt \le \delta/4$. Whereas $\mathbb{P}(A < \sigma_n(1/2)) =$
$\mathbb{P}(\mathcal{G}_{p,n}(A) < n/2)$ which converges to 0 by Corollary 5.1 and since $g_p(A/2) > 1/2$, so this probability is also smaller than $\delta/4$ for large $n$. All this leads to the expected claim (5.2).

The proof of the convergence in probability of $\int_0^{t_n} (1 - \mathcal{G}_{p,n}(t)/n) dt$ to $\int_0^\infty (1 - g_p(t/2)) dt$ when $t_n \to \infty$ is similar. $\square$

# 6 Total gelation time and vicinity

In order to study the first time at which all the vertices of $F_{p,n}$ are frozen, and the number of trees of size $k \in \mathbb{N}$ in its neighborhood, we work in this section with the continuous model, which offers more independence and eases the proofs. At the end of the section, in Subsection 6.3, we transfer the results to the discrete model and prove Theorem 1.9 and Proposition 1.10. In the continuous setting, we recall that $(\mathcal{F}_{p,n}(t), t \ge 0)$ denotes the $p$-frozen model on $n$ vertices and $(\mathcal{G}_{p,n}(t), t \ge 0)$ the corresponding process of mass of gel. As mentioned in the Introduction, the presence of trees of size $k \in \mathbb{N}$ in the model is relative to the threshold time

$$t_{p,n}^{(k)} = \frac{\ln(n)}{kp} + \frac{k-1}{kp} \ln\left(\frac{\ln(n)}{kp}\right),$$

which is decreasing in $k$ provided that $n$ is large enough. Our main goal is to compare the last time at which there is a tree of size $k$ in the continuous model, denoted by $\mathcal{A}_{p,n}^{(k)}$, and the last time at which there is a tree of size greater or equal to $k$, denoted by $\mathcal{A}_{p,n}^{(k+)}$, to the threshold time $t_{p,n}^{(k)}$ (Theorem 6.9 and Theorem 6.10). In that aim we start by evaluating the number of trees of size $k$ at any time $t$. In particular, we prove that at time $t_{p,n}^{(k)} + c, c \in \mathbb{R}$, the number of trees of size $k$ converges in distribution towards a Poisson distribution whose parameter depends on $k, p, c$, the digamma function $\psi$ and the Euler constant $\gamma_E$ (Proposition 6.4).

## 6.1 On the number of trees of size $k$

Let

$$\mathcal{N}_{p,n}^{(k)}(t) = \frac{1}{k} \sum_{i=1}^{n} 1_{\{i \text{ belongs to a tree of size } k \text{ at time } t\}}$$

be the number of trees of size $k$ at time $t \ge 0$. In order to get some information on this quantity, we introduce the following notation. If $t_1, \dots, t_\ell$ are trees of size $k$ with vertices in $\{1, \dots, n\}$ and no common vertices (so necessarily $\ell k \le n$), we set for all times $t \ge 0$

$$P_n^{(k)}(\ell, t) := \mathbb{P}(t_1, \dots, t_\ell \text{ are connected components of } \mathcal{F}_{p,n}(t)).$$

A key observation is that this probability can be expressed as follows.
**Lemma 6.1.** For all $t \ge 0$,

$$P_n^{(k)}(\ell, t) = \left(1 - e^{-t/n}\right)^{\ell(k-1)} \left(e^{-t/n}\right)^{\frac{\ell k(\ell k-1)}{2} - \ell(k-1)} e^{-\frac{\ell k(n-\ell k)}{n}pt} \\ \times \mathbb{E}\left[e^{-\frac{\ell k(n-\ell k)}{n}(1-p)} \int_0^t \left(1 - \frac{G_{p,n-\ell k}(u)}{n-\ell k}\right) du\right]$$

where $G_{p,n-\ell k}$ is the gel mass process of a $\mathcal{F}_{p,n-\ell k}$ model.

This lemma, as well as the following results below and some technical corollaries to prepare Section 6.2, will be proved in Section 6.1.1 and Section 6.1.2.

Using the fluid limit approximation in the continuous model (Section 5.2), this result will in particular give us useful estimates to evaluate the asymptotic behavior of the moments of $\mathcal{N}_{p,n}^{(k)}(t_n)$ at some times $t_n$ that may depend on $n$. Indeed, one easily sees, recalling that there are $k^{k-2}$ different trees involving a fixed set of $k$ labeled vertices (this is Cayley's formula) and using the exchangeability of the vertices $1, \dots, n$, that

$$\mathbb{E}[\mathcal{N}_{p,n}^{(k)}(t)] = \frac{n}{k} \binom{n-1}{k-1} k^{k-2} P_n^{(k)}(1,t). \quad (6.1)$$

More generally we can express the factorial moments of $k\mathcal{N}_{p,n}^{(k)}(t)$ in terms of the probabilities $P_n^{(k)}(\ell, t)$. This is the aim of the following lemma, where $\mathcal{P}_j$ denotes the set of partitions of an integer $j$, i.e. the set of finite non-increasing sequences $(n_1, \dots, n_\ell) \in \mathbb{N}$, with $\ell$ the length of the sequence, such that $\sum_{i=1}^\ell n_i = j$. For such a sequence and all $1 \le i \le j$, we let $m_i$ denote the number of occurrences of the integer $i$ in the sequence.

**Lemma 6.2.** For all times $t \ge 0$ and all positive integers $j \le n$

$$\mathbb{E}\left[\prod_{i=0}^{j-1} (k\mathcal{N}_{p,n}^{(k)}(t) - i)\right] = \sum_{\substack{(n_1, \dots, n_\ell) \in \mathcal{P}_j \\ \text{such that } n_i \le k \ \forall i, \text{ and } \ell k \le n}} \frac{n!}{(n-k\ell)!} \binom{j}{n_1, \dots, n_\ell} \prod_{i=1}^{j} \frac{1}{m_i!} \prod_{i=1}^{l} \frac{1}{(k-n_i)!} \cdot (k^{k-2})^\ell P_n^{(k)}(\ell, t),$$

whereas $\prod_{i=0}^{j-1} (k\mathcal{N}_{p,n}^{(k)}(t) - i) = 0$ when $j > n$.

As said, together with the previous expression of the probabilities $P_n^{(k)}(\ell, t)$, this will allow us to obtain asymptotics of these moments. Notably this will lead us to the following estimates on expectation of the number of trees of size $k' \in \mathbb{N}$ at the threshold time $t_{p,n}^{(k)}$:

**Proposition 6.3.** For all $k, k' \in \mathbb{N}$ and $c \in \mathbb{R}$, as $n \to \infty$

$$\mathbb{E}[\mathcal{N}_{p,n}^{(k')}(\mathbf{t}_{p,n}^{(k)} + c)] = O\left(\left(\frac{n}{\ln(n)}\right)^{1-k'/k}\right).$$
And more precisely when $k' = k$:

**Proposition 6.4.** For all $k \in \mathbb{N}$ and all $c \in \mathbb{R}$

$$ \mathcal{N}_{p,n}^{(k)}(t_{p,n}^{(k)} + c) \xrightarrow[n \to \infty]{(d)} \mathcal{P} \left( \frac{k^{k-2}e^{-kpc}e^{-k(\psi(1/p)+\gamma_E)}}{k!} \right). $$

Additionally, we have the convergence of each positive moment of $\mathcal{N}_{p,n}^{(k)}(t_{p,n}^{(k)} + c)$ to the corresponding moment of the limit Poisson distribution.

### 6.1.1 Estimates on the probabilities $P_n^{(k)}(\ell, t)$

We set up in this part results related to the probabilities $P_n^{(k)}(\ell, t)$, starting with the proof of Lemma 6.1 and then several corollaries that will be useful in the sequel.

**Proof of Lemma 6.1.** By exchangeability, we may assume that $t_1, \dots, t_\ell$ are trees of size $k$ with vertices in $\{1, \dots, \ell k\}$ and no common vertices. Note that the evolution process of the graph reduced to the vertices $\ell k + 1, \dots, n$ before there are interactions with vertices $1, \dots, \ell k$ follows the $\mathcal{F}_{p,n-\ell k}$ model. The trees $t_1, \dots, t_\ell$ are then connected components of $\mathcal{F}_{p,n}(t)$ if and only if:

* the $\ell(k-1)$ edges of the $\ell$ trees $t_1, \dots, t_\ell$ have been added at time $t$, which happens with probability $(1 - e^{-t/n})^{\ell(k-1)}$

* and, the $\ell k(\ell k - 1)/2 - \ell(k-1)$ other possible edges between the vertices $1, \dots, \ell k$ have not been added at time $t$, which happens with probability $(e^{-t/n})^{\frac{\ell k(\ell k-1)}{2} - \ell(k-1)}$, independently

* and, the $\ell k(n-\ell k)$ edges between one of the vertices $1, \dots, \ell k$ and one of the vertices $\ell k+1, \dots, n$ have not been added before time $t$: conditioning on the dynamic of the vertices $\ell k + 1, \dots, n$, this happens with probability

$$ \mathbb{E} \left[ e^{-\frac{\ell k}{n} \left( \int_0^t (n-\ell k - \mathcal{G}_{p,n-\ell k}(u)) du + p \int_0^t \mathcal{G}_{p,n-\ell k}(u) du \right)} \right] = \mathbb{E} \left[ e^{-\frac{\ell k(n-\ell k)}{n} \left( pt + (1-p) \int_0^t \left( 1 - \frac{\mathcal{G}_{p,n-\ell k}(u)}{n-\ell k} \right) du \right)} \right], $$

independently.

This gives the announced expression of $P_n^{(k)}(\ell, t)$. $\square$

This easily leads us to:

**Corollary 6.5.** For any sequence of times $(t_n)$ such that $t_n \to \infty$ and $t_n = o(n)$, for all $\ell \in \mathbb{N}$,

$$ \begin{aligned} P_n^{(k)}(\ell, t_n) &= \left(\frac{t_n}{n}\right)^{\ell(k-1)} e^{-\ell k p t_n - \ell k(\psi(1/p)+\gamma_E)+o(1)} \\ &= (P_n^{(k)}(1, t_n))^{\ell} (1 + o(1)). \end{aligned} $$
In particular, for all $c \in \mathbb{R}$

$$n^k \cdot P_n^{(k)}(1, \mathbf{t}_{p,n}^{(k)} + c) \underset{n \to \infty}{\longrightarrow} e^{-kpc} \cdot e^{-k(\psi(1/p) + \gamma_E)}.$$

**Proof.** • From the expression of Lemma 6.1, we immediately see that when $t_n \to \infty$ and $t_n = o(n)$,

$$P_n^{(k)}(\ell, t_n) = \left(\frac{t_n}{n}\right)^{\ell(k-1)} e^{-\ell k p t_n + O\left(\frac{t_n}{n}\right)} \cdot \mathbb{E} \left[ e^{-\ell k(1-p)} \int_0^{t_n} \left(1 - \frac{G_{p,n-\ell k(u)}}{n-\ell k}\right) du + O\left(\frac{t_n}{n}\right) \right],$$

where the $O(\frac{t_n}{n})$ in the expectation is deterministic. So by Corollary 5.2 and then Lemma 3.2,

$$\mathbb{E} \left[ e^{-\ell k(1-p)} \int_0^{t_n} \left( 1 - \frac{G_{p,n-\ell k(u)}}{n-\ell k} \right) du + O\left( \frac{t_n}{n} \right) \right] \underset{n \to \infty}{\longrightarrow} e^{-\ell k(\psi(1/p) + \gamma_E)}.$$

• Applying this to $t_n = \mathbf{t}_{p,n}^{(k)} + c$ immediately gives $n^k \cdot P_n^{(k)}(1, \mathbf{t}_{p,n}^{(k)} + c) \to e^{-kpc} \cdot e^{-k(\psi(1/p) + \gamma_E)}$. $\square$

We will also need the following control in order to apply, later in Section 6.1.2, the Dominated Convergence Theorem.

**Corollary 6.6.** Fix $c \in \mathbb{R}$. For every $\varepsilon > 0$, there exists $\ell_\varepsilon \in \mathbb{N}$ and $n_\varepsilon \in \mathbb{N}$ such that

$$\frac{n!}{\ell!(n-k\ell)!} \cdot P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \le \varepsilon^\ell, \quad \text{for all } n \ge n_\varepsilon \text{ and all } \ell_\varepsilon \le \ell \le n/k.$$

**Proof.** The "constants" $c_1, c_2, c_3$ appearing in this proof may depend on $k$ and $c$, but not on $n$ or $\ell \le n/k$. On the one hand, by Stirling's formula, there exists some constant $c_1$ such that

$$\frac{n!}{\ell!(n-k\ell)!} \le \frac{n^{k\ell}}{\ell!} \le c_1 n^{k\ell} e^{\ell - \ell \ln(\ell)}, \quad \forall n, \ell \ge 1, \ell \le n/k. \qquad (6.2)$$

On the other hand, since the expectation involved in the expression of $P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c)$ is bounded from above by 1, and since $1 - e^{-x} \le x$ for all $x \ge 0$,

$$P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \le \left( \frac{\mathbf{t}_{p,n}^{(k)} + c}{n} \right)^{\ell(k-1)} \cdot e^{-\frac{\mathbf{t}_{p,n}^{(k)} + c}{n} \left( \frac{\ell k(\ell k-1)}{2} - \ell(k-1) + p\ell k(n-\ell k) \right)}.$$

It is easy to see, using the definition of $\mathbf{t}_{p,n}^{(k)}$, that for $n$ large enough, simultaneously for all $\ell \ge 1$,

$$e^{\ell(k-1) \ln(\mathbf{t}_{p,n}^{(k)} + c) - p\ell k \mathbf{t}_{p,n}^{(k)}} \le \frac{e^{\ell}}{n^{\ell}}.$$

And also, for $\ell \le n/k$, that

$$e^{\frac{-c}{n} \left( \frac{\ell k (\ell k - 1)}{2} - \ell (k-1) + p \ell k (n - \ell k) \right)} \le e^{c_2 \ell}.$$
for some constant $c_2 \in (0, \infty)$. This implies that

$$P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \le \frac{e^{(1+c_2)\ell}}{\eta^{k\ell}} \cdot e^{-\frac{\mathbf{t}_{p,n}^{(k)}}{n}\left(\frac{\ell k (\ell k - 1)}{2} - \ell(k-1) - p(\ell k)^2\right)}. \quad (6.3)$$

• If $p \le 1/2$, $\frac{\ell k (\ell k - 1)}{2} - \ell(k-1) - p(\ell k)^2 \ge -\frac{3\ell k}{2}$ for all $\ell \ge 1$, so we have that, since moreover $\mathbf{t}_{p,n}^{(k)} \ge 0$ and $\frac{\mathbf{t}_{p,n}^{(k)}}{n} \to 0$ as $n \to \infty$,

$$P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \le \frac{e^{c_3 \ell}}{n^{k\ell}}$$

for all $n$ large enough and all $\ell \ge 1$. Together with (6.2) this clearly leads to the statement of the corollary.

• If $p \in (1/2, 1]$, consider $\eta > 0$ such that $a := (1 + \eta)^2(1 - \frac{1}{2p}) \in (0, 1)$. We then use that $\frac{\mathbf{t}_{p,n}^{(k)}}{n} \le (1 + \eta) \frac{\ln(n)}{kpn}$ for $n$ large enough, and that $-\frac{\ell k (\ell k - 1)}{2} + \ell(k-1) + p(\ell k)^2 \le (1 + \eta)(p - \frac{1}{2})(\ell k)^2$ for $\ell$ large enough, to get for those $n, \ell$, using (6.3),

$$P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \le \frac{e^{(1+c_2)\ell}}{n^{k\ell}} \cdot e^{(1+\eta)^2 \frac{\ln(n)}{n} \cdot (1-\frac{1}{2p})\ell^2 k} = \frac{e^{\ell((1+c_2)+a\frac{\ln(n)}{n}\ell k)}}{n^{k\ell}}$$

Together with (6.2), we obtain for those $n, \ell$, assuming moreover that $c_1 \le e^\ell$,

$$\frac{n!}{\ell!(n-k\ell!)} \cdot P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \le e^{\ell((3+c_2)+a\frac{\ln(n)}{n}\ell k - \ln(\ell))} = e^{\ell h(\ell)} \quad (6.4)$$

where $h(x) := (3+c_2)+a\frac{\ln(n)}{n}xk - \ln(x)$. One easily sees that this function is convex on $(0, \infty)$, with

$$h(x) \le 3 + c_2 + \max \left( a \frac{\ln(n)}{n} x_0 k - \ln(x_0); a \ln(n) - \ln(n/k) \right) \quad \text{when } x \in [x_0; n/k]$$

(whatever $x_0 > 0$ is). For every $\varepsilon > 0$, there exists $\tilde{\ell}_\varepsilon \in \mathbb{N}$ such that $3 + c_2 + 1 - \ln(\tilde{\ell}_\varepsilon) \le \ln(\varepsilon)$. Then, take $x_0 = \tilde{\ell}_\varepsilon$. Next, there exists $\tilde{n}_\varepsilon \in \mathbb{N}$ such that for all $n \ge \tilde{n}_\varepsilon$, we have both $3 + c_2 + a \ln(n) - \ln(n/k) \le \ln(\varepsilon)$ (since $a < 1$) and $a \frac{\ln(n)}{n} \tilde{\ell}_\varepsilon k \le 1$. All this implies that for $n \ge \tilde{n}_\varepsilon$ and then $\ell \in [\tilde{\ell}_\varepsilon, n/k]$,

$$h(\ell) \le \ln(\varepsilon).$$

Together with (6.4), this gives the expected upper bound. $\square$

Last, we set up the following bound, in order to prove later Corollary 6.8.

**Corollary 6.7.** Let $k \in \mathbb{N}$, $c \in \mathbb{R}$. Then for all $n$ large enough,

$$\sup_{k+1 \le i \le n} e^i \cdot n^i \cdot P_n^{(i)}(1, \mathbf{t}_{p,n}^{(k)} + c) \le \frac{1}{n^{\frac{1}{2k}}}. $$
**Proof.** From Lemma 6.1,

$$ 
\begin{aligned}
e^i \cdot n^i \cdot P_n^{(i)}(1, \mathbf{t}_{p,n}^{(k)} + c) &\le e^{i+i \ln(n)+(i-1)\ln\left(\frac{\mathbf{t}_{p,n}^{(k)}+c}{n}\right) - \left(\frac{i(i-1)}{2} - (i-1)\right)\frac{\mathbf{t}_{p,n}^{(k)}+c}{n} - \frac{i(n-i)}{n}p(\mathbf{t}_{p,n}^{(k)}+c)} \\
&= e^{\ln(n) \cdot h_n(i)}
\end{aligned}
$$

where $h_n$ is the polynomial of degree 2 defined for $x \in \mathbb{R}$ by

$$ h_n(x) = \frac{x}{\ln(n)} + x + (x-1) \frac{\ln\left(\frac{\mathbf{t}_{p,n}^{(k)}+c}{n}\right)}{\ln(n)} - \left(\frac{x(x-1)}{2} - (x-1)\right) \frac{\mathbf{t}_{p,n}^{(k)} + c}{n \ln(n)} - \frac{x(n-x)}{n \ln(n)} p(\mathbf{t}_{p,n}^{(k)} + c). $$

We let the reader check that as $n \to \infty$,

$$ h_n(k+1) \to -1/k, \quad h'_n(k+1) \to -1/k, \quad h'_n(n) \to -(1-p)/kp. $$

Hence when $p \in (0, 1)$, for $n$ large enough, $h'_n$ is strictly negative, and therefore $h_n$ strictly decreasing, on $[k+1, n]$, uniformly smaller than $-1/2k$ (for $n$ large enough). When $p = 1$, $h''_n(x) = \frac{\mathbf{t}_{p,n}^{(k)}+c}{n\ln(n)}$ for all $x$, hence for $n$ large enough $g_n$ is convex, and $h_n(n) \sim -n/2k$ which, together with $h_n(k+1) \to -1/k$, implies that $h_n$ is also uniformly smaller than $-1/2k$ on $[k+1, n]$ for $n$ large enough.

In conclusion, whatever $p \in (0, 1]$, we have that for $n$ large enough and then all $i \in [k+1, n]$,

$$ e^i \cdot n^i \cdot P_n^{(i)}(1, \mathbf{t}_{p,n}^{(k)} + c) \le e^{-\ln(n) \frac{1}{2k}}. $$

□

### 6.1.2 Moments and asymptotics of $N_{p,n}^{(k)}$

We start this section with the proof of the identities of Lemma 6.2. We will then see how to use them to prove, together with the estimates of Corollary 6.5 and Corollary 6.6, the bounds on $N_{p,n}^{(k')}(\mathbf{t}_{p,n}^{(k)}+c)$, $k' \in \mathbb{N}$ of Proposition 6.3 and the asymptotic distribution of $N_{p,n}^{(k)}(\mathbf{t}_{p,n}^{(k)} + c)$ stated in Proposition 6.4. Last, in complement and to prepare the next section on the behavior of the times $A_{p,n}^{(k)}$, $A_{p,n}^{(k+)}$, we set up a corollary saying that there is asymptotically no tree of size strictly larger than $k$ at time $\mathbf{t}_{p,n}^{(k)} + c$, for any $c$ (Corollary 6.8).

**Proof of Lemma 6.2.** Since $kN_{p,n}^{(k)}(t) \in [0; n]$, its $j$-th factorial moment is null when $j > n$. In the sequel we fix $j \le n$. For $1 \le i \le n$ and $t \ge 0$, consider the random variable

$$ Y_{n,i} := 1_{\{\text{the vertex } i \text{ belongs to a tree of size } k \text{ at time } t\}} $$

so that $kN_{p,n}^{(k)}(t) = \sum_{i=1}^n Y_{n,i}$. The five lines that follow are classical in the study of random graphs: using that $Y_{n,i}^2 = Y_{n,i}$, one sees by induction (on $j$) that

$$ \prod_{i=0}^{j-1} (k N_{p,n}^{(k)}(t) - i) = \sum_{1 \le i_1 \ne i_2 \ne \dots \ne i_j \le n} \prod_{m=1}^{j} Y_{n,im}. $$
Since the random variables $Y_{n,i}$, $1 \le i \le n$ are exchangeable, this gives the following expression for the $j$-th factorial moment of $k\mathcal{N}_{p,n}^{(k)}(t)$:

$$ \mathbb{E}\left[\prod_{i=0}^{j-1} (k\mathcal{N}_{p,n}^{(k)}(t) - i)\right] = \frac{n!}{(n-j)!} \cdot \mathbb{E}\left[\prod_{i=1}^{j} Y_{n,i}\right]. $$

Next, $\mathbb{E}[\prod_{i=1}^{j} Y_{n,i}]$ is the probability that the vertices $1, \dots, j$ belong to a tree of size $k$ at time $t$. By decomposing according to the number of vertices among $1, \dots, j$ which belong to a same tree of size $k$ – which gives a partition of $j$ – and using that the number of trees on $k$ labeled vertices is $k^{k-2}$, we obtain:

$$ \mathbb{E}\left[\prod_{i=1}^{j} Y_{n,i}\right] = \sum_{\substack{(n_1, \dots, n_\ell) \in \mathcal{P}_j, \\ n_i \le k \ \forall i, \ \ell k \le n}} \binom{j}{n_1, \dots, n_\ell} \cdot \frac{1}{\prod_{i=1}^j m_i!} \cdot \binom{n-j}{k-n_1, \dots, k-n_\ell, n-k\ell} \cdot (k^{k-2})^\ell P_n^{(k)}(\ell, t). $$

Together with the above expression of the $j$-th factorial moment of $k\mathcal{N}_{p,n}^{(k)}(t)$ this gives the result. $\square$

**Proof of Proposition 6.3.** We combine (6.1) with Corollary 6.5 and the definition of $t_{p,n}^{(k)}$, to see that

$$ \begin{align*} \mathbb{E}[\mathcal{N}_{p,n}^{(k')}(t_{p,n}^{(k)} + c)] & \underset{n \to \infty}{\sim} n^{k'} \cdot \frac{k'^{k'-2}}{k'!} \cdot P_n^{(k')}(1, t_{p,n}^{(k)} + c) \\ & \underset{n \to \infty}{\sim} n^{k'} \cdot \frac{k'^{k'-2}}{k'!} \cdot n^{1-k'-\frac{k'}{k}} \cdot (\ln(n))^{\frac{k'}{k}-1} \cdot (kp)^{\frac{k'}{k}-k'} \cdot e^{-k'pc-k'(\psi(1/p)+\gamma_E)} \\ & = O\left(\left(\frac{n}{\ln(n)}\right)^{1-k'/k}\right). \end{align*} $$

$\square$

**Proof of Proposition 6.4.** 1) We start with the convergence in distribution and in that aim use that the probability generating function of a $[0; n]$-valued random variable can be expressed in terms of its factorial moments, which here gives

$$ \mathbb{E}\left[x^{k\mathcal{N}_{p,n}^{(k)}}(t_{p,n}^{(k)} + c)\right] = 1 + \sum_{j=1}^{n} \frac{(x-1)^j}{j!} \mathbb{E}\left[\prod_{i=0}^{j-1} (k\mathcal{N}_{p,n}^{(k)}(t_{p,n}^{(k)} + c) - i)\right], \quad \forall x \in \mathbb{R}. $$
From Lemma 6.2, we rewrite the sum as follows

$$
\begin{align*}
& \sum_{j=1}^{n} \frac{(x-1)^j}{j!} \mathbb{E} \left[ \prod_{i=0}^{j-1} (k \mathcal{N}_{p,n}^{(k)}(\mathbf{t}_{p,n}^{(k)} + c) - i) \right] \\
&= \sum_{j=1}^{n} \frac{(x-1)^j}{j!} \sum_{\substack{(n_1, \dots, n_\ell) \in \mathcal{P}_j \\ n_i \le k \forall i, \ell k \le n}} \frac{n!}{(n-k\ell)!} \left( \binom{j}{n_1, \dots, n_\ell} \right) \prod_{i=1}^{j} \frac{1}{m_i!} \prod_{i=1}^{\ell} \frac{1}{(k-n_i)!} \cdot (k^{k-2})^\ell P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \\
&= \sum_{\ell=1}^{\lfloor n/k \rfloor} \frac{1}{\ell!} \frac{1}{(k!)^\ell} \sum_{n_1=1}^{k} \cdots \sum_{n_\ell=1}^{k} \prod_{i=1}^{\ell} \binom{k}{n_i} \cdot \frac{n!}{(n-k\ell)!} (k^{k-2})^\ell P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \cdot (x-1)^{\sum_{i=1}^\ell n_i} \\
&= \sum_{\ell=1}^{\lfloor n/k \rfloor} \frac{1}{\ell!} \frac{1}{(k!)^\ell} \cdot \frac{n!}{(n-k\ell)!} (k^{k-2})^\ell P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \left( \sum_{m=1}^{k} \binom{k}{m} (x-1)^m \right)^\ell \\
&= \sum_{\ell=1}^{\lfloor n/k \rfloor} \frac{1}{\ell!} \frac{1}{(k!)^\ell} \cdot \frac{n!}{(n-k\ell)!} (k^{k-2})^\ell P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) (x^k - 1)^\ell.
\end{align*}
$$

Next, from Corollary 6.5, for each fixed $\ell \in \mathbb{N}$,

$$
\frac{n!}{(n-k\ell)!} P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) \xrightarrow{n \to \infty} \left( e^{-kpc} \cdot e^{-k(\psi(1/p)+\gamma_E)} \right)^{\ell},
$$

which leads to

$$
\mathbb{E} \left[ x^{k} \mathcal{N}_{p,n}^{(k)} (\mathbf{t}_{p,n}^{(k)} + c) \right] \xrightarrow{n \to \infty} e^{\frac{k(k-2)}{k!} e^{-kpc} \cdot e^{-k(\psi(1/p)+\gamma_E)} (x-1)}, \quad \forall x \in \mathbb{R},
$$

since we can use the Dominated Convergence Theorem thanks to Corollary 6.6 (taking there, e.g., $\varepsilon$
such that $\varepsilon(x^k - 1)^{\frac{k(k-2)}{k!}} \le \frac{1}{2}$).

Consequently, the probability generating function of $\mathcal{N}_{p,n}^{(k)}(\mathbf{t}_{p,n}^{(k)} + c)$ has the following asymptotic
behavior

$$
\mathbb{E} \left[ x^{k} \mathcal{N}_{p,n}^{(k)} (\mathbf{t}_{p,n}^{(k)} + c) \right] \xrightarrow{n \to \infty} e^{\frac{k(k-2)}{k!} e^{-kpc} \cdot e^{-k(\psi(1/p)+\gamma_E)} (x-1)}, \quad \forall x \in \mathbb{R},
$$

and we recognize in the right-hand side the probability generating function of the Poisson distribution
with parameter $\frac{k^{k-2}}{k!} e^{-kpc} \cdot e^{-k(\psi(1/p)+\gamma_E)}$.

2) Using the same arguments, we see that for each fixed $j \in \mathbb{N}$,

$$
\mathbb{E} \left[ \prod_{i=0}^{j-1} (k \mathcal{N}_{p,n}^{(k)}(\mathbf{t}_{p,n}^{(k)} + c) - i) \right] \le j! \sum_{\ell=1}^{\lfloor n/k \rfloor} \frac{(k^{k-2})^\ell}{\ell!} \frac{1}{(k!)^\ell} \cdot \frac{n!}{(n-k\ell)!} P_n^{(k)}(\ell, \mathbf{t}_{p,n}^{(k)} + c) (2^k - 1)^\ell,
$$

which, thanks to Corollary 6.5 and Corollary 6.6, is bounded from above by a finite number indepen-
dent of $n$. This holds for all $j \in \mathbb{N}$, consequently any positive moment of $\mathcal{N}_{p,n}^{(k)}(\mathbf{t}_{p,n}^{(k)} + c)$ is bounded
from above independently of $n$. Together with the convergence in distribution of $\mathcal{N}_{p,n}^{(k)}(\mathbf{t}_{p,n}^{(k)} + c)$ to the
Poisson distribution with parameter $k^{k-2}e^{-kpc} \cdot e^{-k(\psi(1/p)+\gamma_E)}/k!$, this is sufficient to get the conver-
gence of every positive moment of $\mathcal{N}_{p,n}^{(k)}(\mathbf{t}_{p,n}^{(k)} + c)$ to the corresponding moment of the limit Poisson
distribution.
$\square$
Last, the expression (6.1) of the expectation of $\mathcal{N}_{p,n}^{(i)}(t)$ for $i \ge k+1$, together with Corollary 6.7, give immediately that with high probability, there is no tree of size strictly larger than $k$ at times $t_{p,n}^{(k)}+c$, for any $c$:

**Corollary 6.8.** For every $k \in \mathbb{N}$ and every $c \in \mathbb{R}$,

$$ \mathbb{P} \left( \text{there exists a tree of size} \geq k+1 \text{ at time } t_{p,n}^{(k)} + c \right) \xrightarrow{n \to \infty} 0. $$

**Proof.** From (6.1),

$$ \begin{aligned} \mathbb{P} \left( \text{there exists a tree of size} \geq k+1 \text{ at time } \mathbf{t}_{p,n}^{(k)} + c \right) &\leq \sum_{i=k+1}^{n} \mathbb{P} \left( \mathcal{N}_{p,n}^{(i)} (\mathbf{t}_{p,n}^{(k)} + c) \geq 1 \right) \\ &\leq \sum_{i=k+1}^{n} \mathbb{E} \left[ \mathcal{N}_{p,n}^{(i)} (\mathbf{t}_{p,n}^{(k)} + c) \right] \\ &\leq \sum_{i=k+1}^{n} n^i \frac{i^{i-2}}{i!} P_n^{(i)} (1, \mathbf{t}_{p,n}^{(k)} + c). \end{aligned} $$

By Stirling's formula, $\frac{i^{i-2}}{i!} \le C \frac{e^i}{i^2\sqrt{i}}$ for some finite $C$ and all $i \ge 1$. Together with Corollary 6.7, this implies that for $n$ large enough

$$ \begin{aligned} \mathbb{P} \left( \text{there exists a tree of size} \geq k+1 \text{ at time } \mathbf{t}_{p,n}^{(k)} + c \right) &\leq C \sum_{i=k+1}^{n} n^i \frac{e^i}{i^2 \sqrt{i}} P_n^{(i)} (1, \mathbf{t}_{p,n}^{(k)} + c) \\ &\leq \frac{C}{n^{\frac{1}{2k}}} \sum_{i=k+1}^{n} \frac{1}{i^2 \sqrt{i}} \end{aligned} $$

which converges to 0 as $n \to \infty$. $\square$

## 6.2 Asymptotics of $\mathcal{A}_{p,n}^{(k)}$, $\mathcal{A}_{p,n}^{(k+)}$

We are now ready to study the last times at which there is a tree of size $k \in \mathbb{N}$ or of size greater or equal to $k$ in the model $\mathcal{F}_{p,n}$:

$$ \mathcal{A}_{p,n}^{(k)} = \sup \left\{ t \ge 0 : \mathcal{N}_{p,n}^{(k)}(t) \ge 1 \right\}, \quad \mathcal{A}_{p,n}^{(k+)} = \sup \left\{ t \ge 0 : \sum_{i \ge k} \mathcal{N}_{p,n}^{(i)}(t) \ge 1 \right\}. $$

We recall that Gu denote a standard Gumbel distribution.

**Theorem 6.9.** For all $k \in \mathbb{N}$

$$ \mathcal{A}_{p,n}^{(k)} - \mathbf{t}_{p,n}^{(k)} \xrightarrow[n \to \infty]{(d)} \frac{\text{Gu}}{kp} - \frac{\Psi(1/p) + \gamma_E}{p} + \frac{\ln(k^{k-2}/k!)}{kp}. $$
Since $t_{p,n}^{(k)} \ll t_{p,n}^{(k-1)}$ as $n \to \infty$, a consequence of this result is that $\mathbb{P}(\mathcal{A}_{p,n}^{(k)} < \mathcal{A}_{p,n}^{(k-1)} < \dots < \mathcal{A}_{p,n}^{(1)}) \to 1$ for all $k \ge 2$. This alone is however not sufficient to claim that there is asymptotically no trees of size larger than $k$ after $\mathcal{A}_{p,n}^{(k)}$, but we can improve it as follows.

**Theorem 6.10.** For all $k \in \mathbb{N}$,

$$ \mathbb{P}(\mathcal{A}_{p,n}^{(k+)} = \mathcal{A}_{p,n}^{(k)}) \underset{n \to \infty}{\longrightarrow} 1. $$

Consequently,

$$ \mathcal{A}_{p,n}^{(k+)} - t_{p,n}^{(k)} \xrightarrow{n \to \infty} \frac{G}{kp} - \frac{\Psi(1/p) + \gamma_E}{p} + \frac{\ln(k^{k-2}/k!)}{kp}. $$

In particular, this gives the asymptotic behavior of the total gelation time, $\mathcal{A}_{p,n}^{(1+)} = \inf\{t \ge 0 : G_{p,n}(t) = n\}$.

To prove these results, we start by setting some preliminary lemmas.

### 6.2.1 Preliminaries

In the following lemmas, c.c. is used as an abbreviation of connected component.

**Lemma 6.11.** Fix $\ell_1, \ell_2 \in \mathbb{N}$. For $n \ge \ell_1 + \ell_2$, consider $t_1, t_2$ two trees with vertices in $\{1, \dots, n\}$ and no common vertices, with respective sizes $\ell_1, \ell_2$. Then for every stopping time $T > 0$,

$$ \mathbb{P}(t_1, t_2 \text{ connect during the process to give a tree of size } \ell_1 + \ell_2 \mid t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(T)) \\ \le \frac{\ell_1 \ell_2}{p(n-1)}. $$

**Proof.** We let $V(t_i)$ denote the set of vertices of $t_i$, for $i = 1, 2$. We also let $T < s_1 < s_2 < \dots$ be the times larger than $T$ at which the PPP governing $\mathcal{F}_{p,n}$ rings, set $s_0 = T$, and introduce for $i \ge 1$ the events:

* $E_n(s_i) = \{\text{at time } s_i \text{ an edge is added between a vertex of } V(t_1) \text{ and a vertex of } V(t_2)\}$

* $\tilde{E}_n(s_i) = \{\text{at time } s_i \text{ an edge stemming from either a vertex of } V(t_1) \text{ or a vertex of } V(t_2) \text{ is added in the process}\}$.

Note that

$$ \begin{align*} & \mathbb{P}(t_1, t_2 \text{ connect during the process to give a tree of size } \ell_1 + \ell_2 \mid t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(T)) \\ &= \mathbb{P}\left(\bigcup_{i=1}^{\infty} E_n(s_i) \cap_{j=1}^{i-1} (\tilde{E}_n(s_j))^c \mid t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(T)\right) \\ &= \sum_{i=1}^{\infty} \mathbb{P}\left(E_n(s_i) \cap_{j=1}^{i-1} (\tilde{E}_n(s_j))^c \mid t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(T)\right). \end{align*} $$
The dynamic of the process $\mathcal{F}_{p,n}$ implies that when $t_1, t_2$ are c.c. of $\mathcal{F}_{p,n}(s_{i-1})$, for all $i \ge 1$:

$$ \mathbb{P}(E_n(s_i) | t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(s_{i-1})) = \frac{2\ell_1\ell_2}{n(n-1)} $$

and

$$ \begin{align*} \mathbb{P}(\tilde{E}_n(s_i) | t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(s_{i-1}), \mathcal{G}_{p,n}(s_{i-1})) & = \frac{2}{n(n-1)} \cdot (\ell_1(n - \mathcal{G}_{p,n}(s_{i-1}) - 1) + \ell_2(n - \mathcal{G}_{p,n}(s_{i-1}) - 1 - \ell_1) + (\ell_1 + \ell_2)p\mathcal{G}_{p,n}(s_{i-1})) \\ & = \frac{2}{n(n-1)} \cdot ((\ell_1 + \ell_2)(n - (1-p)\mathcal{G}_{p,n}(s_{i-1}) - 1) - \ell_1\ell_2) \\ & \ge \frac{2}{n(n-1)} \cdot ((\ell_1 + \ell_2)(pn + (1-p)(\ell_1 + \ell_2) - 1) - \ell_1\ell_2), \end{align*} $$

where we have used in the last line that $\mathcal{G}_{p,n}(s_{i-1}) \le n - (\ell_1 + \ell_2)$ when $t_1, t_2$ are c.c. of $\mathcal{F}_{p,n}(s_{i-1})$. This leads to

$$ \mathbb{P}(\tilde{E}_n(s_i) | t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(s_{i-1})) \ge \frac{2p}{n} $$

(to see this note that for $n \ge \ell_1+\ell_2+1$, the function $p \mapsto (\ell_1+\ell_2)(pn+(1-p)(\ell_1+\ell_2)-1)-\ell_1\ell_2-(n-1)p$ is increasing in $p$ and positive for $p=0$; whereas for $n = \ell_1 + \ell_2$ it is decreasing in $p$ and positive for $p=1$). We then use these bounds to get

$$ \begin{align*} \sum_{i=1}^{\infty} \mathbb{P} \left( E_n(s_i) \cap_{j=1}^{i-1} (\tilde{E}_n(s_j))^c \mid t_1, t_2 \text{ are c.c. of } \mathcal{F}_{p,n}(T) \right) & \le \sum_{i=1}^{\infty} \frac{2\ell_1\ell_2}{n(n-1)} \cdot \left(1 - \frac{2p}{n}\right)^{i-1} \\ & = \frac{\ell_1\ell_2}{p(n-1)}. \end{align*} $$

□

In fact, we will only need that the order of magnitude of this probability is $O(1/n)$. More generally, for every fixed $i \ge 2$ and $m \ge 2$, we have

**Lemma 6.12.** Let $(\ell_1, \dots, \ell_m) \in \mathbb{N}^m$, with $\sum_{j=1}^m \ell_j = i$. For $n \ge i$, consider $t_1, \dots, t_m$ some trees with vertices in $\{1, \dots, n\}$ and no common vertices, with respective sizes $\ell_1, \dots, \ell_m \in \mathbb{N}$. Then for every time $t > 0$,

$$ \mathbb{P}(t_1, \dots, t_m \text{ connect during the process to give a tree of size } i \mid t_1, \dots, t_m \text{ are c.c. of } \mathcal{F}_{p,n}(t)) = O\left(\frac{1}{n^{m-1}}\right). $$

**Proof.** Since only two trees can connect at a time, this is easily proved by induction on $m$, using the previous lemma. □
Consequently,

**Lemma 6.13.** When $k \ge 2$, for any $c \in \mathbb{R}$,

$$ \mathbb{P} \left( \text{a tree of size } \ge k \text{ is formed after time } t_{p,n}^{(k)} + c \right) \xrightarrow{n \to \infty} 0. $$

**Proof.** • We start by proving that for any $i \ge k$,

$$ \mathbb{P} \left( \text{a tree of size } i \text{ is formed after } t_{p,n}^{(k)} + c \right) \xrightarrow{n \to \infty} 0. \qquad (6.5) $$

Indeed, for $i \ge k$,

$$ \begin{aligned} & \mathbb{P} \left( \text{a tree of size } i \text{ is formed after } t_{p,n}^{(k)} + c \right) \\ \le & \sum_{m=2}^{i} \sum_{\substack{\ell_1 \ge \dots \ge \ell_m \\ \sum_{j=1}^{m} \ell_j = i}} \mathbb{P} \left( \text{a tree of size } i \text{ is formed after time } t_{p,n}^{(k)} + c \text{ from } m \text{ trees present at time } t_{p,n}^{(k)} + c \text{ with respective sizes } \ell_1, \dots, \ell_m \right) \\ = & \sum_{m=2}^{i} \sum_{\substack{\ell_1 \ge \dots \ge \ell_m \\ \sum_{j=1}^{m} \ell_j = i}} \mathbb{P} \left( \text{a tree of size } i \text{ is formed after time } t_{p,n}^{(k)} + c \text{ from } m \text{ trees present at time } t_{p,n}^{(k)} + c \text{ with respective sizes } \ell_1, \dots, \ell_m; \mathcal{N}_{p,n}^{(\ell_j)}(t_{p,n}^{(k)} + c) \le (\ln(n))^{\frac{1}{2}} \left( \frac{n}{\ln(n)} \right)^{1-\frac{\ell_j}{k}} \quad \forall 1 \le j \le m \right) \\ & + o(1) \end{aligned} $$

where the $o(1)$ (relative to $n \to \infty$) is a consequence of Proposition 6.3. We then conclude with Lemma 6.12 and again Proposition 6.3 which imply that when $\sum_{j=1}^{m} \ell_j = i$,

$$ \begin{aligned} & \mathbb{P} \left( \text{a tree of size } i \text{ is formed after time } t_{p,n}^{(k)} + c \text{ from } m \text{ trees present at time } t_{p,n}^{(k)} + c \right. \\ & \qquad \left. \text{with respective sizes } \ell_1, \dots, \ell_m; \mathcal{N}_{p,n}^{(\ell_j)}(t_{p,n}^{(k)} + c) \le (\ln(n))^{\frac{1}{2}} \left( \frac{n}{\ln(n)} \right)^{1-\frac{\ell_j}{k}}, \forall 1 \le j \le m \right) \\ \le & O \left( \frac{1}{n^{m-1}} \right) \cdot \left( \prod_{j=1}^{m} (\ln(n))^{\frac{1}{2}} \left( \frac{n}{\ln(n)} \right)^{1-\frac{\ell_j}{k}} \right) \\ = & O \left( (\ln(n))^{\frac{i}{k}-\frac{m}{2}} \cdot n^{1-\frac{i}{k}} \right) \end{aligned} $$

which converges to 0 as soon as $i \ge k$.

• Next, to improve this in $\mathbb{P}(\text{a tree of size } \ge k \text{ is formed after } t_{p,n}^{(k)} + c) \to 0 \text{ as } n \to \infty$, we bound from above this probability by

$$ \mathbb{P} \left( \text{a tree of size } \ge 2k+1 \text{ is formed after } t_{p,n}^{(k)} + c \right) + \sum_{i=k}^{2k} \mathbb{P} \left( \text{a tree of size } i \text{ is formed after } t_{p,n}^{(k)} + c \right) $$
and note that (since only two trees can connect at a time)

$$ \mathbb{P}(\text{a tree of size } \ge 2k+1 \text{ is formed after } t_{p,n}^{(k)} + c) \le \mathbb{P}(\text{there is a tree of size } \ge k+1 \text{ at time } t_{p,n}^{(k)} + c) + \sum_{i=k}^{2k} \mathbb{P}(\text{a tree of size } i \text{ is formed after } t_{p,n}^{(k)} + c). $$

So, we have

$$ \mathbb{P}(\text{a tree of size } \ge k \text{ is formed after } t_{p,n}^{(k)} + c) \le \mathbb{P}(\text{there is a tree of size } \ge k+1 \text{ at time } t_{p,n}^{(k)} + c). $$

and this last sum converges to 0 according to (6.5) and Corollary 6.8. $\square$

### 6.2.2 Proof of Theorem 6.9

Since $\mathcal{N}_{p,n}^{(k)}(t)$ is the number of trees of size $k$ present at time $t$, we have, for any $c \in \mathbb{R}$,

$$ \begin{aligned} \mathbb{P}(\mathcal{N}_{p,n}^{(k)}(t_{p,n}^{(k)} + c) \ge 1) &\le \mathbb{P}(\mathcal{A}_{p,n}^{(k)} > t_{p,n}^{(k)} + c) \\ &\le \mathbb{P}(\mathcal{N}_{p,n}^{(k)}(t_{p,n}^{(k)} + c) \ge 1) + \mathbb{P}(\text{a tree of size } k \text{ is formed after time } t_{p,n}^{(k)} + c). \end{aligned} $$

(When $k = 1$, $\mathbb{P}(\mathcal{A}_{p,n}^{(1)} > t_{p,n}^{(1)} + c) = \mathbb{P}(\mathcal{N}_{p,n}^{(1)}(t_{p,n}^{(1)} + c) \ge 1)$.) According to Lemma 6.13, when $k \ge 2$, the last probability converges to 0 as $n \to \infty$. Consequently, by Proposition 6.4

$$ \begin{aligned} \mathbb{P}(\mathcal{A}_{p,n}^{(k)} > t_{p,n}^{(k)} + c) &\underset{n \to \infty}{\sim} \mathbb{P}(\mathcal{N}_{p,n}^{(k)}(t_{p,n}^{(k)} + c) \ge 1) \\ &\underset{n \to \infty}{\to} 1 - e^{-\frac{k^{k-2}e-kpc_e-k(\psi(1/p)+\gamma_E)}{k!}} \end{aligned} $$

$$ \text{and therefore } \mathbb{P}(kp(\mathcal{A}_{p,n}^{(k)} - t_{p,n}^{(k)}) + k(\psi(1/p) + \gamma_E) - \ln(k^{k-2}/k!) > x) \underset{n \to \infty}{\to} 1 - e^{-e^{-x}}, \text{ for all } x \in \mathbb{R}. $$

### 6.2.3 Proof of Theorem 6.10

Since $\mathcal{A}_{p,n}^{(k+)} \ge \mathcal{A}_{p,n}^{(k)}$, we just need to show that $\mathbb{P}(\mathcal{A}_{p,n}^{(k+)} > \mathcal{A}_{p,n}^{(k)}) \to 0$ as $n \to \infty$. Fix $\varepsilon > 0$ and let $c_\varepsilon \in \mathbb{R}$ be sufficiently small so that $\mathbb{P}(\mathcal{A}_{p,n}^{(k)} < t_{p,n}^{(k)} + c_\varepsilon) \le \varepsilon$ for all $n$ large enough (such a $c_\varepsilon$ exists by Theorem 6.9). Splitting the probability $\mathbb{P}(\mathcal{A}_{p,n}^{(k+)} > \mathcal{A}_{p,n}^{(k)})$ according to whether $\mathcal{A}_{p,n}^{(k)} < t_{p,n}^{(k)} + c_\varepsilon$ or not, we get the upper bound

$$ \begin{aligned} \mathbb{P}(\mathcal{A}_{p,n}^{(k+)} > \mathcal{A}_{p,n}^{(k)}) &\le \varepsilon + \mathbb{P}(\mathcal{A}_{p,n}^{(k+)} > \mathcal{A}_{p,n}^{(k)} \ge t_{p,n}^{(k)} + c_\varepsilon) \\ &\le \varepsilon + \mathbb{P}(\text{there exists a tree of size } \ge k+1 \text{ at time } t_{p,n}^{(k)} + c_\varepsilon) \\ &\quad + \mathbb{P}(\text{a tree of size } \ge k+1 \text{ is formed after time } t_{p,n}^{(k)} + c_\varepsilon). \end{aligned} $$

By Corollary 6.8 and Lemma 6.13, the two latest probabilities converge to 0 as $n \to \infty$. Since this holds for every $\varepsilon > 0$, we are done.
## 6.3 De-Poissonization

Starting from the discrete model $F_{p,n}$ and a standard, independent, Poisson process $N$, we work here with the version $F_{p,n}(N((n-1)/2))$ of the continuous model. All straight notations will refer to the discrete model, while curved notations will refer to the continuous model.

To show that Theorem 6.10 induces Theorem 1.9 and that Proposition 6.4 induces Proposition 1.10, we use the bound

$$ \mathbb{P}(|Y_{\mathcal{P}(\lambda)} - \lambda| \ge a) \le \frac{\mathbb{E}[|Y_{\mathcal{P}(\lambda)} - \lambda|^3]}{a^3} = \frac{\lambda}{a^3} \quad (6.6) $$

for $a > 0$, where $Y_{\mathcal{P}(\lambda)}$ denotes a Poisson random variable with mean $\lambda > 0$.

**Proof of Theorem 1.9.** Noticing that

$$ \mathcal{A}_{p,n}^{(k+)} = \inf \left\{ t \ge 0 : \mathcal{N} \left( \left( \frac{n-1}{2} \right) t \right) \ge \mathcal{A}_{p,n}^{(k+)} + 1 \right\}, $$

we have for all fixed $x \in \mathbb{R}$ and $\varepsilon > 0$,

$$ \begin{aligned} & \mathbb{P} \left( \mathcal{A}_{p,n}^{(k+)} - \mathbf{t}_{p,n}^{(k)} \le 2x - \varepsilon \right) - \mathbb{P} \left( \mathcal{N} \left( \left( \frac{n-1}{2} \right) \left( \mathbf{t}_{p,n}^{(k)} + 2x - \varepsilon \right) \right) > n \left( \frac{\mathbf{t}_{p,n}^{(k)}}{2} + x \right) + 1 \right) \\ & \le \mathbb{P} \left( \frac{\mathcal{A}_{p,n}^{(k+)} - \mathbf{t}_{p,n}^{(k)}}{n} \le x \right) \\ & \le \mathbb{P} \left( \mathcal{A}_{p,n}^{(k+)} - \mathbf{t}_{p,n}^{(k)} \le 2x + \varepsilon \right) + \mathbb{P} \left( \mathcal{N} \left( \left( \frac{n-1}{2} \right) \left( \mathbf{t}_{p,n}^{(k)} + 2x + \varepsilon \right) \right) < n \left( \frac{\mathbf{t}_{p,n}^{(k)}}{2} + x \right) + 1 \right). \end{aligned} $$

Together with (6.6) and the limit in distribution of $\mathcal{A}_{p,n}^{(k+)} - \mathbf{t}_{p,n}^{(k)}$ from Theorem 6.10 towards an absolutely continuous law, this yields the expected limit in distribution of $A_{p,n}^{(k+)} / n - \mathbf{t}_{p,n}^{(k)} / 2$.

Regarding the relation between $A_{p,n}^{(k+)}$ and $A_{p,n}^{(k)}$, we use that $\{A_{p,n}^{(k+)} = A_{p,n}^{(k)}\} = \{A_{p,n}^{(k+)} = A_{p,n}^{(k)}\}$ to get, again with the help of Theorem 6.10, the full statement of Theorem 1.9. $\square$

**Proof of Proposition 1.10.** Fix $k \in \mathbb{N}$, $c \in \mathbb{R}$ and $\varepsilon > 0$. Let $E_n^{(1)}$ be the event "no tree of size $k$ if formed after time $\mathbf{t}_{p,n}^{(k)} + c - \varepsilon$" in the continuous model $\mathcal{F}_{p,n}$ and

$$ E_n^{(2)} := \left\{ \frac{n}{2}(\mathbf{t}_{p,n}^{(k)} + c) \in \left[ \mathcal{N} \left( \left( \frac{n-1}{2} \right) \cdot (\mathbf{t}_{p,n}^{(k)} + c - \varepsilon) \right), \mathcal{N} \left( \left( \frac{n-1}{2} \right) \cdot (\mathbf{t}_{p,n}^{(k)} + c + \varepsilon) \right) \right] \right\}. $$

By Lemma 6.13 and the bound (6.6), $\mathbb{P}(E_n^{(1)} \cap E_n^{(2)}) \to 1$ as $n \to \infty$. Then we use that

$$ \mathcal{N}_{p,n}^{(k)}(t) = N_{p,n}^{(k)} \left( \mathcal{N} \left( \frac{n-1}{2} \cdot t \right) \right), \quad \forall t \ge 0, $$

to get for $i \in \mathbb{Z}_+$,

$$ \begin{aligned} \mathbb{P} \left( N_{p,n}^{(k)} \left( \left\lfloor \frac{n}{2} \cdot (\mathbf{t}_{p,n}^{(k)} + c) \right\rfloor \right) \le i \right) &= \mathbb{P} \left( N_{p,n}^{(k)} \left( \left\lfloor \frac{n}{2} \cdot (\mathbf{t}_{p,n}^{(k)} + c) \right\rfloor \right) \le i, E_n^{(1)} \cap E_n^{(2)} \right) + o(1) \\ &\le \mathbb{P} \left( \mathcal{N}_{p,n}^{(k)} (\mathbf{t}_{p,n}^{(k)} + c + \varepsilon) \le i \right) + o(1). \end{aligned} $$
This leads, with Proposition 6.4, to

$$ \limsup_{n \to \infty} \mathbb{P} \left( N_{p,n}^{(k)} \left( \left\lfloor \frac{n}{2} \cdot (\mathbf{t}_{p,n}^{(k)} + c) \right\rfloor \right) \le i \right) \le \mathbb{P} \left( Y_{\mathcal{P}(k^{k-2}e^{-kp(c+\varepsilon})e^{-k(\psi(1/p)+\gamma_E)/k!})} \le i \right) $$

where we still use the notation $Y_{\mathcal{P}(\lambda)}$ for a Poisson random variable with mean $\lambda$. Similarly,

$$ \liminf_{n \to \infty} \mathbb{P} \left( N_{p,n}^{(k)} \left( \left\lfloor \frac{n}{2} \cdot (\mathbf{t}_{p,n}^{(k)} + c) \right\rfloor \right) \le i \right) \ge \mathbb{P} \left( Y_{\mathcal{P}(k^{k-2}e^{-kp(c-\varepsilon})e^{-k(\psi(1/p)+\gamma_E)/k!})} \le i \right). $$

We get the expected result by letting $\varepsilon \to 0$. □

# 7 Concluding remarks and open questions

We end this paper with a few remarks and related questions on the p-frozen model.

• The case $p = 0$, where the evolution of unicycle components is stopped as soon as they are created, is different in nature from the cases $p \in (0, 1]$. While Theorem 1.2 should also hold when $p = 0$ with a function $g_0$ defined as in Definition 1.1 and the related function $d_0$ (1.3), that is for $t \ge 1/2$

$$ g_0(t) = 1 - \frac{1}{2t} \quad \text{and} \quad d_0(t) = t - 1 + \frac{1}{4t}, $$

its proof requires a partly different approach. Mainly because the forest part of the graph $F_{0,n}(m)$ when $m \gg n/2$ is no more subcritical (as it is when $p \in (0, 1]$) but critical. The approach of Section 4 needs therefore to be adapted, but we note that the results of Section 2 are still valid. Regarding the total gelation time and the last times at which there are trees of size $k$, $k \ge 1$, one expect an asymptotic behavior in $n^2$ – instead of $n \ln(n)$ when $p \in (0, 1]$. Although several intermediate results such as Lemma 6.1 and Lemma 6.2 remain valid when $p = 0$ and points to this $n^2$ order, the difficulty to implement precisely the behavior of the total gelation time when $p = 0$ lies in the presence of trees of all sizes in its vicinity (unlike the case $p \in (0, 1]$ where there are only isolated vertices). These questions will be considered in a future work.

• **Fluid limit of unicycle components.** When $p \in (0, 1]$ the unicycle components continue to grow after their formation, according to a dynamic which is asymptotically similar to the evolution of the gel: they attract new trees with a weight proportional to their size. This is a reinforcement process, see e.g. Pemantle's survey [23] on that topic. One could then expect that the fluid limit of a unicycle component after its formation is the same as that of the gel shifted in time, up to a multiplicative random constant to determine.

• **Asymptotic distribution of unicycle components at the gelation time.** To complete the result on the asymptotic behavior of the total gelation time $A_{p,n}$ obtained in Theorem 1.9, it would be very interesting to determine the asymptotic behavior of the number of unicycle components present at that time $A_{p,n}$, as well as of the vector of their relative sizes. In this direction, Krapivsky [19]
conjectured that the number $U_{p,n}$ of unicycle components at time $A_{p,n}$ verifies

$$ \frac{\mathbb{E}[U_{p,n}]}{\ln(n)} \xrightarrow{n \to \infty} \frac{1}{6} \left(1 + \frac{1}{p}\right). $$

And when $p = 1/2$, the question is solved thanks to Proposition 4 of [12], which implies that the distribution of the final partition of unicycle components at the gelation time is the same as that of a random mapping. This, in the limit, gives a Poisson-Dirichlet distribution with parameter 1/2 for the relative sizes of unicycle components ranked in decreasing order, see e.g. [1].

## Acknowledgements

We thank Nicolas Curien for helpful discussions on the fluid limit part of this work and for pointing out the connection between the final partition of unicycle components when $p = 1/2$ and random mappings. We also thank Pavel Krapivsky for presenting his work [19] to us during a visit to Paris.

# A Appendix

## A.1 The Borel-Tanner distribution

The Borel distribution and its generalization the Borel-Tanner distribution [10],[31] were initially introduced for models in queueing theory and relatively branching processes, and are also used since then for applications in real-word phenomena. We gather here some of their basic properties and highlight some consequences we shall need throughout the paper.

**Definition A.1.** A random variable $B$ follows a Borel distribution with parameter $\theta \in (0, 1]$ if it is $\mathbb{N}$-valued and

$$ \mathbb{P}(B = k) = \frac{k^{k-2}}{(k-1)!} \cdot \theta^{k-1} e^{-\theta k}, \quad \forall k \in \mathbb{N}. $$

For $r \in \mathbb{N}$, a random variable $T_r$ follows a Borel-Tanner distribution with parameter $\theta \in (0, 1]$ if it takes its values in $\{r, r+1, r+2, \dots\}$ and

$$ \mathbb{P}(T_r = k) = \frac{r}{(k-r)!} \cdot k^{k-r-1} \theta^{k-r} e^{-\theta k}, \quad \forall k \ge r. $$

From our random trees perspective, the Borel distribution with parameter $\theta$ is the distribution of the total progeny of a Galton-Watson tree with Poisson offspring distribution with mean $\theta$, and the Borel-Tanner distribution with parameters $(r, \theta)$ is the distribution of the total progeny of a forest composed by $r$ independent Galton-Watson trees with Poisson offspring distribution with mean $\theta$. In particular, note that if $B, B'$ are independent random variables, both following a Borel distribution
with parameter $\theta$, the identity $\mathbb{P}(B + B' = k) = \mathbb{P}(T_2 = k) = \sum_{i=1}^{k-1} \mathbb{P}(B = i)\mathbb{P}(B' = k - i)$ leads for all $k \ge 2$ to:

$$ \frac{2k^{k-3}}{(k-2)!} = \sum_{i=1}^{k-1} \frac{i^{k-2}}{(i-1)!} \cdot \frac{(k-i)^{k-i-2}}{(k-i-1)!} \qquad (A.1) $$

**Mean and approximation.** When $\theta \in (0, 1)$, the expectation of $B$ is finite:

$$ \mathbb{E}[B] = \sum_{k=1}^{\infty} \frac{k^k}{k!} \cdot \theta^{k-1}e^{-\theta k} = \frac{1}{1-\theta}. \qquad (A.2) $$

We will need in Section 4 some estimates on this sum. For $\theta \in [0, 1/2)$ let $S(\theta) = 1/(1-\theta)$, and for $\theta \in [0, 1/2]$ and $N \in \mathbb{N}$,

$$ S_N(\theta) = \sum_{k=1}^{N} \frac{k^k}{k!} \cdot \theta^{k-1}e^{-\theta k}. \qquad (A.3) $$

**Lemma A.2.** 1) The sum $S_N$ converges to $S$ uniformly on all compact subsets of $[0, 1/2)$, and $S_N(1) \to \infty$ as $N \to \infty$.

2) For any $A > 0$, there exists $N_0 \ge 1$ and $\delta > 0$ such that for every $N \ge N_0$ and $\theta \in [1 - \delta, 1]$, $S_N(\theta) \ge A$.

**Proof.** Point 1) is obvious. For 2), note that there exists $N_0 \ge 1$ such that $S_{N_0}(1) \ge A$. Then use that $S_N$ is non-increasing on $[1 - 1/N, 1]$. $\square$

**Connexion with the measures $\mu_x$.** Recall from Section 2.1 the definition of $\mu_x$, for $x \in (0, e^{-1}]$, by

$$ \mu_x(k) = \frac{k^{k-2}}{k!} \cdot \frac{x^k}{T(x)}, \quad \forall k \ge 1, \quad \text{with} \quad T(x) = \sum_{k \ge 1} \frac{k^{k-2}}{k!} x^k, $$

and note that the Borel distribution with parameter $\theta \in (0, 1]$ is the size-biasing of $\mu_{\theta e^{-\theta}}$. This remark leads to the following (well-known in the theory of uniform random forests) points.

**Lemma A.3.** If $x = \theta e^{-\theta}$ with $\theta \in (0, 1]$ then

$$ T(x) = \theta(1 - \theta/2), \quad \sum_{k=1}^{\infty} k \mu_x(k) = \frac{2}{2 - \theta}, \quad \text{and} \quad \mathrm{Var}_{\mu_x} = \frac{2\theta}{(1 - \theta)(2 - \theta)^2} $$

(the variance is infinite when $\theta = 1$).

**Proof.** By definition of the Borel distribution and its expectation,

$$ \sum_{k \ge 1} \frac{k^{k-1}}{k!} \cdot \theta^k e^{-k\theta} = \theta, \quad \sum_{k \ge 1} \frac{k^k}{k!} \cdot \theta^k e^{-k\theta} = \frac{\theta}{1-\theta}, \quad \forall \theta \in [0, 1]. $$
Setting $x(\theta) = \theta e^{-\theta}$, $T(0) = 0$ and differentiating the function $\theta \in [0, 1] \mapsto T(x(\theta))$, we see that

$$ \partial_{\theta} T(x(\theta)) = \sum_{k \ge 1} \frac{k^{k-1}}{k!} \theta^{k-1} e^{-k\theta} - \sum_{k \ge 1} \frac{k^{k-1}}{k!} \theta^k e^{-k\theta} = 1 - \theta. $$

Since $T(x(0)) = 0$, this indeed gives $T(x(\theta)) = \theta - \theta^2/2$ for all $\theta \in (0, 1]$ and then

$$ \sum_{k=1}^{\infty} k \mu_{x(\theta)}(k) = \frac{1}{T(x(\theta))} \cdot \sum_{k \ge 1} \frac{k^{k-1}}{k!} \theta^k e^{-k\theta} = \frac{2}{2-\theta} $$

$$ \sum_{k=1}^{\infty} k^2 \mu_{x(\theta)}(k) = \frac{1}{T(x(\theta))} \cdot \sum_{k \ge 1} \frac{k^k}{k!} \theta^k e^{-k\theta} = \frac{2}{(1-\theta)(2-\theta)}, $$

leading to the result.

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

## A.2 Wormald's differential equation method

We give here a version of Wormald's theorem, initially proved in [36] and then deepened in [37, 35]. Fix $k \in \mathbb{N}$. For $n \in \mathbb{N}$, let $(F_n(m), m \in \mathbb{Z}_+)$ be a filtration and let $Y_n^{(1)}, \dots, Y_n^{(k)}$ be $F_n$-adapted discrete-time stochastic processes. Assume that there exists some constant $C_0$ such that $|Y_n^{(l)}(m)| < C_0 n$ almost surely for all $m \in \mathbb{Z}_+, 1 \le l \le k, n \in \mathbb{N}$. Let then $D$ be a bounded open subset of $\mathbb{R}^{k+1}$ and for $1 \le l \le k$,

$F_l : D \to \mathbb{R}$ be a Lipschitz function.

Finally let $H_D(Y_n^{(1)}, \dots, Y_n^{(k)})$ be the first time $m \in \mathbb{Z}_+$ at which

$$ \left( \frac{m}{n}, \frac{Y_n^{(1)}(m)}{n}, \dots, \frac{Y_n^{(k)}(m)}{n} \right) \notin D $$

with the usual convention $\inf \{\emptyset\} = \infty$. This is a stopping time with respect to the filtration $F_n$.

**Theorem A.4 (Theorem 5.1 in [37], Theorem 2 in [35]).** Assume that $D$ contains the closure of

$$ \{(0, z_1, \dots, z_k) \in \mathbb{R}^{k+1} : \mathbb{P}(Y_n^{(l)}(0) = z_l n, 1 \le l \le k) \neq 0 \text{ for some } n\} $$

and that the two following hypotheses hold for all $n \in \mathbb{N}$:

* Boundedness hypothesis. For some functions $\beta : \mathbb{N} \to [1, \infty)$ and $\gamma : \mathbb{N} \to [0, 1]$ the probability that

$$ \max_{1 \le l \le k} |\Delta Y_n^{(l)}(m+1)| \le \beta(n), $$

conditional on $F_n(m)$, is at least $1 - \gamma(n)$ when $m < H_D(Y_n^{(1)}, \dots, Y_n^{(k)})$.
• Trend hypothesis. For some function $\lambda : \mathbb{N} \to \mathbb{R}_+$ such that $\lambda = o(1)$ as $n \to \infty$, for all $1 \le l \le k$,

$$ \left| \mathbb{E} \left[ \Delta Y_n^{(l)}(m) | \mathbf{F}_n(m) \right] - F_l \left( \frac{m}{n}, \frac{Y_n^{(1)}(m)}{n}, \dots, \frac{Y_n^{(k)}(m)}{n} \right) \right| \le \lambda(n) $$

when $m < H_D(Y_n^{(1)}, \dots, Y_n^{(k)})$.

Then:

(a) For $(0, z_1, \dots, z_a) \in D$, the system of differential equations

$$ y_l(t) = F_l(t, y_1, \dots, y_k), \quad y_l(0) = \hat{z}_l, \quad l = 1, \dots, k $$

has a unique maximal solution.

(b) Let $\eta(n) \ge \lambda(n) + C_0 n \gamma(n)$ with $\eta(n) = o(1)$. For a sufficiently large constant $C$, with probability $1 - O(n\gamma(n) + \frac{\beta(n)}{\eta(n)}\exp(-\frac{n\eta^3(n)}{\beta^3(n)})$,

$$ Y_n^{(l)}(m) = ny_l\left(\frac{m}{n}\right) + O(\eta(n)n) $$

uniformly in $0 \le m \le \sigma(n)n$ and $1 \le l \le k$, where $y_l$ is the solution in (a) with $z_l = Y_n^{(l)}(0)/n$, and $\sigma(n)$ is the supremum of the times $t$ to which the solution can be extended before reaching within $\ell^\infty$-distance $C\eta(n)$ of the boundary of $D$.

## References

[1] D. ALDOUS, Exchangeability and related topics, vol. 1117 of Lectures Notes in Mathematics, Springer, 1985.

[2] ——, Brownian excursions, critical random graphs and the multiplicative coalescent, Ann. Probab., 25 (1997), pp. 812–854.

[3] ——, The percolation process on a tree where infinite clusters are frozen, in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 128, Cambridge University Press, 2000, pp. 465–477.

[4] N. ALON AND J. H. SPENCER, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., John Wiley & Sons, 4th ed., 2016.

[5] D. BARRAEZ, S. BOUCHERON, AND W. FERNANDEZ DE LA VEGA, On the fluctuations of the giant component, Comb. Probab. Comput., 9 (2000), pp. 287–304.

[6] E. BELLIN, A. BLANC-RENAUDIE, E. KAMMERER, AND I. KORTCHEMSKI, Uniform attachment with freezing. Preprint, arXiv:2308.00493 (2023).
[7] E. S. BERNIKOVICH AND Y. L. PAVLOV, *On the maximum size of a tree in a random unlabelled unrooted forest*, Discrete Math. Appl., 21 (2011), pp. 1–21.

[8] B. BOLLOBÁS, *Random graphs*, vol. 73 of Camb. Stud. Adv. Math., Cambridge University Press, 2nd ed., 2001.

[9] B. BOLLOBÁS AND O. RIORDAN, *Constrained graph processes*, Electronic J. Comb., 7 (R18) (2000).

[10] E. BOREL, *Sur l'emploi du Théorème de Bernoulli pour faciliter le calcul d'une infinité de coefficients. Application au problème de l'attente à un guichet*, CR Acad. Sci. Paris, 214 (1942), pp. 452-456.

[11] V. E. BRITIKOV, *Asymptotic number of forests from unrooted trees*, Mathematical Notes, 43 (1988), pp. 387-394.

[12] A. CONTAT AND N. CURIEN, *Parking on Cayley trees and frozen Erdős-Rényi*, Ann. Probab., 51 (2023), pp. 1993-2055.

[13] R. W. DARLING AND J. R. NORRIS, *Differential equation approximations for Markov chains*, Probab. Surveys, 5 (2008), pp. 37-79.

[14] P. ERDŐS AND A. RÉNYI, *On random graphs*, I, Publ. Math. Debr., 6 (1959), pp. 290-297.

[15] ——, *On the evolution of random graphs*, Publ. Math. Inst. Hung. Acad. Sci., Ser. A, 5 (1960), pp. 17-61.

[16] B. V. GNEDENKO AND A. N. KOLMOGOROV, *Limit distributions for sums of independent variables*. Addison-Wesley Publishing Company, 1954.

[17] S. JANSON, D. E. KNUTH, T. ŁUCZAK, AND B. PITTEL, *The birth of the giant component*, Random Struct. Algorithms, 4 (1993), pp. 233-358.

[18] V. F. KOLCHIN, *Random mappings. Transl. from the Russian*. Translation Series in Mathematics and Engineering. Springer-Verlag, 1986.

[19] P. L. KRAPIVSKY, *Simple evolving random graphs*, Phys. Rev. E, 109 (2024), p. 064304.

[20] A. LOGAN, M. MOLLOY, AND P. PRAŁAT, *A variant of the Erdős-Rényi random graph process*, Journal of Graph Theory, 102 (2023), pp. 322-345.

[21] T. ŁUCZAK, *Component behavior near the critical point of the random graph process*, Random Struct. Algorithms, 1 (1990), pp. 287-310.

[22] T. ŁUCZAK AND B. PITTEL, *Components of random forests*, Comb. Probab. Comput., 1 (1992), pp. 35-52.