# METASTABILITY OF THE CONTACT PROCESS ON SLOWLY EVOLVING SCALE-FREE NETWORKS

Emmanuel Jacob, Amitai Linker, Peter Mörters

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

## To cite this version:

Emmanuel Jacob, Amitai Linker, Peter Mörters. METASTABILITY OF THE CONTACT PROCESS ON SLOWLY EVOLVING SCALE-FREE NETWORKS. 2024. hal-04846794

HAL Id: hal-04846794

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

Preprint submitted on 18 Dec 2024

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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# METASTABILITY OF THE CONTACT PROCESS ON SLOWLY EVOLVING SCALE-FREE NETWORKS

EMMANUEL JACOB, AMITAI LINKER AND PETER MÖRTERS

**Abstract:** We investigate the contact process on scale-free networks evolving by a stationary dynamics whereby each vertex independently updates its connections with a rate depending on its power. This rate can be slowed down or speeded up by virtue of decreasing or increasing a parameter $\eta$, with $\eta \downarrow -\infty$ approaching the static and $\eta \uparrow \infty$ the mean-field case. We identify the regimes of slow, fast and ultra-fast extinction of the contact process. Slow extinction occurs in the form of metastability, when the contact process maintains a certain density of infected states for a time exponential in the network size. In our main result we identify the metastability exponents, which describe the decay of these densities as the infection rate goes to zero, in dependence on $\eta$ and the power-law exponent $\tau$. While the fast evolution cases have been treated in a companion paper, Jacob, Linker, Mörters (2019), the present paper looks at the significantly more difficult cases of slow network evolution. We describe various effects, like degradation, regeneration and depletion, which lead to a rich picture featuring numerous first-order phase transitions for the metastable exponents. To capture these effects in our upper bounds we develop a new martingale based proof technique combining a local and global analysis of the process.

**MSc Classification:** Primary 05C82; Secondary 82C22.

**Keywords:** Phase transition, metastable density, metastability, evolving network, temporal network, stationary dynamics, vertex updating, inhomogeneous random graph, scale-free network, preferential attachment network, network dynamics, SIS infection.

## 1. INTRODUCTION

The aim of the present paper and its companion [12] is to provide a paradigmatic study of the combined effects of temporal and spatial variability of a graph on the spread of diffusions on this graph, and to provide the mathematical techniques for such a study if the graph process is stationary and autonomous. There has been considerable interest in the probability literature on the behaviour of diffusions on a variety of evolving graph models, some recent examples are [13, 19, 20, 8, 4]. Our particular interest in this work is in the phase transitions that occur when we tune parameters controlling the speed and inhomogeneity of the graph evolution. For this study our choice is to look at
* finite graphs, which as their size $N$ goes to infinity have a heavy tailed asymptotic degree distribution. These are often called *scale-free networks* in the literature [2, 10, 11]. The tail exponent $\tau$ is the parameter controlling the spatial inhomogeneity of the graph.

* a stationary dynamics based on *updating vertices* at a rate possibly depending on the power of the vertex, see e.g. [14, 21]. Upon updating a vertex resamples all its connections independently with a probability that depends on its power and the power of the potential connecting vertex. This updating mechanism loosely speaking mimics movement of the individuals represented by the vertices. The rate at which a vertex of expected degree $k$ is updated is set to be proportional to $k^{\eta}$, where $\eta \in \mathbb{R}$ is the parameter controlling the speed of the graph process.

* a diffusion modelled by the *contact process*, see e.g. [6, 7, 15, 17]. In this epidemic process healthy vertices recover at rate one, and infected vertices infect their neighbours at rate $\lambda$. Recovered vertices can be reinfected, so that the infection can use edges that remain in the graph long enough several times for an infection. This creates interactions between the contact process and the autonomous graph evolution, which are at the heart of this paper.

We now heuristically describe the main effects behind the results of this paper.

In the case of a static scale-free network if an infected vertex of degree $k \gg \lambda^{-2}$ recovers, it typically has of order $\lambda k$ infected neighbours. The probability that none of these neighbours reinfects the vertex before it recovers is roughly $(1 - \frac{\lambda}{\lambda+1})^{\lambda k} \sim e^{-k\lambda^2}$. Hence the vertex can hold the infection for a time which is exponential in the vertex degree before a sustained recovery. In a static scale-free network there are sufficiently many well-connected vertices of high degree for this local survival mechanism to keep an established infection alive for a time exponential in the graph size, see [1, 5, 9].

If the graph is evolving in time, even when the degree of the powerful vertex remains high throughout, its capacity to use the neighbourhood for local survival is significantly reduced compared to the static case and we observe a substantial *degradation* in the ability of the vertex to sustain an infection locally. Already for slow evolutions, if $\eta < 0$, the degradation effect is significant. On recovery of a vertex of degree $k$ the number of infected neighbours is still of order $\lambda k$ but the probability that none of them reinfects the vertex before it updates is now roughly

$$ \frac{k^{\eta}}{\lambda^2 k + k^{\eta}} \sim \lambda^{-2} k^{\eta-1} \quad \text{if } k \gg \lambda^{-\frac{2}{1-\eta}}. $$

Hence the time that a vertex can survive locally is of order $\lambda^2 k^{1-\eta}$. Although this is just polynomial in the vertex degree and hence much smaller than in the static case, this local survival mechanism together with a spreading strategy can keep an established infection alive for a time exponential in the graph size, we then speak of *slow extinction*.

Updating of vertices has a second effect, which is beneficial to the survival of the infection, namely that in the time up to a sustained recovery updates of a powerful vertex will regenerate its neighbourhood and the overall connectivity of the graph is improved allowing
it to spread the infection more efficiently. When a vertex consistently has degree $k$ over an infection period of length $\lambda^2 k^{1-\eta}$ we see updates at a rate $k^\eta$ and hence if $\lambda^2 k \gg 1$ we have of order $\lambda^2 k$ updates before a sustained recovery. This effect of regeneration gives the vertex an increased effective degree. More precisely, in a period of length $k^{-\eta}$ between two updates the probability that one of the $\lambda k$ neighbours of this vertex passes the infection to a second vertex of degree $k$ is of order $\lambda^2 k^{1-\eta} \frac{k}{N}$ where $\frac{k}{N}$ is the order of the probability that there is an edge between a given neighbour of the first and the second vertex. As there are $\lambda^2 k$ updates before a sustained recovery the overall probability that an infected vertex with degree $k \gg \lambda^{-2}$ passes the infection to a vertex of the same degree via an intermediary vertex is $\lambda^4 k^{3-\eta} \frac{1}{N}$ and if the proportion $a(k)$ of vertices with degree at least $k$ satisfies $a(k) \gg \lambda^{-4} k^{\eta-3}$ the strategy of delayed indirect spreading, where the infection is passed from one powerful vertex to another via an intermediary vertex, yields slow extinction.

A similar argument suggests that, as an infected vertex of degree $k$ has of order $\lambda^2 k$ updates before a sustained recovery, if $\frac{p(k)}{N}$ denotes the probability that two vertices of degree $k$ are connected by an edge, then the probability that by the time of its sustained recovery an infected vertex of degree $k$ directly infects another vertex of degree $k$ is $\lambda^3 k^{1-\eta} \frac{p(k)}{N}$. Hence if the proportion $a(k)$ of vertices with degree at least $k$ satisfies

$$a(k) \gg \lambda^{-3} k^{\eta-1} p(k)^{-1}$$

the strategy of delayed direct spreading, where the infection is passed from one powerful vertex to another directly, should yield slow extinction of the infection. However, this is only correct if the update rate $k^\eta$ of a vertex of degree $k$ is at least of the order of the infection rate $\lambda$. If $k^\eta \ll \lambda$, then the dynamics of the subnetwork of powerful vertices is much slower than the spread of the infection. The infections passed from a powerful vertex will then typically reach vertices that are already infected, an effect we call depletion. In those cases the infection will spread at rate $k^\eta$ instead of $\lambda$, so that overall delayed direct spreading can only give slow extinction if $a(k) \gg k^{-\eta} \lambda^{-2} k^{\eta-1} p(k)^{-1}$. Note that whether the delayed direct spreading mechanism is possible depends not only on the tail exponent $\tau$ of the degree distribution but also on the finer network geometry through the quantity $p(k)$.

When the graph is very densely connected both spreading mechanisms are equally effective and we speak of delayed concurrent spreading. In this case the infection retains a density of infected vertices of the same order if either all edges between high degree vertices were removed or all low degree neighbouring vertices of high degree vertices were leaves.

The degradation and regeneration effects are even stronger for fast evolutions, i.e. when $\eta \ge 0$. On recovery of a vertex of degree $k$ the number of infected neighbours is now of order $k \frac{\lambda}{\lambda+1+k^\eta} \sim \lambda k^{1-\eta}$ and hence the probability that none of them reinfects the vertex before it updates is roughly

$$\frac{k^\eta}{\lambda^2 k^{1-\eta} + k^\eta} \sim \lambda^{-2} k^{2\eta-1} \quad \text{if } \lambda^2 k^{1-\eta} \gg k^\eta.$$

Now only if $\eta \le \frac{1}{2}$ the local survival mechanism persists and vertices with degree $k$ satisfying $k^{1-2\eta} \gg \lambda^{-2}$ can hold the infection for a time of order $\lambda^2 k^{1-2\eta}$. In this case we
can also benefit from the effect of regeneration without depletion. As a result delayed indirect spreading is possible on the set of vertices with expected degree at least $k$ if $a(k) \gg \lambda^{-4}k^{2\eta-3}$ and delayed indirect spreading is possible if $a(k) \gg k^{2\eta-1}\lambda^{-3}p(k)^{-1}$.

Heuristically speaking, the four strategies above, delayed indirect and delayed direct spreading, together with the strategies of quick indirect and direct spreading, which spread the infection without using a local survival mechanism, compete for domination. Each strategy sustains the infection on a set of powerful vertices called the *stars* and the strategy that operates with the smallest threshold degree $k$, or equivalently the largest proportion $a(k)$ of stars among the vertices, dominates. The infected neighbours of the stars form a set comprising an approximate proportion $\lambda ka(k)$ of vertices which remain infected for a time exponential in the graph size. During that time the proportion of infected vertices remains essentially constant, this effect is called *metastability*. The constant proportion of infected vertices is called the *metastable density*.

In this project we establish *metastable exponents* describing the decay of the metastable densities as $\lambda \downarrow 0$ for various network models. The exponents are a function of the power-law exponent $\tau$ and the updating exponent $\eta$. They characterise the underlying survival strategies of the infection and thereby rigorously underpin the heuristics. Proofs of the upper and lower bounds require novel techniques, which are developed in this project:

* *Lower bounds* for metastable densities are based on the identification of the optimal survival strategies for the infection. To show that these strategies are successful a technically demanding coarse graining technique has to be used. This is done in [12] for fast network evolutions, but is getting much harder for slow evolutions as there is much less independence in the system and additional effects like depletion have to be handled. We develop the necessary novel techniques for slow evolutions in Section 3 of this paper.

* *Upper bounds* for metastable densities

- in the fast evolution case are based on model simplification in conjunction with supermartingale arguments, a basic version of this argument is developed in [12]. The argument can be substantially refined using a further distinction of vertices and leads to Theorem 3, which is proved in Section 5.

- upper bounds for very slow evolutions are based on local approximation and results for the contact process on trees. This is done in [13] for the same stationary graph model but running with a different stationary dynamics. Arguments from [13] can be adapted to our case, see Section 4.

- As becomes apparent in Section 4 the techniques above do not suffice to give matching upper bounds for the entire slow evolution domain. In order to close this gap a completely new tool has to be developed combining global and local analysis into a single argument. This is the main technical innovation of this paper. It will be presented as Theorem 4, which is proved in Section 5.

In the next section we give full details of the network models we consider and state our main result for the networks of primary interest based on the factor and preferential attachment kernel. Further results for more general networks are deferred to Sections 3 to 5.
## 2. MAIN RESULT

We now define a stationary evolving graph or network ($\mathcal{G}_t^{(N)}: t \ge 0)_{N \in \mathbb{N}}$. Take a function

$$ \kappa: (0, 1] \to (0, \infty), $$

and a kernel

$$ p: (0, 1] \times (0, 1] \to (0, \infty). $$

The vertex set of the graph $\mathcal{G}_t^{(N)}$ is $\{1, \dots, N\}$ for any $t \ge 0$. The graph is evolving by vertex updating: Each vertex $i$ has an independent Poisson clock with rate $\kappa_i := \kappa(i/N)$. When it strikes, the vertex updates, which means:

* All adjacent edges are removed, and

* new edges $i \leftrightarrow j$ are formed with probability

$$ p_{i,j} := \frac{1}{N} p\left(\frac{i}{N}, \frac{j}{N}\right) \wedge 1. $$

independently for every $j \in \{1, \dots, N\} \setminus \{i\}$.

We denote by ($\mathcal{G}_t^{(N)}: t \ge 0$) the stationary graph process under this dynamics.

For the kernel $p: (0, 1] \times (0, 1] \to (0, \infty)$ we make the following assumptions:

(1) $p$ is symmetric, continuous and decreasing in both parameters,

(2) there is some $\gamma \in (0, 1)$ and constants $0 < \mathbf{c}_1 < \mathbf{c}_2$ such that for all $a \in (0, 1)$,

$$ \mathbf{c}_1 a^{-\gamma} \le p(a, 1) \le \int_0^1 p(a, s) \, ds < \mathbf{c}_2 a^{-\gamma}. \qquad (1) $$

These properties are satisfied by the

* factor kernel, defined by $p(x, y) = \beta x^{-\gamma} y^{-\gamma}$, or the

* preferential attachment kernel, defined by $p(x, y) = \beta(x \wedge y)^{-\gamma}(x \vee y)^{\gamma-1}$,

for $\beta > 0$. These kernels correspond to the connection probabilities of the Chung-Lu or configuration models in the former, and preferential attachment models in the latter case, when the vertices are ranked by decreasing power. While we state the main results below for these principal kernels, our results are by no means limited to these examples.

For a sequence ($i_N$) of vertices $i_N \in \mathcal{G}_t^{(N)}$ such that $i_N \sim xN$ for some $x \in (0, 1]$ the degree distribution of the vertex $i_N$ converges to a Poisson distribution with parameter $\int_0^1 p(x, y)dy$, so its typical degree is of order $(i_N/N)^{-\gamma}$. Moreover, the empirical degree distribution of the network converges in probability to a limiting degree distribution $\mu$, which is a mixed Poisson distribution obtained by taking $x$ uniform in $(0, 1)$, then a Poisson distribution with parameter $\int_0^1 p(x, y)dy$, see [11, Theorem 3.4]. This distribution satisfies

$$ \mu(k) = k^{-\tau+o(1)} \quad \text{as } k \to \infty, \text{ with } \tau = 1 + \frac{1}{\gamma}, $$

i.e., at any time $t$ the network ($\mathcal{G}_t^{(N)})_{N \in \mathbb{N}}$ is scale-free with power-law exponent $\tau > 2$.
For fixed parameters $\eta \in \mathbb{R}$ and $\kappa_0 > 0$ we look at

$$ \kappa(x) = \kappa_0 x^{-\gamma\eta} \quad \text{for } x \in (0, 1]. $$

With this choice the update rate of a vertex is approximately proportional to its expected degree to the power $\eta$. The parameter $\eta$ determines the speed of the network evolution. When $\eta = 0$ network evolution and contact process operate on the same time-scale. If $\eta > 0$ the network evolution is faster, but note that now not all vertices update at the same rate. We let powerful vertices update faster in order to 'zoom into the window' where the qualitative behaviour of the contact process changes. If $\eta < 0$ the network evolution is slower and also here it is particularly slow for the more powerful vertices.

The infection is now described by a process $(X_t(i), i \in \{1, \dots, N\}: t \ge 0)$ with values in $\{0, 1\}^N$, such that $X_t(i) = 1$ if $i$ is infected at time $t$, and $X_t(i) = 0$ if $i$ is healthy at time $t$. The infection process associated to a starting set $A_0$ of infected vertices, is the càdlàg process with $X_0(i) = 1_{A_0}(i)$ evolving according to the following rules:

* to each vertex $i$ we associate an independent Poisson process $\mathcal{R}^i$ with intensity one, which represents recovery times, i.e. if $t \in \mathcal{R}^i$, then $X_t(i) = 0$ whatever $X_{t-}(i)$.

* to every unordered pair $\{i, j\}$ of distinct vertices we associate an independent Poisson process $\mathcal{I}_0^{ij}$ with intensity $\lambda$. If $t \in \mathcal{I}_0^{ij}$ and $\{i, j\}$ is an edge in $\mathcal{G}_t^{(N)}$, then

$$ (X_t(i), X_t(j)) = \begin{cases} (0, 0) & \text{if } (X_{t-}(i), X_{t-}(j)) = (0, 0). \\ (1, 1) & \text{otherwise.} \end{cases} $$

The process $(\mathcal{G}_t^{(N)}, X_t: t \ge 0)$ is a Markov process describing the simultaneous evolution of the network and of the infection. We denote by $(\mathfrak{F}_t: t \ge 0)$ its canonical filtration.

We start the process with the stationary distribution of the graph and all vertices infected. Just like in the static case there is a finite, random extinction time $T_{\text{ext}}$ and we say that there is

* ultra-fast extinction, if there exists $\lambda_c > 0$ such that for all infection rates $0 < \lambda < \lambda_c$ the expected extinction time is bounded by a subpolynomial function of $N$;

* fast extinction, if there exists $\lambda_c > 0$ such that for all infection rates $0 < \lambda < \lambda_c$ the expected extinction time is bounded by a polynomial function of $N$;

* slow extinction if, for all $\lambda > 0$, there exists some $\varepsilon > 0$ such that $T_{\text{ext}} \ge e^{\varepsilon N}$ with high probability.

Our first interest is in characterising phases of ultra-fast, fast or slow extinction. Slow extinction is indicative of metastable behaviour of the process, and in this case our interest focuses on the exponent of decay of the metastable density when $\lambda \downarrow 0$. More precisely, just like in [12], we let

$$ I_N(t) = \frac{1}{N} \mathbb{E} \left[ \sum_{i=1}^{N} X_t(i) \right] = \frac{1}{N} \sum_{i=1}^{N} \mathbb{P}_i (T_{\text{ext}} > t), $$

where $\mathbb{P}_i$ refers to the process started with only vertex $i$ infected and the last equality holds by the self-duality of the process. We say the contact process features
* *metastability* if there there exists $\varepsilon > 0$ such that

- whenever $t_N$ is going to infinity slower than $e^{\varepsilon N}$, we have $\liminf_{N \to \infty} I_N(t_N) > 0$.

- whenever $(s_N)$ and $(t_N)$ are two sequences going to infinity slower than $e^{\varepsilon N}$, we have $\lim_{N \to \infty} I_N(s_N) - I_N(t_N) = 0$.

In that case, we can unambiguously define the lower metastable density $\rho^-(\lambda) = \liminf_{N \to \infty} I_N(t_N) > 0$ and the upper metastable density $\rho^+(\lambda) = \limsup_{N \to \infty} I_N(t_N)$.

* a metastable exponent $\xi$ if, for sufficiently small $\lambda > 0$ there is metastability and

$$ \xi = \lim_{\lambda \downarrow 0} \frac{\log \rho^-(\lambda)}{\log \lambda} = \lim_{\lambda \downarrow 0} \frac{\log \rho^+(\lambda)}{\log \lambda}. $$

We are now ready to state our main result for the featured network kernels, the factor and preferential attachment kernels defined after (1).

**Theorem 1.** Consider the Markov process $(\mathcal{G}_t^{(N)}, X_t: t \ge 0)$ describing the simultaneous evolution of a network $(\mathcal{G}_t^{(N)}: t \ge 0)$ with power law exponent $\tau > 2$ and update speed $\eta \in \mathbb{R}$ and of the contact process $(X_t: t \ge 0)$ on it.

(a) Consider the **factor kernel**.

(i) If $\eta > \frac{1}{2}$ and $\tau > 3$, there is ultra-fast extinction.

(ii) If $\eta \le 0$ and $\tau > 4 - \eta$, or if $0 \le \eta \le \frac{1}{2}$ and $\tau > 4 - 2\eta$, there is fast extinction.

(iii) If $\eta \le 0$ and $\tau < 4 - \eta$, or if $0 \le \eta \le \frac{1}{2}$ and $\tau < 4 - 2\eta$, or if $\eta \ge \frac{1}{2}$ and $\tau < 3$, there is slow extinction and metastability. Moreover, the metastability exponent satisfies

$$ \xi = \begin{cases} \frac{1}{3-\tau} & \text{if } \begin{cases} \eta \le 0 \text{ and } \tau \le \frac{5}{2}, \\ \text{or } 0 \le \eta \le \frac{1}{2} \text{ and } \tau \le \frac{5}{2} + \eta, \\ \text{or } \eta \ge \frac{1}{2} \text{ and } \tau < 3, \end{cases} \\ \\ 2\tau - 3 & \text{if } \begin{cases} \eta \le \frac{5}{2} - \tau \text{ and } \frac{5}{2} \le \tau \le 3, \\ \text{or } \eta \le 2 - \tau \text{ and } \tau \ge 3, \end{cases} \\ \\ \frac{2\tau - 2 - \eta}{4 - \eta - \tau} & \text{if } \eta \le 0 \text{ and } \frac{5}{2} - \eta \le \tau < 4 + 2\eta, \\ \\ \frac{2\tau - 2 - 2\eta}{4 - 2\eta - \tau} & \text{if } 0 \le \eta \le \frac{1}{2} \text{ and } \frac{5}{2} + \eta \le \tau < 4 - 2\eta, \\ \\ \frac{\tau}{4 - \tau} & \text{if } 3 \lor (4 + 2\eta) \le \tau \le 4 + \eta, \\ \\ \frac{3\tau - 4 - \eta}{4 - \tau - \eta} & \text{if } (2 - \eta) \lor (4 + \eta) \le \tau < 4 - \eta. \end{cases} \quad (2) $$

(b) Consider the **preferential attachment kernel**.

(i) If $\eta \ge \frac{1}{2}$ and $\tau > 3$, there is ultra-fast extinction.

(ii) If $\eta < \frac{1}{2}$, or if $\eta \ge \frac{1}{2}$ and $\tau < 3$, there is slow extinction and metastability, and the metastability exponent satisfies
$$ \xi = \begin{cases} 2\tau - 3 & \text{if } \begin{cases} \eta \le -\frac{1}{2}, \\ \text{or } -\frac{1}{2} \le \eta \le 0 \text{ and } \tau \le 2 - \eta, \end{cases} \\ \frac{3\tau - 4 - \eta}{4 - \eta - \tau} & \text{if } -\frac{1}{2} < \eta \le 0 \text{ and } 2 - \eta \le \tau \le \frac{8}{3} + \frac{\eta}{3}, \\ \frac{3\tau - 5 - \eta}{1 - \eta} & \text{if } -\frac{1}{2} < \eta \le 0 \text{ and } \tau \ge \frac{8}{3} + \frac{\eta}{3}, \\ \frac{3\tau - 4 - 2\eta}{4 - 2\eta - \tau} & \text{if } 0 \le \eta \le \frac{1}{2} \text{ and } 2 + 2\eta \le \tau \le \frac{8}{3} + \frac{2\eta}{3}, \\ \frac{3\tau - 5 - 2\eta}{1 - 2\eta} & \text{if } 0 \le \eta \le \frac{1}{2} \text{ and } \tau \ge \frac{8}{3} + \frac{2\eta}{3}, \\ \frac{\tau - 1}{3 - \tau} & \text{if } \tau < 3 \text{ and } \eta > \frac{\tau}{2} - 1. \end{cases} \quad (3) $$

**Remark 1.** The restriction of this theorem to $\eta \ge 0$ is the content of Theorem 3 of [12], although the distinction of fast and ultra-fast extinction has not been made explicit there.

**Remark 2.** Theorem 1 is illustrated in Figure 1 showing the phase boundaries where the metastable exponents are not differentiable by bold lines. In both models they divide the slow extinction region into six different phases. The parametrisation with $(\tau, \eta)$ leads to phase boundaries which are line segments, which is not the case if $(\gamma, \eta)$ is used as a parametrisation as in [12, Figure 1]. Figure 1 also uses colours to show for which of the survival strategies the upper bounds for the metastable exponent matches the lower bounds. It is interesting to see that a crossover between strategies can occur without a phase transition, and a phase transition without a crossover between strategies.

**Remark 3.** Theorem 1 shows that our model interpolates nontrivially between the static case, when $\eta \to -\infty$ and the mean-field case, when $\eta \to +\infty$. Metastable exponents have been found for the static case for a model with factor kernel in [16] and with preferential attachment kernel in [3], and in the mean-field case implicitly in [18].

The rest of this paper is structured as follows. The most innovative results, which provide bounds under general assumptions on the kernel $p$, are stated as Theorems 2, 3 and 4. In Section 3 we prove the lower, and in Section 4 the upper bounds. The full proof of Theorem 4, which introduces a new ‘hybrid’ proof technique, is given in Section 5. We state the major intermediate steps in the proofs and results which are similar to results in the papers [12, 13] as propositions. In the latter case we keep the arguments brief.

**Notation.** This work involves many constants whose precise value is not too important to us, but with nontrivial dependencies between each other. For them we often use the following notational convention. The constant is written with a small $c$ (resp. a capital $C$) if it is a “small positive constant” (resp. a “large constant”), typically introduced with a condition requiring it to be small (resp. large). Then the index indicates the number of the equation or theorem where the constant is introduced, so $c_{(4)}$ is introduced in (4) and $C_2$ in Theorem 2.
<figure><img src="image_3.png" /><figcaption>FIGURE 1. Phase diagram summarizing Theorem 1 for factor kernel (top) and preferential attachment kernel (bottom). Bold lines indicate first order phase transitions, i.e. parameters where the derivative of $\xi$ is discontinuous. The colour code refers to the dominating strategy. Note that a crossover between strategies can occur without a phase transition, and a phase transition without a crossover between strategies.</figcaption></figure>

### 3. SURVIVAL AND LOWER BOUNDS FOR THE METASTABLE DENSITY

Our aim in this section is to provide sufficient conditions for the survival of the contact process, while at the same time giving lower bounds on the metastable density. As in [12, 13] the proofs for survival and the lower metastable densities rely on a graphical construction of the process which can be found in [12] but which we summarize here for the sake of
completeness. The evolving network ($\mathscr{G}_t^{(N)}: t \ge 0, N \in \mathbb{N}$) is represented with the help of the following independent random variables;

(1) For each vertex $i \in \{1, \dots, N\}$, a Poisson point process $\mathcal{U}^i := (U_n^i)_{n \ge 1}$ of intensity $\kappa_i$, describing the updating times of the vertex $i$.

(2) For each $\{i, j\} \subset \{1, \dots, N\}$, $i \ne j$, a sequence $C^{ij} := (C_n^{ij})_{n \ge 0}$ of i.i.d. Bernoulli random variables with parameter $p_{ij}$, where $C_n^{ij} = 1$ if $\{i, j\}$ is an edge of the network between the $n$-th and $(n+1)$-th events in $\mathcal{U}^{ij} := \mathcal{U}^i \cup \mathcal{U}^j$.

Given the network we represent the infection by means of the following set of independent random variables,

(3) For each $i \in \{1, \dots, N\}$, a Poisson point process $\mathcal{R}^i = (R_n^i)_{n \ge 1}$ of intensity one describing the recovery times of $i$.

(4) For each $\{i, j\} \subset \{1, \dots, N\}$ with $i \ne j$, a Poisson point process $\mathcal{I}_0^{ij}$ with intensity $\lambda$ describing the infection times along the edge $\{i, j\}$. Only the trace $\mathcal{I}^{ij}$ of this process on the set

$$ \bigcup_{n=0}^{\infty} \{ [U_n^{ij}, U_{n+1}^{ij}) : C_n^{ij} = 1 \} \subset [0, \infty) $$

can actually cause infections. If just before an event in $\mathcal{I}^{ij}$ one of the involved vertices is infected and the other is healthy, then the healthy one becomes infected. Otherwise, nothing happens.

Throughout this section we slightly change both the network and the parameters of the model as was done in Section 3.1 in [13] in order to both simplify computations and formulate some of the results which will be used here.

Given a fixed $a = a(\lambda) \in (0, 1/2)$ we reduce the vertex set to $\mathscr{S} \cup \mathscr{C}^0 \cup \mathscr{C}^1 \cup \mathscr{V}^{\text{odd}}$ where

$$ \mathscr{S} := \{i \in \{\lceil \frac{aN}{2} \rceil + 1, \dots, \lceilaN\rceil\} : i \text{ is even}\}, $$

$$ \mathscr{C}^0 := \{j \in \{\lceil \frac{N}{2} \rceil + 1, \dots, N\} : j = 4k \text{ for some } k \in \mathbb{N}\}, $$

$$ \mathscr{C}^1 := \{j \in \{\lceil \frac{N}{2} \rceil + 1, \dots, N\} : j = 4k + 2 \text{ for some } k \in \mathbb{N}\}, $$

$$ \mathscr{V}^{\text{odd}} := \{i \in \{1, \dots, N\} : i \text{ is odd}\}. $$

The vertices in $\mathscr{S}$ correspond to stars, which are the key ingredients in the survival strategies. The vertices in $\mathscr{C} = \mathscr{C}^0 \cup \mathscr{C}^1$ correspond to connectors (low power vertices), which are partitioned into $\mathscr{C}^0$ and $\mathscr{C}^1$ depending on whether we use them to survive locally or spread the infection, and vertices in $\mathscr{V}^{\text{odd}}$ will be used to provide lower bounds for the metastable density. Observe that by assigning specific roles to vertices as above we neglect certain infection events and therefore obtain lower bounds for the probability of increasing events with respect to the process $(X_t: t \ge 0)$. As for the edges of the dynamical network we replace the connection probabilities $p_{ij}$ by $\tilde{p}_{ij}$ where

$$ \tilde{p}_{ij} = \begin{cases} p_{\lflooraN\rfloor, \lflooraN\rfloor} & \text{if } i, j \in \mathscr{S} \\ p_{\lflooraN\rfloor, N} & \text{if } i \in \mathscr{S}, j \in \mathscr{C} \text{ or } i \in \mathscr{C}, j \in \mathscr{S} \\ 0 & \text{if } i, j \in \mathscr{C}. \end{cases} $$
The idea behind simplifying the connection probabilities is to work on a model that uses only vertex quantity and not identity. Even though it still remains that the updating rates $\kappa$ are different for each edge, this idea becomes heuristically correct since $\kappa_i = \Theta(a^{-\gamma\eta})$ uniformly over all stars $i$, and $\kappa_j = \Theta(1)$ uniformly over all connectors $j$. Observe that we can construct both $\mathcal{G}_t$ and $\mathcal{G}_t$ so that $\mathcal{G}_t \subseteq \mathcal{G}_t$ and hence the original process dominates the one running on the subgraph. In order to ease notation and computations we will henceforth replace $\tilde{p}_{ij}$ by $\frac{1}{N}p(a, 1)$ or $\frac{1}{N}p(a, a)$ depending on the case.

Following the structure given in [13] we state the following lemma which provides a lower bound for the lower metastable density whenever metastability holds. We do not provide the proof since it is the same as in our previous work.

**Lemma 1** ([13], Lemma 3.1). Define $(\mathfrak{F}_t^{0,1})_{t \ge 0}$ as the filtration given by all the $\mathcal{R}^i$, $\mathcal{I}_0^{ij}$, and $\mathcal{U}^{ij}$ up to time $t$ where $i, j \notin \mathcal{V}^{odd}$, as well as all the connections between such vertices up to $t$. For any $r > 0$ and $t > 0$ there is $c_{(4)} > 0$ (independent of $\lambda, a, N$) such that

$$ \mathbb{E} \left[ \sum_{j \in \mathcal{V}^{odd}} X_{t+1}(j) \middle| \mathfrak{F}_t^{0,1} \right] \ge c_{(4)} \left( \int_0^1 (\lambda \mathrm{ap}(a, x) \wedge 1) \mathrm{d}x \right) N, \quad (4) $$

on any event $A \in \mathfrak{F}_t^{0,1}$ implying $|\{i \in \mathcal{S} : X_t(i) = 1\}| \ge r a N$.

The following result gives sufficient conditions for quick direct spreading and quick indirect spreading to hold, leading to slow extinction. These survival strategies do not rely on local survival of the infection on powerful vertices. They were already studied in [12, 13] and the proof in [13] can be adapted from the model with edge updating to the current setting the only relevant difference being that the definition of $T_0$-stable vertices should now include the requirement that vertices do not update within $T_0$.

**Proposition 1** ([13], Theorem 3.2). There exist positive $M_{(i)}$ and $M_{(ii)}$ (depending on $\kappa_0$) such that slow extinction and metastability hold for the contact process on the network if, for all $\lambda \in (0, 1)$, there is $a = a(\lambda) \in (0, 1/2)$ satisfying at least one of the following conditions:

(i) (Quick direct spreading) $\lambda \mathrm{ap}(a, a) > M_{(i)}$.

(ii) (Quick indirect spreading) $\lambda^2 \mathrm{ap}^2(a, 1) > M_{(ii)}$.

Moreover, in each of these cases we have

$$ \rho^{-}(\lambda) \ge c_{(5)} \lambda a \int_{0}^{1} p(a, s) \mathrm{d}s, \quad (5) $$

where $c_{(5)} > 0$ is a constant independent of $a$ and $\lambda$.

**Remark 4.** We have included in the statement that under the conditions of the theorem metastability holds, which is not part of the original result but which follows from the arguments in Section 3.5 of [13] and the observation that on the slow extinction event the proportion of infected stars never goes below some $\rho(\lambda) > 0$. Moreover, by condition (1) we have $\int_0^1 p(a, s) \mathrm{d}s \ge c_1 a^{-\gamma}$ so the lower bound in (5) is always of the form $c\lambda a^{1-\gamma}$.
We now turn to delayed direct spreading and delayed indirect spreading, which spreads as quick direct (resp. indirect) spreading while also relying on local survival of the infection around powerful vertices. This mechanism was also studied in [12], but as discussed in the introduction, local survival in the case $\eta < 0$ features a weaker degradation effect as compared to the case $\eta > 0$, while the spread of the infection is subject to the additional depletion effect. The main purpose of this section is to deal correctly with these new features so as to obtain the following theorem.

**Theorem 2.** Fix $\eta < 0$, and define

$$T_{\text{loc}} := T_{\text{loc}}(a, \lambda) := \lambda^2 p(a, 1) \kappa(a)^{-1}. \qquad (6)$$

There are constants $C_2$, $M_{(iii)}$, $M_{(iv)} > 0$ large and $c_2 > 0$ small, depending on $\gamma$, $\eta$, $\kappa_0$, $c_1$ and $c_2$ alone, such that slow extinction and metastability hold for the contact process if, for all $\lambda \in (0, c_2)$, there is $a = a(\lambda) \in (0, 1)$ satisfying the following two technical conditions

$$(i) p(a, 1) \le e^{1/\lambda}$$

$$(ii) \lambda^2 p(a, 1) > -C_2 \log(a\lambda)$$

as well as at least one of the following two conditions:

$$(iii) \textbf{(Delayed direct spreading)} \quad (\kappa(a) \wedge \lambda)ap(a, a)T_{\text{loc}} > M_{(iii)}.$$

$$(iv) \textbf{(Delayed indirect spreading)} \quad \lambda^2 ap^2(a, 1)T_{\text{loc}} > M_{(iv)}.$$

Moreover, in each of these cases we have

$$\rho^{-}(\lambda) \ge c_{(7)} \lambda a \int_{0}^{1} p(a, s) \, ds, \qquad (7)$$

where $c_{(7)} > 0$ is a constant independent of a and $\lambda$.

**Remark 5.** Again we do not address here the metastability, which follows from a simple adaptation of the arguments given in Section 3.5 of [13], and again the lower bound in (7) is always of the form $c\lambda a^{1-\gamma}$.

**Remark 6.** The condition

$$\lambda^2 ap^2(a, 1)T_{\text{loc}} > M_{(iv)}$$

required for delayed indirect spreading is similar to the one for quick indirect spreading, except for the $T_{\text{loc}}$ factor which allows for the infection to ‘wait’ around stars until spreading is possible. For delayed direct spreading, on the other hand, the condition reads

$$(\lambda \wedge \kappa(a))ap(a, a)T_{\text{loc}} > M_{(iii)}$$

so the same would be true if not for the factor $\lambda \wedge \kappa(a)$ replacing $\lambda$. This is due to the depletion effect described in the introduction. In [12] we have similar conditions for delayed direct/indirect spreading in the case $\eta \ge 0$, but without the depletion effect, and with a different expression for $T_{\text{loc}}$.

**Remark 7.** In order to address the right order of the local survival time we need to differentiate between short and long updating times. The short updating times will be handled with the use of Proposition 2 where we obtain lower bounds containing a logarithmic term, while long updating times will be handled with the use of Proposition 3 which gives lower
bounds without any such term. For $\eta < 0$ most updating times are long, and Proposition 3 then gives rise to the definition of $T_{loc}$ without logarithmic correction. We also discuss the case $\eta \ge 0$ where we obtain a local survival time with a logarithmic correction (coming from typical updating times being short), which can be shown to replace the $\log^2(\lambda a)$ correction appearing in the local survival time in [12], thus improving it.

**Remark 8.** In our proofs the spreading mechanisms are similar to the ones used in the fast evolving networks, which may come as a surprise since on these proofs the high rate of change in the graph played an important role in order to provide some degree of independence between infection events, while in this case, the slow evolving networks are closer in spirit to the static ones, for which there is a high level of dependency. The answer to this apparent contradiction is that even though updating times become large when a $\downarrow 0$, the local survival around stars become much larger, thus allowing for vertices to update many times on each unit interval, giving enough independence for our methods to work.

The rest of this section is divided as follows: In Section 3.1 we give a technical definition of the local survival event and show that upon reaching a given star its probability is bounded from below. In Sections 3.2 and 3.3 we show how the conditions given in Theorem 2 give slow extinction of the process.

**3.1. Local survival.** For static networks, the local survival mechanism has been studied many times, see for example [1, 5, 9], and is generally understood as the event in which a highly connected vertex infects neighbours which in turn infect it back, thus creating a persistent loop which eventually breaks down after some event of small probability. In this subsection we look at the local survival mechanism for evolving networks, if no assumption is specified results hold for arbitrary update parameters $\eta \in \mathbb{R}$.

Since the local survival mechanism will be used for different stars within the proof of slow extinction, we want to avoid the undesirable dependencies amongst them which arise from sharing common neighbours. To do so fix a sequence $(J_k)_{k \ge 1}$ of time intervals with $J_0 = [0, 4)$, $J_1 = [0, 5)$ and for $k \ge 2$, $J_k := [(k-2), (k+4))$ and define for each $k \in \mathbb{N}$ the set of stable connectors

$$ \mathcal{C}_k := \{j \in \mathcal{C}^0 : (\mathcal{R}^j \cup \mathcal{U}^j) \cap J_k = \emptyset\} $$

which can be seen as the set of useful connectors for local survival across all stars. Notice that, as mentioned before, we construct $\mathcal{C}_k$ using only connectors in $\mathcal{C}^0$ since the ones in $\mathcal{C}^1$ will be used to spread the infection. Now, for any given star $i \in \mathcal{S}$ and $t \ge 0$ define

$$ \mathcal{C}_{t,i} := \{j \in \mathcal{C}_{[t]} : \{i, j\} \in \mathcal{G}_t\} $$

which by definition of $\mathcal{C}_{[t]}$ are neighbours of $i$ that do not update nor recover on $[t, t+4]$ (this will be relevant throughout the following sections). Using these sets we now define the processes $\bar{X}_t^i$ as in [13].

**Definition 1.** Fix $i \in \mathcal{S}$. For any realisation of the graphical construction, the process $(\bar{X}_t^i: t \ge 0)$, is defined analogously to $(X_t: t \ge 0)$ with the only exception that

* $\bar{X}_0^i = X_0$ on $\mathcal{C}_{0,i} \cup \{i\}$ and $\bar{X}_0^i = 0$ everywhere else.
• An infection event $s \in \mathcal{I}^{hj}$ is only valid if

$$h = i \text{ and } j \in \mathcal{C}_{r,i} \text{ for some } r \in [s-4, s+1].$$

Observe that for a given $i \in \mathcal{S}$ the process $(\bar{X}_t^i)$ defined above depends only on the processes $\{\mathcal{I}^{ij}\}_{j \in \mathcal{C}^0}$, $\mathcal{R}^i$, $\mathcal{U}^i$, $\{\mathcal{R}^j\}_{j \in \mathcal{C}^0}$, and $\{\mathcal{U}^j\}_{j \in \mathcal{C}^0}$, as well as the respective connections $\{\mathcal{C}^{ij}\}_{j \in \mathcal{C}^0}$. Since both the infections and the connections are defined on the edges of the graph, it follows that we can make local survival events independent across different stars as soon as we work on a fixed realisation of the $\{\mathcal{R}^j\}_{j \in \mathcal{C}^0}$ and $\{\mathcal{U}^j\}_{j \in \mathcal{C}^0}$ processes. With this in mind observe that for any fixed $k$, connectors in $\mathcal{C}^0$ belong to $\mathcal{C}_k$ independently with probability $e^{-(\kappa(j)+1)|J_k|}$ which is lower bounded by a positive function of $\kappa_0$ and $\eta$. It follows then from a large deviation argument that there is a constant $c_{(8)} > 0$ depending on $\kappa_0$ and $\eta$ alone such that for any $N$ large

$$\mathbb{P}(|\mathcal{C}_k| > c_{(8)}N \text{ for all } k \in \{0, \dots, \lfloor e^{c_{(8)}N} \rfloor\}) \geq 1 - e^{-c_{(8)}N}, \quad (8)$$

where we call $\mathcal{A}_0$ the event on the left. Since the lower bound on the right is already of the form required for slow extinction we will work on a fixed realisation of the $\{\mathcal{R}^j\}_{j \in \mathcal{C}^0}$ and $\{\mathcal{U}^j\}_{j \in \mathcal{C}^0}$ processes such that $\mathcal{A}_0$ holds. Now that we have addressed independence we can start constructing the local survival event for a given star $i \in \mathcal{S}$, which consists of ‘surviving’ the updating events in $\mathcal{U}^i$ for a long time. Fix $s \ge 0$ and let $U(s)$ be the first event in $\mathcal{U}^i \cap (s, \infty)$. Define the event

$$S_s^{\text{short}} := \{U(s) - s \le 4 \text{ and } \bar{X}_{U(s)}^i(i) = 1\},$$

which can be thought as surviving an updating event that arrives quickly after time $s$. Our aim is to show that if at time $s$ the central node $i$ is infected and it has sufficiently many stable neighbours, then such survival is very likely to occur. To do so define for each $s \ge 0$ and $i \in \mathcal{S}$ the $\sigma$-algebra $\mathfrak{F}_s^i$ given by the graphical construction throughout $[0, s]$ restricted to the subgraph generated by $\{i\} \cup \mathcal{C}^0$. Also denote by $\mathfrak{F}$ the $\sigma$-algebra generated by the processes $\{\mathcal{R}^j, \mathcal{U}^j\}_{j \in \mathcal{C}^0}$.

**Proposition 2.** Fix $i \in \mathcal{S}$, $s \ge 0$, and $\lambda \le \frac{1}{4}$. Then $S_s^{\text{short}}$ is $\mathfrak{F}_{U(s)}^i$-measurable, and for any $0 < c < 1$,

$$\mathbb{P}(S_s^{\text{short}} | \mathfrak{F}_s^i, \mathfrak{F}) \ge 1 - \frac{C_{(9)}\kappa(a)}{c\lambda^2 p(a, 1)} \log \left( 1 + \frac{\lambda^2 cp(a, 1)}{(1 + \kappa(a))^2} \right) - e^{-4\kappa(a)} \quad (9)$$

on the event $\mathcal{A}_0 \cap \{|\mathcal{C}_{s,i}| > cp(a, 1) \text{ and } \bar{X}_s^i(i) = 1\}$, where $C_{(9)} = 20(1 + \kappa_0 + \kappa_0^{-1})^2$.

*Proof.* Abusing notation for the sake of clarity, we will assume that $\mathbb{P}$ stands for the law of the process conditioned on $\mathfrak{F}_s^i$ and $\mathfrak{F}$. The fact that $S_s^{\text{short}}$ is $\mathfrak{F}_{U(s)}^i$-measurable follows directly from the definition of $S_s^{\text{short}}$ so we only prove the inequality.

Let $(E_n)_{n \ge 1}$ be the ordered elements of $(\mathcal{R}^i \cup \mathcal{U}^i) \cap (s, \infty)$ so the sequence $(E_{n+1} - E_n)_{n \ge 1}$ are i.i.d. exponential random variables with rate $1 + \kappa(a)$, and each $E_n$ is independently assigned to be a recovery event with probability $1/(1+\kappa(a))$ or an updating event otherwise. Note that the first updating event occurs at $U(s) = E_M$ where $M$ is a geometric random variable with parameter $\kappa(a)/(1+\kappa(a))$ independent of $(E_n)_{n \ge 1}$. Our analysis of $\mathbb{P}(S_s^{\text{short}})$
will depend on $M$ as follows: On the event $\{M = 1\}$ there are no recovery events between $s$ and $U(s)$ so that

$$ \mathbb{P}(S_s^{\text{short}} \cap \{M=1\}) = \mathbb{P}(U(s) - s \le 4 \text{ and } M=1). \quad (10) $$

On the event $\{M \ge 2\}$, we write $T_l = E_1 - s$ and $T_r = E_M - E_{M-1}$ to denote the length of the intervals before the first recovery and after the last. Now, since $|\mathcal{C}_{s,i}| > cp(a, 1)$ we know that $i$ has at least $cp(a, 1)$ neighbours in $\mathcal{C}^0$ which do not update or recover throughout $[s, s+4]$ so on the event $\{U(s) - s \le 4\}$ it is enough for $\bar{X}_{U(s)}^i(i) = 1$ to occur, to find some such neighbour that gets infected in $[s, E_1]$ and infects $i$ back in $[E_{M-1}, E_M]$. Conditionally on $(E_n)_{n \ge 1}$ this occurs with probability

$$ 1 - (1 - (1 - e^{-\lambda T_l})(1 - e^{-\lambda T_r}))^{|\mathcal{C}_{s,i}|} \ge 1 - (1 - \lambda^2 T_l T_r / 4)^{|\mathcal{C}_{s,i}|} \ge 1 - e^{-\lambda^2 cp(a,1)T_l T_r / 4} $$

on the event $\{U(s) - s \le 4 \text{ and } M \ge 2\}$, since these events are independent for different neighbours, and where we have used that both $T_l$ and $T_r$ are bounded by 4 and $\lambda \le \frac{1}{4}$ to apply the inequality $1 - e^{-x} \ge x/2$. Taking expectations with respect to $(E_n)_{n \ge 1}$ and adding the result to (10) we obtain

$$ \mathbb{P}(S_s^{\text{short}}) \ge \mathbb{P}(U(s) - s \le 4) - \mathbb{E}[e^{-\lambda^2 cp(a,1)T_l T_r / 4} \mathbf{1}_{\{U(s) - s \le 4 \text{ and } M \ge 2\}}]. \quad (11) $$

If $\eta \ge 0$, then the event $\{U(s) - s \le 4\}$ is likely to occur and hence we do not lose much by further bounding (11) as

$$ \mathbb{P}(S_s^{\text{short}}) \ge \mathbb{P}(U(s) - s \le 4) - \mathbb{E}[e^{-\lambda^2 cp(a,1)T_l T_r / 4} \mathbf{1}_{\{M \ge 2\}}] $$

but conditionally on $\{M \ge 2\}$ the random variables $T_l$ and $T_r$ are just independent exponential random variables with parameter $1 + \kappa_a$. Since for i.i.d. exponential random variables $Y, Y'$ with rate 1 and $t \ge 0$ we have

$$ \mathbb{E}[e^{-tYY'}] = \mathbb{E}\left[\frac{1}{1+tY}\right] = \int_{0}^{+\infty} \frac{e^{-s}}{1+st}ds = \frac{e^{1/t}}{t} \int_{1/t}^{+\infty} \frac{e^{-s}}{s}ds \le \frac{\log(1+t)}{t} \quad (12) $$

we conclude that for $\eta \ge 0$ we have

$$ \begin{aligned} \mathbb{P}(S_s^{\text{short}}) &\ge \mathbb{P}(U(s) - s \le 4) - \mathbb{P}(M \ge 2) \frac{4(1+\kappa(a))^2}{\lambda^2 cp(a,1)} \log \left(1 + \frac{\lambda^2 cp(a,1)}{4(1+\kappa(a))^2}\right) \\ &\ge 1 - e^{-4\kappa(a)} - \frac{4(1+\kappa(a))}{\lambda^2 cp(a,1)} \log \left(1 + \frac{\lambda^2 cp(a,1)}{4(1+\kappa(a))^2}\right), \end{aligned} $$

where we used that $\mathbb{P}(M \ge 2) = \frac{1}{1+\kappa(a)}$. Inequality (9) follows as $\eta \ge 0$ and $a < 1$ imply $4(1 + \kappa(a)) \le 4(1 + \kappa_0^{-1})\kappa(a) \le C_{(9)}\kappa(a)$.

Suppose now that $\eta < 0$ so that $\{U(s) - s \le 4\}$ is no longer a likely event. In this scenario we observe that

$$ \{M \ge 2 \text{ and } U(s) - s \le 4\} \subseteq \{M = 2\} \cup \{M \ge 3 \text{ and } E_{M-1} - E_1 \le 4\} $$

and that both events $\{M = 2\}$ and $\{M \ge 3\} \cap \{E_{M-1} - E_1 \le 4\}$ are independent from $T_l, T_r$ conditionally on $M \ge 2$. To compute the probability of this event observe that $E_{M-1} - E_1$ corresponds to the sum of $M - 2$ exponential random variables with rate
1 + $\kappa(a)$, and since conditionally on $\{M \ge 3\}$, the random variable $M - 2$ is geometric with rate $\kappa(a)/(1 + \kappa(a))$, it follows that $E_{M-1} - E_1$ is exponential with rate $\kappa(a)$ and hence

$$ \mathbb{P}(M = 2 \text{ or } (M \ge 3 \text{ and } E_{M-1} - E_1 \le 4)) \le \frac{\kappa(a)}{1+\kappa(a)} + 1 - e^{-4\kappa(a)} \le 5\kappa(a). $$

Using the independence between the previous event and $T_l, T_r$ we obtain from (11) and (12),

$$ \begin{aligned} \mathbb{P}(S_s^{\text{short}}) &\ge \mathbb{P}(U(s) - s \le 4) - \mathbb{E}[e^{-\lambda^2 cp(a,1)T_l T_r/4} \mathbf{1}_{\{M \ge 2\} \cup \{M \ge 3 \wedge E_{M-1} - E_1 \le 4\}}] \\ &\ge \mathbb{P}(U(s) - s \le 4) - 5\kappa(a) \frac{4(1+\kappa(a))^2}{\lambda^2 cp(a,1)} \log \left(1 + \frac{\lambda^2 cp(a,1)}{4(1+\kappa(a))^2}\right) \\ &\ge 1 - \frac{C_{(9)}\kappa(a)}{\lambda^2 cp(a,1)} \log \left(1 + \frac{\lambda^2 cp(a,1)}{4(1+\kappa(a))^2}\right) - e^{-4\kappa(a)}, \end{aligned} $$

where in the last line we have used that if $\eta < 0$ then $20(1+\kappa(a))^2 \le 20(1+\kappa_0)^2 \le C_{(9)}$. $\square$

Recall that $S_s^{\text{short}}$ was thought as surviving an updating event that arrives quickly after time $s$. To address the case where updating events take a long time to occur we first define the set of *infected stable neighbours* of $i$ as

$$ \mathcal{C}'_{t,i} := \{y \in \mathcal{C}_{t,i} : \bar{X}_t^i(y) = 1\}, $$

which are the stable connectors of $i$ that are infected at time $t$. Similarly to [13], for any fixed $i \in \mathcal{S}$ and $t \ge 0$ we introduce the ‘good’ event $W_i(t)$ as

$$ W_i(t) = \left\{ |\mathcal{C}'_{t,i}| \ge \frac{c_{(8)}}{80} \lambda p(a, 1) \text{ and } \int_t^{t+1} \bar{X}_s^i(i) ds \ge \frac{1}{2} \right\}. \quad (13) $$

In words, the event $W_i(t)$ implies that on $[t, t+1]$ the central vertex is both infected a large proportion of the time, and has many infected neighbours. Again, for any $s \ge 0$ call $U(s)$ the first event in $U^i \cap (s, \infty)$ and define the random variable $n = [U(s) - s]$ so that $s + n \le U(s) < s + n + 1$. We can now define $S_s^{\text{long}}$ as the event in which

(1) $U(s) - s \ge 4$,

(2) for each $2 \le j \le n - 2$, the event $W_i(s + j)$ holds,

(3) $\bar{X}_{U(s)}^i(i) = 1$.

The following proposition shows that the event $S_s^{\text{long}}$ is very likely to occur.

**Proposition 3.** Fix $i \in \mathcal{S}$, $s \ge 0$, and $\eta < 0$, and let $\mathfrak{F}_s^i$ and $\mathfrak{F}$ as defined before Proposition 2. There are $0 < c_\lambda < 1/e$ small and $C_3 > 0$ large depending on $c_{(8)}$, $\gamma$, $\eta$, $\kappa_0$, $c_1$ and $c_2$ alone, such that if $\lambda \in (0, c_\lambda)$ and $a \in (0, 1)$ are chosen satisfying

(i) $p(a, 1) \le e^{1/\lambda}$

(ii) $\lambda^2 p(a, 1) > -C_3 \log(a\lambda)$

then $S_s^{\text{long}}$ is $\mathfrak{F}_{U(s)}^i$-measurable and there is $C_{(14)} > 0$ depending on $c_\lambda, c_{(8)}$, and the parameters $\gamma, \eta, \kappa_0, c_1$ and $c_2$, such that, for all $N$ sufficiently large,

$$ \mathbb{P}(S_s^{\text{long}} | \mathfrak{F}_s^i, \mathfrak{F}) \ge e^{-4\kappa(a)} - \frac{C_{(14)}}{\lambda^2 p(a, 1)} \quad (14) $$
on the event

$$ \mathcal{A}_1 := \mathcal{A}_0 \cap \{|\mathcal{C}_{s,i}| > \frac{c_{(8)}}{5} p(a, 1) \text{ and } \bar{X}_s^i(i) = 1\}, \quad (15) $$

for $\mathcal{A}_0$ as defined in (8).

*Proof.* As in the previous result we abuse notation for the sake of clarity, and assume that $\mathbb{P}$ stands for the conditional law given $\mathfrak{F}_s^i$ and $\mathfrak{F}$. The fact that $S_s^{long}$ is $\mathfrak{F}_{U(s)}$-measurable follows from the definition of $S_s^{long}$ so we only need to prove (14).

We first condition on $U(s)$ and assume that $\{U(s) - s \ge 4\}$. Since $\bar{X}$ is defined on the star graph formed by $i$ and $\mathcal{C}^0$, and $i$ does not update throughout $[s, U(s)]$, we can think of the updating clocks placed on each connector $j$ as placed on the edge $\{i, j\}$ instead, and hence on this interval the model is equivalent to the one studied in [13] (with the parameter $t$ being equal to 1) so we can use some of the results therein. As in said work we will assume that the realization of the dynamical network around $i$ is typical throughout $[s, U(s)]$, meaning that the event

$$ \mathcal{A}_2 := \{|\mathcal{C}_{s+k,i}| \ge \frac{c_{(8)}}{5} p(a, 1) \forall 1 \le k \le n\} $$

holds. As the initial distribution is the stationary measure, at any given time $t$ each connector $j \in \mathcal{C}_{[s]}$ belongs to $\mathcal{C}_{t,i}$ independently with probability $\frac{1}{N}p(a, 1)$, and because on $\mathcal{A}_0$ we have $|\mathcal{C}_{[t]}| > c_{(8)}N$, a Chernoff bound for binomial random variables gives

$$ \mathbb{P}(|\mathcal{C}_{t,i}| \le \frac{c_{(8)}}{5} p(a, 1) | \mathcal{A}_0) \le e^{-c_{(8)}p(a,1)/3}. \quad (16) $$

It follows that

$$ \mathbb{P}(\mathcal{A}_2 | \mathcal{A}_1, U(s)) \ge 1 - (U(s) - s)e^{-c_{(8)}p(a,1)/3}. \quad (17) $$

Fix now a realization of the updating events of the connectors on $[s, U(s)]$, and also on the connections between them and $i$ such that both $\mathcal{A}_1$ and $\mathcal{A}_2$ hold. On this event we have to bound from below the probability of $S_s^{long}$, so in particular we need to prove that the star $i$ manages to infect several connectors. This is exactly the content of Proposition 3.11 in [13], which (adapted to this context) states that there is $C_{(18)}$ depending on $c_{(8)}$ alone, such that if $\lambda^2 p(a, 1) \ge C_{(18)}$ then

$$ \mathbb{P}\left(\left|\mathcal{C}'_{s+2,i}\right| \ge \frac{c_{(8)}\lambda p(a,1)}{80} \mid U(s), \mathcal{A}_1, \mathcal{A}_2\right) \ge 1 - \frac{C_{(18)}(\lambda \log(\lambda p(a,1))+1)}{\lambda^2 p(a,1)} \ge 1 - \frac{2C_{(18)}}{\lambda^2 p(a,1)}, \quad (18) $$

where the second inequality follows from the hypothesis $p(a, 1) \le e^{1/\lambda}$, and by taking $c_\lambda < 1$. Observe that we can use this result by simply imposing that $C_3 > C_{(18)}$. Once there are sufficiently many infected neighbours of $i$, local survival around this star follows directly from Proposition 3.10 in [13], which (once again adapted to this context) states that by choosing $c_\lambda$ small depending on $c_{(8)}$, there is a universal $C_{(19)} > 0$ such that

$$ \mathbb{P}\left(\bigcap_{k=2}^{n-2} W_i(s+k) \mid U(s), \mathcal{A}_1, \mathcal{A}_2, \left|\mathcal{C}'_{s+2,i}\right| \ge \frac{c_{(8)}\lambda p(a,1)}{80}\right) \ge 1 - (U(s) - s)C_{(19)}e^{-\frac{c_{(8)}\lambda^2 p(a,1)}{200}} \quad (19) $$

on the event $\{U(s) - s \ge 4\}$, where the term $U(s) - s$ (not appearing in the original statement) follows from a union bound over the probability of failing to satisfy at least one
of the $W_i(s+k)$ events. Putting (17), (18) and (19) together we obtain that on the event $\{U(s) - s \ge 4\}$, we have

$$ \mathbb{P}\left(\bigcap_{k=2}^{n-2} W_i(s+k) \mid U(s), \mathcal{A}_1\right) \ge 1 - \frac{2C_{(18)}}{\lambda^2 p(a,1)} - (U(s)-s)\left[e^{-\frac{c_{(8)}p(a,1)}{3}} + C_{(19)}e^{-\frac{c_{(8)}\lambda^2 p(a,1)}{200}}\right]. $$

Assuming that $c_\lambda < 1$ is enough to guarantee that $C_{(19)}e^{-c_{(8)}\lambda^2 p(a,1)/200} \ge e^{-c_{(8)}p(a,1)/3}$ and hence we arrive at

$$ \mathbb{P}\left(\bigcap_{k=2}^{n-2} W_i(s+k) \mid U(s), \mathcal{A}_1\right) \ge 1 - \frac{2C_{(18)}}{\lambda^2 p(a,1)} - 2(U(s)-s)C_{(19)}e^{-c_{(8)}\lambda^2 p(a,1)/200}, \quad (20) $$

which addresses condition (2) in the definition of $S_s^{long}$. In order to address condition (3) within that definition we now prove that

$$ \mathbb{P}(\bar{X}_{U(s)}^i(i) = 1 | W_i(s+n-2), U(s), \mathcal{A}_1) \ge 1 - \frac{100}{c_{(8)}\lambda^2 p(a,1)}. \quad (21) $$

Observe that if $W_i(s+n-2)$ holds then $|\mathcal{C}'_{s+n-2,i}| > c_{(8)}\lambda p(a,1)/80$ and since stable connectors do not update nor recover in at least 4 units of time, these represent sources of infection throughout the interval $[s+n-1, U(s)]$. Now, let

$$ \mathcal{Z} := \bigcup_j \mathcal{I}_0^{ij} \cup \mathcal{R}^i, $$

where $j$ ranges over all the connectors in $\mathcal{C}'_{s+n-2,i}$, and which from our assumption on the number of stable connectors, is a Poisson point process with intensity bounded from below by $(c_{(8)}\lambda^2 p(a,1)/80) + 1$. It is sufficient for $i$ to be infected at time $U(s)$ that

* $\mathcal{Z} \cap [s+n-1, U(s)] \ne \emptyset$ (observe that $[s+n-1, U(s)]$ has length at least 1), and

* the last element of $\mathcal{Z}$ in this set does not belong to $\mathcal{R}^i$,

so computing the probability of these two events gives the lower bound

$$ \begin{aligned} \left(1 - e^{-\frac{c_{(8)}\lambda^2 p(a,1)}{80}}\right)^{-1} \left(1 - \frac{80}{c_{(8)}\lambda^2 p(a,1)+80}\right) &\ge 1 - e^{-\frac{c_{(8)}\lambda^2 p(a,1)}{80}} - \frac{90}{c_{(8)}\lambda^2 p(a,1)} \\ &\ge 1 - \frac{100}{c_{(8)}\lambda^2 p(a,1)}, \end{aligned} $$

where both inequalities follow from the hypothesis $\lambda^2 p(a,1) \ge C_3$ with $C_3$ sufficiently large (depending on $c_{(8)}$). Combining (21) with (20), and assuming that $C_{(18)} \ge 50$ gives

$$ \mathbb{P}(S_s^{long} \mid U(s), \mathcal{A}_1) \ge 1 - \frac{4C_{(18)}}{\lambda^2 p(a,1)} - 2(U(s) - s)C_{(19)}e^{-c_{(8)}\lambda^2 p(a,1)/200} $$

on the event $\{U(s) - s \ge 4\}$. Taking expectations with respect to $U(s) - s$ (which is exponentially distributed with rate $\kappa(a)$) we obtain

$$ \mathbb{P}(S_s^{long} | \mathcal{A}_1) \ge e^{-4\kappa(a)} - \frac{4C_{(18)}}{\lambda^2 p(a,1)} - 2\kappa(a)^{-1}C_{(19)}e^{-c_{(8)}\lambda^2 p(a,1)/200}, $$
so in order to conclude (14) it is enough to show that by properly choosing the constants $c_\lambda$ and $C_3$ we have

$$2\kappa(a)^{-1}C_{(19)}e^{-c_{(8)}\lambda^2p(a,1)/200} \leq \frac{4C_{(18)}}{\lambda^2p(a,1)}.$$

Recall from (1) that $p(a, 1) \leq c_2 a^{-\gamma}$, so using condition (ii) from the hypothesis the previous inequality follows by showing that

$$2C_{(19)}(a\lambda)^{\frac{c_{(8)}C_3}{200}} \leq \frac{4C_{(18)}\kappa_0 a^{\gamma(1-\eta)}}{\lambda^2 c_2}$$

Since $a, \lambda < 1$ it is enough to choose $\frac{c_{(8)}C_3}{200} \geq \gamma(1 - \eta)$ and $c_\lambda$ so small that $c_\lambda^2 \leq \frac{4C_{(18)}\kappa_0}{2C_{(19)}c_2}$. The result follows by fixing $C_{(14)} = 8C_{(18)}$. $\square$

**Remark 9.** Observe that the previous result holds even if (i) is not satisfied. In this case the lower bound is slightly worse;

$$\mathbb{P}(S_s^{long} | \tilde{\mathfrak{F}}_s^i, \mathfrak{F}) \geq e^{-4\kappa(a)} - \frac{C_{(14)} \log(p(a, 1))}{\lambda p(a, 1)}$$

Now define $S_s := S_s^{long} \cup S_s^{short}$ and observe that under the conditions of Proposition 2 and Proposition 3 we have

$$\mathbb{P}(S_s | \tilde{\mathfrak{F}}_s^i, \mathfrak{F}) \geq 1 - \frac{5C_{(9)}\kappa(a)}{c_{(8)}\lambda^2 p(a, 1)} \log \left( 1 + \frac{c_{(8)}\lambda^2 p(a, 1)}{5(1 + \kappa(a))^2} \right) - \frac{C_{(14)}}{\lambda^2 p(a, 1)}$$

on the event $A_1$ if we choose $\lambda$ and $a$ satisfying the conditions of Proposition 3. Observe however that by definition of $\kappa(a)$ and (1) we have

$$\kappa(a) \log \left( 1 + \frac{c_{(8)}\lambda^2 p(a, 1)}{5(1 + \kappa(a))^2} \right) \leq \kappa_0 a^{-\gamma\eta} \log (1 + c_{(8)}c_2 a^{-\gamma})$$

which is bounded since $\eta < 0$, and where the bound depends on the parameters appearing in the inequality above. It follows that we can further bound

$$\mathbb{P}(S_s | \tilde{\mathfrak{F}}_s^i, \mathfrak{F}) \geq 1 - \frac{C_{(22)}}{\lambda^2 p(a, 1)} \qquad (22)$$

where $C_{(22)}$ again only depends on $c_{(8)}$, $\gamma$, $\eta$, $\kappa_0$, $c_1$ and $c_2$.

The event $S_s$ can be seen as surviving the next updating event after $s$, but in a specific way if the event takes a long time to occur. The main result of this section is Proposition 4, which states that once infected the process can survive in this manner until a given time horizon. Let $T > 0$ represent this time horizon and $0 \leq t \leq T$ be the time at which $i$ gets infected (the reader might think of taking the value $t = 0$ for all practical purposes). Also, let $u_1 < u_2 < \dots$ be the ordered elements of $U^i \cap [t, T]$ to which we also add $u_0 = t$. We use these times and events to give a technical definition of local survival.
**Definition 2.** Let $0 \le t < T$ we say that $i \in \mathcal{S}$ is $[t, T]$-infected if the following conditions are satisfied:

$$ (1) \quad \frac{T-t}{3} \kappa(\frac{a}{2}) \le |\mathcal{U}^i \cap [t, T]| \le 3(T-t)\kappa(a). $$

$$ (2) \quad \text{At every } u_k \text{ with } k < |\mathcal{U}^i \cap [t, T]| \text{ both } S_{u_k} \text{ and } \{|\mathcal{C}_{u_k, i}| > \frac{c_{(8)}}{5} p(a, 1)\} \text{ hold.} $$

$$ (3) \quad \bar{X}_T^i(i) = 1. $$

The next result states that given the conditions of Theorem 2, the probability of being $[t, T]$-infected is bounded away from zero for certain choices of $t$ and $T$.

**Proposition 4 (Local survival).** Recall the definition of $T_{loc}$ in (6) and the constants $c_\lambda$, $C_3$ from Proposition 3. Fix $i \in \mathcal{S}$ and assume that $\eta < 0$. For any $\varepsilon > 0$ there are $C_4 > C_3$, $0 < \tilde{c}_\lambda \le c_\lambda$ and $0 < \mathfrak{c}_0 < 1$ independent of $a$, $\lambda$ and $N$, such that if $\lambda \in (0, \tilde{c}_\lambda)$ and $a \in (0, 1)$ are chosen satisfying

$$ (i) \quad p(a, 1) \le e^{1/\lambda} $$

$$ (ii) \quad \lambda^2 p(a, 1) > -C_4 \log(a\lambda) $$

then for any $0 \le t \le T \le e^{c_{(8)}N}$ with $\frac{c_0 T_{loc}}{2} \le T - t \le \mathfrak{c}_0 T_{loc}$,

$$ \mathbb{P}(i \text{ is } [t, T]\text{-infected} \mid \mathfrak{F}_t^i, \mathfrak{F}) \ge 1 - \varepsilon, $$

on the event

$$ \{\bar{X}_t^i(i) = 1\} \cap \mathcal{A}_0 $$

where $\mathfrak{F}_t^i$ and $\mathfrak{F}$ are as defined before Proposition 2.

**Remark 10.** The condition $p(a, 1) \le e^{1/\lambda}$ is assumed here to avoid a logarithmic factor appearing as in Proposition 3.11 in [13], and it will be satisfied for all the cases treated in this paper since a is always a power of $\lambda$ (maybe with some logarithmic correction). However the result still holds redefining $T_{loc}$ as

$$ T_{loc} = \frac{\lambda p(a, 1)}{\kappa(a) \log(p(a, 1))}, $$

which follows from the proof of Proposition 4 and Remark 9. The condition $\lambda^2 p(a, 1) > -C_4 \log(a\lambda)$ on the other hand is slightly stronger than the usual condition $\lambda^2 k \gg 1$ required for local survival of a vertex of degree $k$ in the literature. Even though we could derive local survival under this weaker condition, we do not prove this and instead we ensure $[t, T]$-infection which is a stronger event that will be sufficient for the spreading mechanisms described in Sections 3.2 and 3.3.

**Proof.** As in the previous results we abuse notation and assume that $\mathbb{P}$ stands for the law of the process conditioned on $\mathfrak{F}_t^i$ and $\mathfrak{F}$. Since $|\mathcal{U}^i \cap [t, T]|$ is Poisson distributed with rate between $(T-t)\kappa(\frac{a}{2})$ and $(T-t)\kappa(a)$, both of them bounded from below by $2^{\gamma-1}\mathfrak{c}_0\lambda^2 p(a, 1) \ge C$, with $C = 2^{\gamma-1}\mathfrak{c}_0C_4$. It follows from standard Chernoff bounds that

$$ \mathbb{P}(|\mathcal{U}^i \cap [t, T]| \ge 3(T-t)\kappa(a)) \le e^{-C} $$
and

$$ \mathbb{P}(|\mathcal{U}^i \cap [t, T]| \le \frac{(T-t)}{3}\kappa(\frac{a}{2})) \le e^{-0.3C}, $$

so the probability of not satisfying condition (1) in Definition 2 is bounded by $2e^{-0.3C}$. To address condition (2) observe that, as in (16),

$$ \mathbb{P}(|\mathcal{C}_{t,i}| > \frac{c_{(8)}}{5} p(a, 1) | \mathcal{A}_0) \ge 1 - e^{-c_{(8)}p(a,1)/3}, $$

and since $C_4 > C_3$, $\tilde{c}_\lambda < c_\lambda$, and we are assuming $\bar{X}_t^i(i) = 1$, then (22) gives that $\mathbb{P}(S_s) \ge 1 - \frac{c_{(22)}}{\lambda^2 p(a,1)}$. The event is $\mathfrak{F}_{u_1}^i$-measurable so we can use the strong Markov property to restart the process at $u_1$, where the event $S_s$ now gives $\bar{X}_{u_1}^i(i) = 1$. Since on $u_1$ there is an updating time we can again use (16) to deduce $\mathbb{P}(|\mathcal{C}_{u_1,i}| > \frac{c_{(8)}}{5} p(a, 1) | \mathcal{A}_0) \ge 1 - e^{-c_{(8)}p(a,1)/3}$, which in turn allows us to bound the probability of $S_{u_1}$ from below as before. Proceeding repeatedly we get,

$$ \begin{aligned} \mathbb{P}(i \text{ does not satisfy (2)}) &\le \mathbb{P}(i \text{ does not satisfy (3)} \text{ and } |\mathcal{U}^i \cap [t, T]| \le 3(T-t)t\kappa(a)) + e^{-C} \\ &\le 3\mathfrak{c}_0 T_{loc}\kappa(a) \left( \frac{C_{(22)}}{\lambda^2 p(a, 1)} + e^{-c_{(8)}p(a,1)/3} \right) + e^{-C} \\ &\le 3\mathfrak{c}_0 T_{loc}\kappa(a) \left( \frac{C_{(22)}}{\lambda^2 p(a, 1)} + \lambda^{\frac{c_{(8)}}{3\lambda^2 C_4}} \right) + e^{-C} \\ &\le 3C_{(22)}\mathfrak{c}_0 + 3\mathfrak{c}_0\mathfrak{c}_2\lambda^{\frac{c_{(8)}}{3\lambda^2 C_4} - 2 - \gamma} + e^{-C}, \end{aligned} $$

where in the third inequality we have used (ii) from our assumptions, and in the last line we used the definition of $T_{loc}$ and (1). Finally, to address condition (3) we can repeat the proofs of Propositions 2 and 3 but replacing the event $\bar{X}_{U(s)}^i(i) = 1$ with $\bar{X}_T^i(i) = 1$, thus obtaining from (22)

$$ \mathbb{P}(i \text{ satisfies (3)} | u_l, \bar{X}_{u_l}^i(i) = 1) \ge 1 - \frac{C_{(22)}}{\lambda^2 p(a, 1)} \ge 1 - \frac{C_{(22)}}{C_4}. $$

Putting together all the bounds obtained thus far gives

$$ \mathbb{P}(i \text{ is not } [t, T]\text{-infected } | \mathfrak{F}_t^i, \mathfrak{F}) \le 4e^{-0.3C} + 3C_{(22)}\mathfrak{c}_0 + 3\mathfrak{c}_0\mathfrak{c}_2\lambda^{\frac{c_{(8)}}{3\lambda^2 C_4} - 2 - \gamma} + \frac{C_{(22)}}{C_4} $$

Now fix the constants $C_4$, $\tilde{c}_\lambda$, and $\mathfrak{c}_0$ as follows; first choose $\mathfrak{c}_0$ small such that $3C_{(22)}\mathfrak{c}_0 \le \frac{\varepsilon}{4}$, then fix $C_4$ sufficiently large such that $C_{(22)}/C_4 \le \frac{\varepsilon}{4}$ and $4e^{-0.3C} = 4e^{-0.32\gamma\eta-1}\mathfrak{c}_0C_4 \le \frac{\varepsilon}{4}$. Finally, fixing $\tilde{c}_\lambda$ sufficiently small so that

$$ 3\mathfrak{c}_0\mathfrak{c}_2\lambda^{\frac{c_{(8)}}{3\lambda^2 C_4} - 2 - \gamma} \le \frac{\varepsilon}{4} $$

we obtain the desired bound.

□
3.2. **Delayed direct spreading.** In this section we prove that under the main conditions of Theorem 2 together with

$$ (\kappa(a) \wedge \lambda)ap(a, a)T_{loc} > M_{(iii)}, $$

for sufficiently large $M_{(iii)}$, there is slow extinction and we get the corresponding lower bounds for the metastable density.

To begin the proof recall the definitions of $T_{loc}$, $J_k$, $\mathscr{C}_{t,i}$, $\mathscr{C}'_{t,i}$, $A_0$, the $\mathcal{S}$ events, and the $W_i(t)$ events pertaining to a given star $i \in \mathscr{S}$, together with the definition of $i$ being $[t, T]$-infected. Also recall the constants $\tilde{c}_\lambda$, $C_4$ and $0 < \mathfrak{c}_0 < 1$ appearing in Proposition 4, we will assume throughout this section that $C_4 > C_2$ and $c_2 \le \tilde{c}_\lambda$. Fix a realization of the $\mathcal{R}^j$ and $\mathcal{U}^j$ processes with $j \in \mathcal{C}^0$ such that $A_0$ holds, and define the sequences $\{\tilde{\mathcal{F}}_m\}_{m \in \mathbb{N}}$ and $\{\mathscr{S}'_m\}_{m \in \mathbb{N}}$ as

$$ \tilde{\mathcal{F}}_m := \{i \in \mathscr{S} : \bar{X}_{\mathfrak{c}_0 T_{loc} m}^i (i) = 1\} $$

$$ \mathscr{S}'_m := \{i \in \tilde{\mathcal{F}}_m : i \text{ is } [\mathfrak{c}_0 T_{loc} m, \mathfrak{c}_0 T_{loc} (m+1)]\text{-infected}\} $$

Since at time 0 all vertices are infected we have $|\tilde{\mathcal{F}}_0| = aN/2$. Our goal is to show that there are small constants $c_{(23)}$, $c'_{(23)} > 0$ with $c_{(23)}$ independent of $a$, $\lambda$ and $N$, and $c'_{(23)}$ independent of $N$ such that

$$ \mathbb{P}(|\tilde{\mathcal{F}}_{m+1}| > c_{(23)}aN | |\tilde{\mathcal{F}}_m| > c_{(23)}aN) \ge 1 - e^{-c'_{(23)}N}, \quad (23) $$

which together with a union bound gives slow extinction. Define $\mathcal{F}_t$ as the $\sigma$-algebra generated by the graphical construction up to time $t$, our proof relies on the fact from Proposition 4 that, for any $i \in \mathscr{S}$ and $\mathfrak{c}_0 T_{loc} m \le t \le \mathfrak{c}_0 T_{loc} (m + 1/2)$, taking $\varepsilon = \frac{1}{2}$,

$$ \mathbb{P}(i \text{ is } [t, \mathfrak{c}_0 T_{loc} (m+1)]\text{-infected} | \mathcal{F}_t) \ge 1/2 \quad (24) $$

on the event $\{\bar{X}_t^i (i) = 1\}$ as soon as $\lambda$ and $a$ are sufficiently small (satisfying the conditions of the proposition). Now, it follows from the definition of $[t, \mathfrak{c}_0 T_{loc} (m+1)]$-infection that any star satisfying the event above must be infected at time $\mathfrak{c}_0 T_{loc} (m+1)$ so in the particular case $t = \mathfrak{c}_0 T_{loc} m$ we conclude that $\mathscr{S}'_m \subseteq \tilde{\mathcal{F}}_{m+1}$. On the other hand, from (24) we deduce that each $x \in \tilde{\mathcal{F}}_m$ belongs to $\mathscr{S}'_m$ independently with probability at least $1/6$ so from a large deviation bound we obtain

$$ \mathbb{P}(|\tilde{\mathcal{F}}_{m+1}| > \frac{1}{4}|\tilde{\mathcal{F}}_m| | \mathcal{F}_{\mathfrak{c}_0 T_{loc} m}) \ge (1 - e^{-c_{(23)}aN/10}) \mathbf{1}_{\{|\tilde{\mathcal{F}}_m| > c_{(23)}aN\}}. \quad (25) $$

From this bound it follows that (23) is automatically satisfied in the case $|\tilde{\mathcal{F}}_m| > 4c_{(23)}aN$ therefore we assume onwards that $c_{(23)}aN < |\tilde{\mathcal{F}}_m| \le 4c_{(23)}aN$, and further that $c_{(23)} < 1/16$ so that $4c_{(23)}aN \le \frac{aN}{4}$. Divide $[\mathfrak{c}_0 T_{loc} m, \mathfrak{c}_0 T_{loc} (m + 1/2)]$ into $\lfloor \mathfrak{c}_0 T_{loc} \kappa(a)/2 \rfloor$ intervals

$$ K_k = [\mathfrak{c}_0 T_{loc} m + k\kappa(a)^{-1}, \mathfrak{c}_0 T_{loc} m + (k+1)\kappa(a)^{-1}] $$

of length $\kappa(a)^{-1}$ (recall from our assumptions that $T_{loc} \kappa(a) = \lambda^2 p(a, 1)$ is large) and divide these intervals further into their first and second half, $K_k^-$ and $K_k^+$, respectively. Using
the $K_k$ we define a sequence of i.i.d. Bernoulli random variables $U(i, k)$ with $i \in \mathcal{S}'_m$ and $0 \le k \le \lfloor \mathfrak{c}_0 T_{loc} \kappa(a)/2 \rfloor - 1$ such that

$$U(i, k) = 1 \iff \mathcal{U}^i \cap K_k^- \neq \emptyset \text{ and } \mathcal{U}^i \cap K_k^+ = \emptyset, \quad (26)$$

that is, $U(i, k)$ indicates the event in which $i$ updates on the first half of $K_k$ and on the second half it does not update. Since the $K_k$ have length $\kappa(a)^{-1}$ it follows that $\mathbb{P}(U(i, k) = 1) \ge \varphi$ for some constant $\varphi$ depending on $\kappa_0$ and $\eta$ alone. Using these random variables we construct the set

$$\mathcal{S}_m'' := \left\{ i \in \mathcal{S}_m' : \sum_{k=0}^{\lfloor \mathfrak{c}_0 T_{loc} \kappa(a)/2 \rfloor - 1} U(i, k) \ge \frac{\varphi \mathfrak{c}_0 T_{loc} \kappa(a)}{4} \right\},$$

which contains the stars that satisfy the condition appearing in (26) for sufficiently many intervals $K_k$. Noticing that the random variables $\{U(i, k)\}_{i \in \mathcal{S}'_m, k \ge 0}$ are independent and that $\mathfrak{c}_0 T_{loc} \kappa(a) \ge \mathfrak{c}_0 C_2$ can be taken to be large, we deduce from a large deviation argument together with (24) that

$$\mathbb{P}(i \in \mathcal{S}_m'' | \mathcal{F}_{\mathfrak{c}_0 T_{loc} m}) \ge \frac{1}{8}$$

on the event $\{\bar{X}_{\mathfrak{c}_0 T_{loc} m}^i(i) = 1\}$, and hence for $N$ sufficiently large yet another large deviation argument gives

$$\mathbb{P}(|\mathcal{S}_m''| > \frac{c_{(23)}aN}{16} | \mathcal{F}_{T_{loc}m}) \ge (1 - e^{-c_{(23)}N/30}) 1_{\{|\tilde{\mathcal{F}}_m|>c_{(23)}aN\}}$$

Let $\mathcal{A}_m = \{|\mathcal{S}_m''| > \frac{c_{(23)}aN}{16}\}$ the event within the probability above, which we will assume holds for a given $m$ since the lower bound is already of the form $1 - e^{-cN}$. Let $i \in \mathcal{S} \setminus \tilde{\mathcal{S}}_m$ be a star not infected at time $\mathfrak{c}_0 T_{loc} m$; our main goal is to show that the probability that at some point in $[\mathfrak{c}_0 T_{loc} m, \mathfrak{c}_0 T_{loc}(m + \frac{1}{2})]$ $i$ becomes infected by some $i' \in \mathcal{S}_m''$, is bounded from below by some constant independent of $a, \lambda$ and $N$. To do so fix $i' \in \mathcal{S}_m''$ and observe:

* By definition $U(i', k) = 1$ for at least $\varphi \mathfrak{c}_0 T_{loc} \kappa(a)/4$ many intervals $K_k$.

* For any fixed such $k$ there are no updating events of $i'$ on $K_k^+$ which means that the time difference between the last updating event $u_l$ in $K_k^-$ to the next one is greater than 4.

* Since $i'$ is $[\mathfrak{c}_0 m, \mathfrak{c}_0 T_{loc}(m + 1)]$-infected we know that $S_{u_l}^{long}$ holds and hence the event $W_{i'}(u_l + \ell)$ holds for every $\ell \in \mathbb{N}$ with $u_l + \ell \in K_k^+$. In particular, we have

$$\int_{K_k^+} \bar{X}_{s}^{i'}(i') \, ds \ge \kappa(a)^{-1/8}$$

* Since there is at least one updating event of $i'$ in $K_k^-$, the edge $\{i, i'\}$ is present throughout $K_k^+$ with probability $p(a, a)/N$.

As a result of these observations the probability of $i'$ infecting $i$ at some $t \in K_k$ is at least

$$(1 - e^{-\lambda \kappa(a)^{-1}/8}) \frac{p(a, a)}{N} \ge \frac{(1 \wedge \lambda \kappa(a)^{-1}) p(a, a)}{20N}$$
and since $i' \in \mathcal{S}_m''$, there are at least $\varphi_{c_0}T_{loc}\kappa(a)/4$ intervals $K_k$ of length $\kappa(a)^{-1}$ such that $U(i', k) = 1$. When considering all the pairs $(i', K_k)$ with $i' \in \mathcal{S}_m''$ and $K_k$ as before we conclude that

$$ \mathbb{P}(\exists i' \in \mathcal{S}_m'' \text{ that infects } i \text{ in } [c_0 T_{loc} m, c_0 T_{loc} (m + \frac{1}{2})] \mid |\mathcal{S}_m''| > \frac{c_{(23)} a N}{16}) \quad (27) $$

is bounded from below by

$$ 1 - \left(1 - \frac{(1 \wedge \lambda \kappa(a)^{-1}) p(a,a)}{20N}\right)^{\frac{c_{(23)} \varphi_{c_0} T_{loc} \kappa(a) a N}{32}} \geq 1 - \exp\left(-\frac{c_{(23)} c_0 \varphi(\kappa(a) \wedge \lambda) a p(a,a) T_{loc}}{1500}\right) \geq \frac{2}{3}, $$

where the last inequality follows from our assumptions on the parameters, given that $M_{(iii)}$ is taken large enough. Assume now that the event above holds and let $\tau_i$ be the first time in $[c_0T_{loc}m, c_0T_{loc}(m + \frac{1}{2})]$ that $\bar{X}_{\tau_i}^i(i) = 1$. The idea at this point is to ask whether $i$ is $[\tau_i, c_0T_{loc}(m+1)]$-infected which in particular implies that $i$ is infected at time $T_{loc}(m+1)$ and hence $i \in \tilde{\mathcal{S}}_{m+1}$. Now, these events rely on the $\mathcal{I}^{i,j}$, $\mathcal{C}^{i,j}$ and $\mathcal{U}^i$ events on $[\tau_i, c_0T_{loc}(m+1)]$ and hence are independent of the event in (27). Also, since $\varphi$ is independent of $a, \lambda$ and $N$ we can apply (24) with $t = \tau_i$ to conclude that

$$ \mathbb{P}(i \in \tilde{\mathcal{S}}_{m+1} \mid \exists i' \in \mathcal{S}_m'' \text{ that infects } i \text{ in } [c_0 T_{loc} m, c_0 T_{loc} (m + \frac{1}{2})]) \geq \frac{1}{12}. $$

Finally, observe that from our assumption $c_{(23)} < \frac{1}{48}$ we have $|\mathcal{S} \setminus \tilde{\mathcal{S}}_m| \geq \frac{aN}{4}$ in the event $\{c_{(23)}aN < |\tilde{\mathcal{S}}_m| \leq 4c_{(23)}aN\}$ and since the events $\{i \in \tilde{\mathcal{S}}_{m+1}\}$ are independent we can use a large deviation bound to conclude

$$ \mathbb{P}(|\tilde{\mathcal{S}}_{m+1}| \geq \frac{aN}{320} | c'_{(23)}aN < |\tilde{\mathcal{S}}_m| \leq 4c_{(23)}aN) \geq 1 - e^{-c'_{(23)}N}, $$

for some $c'_{(23)} > 0$ independent of $N$. By taking $c_{(23)} < \frac{1}{320}$ we finally conclude (23).

To obtain the lower bound on the metastable density given by (7) fix $c_0T_{loc} < t < e^{c'_{(23)}N}$ (we can take $t > c_0T_{loc}$ w.l.o.g. since $T_{loc}$ does not depend on $N$) and observe that from the last proof we have deduced in particular that

$$ \mathbb{P}(|\tilde{\mathcal{S}}_{m-1}| > c_{(23)}aN) \geq 1 - e^{-c'_{(23)}N}, $$

where $m$ is such that $t \in [c_0T_{loc}m, c_0T_{loc}(m+1)]$. We can use a slightly extended proof of Lemma 4 including intervals of length up to $2c_0T_{loc}$ to conclude that for every $i \in \tilde{\mathcal{S}}_{m-1}$ we have

$$ \mathbb{P}(i \text{ is } [c_0 T_{loc}(m-1), t] \text{ infected } | |\tilde{\mathcal{S}}_{m-1}| > c_{(23)} a N) \geq c' $$

for some $c' > 0$ independent of $a, \lambda$ and $N$. Using a large deviation bound we conclude that the total number of stars satisfying the event above is at least $ac_{(23)}c'N/2$ with high probability. As these stars are infected at time $t$ the result follows from Lemma 1.
### 3.3. Delayed indirect spreading.
In this section we prove that under the main conditions of Theorem 2 together with

$$ \lambda^2 ap^2(a, 1)T_{loc} > M_{(iv)}, $$

for sufficiently large $M_{(iv)}$, there is slow extinction and we get the corresponding lower bounds for the metastable density. We follow a similar structure to the one used in the previous section but incorporating the ideas used for delayed indirect spreading in [12]. As before, recall from Section 3.1 the definitions of $T_{loc}$, $J_k$, $\mathcal{C}_{t,i}$, $\mathcal{C}'_{t,i}$, $A_0$, the $S$ events, and the $W_i(t)$ events pertaining to a given star $i \in \mathcal{S}$, together with the definition of $[t, T]$-infection. As before recall the constants $\tilde{c}_\lambda$, $C_4$ and $0 < c_0 < 1$ appearing in Proposition 4, and assume that $C_4 > C_2$ and $c_2 \le \tilde{c}_\lambda$. Further, assume that $A_0$ holds and define the sequences $\{\tilde{\mathcal{I}}_m\}_{m \in \mathbb{N}}$ and $\{\mathcal{I}'_m\}_{m \in \mathbb{N}}$ as in Section 3.2. Once again, the main goal is to show that there are small constants $c_{(28)}$, $c'_{(28)} > 0$ to be fixed later, with $c_{(28)}$ independent of $a$, $\lambda$ and $N$, and $c'_{(28)}$ independent of $N$ such that

$$ \mathbb{P}(|\tilde{\mathcal{I}}_{m+1}| > c_{(28)}aN \mid |\tilde{\mathcal{I}}_m| > c_{(28)}aN) \ge 1 - e^{-c'_{(28)}N}, \quad (28) $$

which together with a union bound gives slow extinction. Following the same reasoning as in the previous section we obtain

$$ \mathbb{P}(|\tilde{\mathcal{I}}_{m+1}| > \frac{1}{4}|\tilde{\mathcal{I}}_m| \mid \mathcal{F}_{c_0 T_{loc} m}) \ge (1 - e^{-c_{(28)}N/10})1_{\{|\tilde{\mathcal{I}}_m| > c_{(28)}aN\}}, $$

and (28) is automatically satisfied in the case $|\tilde{\mathcal{I}}_m| \ge 4c_{(28)}aN$. Henceforth we may assume that $c_{(28)}aN < |\tilde{\mathcal{I}}_m| \le 4c_{(28)}aN$ (once again choosing $c_{(28)} \le \frac{1}{16}$). It is at this point that the proof differs from the previous one. Indeed, while in the case of direct spreading the proof relied on showing that most stars update in a 'normal' fashion, in this case the main idea is to show that the local survival of stars is sufficiently 'synchronous', meaning that during a fraction of the time we will always observe sufficiently many infected stars that can transmit their infections to connectors in $\mathcal{C}^1$. We begin by introducing a set of indices

$$ \mathcal{J} := 5\mathbb{N} \cap [c_0 T_{loc} m, c_0 T_{loc} (m + \frac{1}{2})] $$

which are used to define time intervals of the form $[k, k+5]$ with $k \in \mathcal{J}$. Using these indices we now define a new sequence of i.i.d. Bernoulli random variables $\bar{U}(i, k)$ with $i \in \mathcal{S}'_m$ and $k \in \mathcal{J}$ such that

$$ \bar{U}(i, k) = 1 \iff \mathcal{R}^i \cap [k, k+5] = \emptyset, \quad (29) $$

and use these random variables to define the set of synchronous stars $\mathcal{S}^s_m$ as

$$ \mathcal{S}^s_m := \{i \in \mathcal{S}'_m : \sum_{k \in \mathcal{J}} \bar{U}(i, k) > \frac{c_0 T_{loc}}{60e^5}\}. $$

The definition of $\mathcal{S}^s_m$ given here is similar to the one introduced in Definition 5 in [12]. The main idea is that intervals $[k, k+5]$ with sufficiently many stars satisfying $\bar{U}(i, k) = 1$ serve as time windows in which connectors can become infected. These connectors, however,
need to be able to hold the infection in order to further infect more vertices. We thus
define for every $k \in \mathcal{J}$ the set

$$
\mathcal{C}_k^1 := \{ j \in \mathcal{C}^1 : \mathcal{U}^j \cap [k+3, k+4] \neq \emptyset, (\mathcal{U}^j \cup \mathcal{R}^j) \cap [k+4, k+5] = \emptyset \}
$$

of stable connectors, which neither update nor recover throughout $[k+4, k+5]$ but updated
before. We claim that for any fixed $k \in \mathcal{J}$, a stable connector $j \in \mathcal{C}_k^1$ is infected throughout
$[k+4.5, k+5]$ as soon as there is some $i \in \mathcal{S}_m'$ for which:

$$
(i) \mathcal{R}^i \cap [k, k+5] = \emptyset,
$$

(ii) $i$ is a neighbour of $j$ at time $k+4$, and

$$
(iii) \mathcal{I}_0^{ij} \cap [k+4, k+4.5] \neq \emptyset.
$$

Indeed, suppose that (i) holds; because $i \in \mathcal{S}_m'$, by definition it must be $[c_0T_{loc}m, c_0T_{loc}(m+1)]$-infected and hence it is either the case that there is an updating event $u \in [k, k+4]$ at which $S_u$ holds so $i$ is infected, or there are no updating events in this interval, in which case at the last updating event $u$ we had $S_u^{long}$ and hence $W_i(u+l)$ holds for some $u+l \in [k, k+3]$ which again means that $i$ is infected at some time in $[k, k+4]$. Either way, because $\mathcal{R}^i \cap [k, k+5] = \emptyset$ the infection of $i$ is sustained throughout $[k+4, k+5]$ and hence it follows directly from (ii), (iii) that there is a valid infection event between $i$ and $j$ in $[k+4, k+4.5]$. By definition of $\mathcal{C}_k^1$, $j$ does not recover throughout $[k+4, k+5]$, thus proving the claim.

Observe that a given $i \in \mathcal{S}_m'$ belongs to $\mathcal{S}_m^s$ with probability at least $1 - e^{-0.3c_0T_{loc}/20e^5} \ge \frac{1}{8}$, where the bound follows by choosing $C_4$ large (depending on $c_0$). From this bound and Proposition 4 (fixing $\epsilon = \frac{1}{2}$) we thus obtain that

$$
\mathbb{P}(i \in \mathcal{S}_m^s \mid \mathcal{F}_{c_0 T_{loc} m}) \ge \frac{1}{16}
$$

on the event $\{\bar{X}_{c_0 T_{loc} m}^i (i) = 1\}$ and hence a large deviation argument gives

$$
\mathbb{P}(|\mathcal{S}_m^s| \ge \frac{c_{(28)}}{48} aN \mid \mathcal{F}_{c_0 T_{loc}m}) \ge \left(1 - e^{-c_{(28)}N/80}\right) 1_{\{|\tilde{\mathcal{M}}_m| > c_{(28)}aN\}}, \quad (30)
$$

which is already a bound of the right form for slow extinction so we may as well assume that
$|\mathcal{S}_m^s| \ge \frac{c_{(28)}}{48} aN$ as soon as $|\tilde{\mathcal{S}}_m| > c_{(28)}aN$. Similarly, observe that since the connectors
have index at least $N/2$ we can safely say that each $j \in \mathcal{C}^1$ belongs to $\mathcal{C}_k^1$ independently
with some probability $\varphi$ depending on $\kappa_0$ alone. Hence it follows from a large deviation
argument that

$$
\mathbb{P}(|\mathcal{C}_k^1| \ge \varphi N/3) \ge 1 - e^{-0.3\varphi N} \quad (31)
$$

which is again of the right form for slow extinction so we again assume that $|\mathcal{C}_k^1| \ge \varphi N/3$
for all $k \in \mathcal{J}$. Write $\mathcal{B}$ for the event $\{|\mathcal{S}_m^s| \ge \frac{c_{(28)}}{48} aN\} \cap \{|\mathcal{C}_k^1| \ge \varphi N/3\}, \forall k \in \mathcal{J}\}$ in
which there are many synchronous stars to spread the infection, and stable connectors to
receive it. Define now the index set

$$
\mathcal{K} := \left\{ k \in \mathcal{J} : \left| \left\{ i \in \mathcal{S}_m^s, \bar{U}(i, k) = 1 \right\} \right| \ge \frac{|\mathcal{S}_m^s|}{12e^5} \right\},
$$
which corresponds to the set of intervals at which we can find enough stars in $\mathcal{S}_m^s$ that do not recover. Using the previous claim and the definitions of $\mathcal{B}$ and $\mathcal{K}$ we deduce that there is some constant $c$ independent of $\lambda, a$ and $N$ such that

$$ \mathbb{P}(|\{j \in \mathcal{C}_k^1 : X_{k+4.5}(j) = 1\}| \ge \frac{c\varphi\lambda\mathrm{ap}(a,1)N}{9} | \mathcal{F}_{c_0T_{\mathrm{loc}}m}, \mathcal{B}, k \in \mathcal{K}) \ge 1 - e^{-0.1\varphi c\lambda\mathrm{ap}(a,1)N} \quad (32) $$

on the event $\{|\tilde{\mathcal{I}}_m| > c_{(28)}aN\}$. Indeed, for any $j \in \mathcal{C}_k^1$ and $i \in \mathcal{S}_m^s$ satisfying $\mathcal{R}^i \cap [k, k+5] = \emptyset$ the probability of satisfying (ii) and (iii) is equal to

$$ \frac{p(a,1)}{N} (1 - e^{-\lambda/2}) \ge \frac{\lambda p(a,1)}{4N} $$

because by definition $j$ updated during $[k+3, k+4]$. Since $\mathcal{B}$ holds there are many synchronous stars, and hence using the definition of $\mathcal{K}$ we conclude from a large deviation argument and the previous claim that any given $j \in \mathcal{C}_k^1$ is infected at time $k+4.5$ with probability at least

$$ 1 - \left(1 - \frac{\lambda p(a,1)}{4N}\right)^{\frac{c_{(28)}}{600e^5}aN} \ge 1 - \exp\left(-\frac{c_{(28)}\lambda p(a,1)}{2400e^5}\right) \ge c\lambda p(a,1), $$

where $c = 1/4800e^5$. Hence (32) follows from the bound on $|\mathcal{C}_k^1|$ and yet another large deviation argument.

So far we have seen that for any given $k \in \mathcal{K}$ with high probability there are of order $\lambda ap(a, 1)N$ infected connectors at time $k+4.5$. However, in order to spread the infection we need to consider all these sources of infections at different times $k \in \mathcal{K}$ simultaneously. For that purpose we introduce the set $\mathcal{P}_m$ of pairs $(k, j)$ as follows

$$ \mathcal{P}_m := \{(k, j) : k \in \mathcal{K}, j \in \mathcal{C}_k^1, X_{k+4.5}(j) = 1\}. $$

To lower bound the number of synchronous times in $\mathcal{K}$ we use a double count to deduce

$$ \frac{|\mathcal{S}_m^s|c_0T_{\mathrm{loc}}}{60e^5} \le \sum_{i \in \mathcal{S}_m^s} \sum_{k \in \mathcal{J}} \bar{U}(i, k) \le |\mathcal{K}| |\mathcal{S}_m^s| + \left(\frac{c_0T_{\mathrm{loc}}}{10} - |\mathcal{K}|\right) \frac{|\mathcal{S}_m^s|}{12e^5}, $$

where the left inequality follows from the definition of $\mathcal{S}_m^s$, and the right one from the fact that there are at most $\frac{c_0T_{\mathrm{loc}}}{10}$ intervals in $[c_0T_{\mathrm{loc}}m, c_0T_{\mathrm{loc}}(m + \frac{1}{2})]$, and the definition of $\mathcal{K}$. We conclude that $|\mathcal{K}| \ge c_0T_{\mathrm{loc}}/240e^5$. Putting this together with (30), (31), and (32) gives

$$ \mathbb{P}(|\mathcal{P}_m| \ge \frac{c\varphi\lambda\mathrm{ap}(a,1)c_0T_{\mathrm{loc}}N}{720e^5} | \mathcal{F}_{c_0T_{\mathrm{loc}}m}) \ge 1 - e^{-c_{(33)}N}, \quad (33) $$

for some $c_{(33)} > 0$ independent of $N$, on the event $\{|\tilde{\mathcal{I}}_m| > c_{(28)}aN\}$. In order to conclude (28) we need to show that stars in $\mathcal{S} \setminus \tilde{\mathcal{I}}_m$ have a sufficiently large chance of getting infected by the sources of infections represented by the pairs time-connector in $\mathcal{P}_m$. Fix $i \in \mathcal{S} \setminus \tilde{\mathcal{I}}_m$ and observe that in order for $i$ to get infected in $[c_0T_{\mathrm{loc}}m, c_0T_{\mathrm{loc}}(m + \frac{1}{2})]$ it is enough to find $(k, j) \in \mathcal{P}_m$ such that

(i) $j$ is a neighbour of $i$ at time $k+4$, and

(ii) $\mathcal{I}_0^{i,j} \cap [k+4.5, k+5] \ne \emptyset$.
Indeed, by definition of $\mathcal{C}_k^1$ the connector $j$ does not recover not update throughout $[k + 4.5, k + 5]$ so any infection towards $i$ in this interval is valid. Once again the probability of satisfying these conditions for a given pair $(k, j)$ is at least $\frac{\lambda p(a, 1)}{5N}$ and since the state of the edges $\{i, j\}$ at times $k + 4.5$ are independent across the $j$ and $k$ (since by definition the connector updated in the interval $[k + 3, k + 4]$), a large deviation argument yields

$$ 
\begin{aligned}
& \mathbb{P}\left(\exists t \in [c_0T_{loc}m, c_0T_{loc}(m + \frac{1}{2})] \text{ with } X_t(i) = 1 \middle| \begin{array}{l} \mathcal{F}_{c_0T_{loc}m}, |\mathcal{P}_m| \ge \frac{c\varphi\lambda ap(a, 1)c_0T_{loc}N}{720e^5} \\ \ge 1 - \left(1 - \frac{\lambda p(a, 1)}{4N}\right)^{\frac{c\varphi\lambda ap(a, 1)c_0T_{loc}N}{720e^5}} \ge 1 - \exp\left(\frac{c\varphi\lambda^2 ap^2(a, 1)c_0T_{loc}}{7000e^5}\right) \end{array} \right)
\end{aligned}
$$

on the event $\{|\tilde{\mathcal{I}}_m| > c_{(28)}aN$ and $i \in \mathcal{S} \setminus \tilde{\mathcal{I}}_m\}$. From the hypothesis of the Theorem we know that $\lambda^2 ap^2(a, 1)T_{loc} > M_{(iv)}$, and the constants $c_0, c$ and $\varphi$ do not depend on $a, \lambda$ or $N$, so taking $M_{(iv)}$ large enough we finally obtain

$$ P\left(\exists t \in [c_0T_{loc}m, c_0T_{loc}(m + \frac{1}{2})], X_t(i) = 1 \middle| \begin{array}{l} \mathcal{F}_{c_0T_{loc}m}, |\mathcal{P}_m| \ge \frac{c\varphi\lambda ap(a, 1)c_0T_{loc}N}{720e^5} \\ \ge \frac{2}{3} \end{array} \right) $$

on the event $\{|\tilde{\mathcal{I}}_m| > c_{(28)}aN$ and $i \in \mathcal{S} \setminus \tilde{\mathcal{I}}_m\}$. From this point onwards the proof is the same as the one in the previous section; defining $\tau_i$ as the first time in $[c_0T_{loc}m, c_0T_{loc}(m+\frac{1}{2})]$ that $X_{\tau_i}^i(i) = 1$ we flip a coin to ask whether $i$ is $[\tau_i, c_0T_{loc}(m+1)]$-infected which in particular implies that $i$ is infected at time $c_0T_{loc}(m+1)$ and hence $i \in \tilde{\mathcal{I}}_{m+1}$. Using (24) with $t = \tau_i$ we conclude that

$$ \mathbb{P}\left(i \in \mathcal{S}_{m+1}'' \middle| \begin{array}{l} \mathcal{F}_{c_0T_{loc}m}, |\mathcal{P}_m| \ge \frac{c\varphi\lambda ap(a, 1)c_0T_{loc}N}{720e^5} \\ \ge \frac{1}{36} \cdot 1_{\{c_{(28)}aN < |\tilde{\mathcal{I}}_m| \text{ and } i \in \mathcal{S} \setminus \tilde{\mathcal{I}}_m\}} \end{array} \right) $$

Finally, on the event $\{c_{(28)}aN < |\tilde{\mathcal{I}}_m| \le 4c_{(28)}aN\}$ we have $|\mathcal{S} \setminus \tilde{\mathcal{I}}_m| \ge \frac{aN}{4}$ and it follows from a large deviation bound together with (33) that

$$ \mathbb{P}\left(|\mathcal{S}_{m+1}''| \ge \frac{aN}{320} \middle| \begin{array}{l} \mathcal{F}_{c_0T_{loc}m} \ge (1 - e^{-c'N}) 1_{\{c_{(28)}aN < |\tilde{\mathcal{I}}_m| \le 4c_{(28)}aN\}} \end{array} \right) $$

for some $c' > 0$ independent of $N$. The result then follows by taking $c_{(28)} < \frac{1}{320}$. The corresponding lower bound for the metastable density follows the exact same proof as in the previous section so we omit it.

3.4. **Slow extinction and optimal strategies.** In this section we prove Theorem 1 in the case $\eta < 0$, that is, we show how to use the results from the previous sections to deduce slow extinction and find an upper bound for the metastability exponent for both the factor and preferential attachment kernels. More precisely, for each kernel and survival strategy we describe the parameters $\eta, \tau$ for which the strategy is available, with the union of these parameter sets constituting the region of slow extinction. As for any strategy the metastable density is bounded from lower by $\lambda ap(a, 1)$, which is increasing in $a$, we only need to obtain the maximal value of $a$ for which the strategy succeeds; this gives the best possible lower bound for the strategy and comparing all strategies we find the optimal strategy and the corresponding upper bound on the metastability exponent. In all cases, the maximal $a$ is a power of $\lambda$ and hence the condition $a \le e^{1/\lambda}$ appearing in Theorem 2 is automatically satisfied so we disregard it throughout this section.
3.4.1. *The factor kernel.* Recall that for the factor kernel $p(a, a) = a^{-2\gamma}$ and $p(a, 1) = a^{-\gamma}$ which we use to analyse the survival mechanisms separately:

* **Quick direct spreading:** The condition ensuring the mechanism works is that $\lambda a^{1-2\gamma} > M_{(i)}$, which is possible if $\gamma > \frac{1}{2}$ with a of order $a_{qds} = \lambda^{\frac{1}{2\gamma-1}+o(1)}$.

* **Quick indirect spreading:** The condition ensuring the mechanism works is that $\lambda^2 a^{1-2\gamma} > M_{(ii)}$, which is possible if $\gamma > \frac{1}{2}$ with a of order $a_{qis} = \lambda^{\frac{2}{2\gamma-1}+o(1)}$.

* **Delayed direct spreading:** For this mechanism two conditions need to be met,

$$ \lambda^2 a^{-\gamma} \ge C_2 \log(\frac{1}{a\lambda}) \quad \text{and} \quad (1 \wedge \lambda a^{\gamma\eta}) a^{1-3\gamma} \lambda^2 > M_{(iii)}. \qquad (34) $$

The mechanism is available as soon as $\gamma > \frac{1}{3}$. The metastability exponent analysis needs to be handled by dividing it into different subcases.

- Suppose the first condition in (34) is the most restrictive one. Maximizing $a$ subject to this condition gives $a$ of order $a_{ls} = \lambda^{2/\gamma+o(1)}$. Here the actual spreading mechanism does not affect the exponent. To check that the former succeeds we still require the second condition in (34) to hold. Replacing $a_{ls}$ in this condition gives

$$ (1 \wedge \lambda^{1+2\eta-o(1)}) \lambda^{\frac{2}{\gamma}-4-o(1)} = \lambda^{(0\vee(1+2\eta))+\frac{2}{\gamma}-4-o(1)} > M_{(iii)} $$

We get the restrictions $\gamma \ge \frac{1}{2}$ and $\gamma \ge \frac{2}{3-2\eta}$.

- Suppose now that the second condition in (34) is the most restrictive one while at the same time $\lambda a^{\gamma\eta} \le 1$ holds. The maximal $a$ is of order

$$ a_{dds} = \lambda^{\frac{3}{3\gamma-1-\gamma\eta}+o(1)} $$

Since we now require that both $\lambda^2 a^{-\gamma} \ge C_2$ and $\lambda a^{\gamma\eta} \le 1$ hold, substituting the expression for $a_{dds}$ gives the restrictions $\gamma \le \frac{2}{3-2\eta}$ and $\gamma > \frac{1}{3+2\eta}$.

- Suppose that the second condition in (34) is the most restrictive one while $\lambda a^{\gamma\eta} \ge 1$ holds, which is the case when depletion occurs. The maximal $a$ in the condition $\lambda^2 a^{1-3\gamma} > M_{(iii)}$ is of order

$$ a_{ddds} = \lambda^{\frac{2}{3\gamma-1}+o(1)} $$

We now require $\lambda^2 a^{-\gamma} \ge C_2$ and $\lambda a^{\gamma\eta} \ge 1$. Substituting the expression for $a_{ddds}$ gives the restrictions $\gamma \le \frac{1}{2}$ and $\gamma \le \frac{1}{3+2\eta}$.

* **Delayed indirect spreading:** As in the previous mechanism there are two conditions to be met, which after performing the same simplification as before are of the form

$$ \lambda^2 a^{-\gamma} \ge C_2 \quad \text{and} \quad \lambda^4 a^{1-3\gamma+\gamma\eta} \ge M_{(iv)}. \qquad (35) $$

In this case the condition under which slow extinction holds is $\frac{1}{3-\eta} < \gamma$ and for the metastability exponent we again treat separate scenarios:
- Suppose that the first condition in (35) is the most restrictive one, so that the maximal $a$ is of order $a_{ls}$. Substituting this in the second condition of (35) gives the restriction $\gamma \ge \frac{1}{1-\eta}$. Recall that delayed concurrent spreading is possible if both the direct and indirect spreading mechanisms succeed, which is the case if $\gamma \ge \frac{1}{2}$ and $\gamma \ge \frac{1}{1-\eta}$.

- Suppose now that the second condition in (35) is the most restrictive one, so that the maximal $a$ is of order

$$a_{dis} = \lambda^{\frac{4}{3\gamma-1-\gamma\eta}} + o(1)$$

Substituting $a_{dis}$ in the first condition of (35) gives the restriction $\gamma \le \frac{1}{1-\eta}$.

For each one of the densities above we compute the corresponding lower bound for the metastable density $\lambda ap(a, 1) = \lambda a^{1-\gamma}$ and express both the result and the restrictions on the parameters in terms of $\eta$ and $\tau = \frac{1}{\gamma} + 1$. The information is summarized in Table 1. The only thing left to do in order to conclude the first part of Theorem 1 is to compute which is the largest bound for the metastable density (or equivalent, which is the smallest exponent) in the region of slow extinction. This is an elementary exercise.

<table><caption>TABLE 1. Density and restrictions per mechanism for the factor kernel</caption><thead><tr><th>Mechanism</th><th>Density</th><th>Region</th></tr></thead><tbody><tr><td>Quick direct spreading</td><td>λ<sup>1/3-τ</sup> + o(1)</td><td>R<sub>1</sub> := {τ &lt; 3}</td></tr><tr><td>Quick indirect spreading</td><td>λ<sup>τ-1/3-τ</sup> + o(1)</td><td>R<sub>1</sub> = {τ &lt; 3}</td></tr><tr><td>Local survival</td><td>λ<sup>2τ-3+o(1)</sup></td><td>R<sub>2</sub> := {τ ≤ (5/2 - η) &wedge; 3} ∪ {τ ≤ 2 - η}</td></tr><tr><td>Delayed direct spreading</td><td>λ<sup>2τ-2-η/4-τ-η</sup> + o(1)</td><td>R<sub>3</sub> := {5/2 - η &lt; τ ≤ 4 + 2η}</td></tr><tr><td>Delayed depleted direct spreading</td><td>λ<sup>τ/4-τ</sup> + o(1)</td><td>R<sub>4</sub> := {(4 + 2η) &vee; 3 ≤ τ &lt; 4}</td></tr><tr><td>Delayed indirect spreading</td><td>λ<sup>3τ-4-η/4-τ-η</sup> + o(1)</td><td>R<sub>5</sub> := {2 - η ≤ τ &lt; 4 - η}</td></tr></tbody></table>

### 3.4.2. The preferential attachment kernel.
Recall that for the preferential attachment kernel $p(a, a) = a^{-1}$ and $p(a, 1) = a^{-\gamma}$. Again we analyse the survival mechanisms separately.

* **Quick direct spreading:** In this case the condition ensuring the mechanism is $\lambda > M_{(i)}$, which fails for $\lambda$ small for any choice of the parameters.

* **Quick indirect spreading:** In this case the condition ensuring the mechanism is $\lambda^2 a^{1-2\gamma} > M_{(ii)}$ which was already analysed for the factor kernel. It follows that the mechanism holds as soon as $\gamma > \frac{1}{2}$ and the maximal $a$ is of order $a_{qis}$ as before.

* **Delayed direct spreading:** For this mechanism the simplified conditions are

$$\lambda^2 a^{-\gamma} \ge C_2 \quad \text{and} \quad (1 \wedge \lambda a^{\gamma\eta})\lambda^2 a^{-\gamma} > M_{(iii)}. \qquad (36)$$
Surprisingly, for this kernel the mechanism is available for all values $\gamma$ and $\eta$, and we analyse the metastability exponent by considering two cases.

- Suppose that the first condition in (36) is the most restrictive one, which shows that the maximal $a$ is of order $a_{ls}$. Substituting $a_{ls}$ into the second condition in (36) gives the restriction $\eta \le -\frac{1}{2}$.

- Suppose now that the second condition in (36) is the most restrictive one and further assume that $\lambda a^{\gamma\eta} \le 1$ since otherwise we fall into the previous case. Maximizing $a$ in the condition $\lambda^3 a^{-\gamma+\gamma\eta} > M_{(iii)}$ gives the order

$$a_{dds} = \lambda^{\frac{3}{\gamma-\gamma\eta}+o(1)}$$

Observe that the condition $\lambda^2 a^{-\gamma} \ge C_2$ is trivially satisfied, while replacing $a_{dis}$ into the assumption gives the restriction $\eta \ge -\frac{1}{2}$.

* **Delayed indirect spreading:** Since the kernel appears in the conditions only through $p(a, 1) = a^{-\gamma}$ the analysis of this mechanism is the same as for the factor kernel and hence we have that the mechanism holds as soon as $\frac{1}{3-\eta} < \gamma$.

- If $\gamma \ge \frac{1}{1-\eta}$ then the maximal $a$ is of order $a_{ls} = \lambda^{\frac{2}{\gamma}+o(1)}$. Hence delayed concurrent spreading is possible if $\eta \le -\frac{1}{2}$ and $\gamma \ge \frac{1}{1-\eta}$.

- If $\gamma \le \frac{1}{1-\eta}$ then the maximal $a$ is of order $a_{dis} = \lambda^{\frac{4}{3\gamma-1-\gamma\eta}+o(1)}$.

As in the previous section we compute the corresponding lower bound for the metastable density $\lambda ap(a, 1) = \lambda a^{1-\gamma}$ for each mechanism and express both the result and the restrictions on the parameters in terms of $\eta$ and $\tau = \frac{1}{\gamma} + 1$, which are summarized in Table 2.

<table><caption>TABLE 2. Densities and restrictions per mechanism</caption><thead><tr><th>Mechanism</th><th>Density</th><th>Region</th></tr></thead><tbody><tr><td>Quick indirect spreading</td><td>λ<sup>τ-1</sup>/(3-τ)+o(1)</td><td>R<sub>1</sub> := {τ ≤ 3}</td></tr><tr><td>Local survival</td><td>λ<sup>2τ-3</sup>+o(1)</td><td>R<sub>2</sub> := {τ ≤ 2 - η} ∪ {η ≤ -1/2}</td></tr><tr><td>Delayed direct spreading</td><td>λ<sup>3τ-5-η</sup>/(1-η)+o(1)</td><td>R<sub>3</sub> := {η ≥ -1/2}</td></tr><tr><td>Delayed indirect spreading</td><td>λ<sup>3τ-4-η</sup>/(4-τ-η)+o(1)</td><td>R<sub>4</sub> := {2 - η ≤ τ < 4 - η}</td></tr></tbody></table>

We observe that among the delayed mechanisms the density associated to local survival is the largest and hence dominates in the domain $R_2$ where it is feasible. It is easy to calculate that delayed indirect spreading dominates delayed direct spreading if $\tau \le \frac{8}{3} + \frac{\eta}{3}$ and quick indirect spreading only prevails if no other strategy is available. This completes the proof of Theorem 1 in the case $\eta < 0$.
3.5. **Fast extinction phase.** Recall the distinction between fast extinction, where the expected extinction time grows as a power of $N$, and ultra-fast extinction, where it grows subpolynomially. Both for the factor kernel and the preferential attachment kernel ultra-fast extinction occurs if $\eta \ge \frac{1}{2}$ and $\tau > 3$, which follows directly from Theorem 2 in [12], which also gives a polynomial upper bound for the extinction time expectation in the fast extinction regimes for $\eta \ge 0$. For $\eta < 0$ an appropriate upper bound will follow from Theorem 3 in the next section. In order to conclude that no ultra-fast extinction occurs unless $\eta \ge \frac{1}{2}$ and $\tau > 3$, we need a lower bound for the expected extinction time, which we provide here in the case $\eta < 0$. The case $\eta \ge 0$ follows from analogous ideas together with the results found in Sections 4.3 and 4.4 in [12].

**Lemma 2.** Let $p$ be any kernel satisfying (1) and $\eta < 0$. Then for any $\varepsilon > 0$ there are constants $\tilde{c}_\lambda$ and $c_2$ such that for any $\lambda < \tilde{c}_\lambda$ and all $N$ large,

$$ \mathbb{P}(T_{\text{ext}} \ge \frac{\lambda c_2 N^{\gamma(1-\eta)}}{\log N} | X_0 = 1) = 1 - o(1) $$

**Remark 11.** Observe that the exponent given does not necessarily match the one from Theorem 3 below. Finding the exact exponent is an interesting question which could shed light onto the behaviour in the fast extinction regime. We do not pursue this here.

*Proof.* Fix $i = \frac{1}{N}$ which is the most powerful vertex in the network, and observe that it is initially infected since $X_0 = 1$. For this choice of $a$ we have from (1) that $p(a, 1) \ge c_1 a^{-\gamma} = c_1 N^{\gamma}$ and $\kappa(a) = \kappa_0 N^{\gamma\eta}$ it then follows from Proposition 4 together with Remark 10 that for any $\varepsilon > 0$ there is a choice of $\tilde{c}_\lambda$ and $c_0$ such that

$$ \mathbb{P}(i \text{ is } [0, c_0 T_{\text{loc}}]-\text{infected} | X_0 = 1, \mathfrak{F}) \ge 1 - \varepsilon, $$

on the event $\mathcal{A}_0$. Now, in this particular case

$$ T_{\text{loc}} = \frac{\lambda p(a, 1)}{\kappa(a) \log(p(a, 1))} = \frac{c \lambda N^{\gamma(1-\eta)}}{\log(N)}, $$

for some constant $c$. Taking $c_2 = c c_0$ and observing that from (8) we already have that $\mathbb{P}(\mathcal{A}_0) > 1 - e^{-c_0 N}$, the result then follows from the observation that by time $c_0 T_{\text{loc}}$ the vertex $i$ is infected and hence $T_{\text{ext}} > c_0 T_{\text{loc}}$. $\square$

## 4. UPPER BOUNDS

4.1. **Upper bound by local approximation.** Proposition 8 of [13] can be easily adapted to our situation and yields the following result.

**Proposition 5.** Suppose $\eta \le 0$. There is a constant $C_{(37)} > 0$ such that, for all $\lambda > 0$, the upper metastable density $\rho^+(\lambda)$ satisfies

$$ \rho^+(\lambda) \le \begin{cases} C_{(37)} \lambda^{\frac{1}{3-\tau}} & \text{in the case of the factor kernel with } \tau \le \frac{5}{2}, \\ C_{(37)} \lambda^{2\tau-3} & \text{in the case of either} \left\{ \begin{array}{l} \text{the preferential attachment kernel,} \\ \text{the factor kernel with } \tau > \frac{5}{2}. \end{array} \right. \end{cases} \quad (37) $$
This gives the right upper bound appearing in Theorem 1 only in the regions $R_2$ introduced in Section 3.4 for both kernels. The remaining regions are covered in next section.

### 4.2. Upper bound by the supermartingale technique.
We complete the proof of Theorem 1 by showing the following two propositions.

**Proposition 6.** Suppose $\eta < 0$. There is a constant $C_6 > 0$ such that the following holds:

(a) For the factor kernel,

(i) if $\tau > 4 - \eta$, there is fast extinction;

(ii) if $\frac{5}{2} - \eta \le \tau < 4 + 2\eta$, the upper metastable density satisfies

$$ \rho^{+}(\lambda) \le C_6 \lambda^{\frac{2\tau-2-\eta}{4-\eta-\tau}} $$

(iii) If $3 \wedge (4 + 2\eta) \le \tau \le 4 + \eta$, the upper metastable density satisfies

$$ \rho^{+}(\lambda) \le C_6 \lambda^{\frac{\tau}{4-\tau}} $$

(iv) If $(2 - \eta) \wedge (4 + 2\eta) \le \tau < 4 - \eta$, the upper metastable density satisfies

$$ \rho^{+}(\lambda) \le C_6 \lambda^{\frac{3\tau-2-\eta}{4-\tau-\eta}} $$

(b) For the preferential attachment kernel and $-\frac{1}{2} < \eta < 0$ the upper metastable density satisfies:

$$ \rho^{+}(\lambda) \le \begin{cases} C_6 \lambda^{\frac{3\tau-4-\eta}{4-\eta-\tau}} & \text{if } 2-\eta \le \tau \le \frac{8}{3}+\frac{\eta}{3}, \\ C_6 \lambda^{\frac{3\tau-5-\eta}{1-\eta}} & \text{if } \tau \ge \frac{8}{3}+\frac{\eta}{3}. \end{cases} $$

**Proposition 7.** Suppose $\eta \ge 1/2$ and $\tau > 3$. Then for the factor or preferential attachment kernel, there is ultra-fast extinction.

As in [12, Theorem 2] or [13, Theorem 5] the basic approach for the proof of Propositions 6 and 7 is to use a function $s: (0, 1] \to [1, \infty)$ associated with the model and a functional inequality satisfied by $s$ to define a supermartingale, which in first approximation associates the score $s(i/N)$ to each infected vertex $i$. The optional stopping theorem gives an upper bound on the time when the total score hits zero. The main difficulties in this approach are:

* Choosing an appropriate functional inequality. There is no ready-made recipe, although the inequalities we get, namely (41), (42), and (48)–(50), are directly inspired by understanding of the local survival and spreading mechanisms studied in Section 3.

* Defining the supermartingale. This is hard as the underlying Markov process of network evolution and infection has a large and complex state space with a sophisticated transition structure depending on the network geometry. To deal with this we introduce an exploration process which only partially reveals the network structure depending on the infection paths. Again, we are guided by our understanding of the survival mechanisms.
**Theorem 3** below allows us to prove Proposition 7 and to treat the case of the factor kernel in Proposition 6 (a),(i) and (ii), and of the preferential attachment kernel in Proposition 6 (b). Theorem 4 is considerably more difficult to prove as it introduces a new 'hybrid' approach where we treat low-degree vertices locally as in a static network and include this treatment in our global supermartingale approach. The combination of local and global ideas is the main technical innovation of this paper. Theorem 4 allows us to treat the case of the factor kernel in Proposition 6 (a)-(iii) and (iv).

**Definition 3.** Define $\pi: (0, 1) \to (0, \infty)$ and the time-scale function $T^{\text{loc}}: (0, 1) \to [1, \infty)$ as

$$ \pi(x) = \int_{0}^{1} \frac{p(x, y)}{\kappa(x) + \kappa(y)} dy, \qquad (38) $$

$$ T^{\text{loc}}(x) = \max \left\{ 8, \frac{8}{3\kappa(x)}, 16\lambda^2 \frac{\pi(x)}{\kappa(x)} \right\}. \qquad (39) $$

For given $j \in \{1, \dots, N\}$, the time $T_j^{\text{loc}} := T^{\text{loc}}(j/N)$ should be interpreted as an upper bound for the time during which the infection can survive locally around $j$ using only infections of its neighbours and direct reinfection of $j$ from these neighbours, but the precise definition of $T^{\text{loc}}$ comes from the statements and proofs of Theorems 3 and 4 below. The definition of $T^{\text{loc}}$ is of course to be compared with the definition of $T_{\text{loc}}$ by (6). In many cases we have $\pi(x) \asymp p(x, 1) \asymp x^{-\gamma}$ all of the same order, so for strong vertices we will typically have $T_j^{\text{loc}} \asymp \lambda^2(j/N)^{-\gamma} \kappa(j/N)^{-1} \asymp T_{\text{loc}}(j/N, \lambda)$ all of the same order, which is an indication that in these cases $T^{\text{loc}}$ is an accurate upper bound.

In Theorem 3 below, we will say a vertex $j$ is quick if it updates at rate $\kappa(j/N) \ge \lambda$ and slow if it updates at rate $\kappa(j/N) < \lambda$. When $\eta \ge 0$, we assume for simplicity $\lambda \le \kappa_0$ so all vertices are quick. When $\eta < 0$, a vertex is slow if $j/N < a_{\text{slow}}$, where $a_{\text{slow}}$ is defined as

$$ a_{\text{slow}} = \left( \frac{\lambda}{\kappa_0} \right)^{-\frac{1}{\gamma\eta}}. \qquad (40) $$

**Theorem 3.** Let $\eta \in \mathbb{R}$ and suppose there exists some $a = a(\lambda) \ge 0$ and some non-increasing function $s: [a, 1] \to [1, \infty)$, or $s: (0, 1] \to [1, \infty)$ if $a = 0$, such that for all $x > a$, we have

$$ 7T^{\text{loc}}(x) \int_{0}^{1} \lambda p(x, y) s(y \vee a) dy \le s(x) \qquad (41) $$

if $\eta \ge 0$ or $x \ge a_{\text{slow}}$, or

$$ 7 T^{\text{loc}}(x) \left( \int_{0}^{a_{\text{slow}}} (\kappa(x) \vee \kappa(y)) p(x, y) s(y \vee a) dy + \int_{a_{\text{slow}}}^{1} \lambda p(x, y) s(y) dy \right) \le s(x) \qquad (42) $$

if $\eta < 0$ and $x < a_{\text{slow}}$.

(1) If $a = 0$, then the expected extinction time is at most linear in $N$ and in particular there is fast extinction. More precisely, writing $(H)_\delta$ for the hypothesis that $T^{\text{loc}}s^{-\delta}$ is a bounded function, we have

(a) $(H)_1$ is a consequence of (41) and (42).
(b) If $(H)_\delta$ is satisfied for some $\delta \in (0, 1]$, then there is $\omega = \omega(\lambda, \delta)$ such that for all $N$,

$$ \mathbb{E}[T_{\text{ext}}] \le \omega N^{\delta}. \qquad (43) $$

Combining with (a) we have that $\mathbb{E}[T_{\text{ext}}]$ is always at most linear in $N$.

(c) $(H)_0$ is satisfied exactly when $\eta \ge 1/2$, and in that case there is ultra-fast extinction. More precisely, there is $\omega = \omega(\lambda, \delta)$ such that for all $N$,

$$ \mathbb{E}[T_{\text{ext}}] \le \omega \log N. $$

(2) If $a > 0$ then there exists $\omega = \omega(a, \lambda) > 0$ such that, for all large $N$ and all $t \ge 0$,

$$ I_N(t) \le a + \frac{7}{6s(a)} \int_a^1 s(y) \, dy + \frac{\omega}{t} + \frac{1}{N}. \qquad (44) $$

In particular, if there is metastability, then the upper metastable density satisfies

$$ \rho^+(\lambda) \le a(\lambda) + \frac{7}{6s(a(\lambda))} \int_{a(\lambda)}^1 s(y) \, dy. \qquad (45) $$

Note that Theorem 2 in [12] is similar to Theorem 3 here, but it holds only for $\eta \ge 0$, and always requires a condition similar to (41) (with only a different multiplicative constant in the left-hand side of the inequality), irrespectively of whether the vertex is quick or slow. Inequality (41) would actually be the natural inequality to look at if we were considering a model of infection without any underlying graph, where an infected vertex $i$ could infect any other vertex $j$ with the ‘temporal mean rate’ $\lambda p_{ij} \le \lambda p(i/N, j/N)/N$, and could recover at rate $1/(7T_i^{\text{loc}})$ instead of one. It is remarkable that our model can in this sense be upper bounded by a model without any underlying graph, or more precisely where the only manifestation of the underlying geometry lies in the introduction of this ‘local survival time’ $T_i^{\text{loc}}$ at each vertex. The fact that Theorem 2 in [12] only requires a condition like (41) is also an indication that this theorem takes into account adequately the degradation and regeneration effects discussed in the introduction. In a sense, our Theorem 3 generalizes Theorem 2 of [12] with the following additional ingredients:

(i) The local time $T_i^{\text{loc}}$ is appropriately extended to negative values of $\eta$ and thus takes into account the weaker degradation effect for slow evolutions.

(ii) The depletion effect is now taken into account by requiring only Inequality (42) to be satisfied for slow vertices, instead of Inequality (41).

Theorem 3 is quite strong but still has a weakness. For weak vertices with typical degree smaller than $\lambda^{-2}$, we might still have $T_i^{\text{loc}}$ large, which does not reflect well the fact that reinfections should be rare and the local survival effect should be nonexistent.

Theorem 4 below provides a special treatment for these weak vertices. It requires to first distinguish weak and strong vertices, and then distinguish strong quick and strong slow
vertices. More precisely, we define

$$a_{\text{str}} := \sup \left\{ x \in (0, 1], \int_{0}^{1} p(x, y) \, dy > \frac{1}{10\lambda^2} \right\}, \quad (46)$$

$$a_{\text{stsl}} := a_{\text{str}} \wedge a_{\text{slow}}, \quad (47)$$

and say a vertex $j$ is strong slow if $j/N < a_{\text{stsl}}$, strong quick if $a_{\text{stsl}} \le j/N < a_{\text{str}}$ and weak if $a_{\text{str}} \le j/N$. Note there is no strong quick vertex if $a_{\text{stsl}} = a_{\text{str}}$.

**Theorem 4.** There exists a large constant $c$ such that the following holds: Let $\eta \le 0$ and suppose there exists some $a = a(\lambda) > 0$ and some non-increasing function $s: [a, 1] \to [1, \infty)$ such that the following master inequality is satisfied: for all $x > a$,

$$c \int_{0}^{1} \lambda p(x, y) s(y \vee a) \, dy \le s(x) \quad (48)$$

if $x \ge a_{\text{str}}$, or

$$c T^{\text{loc}}(x) \int_{0}^{1} \lambda p(x, y) s(y \vee a) \, dy \le s(x) \quad (49)$$

if $a_{\text{stsl}} \le x < a_{\text{str}}$, or

$$c T^{\text{loc}}(x) \left( \int_{0}^{a_{\text{stsl}}} (\kappa(x) \vee \kappa(y)) p(x, y) s(y \vee a) \, dy + \int_{a_{\text{stsl}}}^{1} \lambda p(x, y) s(y) \, dy \right) \le s(x) \quad (50)$$

if $x < a_{\text{stsl}}$. Suppose also the following technical assumptions are satisfied:

$$(H1) \quad s(a_{\text{str}}) \int_{y<a_{\text{str}}} p(x, y) dy \le s(x) \quad \text{for all } x > a_{\text{str}} \text{ and}$$

$$(H2) \text{ there exists some } \alpha > 0 \text{ and } c_{(51)} > 0 \text{ not depending on } \lambda, \text{ such that}$$

$$s(a_{\text{str}}) \le c_{(51)} \lambda^{-3+\alpha}, \quad (51)$$

$$s(a_{\text{str}}) \le c_{(51)} \lambda^{-1+\alpha} \inf \left\{ \frac{s(x)}{T^{\text{loc}}(x)} : x < a_{\text{str}} \right\}. \quad (52)$$

Suppose finally the functions $a^{-1}$ and $s(a)$ have polynomial growth at 0, in the sense that they are bounded by $\lambda^{-c'}$ when $\lambda \to 0$ for some $c' > 0$. Then, there exists $\omega = \omega(\lambda) > 0$ and $\omega' = \omega'(\lambda) > 0$ such that, for all $N$ and all $t \ge 0$, we have, for small $\lambda$,

$$I_N(t) \le 2a + \frac{4}{3s(a)} \int_a^1 s(y) \, dy + \frac{\omega}{t} + \frac{\omega'}{N}. \quad (53)$$

If there is metastability, we get that the upper metastable density satisfies, for small $\lambda > 0$,

$$\rho^{+}(\lambda) \le 2a(\lambda) + \frac{4}{3s(a(\lambda))} \int_{a(\lambda)}^{1} s(y) \, dy. \quad (54)$$
We postpone the proof of these theorems to Section 5, and check here how they can be used to deduce Propositions 6 and 7. In order to use Theorems 3 and 4, we have to determine a level a and a function s satisfying the hypotheses of the theorems and providing the required upper bounds. The way we do this is led by two complementary principles. First, a purely analytic approach, when the conditions required by Theorems 3 and 4 lead to optimal or natural choices. Second, the comparison of the approach with the lower bounds. In the lower bounds, we were seeking for the largest possible threshold a such that the stars $\mathcal{S} := \{1, \dots, \lflooraN\rfloor\}$ are typically infected in the metastable state. By contrast, in this upper bound section we seek for the smallest possible threshold a such that the contact process shows a subcritical behaviour while infecting only vertices in $\{\lflooraN\rfloor + 1, \dots, N\}$. We thus expect that the a we use in this section to be larger than the a used in the lower bounds section, and our aim is to make them of the same order.

To avoid cluttered notation, we henceforth assume $\beta = 1$ in the definition of the kernels. Recall that $\tau \in (2, \infty)$ and $\gamma \in (0, 1)$ are linked by $\tau = 1 + 1/\gamma$. To shorten computations, we write $f \lesssim g$ if the positive functions $f$ and $g$ of $\lambda$ satisfy that $f/g$ is bounded when $\lambda \to 0$, and similarly $f \gtrsim g$ or $f \asymp g$. We will use repeatedly that $\int_a^b y^{r-1}dy \asymp a^r + b^r$ when the parameter $r$ is different from 0. Of course, when the sign of $r$ is known, only one of the two terms $a^r$ or $b^r$ has to be kept. For simplicity we disregard in our computations the cases involving a parameter $r = 0$. These cases would induce a logarithmic factor coming from the integration of the harmonic function, but this logarithmic factor never concerns the leading term of the quantities we are estimating and can therefore be omitted.

**Application of Theorem 3 to the preferential attachment kernel.** When applying Theorem 3, we actually check (41) for all $x$ irrespectively of whether $x \ge a_{\text{slow}}$ or $x < a_{\text{slow}}$, so as to ease computations<fnref n="1" />. Recall that Proposition 6 assumes $\eta \in (-\frac{1}{2}, 0)$, and under this hypothesis, we have for $c_3 = \frac{1}{1-\gamma} + \frac{1}{\gamma+\gamma\eta}$ and $y \in (0, 1]$,

$$ \pi(y) = \int_0^1 \frac{p(y, z)}{\kappa(y) + \kappa(z)} dz \le c_3 y^{-\gamma}. $$

Introducing $f(x) = s(x)/T^{\text{loc}}(x)$ Inequality (41) is equivalent to $\Delta_a(f)(x) \le f(x)$ for all $x \ge a$, where we have defined the functional $\Delta_a$ by

$$ \Delta_a(f)(x) := 8\lambda \int_0^1 p(x, y) f(y \vee a) T^{\text{loc}}(y \vee a) dy. $$

The assumption $\eta < 0$ yields $T^{\text{loc}}(y) \asymp y^{\gamma\eta} + \lambda^2 y^{-\gamma+\gamma\eta}$. In our pursuit to match the dominant strategies in Section 3.4.2 we now suppose $a(\lambda) \lesssim \lambda^{2/\gamma} \approx a_{ls}$ (where $a_{ls}$ was introduced in Section 3.4.1). With this assumption, when $y = a$ the last estimate simplifies

<footnote n="1">¹Checking instead the less demanding Condition (42) for slow vertices would actually provide slightly better upper bounds, but only in regimes where our optimal upper bound requires Theorem 4 anyway.</footnote>
to $T^{\text{loc}}(a) \asymp \lambda^2 a^{-\gamma+\gamma\eta}$. In case of the preferential attachment kernel we get, for $x \ge a$,

$$ \begin{aligned} \Delta_a(f)(x) \asymp & \lambda x^{\gamma-1} \int_0^a a^{-\gamma} f(a) \lambda^2 a^{-\gamma+\gamma\eta} dy \\ & + \lambda x^{\gamma-1} \int_a^x y^{-\gamma} f(y) (y^{\gamma\eta} + \lambda^2 y^{-\gamma+\gamma\eta}) dy \\ & + \lambda x^{-\gamma} \int_x^1 y^{\gamma-1} f(y) (y^{\gamma\eta} + \lambda^2 y^{-\gamma+\gamma\eta}) dy. \end{aligned} $$

Searching for a monomial $f(x) = x^\alpha$ with $\alpha < 0$, and assuming for simplicity that none of the four exponents $1 - \gamma + \alpha + \gamma\eta$, $1 - 2\gamma + \alpha + \gamma\eta$, $\gamma + \alpha + \gamma\eta$, or $\alpha + \gamma\eta$, equals 0, we get

$$ \Delta_a(f)(x) \sim \lambda x^{\alpha+\gamma\eta} + \lambda^3 x^{\alpha-\gamma+\gamma\eta} + \lambda^3 x^{\gamma-1} a^{\alpha+1-2\gamma+\gamma\eta} + \lambda x^{-\gamma}. $$

For $\Delta_a(f)(x) \le f(x)$ to hold for all $x \ge a$, we need

$$ (i) \lambda \lesssim a^{-\gamma\eta}, \quad (ii) \lambda^3 \lesssim a^{\gamma(1-\eta)}, \quad (iii) \lambda^3 \lesssim a^{2\gamma-1-\alpha-\gamma\eta}, $$

$$ (iv) \lambda \lesssim a^{\alpha+\gamma}, \quad (v) \lambda^4 \lesssim a^{3\gamma-1-\gamma\eta}. $$

Here (v) is just a consequence of (iii) and (iv). (i), (ii) and (v) do not depend on $\alpha$, and prevent us from choosing $a$ too small. We now consider the different cases.

(1) The case $-\frac{1}{2} < \eta \le 0$ and $\tau > \frac{8}{3} + \frac{\eta}{3}$.

This is the delayed direct spreading phase, where (i) and (v) are less restrictive than (ii), leading naturally to the choice (with $r$ some constant to be defined later)

$$ a(\lambda) = r \lambda^{\frac{3}{\gamma(1-\eta)}}. $$

(iii) requires $\alpha \ge \gamma - 1$, while (iv) requires $\alpha \ge \frac{\gamma}{3}(\eta - 2)$ which is less restrictive under our assumptions, so we choose $\alpha = \gamma - 1$, as (45) will then give the best possible upper bound for the upper metastable density. It is now a simple verification that choosing $r$ large enough indeed ensures (41) is satisfied for small $\lambda > 0$. Then (45) yields

$$ \rho^{+}(\lambda) \lesssim \frac{1}{s(a(\lambda))} \lesssim \frac{1}{a^{\gamma-1} \lambda^2 a^{-\gamma+\gamma\eta}} \lesssim \lambda^{\frac{3-2\gamma-\gamma\eta}{\gamma-\gamma\eta}} = \lambda^{\frac{3\tau-5-\eta}{1-\eta}}. $$

(2) The case $-\frac{1}{2} < \eta \le 0$ and $2 - \eta \le \tau \le \frac{8}{3} + \frac{\eta}{3}$.

This is the delayed indirect spreading phase, where (i) and (ii) are less restrictive than (v), leading naturally to the choice (with $r$ some constant to be defined later)

$$ a(\lambda) = r \lambda^{\frac{4}{\gamma(3-\eta)-1}}, $$

(iii) and (iv) is more restrictive than (iii), thus leading to the choice $\alpha = -\frac{\gamma+\gamma\eta+1}{4}$. Choosing $r$ large we see that (41) is satisfied for small $\lambda > 0$. Furthermore $a \lesssim \lambda^{2/\gamma}$ holds as $\gamma < \frac{1}{1-\eta}$. Finally, (45) yields

$$ \rho^{+}(\lambda) \lesssim \lambda^{\frac{3-\gamma-\gamma\eta}{3\gamma-\gamma\eta-1}} = \lambda^{\frac{3\tau-4-\eta}{4-\eta-\tau}}. $$
**Application of Theorem 3 to the factor kernel.** As discussed previously, for the factor kernel we use Theorem 3 to prove the upper bounds in Proposition 6 only in the cases (a),(i) and (ii), so we either assume $\frac{5}{2} - \eta \le \tau < 4 + 2\eta$ or $4 - \eta < \tau$. As in the previous analysis we check for Condition (41). Replacing $p(x, y) = x^{-\gamma}y^{-\gamma}$, the left side of this inequality factorizes as $D_a T^{\text{loc}}(x)x^{-\gamma}$, where $D_a$ does not depend on $x$ and is given by

$$D_a := 8\lambda \int_0^1 y^{-\gamma} s(a \lor y) dy.$$

It is thus natural to choose the scoring function $s(x) = T^{\text{loc}}(x)x^{-\gamma}$, so that (41) becomes equivalent to $D_a \le 1$. From our assumptions we have $2 - \eta < \tau$, so that $\pi(x) = O(x^{-\gamma})$ and we get

$$D_a \lesssim \lambda + \lambda a^{1-2\gamma+\gamma\eta} + \lambda^3 a^{1-3\gamma+\gamma\eta}, \quad (55)$$

assuming for simplicity that the exponents $1 - 2\gamma + \gamma\eta$ and $1 - 3\gamma + \gamma\eta$ are nonzero. To discuss which values of $a$ can make $D_a$ smaller than 1, we consider different cases.

### (1) The case $\tau > 4 - \eta$.

In this case the two exponents on the right-hand side of (55) are positive so we have $D_0 \lesssim c\lambda$ with finite $c$, and in particular (41) is satisfied for $a = 0$ and $\lambda \le 1/c$, yielding fast extinction. Moreover, the reader might check that the hypothesis $(H)_\delta$ is satisfied for $\delta \ge \frac{1-\eta}{2-\eta}$. It follows that, for $\lambda \le 1/c$, the expected extinction time is at most $\omega N^{\frac{1-\eta}{2-\eta}}$, for some $\omega = \omega(\lambda) < \infty$.

### (2) The case $\tau = 4 - \eta$.

We get $D_a \sim \lambda + \lambda^3 \log(1/a)$ and so $D_a \le 1$ for $a(\lambda) = e^{-r\lambda^{-3}}$, for well-chosen $r$ and $\lambda$ small. Thus we get an exponentially small upper bound for the upper metastable density.

### (3) The case $\frac{5}{2} - \eta \le \tau \le 4 + 2\eta$.

In this region, the largest term of (55) is $\lambda^3 a^{1-3\gamma+\gamma\eta}$ so we get $D_a \le 1$ for small $\lambda$ by taking $a(\lambda) = r\lambda^{\frac{3\gamma-1-\gamma\eta}{3\gamma-1-\gamma\eta}}$, for a well-chosen $r$. (45) then gives us the upper bound for the upper metastable density as

$$\rho^+(\lambda) \lesssim a(\lambda) + \frac{1}{s(a(\lambda))} \int_{a(\lambda)}^1 s(y) dy \lesssim \frac{1}{s(a(\lambda))} \lesssim \lambda^{\frac{2-\gamma\eta}{3\gamma-1-\gamma\eta}} = \lambda^{\frac{2\tau-2-\eta}{4-\tau-\eta}}.$$

Notice that this bound is available in the full region $\frac{5}{2} - \eta \le \tau < 4 - \eta$, yet it does not match the lower bounds obtained in Section 3.4.1 when $4 + 2\eta \le \tau < 4 - \eta$. In the next section we use Theorem 4 to obtain the matching upper bounds we are missing here.

**Application of Theorem 4 to the factor kernel.** We consider the vertex updating model for the factor kernel $p(x, y) = x^{-\gamma}y^{-\gamma}$ in the region delimited by the inequalities $\tau > 3$, $\tau > 4 + 2\eta$, $\tau > 2 - \eta$ and $\tau < 4 - \eta$. The inequality $\tau > 2 - \eta$ implies $\pi(x) \asymp x^{-\gamma}$. We also have $a_{\text{str}} \asymp \lambda^{2/\gamma}$. For $\eta > -1/2$, we have $a_{\text{stsl}} \asymp \lambda^{1-\gamma\eta} < a_{\text{str}}$ while for $\eta < -1/2$, we have $a_{\text{stsl}} = a_{\text{str}} \asymp \lambda^{2/\gamma}$. We now search for some $a < a_{\text{stsl}}$ and function $s$ satisfying
Conditions (48), (49) and (50) as well as the Hypotheses (H1) and (H2). Let us introduce $A_1$, $A_2$ and $A_3$ the following integrals over the function $s$:

$$A_1 = \int_0^{a_{\text{stsl}}} \lambda y^{-\gamma} s(y \vee a) dy, \quad A_2 = \int_0^{a_{\text{stsl}}} \kappa(y) y^{-\gamma} s(y \vee a) dy, \quad A_3 = \int_{a_{\text{stsl}}}^1 \lambda y^{-\gamma} s(y) dy.$$

Recalling the form of the factor kernel $p(x, y) = x^{-\gamma}y^{-\gamma}$ and bounding the max $\kappa(x) \wedge \kappa(y)$ by the sum, we see that the inequalities (48), (49) and (50) are guaranteed by

$$c(A_1 + A_3) x^{-\gamma} \leq s(x), \quad \text{for } x \geq a_{\text{str}},$$

$$c(A_1 + A_3) x^{-\gamma} T^{\text{loc}}(x) \leq s(x), \quad \text{for } a_{\text{stsl}} \leq x < a_{\text{str}},$$

$$c\left(\frac{\kappa(x)}{\lambda} A_1 + A_2 + A_3\right) x^{-\gamma} T^{\text{loc}}(x) \leq s(x), \quad \text{for } x < a_{\text{stsl}}.$$

A natural choice for the scoring function $s$ is then given by

$$s(x) = \begin{cases} x^{-\gamma} & \text{for } x \geq a_{\text{str}} \\ x^{-\gamma} T^{\text{loc}}(x) & \text{for } a_{\text{stsl}} \leq x < a_{\text{str}} \\ \frac{\kappa(x)}{\lambda} x^{-\gamma} T^{\text{loc}}(x) + \rho x^{-\gamma} T^{\text{loc}}(x) & \text{for } x < a_{\text{stsl}}, \end{cases}$$

leading naturally to the requests

$$\begin{cases} c(A_1 + A_3) \leq 1, \\ c(A_2 + A_3) \leq \rho, \end{cases}$$

which in turn are implied by the three requests

$$A_1 \leq \frac{1}{2c}, \quad A_2 \leq \frac{\rho}{2c}, \quad A_3 \leq \frac{1 \wedge \rho}{2c}.$$

Before computing these terms, we check that the hypotheses (H1) and (H2) are satisfied with this choice of scoring function. The hypothesis (H1) is equivalent to

$$a_{\text{str}}^{-\gamma} \int_{0}^{a_{\text{str}}} x^{-\gamma} y^{-\gamma} dy \leq x^{-\gamma}, \quad \text{for } x > a_{\text{str}},$$

which is in turn equivalent to $a_{\text{str}}^{1-2\gamma}/(1-\gamma) \leq 1$, and is satisfied for small $\lambda$ as we lie in the phase $\tau > 3$ or equivalently $\gamma < 1/2$. Furthermore, we have

$$s(a_{\text{str}}) = a_{\text{str}}^{-\gamma} \asymp \lambda^{-2},$$

so the first part of the hypothesis (H2) is satisfied, with $\alpha = 1$. We will check the second part of the hypothesis (H2) later on, while we now bound the terms $A_1$ to $A_3$, up to multiplicative constants depending only on $\gamma$ and $\eta$. First, observe that since $a_{\text{stsl}} \leq a_{\text{str}}$ we have that $T^{\text{loc}}(x) \asymp \lambda^2 x^{-\gamma+\gamma\eta}$, for $x < a_{\text{stsl}}$, and hence by our choice of $s$ and the definition of $a_{\text{stsl}}$,

$$\begin{aligned} A_1 &\asymp \lambda a^{1-\gamma} s(a) + \rho \int_a^{a_{\text{stsl}}} \lambda^3 y^{-3\gamma+\gamma\eta} dy + \int_a^{a_{\text{stsl}}} \lambda^2 y^{-3\gamma} dy \\ &\asymp \rho \lambda^3 a^{1-3\gamma+\gamma\eta} + \lambda^2 a^{1-3\gamma} + \lambda^2 a_{\text{stsl}}^{1-3\gamma}, \end{aligned}$$

using that $1-3\gamma+\gamma\eta = (\tau-4+\eta)\gamma < 0$ for $\tau < 4-\eta$, and assuming for simplicity $1-3\gamma \neq 0$.
When $\eta \ge -1/2$, we have $a_{\text{stsl}} \asymp \lambda^{-1/\gamma\eta}$ and therefore we get that $\lambda^2 a_{\text{stsl}}^{1-3\gamma} \asymp \lambda^{\frac{\tau-4-2\eta}{-\eta}}$, and this term tends to 0 as $\lambda$ tends to 0 as $\tau > 4 + 2\eta$. When $\eta < -1/2$, we have $a_{\text{stsl}} \asymp \lambda^{2/\gamma}$ and thus the term $\lambda^2 a_{\text{stsl}}^{1-3\gamma} \asymp \lambda^{2\tau-6}$ also goes to 0 as $\tau > 3$. Thus, to guarantee the inequality $A_1 \le 1/2c$ for small $\lambda$, it suffices to satisfy the following requests:

$$ \lambda^2 a^{1-3\gamma} \lesssim 1, \qquad (56) $$

$$ \lambda^3 a^{1-3\gamma+\gamma\eta} \lesssim 1/\rho, \qquad (57) $$

with an abuse of notation, as for these requests to make sense, the involved multiplicative constants should be specified. In other words, the request $\lesssim 1$ should be understood as $\le c(\gamma, \eta)$, where $c(\gamma, \eta) > 0$ is some constant which may change from one inequality to the other, and which could be made explicit if necessary.

Similarly, we obtain

$$ A_2 \asymp \rho(\lambda^2 a^{1-3\gamma} + \lambda^2 a_{\text{stsl}}^{1-3\gamma}) + (\lambda a^{1-3\gamma-\gamma\eta} + \lambda a_{\text{stsl}}^{1-3\gamma-\gamma\eta}), $$

leading to the requests (56) and (57) again, as well as the additional requests

$$ \lambda a^{1-3\gamma-\gamma\eta} + \lambda a_{\text{stsl}}^{1-3\gamma-\gamma\eta} \lesssim \rho. \qquad (58) $$

To bound $A_3$, we first treat the case $\eta < -1/2$ for which $A_3 = \lambda \int_{a_{\text{stsl}}}^1 y^{-2\gamma} dy \asymp \lambda$ as we have $\tau > 3$ or equivalently $\gamma < 1/2$. In the case $\eta > -1/2$, we obtain

$$ \begin{aligned} A_3 &\asymp \lambda + (1 + \rho)\lambda^3 a_{\text{stsl}}^{1-3\gamma+\gamma\eta} \\ &\asymp \lambda + (1 + \rho)\lambda a_{\text{stsl}}^{1-3\gamma-\gamma\eta}, \end{aligned} $$

using the value of $a_{\text{stsl}}$ in that case. Assuming further $\rho \le 1$, the original request for $A_3$ now reads

$$ \lambda + \lambda a_{\text{stsl}}^{1-3\gamma-\gamma\eta} \lesssim \rho $$

where the bound on $\lambda a_{\text{stsl}}^{1-3\gamma-\gamma\eta}$ already follows from (58) and thus we only require

$$ \lambda \lesssim \rho. \qquad (59) $$

Thus far we have several requests, namely, (56), (57), (58), and (59). In order to make these inequalities independent of $\rho$ we combine (59) with inequality (57), obtaining

$$ \lambda^4 a^{1-3\gamma+\gamma\eta} \lesssim 1, \qquad (60) $$

and also combine inequalities (57) and (58), which gives

$$ \lambda^4 a^{2-6\gamma} \lesssim 1, $$

$$ \lambda^4 a^{1-3\gamma+\gamma\eta} a_{\text{stsl}}^{1-3\gamma-\gamma\eta} \lesssim 1. $$

These last two inequalities are redundant with (56) and (60); the first of these requests amounts to (56), while the second is less restrictive than either (56) or (60) depending on the sign of $1 - 3\gamma - \gamma\eta$ (using the fact that $a \le a_{\text{stsl}}$).
We are thus left with the two main requests (56) and (60). The other requests only yield restrictions on the choice of $\rho$, which we should check are compatible with $\rho \le 1$. Which of (56) or (60) is the most demanding depends on whether $\tau$ is larger or smaller than $4+\eta$, and we now treat these two cases.

• $\tau < 4 + \eta$. In that case the most restrictive request is (56), leading to the choice

$$a \asymp \lambda^{\frac{2}{3\gamma-1}}.$$

Moreover, $\rho$ should satisfy

$$\lambda \lesssim \rho \lesssim \lambda^{-3} a^{-1+3\gamma+\gamma\eta} \asymp \lambda^{\frac{\tau-4-2\eta}{4-\tau}} \asymp \lambda^{1-2\frac{4+\eta-\tau}{4-\tau}}.$$

In particular, the choice $\rho \asymp \lambda^{1-2\frac{4+\eta-\tau}{4-\tau}}$ allows to satisfy the second part of (H2) with $\alpha = 2\frac{4-\tau+\eta}{4-\tau} \in (0,2)$. Pushing further the computations we get

$$\frac{1}{s(a)} \int_a^1 s(y) dy \asymp \frac{1}{s(a(\lambda))} \asymp \lambda^{\frac{\tau}{4-\tau}}.$$

We thus obtain an upper bound for the metastable density as

$$\rho^+(\lambda) \lesssim \lambda^{\frac{\tau}{4-\tau}}.$$

• $\tau \ge 4 + \eta$. In that case the most restrictive request is (60), leading to the choice

$$a \asymp \lambda^{\frac{4}{3\gamma-1-\gamma\eta}}$$

In that case we have $\rho \asymp \lambda$, which does not allow to satisfy the hypothesis (H2) for $\alpha > 0$. The first term in the definition of $s(x)$ gives another bound, but this also does not always allows to satisfy (H2). However, we can modify slightly the definition of $s(x)$ so that (H2) is satisfied, by adding the term $\lambda^{1-\alpha} a_{\text{str}}^{-\gamma} T^{\text{loc}}(x)$ when $x < a_{\text{str}}$, for some $\alpha > 0$, which makes (H2) automatically satisfied. This new term changes the values of the integrals by adding new terms $A'_1, A'_2$ and $A'_3$ to the previous ones, however the new inequalities that we request remain almost unchanged

$$\begin{cases} \mathfrak{c}((A_1 + A'_1) + (A_3 + A'_3)) \le 1 \\ \mathfrak{c}((A_2 + A'_2) + (A_3 + A'_3)) \le \lambda, \end{cases}$$

since it is enough to satisfy the inequalities for the previous score function (because the new one is bigger). We thus obtain the additional requests $A'_1 \lesssim 1$ and $A'_2, A'_3 \lesssim \lambda$. Computing the integrals yields

$$\begin{aligned} A'_1 &\asymp \lambda^{4-\alpha} a_{\text{str}}^{-\gamma} \left( a^{1-2\gamma+\gamma\eta} + a_{\text{stsl}}^{1-2\gamma+\gamma\eta} \right) \\ &\asymp \lambda^{2-\alpha} \left( a^{1-2\gamma+\gamma\eta} + a_{\text{stsl}}^{1-2\gamma+\gamma\eta} \right). \end{aligned}$$

By the value of $a$, the first term is $\lambda$ to the power $\frac{2(\tau-2+\eta)}{4-\tau-\eta} - \alpha$, leading to the condition $\alpha < \frac{2(\tau-2+\eta)}{4-\tau-\eta}$. For the second term, we split the analysis between the case $\eta \ge -1/2$,
with $a_{\text{stsl}} \asymp \lambda^{-1/\gamma\eta}$, leading to $\alpha < \frac{\tau-3-\eta}{-\eta}$, and the case $\eta < -1/2$, with $a_{\text{str}} \asymp \lambda^{2/\gamma}$, leading to the request $\alpha < 2(\tau - 2 + \eta)$. Similarly, we compute

$$A_2' \asymp \lambda^{3-\alpha} a_{\text{str}}^{-\gamma} a_{\text{stsl}}^{1-2\gamma} \asymp \lambda^{1-\alpha} a_{\text{stsl}}^{1-2\gamma}.$$

Splitting again the analysis in the two cases $\eta \ge -1/2$ and $\eta < -1/2$, we see that the request $A_2' \lesssim \lambda$ is guaranteed by asking $\alpha < \frac{\tau-3}{-\eta}$ in the first case, and $\alpha < 2(\tau - 3)$ in the second case.

Finally, the term $A_3'$ is present only in the case $\eta > -1/2$, where $a_{\text{str}} > a_{\text{stsl}} \asymp \lambda^{1/\gamma\eta}$, and we then have

$$A_3' \asymp \lambda^{2-\alpha} a_{\text{stsl}}^{1-2\gamma+\gamma\eta} \asymp \lambda^{1-\alpha} a_{\text{stsl}}^{1-2\gamma} \asymp A_2'$$

thus not leading to any further request. There is now no difficulty choosing $\alpha > 0$ small satisfying all the requests, and pushing further the computations we then get

$$\frac{1}{s(a)} \int_a^1 s(y) dy \asymp \frac{1}{s(a(\lambda))} \asymp \lambda^{\frac{3\tau-4-\eta}{4-\tau-\eta}}.$$

We thus obtain an upper bound for the metastable density as $\rho^+(\lambda) \lesssim \lambda^{\frac{3\tau-4-\eta}{4-\tau-\eta}}$.

## 5. PROOF OF THEOREMS 3 AND 4

### 5.1. Proof of Theorem 3.
We now provide the proof of Theorem 3, using settings and notations that will be reusable in the proof of Theorem 4. In particular, we rewrite (41) as

$$c \, T^{\text{loc}}(x) \int_0^1 \lambda p(x, y) s(y \vee a) \, dy \le s(x)$$

with of course $c = 7$, and similarly for (42). We suppose $a(\lambda)$ and $s(x)$ are given satisfying the hypotheses of Theorem 3. When $a > 0$, we extend $s$ to $(0, 1]$ by $s(x) = s(x \vee a)$. The theorem also involves other functions defined on $(0, 1]$, namely $\kappa$, $\pi$ and $T^{\text{loc}}$. We use the subscript notation when considering the corresponding functions defined on $\{1, \dots, N\}$, so $\kappa_j = \kappa(j/N)$, $\pi_j = \pi(j/N)$, $T_j^{\text{loc}} = T^{\text{loc}}(j/N)$, and $s_j = s(j/N)$. Recall the notation $p_{i,j} = \frac{1}{N} p(i/N, j/N) \wedge 1$.

The fact that $(H)_1$ follows from (41) and (42) (when $a = 0$) is immediate as then, using the monotonicity of $p$,

$$\frac{s(x)}{T^{\text{loc}}(x)} \ge c \int_0^1 (\lambda \wedge \kappa(y)) p(1, y) s(y \vee a) \, dy > 0.$$

Moreover, $(H)_0$ is satisfied when $\eta \ge 1/2$ since

$$\frac{\pi(x)}{\kappa(x)} \le \frac{1}{\kappa(x)^2} \int_0^1 p(x, y) dy \le \frac{c_2}{\kappa_0^2} x^{-\gamma+2\gamma\eta},$$

where the second inequality follows from (1). Using again (1) we deduce that for $\eta < 1/2$ it cannot hold since

$$\frac{\pi(x)}{\kappa(x)} \ge \frac{c_1 x^{-\gamma}}{2\kappa(x)(\kappa(x) + \min(\kappa(y), y \in [1/2, 1]))}.$$
If $a > 0$ we call the vertices $j < aN$ stars. The proof attaches a score to a configuration that behaves as a supermartingale as long as no star gets infected. We stop the process when infecting a star, thus before any edge between stars can be used to transmit the infection. It is convenient and clearer to consider in the following that there are simply no edges between stars, for example by redefining $p_{ij} = 0$ when $i$ and $j$ are stars.

Recall the definition of slow vertices just before Theorem 3, and in particular the definition of $a_{\text{slow}}$ in (40). In Theorem 3, the request (42) seems to indicate that the infection propagates between slow vertices at rate $\kappa(x) \lor \kappa(y)$ instead of $\lambda$, which amounts to take into account the depletion effect, and is a significant difficulty in this theorem. We say an edge $\{i, j\}$ (not necessarily in $G$) is slow if $i$ and $j$ are both slow vertices, otherwise we refer to the edge as quick. So a slow edge updates at a rate bounded by $2\lambda$, and a quick edge at rate at least $\lambda$. In the following, we suppose $a < a_{\text{slow}}$. When this does not hold, the proof still works and is actually easier as there are no slow edges.

The proof relies on the following ideas, introducing a modification of the entire process (which alters the underlying network, its dynamics and the evolution of the infection) which constitutes a stochastic upper bound:

* For the new underlying network keep the original set of vertices $\{1, \dots, N\}$, maintaining their previous classification as either slow or quick, as well as the definition of stars. We also maintain all quick edges, consisting of edges with at least one quick vertex as an endpoint.

* As for the remaining edges (between slow vertices), we replace them with their directed versions so for each pair $i, j$ of slow vertices we consider $(i, j)$ and $(j, i)$ as possible edges of the network (even at the same time) instead of $\{i, j\}$.

* Each vertex $i$ still updates at rate $\kappa_i$, however updatings affect the edges differently according to their type. At this point it is enough to keep in mind that updatings maintain the role of losing the local neighbourhood of vertices.

* The new process is still a contact process at its core, where each vertex is classified as either healthy or infected, and can be infected, recover, and be reinfected. Vertices recover at rate 1 independently from one another as in the original process, however the rate at which the infection is transmitted along each edge is more intricate.

* A new addition to the process is that we also subclassify infected vertices as *saturated* and *unsaturated*. The reader might think of a vertex as saturated whenever it is surrounded by many neighbours (or maybe just powerful ones), likely to reinfect it after its recovery. For this reason for saturated vertices we just negate recoveries altogether, and hence these become beacons of infection that *cannot recover*. In order for saturated vertices to disappear they have to first update and observe a more favourable environment to become unsaturated, and thus be available for recovery. The different conditions that result in saturation will be given gradually as we explain below the evolution of the process.
• We begin by describing first the rules affecting slow vertices and slow (directed) edges, see Figure 2 for an example. By definition, for the original process the subnetwork of slow vertices evolves at a slower pace than the contact process and hence is seen as almost static by the infection, which explores it as it spreads. We adopt the point of view of the infection and thus classify slow edges as either *unrevealed*, *present* or, *absent* (all mutually exclusive). A fourth label, *saturated*, will be helpful when dealing with saturated vertices, but we leave the intuition behind this label for later. Slow edges can change their labels through updates or infections of slow vertices:

- Every slow vertex $i$ updates at rate $\kappa_i$, and upon updating a two-step mechanism occurs:

* First, all slow edges $(i, j)$ and $(j, i)$ become unrevealed regardless of their previous status.

* Next, if $i$ is infected at the time of the update, we *resample* each edge $(i, j)$, declaring it *present* or *absent* by tossing a coin with probability $p_{i,j}$, independently from all other edges. We do the same for each edge $(j, i)$ for which $j$ is infected at the time of the update.

- If a slow vertex $i$ becomes infected, we *resample* each unrevealed edge $(i, j)$ leaving $i$ in the same manner as before. Observe that this procedure does not affect already revealed edges.

<figure><img src="image_4.png" /><figcaption>FIGURE 2. Left: Four slow vertices, of which the top and right ones are infected. Unrevealed edges are represented as dotted, present as solid, and absent are not drawn. In the picture the edges leaving the infected vertices, marked as shaded, have been revealed. Centre: The vertex on the right has recovered but no updatings have occurred so the information about edges is kept. Right: The vertex on the right has updated making all the edges leaving it unrevealed. Observe that the edge going from the top vertex to the right one also updates since the top vertex is infected, but it is immediately revealed again, flipping a coin to decide its status which in this case turns to be absent.</figcaption></figure>

• Slow vertices recover at rate 1 (unless saturated) and transmit the infection through present edges at rate $\lambda$ (regardless of the state of the receiving vertex). If an infection is sent through the present edge $(i, j)$, then
- both vertices $i$ and $j$ become instantly saturated;

- the edges $(i, j)$ and $(j, i)$ become saturated, regardless of their previous state.

See Figure 3 for an example. The reason why this infection leads to saturation is that for a slow vertex $i$ we have $T^{\text{loc}}(i/N) \ge 8/3\kappa_i \ge 8/3\lambda$, which fits the intuition that both $i$ and $j$ are likely to have enough time to infect each other if the edge $(i, j)$ is present. Contrary to the intuition given for vertices, the saturation of an edge means that it becomes useless for the infection, since we know that both vertices are saturated and hence constantly infected. It will be important later that when referring to present edges we are not including saturated ones for this same reason.

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

If $i$ becomes infected and $j$ is not, we reveal the edge $(i, j)$, which in this case is absent. We keep the edge $(j, i)$ unrevealed.

If $j$ gets infected by a third vertex, we reveal the edge $(j, i)$, which in this case is present.

An infection occured along $(j, i)$. Both vertices and both edges are now saturated. Only an update of $i$ or $j$ will change this situation.

<caption>FIGURE 3. Dynamics of the slow edges $(i, j)$ and $(j, i)$.</caption>

* For any given slow vertex $i$ define $N_i^{\text{pr}}(t)$ as the number of present edges leaving $i$ at time $t$. If at any given time it satisfies

$$N_i^{\text{pr}}(t) \ge \frac{3\kappa_i T_i^{\text{loc}}}{8\lambda},$$

then we declare vertex $i$ to be saturated. Observe that when a vertex is healthy, the number of present edges leaving it can only decrease so at any time in which the condition is met, $i$ must be necessarily infected. We remind the reader that a saturated vertex can only stop being saturated by updating, so dropping $N_i^{\text{pr}}(t)$ below $\frac{3\kappa_i T_i^{\text{loc}}}{8\lambda}$ by the updating of its neighbours is irrelevant. Intuitively, this condition entails that $i$ is anyway very likely to quickly transmit an infection to another slow vertex, thus leading to saturation by the previous rule.

* When a slow vertex $i$ updates while infected, we sample freshly the slow edges leaving it and thus observe a totally new value for $N_i^{\text{pr}}(t)$. Irrespectively of whether $i$ was saturated or unsaturated before the update, the vertex $i$ will be saturated after the update only if the new value of $N_i^{\text{pr}}(t)$ is too large, however this happens with probability bounded, using the Markov inequality, by

$$\frac{8\lambda}{3\kappa_i T_i^{\text{loc}}} \sum_{j \le a_{\text{slow}}N} p_{ij} \le \frac{1}{6\lambda\pi_i} \int_0^{a_{\text{slow}}} p(i/N, z) dz \le \frac{1}{3}, \quad (61)$$
where the first inequality comes from the definition of $T_i^{\text{loc}}$ and the second from that of $\pi_i$, together with the fact that the updating rate of a slow edge is bounded by $2\lambda$.

* We now describe the rules affecting quick edges, for which we use the wait-and-see coupling introduced in [12, Section 5.1] where each such edge is treated as a possible channel for the infection, irrespectively of whether the edge belongs to the original network or not. Instead of thinking of quick edges as absent or present we classify them as clogged or clear. A clogged edge $\{i, j\}$ transmits the infection at the reduced rate $\lambda p_{i,j}$ (as long as either i or j is infected), and if this happens the edge is cleared. A clear edge then transmits the infection at the regular rate $\lambda$. Note that if the vertices i and j are infected and the edge is clogged, we still count an infection along the edge at rate $\lambda p_{i,j}$, with the only effect of clearing the edge. The reduced rate associated to clogged edges reflects the fact that the edge is likely to be absent from the original network. We refer to [12, Section 5.1] to justify that we get an upper bound for the original process. Observe that only quick edges can be clogged or clear whereas only slow edges can be unrevealed, present, absent or saturated.

<table><caption>TABLE 3. Infection rate along an edge, depending on its state.</caption><thead><tr><th>Type of edge</th><th colspan="2">Quick</th><th colspan="3">Slow</th></tr><tr><th>State of edge</th><th>clogged</th><th>clear</th><th>unrevealed</th><th>absent</th><th>present</th><th>saturated</th></tr></thead><tbody><tr><th>Infection rate</th><td>λp<sub>i,j</sub></td><td>λ</td><td>✓</td><td>0</td><td>λ</td><td>✓</td></tr></tbody></table>

* Recall that quick edges can be adjacent to both slow and quick vertices i, the latter also updating at rate $\kappa_i$. When a vertex i updates, all quick edges $\{i, j\}$ become clogged irrespectively of their previous status.

* For every quick edge $\{i, j\}$ define $R_{ij} = \lambda/(\kappa_i + \kappa_j)$ and for any vertex i (quick or slow) define

$$R_i(t) := \sum_{\{i,j\} \text{ clear}} R_{ij},$$

which is an upper bound for the probability that one of the clear edges incident to i transmits an infection to i before being updated. If at any given time, vertex i satisfies $R_i(t) \ge 1/4$, then we declare it to be saturated. Observe that quick edges can only become clear through the spread of an infection, thus at the time in which $R_i(t) \ge 1/4$ vertex i is necessarily infected. Commonly, the number of infected neighbours of i is a fraction of $R_i$ and hence a vertex, which is saturated due to this condition, would be very likely reinfected after a recovery.

* At time $t = 0$ the initial configuration of the process is constructed as follows:

- First, declare the set of vertices that are infected. Also, set each quick edge as clogged and each slow edge as unrevealed.

- Next, update each slow vertex through the two-step mechanism described above. This reveals all slow edges leaving slow infected vertices, while maintaining all other slow edges unrevealed.
The fact that this new process is a stochastic upper bound of the original contact process can be proved similarly to what was done in [12, Section 5.1], together with Lemma 3 below, and observing that saturated vertices cannot recover, and whenever a slow edge $(i, j)$ is used to spread the infection, both $(i, j)$ and $(j, i)$ become saturated, and thus can be thought as belonging to the network.

**Lemma 3.** Suppose $p \in [0, 1]$, $G = (V, E)$ is a finite graph, and $e \in \mathcal{P}_2(V)\setminus E$ an edge not present in the graph. Let $G^{e,p}$ and $\bar{G}^{e,p}$ be two random graphs such that:

* $G^{e,p}$ is obtained from $G$ by adding edge $e$ with probability $p$.

* $\bar{G}^{e,p}$ is obtained from $G$ by adding independently<fnref n="2" /> the directed edge $\vec{e}$ as well as its reverse edge $\overleftarrow{e}$ with probability $p$.

Writing $G^e = (V, E \cup \{e\})$, we thus have $\mathbb{P}(G^{e,p} = G^e) = p$. The contact process on $G^{e,p}$ is then stochastically dominated by the contact process on $\bar{G}^{e,p}$ where, the first time an infection is transmitted along edge $\vec{e}$ or $\overleftarrow{e}$, the graph is instantly replaced by $G^e$.

*Proof.* Consider the contact process on $G^e$, but at the first time the edge $e$ is used to transmit the infection, with probability $1-p$ the infection and the edge $e$ are deleted. We get the contact process on $G^{e,p}$ (with the presence of $e$ in the graph not being revealed at once). If the infection (in $G^e$) was transmitted in the direction of $\vec{e}$ (resp. $\overleftarrow{e}$), we couple the choice of keeping $e$ in $G^{e,p}$ with that of keeping $\vec{e}$ (resp. $\overleftarrow{e}$) in $\bar{G}^{e,p}$. Then, the first infection using $e$ in $G^{e,p}$ (if $G^{e,p} = G^e$) is an infection in $\bar{G}^{e,p}$. The lemma follows. □

We are now ready to define the score associated to a given configuration of the new process: Let $s$ be the function given in the hypothesis of the theorem and define

$$t(x) = \frac{s(x)}{r\kappa(x)T^{\text{loc}}(x)}, \qquad (62)$$

as well as $t_j = t(j/N)$, with the constant $r$ being defined<fnref n="3" /> by $r = 3/2$. Since $T_i^{\text{loc}} \le 8$ and $T_i^{\text{loc}} \le \frac{8}{3\kappa_i}$ we obtain the following bounds which will be used extensively throughout this section:

$$t_j \le \frac{3s_j}{8r} = \frac{s_j}{4}, \quad \text{and} \quad \kappa_i t_i \le \frac{T_i^{\text{loc}}}{8} = \frac{s_i}{8r}. \qquad (63)$$

Define

$$m_j(t) := \begin{cases} s_j + t_j & \text{if } j \text{ is infected saturated,} \\ s_j + 4R_j(t)t_j & \text{if } j \text{ is infected unsaturated,} \\ 2R_j(t)(s_j + t_j) & \text{if } j \text{ is healthy.} \end{cases}$$

The score associated to the configuration is then

$$M_t := \sum_i m_i(t) + \sum_{(i,j) \text{ present edge}} s_j + t_j + u_j, \qquad (64)$$

<footnote n="2">²The lemma stays true without this independence property, and this assumption is not used in the proof.</footnote>

<footnote n="3">³The proof of Theorem 4 will use again the same notation but with a different value for $r$, which is why we do not use that $r = 3/2$ up until the end of the proof.</footnote>
where $u_j = t_j/3$. We refer to the first term on the right-hand side of (64) as the vertex score, whereas we refer to the second term as the edge score. We now discuss the idea behind this score and some computations involved:

* Each vertex $j$ is associated to a score $m_j(t)$ that depends on its current state (healthy, infected unsaturated, infected saturated), on the quick edges $\{j, k\}$ and on the slow edges $(j, k)$ leaving $j$. Each present slow edge $(i, j)$ entering $j$ is also associated to a score, that reflects the fact that $i$ is likely to later infect $j$. No score is associated to other slow or quick edges and in particular no score is associated to saturated edges.

* The score $m_j(t)$ associated to an infected vertex $j$ consists of a base score $s_j$ (reflecting the infective potential of the vertex) plus a term $4R_j(t)t_j$ which scales linearly with $R_j$ and thus with the number of clear edges connected to it. We cap this score at saturation.

* The score $m_j(t)$ associated to a healthy vertex $j$ also scales with $R_j$, and thus on the estimated probability that $j$ could be later (re)infected by one of these edges.

* When revealing the neighbourhood of a slow vertex (whether it is a result of an infection or an update), the average increase of the edge score is bounded by

$$ \sum_{j<a_{\text{slow}}N} p_{ij}(s_j + t_j + u_j) \le \frac{4}{3} \frac{1}{\kappa_i} \sum_{j<a_{\text{slow}}N} (\kappa_i \vee \kappa_j) p_{ij}s_j \le \frac{4}{3} \frac{s_i}{c \kappa_i T_i^{\text{loc}}} = \frac{4r}{c} u_i \le u_i, \quad (65) $$

where we have used that $s_j + t_j + u_j \le s_j + \frac{4}{3}t_j \le \frac{4}{3}s_j$, the assumptions on the function $s$, the definition of $t$, and our choice $c > 4r = 6$.

* Note that when the present directed slow edge $(i, j)$ transmits an infection to $j$, the score $s_j + t_j + u_j$ associated to it, is itself an upper bound for the new score $m_j(t) = s_j + t_j$ assigned to $j$ (that is now infected and saturated) plus the average increase in score due to revealing the directed slow edges leaving $j$ (since it is bounded by $u_j$ from the previous argument). Simultaneously, the edge $(i, j)$ becomes saturated, with no score associated to it anymore. Hence, this infection does not increase the total score in average, except possibly for the score associated to $i$, which will then also be saturated. It is especially for this feature that we have introduced $u_j$ and associated the score $s_j + t_j + u_j$ to the present edge $(i, j)$. In a sense, associating the score $s_j + t_j + u_j$ to a present slow edge $(i, j)$ also amounts to considering that revealing the edge $(i, j)$ is “as bad” as using it to transmit the infection.

* We now summarize the previously described conditions entailing saturation:

(i) $i$ is a slow vertex, and since its last update it has infected another slow vertex or has been infected by another slow vertex.

(ii) $R_i(t) \ge 1/4$,

(iii) $i$ is a slow vertex and $N_i^{\text{pr}}(t) \ge \frac{3\kappa_i T_i^{\text{loc}}}{8\lambda}$.

Recall also that a vertex can only stop being saturated by updating, so saturation is maintained even if $R_i(t)$ or $N_i^{\text{pr}}$ drop below their respective values due to the updating of other vertices.

Let $T_{\text{hit}}$ be the first infection time of a star in $[1, \dots, \lfloor aN \rfloor]$. Our aim is to show that $M_{t \wedge T_{\text{hit}}}$ is a supermartingale. To do so we fix $t > 0$, and bound the expected infinitesimal
change of the score

$$ \frac{1}{dt} \mathbb{E}[M_{t+dt} - M_t | \mathfrak{F}_t] \qquad (66) $$

uniformly over all configurations in $\mathfrak{F}_t$ where stars have not yet been infected. Loosely speaking, if $dt$ is sufficiently small, then aside from some term tending to zero with $dt$, the difference $M_{t+dt}-M_t$ comes from a single configuration-changing event. The possible events are infections, recoveries and updates, whose effect on the configuration vary depending on the type of vertex/edge and its state. Since the score is a sum of individual scores, the expression (66) becomes a large sum of terms associated to different vertices/edges affected by these events. In order to facilitate the analysis of this sum, we group these terms into contributions which we control below. The reader can easily check that these contributions indeed exhaust the changes of $M_t$ under all possible events without double counting.

### (i) Negative Contributions.

*Recoveries of infected unsaturated vertices.* The recovery of an infected unsaturated vertex $i$ (whether fast or slow) holds at rate one and induces a change of score

$$ m_i(t + dt) - m_i(t) = 2R_i(t)(s_i + t_i) - (s_i + 4R_i(t)t_i) \le (2R_i(t) - 1)s_i \le -\frac{s_i}{2} $$

since the fact that $i$ is unsaturated implies that $R_i \le \frac{1}{4}$. The total contribution to the expected infinitesimal change is thus upper bounded by

$$ - \sum_{i \text{ infected unsaturated}} \frac{s_i}{2}. \qquad (67) $$

*Unrevealing of present slow edges.* In this contribution we group the terms which appear due to the effect of *unrevealing* previously present edges as a result of the updating of slow vertices. For any given present directed slow edge $(i, j)$, the update of one of its endvertices occurs at rate $\kappa_i + \kappa_j$, and has probability at least $2/3$ (actually tending to 1 with $N$) to stay unrevealed after the update. This yields a contribution

$$ - \sum_{(i,j) \text{ present}} \frac{2}{3}(\kappa_i + \kappa_j)(s_j + t_j + u_j). \qquad (68) $$

*Updates of infected saturated vertices.* In this contribution we group the change in score of infected saturated vertices as a result of their own updating, together with the increase in score that occurs as a result of revealing their new neighbourhood. Each saturated vertex $i$ updates at rate $\kappa_i$, and after its update we have $R_i(t+dt) = 0$ so if $i$ is quick, then

$$ m_i(t + dt) - m_i(t) = s_i - (t_i + s_i) = -t_i. $$

If $i$ is slow, on the other hand, we also need to take into account the effect of the update on the slow edges:

- During the first step of the two-step mechanism all slow edges leaving $i$ become unrevealed, thus dropping $N_i^{\text{pr}}(t+dt)$ to zero.
- During the second step it could happen that $i$ reveals a large value of $N_i^{pr}(t+dt)$, thus becoming saturated again, so $m_i(t+dt) - m_i(t) = 0$. However, from (61) the probability of this event is bounded by $1/3$.

- Also during the second step, a new neighbourhood of $i$ is revealed, which induces a change in the edge score that is in average upper bounded by $u_i = t_i/3$ due to (65).

Adding both effects we obtain that for a slow vertex $i$ the average change in score is upper bounded by $\frac{2}{3}(-t_i) + \frac{t_i}{3} = -\frac{t_i}{3}$, and since this bound also works for quick vertices, we deduce that the total contribution to (66) is at most

$$ - \sum_{i \text{ infected, saturated}} \frac{1}{3} \kappa_i t_i. \qquad (69) $$

• Updates of clear edges adjacent to at least one healthy vertex. In this contribution we count the change in score $m_i(t+dt) - m_i(t)$ for every healthy vertex $i$ due to the decrease of $R_i$ after either its own update or the update of one of its neighbours. Observe that the previous contribution addressed the change in score for saturated vertices, which are infected, and hence we are not double counting. For each healthy vertex $i$, its vertex score is

$$ m_i(t) = 2R_i(t)(s_i + t_i) = 2 \sum_{\substack{j \sim i \\ \{i,j\} \text{ clear edge}}} \frac{\lambda}{\kappa_i + \kappa_j} (s_i + t_i) $$

This score can decrease by $2R_i(t)(s_i + t_i)$ after its own update (which occurs at rate $\kappa_i$), or can decrease by $2\frac{\lambda}{\kappa_i+\kappa_j}(s_i + t_i)$ after the update of its neighbour $j$ (which occurs at rate $\kappa_j$). This yields a contribution

$$ \sum_{i \text{ healthy}} \left[ -2R_i(t)\kappa_i(s_i+t_i) - 2 \sum_{\substack{j \sim i \\ \{i,j\} \text{ clear}}} \frac{\lambda\kappa_j}{\kappa_i + \kappa_j} (s_i+t_i) \right] = - \sum_{i \text{ healthy}} 2\lambda N_i^{\text{cl}}(t)(s_i+t_i), \quad (70) $$

where $N_i^{\text{cl}}(t)$ is the number of clear edges incident to $i$.

• Remaining negative contributions. There are a few negative contributions we are neglecting in our count, such as the decrease of $R_i$ after an infected unsaturated vertex $i$ updates, or after one of its neighbours does. The reason behind neglecting such terms is that these are smaller in magnitude than the ones already considered, and are not necessary to counteract the positive contributions we count below.

We now come to all the positive contributions, coming from the infections and from the updating of the infected vertices (which may reveal a less favourable environment). We will systematically express these positive terms so as to have them easily compared with and compensated by the negative ones.

### (ii) Positive contributions.

• Revealing the neighbourhood of infected unsaturated vertices. In this contribution we group the terms coming from revealing the neighbourhood of infected unsaturated (slow) vertices after their own update. Observe that this leaves out the effect of revealing new
neighbours as a result of the updating of said neighbours; this will be addressed in another contribution. Similarly as for saturated vertices, we count both the increase of the edge scores of the newly revealed present edges, and the one coming from the possibility of having $N_i^{\text{pr}}$ too large after the update. This gives a positive contribution bounded by

$$ \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{2}{3} \kappa_i t_i \le \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{2}{3} \frac{s_i}{8r}. \qquad (71) $$

• *Infections along clear edges.* The infection of a healthy vertex $i$ through clear edges holds at rate $\lambda N_i^{\text{cl}}(t)$ and implies an increase of its vertex score of at most

$$ m_i(t + dt) - m_i(t) = (s_i + 4R_i(t)t_i) - 2R_i(t)(s_i + t_i) = s_i + 2R_i(t)(t_i - s_i) \le s_i $$

Observe that if $i$ is slow, the infection of $i$ has the added effect of revealing its neighbourhood, thus increasing the edge score. Again, due to (65) this increase is bounded in average by $u_i \le t_i$, so grouping together this term and the previous one we obtain a contribution bounded by

$$ \sum_{i \text{ healthy}} \lambda N_i^{\text{cl}}(t)(s_i + t_i). \qquad (72) $$

• *Infections along present edges.* Each present slow edge $(i, j)$ with $i$ infected transmits the infection at rate $\lambda$. This infection has the effect of making $i, j$ and $(i, j)$ saturated, while also possibly revealing the neighbours of $j$. The saturation of $j$ implies a maximal increase in edge score of $s_j + t_j$ while the new edges revealed imply an average increase in score of $u_j$. Both contributions cancel out with the saturation of $(i, j)$ which imply a decrease in score of $s_j + t_j + u_j$. It follows that we only have to consider the increase in score given by the saturation of $i$, which is null if $i$ was saturated, and is bounded by $t_i$ otherwise (since $i$ was already infected). It follows that this contribution is bounded by

$$ \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \lambda N_i^{\text{pr}}(t) t_i \le \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{3}{8} T_i^{\text{loc}} \kappa_i t_i = \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} 3 \frac{s_i}{8r}, \qquad (73) $$

where in the first inequality we have used the bound $N_i^{\text{pr}} \le \frac{3T_i^{\text{loc}}\kappa_i}{8\lambda}$ which holds for unsaturated vertices.

• *Infections along clogged edges and revealing of slow edges (i, j) by the update of j.* In this contribution we cluster the terms coming from two different effects, since the bounds obtained from each effect can be naturally merged into one. Consider first any infected vertex $i$. For any clogged edge $\{i, j\}$, we have transmission of an infection from $i$ to $j$ with intensity $\lambda p_{i,j}$. This increases:

(I.1) The vertex score of $j$, which is bounded by $s_j + t_j$.

(I.2) The edge score associated to the possible revealing of the neighbourhood of $j$ (if $j$ slow). By (65) the average increase of this score is bounded by $u_j$.

(I.3) The vertex score of $i$ by the increase of $R_i(t)$. This increase in score is equal to $\frac{4\lambda}{\kappa_i + \kappa_j} t_i$ if $i$ is unsaturated.
Suppose now that $i$ is an infected slow vertex (so its neighbourhood has been revealed) and fix any absent slow edge $(i, j)$. This edge becomes present by the update of $j$ with intensity $\kappa_j p_{i,j}$ (it can also become present by the update of $i$, but it was already taken into account). This has the effect of:

(II.1) Increasing the edge score by $s_j + t_j + u_j$ due to the new present edge.

(II.2) Possibly making $i$ saturated if $N_i^{pr}(t)$ becomes too large by this additional present edge. Since $i$ was already infected, the score increase is at most $t_i$.

In order to deal with all these contributions suppose first that $i$ is infected and quick. Grouping (I.1) and (I.2) together gives a contribution bounded by

$$ \sum_j \lambda p_{i,j} (s_j + t_j + u_j) \leq \frac{4}{3} \sum_j \lambda p_{i,j} s_j \leq \frac{4}{3} \frac{s_i}{c T_i^{\text{loc}}} $$

where in the last inequality we have used (41). Suppose now that $i$ is infected and slow. In that case the contributions (I.1) and (I.2) only arise for neighbours $j$ that are quick, while for slow neighbours we can count the contribution coming from (II.1):

$$ \sum_{j \text{ quick}} \lambda p_{i,j} (s_j + t_j + u_j) + \sum_{j \text{ slow}} \kappa_j p_{i,j} (s_j + t_j + u_j) = \sum_j (\lambda \wedge \kappa_j) p_{i,j} (s_j + t_j + u_j) \\ \leq \frac{4}{3} \sum_j (\lambda \wedge \kappa_j) p_{i,j} s_j \leq \frac{4}{3} \frac{s_i}{c T_i^{\text{loc}}} $$

where this time we have used (42). We conclude then that from (I.1), (I.2) and (II.1) we obtain the bound

$$ \sum_{i \text{ infected}} \frac{4}{3} \frac{s_i}{c T_i^{\text{loc}}} $$

It will be convenient to split this sum, counting separately over saturated and unsaturated vertices. Using the bounds $T_i^{\text{loc}} \geq 8$ and $T_i^{\text{loc}} \geq \frac{8}{3\kappa_i}$ we obtain

$$ \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{4}{3} \frac{s_i}{c T_i^{\text{loc}}} \leq \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{4}{3c} \frac{s_i}{8} \quad (74) $$

and

$$ \sum_{\substack{i \text{ infected} \\ \text{saturated}}} \frac{4}{3} \frac{s_i}{c T_i^{\text{loc}}} \leq \sum_{\substack{i \text{ infected} \\ \text{saturated}}} \frac{4r}{3c} \kappa_i t_i \quad (75) $$

Regarding (I.3) we first assume that $i$ is quick and unsaturated so the total contribution coming from clogged edges incident to $i$ is at most

$$ \sum_j \lambda p_{i,j} \frac{4\lambda}{\kappa_i + \kappa_j} t_i = 4\lambda^2 t_i \pi_i \leq \frac{T_i^{\text{loc}}}{4} \kappa_i t_i = \frac{s_i}{4r} $$

where in the inequality we have used that $T_i^{\text{loc}} \geq 16 \frac{\lambda^2 \pi_i}{\kappa_i}$. Suppose now that $i$ is slow. In this case we can use the fact that for any slow vertex $j$ we have $\kappa_j \leq \lambda$ to bound the
contribution coming from (II.2) by

$$ \sum_{j \text{ slow}} \kappa_j p_{i,j} t_i \le \sum_{j \text{ slow}} \lambda p_{i,j} t_i \le \sum_{j \text{ slow}} \lambda p_{i,j} t_i \frac{2\lambda}{\kappa_i + \kappa_j} $$

Since vertices connected to $i$ through clogged edges are necessarily quick we can thus add the terms coming from (I.3) and (II.2) (associated to $i$) together to obtain

$$ \sum_{j \text{ quick}} \lambda p_{i,j} \frac{4\lambda}{\kappa_i + \kappa_j} t_i + \sum_{j \text{ slow}} \kappa_j p_{i,j} t_i \le \sum_{j} \frac{4\lambda^2}{\kappa_i + \kappa_j} t_i p_{i,j} \le \frac{s_i}{4r} $$

which is the same bound obtained for quick vertices, and hence we conclude the upper bound for the total contribution of terms coming from (I.3) and (II.2)

$$ \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{s_i}{4r} \qquad (76) $$

We can now group all the different contributions to the expected infinitesimal change. We begin by grouping (67), (71), (73), (74) and (76) together, so we arrive at

$$ - \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \left( 4r - \frac{17}{3} - \frac{4r}{3c} \right) \frac{s_i}{8r} = - \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{1}{21} \frac{s_i}{8r} \le - \sum_{\substack{i \text{ infected} \\ \text{unsaturated}}} \frac{\kappa_i t_i}{21}, $$

where in the equality we have injected the values $r = 3/2$ and $c = 7$, and in the inequality we have used (63). Grouping together (69) and (75) yields the upper bound

$$ - \sum_{\substack{i \text{ infected} \\ \text{saturated}}} \left( \frac{1}{3} - \frac{4r}{3c} \right) \kappa_i t_i = - \sum_{\substack{i \text{ infected} \\ \text{saturated}}} \frac{\kappa_i t_i}{21}. $$

Next, we group together (70) and (72), which gives

$$ - \sum_{i \text{ healthy}} \lambda N_i^{\text{cl}}(t) (s_i + t_i). $$

Using the basic observation $R_i(t) \le N_i^{\text{cl}}(t)$, we finally obtain that the average infinitesimal increase $\frac{1}{dt}\mathbb{E}[M_{t+dt} - M_t|\mathfrak{F}_t]$ is upper bounded by

$$ - \sum_{i \text{ infected}} \frac{\kappa_i t_i}{21} - \sum_{i \text{ healthy}} \frac{\lambda}{2} m_i(t) - \sum_{(i,j) \text{ present}} \frac{2}{3}(\kappa_i + \kappa_j)(s_j + t_j + u_j), \quad (77) $$

and since this quantity is negative we conclude that $M_{t \wedge T_{\text{hit}}}$ is a supermartingale.

To finish the proof of the theorem, we first consider the case $a > 0$, and go back to the original contact process $X$, for which we can use self-duality to get

$$ I_N(t) \le \frac{[aN]}{N} + \frac{1}{N} \sum_{i=[aN]+1}^{N} \mathbb{P}_i(t < T_{\text{ext}}^X), \qquad (78) $$
where $\mathbb{P}_i$ stands for the law of the infection process with initially only vertex $i$ infected, and $T_{\text{ext}}^X$ stands for its extinction time. Since $X$ is stochastically bounded from above by the new process up until the hitting time $T_{\text{hit}}$, we know that on the event $T_{\text{ext}} < T_{\text{hit}}$, where $T_{\text{ext}}$ is the extinction time of the new process, we have $T_{\text{ext}}^X \le T_{\text{ext}}$. Letting $T = T_{\text{hit}} \wedge T_{\text{ext}}$, we thus have

$$ \mathbb{P}_i(t < T_{\text{ext}}^X) \le \mathbb{P}_i(T_{\text{hit}} < T_{\text{ext}}) + \mathbb{P}_i(t < T). \quad (79) $$

To control the term $\mathbb{P}_i(T_{\text{hit}} < T_{\text{ext}})$ we use that $(M_{t \wedge T})$ is a supermartingale to obtain

$$ \mathbb{E}_i[M_0] \ge \mathbb{E}_i[M_T] = \mathbb{E}_i[M_{T_{\text{hit}}}] \mathbb{1}_{T_{\text{hit}} < T_{\text{ext}}} + \mathbb{E}_i[M_{T_{\text{ext}}}] \mathbb{1}_{T_{\text{hit}} > T_{\text{ext}}} = \mathbb{E}_i[M_{T_{\text{hit}}}] \mathbb{1}_{T_{\text{hit}} < T_{\text{ext}}}, $$

since $M_{T_{\text{ext}}} \ge 0$. Now, at $T_{\text{hit}}$ we know that there is at least one star infected, so $M_{T_{\text{hit}}} \ge s(a)$. On the other hand, under the assumption that at time $t=0$ only $i$ is infected, the total score of the configuration comes from its vertex score, and the initially revealed slow edges $(i, j)$ (if $i$ slow). From (61) and (65) we can thus bound

$$ \mathbb{P}_i(T_{\text{hit}} < T_{\text{ext}}) \le \frac{\mathbb{E}_i[M_0]}{s(a)} \le \frac{s_i + \frac{t_i}{3} + u_i}{s(a)} \le \frac{7}{6} \frac{s_i}{s(a)}. $$

To control the term $\mathbb{P}_i(t < T)$ we observe that on $t < T$ there is at least one vertex $j > aN$ infected and hence from (77) we deduce that $\frac{1}{dt}\mathbb{E}[M_{t+dt} - M_t|\mathfrak{F}_t] \le -r$ for some $r > 0$ independent of $i, t$ and $N$ (but which might depend on $a$ and $\lambda$). Hence $M_{t \wedge T} + r(t \wedge T)$ is a supermartingale, and in particular $r\mathbb{E}_i[T] \le \mathbb{E}_i[M_T + rT] \le \mathbb{E}_i[M_0]$. We infer that

$$ \mathbb{P}_i(t < T) \le \frac{1}{t} \mathbb{E}_i[T] \le \frac{1}{rt} \mathbb{E}_i[M_0] \le \frac{7s_i}{6rt}. $$

Finally, replacing the bounds found in (79) and using said bounds in (78) together with a simple sum-integral comparison yields

$$ I_N(t) \le a + \frac{1}{N} + \frac{7}{6s(a)} \int s(y)dy + \frac{7}{6rt} \int s(y)dy, $$

and hence we conclude (44).

In the case $a=0$ with $(H)_\delta$ satisfied for some $\delta \in [0, 1]$, there is $C = C(a, \lambda)$ independent of $N$ such that $T^{\text{loc}}s^{-\delta} \le C$. We can use this to further improve (77) by observing that

$$ \kappa_i t_i \ge \frac{1}{C} \kappa_i t_i T_i^{\text{loc}} s_i^{-\delta} = \frac{s_i^{1-\delta}}{Cr} \ge \frac{(s_i + t_i + u_i)^{1-\delta}}{C'}, $$

for some $C'$. It follows from (77) that

$$ \begin{aligned} \frac{1}{dt}\mathbb{E}[M_{t+dt} - M_t|\mathfrak{F}_t] &\le - \sum_{i \text{ infected}} \frac{\kappa_i t_i}{21} - \sum_{i \text{ healthy}} \frac{\lambda}{2} m_i(t) - \sum_{(i,j) \text{ present}} \frac{2}{3} \kappa_j t_j \\ &\le - \sum_{i \text{ infected}} \frac{(s_i + t_i)^{1-\delta}}{21C'} - \sum_{i \text{ healthy}} \frac{\lambda}{2} m_i(t)^{1-\delta} - \sum_{(i,j) \text{ present}} \frac{2}{3C'} (s_j + t_j + u_j)^{1-\delta} \\ &\le - \frac{1}{C''} M_t^{1-\delta}, \end{aligned} $$

where in the last inequality we used the concavity of the function $f(x) = x^{1-\delta}$.
In particular, if $\delta > 0$ we conclude that $M_{t \wedge T_{\text{ext}}}^{\delta} + \frac{\delta}{C''}(t \wedge T_{\text{ext}})$ is a supermartingale and so

$$ \mathbb{E}_i[T_{\text{ext}}] = \mathbb{E}_i \left[ T_{\text{ext}} + \frac{C''}{\delta} M^{\delta} T_{\text{ext}} \right] \le \frac{C''}{r\delta} \mathbb{E}[M_0^{\delta}] \le \frac{C''}{r\delta} \mathbb{E}[M_0]^{\delta} \le \frac{C'' \left( \frac{7}{6} \int s(y) dy \right)^{\delta}}{\delta} N^{\delta}. $$

We get that (43) holds. When $\delta = 0$ we use that $\log(1 + M_{t \wedge T_{\text{ext}}}) + r(t \wedge T_{\text{ext}})/2$ is a supermartingale to deduce the upper bound $\mathbb{E}[T_{\text{ext}}] = O(\log N)$, so (44) holds. For more details, we refer here to the similar computations made in the appendix of [13].

### 5.2. Proof of Theorem 4.
The general strategy of the proof is the same as in the proof of Theorem 3: We introduce a stochastic upper bound for the infection process and then associate a score with each configuration. We then prove that the scoring function, recording the evolution in time of the score, defines a supermartingale. We maintain the name $M(t)$ for this scoring function, to emphasise the fact that several computations from the previous proof will be reused here. However, our upper bound is much closer to the actual process and the analysis of the supermartingale therefore more complex. In particular, the scores depend on a finer classification of vertices allowing us to separate local and global features of the infection process in the analysis.

As before, the threshold $a$ provided in the statement of the theorem defines stars $i < aN$ and non-star vertices $i \ge aN$. We also recall the thresholds

$$ a_{\text{slow}} = (\lambda/\kappa_0)^{-\frac{1}{\gamma\eta}} \quad \text{and} \quad a_{\text{stsl}} = a_{\text{str}} \wedge a_{\text{slow}}, $$

where $a_{\text{str}}$ was defined by (46) and which, by (1), is of order $\lambda^{2/\gamma}$. Using these thresholds we introduce the new classification of the vertices, dividing them into strong slow, strong quick, and weak, as shown in Table 4 below. Without loss of generality we suppose $a < a_{\text{stsl}}$, as this is the case featuring the largest variety in the classification for nonstar vertices. This also implies that star vertices are strong slow vertices.

<table><caption>TABLE 4. The three types of vertices and their main features.</caption><thead><tr><th>Vertex <i>i</i></th><th><i>i</i> &le; <i>a</i><sub>stsl</sub><i>N</i></th><th><i>a</i><sub>stsl</sub><i>N</i> &lt; <i>i</i> &le; <i>a</i><sub>str</sub><i>N</i></th><th><i>a</i><sub>str</sub><i>N</i> &lt; <i>i</i> &le; <i>N</i></th></tr></thead><tbody><tr><td>Type of vertex</td><td>Strong slow</td><td>Strong quick</td><td>Weak</td></tr><tr><td>Average degree</td><td colspan="2">&ge; 1/(10&lambda;<sup>2</sup>)</td><td>&lt; 1/(10&lambda;<sup>2</sup>)</td></tr><tr><td>Updating rate</td><td>&lt; &lambda;</td><td>&ge; &lambda;</td><td></td></tr><tr><td><i>T</i><sup>loc</sup><sub><i>i</i></sub></td><td colspan="2">max(8, <sup>8</sup>&frasl;<sub>3&kappa;<sub><i>i</i></sub></sub>, 16&lambda;<sup>2</sup> <sup>&pi;<sub><i>i</i></sub></sup>&frasl;<sub>&kappa;<sub><i>i</i></sub></sub>)</td><td>not applicable</td></tr></tbody></table>

To compare the current classification of vertices to the one used in the proof of Theorem 3 we consider separately the cases $\eta < -1/2$ and $\eta \ge -1/2$. In the first case we have $a_{\text{stsl}} \ll a_{\text{str}}$, and hence the strong slow vertices coincide with slow vertices, while the quick vertices are subdivided into strong quick and weak. On the other hand, if $\eta \ge -1/2$, we have $a_{\text{stsl}} = a_{\text{str}}$, so strong quick vertices do not exist. In that case, strong slow vertices are still slow, but now weak vertices can be slow, too. Although weak vertices may exhibit qualitatively distinct behaviours, our methods allow us to work with these vertices without the need to differentiate between the quick and the slow ones.
<table><caption>TABLE 5. Comparison of the classification of vertices in both theorems</caption><thead><tr><th>Theorem 3</th><th>Slow</th><th colspan="2">Quick</th></tr></thead><tbody><tr><td>Theorem 4, case η &lt; -1/2</td><td>Strong slow</td><td>Strong quick</td><td>Weak</td></tr><tr><td>Theorem 4, case η ≥ -1/2</td><td>Strong slow</td><td colspan="2">Weak</td></tr></tbody></table>

Compared to Theorem 3, the new classification introduced here allows for a finer control of the behaviour of the infection, combining a local and global element of the analysis. This can be observed when comparing the inequalities within the statements of both theorems: while inequalities (41) and (42) have analogous counterparts (49) and (50), in Theorem 4 we also find inequality (48) for weak vertices. Most noticeably, there is no term $T^{\text{loc}}$ in (48), which is in line with the idea that local survival does not apply to weak vertices, and hence imposing this inequality follows closer the expected behaviour of the infection on weak vertices. With the new classification comes a small trade-off: a slight decrease in precision concerning the constants within the statement. Unlike in Theorem 3, where the constant c was explicit, here we need it to be sufficiently large for the proof to work.

The stochastic upper bound introduced here has several differences with the one introduced in the proof of Theorem 3 (although many similarities as well), and to motivate its definition we point out the following observations:

* Providing an upper bound for $I_N(t)$ translates by (78) into bounding from above the extinction probability of the contact process starting from a single infected non-star vertex. The infection should not be able to spread and survive for too long, unless it infects a star on its way. Hence we should not observe vertices with unusually large degree, short cycles, or other structures that are rare in the local limit of the (static) network. If we do, we stop the process. Part of the proof consists in showing that by that time the infection has already either died out or infected a star.

* The stochastic upper bound for $(\mathcal{G}_t^{(N)}, X_t)$ is an infection process (akin to the contact process) running on top of an environment modelled as a growing oriented network $(G_t)_{t \ge 0}$ representing the environment seen by the infection. The growth of the network is following the oriented infection paths using updating rules similar to those in $\mathcal{G}_t^{(N)}$, with one significant deviation from the previous model: connections are never destroyed but merely blocked for the infection. Hence the growing network serves not only to carry the infection process, but also to keep track of all the vertices and connections that have been revealed in the past. This information can be used for the global analysis in a similar way as in the previous section.

* The growing network is set up to have a tree structure, which we exploit in order to control the behaviour of the infection on weak vertices. For these vertices, the scoring function $M(t)$ is defined for the local analysis similarly as in [16], where the authors study the contact process on static trees with degrees bounded by $1/(8\lambda^2)$. Note that weak vertices have expected degree less than $1/(10\lambda^2)$, and thus are quite likely to have degree bounded by $1/(8\lambda^2)$. At the early stage of the infection, we will typically never visit a weak vertex with a degree higher than this threshold.
* For our methods to work we need to control the degree of weak vertices, which, as seen in Table 5 can be slow. In particular, it is not viable to use the clogged/clear scheme introduced in the proof of Theorem 3, where vertices steadily increase their degree until the next updating event. Instead, we are forced to reveal more of the network structure, which implies several complications. But this network structure will also imply simplifications in our computations as compared to the previous section.

**The stochastic upper bound.** We now define more precisely the upper bound consisting of an infection process running on top of a growing oriented network $(G_t)_{t \ge 0}$. Despite the complexity of the process it will always be clear from the construction that up to the time when the process is stopped it represents a stochastic upper bound on the infection.

Let $\mathcal{E}$ the set of all oriented edges of the vertex set $\{1, 2, \dots, N\}$ excluding loops. The growing network is initialized at time $t=0$ as some $G_0 = (V_0, E_0)$ to be described later, with vertex set $V_0 \subseteq \{1, \dots, N\}$ and $E_0 \subseteq \mathcal{E}$. The network then evolves by connecting to new vertices from this set through edges in $\mathcal{E}$. Together with the evolution of the network $(G_t)_{t \ge 0}$ we also keep track of an accompanying process $(\mathfrak{A}_t)_{t \ge 0}$ of available edges, where $\mathfrak{A}_t \subseteq \mathcal{E} \setminus E_t$ at each time $t$ consists of all the oriented edges that can be used for the growth of the network. Each edge can only be used once and in only one of the two possible orientations in the construction of $G_t$, so the set of available edges decreases over time and the set inequality $\mathfrak{A}_t \subseteq \mathcal{E} \setminus E_t$ is, in general, strict because as the network grows, several unused edges will be discarded.

We maintain the classification of vertices in $\{1, \dots, N\}$ distinguishing between strong slow, strong quick, and weak. Vertices can be either *healthy* or *infected*, and strong vertices (both quick and slow) can also be *saturated*, which is a state analogous to the one defined in the proof of Theorem 3. We also classify each oriented edge $(i, j)$ as either

* *weak*, if $j$ is weak,

* *strong slow* if both $i$ and $j$ are strong slow,

* or *strong quick* if $j$ is strong (either quick or slow) but $(i, j)$ is not strong slow,

see Table 6. Observe that in general it is the head of the oriented edge $(i, j)$ which determines its classification, except for strong slow edges. Also note that in the case $\eta \ge -1/2$, strong quick edges only occur if the head is strong slow and the tail is weak. In that case the term “strong” is a bit awkward, but, as will become clear below, it points towards the idea that the infection uses such an edge to discover a new strong vertex.

Besides their classification, edges also have a *state* which depends on their type and whether they belong to the network at a given time:

* Edges that belong to $G_t$ are either *present* or *absent*, regardless of their classification. The reader might think of this in the same way as in the original dynamic network, where present edges are used for the spread of the infection, while absent edges are not.

* Strong slow edges that belong to $G_t$ (and only these edges) can also become saturated, which is a state analogous to the one defined for slow edges in the proof of Theorem 3. Again, the intuition is that saturated edges connect saturated vertices, and hence become useless (we provide the exact conditions for saturation later).
* Available edges that are strong quick are *clogged*, which, as in Theorem 3, can be thought of as constantly available channels for the infection, traversed at a much smaller rate.

* Available edges that are either weak or strong slow are *unseen*, which is a state that reflects the fact that “these connections have not occurred so far”.

<table><caption>TABLE 6. The possible states of an edge $(i, j)$. Edges are classified *strong slow* in the green, *strong quick* in the blue and *weak* in the yellow field.</caption><thead><tr><th>Type of <i>j</i></th><th>Strong slow</th><th>Strong quick</th><th>Weak</th></tr></thead><tbody><tr><th>Strong slow</th><td>unseen/absent/<br>present/saturated</td><td></td><td>unseen/absent/present</td></tr><tr><th>Strong quick</th><td></td><td></td><td></td></tr><tr><th>Weak</th><td>clogged/absent/present</td><td></td><td></td></tr></tbody></table>

The network $G_t$ represents the graph structure that has been observed by the infection by time $t$. In this sense, the reader may find it useful to think of $G_t$ as a window in which we (somewhat closely) track the structure belonging to $\mathcal{G}_t^{(N)}$, and hence it makes intuitive sense for this window to grow over time, representing the growth of the region “explored” by the infection. This intuition may contrast with the intuition about the *actual* structure in $\mathcal{G}_t^{(N)}$, where connections are destroyed over time. We reconcile both intuitions by pointing out that while $G_t$ grows, most of its edges are labeled *absent* over time. From this point onwards, all comments about the growth of the network refer to $G_t$.

We now define the following operations:

(1) Let $(i, j)$ in $\mathfrak{A}_t$ be an available edge at time $t$. We say that we *incorporate* the edge into the network, by:

* Adding the vertex $j$ to $G_t$. If $j$ was already in $G_t$, we ignore this step.

* Adding the edge $(i, j)$ to $G_t$, changing its state to *present*.

* Removing both $(i, j)$ and $(j, i)$ from $\mathfrak{A}_t$.

At times we abuse notation and say that we incorporate a vertex $j$. This amounts to saying that we incorporate the edge $(i, j)$ if $i$ is clear from context.

(2) Let $i$ be a vertex in $G_t$. We say that we *reveal new neighbours of i* by:

* Tossing an independent coin with probability $p_{i,j}$ for each *unseen* edge $(i, j)$.

* Incorporating to the network each edge whose toss turned up heads. We frequently specify some subset of the neighbours of $i$ to reveal. This means that we only toss coins for the edges $(i, j)$ with $j$ belonging to the specified subset.

(3) Let $i \in \{1, 2, \dots, N\}$. We say that we *reveal i* by:

* Tossing an independent coin with probability $p_{j,i}$ for each *unseen* edge $(j, i)$, $j \in G_t$.

* Incorporating to the network each edge whose toss turned up heads. As in the previous operation, we might specify that $i$ is revealed to a particular subset of vertices, which implies that we only toss coins for the edges $(j, i)$ with $j$ belonging to the specified subset.
<figure><img src="image_6.png" /><figcaption>FIGURE 4. a) An example where the vertex set of $G_t$ is {1, 2, 3}, while 4, 5, and 6 have not been added to the network yet. Vertex 3 reveals new neighbours so we require to sample all *unseen* available edges leaving 3. In this case, this includes the edge (3, 2), even though 2 already belongs to $G_t$. We also exclude the edge (3, 4) which is *clogged*, represented through a squiggly arrow. b) After sampling all edges, only edge (3, 5) is incorporated to the network, so in particular the new vertex set of $G_t$ is {1, 2, 3, 5}.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>FIGURE 5. c) In the picture we see the network from Figure 4 where now it is vertex 4 that is being revealed. This requires to sample all *unseen* available edges entering 4 from vertices in $G_t$. Again, this excludes edge (3, 4) which is *clogged*. d) After sampling all edges, both (1, 4) and (2, 4) are incorporated to the network. The creation of a cycle then stops the process.</figcaption></figure>

The following observations are key about the newly defined operations:

(a) Incorporating an edge means that the network grows by adding the edge (with the corresponding endpoint) to its structure, and since edges can only be incorporated once it must become unavailable afterwards along with its inverse.

(b) When revealing new neighbours of a vertex $i$, we only reveal *unseen* edges, thus leaving out strong quick edges. The reason behind this is that in the new process, strong slow and weak edges behave similarly to the edges in the original dynamic network $G_t^{(N)}$, while strong quick edges behave similarly to the quick edges in the previous proof, see Figure 4 for an example.
(c) Typically, when we reveal new neighbours of $i \in G_t$, these will not be in $G_t$ and when we reveal a vertex $i$ to a vertex $j \in G_t$, we have $i \notin G_t$. It is still possible that neighbours $i, j \in G_t$ are revealed (and the tree structure is broken), see for example Figure 5, but this is an unlikely and undesirable scenario upon which we stop the process, as we will explain later.

(d) The classification of edges is such that strong quick vertices can never be revealed, and strong slow ones can only be revealed to strong slow vertices in $G_t$.

We say a vertex $i \in \{1, 2, \dots, N\}$ has been *visited* by time $t$, if it has become infected or saturated at least once by that time. Since $G_t$ represents the part of the environment observed by the infection by time $t$, visited vertices always belong to the network. The reader might think of non-visited vertices in $G_t$ as places yet to be explored by the infection.

Using the new definitions, we can now begin to describe the evolution of the process and the scoring associated with the configurations it can reach.

*Evolution of the process within $G_t$. Setting aside the growth of the network, the rules followed by the process are analogous to the original contact process on $\mathcal{G}_t^{(N)}$:*

Rule (1): Each vertex $i \in \{1, 2, \dots, N\}$ updates at rate $\kappa_i$. If $i$ belongs to $G_{t-}$, then (among other effects we describe later) all edges $(i, j)$ and $(j, i)$ in $G_{t-}$, whether previously present, absent, or saturated, are resampled as in $\mathcal{G}_t^{(N)}$: for each such edge, we flip a coin with probability $p_{i,j}$ and label *present* all the ones for which the coin turned up heads. We label *absent* all the rest.

Rule (2): Within $(G_t)_{t \ge 0}$ the infection evolves as a regular contact process with infection rate $\lambda$ (except for saturated vertices which we cover later). The edges used to spread the infection must always be *present* (not absent or saturated) and can be used regardless of their orientation.

Note that within $G_t$ all edges and vertices are treated the same, regardless of their type, and oriented edges are treated as if they were unoriented. The classification of vertices has more impact on the network growth than on the changes and infections occurring within it.

*Evolution of the process by inherited rules.* Several of the evolution rules and scoring functions are adaptations of what was defined in the previous section. Before giving these rules we provide a brief (and incomplete) summary of the process described in Section 5:

* Vertices were divided into slow and quick, where each vertex $i$ updated at rate $\kappa_i$.

* When a slow vertex $i$ updated, it lost its set of slow neighbours (which became *unrevealed*). However, if at that time $i$ was infected, we sampled a new set of slow neighbours. Also, while $i$ was infected (or saturated), every time another slow vertex $j$ updated, its connection to $i$ was resampled.

* When a slow vertex $i$ transitioned from *healthy* to *infected* or *saturated*, we added new slow neighbours among the ones that were *unrevealed* at that time.

* Edges $\{i, j\}$ with at least one quick vertex were classified as either *clogged* or *clear*. Clogged edges transmitted the infection at rate $\lambda p_{i,j}$, and at the infection event, the edge was cleared. Clear edges transmitted the infection at rate $\lambda$, and upon updating, become clogged again.
We refer the reader to Section 5.1 for the intuition behind this construction. We adapt these rules to the current scenario, with strong slow and strong quick vertices playing the role of slow and quick vertices, respectively:

Rule (3): A strong slow vertex $i \in G_t$ reveals new strong slow neighbours if either,

• it updates while infected or saturated ($i$ must be *visited* at time $t^{-}$), or

• it transitions from *healthy* to *infected* or *saturated*.

Rule (4): When a strong slow vertex $j \in \{1, 2, \dots, N\}$ updates at a time $t$, it is revealed to the strong slow vertices in $G_t$ that are infected.

Rule (5): An infected vertex $i$ transmits the infection through the clogged edges of the form $(i, j)$ at rate $\lambda p_{i,j}$. When an infection of this sort takes place, $j$ becomes infected, $(i, j)$ is incorporated to the network and $j$ becomes instantly infected (and thus visited), see for example Figure 6.

<figure><img src="image_8.png" /><figcaption>FIGURE 6. a) In the picture $G_t$ consists of the four vertices joined through solid arrows, with a single vertex infected, depicted as grey. Each vertex is classified as either weak (W), strong slow (Ss), or strong quick (Sq), and solid arrows marked by an X are absent. The infected vertex can infect its strong slow neighbour (but not the weak one) or transmit the infection through one of the *clogged* edges, depicted as squiggly arrows, at rate $\lambda p_{i,j}$. b) The infection is transmitted through the present edge. The newly infected strong slow vertex reveals new strong slow neighbours, which results in the incorporation of a new edge to the network.</figcaption></figure>

A small difference between the rules given here, and the description of the process in Section 5 is that strong quick edges belonging to $G_t$ do not become clogged again upon updating, and instead evolve as any other edge. In that sense, the current process is closer to the original dynamic network $\mathcal{G}_t^{(N)}$, because it has “better memory”.

*Evolution of the process at weak vertices and edges.* As pointed out after the presentation of Theorem 3 at the beginning of Section 4.2, the main improvement of Theorem 4 over Theorem 3 is related to the treatment of weak vertices. In this treatment, we need to control the degrees of these vertices at all times, which forces us to endow weak vertices and edges with a set of rules that closely resembles those in the original network $\mathcal{G}_t^{(N)}$:
Rule (6): When a visited vertex $i \in G_t$ updates, it reveals new weak neighbours. This also occurs when $i$ first becomes visited.

Rule (7): When a weak vertex $i \in \{1, 2, \dots, N\}$ updates, we reveal it to all visited vertices in $G_t$.

Note that Rule (7) introduces a steady growth of the network, while Rule (6) introduces jumps to this growth. Also new weak edges are only appended to visited vertices, since the structure around non-visited vertices has not yet been observed by the infection.

All the rules described so far act either simultaneously, or following a sequential intuitive ordering. For example, see Figure 7, when a visited weak vertex within $G_t$ updates, it resamples the state of the connections within $G_t$ (following Rule (1)), reveals new weak neighbours (Rule (6)), and reveals itself to non-neighbouring vertices in $G_t$ (Rule (7)), all at the same time.

<figure><img src="image_9.png" /><figcaption>FIGURE 7. a) The visited weak vertex (identified with a wide border) updates, so we require to resample its connection to the strong vertex at the top left, and both reveal new weak neighbours, and be revealed to the vertices in the network.
b) After resampling its connection to the strong vertex, the edge becomes absent. Also, two new edges are incorporated to the network.</figcaption></figure>

As a further example, when a vertex $i \in G_t$ infects some $j \notin G_t$ through a clogged edge, $j$ is added to the network and becomes visited. Consequently, according to Rule (6), it reveals new weak neighbours. If $j$ is a strong slow vertex, then according to Rule (3), it also reveals new strong slow neighbours. Observe that we have not provided the mechanisms involved in the saturation of vertices and edges. As some of the conditions for saturation require us to describe certain elements of the scoring function we will postpone it.

*Starting and stopping the process.* As pointed out before, the goal of the theorem is to upper bound the extinction probability $P_{i_0}(t < T_{\text{ext}})$ of the contact process starting from a single infected non-star vertex. We fix such a vertex $i_0$ and initialize $G_0$ as follows:

• Initially, we consider all possible oriented edges $(i, j)$ in $\mathcal{E}$ as available.

• We start by adding $i_0$ to the network and infecting it, thus declaring it visited.

• Following Rules (3) and (6), we reveal new weak and (possibly) strong slow neighbours of $i_0$, thereby defining $G_0$ as well as $\mathfrak{A}_0$.