\documentclass[a4paper]{amsart} \usepackage{amsfonts,amssymb,amsmath, dsfont} \usepackage{upgreek} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{graphicx, epstopdf} \usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue,pagebackref=false]{hyperref} \usepackage{microtype} %\usepackage[notcite,notref,color]{showkeys} %\definecolor{labelkey}{gray}{.8} %\definecolor{refkey}{gray}{.8} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{rem}[theorem]{Remark} \renewcommand{\theequation}{\thesection .\arabic{equation}} \def \IP {\mathbb{P}} \def \C {{\mathbb C}} \def \E {{\mathbb E}} \def \L {{\mathbb L}} \def \N {{\mathbb N}} \def \P {{\mathbb P}} \def \Q {{\mathbb Q}} \def \R {{\mathbb R}} \def \Z {{\mathbb Z}} \def \ra {\rightarrow} \def \ba {\begin{array}} \def \ea {\end{array}} \def \da {\downarrow} \def \ua {\uparrow} \def \lra {\longrightarrow} \def \Id {{\rm Id}} \def \ES {{\rm E}} \def \PS {{\rm P}} \def \Sp {{\rm Sp}} \def \SES {{\hbox{\footnotesize\rm SES}}} \def \IRW {{\hbox{\tiny\rm IRW}}} \def \RW {{\hbox{\tiny\rm RW}}} \def \maj {{\rm maj}} \def \new {{\rm new}} \def \var {{\rm var}} \def \Var {{\rm Var}} \def \osc {{\rm osc}} \def \diag {{\rm diag}} \def \off {{\rm off}} \def \c {{\rm c}} \def \cA {{\mathcal A}} \def \cC {{\mathcal C}} \def \cD {{\mathcal D}} \def \cE {{\mathcal E}} \def \cF {{\mathcal F}} \def \cG {{\mathcal G}} \def \cH {{\mathcal H}} \def \cI {{\mathcal I}} \def \cL {{\mathcal L}} \def \cM {{\mathcal M}} \def \cN {{\mathcal N}} \def \cP {{\mathcal P}} \def \cS {{\mathcal S}} \def \cSb {{\mathcal S}_b} \def\embf#1{\emph{\bf #1}} \def \un {\underline} \def \ov {\overline} \def \td {\tilde} \def \Ll {\left} \def \Rr {\right} \def \subset {\subseteq} \def \d {\mathrm d} \def \tdj {\td{\jmath}} \def \emptyset {\varnothing} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \title[Exponential extinction time of the contact process]{Exponential extinction time of the contact process on finite graphs} \author[T.\ Mountford, J.-C.\ Mourrat, D.\ Valesin, Q.\ Yao]{Thomas Mountford\textsuperscript{1}, Jean-Christophe Mourrat\textsuperscript{1}, Daniel Valesin\textsuperscript{2,3} and Qiang Yao\textsuperscript{4,5}} \footnotetext[1]{\'Ecole Polytechnique F\'ed\'erale de Lausanne, D\'epartement de Math\'ematiques, 1015 Lausanne, Switzerland} \footnotetext[2]{University of British Columbia, Department of Mathematics, V6T1Z2 Vancouver, Canada} \footnotetext[3]{Research funded by the Post-Doctoral Research Fellowship of the Government of Canada} \footnotetext[4]{School of Finance and Statistics, East China Normal University, Shanghai 200241, China} \footnotetext[5]{Research partially supported by NSFC grants(No.11201150, No.11126236 and No.10901008), SSSTC grant(No.EG55-032010), the Fundamental Research Funds for the Central Universities(No.239201278210075), and the 111 Project(B14019)} \begin{abstract} We study the extinction time $\uptau$ of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on $\Z$, then, uniformly over all trees of degree bounded by a given number, the expectation of $\uptau$ grows exponentially with the number of vertices. Additionally, for any increasing sequence of trees of bounded degree, $\uptau$ divided by its expectation converges in distribution to the unitary exponential distribution. These results also hold if one considers a sequence of graphs having spanning trees with uniformly bounded degree, and provide the basis for powerful coarse-graining arguments. To demonstrate this, we consider the contact process on a random graph with vertex degrees following a power law. Improving a result of Chatterjee and Durrett \cite{CD}, we show that, for any non-zero infection rate, the extinction time for the contact process on this graph grows exponentially with the number of vertices. \bigskip \noindent \textsc{MSC 2010:} 82C22, 05C80. \medskip \noindent \textsc{Keywords:} contact process, interacting particle systems, metastability. \end{abstract} %\noindent\textit{Mathematics Subject Classification.} Primary: 82C22. Secondary: 05C80. \\\textit{Key words:} % contact process, interacting particle systems, metastability. \maketitle % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % \section{Introduction} \label{s:intro} \setcounter{equation}{0} We study the contact process on finite graphs. Our main goal is to present robust results and techniques which justify that, for certain values of the infection parameter, the contact process survives for a time which is exponential in the number of vertices of the underlying graph. We start by introducing notations and recalling important facts. Let $G = (V, E)$ be a graph with undirected edges. The contact process on $G$ with parameter $\lambda > 0$ is a continuous-time Markov process $(\xi_t)_{t \geq 0}$ on the space of subsets of $V$ whose transitions are given by: \begin{equation} \label{eq1gen} \begin{array}{lll} \text{for every } x \in \xi_t, & \xi_t \to \xi_t \setminus \{x\} & \text{with rate } 1, \\ \text{for every } x \notin \xi_t, & \xi_t \to \xi_t \cup \{x\} & \text{with rate } \lambda \ |\{y \in \xi_t : \{x,y\} \in E\}|, \end{array} \end{equation} where for a set $A$, we write $|A|$ to denote its cardinality. Given $A \subset V$, we write $(\xi^A_t)_{t \ge 0}$ to denote the contact process started from the initial configuration equal to $A$. For $x \in V$, we write $(\xi^x_t)$ rather than $(\xi^{\{x\}}_t)$; also, rather than $(\xi^V_t)$, we write $(\xi^{\un{1}}_t)$. When we write $(\xi_t)_{t \geq 0}$, with no superscript, the initial configuration will either be clear from the context or unimportant. We often abuse notation and associate configurations $\xi \subset V$ with the corresponding indicator functions (that is, elements of $\{0,1\}^V$). The contact process can be thought of as a model for the spread of an infection in a population. Vertices of the graph (sometimes referred to as \textit{sites}) represent individuals. In a configuration $\xi \in \{0,1\}^V$, individuals in state 1 are said to be \textit{infected}, and individuals in state 0 are \textit{healthy}. Pairs of individuals that are connected by edges in the graph are in proximity to each other in the population. With this terminology, the dynamics can be described as follows. First, infected individuals \textit{recover} with rate 1. Second, an individual that is infected transmits its infection to a neighbouring site with rate $\lambda$ (assuming no multiple edges). %The empty configuration $\underline{0} \in\{0,1\}^V$ is a trap for $(\xi_t)$. For certain choices of the underlying graph $G$ and the parameter $\lambda$, it may be the case that the probability of the event $\{\underline{0} \text{ is never reached}\}$ is positive even if the process starts from finitely many infected sites. Whether or not this probability is positive does not depend on the set of initially infected sites, as long as this set is nonempty and finite. We say that the process \textit{survives} if this probability is positive; otherwise we say that the process \textit{dies out}. We begin by presenting some of the properties of the contact process for certain choices of the graph $G$, namely: the lattice $\mathbb{Z}^d$, regular infinite trees, and the finite counterparts of these graphs. For proofs of these properties and a detailed treatment of the topic, we refer the reader to \cite{lig85,lig99}. On $\Z^d$ (equipped with its usual nearest-neighbour graph structure), there exists a number $\lambda_c = \lambda_c(\Z^d)$ such that the following holds. If $\lambda \le \lambda_c$, then the contact process \emph{dies out}, meaning that for any finite initial configuration, the empty configuration $\underline{0}$ is almost surely eventually reached. On the other hand, if $\lambda > \lambda_c$, then the contact process \emph{survives strongly}: for any non-empty initial configuration, the event $\{\xi_t \neq \underline{0} \text{ for all } t\}$ has positive probability and, conditioned on this event, almost surely any vertex of $\Z^d$ becomes infected infinitely many times. The interest in the contact process on trees was prompted when it was discovered that death and strong survival are not the only possibilities in this case \cite{P}. For $d \geq 2$, let $T_d$ denote the infinite $(d+1)$-regular tree with a distinguished vertex $o$ called the root. The different phases of the process are captured by two constants $0 < \lambda_1(T_d) < \lambda_2(T_d)< +\infty$. If $\lambda \leq \lambda_1$, then the contact process dies out, while if $\lambda > \lambda_2$, then it survives strongly. If $\lambda \in (\lambda_1,\;\lambda_2]$, then the process \textit{survives weakly}. That is, if started with a non-empty finite initial configurantion, then the infection has positive probability of always being present on the graph, yet each individual site eventually becomes permanently healthy. If $G$ is a finite graph, then the contact process on $G$ dies out. This does not however rule out qualitative changes of the behaviour of the contact process as $\lambda$ varies, as we now describe. To be precise, for $A\subset V$, let us write $\uptau_G^A = \inf\{t: \xi^A_t = \underline{0}\}$ for the \textit{extinction time} of the process started from occupancy in $A$. We may omit the subscript $G$ when the context is clear enough, and simply write $\uptau$ when the contact process is started from full occupancy, that is, $\uptau = \uptau^{\un{1}}$. Consider the graph $\{0,\ldots,n\}^d$ (viewed as a subgraph of $\Z^d$) and the distribution of $\uptau$ for this graph, as $n$ goes to infinity. If $\lambda < \lambda_c(\Z^d)$, then $\uptau/\log n$ converges in probability to a constant \cite{durliu}, \cite{chencp}; see also Theorem 3.3 in \cite{lig99}. If $\lambda > \lambda_c$, then $\log E[\uptau]/n^d$ converges to a positive constant, and $\uptau/E[\uptau]$ converges in distribution to the unit exponential distribution \cite{dursc,tommeta,tomexp}. In particular, when $\lambda > \lambda_c$, the order of magnitude of the extinction time is exponential in the number of vertices of the graph; the process is said to exhibit \textit{metastability}, meaning that it persists for a long time in a state that resembles an equilibrium and then quickly moves to its true equilibrium ($\underline{0}$ in this case). Metastability for the contact process in this setting was also studied in \cite{eulalia} and \cite{schonmeta}. Finally, if $d=1$, it is also known that, if $\lambda = \lambda_c$, then $\uptau/n \to \infty$ and $\uptau/n^4 \to 0$ in probability \cite{dursctan}. For the case of finite trees, the picture is less complete, and the available results concerning the extinction time are contained in \cite{St}. Fix $d \geq 2$, let $T_d^h$ be the finite subgraph of $T_d$ defined by considering up to $h$ generations from the root and again take the contact process started from full occupancy on this graph, with associated extinction time $\uptau$. If $\lambda < \lambda_2$, then there exist constants $c, C>0$ such that $P(ch \leq \uptau \leq Ch) \to 1$ as $h \to \infty$. If $\lambda > \lambda_2$, then for any $\sigma < 1$, $P\left[\uptau > \exp({(\sigma d)^h})\right] \to 1 \text{ as } h \to \infty$. This implies that $\uptau$ is at least as large as a stretched exponential function of the number of vertices, $(d+1)^h$. As far as we know, no rigorous results are available concerning more general classes of graphs. \medskip For $n \in \N$ and $d>0$, let $\Lambda(n,d)$ be the set of all (connected) trees with $n$ vertices and degree bounded by $d$, and let $\cG(n,d)$ be the set of graphs having a spanning tree in $\Lambda(n,d)$. In this paper, we prove the following results. \begin{theorem} \label{thm1main1} For any $d \geq 2$ and $\lambda > \lambda_c(\Z)$, there exists $c>0$ such that \begin{equation}\label{eq:thm11}\lim_{n \to \infty}\; \inf_{T \in \Lambda(n,d)} P\left[\uptau_T \ge e^{cn}\right] = 1.\end{equation} In particular, \begin{equation}\label{eq:thm12}\liminf_{n \to \infty}\;\inf_{T \in \Lambda(n,d)} \frac{\log E[\uptau_T]}{n} \geq c.\end{equation} \end{theorem} \begin{theorem} \label{thm2main2} Let $d \geq 2$, $\lambda > \lambda_c(\Z)$, and $(G_n)_{n \in \N}$ be a sequence of graphs with $G_n \in \cG(n,d)$. The distribution of $\uptau_{G_n}/E[\uptau_{G_n}]$ converges to the unitary exponential distribution as $n$ tends to infinity. \end{theorem} Theorem~\ref{thm2main2} is a (weak) way of exposing the metastability of the contact process (see part (3) of Proposition~\ref{p:expalpha} for a finer statement; note also that from this statement, it is easy to extend the above theorems to more general initial configurations than full occupancy, with appropriate modifications). In Theorem~\ref{thm1main1}, one can replace $\Lambda(n,d)$ by the set of all graphs having a subgraph in $\Lambda(n,d)$, and in particular, one can replace $\Lambda(n,d)$ by $\cG(n,d)$. For instance, the above results cover the case of any sequence of increasingly large connected subsets of $\Z^d$. At the cost of requiring $\lambda > \lambda_c(\Z)$, we thus recover and extend previously mentioned results, without any strong assumption on the regularity of the graph. For such values of~$\lambda$, this shows in particular that on regular trees with finite depth, the extinction time is actually exponentially large in the number of vertices. \medskip This is however not quite the way in which we think our results are most useful. Rather, they are the basic ingredient of a general strategy to prove that the extinction time of the contact process is exponentially large in the number of vertices as soon as the infection parameter is above the natural critical value of the particular graphs we consider (instead of $\lambda_c(\Z)$). We now expose this strategy on certain random graphs whose degree distribution follows a power law. The case of finite homogeneous trees is discussed in \cite{cmmv}. We consider random graphs given by the configuration model with degree distribution equal to a power law. Let us explain what this means. For any $n \in \N$, we construct a graph $G_n$ on $n$ vertices. The vertex set is simply $\{1, \ldots, n\}$. The random set of edges will be constructed from a probability $p$ on $\{3,4,\ldots\}$ with the property that, for some $a>2$, $$0 < \liminf_{m\to\infty} m^a p(m) \le \limsup_{m\to\infty} m^a p(m) < \infty.$$ (We assume that $p$ is supported on integers larger than 2 because in \cite[Theorem~10.14]{vdH}, it is shown that under this assumption, it follows that $G_n$ is a connected graph with probability tending to 1 as $n \to \infty$.) We then let $d_1, \cdots, d_n$ be independent random variables distributed according to $p$. We want $\sum_{i=1}^n d_i$ to be even, so if it is not, we simply add 1 to one of the $d_i$ chosen uniformly at random. Next, from each vertex $i \in \{1, \ldots, n\}$ we place $d_i$ \textit{half-edges}; when two half-edges are connected, an edge is formed. We pair up the $d_1+\cdots+d_n$ half-edges in a random way that is uniformly chosen among all possibilities. %Note that this can produce multiple edges between two vertices and also loops (edges that start and finish at the same vertex). We then take the contact process with parameter $\lambda > 0$ on this random graph. Notice that the generator given by (\ref{eq1gen}) does not exclude the case of multiple edges or loops: the latter have no effect in the dynamics and the former increase the rate of transmission between vertices. Let us write $\mathbb{P}$ to denote a probability measure under which both the random graph and the contact process on this graph are defined. In \cite{CD}, it is shown that, for any $\lambda > 0$ and any $\delta > 0$, we have $\IP[\uptau_{G_n} \ge e^{n^{1-\delta}}] \to 1$ as $n \to \infty$. In particular, in the limit when the number of vertices tends to infinity, the critical infection parameter for these graphs is $0$. We strengthen this observation by showing: \begin{theorem} \label{thm1cd1} For any $\lambda > 0$, there exists $c > 0$ such that $$\mathbb{P}\left[\uptau_{G_n} \ge e^{cn} \right] \to 1 \text{ as } n \to \infty.$$ \end{theorem} Although it would be simple to deduce Theorem~\ref{thm1cd1} from Theorem \ref{thm1main1} assuming $\lambda > \lambda_c(\Z)$, we stress again that Theorem~\ref{thm1cd1} covers any non-zero infection parameter. We think that Theorem \ref{thm1cd1} is true for all $a>1$, but we only give the proof for $a > 2$, which is the harder case (when we increase $a$, the degrees of the vertices become stochastically smaller, so the graph becomes less connected). \medskip For finite boxes of $\Z^d$, the proof that the extinction time is exponential in the number of vertices relies on a coarse-graining argument. This coarse-graining enables to map the initial contact process into a coarse-grained (discrete-time) contact process with an increasingly large infection parameter. The remarkable feature of~$\Z^d$ is its scale invariance, which ensures that the coarse-grained graph is still $\Z^d$ (or rather, a finite box of $\Z^d$). Now, simple percolation arguments show that on finite boxes of $\Z^d$, the time of survival is exponential in the number of vertices if the infection parameter is sufficiently large, say larger than $\lambda_{\text{target}}$. To sum up, the proof for finite boxes of $\Z^d$ consists in defining a coarse-graining scheme, and then in fixing a finite length of coarse-graining such that the coarse-grained system has infection parameter larger than $\lambda_{\text{target}}$. For $G_n$ given by the configuration model, coarse-grained blocks will consist of certain \emph{stars}, that is, vertices with a given large number of neighbours. The difficulty in trying to adapt the strategy to these graphs (or to finite homogeneous trees) is that there is no easy scale invariance as on $\Z^d$. It then becomes a very delicate matter to control the geometry of the coarse-grained graph, and thus to define a suitable equivalent of $\lambda_{\text{target}}$. However, Theorem~\ref{thm1main1} roughly tells us that \emph{we do not need to control this geometry}, and that we can choose $\lambda_{\text{target}} = \lambda_c(\Z)$. The approach in \cite{CD} is also based on a coarse-graining procedure. There, the question of controlling the coarse-grained geometry was bypassed by choosing the coarse-grained scale so large as to ensure that the coarse-grained graph was a complete graph. Since the diameter of the graphs $G_n$ goes to infinity, this cannot be ensured unless the length scale of the coarse-graining diverges. In other words, in this approach, stars should have more and more vertices as $n$ increases, and the number of points in the coarse-grained scale must thus be $o(n)$. With our approach, we can choose instead a large but \emph{fixed} size for the relevant stars in the graph, so that the coarse-grained graph still contains of order $n$ sites, and Theorem~\ref{thm1cd1} follows from this construction. \medskip We close this introduction by pointing to other related works and questions. To the best of our knowledge, the rigorous study of the behaviour of the contact process on random graphs with a power-law degree distribution began with \cite{BBCS}. The graph studied there is obtained by a generalization of the \emph{preferential attachment} mechanism introduced in \cite{ab,br}. Vertices are added one by one. When a new vertex is added, it is connected to $m$ of the older vertices. These are chosen independently as follows: with probability $\alpha$, the vertex is chosen uniformly; with probability $1-\alpha$, it is chosen with a probability proportional to its degree. That the degree distribution of these graphs follows a power law was proved in \cite{cf}. The structure of these graphs is more difficult to analyse than that of the configuration model, and \cite{BBCS} could only show that the extinction time is at least $\exp(n^{\beta})$ for some $\beta < 1$ depending on $\alpha$ (where $n$ is the number of vertices). It would be interesting to investigate whether the results presented here (possibly in combination with the recent \cite{BBCS2}) enable to show that the extinction time is actually of the order of $\exp(cn)$ for some constant $c$. In another direction, \cite{vM} computes very precise asymptotics for the extinction time of the contact process on the complete graph. The question of whether or not the critical infection parameter is zero for a given sequence of graphs still lacks a unified mathematical treatment. Results such as \cite{ dj, contact_reg} point towards the conjecture that the epidemic threshold of a sequence of random graphs is given by the lower critical infection parameter of the local graph limit of the sequence (see \cite{contact_reg} for a more detailed discussion on this). The local limit of a sequence of random graphs given by the configuration model are Galton-Watson trees. However, we do not know of a good criterion for deciding whether the lower critical infection parameter of a given Galton-Watson tree is $0$. It is suggested in \cite{tail} that this threshold is zero as soon as the degree distribution decays slower than exponentially. Beyond this, physicists have investigated finite-size corrections to the asymptotic behaviour discussed here, see for instance \cite{compare}. \medskip \noindent \textbf{Organization of the paper.} Section~\ref{s:remind} is a brief reminder on some properties of the contact process that will be useful for our purposes. In Section \ref{s:metastab}, we show a weaker version of Theorem~\ref{thm1main1}, which states that the expectation of the extinction time is larger than $e^{cn^{\alpha}}$ for some $\alpha > 0$. In order to do this, we consider two cases: either the tree contains a large segment, or it contains a large number of disjoint smaller segments. In the first case, the result follows from the known behavior of the extinction time on finite intervals of $\Z$. In the second case, we adapt an argument of \cite{CD} and show that, even if the segments are not too large, the time scale of extinction in individual segments is large enough for the infection to spread to other, possibly inactive, segments, so that the segments can jointly sustain activity for the desired amount of time. At this point, using a general metastability argument from \cite{tommeta}, we prove Theorem \ref{thm2main2} (for completeness, we include a version of the argument of \cite{tommeta} in an Appendix). Given a tree $T \in \Lambda(n,d)$, we decompose it into two subtrees $T_1, T_2$ by removing an edge; we argue that this can be done so that $T_1$ and $T_2$ both contain a non-vanishing proportion of the vertices of $T$. In Section \ref{s:comparison2}, we compare the contact process $(\xi_t)_{t \ge 0}$ on $T$ to a pair of processes $(\zeta_{T_1,t})_{t \ge 0}$ on $T_1$ and $(\zeta_{T_2,t})_{t \ge 0}$ on $T_2$. The process $\zeta_{T_1}$ evolves as a contact process on $T_1$ until extinction. Once extinct, the process stays extinct for some time, and then rises from the ashes (we call it a \emph{Phoenix contact process}). This rebirth of the process reflects the fact that, as long as the true process $\xi$ has not died out, the tree $T_1$ constantly receives new infections that can restore its activity. The process $\zeta_{T_2}$ evolves independently, following the same rules. We show that the true process $\xi$ dominates $\zeta_{T_1} \cup \zeta_{T_2}$ up to the extinction of $\xi$, with probability close to $1$. With this comparison at hand, we argue that, modulo a factor that is polynomial in the number of vertices, the expected extinction time for $T$ is larger than the product of the expected extinction times for $T_1$ and $T_2$. The polynomially growing error term can be washed away using the lower bound $e^{cn^\alpha}$ mentioned in the previous paragraph. We thus obtain part \eqref{eq:thm12} of Theorem~\ref{thm1main1}, from which we deduce part \eqref{eq:thm11} using attractiveness. In Section \ref{s:discrete}, we re-state some of the results explained above for a discrete-time version of the contact process. Finally, we prove Theorem~\ref{thm1cd1} in Section \ref{s:nsw}. %we turn to the NSW random graph $G^n$. We present an algorithm that finds with high probability a certain subgraph $G'$ of $G^n$ containing a large quantity of vertices with degree above a certain threshold $M$ ($M$ depends on $\lambda$ but not on $n$). The algorithm also guarantees that most of these vertices are not isolated from other vertices with degree above $M$. Next, a tree $T$ and a mapping $\theta$ from the vertices of $T$ to those of $G'$ are given. $\theta$ has the properties that, for any $x$, $\theta(x)$ has degree larger than $M$ and, if $x, y$ are neighbors in $T$, then $\theta(x)$ and $\theta(y)$ are not far from each other in $G'$. By considering $(\xi_t \cap G')$ only at values of $t$ that are integer multiples of a large constant $R$, we then define a discrete-time version of the contact process on $T$, denoted $(\eta_k)_{k \geq 1}$. The construction is such that, if a vertex $\theta(x)$ of $G'$ has many infected neighbors in the configuration $\xi_{k\cdot R}\cap G'$, we have $\eta_k(x) = 1$. The key idea is that, on $G'$, around vertices of degree above $M$, the infection has high probability of persisting for more than $R$ units of time, and during this period, of propagating far enough that other vertices of high degree are reached; this is then interpreted as a transmission in the process $(\eta_k)$. Even if the parameter $\lambda$ is very small, we can construct $T$ and $\theta$ so that, if $n$ is large enough, $(\eta_k)$ has parameter $\lambda'$ larger than the critical parameter for the one-dimensional contact process. We then apply our results to conclude that $(\eta_k)$, and consequently $(\xi_t)$, survive for a long time. \medskip \noindent \textbf{Notations.} For $x \in \R$, we write $\lfloor x \rfloor$ for the integer part of $x$. When talking about the size of a graph, we always mean its number of vertices. % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % \section{A reminder on the contact process} \label{s:remind} \setcounter{equation}{0} \noindent \textbf{Graphical construction.} We start this section by presenting the graphical construction of the contact process. Fix a graph $G = (V,E)$ and $\lambda > 0$. We take the following family of independent Poisson point processes on $[0,\infty)$: $$\begin{array}{ll} (R^x): x \in V &\text{with rate } 1;\\ (N^e): e \in E &\text{with rate } \lambda.\end{array}$$ Let $H$ denote a realization of all these processes. Given $x,y\in V,\; s \leq t$, we say that $x$ and $y$ are connected by an \textit{infection path in $H$} (and write $(x,s)\leftrightarrow (y,t)$ in $H$) if there exist times $t_0 = s < t_1 < \cdots < t_k = t$ and vertices $x_0 = x, x_1, \ldots, x_{k-1} = y$ such that \begin{itemize} \item[$\bullet$] $R^{x_i} \cap (t_i,\; t_{i+1}) = \emptyset$ for $i = 0, \ldots, k - 1$; \item[$\bullet$] $\{x_i,x_{i+1}\}\in E$ for $i = 0, \ldots, k-2$; \item[$\bullet$] $t_i \in N^{\{x_{i-1}, x_i\}}$ for $i = 1, \ldots, k-1$. \end{itemize} Points of the processes $(R^x)$ are called \textit{recovery marks} and points of $(N^e)$ are \textit{links}; infection paths are thus paths that traverse links and do not touch recovery marks. $H$ is called a \textit{Harris system}; we often omit dependence on $H$. For $A, B \subset V$, we write $A\times\{s\} \leftrightarrow B \times \{t\}$ if $(x,s)\leftrightarrow (y,t)$ for some $x \in A$, $y \in B$. We also write $A\times \{s\} \leftrightarrow (y,t)$ and $(x,s) \leftrightarrow B\times\{t\}$. Finally, given another set $C \subset V$, we write $A \times \{s\} \leftrightarrow B \times \{t\}$ \textit{inside} $C$ if there is an infection path from a point in $A\times \{s\}$ to a point in $B\times\{t\}$ and the vertices of this path are entirely contained in $C$. Given $A \subset V$, put \begin{equation}\label{eq1harris} \xi^A_t(x) = \mathds{1}_{\{A \times \{0\} \leftrightarrow (x,t)\}} \text{ for } x \in V,\; t \geq 0\end{equation} (here and in the rest of the paper, $\mathds{1}$ denotes the indicator function). It is well-known that the process $(\xi^A_t)_{t\geq 0} = (\xi^A_t(H))_{t\geq 0}$ thus obtained has the same distribution as that defined by the infinitesimal generator (\ref{eq1gen}). The advantage of (\ref{eq1harris}) is that it allows us to construct in the same probability space versions of the contact processes with all possible initial distributions. From now on, we always assume that the contact process is constructed from a Harris system, and will write $P_{G,\lambda}$ to refer to a probability measure under which such a system (on graph $G$ and with rate $\lambda$) is defined; we usually omit $G,\lambda$.\medskip \noindent \textbf{Time-shifted process.} Given $s\ge 0$, $B \subset V$ and a Harris system $H$, define $(\xi^{B,s}_t)_{t \ge s}$ by \begin{equation} \label{e:def:timeshift} \xi^{B,s}_t(x) = \mathds{1}_{\{B \times \{s\} \leftrightarrow (x,t)\}} \text{ for } x \in V,\; t \geq s. \end{equation} It can then be readily checked that \begin{equation}\label{eq:inttime} \text{ for all } A \subset V \text{ and } 0 \le s \le t,\; \xi^A_t = \xi^{\xi^A_s, s}_t. \end{equation} From this it follows that \begin{equation}\text{ for all } A, B \subset V \text{ and } 0 \le s \le t, \text{ if } \xi^A_s = \xi^B_s, \text{ then } \xi^A_t = \xi^B_t. \label{eq:coupaf} \end{equation}\medskip \noindent \textbf{Attractiveness.} An immediate consequence of (\ref{eq1harris}) is that for all $A \subset V$ and $t \ge 0$, we have $\xi^A_t = \cup_{x \in A} \xi^x_t.$ From this we obtain the \textit{attractiveness} property of the contact process: \begin{equation} \text{for all } A \subset B \subset V \text{ and } t \ge 0,\; \xi^A_t \subset \xi^B_t. \label{eq:attractd} \end{equation} Using (\ref{eq:coupaf}) and (\ref{eq:attractd}), we see that, if for some $x \in V$ and $s \ge 0$ we have $\xi^x_s = \xi^{\underline{1}}_s$, then for any $A \subset V$ that contains $x$ and $t \ge s$, we must have $\xi^A_t = \xi^{\underline{1}}_t$. Together with a union bound, this yields \begin{equation} \label{coupun} P\left[ \xi^A_t \neq \underline{0},\; \xi^A_t \neq \xi^{\underline{1}}_t\right] \le \sum_{x \in A} P\left[ \xi^ x_t \neq \underline{0},\; \xi^x_t \neq \xi^{\underline{1}}_t\right]. \end{equation}\medskip \noindent \textbf{Duality.} Fix $A \subset V,\; t > 0$ and a Harris system $H$. Let us define the \textit{dual process} $(\hat \xi^{A, t}_s)_{0 \leq s \leq t}$ by $$\hat \xi^{A,t}_s(y) = \mathds{1}_{\{(y,t-s)\leftrightarrow A \times \{t\} \text{ in } H\}}.$$ If $A = \{x\}$, we write $(\hat \xi^{x,t}_s)$. This process satisfies two important properties. First, its distribution (from time 0 to $t$) is the same as that of a contact process with same initial configuration. Second, it satisfies the \textit{duality equation} \begin{equation}\xi^A_t \cap B \neq \emptyset \text{ if and only if } A \cap \hat \xi^{B,t}_t \neq \emptyset. \end{equation} In particular, $\xi^{\underline 1}_t(x) = 1 \text{ if and only if } \hat \xi^{x,t}_t \neq \underline{0}.$ We will also need the fact that \begin{equation} \label{eq:dualAB} \text{if } \xi^A_t = \xi^{\underline{1}}_t \text{ and } \hat \xi^{B,t}_t \neq \underline{0}, \text{then } \xi^A_t \cap B \neq \varnothing. \end{equation} \medskip \noindent \textbf{Contact process on an interval.} We now gather some classical results about the contact process on the graph with vertex set $\{0, \ldots, N\}$ (where $N \in \Z_+$) and nearest-neighbour edges. We start defining, for $x, y \in \{0, \ldots, N\}$ and the contact process on $\{0, \ldots, N\}$, $$\sigma^N_{x \to y} = \inf\{t: \xi^x_t(y) = 1\}.$$ \begin{proposition} \label{cpinterval} For any $\lambda > \lambda_c(\Z)$, there exist $\ov{c}_1 > 0$ such that the following holds. For any $N$ and any $x \in \{0, \ldots, N\}$, \begin{equation}\label{eq:cpinterval1} P\Ll[ \max\left(\sigma^N_{x \to 0},\; \sigma^N_{x \to N} \right) < \frac{N}{\ov{c}_1}\Rr] > \ov{c}_1 \end{equation} and \begin{equation} \label{eq:cpinterval2} P\Ll[ \max\left(\sigma^N_{x \to 0},\; \sigma^N_{x \to N} \right) \ge \frac{N}{\ov{c}_1}, \ \xi^x_{N/\ov{c}_1} \neq \un{0} \Rr] \le e^{-N}. \end{equation} Additionally, for any $N$ and any $t \ge 0$, \begin{equation} \label{eq:cpinterval3} P\Ll[ \uptau^{\underline{1}}_{\{0,\ldots, N\}} \le t \Rr] \le t e^{-\ov{c}_1 N}. \end{equation} \end{proposition} This follows from the classical renormalization argument that compares the contact process with supercritical oriented percolation, see for instance the proof of \cite[Corollary~VI.3.22]{lig85}. \begin{rem} \label{r:coupling} A crucial aspect of the contact process on an interval is the observation that for every starting point $x \in \{0,\ldots,N\}$, we have $\xi_{t}^{x} = \xi_{t}^{\un{1}}$ for every $t \ge \max\left(\sigma^N_{x \to 0},\; \sigma^N_{x \to n} \right)$. In other words, when the contact process started from $x$ has reached the extremal points of the interval, it is coupled with the contact process that was started from the fully occupied configuration. To see this, assume that there exists an infection path $\gamma_1$ from $(x,0)$ to $(0,\sigma^N_{x \to 0})$ and an infection path $\gamma_2$ from $(x,0)$ to $(N,\sigma^N_{x \to N})$ (i.e.\ assume that the random times are finite). For any two sites $y$ and $z$ and $t \ge \max(\sigma^N_{x \to 0} , \sigma^N_{x \to N})$, let $\gamma'$ be an infection path from $(y,0)$ to $(z,t)$. Since the graph is an interval, the infection path $\gamma'$ is forced to intersect $\gamma_1$ or $\gamma_2$, and in both cases, this implies the existence of an infection path from $(x,0)$ to $(z,t)$. \end{rem} \begin{corollary} Assume $\lambda > \lambda_c(\Z)$. Then, for any $N$, any $t \ge N/\ov{c}_1$ and any non-empty $A \subset \{0, \ldots, N\}$, \begin{equation} \label{eq:cpinterval4} P_{\{0,\ldots,N\},\lambda}\Ll[ \xi^A_t =\xi^{\underline{1}}_t \Rr] \ge \ov{c}_1,\qquad P_{\{0,\ldots,N\},\lambda}\Ll[ \xi^A_t =\xi^{\underline{1}}_t \neq \underline{0} \Rr] \ge \ov{c}_1 - te^{-\ov{c}_1 N}. \end{equation} Additionally, for any $A \subset \{0,\ldots,N\}$ and any $t \ge N/\ov{c}_1$, \begin{equation} \label{eq:cpinterval5} P_{\{0,\ldots,N\},\lambda}\Ll[ \xi^A_t \neq \underline{0},\; \xi^A_t \neq \xi^{\underline{1}}_t\Rr] \leq |A| e^{-N}. \end{equation} \end{corollary} \begin{proof} (\ref{eq:cpinterval4}) follows from fixing $x\in A$ and applying the comment that follows (\ref{eq:attractd}), Remark \ref{r:coupling}, (\ref{eq:cpinterval1}) and (\ref{eq:cpinterval3}). (\ref{eq:cpinterval5}) follows from Remark \ref{r:coupling}, (\ref{coupun}) and (\ref{eq:cpinterval2}). \end{proof} In the course of the proof, we will need a slightly more technical result on contact processes on intervals. For the sake of clarity, we prefer to derive it now, although its motivation will become clear only later. For $\lambda > 0,\; G = (V,E), \;A \subset V$ and $t > 0$, define $$p(A, t) = p_{G}(A, t) = P_{G, \lambda}\left[\xi^A_t = \xi^{\underline{1}}_t \neq \underline{0}\right].$$ Obviously, \begin{equation} \label{eq:cpinterval6}p(V,t) = P\Ll[\uptau_G > t\Rr]. \end{equation} Also, as a consequence of (\ref{eq:dualAB}), for any $A, B \subset V$ and $t > 0$, \begin{equation} \label{eq:dualABh} P\Ll[\xi^ A_t \cap B \neq \varnothing \Rr] \ge P\Ll[\xi^A_t = \xi^{\underline{1}}_t\Rr] - P\Ll[\hat \xi^B_t = \underline{0}\Rr] \ge p(A, t) + p(B,t)- 1. \end{equation} \begin{lemma}\label{lem:pprop} For any $\lambda > \lambda_c(\Z)$, $N \in \Z_+$ and $t_0 \ge N/\ov{c}_1$, the following holds. \begin{itemize} \item[(i.)] For any $A \subset \{0,\ldots, N\}$ satisfying $p(A,t_0) \ge 1-\epsilon$ and any $\kappa > 0$, $$P_{\{0, \ldots, N\},\lambda}\left[\;p(\xi^A_{t_0}, t_0) > 1-\kappa\;\right] \ge 1 - \epsilon - \frac{1}{\kappa}\left( 2t_0e^{-\bar c_1 N} + Ne^{-N} \right).$$ \item[(ii.)] For any non-empty $A \subset \{0,\ldots, N\}$ and any $\kappa > 0$, $$P_{\{0, \ldots, N\},\lambda}\left[\;p(\xi^A_{t_0}, t_0) > 1-\kappa\;\right] \ge \ov{c}_1 - \frac{1}{\kappa}\left( 2t_0e^{-\bar c_1 N} + Ne^{-N} \right).$$ \end{itemize} \end{lemma} \begin{proof} Recalling the definition of the time-shifted process \eqref{e:def:timeshift}, we observe that $$\begin{aligned} &P\left[p(\xi^{\underline{1}}_{t_0}, t_0) \le 1 - \kappa\right] = P\left[1-p(\xi^{\underline{1}}_{t_0}, t_0) > \kappa \right]\le \frac{1}{\kappa}E\left[1 - p(\xi^{\underline{1}}_{t_0}, t_0) \right] \\&= \frac{1}{\kappa}\sum_{B} P\left[\xi^{\underline{1}}_{t_0} = B \right] \cdot (1 - p(B, t_0))\\ &= \frac{1}{\kappa} \sum_B P[\xi^{\underline{1}}_{t_0} = B] \cdot P\left[\xi^{B,t_0}_{2t_0} = \underline{0} \text{ or } \xi^{B, t_0}_{2t_0} \neq \xi^{\underline{1}, t_0}_{2t_0}\right]\\ &= \frac{1}{\kappa} \sum_B P[\xi^{\underline{1}}_{t_0} = B] \cdot \left( P\left[\xi^{B,t_0}_{2t_0} = \underline{0}\right] + P\left[\xi^{B,t_0}_{2t_0} \neq \underline{0},\; \xi^{B, t_0}_{2t_0} \neq \xi^{\underline{1}, t_0}_{2t_0}\right] \right)\\ &\le \frac{1}{\kappa} \left(P\left[\xi^{\underline{1}}_{2t_0} = \underline{0}\right] + \sum_B P\left[\xi^{\underline{1}}_{t_0} = B \right] P\left[\xi^{B, t_0}_{2t_0} \neq \underline{0},\;\xi^{B, t_0}_{2t_0} \neq \xi^{\underline{1}, t_0}_{2t_0} \right]\right), \end{aligned} $$ where we have used the Markov inequality in the first inequality and (\ref{eq:inttime}) in the last inequality. By (\ref{eq:cpinterval3}) and (\ref{eq:cpinterval5}) respectively, $$P\left[\xi^{\underline{1}}_{2t_0} = \underline{0}\right] \leq 2t_0 e^{-\bar c_1 N} \quad \text{ and } \quad P\left[\xi^{B, t_0}_{2t_0} \neq \underline{0},\;\xi^{B, t_0}_{2t_0} \neq \xi^{\underline{1}, t_0}_{2t_0} \right] \le N e^{-N},$$ so we get $$P\Ll[p(\xi^{\underline{1}}_{t_0}, t_0) \le 1-\kappa\Rr] \le \frac{1}{\kappa}\left( 2t_0e^{-\bar c_1 N} + Ne^{-N} \right).$$ Parts (i.) and (ii.) now follow respectively from the definition of $p$ and (\ref{eq:cpinterval4}). \end{proof} % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % \section{Metastability} \label{s:metastab} \setcounter{equation}{0} In this section, we show that for $\lambda > \lambda_c(\Z)$, the extinction time of the contact process is at least $e^{c n^{\alpha}}$ for some $\alpha > 0$, uniformly over $T \in \Lambda(n,d)$. This is clear by Proposition~\ref{cpinterval} if the tree has diameter at least $n^\alpha$. Else, we rely on a recursive decomposition of the tree into many subtrees each of which has size at least $\sqrt{n}$. We then pick long intervals (of logarithmic size) inside each of these trees, and study how these can sustain the infection. For a suitable choice of the parameters, the time it takes for such an interval, isolated from the rest of the graph, to turn extinct, is much larger than the time it takes for the infection to travel from one interval to another, since the diameter of the whole graph is assumed small. Over time, the number of infected intervals can be compared to a random walk on the integers with a drift to the right. Analyzing this walk gives the desired result. Using this construction, we also show metastability of the contact process, in the sense that after time $n^2$, either the contact process is extinct, or it is equal to the contact process that was started from full occupancy (and thus the initial configuration is forgotten). Since $n^2$ is much smaller than the extinction time, this is a quantitative way of presenting the metastability of the contact process, and indeed we will conclude the section by proving Theorem~\ref{thm2main2}. \medskip We begin with the following basic graph-theoretic observation, on which our recursive decomposition of the tree is based. \begin{lemma} \label{lem1} For a tree $T \in \Lambda(n,d)$, there exists an edge whose removal separates $T$ into two subtrees $T_1$ and $T_2$ both of size at least $\lfloor n/d \rfloor$. \end{lemma} \begin{proof} Associate to each edge the value of the smallest cardinality of the two subtrees resulting from the edge's removal. Let $\{x,y\} $ be an edge having maximal value. We suppose that the subgraph $T_y$ containing vertex $y$ is the smaller and that the value of its subtree is no more than $\lfloor n/d \rfloor - 1$. Let the remaining edges of vertex $x$ be $\{x, x_1\}, \ \{x, x_2\}, \cdots \{x, x_r\} $, where $r \leq d-1$. Let $T_j$ be the subtree containing $x_j$ obtained by removing the edge $\{x, x_j\}$, and let $n_j$ be its cardinality. By maximality, all the $n_j$ must be no more than $\lfloor n/d \rfloor - 1$, but we also have $$ |T_y| = \Ll| T \setminus \Ll(\{x\} \cup T_1 \cup \cdots \cup T_r\Rr) \Rr| = n-(1 + n_1 + n_2 + \cdots +n_r) \leq \lfloor n/d \rfloor - 1. $$ That is, $n \le (d-1) (\lfloor n/d \rfloor - 1) + \lfloor n/d \rfloor \le n -(d-1)$, a contradiction (the case $d = 1$ being trivial). \end{proof} \begin{proposition} \label{p:expalpha} For any $d > 0$ and $\lambda > \lambda_c(\Z)$, there exists $\alpha > 0$ and $\ov{c}_2 > 0$ such that the following holds. \begin{enumerate} \item For any $n$ large enough, any $T \in \Lambda(n,d)$, any non-empty $A \subset T$, one has $$ P\Ll[ \uptau^A \ge e^{n^\alpha} \Rr] \ge \ov{c}_2. $$ In particular, $E[\uptau^A] \ge \ov{c}_2 e^{n^\alpha}$. \item Moreover, $$ P\Ll[ \uptau \ge e^{n^{\alpha}} \Rr] \ge 1-e^{-n^{{\alpha}}}, $$ where we recall that we write $\uptau$ as a shorthand for $\uptau^{\un{1}}$. \item For $n$ large enough, any $G = (V, E) \in \cG(n,d)$ and any $A \subset V$, $$P_{G, \lambda}\Ll[ \xi^{A}_{n^2} \neq \underline{0},\;\xi^A_{n^2} \neq \xi^{\underline{1}}_{n^2}\Rr] \le e^{-n^{\alpha/2}}.$$ \end{enumerate} \end{proposition} From now on, $d$ is fixed and we consider a tree $T$ of maximal degree $d$ and size $n \to \infty$. Let $\beta > 0$ to be determined later, not depending on $n$. Applying Lemma~\ref{lem1} repeatedly $\beta \log n$ times, we obtain $L_n = 2^{\beta \log n}$ disjoint subtrees each of size at least $\frac{n}{{(2d)}^{\beta \log n}} \geq \sqrt{n}$, provided $\beta \le 1/(2\log(2d))$ (for clarity, we simply assume that $L_n$ is an integer, without writing that the integer part should be taken). We write $T_1,\ldots, T_{L_n}$ for the trees thus obtained. Since the tree $T$ has maximal degree bounded by $d$, so do the subtrees $(T_j)$. Now, the size of a tree with maximal degree $d$ is at most $$ 1+d+\ldots+d^\textsf{diam} = \frac{d^{\textsf{diam}+1}-1}{d-1}, $$ where $\textsf{diam}$ denotes its diameter. As a consequence, for $n$ large enough, each $T_j$ must have a diameter at least $\frac{\log n}{4 \log d}$, and thus contain a path of $\frac{\log n}{4 \log d}$ distinct vertices. We write $I_j$ to denote such a path, which we identify with an interval of length $\frac{\log n}{4 \log d}$. \medskip In what follows, we will distinguish between the two possibilities: \begin{enumerate} \item[(A)] the diameter of $T$ is at least $n^{\beta}$, \item[(B)] the diameter of $T$ is less than $n^\beta$, \end{enumerate} \begin{proof}[Proof of parts (1-2) of Proposition~\ref{p:expalpha}] Assume that the tree $T$ satisfies (A). For part (1), by attractiveness, it suffices to consider initial configurations with a single occupied site $x$; we now fix $x$. Condition (A) ensures that one can find an interval of length $k \ge n^\beta$ on $T$; we write $[y, z]$ to denote such an interval, with $y$ and $z$ its endpoints. We also write $[x, y]$ to denote the shortest path (in graph distance) starting at $x$ and ending at $y$. Let $\sigma = \inf\{t: \xi^x_t(y) = 1\}$. Then, \begin{equation} \label{eq:caseA}P\Ll[\xi^x_{\exp(\ov{c}_1 n^\beta/2)} \neq \underline{0} \Rr] \ge P\Ll[\sigma < \infty,\; \xi^{y, \sigma}_{\sigma+ \exp(\ov{c}_1 n^\beta/2)} \neq \underline{0} \Rr].\end{equation} Using (\ref{eq:cpinterval1}) on the contact process on $[x,y]$, we have $P\Ll[\sigma < \infty\Rr] > \ov{c}_1$. Using (\ref{eq:cpinterval4}) on the contact process on $[y,z]$, we have $$ P\Ll[ \left.\xi^{y, \sigma}_{\sigma+ \exp(\ov{c}_1 n^\beta/2)} \neq \underline{0} \;\right| \sigma < \infty\Rr]\ge \ov{c}_1 - e^{\ov{c}_1 n^\beta/2} \cdot e^{-\ov{c}_1 k}.$$ Thus the right-hand side of (\ref{eq:caseA}) is larger than $\ov{c}_1^2/2$ when $n$ is large enough, proving part (1). Part (2) follows from applying (\ref{eq:cpinterval3}) to the restriction of the contact process on $[y,z]$. We now assume that the graph satisfies (B), and adapt an approach due to \cite{CD}. For any $B \subset I_i$, we write $(\xi^{B}_{i,t})_{t \ge 0}$ for the contact process on $I_i$ with initial configuration $B$, that is, $$\xi^B_{i,t}(x) = \mathds{1}_{\{B \times \{0\} \leftrightarrow (x,t) \text{ inside } I_i\}}, \qquad x\in I_i, t\ge 0.$$ When we write $(\xi_t)$ (or $(\xi^{\underline{1}}_t)$, or $(\xi^A_t)$ with $A \subset T$) with only the subscript corresponding to time, we mean the contact process on the whole graph $T$. Obviously, for any $A \subset T$, \begin{equation}\label{eq:propCoup}\xi^A_t \supset \cup_i \; \xi^{A \cap I_i}_{i, t} \qquad \text{ and } \qquad (\xi^{A \cap I_i}_{i,t})_{t \ge 0} \text{ for } i = 1, \ldots, L_n \text{ are independent.}\end{equation} In accordance with the previous section, we write $$ p_{I_i}(B, t) = P\Ll[ \xi^{B}_{i,t} = \xi^{\un{1}}_{i,t} \neq \un{0} \Rr], \qquad B \subset I_i,\; t > 0. $$ For $1 \le i \le L_n$, we say interval $I_i$ is \textit{good at time} $t$ if $p_{I_i}(\xi_t \cap I_i,\; 2n^\beta/\ov{c}_1) > 1 - n^{-2\beta}$. We interpret this as meaning that the set of infected sites $\xi_{t} \cap I_i$ is ``large enough''. Here ``large enough'' means that, if this set is taken as the initial configuration for a contact process on $I_i$, then it gives probability higher than $1 - n^{-2\beta}$ to the event that the infection is sustained for time $2n^\beta/\ov{c}_1$ and couples with the comparison process which evolves in $I_i$ starting from full occupancy. We put $t_k = (2n^\beta/\ov{c}_1)k$ and define $Y_{i,k}$ as the indicator function that interval $I_i$ is good at time $t_k$. We finally define $X_k = \sum_{i=1}^{L_n} Y_{i,k}$ as the number of good intervals at time $t_k$. \begin{lemma} \label{lem:auxTres} Assume $\beta < \frac{\ov{c}_1}{20\log d}$. Then, if $n$ is large enough, the following holds. \begin{itemize} \item[(i.)] on $\{\xi_{t_k} \supset I_i\}$, $Y_{i, k} = 1$;\medskip \item[(ii.)] for any $x \ge 0$, $P\Ll[X_{k+1} \le X_k -x \;|\; \xi_{t_k}\Rr] \le \P\Ll[ \mathsf{Bin}(L_n, 2n^{-2\beta}) \ge x\Rr]$, where $\mathsf{Bin}(m,q)$ denotes a Binomial random variable with parameters $m$ and $q$;\medskip \item[(iii.)] on $\{\xi_{t_k} \neq \underline{0},\; X_k < L_n\}$, $P\Ll[\;X_{k+1} \ge X_k + 1 \:|\; \xi_{t_k}\;\Rr] \ge \ov{c}_1^2/2.$\medskip \end{itemize} \end{lemma} \begin{proof} For (i.), from (\ref{eq:cpinterval6}) we get that, on $\{\xi_{t_k} \supset I_i\}$, \begin{equation*} p_{I_i}(I_i,\; 2n^\beta/\ov{c}_1) > 1 - \frac{2n^\beta}{\ov{c}_1}\cdot e^{-\ov{c}_1 \frac{\log n}{4\log d}} > 1- n^{-2\beta} \end{equation*} when $\beta < \frac{\ov{c}_1}{20 \log d}$ and $n$ is large, so that $Y_{i, k} = 1$. (ii.) will follow from (\ref{eq:propCoup}) and the fact, which we now prove, that on $\{Y_{i,k} = 1\}, \;P[Y_{i, k+1} = 1\;|\; \xi_{t_k}] > 1- 2n^{-2\beta}.$ This is a consequence of attractiveness and applying Lemma \ref{lem:pprop}(i.) with the choice of variables: $$A = \xi_{t_k} \cap I_i, \quad N = |I_i| = \frac{\log n}{4\log d},\quad t_0 = \frac{2n^\beta}{\ov{c}_1}, \quad\epsilon = \kappa = n^{-2\beta}.$$ The first requirement that $t_0 > \frac{N}{\ov{c}_1}$ is satisfied since $\frac{2n^\beta}{\ov{c}_1} > \frac{\log n}{4 \ov{c}_1 \log d}$ when $n$ is large. The second requirement that $p_{I_i}(A,t_0) \ge 1-\epsilon$ holds since we restrict our attention to the event $\{Y_{i,k} = 1\}$. The conclusion of the lemma then reads $$P\Ll[Y_{i,k+1} = 0 \;|\;\xi_{t_k}\Rr] \le n^{-2\beta} + n^{2\beta}\left(\frac{4n^\beta}{\ov{c}_1}\cdot e^{-\ov{c}_1 \frac{\log n}{ 4\log d}} + \frac{\log n}{4\log d}\cdot e^{-\frac{\log n}{4 \log d}}\right)$$ and the right-hand side is smaller than $2n^{-2\beta}$ if $\beta < \frac{\ov{c}_1}{20\log d}$ and $n$ is large enough. (ii.) is now proved. Let us prove (iii.). On the event $\{\xi_{t_k} \neq \underline{0},\; X_k < L_n\}$, we can find $x$ and $i$ such that $\xi_{t_k}(x) = 1$ and $Y_{i, k} = 0$. Fix $y \in I_i$ and let $\sigma = \inf\{t > t_k: \xi^{x, t_k}_t(y)= 1\}$. Note that, since it is assumed that the diameter of the graph is less than $n^\beta$, we can use Proposition \ref{cpinterval}(i.) to get $P[\sigma < t_k + n^\beta/\ov{c}_1] > \ov{c}_1$. Then, $$P\Ll[Y_{i, k+1} = 1\;|\; \xi_{t_k} \Rr] \ge \ov{c}_1 \cdot P\Ll[\left.\;p_{I_i}\left(\xi^{y,\sigma}_{i,t_{k+1}},\; \frac{2n^\beta}{\ov{c}_1} \right) > 1- n^{-2\beta} \;\right|\;\xi_{t_k},\; \sigma < t_k + \frac{n^\beta}{\ov{c}_1}\Rr].$$ Now, if $\sigma < t_k + n^\beta/\ov{c}_1$, then $2n^\beta/\ov{c}_1 > t_{k+1} - \sigma > n^\beta/\ov{c}_1 > |I_i|/\ov{c}_1$, so we can use Lemma \ref{lem:pprop}(ii.) to conclude that the right-hand side is larger than $$\ov{c}_1 \cdot \left(\ov{c}_1 - n^{2\beta}\left(\frac{4n^\beta}{\ov{c}_1}e^{-\ov{c}_1\frac{\log n}{4\log d}} + \frac{\log n}{4\log d}e^{-\frac{\log n}{4\log d}} \right)\right) > \frac{3}{4}\ov{c}_1^2$$ when $n$ is large enough. We can now end the proof as follows: $$P\Ll[X_{k+1} > X_k\;|\;\xi_{t_k}\Rr] \ge P\Ll[Y_{i,k+1} = 1\;|\;\xi_{t_k}\Rr] - P\Ll[X_{k+1} < X_k\;|\;\xi_{t_k}\Rr] \ge \ov{c}_1^2/2$$ since, by part (ii.) and a union bound, $P\Ll[X_{k+1} < X_k\;|\;\xi_{t_k}\Rr]\le L_n \cdot 2n^{-2\beta} = n^{\beta \log 2} \cdot 2n^{-2\beta} \to 0$ as $n \to \infty$. \end{proof} The conclusion will now follow from the above lemma by a comparison with a random walk on $\Z \cap (-\infty,L_n]$ with a drift to the right. The necessary information on this drifted walk is contained in the following lemma. % \begin{lemma} \label{l:rw} Let $(Z_l)_{l \in \N}$ be the random walk on $\Z \cap (-\infty,L_n]$ with transition probabilities $$ P[Z_{l+1} = x + k \ | \ Z_l = x < L_n] = \left|\begin{array}{ll} 0 & \text{if } k > 1, \\ \ov{c}_1^2/{2} & \text{if } k = 1, \\ e^{-n^{-\beta}} \ n^{-|k|\beta}/{|k|!} & \text{if } k \le -1 \end{array} \right. $$ and $$ P[Z_{l+1} = x + k \ | \ Z_l = L_n] = \left|\begin{array}{ll} 0 & \text{if } k \ge 1, \\ e^{-n^{-\beta}} \ n^{-|k|\beta}/{|k|!} & \text{if } k \le -1. \end{array} \right. $$ Let also $H_0$ be the hitting time of $\Z_- = \Z \cap(-\infty,0]$, and $H_L$ be the hitting time of $L_n$. For any $n$ large enough and any $x \le L_n$, we have $$ P\Ll[ H_0 < H_L \ | \ Z_0 = x \Rr] \le n^{-x \beta/2}. $$ \end{lemma} Let us postpone the proof of this lemma, and see how it enables us to conclude. From Lemma \ref{lem:auxTres}(iii.), we learn that whatever the initial non-empty configuration, we have $X_1 \ge 1$ with probability bounded away from $0$. On this event, we want to couple $(X_k)$ with the random walk of Lemma~\ref{l:rw} started at $X_1$, so that $X_{k+1} \ge Z_k$ for every $0 \le k \le H_0$. In the r.h.s.\ of the inequality in Lemma \ref{lem:auxTres}(ii.), a Binomial random variable appears, while jumps to the left for $(Z_l)$ follow a Poisson random variable. Since a Bernoulli random variable of parameter $p$ is stochastically dominated by a Poisson random variable of parameter $-\log(1-p)$, it follows that $\mathsf{Bin}(L_n, 2 n^{-2\beta})$ is stochastically dominated by a Poisson random variable of parameter $$ -L_n \log (1-2 n^{-2\beta}) = -n^{\beta \log 2}\log (1-2 n^{-2\beta}) \le n^{-\beta}. $$ This and Lemma \ref{lem:auxTres}(iii.) guarantee the existence of the coupling. With probability at least $1-n^{-\beta/2} \ge 1/2$, the random walk hits $L_n$ before entering $\Z_-$. Let $\alpha = \frac{\log 2}{4}\beta$. The proof of part (1) will be complete if we can argue that starting from $L_n$, with probability close to $1$, the walk needs to hit and exit $L_n$ at least $e^{n^{\alpha}}$ times before reaching $\Z_-$. Let us consider a sequence of $e^{n^\alpha}$ excursions from $L_n$, and show that with high probability, none of them visits $\Z_-$. Each jump out of $L_n$ is distributed according to a Poisson random variable of parameter $n^{-\beta}$. By the exponential Chebyshev inequality, for $n$ large enough we have $\P\Ll[ \mathsf{Poi}(n^{-\beta}) > x\Rr] < 2e^{-x}$ for any $x > 0$. Thus, with probability tending to $1$, the maximum over $e^{n^{\alpha}}$ such random variables does not exceed $n^{2 \alpha} \le L_n/4$. In view of Lemma~\ref{l:rw}, given an excursion whose first step has size smaller than $L_n/4$, the excursion will visit $\Z_-$ with probability smaller than $n^{-3L_n\beta/8} \le e^{-2n^\alpha}$, and this finishes the proof of part (1). As for part (2), the argument is similar, except that in this case $X_0 = L_n$, and we couple with the random walk of Lemma~\ref{l:rw} started from $Z_0 = X_0 = L_n$. Consider $e^{n^{\alpha}}$ excursions from $L_n$. None of these excursions has first jump larger than $n^{3\alpha} \le L_n/4$ with probability at least $1-e^{n^\alpha} \cdot 2e^{-n^{3\alpha}} > 1-\frac{1}{2}e^{-n^{\alpha}}$. As noted above, given an excursion from $L_n$ whose first step has size smaller than $L_n/4$, the excursion will visit $\Z_-$ with probability smaller than $n^{-3L_n\beta/8} \le \frac{1}{2}e^{-2n^\alpha}$, thus finishing the proof of part (2). \end{proof} \begin{proof}[Proof of Lemma~\ref{l:rw}] Let $h(x) = P\Ll[ H_0 < H_L \ | \ Z_0 = x \Rr]$, $\td{h}(x) = n^{-x \beta/2}$, and let $\cL$ be the generator of the random walk: $$ \cL f(x) = \frac{\ov{c}_1^2}{2}(f(x+1)-f(x)) + e^{-n^{-\beta}} \sum_{k = 1}^{+\infty} \frac{n^{-k\beta}}{k!} (f(x-k) - f(x))\qquad (x < L_n). $$ For $x \in \Z \cap (0,L_n)$, we have $\cL h(x) = 0$. On the other hand, for such $x$, we have \begin{eqnarray*} \cL \td{h}(x) & = & \frac{\ov{c}_1^2}{2}\Ll(n^{-\beta/2}-1\Rr)\td{h}(x) + e^{-n^{-\beta}}\sum_{k = 1}^{+\infty} \frac{n^{-k\beta}}{k!} (n^{k\beta/2}-1)\td{h}(x) \\ & \le & \frac{\ov{c}_1^2}{2}\Ll(n^{-\beta/2}-1\Rr)\td{h}(x) + \sum_{k = 1}^{+\infty} \frac{n^{-k\beta}}{k!} n^{k\beta/2}\td{h}(x) \\ & \le & \Ll[\frac{\ov{c}_1^2}{2}\Ll(n^{-\beta/2}-1\Rr) + e^{n^{-\beta/2}}-1 \Rr] \td{h}(x), \end{eqnarray*} so $\cL \td{h}(x)\le 0$ as soon as $n$ is large enough. As a consequence, $\cL (h-\td{h}) \ge 0$ on $\Z \cap (0,L_n)$. By the maximum principle, $$ \max_{\Z \cap (0,L_n)} (h-\td{h}) \le \max_{\Z_- \cup \{L_n\}} (h-\td{h}) = 0, $$ and the lemma is proved. \end{proof} \begin{proof}[Proof of part (3) of Proposition~\ref{p:expalpha}] We continue with case (B), but considering that $T$ is the spanning tree of some graph $G = (V,E)$. For an arbitrary non-empty $A \subset V$, we wish to bound $$ P\Ll[ \xi^A_{n^2} \neq \xi^{\un{1}}_{n^2}, \ \xi^A_{n^2} \neq \un{0} \Rr]. $$ The probability above is equal to $P[\exists y : \xi^A_{n^2}(y) \neq \xi^{\un{1}}_{n^2}(y), \ \xi^A_{n^2} \neq \un{0}]$. For any fixed $y$, we will thus bound \begin{equation} \label{e:debut} P\Ll[\xi^A_{n^2}(y) \neq \xi^{\un{1}}_{n^2}(y), \ \xi^A_{n^2} \neq \un{0}\Rr]. \end{equation} Letting $(\hat{\xi}^{y,n^2}_t)_{0 \le t \le n^2}$ be the dual contact process for time $n^2$ started with configuration $\{y\}$, we can rewrite this probability as $$ P\Ll[\xi^A_{n^2}(y) = 0,\ \hat{\xi}^{y,n^2}_{n^2} \neq \un{0}, \ \xi^A_{n^2} \neq \un{0}\Rr]. $$ As in the proof of part (1), we consider $X_k$ the number of good intervals at time $t_k = (2n^\beta/\ov{c}_1)k$. By attractiveness, if an interval is good for the contact process on $T$, then it must be good for the contact process on $G$. Note that, for $H_L$ as in Lemma~\ref{l:rw}, a classical large deviation estimate on sums of i.i.d.\ random variables with an exponential moment gives us that $$ P\Ll[ H_L > m \Rr] \le e^{-\sqrt{m}}, $$ and as a consequence, \begin{equation} \label{step1} P\Ll[L_n \notin \{X_k, \ k \le m\}, \ \xi^A_{t_m} \neq \un{0} \Rr] \le e^{-\sqrt{m}}. \end{equation} Let $\cE_{3/4}$ be the event that starting from $A$ occupied, a proportion at least $3/4$ of all the intervals~$(I_i)_{i \le L_n}$ are good in $\xi^A_{n^2/2}$ (for simplicity, $n^2/2$ is assumed to be a multiple of $2n^\beta/\ov{c}_1$). Arguing as in part (2), we see that once $X_k$ has reached $L_n$, the probability that it reaches a point below $3L_n/4$ before time $n^2/2$ is smaller than $e^{-n^{\alpha}}$. Combining this with \eqref{step1}, we obtain $$ P\Ll[ \xi^A_{n^2} \neq \un{0},\ \cE_{3/4}^c \Rr] \le 2 e^{-n^{\alpha}}, $$ where $\cE_{3/4}^c$ denotes the complement of $\cE_{3/4}$. Similarly, if we let $\hat{\cE}_{3/4}$ denote the event that for the dual process $\hat{\xi}^{y,n^2}$, a proportion at least $3/4$ of the intervals are good at time $n^2/2 - 2n^\alpha/\ov{c}_1$, then $$ P\Ll[ \hat{\xi}^{y,n^2}_{n^2} \neq \un{0},\ \hat{\cE}_{3/4}^c \Rr] \le 2 e^{-n^{\alpha}}. $$ Consider the event $\td{\cE}_i$ defined by: $$\td{\cE}_i = \left\{ \xi^A_{n^2/2} \times \{n^2/2\} \leftrightarrow \hat \xi^{y,n^2}_{n^2/2 - 2n^\beta/\ov{c}_1} \times \{n^2/2 + 2n^\beta/\ov{c}_1\} \text{ inside } I_i \right\}.$$ (see picture). \begin{figure}[htb] \begin{center} \setlength\fboxsep{0pt} \setlength\fboxrule{0pt} \fbox{\includegraphics[width = 0.7\textwidth]{drawing.pdf}} \caption{Event $\td{\cE}_i.$} \end{center} \end{figure} %With the notation of the proof of parts (1-2) of Proposition~\ref{p:expalpha}, the event $\td{\cE}_i$ can be rephrased as %$$ %\xi_{i,Kn^\alpha}^{\xi_{n^2/2}^z} = \xi_{i,Kn^\alpha}^{\un{1}} \text{ and } \hat{\xi}_{i,Kn^\alpha}^{\hat{\xi}^{y,n^2}_{n^2/2-Kn^\alpha}} \neq \un{0}. %$$ Let also $\cI$ be the set of indices $i$ such that $I_i$ is good both for the contact process at time $n^2/2$, and for its dual $\hat{\xi}^{y,n^2}$ at time $n^2/2-2n^\beta/\ov{c}_1$. We have \begin{equation*} P\Ll[\bigcap_{i \le L_n} (\td{\cE}_i)^c, \cE_{3/4},\hat{\cE}_{3/4} \Rr] \le P\Ll[\bigcap_{i \in \cI} (\td{\cE}_i)^c, \cE_{3/4},\hat{\cE}_{3/4} \Rr]. \end{equation*} Given that ${\cE}_{3/4}$ and $\hat{\cE}_{3/4}$ both happen, at least $1/2$ of the intervals are good both for the contact process and its dual, or in other words, $|\cI| \ge L_n/2$. Moreover, the events $\cE_{3/4}$ and $\hat{\cE}_{3/4}$, and the set $\cI$, are independent of the state of the Harris system in the time layer $[n^2/2,n^2/2+2n^\beta/\ov{c}_1]$. By the definition of being good and (\ref{eq:dualABh}), we have $P[(\td{\cE}_i)^c \ | \ i \in \cI] \le 2 n^{-2\beta}$. Note also that the events $(\td{\cE}_i)$ are independent. Hence \begin{equation*} P\Ll[\bigcap_{i \le L_n} (\td{\cE}_i)^c, \cE_{3/4},\hat{\cE}_{3/4} \Rr] \le (2n^{-2\beta})^{L_n/2}. \end{equation*} Finally, note that when one of the $\td{\cE}_i$ happens, it must be that $A \times\{0\} \; \leftrightarrow \; (y,n^2)$, that is, $\xi^A_{n^2}(y) = 1$. We have thus proved that \begin{eqnarray*} P\Ll[\xi^A_{n^2}(y) = 0,\ \hat{\xi}^{y,n^2}_{n^2} \neq \un{0}, \ \xi^A_{n^2} \neq \un{0}\Rr] & \le & P\Ll[\xi^A_{n^2}(y) = 0,\ \cE_{3/4}, \hat{\cE}_{3/4} \Rr] + 4 e^{-n^{\alpha}}\\ & \le & \Ll( 2n^{-2\beta} \Rr)^{L_n/2} + 4 e^{-n^{\alpha}} \\ & \le & 5 e^{-n^{\alpha}}. \end{eqnarray*} Recalling that the probability on the l.h.s.\ above is that appearing in \eqref{e:debut}, we have thus shown that $$ P\Ll[ \xi^A_{n^2} \neq \xi^{\un{1}}_{n^2}, \ \xi^A_{n^2} \neq \un{0} \Rr] \le 5n e^{-n^{\alpha}}. $$ \medskip For case (A), the reasoning is similar, only simpler, so we will just outline the steps involved in the proof. Let $I$ be an interval of length $n^\beta$ contained in $T$. We will say that $I$ is good at time $t$ if $$p_I\left(\xi_t \cap I,\; \frac{2n}{\ov{c}_1} \right) > 1 - e^{-n^{\beta/2}}.$$ Define $s_k = (2n/\ov{c}_1)k$ and let $X_k$ be the indicator function of the event that $I$ is good at time $s_k$. Similarly to Lemma \ref{lem:auxTres}, we can then prove that \begin{itemize} \item on $\{\xi_{s_k} \neq \underline{0}\},\;P\Ll[X_{k+1} = 1\;|\; \xi_{s_k}\Rr] \ge \ov{c}_1^2/2$; \item on $\{X_k = 1\},\; P\Ll[ X_{k+1} = 1\;|\; \xi_{s_k}\Rr] \ge 1-2e^{-n^{\beta/2}}$. \end{itemize} Using these facts, we can show that, for $\alpha$ small, non-empty $A$ and $y$, $$\begin{aligned} &P\Ll[\xi^A_{n^2} \neq \underline{0},\; I \text{ is not good for } \xi^A_{n^2/2}\Rr] \le e^{-n^\alpha},\\&P\Ll[\hat \xi^{y,n^2}_{n^2} \neq \underline{0},\; I \text{ is not good for }\hat \xi^{y,n^2}_{n^2/2-2n/\ov{c}_1}\Rr] \le e^{-n^\alpha} \end{aligned}$$ and, conditioned on $I$ being good for both $\xi^A_{n^2/2}$ and $\hat \xi^{y,n^2}_{n^2/2-2n/\ov{c}_1}$, the probability of $$\Ll\{\xi^A_{n^2/2} \times \{n^2/2\} \; \leftrightarrow \; \hat \xi^{y,n^2}_{n^2/2 - 2n/\ov{c}_1} \times \{n^2/2 + 2n/\ov{c}_1\} \text{ inside } I \Rr\}$$ is larger than $1-2e^{-n^{\beta/2}}$. The proof is then completed by summing over $y$. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm2main2}] The result follows from Lemma \ref{lem:ap} in the Appendix, using parts (2) and (3) of Proposition~\ref{p:expalpha}. \end{proof} %$$P(\# \textrm{of infected sites by time}\hspace{0.3cm} n^{\alpha} \geq c n^{\beta \log 2}) > c$$ % %for some $c > 0$ and thus (arguing as in (1)) %$$P(\# \textrm{of infected sites by time}\hspace{0.3cm} n^{\beta} \textrm{will be} \geq %\frac{9 n^{\beta}}{10}) \textrm{ outside}.$$ %exponentially small probability in $n$) %\noindent Thus $\forall \hspace{0.3cm}z \in G \hspace{0.4cm} P(\hat{\xi} ^{z}_{n-n ^{2 \beta %} %} \cap \xi _{n^ [2\beta}] = \emptyset ,\hat{\xi} ^{z}_{n-n ^{2 \beta } %} , \xi _{n^ {2\beta} } \not= \emptyset ) \leq e^{- \frac{n^{\beta}}{4}}$ %from which the result follows. %\vspace{0.4cm} % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % \section{Comparison with Phoenix contact processes} \label{s:comparison2} \setcounter{equation}{0} The aim of this section is to prove Theorem~\ref{thm1main1}. To this end, we manufacture a ``Phoenix contact process''. This process evolves as a contact process up to extinction, but has then the ability to recover activity. Separating a tree $T$ into $T_1$ and $T_2$ as in Lemma~\ref{lem1}, we show that with high probability, the true contact process $\xi$ dominates the union of two Phoenix contact processes running independently on $T_1$ and $T_2$, as long as these two Phoenix contact processes are not simultaneously in the empty configuration. From this, we derive a recursive relation between $\E[\uptau_{T}]$ and the product $\E[\uptau_{T_1}] \E[\uptau_{T_2}]$, which enables us to conclude. \medskip Let $T \in \Lambda(n,d)$. We say that the Harris system is \emph{trustworthy} on the time interval $[0,n^4]$ if for any $(x,s) \in T \times [0,n^4/2]$, the following two conditions hold: \begin{enumerate} \item[(C$_1$)] if $\xi^{x,s}$ survives up to time $n^4$, then $\xi^{x,s}_{n^4} = \xi^{\un{1}}_{n^4}$, \item[(C$_2$)] if $\xi^{x,s}$ survives up to time $s+2 n^2$, then it survives up to time $n^4$. \end{enumerate} We say that the Harris system $H$ is trustworthy on the time interval $[t,t+n^4]$ if $\Theta_t H$ is trustworthy on the time interval $[0,n^4]$, where $\Theta_t H$ is the Harris system obtained by a time translation of $t$ [i.e.\ $(x,u) \leftrightarrow (y,v)$ in $\Theta_t H$ if and only if $(x,t+u) \leftrightarrow (y,t+v)$ in $H$]. For a given Harris system and for $(Y_t)_{t \in \R_+}$ a family of independent auxiliary random variables following a Bernoulli distribution of parameter $1/2$, independent of the Harris system, we define the \emph{Phoenix contact process} $(\zeta_{T,t})_{t \ge 0} = (\zeta_t)_{t \ge 0}$ on $\{0,1\}^T$ as follows. \noindent \emph{Step 0.} Set $\zeta_0 = \un{1}$, and go to Step 1. \noindent \emph{Step 1.} Evolve as a contact process according to the Harris system, up to reaching the state $\un{0}$, and go to Step 2. \noindent \emph{Step 2.} Let $t$ be the time when Step 2 is reached. Stay at $\un{0}$ up to time $t+n^4$ and \begin{itemize} \item if the Harris system is trustworthy on $[t,t+n^4]$ and $Y_{t} = 1$, then set $\zeta_{t+n^4} = \xi^{\un{1},t}_{t+n^4}$ (where $\xi^{\un{1},t}$ is the contact process started with full occupancy at time $t$ and governed by the Harris system), and go to Step 1 ; \item else, go to Step 2. \end{itemize} We say that the process is \emph{active} when it is running Step 1; is \emph{quiescent} when it is running Step 2. Note that after initialization, the process alternates between active and quiescent phases. If it happens that during Step 2, the Harris system is trustworthy on $[t,t+n^4]$ and $Y_t = 1$, but $\xi^{\un{1},t}_{t+n^4} = \un{0}$, we consider that the process is active at time $t+n^4$, and becomes inactive again immediately afterwards. %\begin{rem} %Since the time the process spends on state $\un{0}$ is not exponential, $(\zeta_t)$ is not Markovian. It is however easy to make it into a Markovian process, by enlarging its state space into $\Ll(\{0,1\}^T \setminus \{\un{0}\}\Rr) \cup \Ll(\{\un{0}\} \times [0,n^4)\Rr)$, so that when arriving in Step 2, the process is in the state $(\un{0},0)$, and subsequently the second coordinate increases at unit speed. We will always identify all points in $\{\un{0}\} \times [0,n^4)$ to the single state $\un{0}$. %\end{rem} \begin{rem} \label{r:markov} Note that since the time the process spends on state $\un{0}$ is not exponentially distributed, $(\zeta_t)$ is not Markovian. It would however be easy to make the process Markovian, by enlarging its state space into $\Ll(\{0,1\}^T \setminus \{\un{0}\}\Rr) \cup \Ll(\{\un{0}\} \times [0,n^4)\Rr)$, so that when arriving in Step 2, the process is in the state $(\un{0},0)$, and subsequently the second coordinate increases at unit speed. \end{rem} \begin{rem} \label{r:randomization} The auxiliary randomization of $\zeta$ provided by the family $(Y_t)$ is a technical convenience, which guarantees that if $\zeta_t$ is quiescent at some time $t$, then with probability at least $1/2$ it remains so at least up to time $t + n^4$. \end{rem} \begin{rem} \label{r:defnu} Each time the process becomes active again, its distribution at this time is that of $\xi^{\un{1}}_{n^4}$ conditioned on the event that the Harris system is trustworthy on the time interval $[0,n^4]$. We write $\nu$ to denote this distribution. \end{rem} Our first goal is to ensure that the Phoenix contact process is quiescent at a given time $t$ with small probability, of order $1/E[\uptau]$, with some polynomial multiplicative correction. This is achieved in Lemma~4.6. Two intermediate results are written as lemmas for later reference. Roughly speaking, Lemma~4.6 implies that the probability for two independent Phoenix contact processes running respectively on $T_1$ and $T_2$ to be both quiescent at a given time is bounded by $(E[\uptau_{T_1}] E[\uptau_{T_2}])^{-1}$. \begin{lemma} \label{l:trust} Let $T \in \Lambda(n,d)$. For any $n$ large enough and any $t$, the probability that the Harris system on $T$ is trustworthy on $[t,t+n^4]$ is larger than $1/2$. \end{lemma} \begin{proof} It suffices to show the lemma for $t = 0$. We first consider condition (C$_1$). By part (3) of Proposition~\ref{p:expalpha}, the probability that \begin{equation} \label{eventC1} \forall z \in T, \ \xi^{z,n^4/2}_{n^4} \neq \un{0} \Rightarrow \xi^{z,n^4/2}_{n^4} = \xi^{\un{1},n^4/2}_{n^4} \end{equation} goes to $1$ as $n$ tends to infinity. Let $(x,s) \in T \times [0,n^4/2]$, and assume that $\xi^{x,s}$ survives up to time $n^4$, that is, $$ (x,s) \leftrightarrow T \times \{n^4\}. $$ Then there must exist $z \in T$ such that $$ (x,s) \leftrightarrow (z,n^4/2) \leftrightarrow T \times \{n^4\}. $$ On the event \eqref{eventC1}, we thus have $\xi^{x,s}_{n^4} \ge \xi^{\un{1},n^4/2}_{n^4}$. The converse comparison being clearly satisfied, we have in fact $\xi^{x,s}_{n^4} = \xi^{\un{1},n^4/2}_{n^4}$. In order to show that condition (C$_1$) is satisfied for any $(x,s) \in T \times [0,n^4/2]$ with probability tending to $1$, it thus suffices to show that \begin{equation} \label{C1bis} P\Ll[ \xi^{\un{1}}_{n^4} = \xi^{\un{1},n^4/2}_{n^4} \Rr] \to 1 \text{ as } n \to \infty. \end{equation} In view of part (2) of Proposition~\ref{p:expalpha}, with probability tending to one, we have $\xi^{\un{1}}_{n^4} \neq \un{0}$. On this event, by part (3) of Proposition~\ref{p:expalpha}, we also have $\xi^{\un{1},n^4/2}_{n^4} = \xi^{\un{1}}_{n^4}$ with probability tending to $1$, and thus \eqref{C1bis} is proved. We now turn to condition (C$_2$). Note that the event $\xi^{x,s}_{s+2n^2} \neq \un{0}$ can be rewritten as $$ (x,s) \leftrightarrow T \times \{s+2n^2\}, $$ and under such a circumstance, there must exist $z \in T$ such that $$ (x,s) \leftrightarrow (z, \lceil s/n^2 \rceil n^2) \leftrightarrow T \times \{s+2n^2\}. $$ It is thus sufficient to show that \begin{equation} \label{C2a} P\Ll[\exists z \in T, k \in \{0,\ldots, \lceil n^2/2 \rceil\} : \ \xi^{z,kn^2}_{(k+1)n^2} \neq \un{0} \text{ but } \xi^{z,kn^2}_{n^4} = \un{0}\Rr] \to 0 \text{ as } n \to \infty. \end{equation} For a fixed $z \in T$ and integer $k$, we have by part (3) of Proposition~\ref{p:expalpha} that $$ P\Ll[ \xi^{z,kn^2}_{(k+1)n^2} \neq \un{0} \text{ but } \xi^{z,kn^2}_{(k+1)n^2} \neq \xi^{\un{1},kn^2}_{(k+1)n^2} \Rr] \le e^{-n^{\alpha/2}}, $$ so the probability of the event \begin{equation} \label{C2b} \forall z \in T, k \in \{0,\ldots, \lceil n^2/2 \rceil\} : \ \xi^{z,kn^2}_{(k+1)n^2} = \un{0} \text{ or } \xi^{z,kn^2}_{(k+1)n^2} = \xi^{\un{1},kn^2}_{(k+1)n^2} \end{equation} tends to $1$ as $n$ tends to infinity. On the other hand, with probability tending to $1$, $\xi^{\un{1}}$ survives up to time $n^4$, and $\xi^{\underline{1}}_{n^4}$ is clearly dominated by $\xi^{\un{1},kn^2}_{n^4}$, for any $k \le \lceil n^2/2 \rceil$. On the conjunction of this event and the one described in \eqref{C2b}, we thus have $$ \forall z \in T, k \in \{0,\ldots, \lceil n^2/2 \rceil\},\text{ either } \ \xi^{z,kn^2}_{(k+1)n^2} = \un{0} \text{ or } \xi^{z,kn^2}_{n^4} \ge \xi^{\un{1}}_{n^4} \neq \un{0}, $$ and this proves \eqref{C2a}. \end{proof} For the next lemma, recall that $\uptau$ is the extinction time of the contact process started with full occupancy. \begin{lemma} \label{l:attract} For any $s > 0$, one has $$ P\Ll[\uptau \le s \Rr] \le \frac{s}{E[\uptau]}, $$ Moreover, there exists a constant $C$ such that for any $T \in \Lambda(n,d)$, $E[\uptau] \le e^{Cn}$. \end{lemma} \begin{proof} Attractiveness of the contact process implies that for any $r \in \N$, \begin{equation} \label{e:prob00} P\Ll[ \uptau \ge r s \Rr] \le \Ll(P\Ll[ \uptau \ge s \Rr]\Rr)^r. \end{equation} Since \begin{equation} \label{e:prob1} E[\uptau] \le s \sum_{r = 0}^{+\infty} P\Ll[ \uptau \ge r s \Rr] \le \frac{s}{1-P\Ll[ \uptau \ge s \Rr]}, \end{equation} it comes that $$ P\Ll[ \uptau \ge s \Rr] \ge 1-\frac{s}{E[\uptau]}, $$ which proves the first part. For the second part, note that one can find $C$ such that \begin{equation} \label{e:prob01} P\Ll[\uptau \ge 1\Rr] \le 1-e^{-Cn} \end{equation} uniformly over $T \in \Lambda(n,d)$. The conclusion thus follows from \eqref{e:prob1}. \end{proof} \begin{lemma} \label{l:prob0} For any $n$ large enough, any $T \in \Lambda(n,d)$ and any $t \ge 0$, one has \begin{equation} \label{e:prob0} P\Ll[ \zeta_t = \un{0} \Rr] \le \frac{6 n^6}{E[\uptau]}. \end{equation} \end{lemma} \begin{proof} Using Lemma~\ref{l:attract} with $s = n^6$, it is clear that \eqref{e:prob0} holds for any $n$ and any $t \le n^6$. Note moreover that, writing $\uptau^\nu$ for the extinction time of the contact process started from the distribution $\nu$ defined in Remark~\ref{r:defnu}, we have \begin{equation} \label{e:prob2} P\Ll[ \uptau^\nu \le n^6 -n^4 \Rr] = P\Ll[ \uptau \le n^6 \ | \ \text{Harris sys. trustworthy on } [0,n^4] \Rr] \le \frac{2n^6}{E[\uptau]}, \end{equation} where we used Lemma~\ref{l:trust} in the last step. Suppose now that $t > n^6$, and consider the event $\cE$ defined by $$ \exists s \in (t - n^6/2, t - n^6/4] \mbox{ such that } \zeta_s = \underline 0. $$ We write $\td{\uptau}$ for the first $s \ge t-n^6/2$ such that $\zeta_s = \un{0}$. On the event $\cE$, we have $\td{\uptau} \le t - n^6/4$. The event $\cE'$ defined by \begin{multline*} \forall k \in \N, k < \lfloor n^2/4 \rfloor , \\ \text{Harris sys. not trustworthy on } [\td{\uptau} + k n^4, \td{\uptau} + (k+1) n^4] \text{ or } Y_{\td{\uptau} + k n^4} \neq 1 \end{multline*} has probability smaller than $(3/4)^{\lfloor n^{2}/4 \rfloor}$ by Lemma~\ref{l:trust}. When $\cE$ and $(\cE')^c$ both hold, the process $\zeta$ becomes active at some time $t_A \in [t-n^6/2, t]$, and is distributed according to $\nu$ at this time. Hence, \begin{eqnarray*} P\Ll[\zeta_t = \un{0}, \cE \Rr] & \le & P\Ll[\zeta_t = \un{0}, \cE, (\cE')^c\Rr] + P\Ll[\cE'\Rr] \\ & \le & P\Ll[\uptau^\nu \le n^6/2\Rr] + P\Ll[\cE'\Rr]. \end{eqnarray*} Since $P[\cE'] \ll 1/E[\uptau]$ and in view of \eqref{e:prob2}, we have indeed \begin{equation} \label{e:prob3} P\Ll[\zeta_t = \un{0}, \cE \Rr] \le \frac{3 n^6}{E[\uptau]} \end{equation} for any large enough $n$. It thus remains to bound \begin{equation} \label{e:prob4} P\Ll[\zeta_t = \un{0}, \cE^c \Rr]. \end{equation} Let $k$ be the first positive integer such that $Y_{t-n^6/2+kn^4} = 1$ and the Harris system is trustworthy on $$ [a_k,b_k] \stackrel{\text{(def)}}{=} [t - n^6/2 + k n^4, t - n^6/2 + (k+1) n^4]. $$ For the same reason as above, we may assume that $[a_k,b_k] \subset [t-n^6/2,t-n^6/4]$. Since on the event $\cE^c$, the process $\zeta$ remains active on the time interval $[a_k,b_k]$, and considering the definition of trustworthiness and of the Phoenix process, we know that $\zeta_{b_k} = \xi^{\un{1},a_k}_{b_k}$, and moreover, the latter random variable is distributed according to $\nu$. Hence, up to a negligible event, the probability in \eqref{e:prob4} is bounded by $$ P\Ll[ \uptau^\nu \le n^6/2 \Rr], $$ and thus, using \eqref{e:prob2} again, \begin{equation} \label{e:prob5} P\Ll[\zeta_t = \un{0}, \cE^c \Rr] \le \frac{3 n^6}{E[\uptau]}. \end{equation} The conclusion now follows, combining \eqref{e:prob3} and \eqref{e:prob5}. \end{proof} In order to justify that with high probability, the true contact process on $T$ dominates the union of two independent Phoenix contact processes on the subtrees $T_1$ and $T_2$ until extinction, we need to make sure that if the contact process is alive in $T_1$ but not in $T_2$, it will try to infect $T_2$ many times in a short time interval (so that with high probability, a large-scale infection happens in $T_2$ before the Phoenix contact process in $T_2$ becomes active again). The next lemma ensures that any given vertex $x \in T_1$ is infected many times if the contact process remains alive for some short amount of time (we think of $x$ as being the site bordering the cut of $T$ into two pieces, so that having $x$ infected gives the immediate opportunity to start an infection in $T_2$). \begin{lemma} \label{transmission} Let $T$ be a tree with size at most $n$ and maximal degree at most $d$, and let $x \in T$. Define recursively $\gamma_0 = 0$ and, for any $i \in \N$, $$ \gamma_{i+1} = \inf\{t \ge \gamma_i + 2 n^2 : \xi_t(x) = 1\} \quad (+ \infty \text{ if empty}). $$ For $n$ large enough, we have $$ P\Ll[ \gamma_{n^2/8} > n^4/2 \ | \ \xi_{n^4/2} \neq \un{0}\Rr] \le e^{-n^{2}}. $$ \end{lemma} % \begin{proof} In view of part (1) of Proposition~\ref{cpinterval}, for any non-empty $A \subset T$, we have $$ P\Ll[ \exists s \le \frac{n}{\ov{c}_1} : \xi^A_s(x) = 1 \Rr] \ge \ov{c}_1. $$ Let $\cF_i$ be the $\sigma$-field generated by $\{\xi_t, t \le \gamma_i\}$. By induction and the Markov property, we can thus show that for any $k \in \N$, $$ P\Ll[\gamma_{i+1}-(\gamma_i+2 n^2) \ge \frac{kn}{\ov{c}_1},\ \xi_{\gamma_i+2n^2+(k-1)n/\ov{c}_1} \neq \un{0} \ | \ \cF_i \Rr] \le (1-\ov{c}_1)^{k}. $$ Hence, \begin{eqnarray*} P\Ll[ \gamma_{n^2/8} > n^4/2, \ \xi_{n^4/2} \neq \un{0}\Rr] & = & P\Ll[ \sum_{i = 0}^{n^2/8-1}\gamma_{i+1}-(\gamma_i+2 n^2) > n^4/4 , \ \xi_{n^4/2} \neq \un{0}\Rr] \\ & \le & P\Ll[\sum_{i = 0}^{n^2/8-1} B_i n /\ov{c}_1 > n^4/4 \Rr], %= P\Ll[\sum_{i = 0}^{n^2/4-1} B_i > \ov{c}_1n^3/4 \Rr] , \end{eqnarray*} where $(B_i)$ are independent geometric random variables of parameter $1-\ov{c}_1$. For $\lambda > 0$ small enough, we have $$ e^{\phi(\lambda)} \stackrel{\text{(def)}}{=} E[e^{\lambda B_i}] < +\infty, $$ and we thus obtain $$ P\Ll[\sum_{i = 0}^{n^2/8-1} B_i > \ov{c}_1n^3/4 \Rr] \le \exp\Ll(\phi(\lambda) n^2/8 - \lambda \ov{c}_1n^3/4\Rr), $$ which, together with part (1) of Proposition~\ref{p:expalpha}, proves the claim. \end{proof} We are now ready to prove our coupling result. \begin{proposition} \label{p:coupling} For $n$ large enough, let $T \in \Lambda(n,d)$ be split into two subtrees $T_1,T_2$ as described by Lemma~\ref{lem1}. Define the process $(\td{\zeta}_t)_{t \ge 0}$ by $$ \td{\zeta}_t = \zeta_{T_1,t} \cup \zeta_{T_2,t} \qquad (t \ge 0), $$ where $\zeta_{T_1}$ and $\zeta_{T_2}$ are Phoenix processes defined on $T_1$ and $T_2$ respectively, using the Harris system on $T$ together with two independent families of auxiliary random variables, independent of the Harris system. One has $$ P\Ll[ \forall t \le \uptau, \ \xi_t \ge \td{\zeta}_t \Rr] \ge 1-e^{-n^{3/2}}. $$ \end{proposition} \begin{proof}%[Proof of Proposition~\ref{p:coupling}] Let $(\sigma_i)_{i \ge 1}$ be the sequence of (stopping) times when the process $\zeta_{T_1}$ becomes quiescent. We start by showing that, for any $i$, \begin{equation} \label{activation} P\Ll[\xi_{\sigma_i+n^4} < \zeta_{T_1,\sigma_i+n^4}, \ \xi_{\sigma_i+n^4} \neq \un{0}\Rr] \le e^{-n^{7/4}}. \end{equation} For some arbitrary $x \in T_1$, consider the stopping times introduced in Lemma~\ref{transmission}, but started with $\gamma_0 = \sigma_i$, and let $N$ be the largest index satisfying $\gamma_N \le \sigma_i + n^4/2$. By Lemma~\ref{transmission}, we have \begin{equation} \label{e:p:coupling0} P\Ll[N < n^2/8 ,\ \xi_{\sigma_i+n^4} \neq \un{0}\Rr] \le e^{-n^2}. \end{equation} Moreover, part (1) of Proposition~\ref{p:expalpha} ensures that, for any $j$, \begin{equation} \label{e:p:coupling} P\Ll[\xi^{x,\gamma_j}_{T_1} \text{ survives up to time } \gamma_j + 2 n^2 \ | \ \gamma_j < +\infty \Rr] \ge \ov{c}_2, \end{equation} where $\xi^{x,\gamma_j}_{T_1}$ denotes the contact process restricted to $T_1$ started with $x$ occupied at time $\gamma_j$. We introduce the stopping times $\td{\gamma}_j$ to deal with the fact that $\gamma_j$ may be infinite. %Let $\tdj$ we be the largest index such that $\gamma_{\tdj} \le \sigma_i + n^4/2$. We let $\td{\gamma}_j = \gamma_j$ if $j\le N$, $\td{\gamma}_{N+1} = \sigma_i + n^4/2 + 2 n^2$, and then recursively, $\td{\gamma}_{j+1}-\td{\gamma}_j = 2 n^2$. We have \begin{multline} \label{e:p:coup} P\Ll[ \forall j \le N, \ \xi^{x,\gamma_j}_{T_1, \gamma_j + 2 n^2} = \un{0}, \ \xi_{\sigma_i+n^4} \neq \un{0}\Rr] \\ \le P\Ll[N < n^2/8,\ \xi_{\sigma_i+n^4} \neq \un{0}\Rr] + P\Ll[ \forall j \le n^2/8, \ \xi^{x,\td{\gamma}_j}_{T_1, \td{\gamma}_j + 2 n^2} = \un{0}\Rr], \end{multline} Since for any $j$, we have $\td{\gamma}_{j+1} \ge \td{\gamma}_j + 2 n^2$, the events indexed by $j$ appearing in the second probability on the r.h.s.\ of \eqref{e:p:coup} are independent. Using also \eqref{e:p:coupling0} and \eqref{e:p:coupling} (with $\gamma_j$ replaced by $\td{\gamma}_j$), we thus arrive at \begin{equation} \label{e:p:coupling1} P\Ll[ \forall j \le N, \ \xi^{x,\gamma_j}_{T_1, \gamma_j + 2 n^2} = \un{0}, \ , \xi_{\sigma_i+n^4} \neq \un{0}\Rr] \le e^{-n^2} + (1-\ov{c}_2)^{n^2/8}. \end{equation} We now show that \begin{equation} \label{e:p:coupling2} \exists j \le N, \ \xi^{x,\gamma_j}_{T_1, \gamma_j + 2 n^2} \neq \un{0} \ \Rightarrow \ \xi_{\sigma_i+n^4} \ge \zeta_{T_1,\sigma_i+n^4}. \end{equation} Indeed, in order for $\zeta_{T_1, \sigma_i+n^4}$ to be non $\un{0}$, it must be that the Harris system restricted to $T_1$ is trustworthy on $[\sigma_i,\sigma_i+n^4]$. In this case, by the definition of trustworthiness, if there exists some $j \le N$ such that $\xi^{x,\gamma_j}_{T_1, \gamma_j + 2 n^2} \neq \un{0}$, then it must be that $$ \xi^{x,\gamma_j}_{T_1,\sigma_i+n^4} = \xi^{\un{1},\sigma_i}_{T_1,\sigma_i + n^4} \ge \zeta_{T_1,\sigma_i+n^4} $$ (the last two being equal when $Y_{\sigma_i} = 1$, otherwise $\zeta_{T_1,\sigma_i+n^4} = \un{0}$). Since $\xi_{\gamma_j}(x) = 1$, it is clear that $\xi_{\sigma_i+n^4} \ge \xi^{x,\gamma_j}_{T_1,\sigma_i+n^4}$, thus justifying \eqref{e:p:coupling2}. This and \eqref{e:p:coupling1} prove \eqref{activation}. In order to conclude, we first show that $\uptau$ cannot be too large. It comes from \eqref{e:prob00} and \eqref{e:prob01} that \begin{equation} \label{e:p:coupling3} P\Ll[\uptau \ge n^4 e^{C n}\Rr] \le e^{-n^{2}}, \end{equation} where $C$ can be chosen uniformly over $T \in \Lambda(n,d)$. If $\zeta_{T_1}$ is active at time $t$ and $\xi$ dominates $\zeta_{T_1}$ at this time, then the domination is preserved during the whole phase of activity, since $\zeta_{T_1}$ is driven by a subset of the Harris system driving the evolution of $\xi$. When $\zeta_{T_1}$ becomes quiescent, the domination is obviously preserved. As a consequence, if the domination of $\zeta_{T_1}$ by $\xi$ is broken at some time, it must be when $\zeta_{T_1}$ turns from quiescent to active. We thus have $$ P\Ll[ \exists t \le \uptau, \ \xi_t < \zeta_{T_1,t} \Rr] = P\Ll[ \exists i : \xi_{\sigma_i+n^4} < \zeta_{T_1,\sigma_i+n^4}\text{ and } \xi_{\sigma_i+n^4} \neq \un{0} \Rr]. $$ Since $\sigma_{i+1} - \sigma_i \ge n^4$, on the event $\uptau \le n^4 e^{C n}$, there are at most $e^{C n}$ times when $\zeta_{T_1}$ turns from quiescent to active. Using \eqref{activation}, we thus obtain $$ P\Ll[ \exists t \le \uptau, \ \xi_t < \zeta_{T_1,t} \Rr] \le P[\uptau \ge n^4 e^{C n}] + e^{C n} e^{-n^{7/4}}. $$ The proposition is now proved, using \eqref{e:p:coupling3} together with the fact that $$ P\Ll[ \exists t \le \uptau, \ \xi_t < \td{\zeta}_{t} \Rr] \le P\Ll[ \exists t \le \uptau, \ \xi_t < \zeta_{T_1,t} \Rr] + P\Ll[ \exists t \le \uptau, \ \xi_t < \zeta_{T_2,t} \Rr]. $$ \end{proof} \begin{corollary} \label{c:coupling} For $n$ large enough, let $T \in \Lambda(n,d)$ be split into two subtrees $T_1,T_2$ as described by Lemma~\ref{lem1}. We have $$ E[\uptau_T] \ge n^{-9} \ E\Ll[\uptau_{T_1}\Rr] E\Ll[\uptau_{T_2}\Rr]. $$ \end{corollary} \begin{proof} Let $\td{\sigma}$ be the first time when $\zeta_{T_1}$ and $\zeta_{T_2}$ are simultaneously quiescent. By Proposition~\ref{p:coupling}, for any $t \ge 0$, we have \begin{equation} \label{e:c0} P[\uptau \le t] \le P[\td{\sigma} \le t] + e^{-n^{3/2}}. \end{equation} In view of Remark~\ref{r:randomization}, at time $\td{\sigma}$, both $\zeta_{T_1}$ and $\zeta_{T_2}$ remain quiescent for a time $n^4$ with probability at least $1/2$ (one of them just becomes quiescent at time $\td{\sigma}$, while the other stays quiescent for a time $n^4$ with probability at least $1/2$). As a consequence, for any $t \ge 0$, $$ P\Ll[\td{\sigma} \le t\Rr] \le \frac{2}{n^4} \int_0^{t+n^4} P\Ll[\td{\zeta}_s = 0\Rr] \ \d s. $$ Since $\zeta_{T_1}$ and $\zeta_{T_2}$ are independent, and using Lemma~\ref{l:prob0}, we thus obtain \begin{equation} \label{e:c1} P[\td{\sigma} \le t] \le \frac{2}{n^4} (t+n^4) \frac{(6n^6)^2}{E[\uptau_{T_1}]E[\uptau_{T_2}]} = \frac{72 n^8(t+n^4)}{E[\uptau_{T_1}]E[\uptau_{T_2}]}. \end{equation} Let us now fix $$ \td{t} = 2 \frac{{E[\uptau_{T_1}]E[\uptau_{T_2}]}}{n^9}. $$ Since we know from part (1) of Proposition~\ref{p:expalpha} that $\td{t}$ grows faster than any power of $n$, \eqref{e:c1} gives us that for $n$ large enough, $$ P\Ll[\td{\sigma} \le \td{t}\Rr] \le 1/4. $$ In view of \eqref{e:c0}, we thus obtain $$ P\Ll[\uptau \le \td{t}\Rr] \le 1/4 + e^{-n^{3/2}} \le 1/2, $$ which implies that $E[\uptau] \ge \td{t}/2$, and thus the corollary. \end{proof} \begin{proof}[Proof of Theorem \ref{thm1main1}] Let $\rho = 1+1/d$, and consider, for any $r \in \N$, the quantity $$ V_{r}= \inf_{n \in (\rho^{r-1}/d, \rho^r]} \ \inf_{T \in \Lambda(n,d)} \frac{\log E[\uptau(T)]}{|T|} $$ Statement \eqref{eq:thm12} of Theorem~\ref{thm1main1} will be proved if we can show that $\liminf_{r \to \infty} V_r > 0$. Let $r$ be a positive integer, and $T$ be a tree of degree bounded by $d$ and whose size lies in $\left(\rho^{r},\rho^{r+1} \right]$. Since $1-\rho^{-1} = 1/(d+1) < 1/d$ and in view of Lemma~\ref{lem1}, for $r$ large enough, we can split up $T$ into two subtrees $T_1$, $T_2$ such that $$ |T_{1}|, |T_{2}| \ge |T|(1-\rho^{-1}). $$ As a consequence, $$ |T_1|, |T_2| \ge \rho^{r-1}/d, $$ and also $$ | T_{1}| \leq |T| - |T_2| \leq |T|\left( 1-(1-\rho^{-1}) \right) \le \rho^r, $$ with the same inequality for $T_2$. Corollary~\ref{c:coupling} tells us that for $r$ large enough, $$ E[\uptau(T)] \ge \frac{1}{|T|^{9}} E[\uptau(T_1)] \ E[\uptau(T_2)], $$ that is to say, $$ \log E[\uptau(T)] \ge \log E[\uptau(T_1)] + \log E[\uptau(T_2)] - \log |T|^{9}. $$ Observing that $$ \log E[\uptau(T_1)] + \log E[\uptau(T_2)] \ge V_r (|T_1| + |T_2|) = V_r |T|, $$ we arrive at \begin{equation} \label{superadd} \frac{\log E[\uptau(T)]}{|T|} \ge V_r - \frac{\log |T|^{9}}{|T|}. \end{equation} Part (1) of Proposition~\ref{p:expalpha} ensures that for $r$ large enough, one has \begin{equation} \label{positivvr} V_r \ge \frac{c}{\rho^{r(1-\alpha)}} \end{equation} for some constant $c > 0$. Recalling that $|T| \le \rho^{r+1}$, we thus have $$ \frac{\log |T|^{9}}{|T|} \le \frac{V_r}{\rho^{r\alpha/2}}, $$ and \eqref{superadd} turns into $$ \frac{\log E[\uptau(T)]}{|T|} \ge V_r\left(1-\frac{1}{\rho^{r \alpha/2}}\right), $$ for any large enough $r$ and any tree whose size lies in $(\rho^r,\rho^{r+1}]$. If the size of the tree lies in $(\rho^r/d,\rho^r]$, then the inequality $$ \frac{\log E[\uptau(T)]}{|T|} \ge V_r $$ is obvious, so we arrive at $$ V_{r+1} \ge V_r\left(1-\frac{1}{\rho^{r \alpha/2}}\right). $$ Since $V_r > 0$ for any $r$ large enough by \eqref{positivvr}, and $$ \prod_{r} \left(1-\frac{1}{\rho^{r \alpha/2}}\right) > 0, $$ we have shown that $\liminf_{r \to \infty} V_r = c> 0$. This proves (\ref{eq:thm12}). In order to prove (\ref{eq:thm11}), it suffices to note that, by Lemma~\ref{l:attract}, $$\sup_{T\in \Lambda(n,d)} P\Ll[ \uptau \le e^{cn/2}\Rr] \le \frac{e^{cn/2}}{\displaystyle \inf_{T \in \Lambda(n,d)} E[\uptau]} \le e^{-cn/4}$$ for $n$ large enough. \end{proof} % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % \section{Discrete time growth process} \label{s:discrete} \setcounter{equation}{0} For comparison purposes, it is useful to consider a discrete-time analogue of the contact process; we will need to consider such a process in the next section. Though many different definitions may be proposed, we have decided on the following. Fix $p \in (0,1)$ and let $\{I^r_{(x,y)}: r \in \{0,1, \ldots\},\;x,y \in \Z,\;|x-y|\leq 1\}$ be a family of independent Bernoulli($p$) random variables. Fix $\eta_0 \in \{0,1\}^\Z$ and, for $r\geq 0$, let \begin{equation}\eta_{r+1}(x) = \mathds{1}_{\{\exists y:\;|y-x| \leq 1,\; \eta_r(y) = 1,\;I^r_{(y,x)} = 1\}}.\label{eq:defCompP}\end{equation} The following is standard. \begin{proposition} The above process is attractive and there exists $p_{c}^{(1)} < 1$ such that for $p > p^{(1)}_{c}$ the process survives in the sense that, for any $\eta_0 \neq \underline{0}$, $$P\left[\eta_r \neq \underline{0} \hspace{0.3cm} \forall r\right] > 0$$ and, if $\eta_0 = \underline{1}$, then $\eta_{r}$ decreases stochastically to a non-zero limit. \end{proposition} This process generalizes to any locally finite graph $G= (V,E)$ just as does the contact process: we take independent Bernoulli($p$) random variables $$\{I^r_{(x,y)}: x,y \in V,\; \mathsf{dist}(x,y) \leq 1\}$$ (where $\mathsf{dist}$ denotes graph distance) and, given $\eta_0 \in \{0,1\}^V$, let \begin{equation}\label{eq:defCompQ}\eta_{r+1}(x) = \mathds{1}_{\{\exists y: \mathsf{dist}(x,y) \leq 1,\;\eta_r(y)=1,\;I^r_{(y,x)} = 1\}},\qquad r\geq 0,\; x\in V.\end{equation} In particular, $\{\eta_r\}_{r \geq 0}$ has the self-duality property, and we can follow through the arguments of the preceding sections to arrive at: %\noindent The process has a simple duality and arguing as in Section two we have \begin{proposition} \label{discrete} \noindent Let $d \geq 2$ and $p > p_c^{(1)}$. There exists $c>0$ such that $$\inf_{T\in \Lambda(n,d)} \; P\left[\uptau_T \geq e^{cn}\right] \longrightarrow 1 \text{ as } n \to \infty.$$ \end{proposition} \noindent(Here, $\uptau_T$ is the extinction time for the discrete-time process on $T$ started from full occupancy). %\vspace{0.4cm} % % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % \section{Extinction time for the configuration model} \label{s:nsw} Let us briefly recall the definition of the random graph $G_n = (V_n, E_n)$. We take $V_n = \{1, 2, \ldots, n\}$ and suppose given a probability $p(\cdot) $ on the positive integers greater than or equal to $3$ with the property that there exist $a > 2$ and $0 < c_0 < C_0$ such that, if $m$ is large enough, \begin{equation}c_0 < m^a\cdot p(m) < C_0.\label{eqn5compInt0}\end{equation} To generate $G_n$, we first choose the degrees for the $n$ vertices $d_1, d_2, \ldots, d_n$, according to i.i.d. random variables of law $p(\cdot)$ (and add 1 to one of the $d_i$, if necessary, to make $\sum d_i$ even). Given this realization, we choose the edges by first giving each vertex $x\; d_x$ half-edges and then matching up the half-edges uniformly among all possible matchings, so that, say, a half-edge for vertex $x$ matched with a half-edge of vertex $y$ becomes an edge between $x$ and $y$. In \cite[Theorem~10.14]{vdH}, it is shown that from the assumption that $p$ is supported on integers larger than 2, it follows that $G_n$ is a connected graph with probability tending to 1 as $n \to \infty$. We consider the contact process with parameter $\lambda > 0$ on $G_n$. In order to do so, we need to slightly modify the generator given in (\ref{eq1gen}) to accomodate the fact that the random graph obtained from the above distribution may have loops and parallel edges. We put \begin{equation} \label{eqNewDyn} \begin{array}{lll} \text{for every } x \in \xi_t, & \xi_t \to \xi_t \setminus \{x\} & \text{with rate } 1, \\ \text{for every } x \notin \xi_t, & \xi_t \to \xi_t \cup \{x\} & \text{with rate } \lambda \ \sum_{y: y\in \xi_t}|\{e \in E_n : x, y \in e\}|. \end{array} \end{equation} By $x, y \in e$ we mean simply that the extremities of $e$ are $x$ and $y$ (this may now be true for more than one edge $e$). With this definition, loops have no effect on the dynamics and parallel edges are seen as independent channels for the transmission of the infection. The graphical construction defined in the beginning of Section \ref{s:remind} is compatible with (\ref{eqNewDyn}) and requires no modification. We will prove Theorem \ref{thm1cd1} under the assumption that $a > 2$, as mentioned in the Introduction. We will also assume that $\lambda$ is small; this is not problematic to us because clearly it is sufficient to prove Theorem \ref{thm1cd1} for $\lambda$ small enough. We rely on the idea that the contact process is sustained for a long time in the vicinity of vertices of high degree (``stars''). Our approach is to exhibit a subgraph $G_n'$ of $G_n$ that has sufficiently many stars arranged so that none of them is very far from others, and to argue that $G_n'$ provides a very fertile environment for the persistence of the infection. Let us be a bit more specific in sketching the proof. Depending on $\lambda$, we fix a degree threshold $S$ -- stars will be vertices with degree above $S/2$ --, a distance threshold $D$ and a time scale $\kappa$. Our subgraph $G_n'$ is a (connected) tree composed essentially of $O(n)$ stars and line segments connecting these stars (to be exact, $G_n'$ will end up containing some other vertices which do not fall in either category, but let us ignore that for the moment). Each star is directly connected by segments to at most 3 other stars, and the lengths of the segments are all below $D$. We then define a tree $G_n''$ as a renormalized version of $G_n'$ in a very natural way: stars of $G_n'$ correspond to vertices of $G_n''$ and segments of $G_n'$ correspond to edges of $G_n''$. In particular, the degrees in $G_n''$ are bounded by 3. The contact process on $G_n'$ then induces a discrete-time growth process $(\eta_r)$ on $G_n''$; roughly speaking, for a vertex $x$ of $G_n''$ we say that $\eta_r(x)=1$ if the star of $G_n'$ that corresponds to $x$ has many infected vertices (or is \textit{infested}, as we will write) at time $\kappa\cdot r$. The parameters $S$, $D$ and $\kappa$ can be chosen so that, if a star is infested at time $\kappa r$, then with high probability it keeps being infested until time $\kappa(r+1)$, and this in turn is long enough that, with high probability, the infection reaches nearby stars, which also become infested. For the growth process $(\eta_r)$, this translates into saying that the closure parameter $p$ is very close to 1. We then apply Proposition \ref{discrete} to $(\eta_r)$, thus concluding that it stays active for an amount of time that is exponential in the number of vertices of $G_n''$, which as mentioned is $O(n)$. The desired conclusion for the contact process on $G_n$ is then immediate. %Our approach is to show that with high probability, $G_n$ has a subgraph $G_n' = (V_n', E_n')$ with a set of distinguished vertices $J_n' \subset V_n'$ satisfying certain properties that will guarantee that the extinction time of the contact process on $G_n'$ is exponential in $n$. From this, by attractiveness, we will conclude that the extinction time for the contact process on $G_n$ is also exponential in $n$ with high probability. This section is organized as follows. We will first list the formal properties that we want for the subgraph $G_n'$ endowed with a set of distinguished vertices $J_n'$. We state in Proposition \ref{prop6goodSubg} that with high probability, large enough $G_n', J_n'$ satisfying these properties indeed exist. Next, we will show how this proposition implies Theorem \ref{thm1cd1}. Finally, we will prove the proposition, showing how $G_n', J_n'$ can be constructed. The first property on our list is\medskip\\ \textit{Property 1:} $G_n'$ is a (connected) tree (with no loops or multiple edges).\medskip Before listing the other properties, we need some notation. Let $\deg'$ denote the degree of a vertex in $G_n'$, that is, $\deg'(x) = |\{y \in V_n': \{x,y\} \in E_n'\}|,$ and $\text{dist}'$ denote the graph distance in $G_n'$, that is, $\text{dist}'(x,y)$ is the length of the minimal path from $x$ to $y$ contained in $G_n'$. For $x, y \in J_n'$, write $x \stackrel{*}{\sim} y$ if the unique path contained in $G_n'$ from $x$ to $y$ contains no vertices of $J_n'$ other than $x$ and $y$. Let $S$ be a large constant to be chosen later and $D = \lambda^4 S$. \medskip\\ \textit{Property 2:} $\deg'(x) \geq \frac{S}{2}$ for all $x \in J_n'$.\medskip\\ \textit{Property 3:} $\text{dist}'(x,y) \leq D$ for all $x,y \in J_n'$ with $x \stackrel{*}{\sim}y$.\medskip\\ \textit{Property 4:} The graph $G_n'' = (V_n'', E_n'')$ given by $$V_n'' = J_n';\qquad E_n'' = \{\{x,y\}:x,y \in J_n',\; x\stackrel{*}{\sim}y\}$$ is a (connected) tree with degree bounded by 3. \begin{proposition}\label{prop6goodSubg} For small enough $\lambda > 0$, if $S$ is large enough (depending on $\lambda$), there exists $\delta > 0$ such that, with probability tending to 1 as $n \to \infty,\; G_n$ has a subgraph $G_n'$ with a set of vertices $J_n' \subset V_n'$ such that Properties 1-4 are satisfied and $|J_n'| > \delta n$. \end{proposition} \begin{proof}[Proof of Theorem \ref{thm1cd1}.] Assume $G_n',\; J_n'$ are as in the above proposition and $G_n''$ is as in Property 4. $G_n''$ is thus a tree with more than $\delta n$ vertices and degree bounded by 3. We will couple the contact process $(\xi'_t)_{t \geq 0}$ on $G'_n$ (starting from full occupancy) and a discrete time growth process $(\eta_r)_{r\geq 0}$ on $G_n''$ (again starting from full occupancy); this comes down to a coupling between the Harris system on $G'_n$ and the Bernoulli random variables used to define the growth process. $(\eta_r)$ is to be thought of as a coarse-grained version of $(\xi_t')$. We define $\kappa = e^{\lambda^3 S}$; one time unit for $(\eta_r)$ will correspond to a period of length $\kappa$ for $(\xi_t)$. Our choice of parameters and Proposition \ref{discrete} will guarantee that the extinction time for $(\eta_r)$ is exponential in $n$, and the corresponding fact for $(\xi'_t)$ will be immediate. Given a vertex $x \in V''_n$, we define the neighbourhoods $$\begin{aligned} &\mathcal{N}'(x) = \{y \in V_n': \text{dist}'(x,y) \leq 1\},\\ &\mathcal{N}''(x) = \{x\} \cup \{y \in V_n'': x\stackrel{*}{\sim} y\}. \end{aligned}$$ For $x, y \in V_n''$ with $x\stackrel{*}{\sim} y$, let $b(x,y)$ be the set of vertices of $G'_n$ in the unique path from $x$ to $y$ (notice that this path has length less than $D$). Define $$\Uplambda(x) = \mathcal{N}'(x) \cup \left(\bigcup_{y \in \mathcal{N}''(x),\; y \neq x}\; \mathcal{N}'(y) \cup b(x,y) \right).$$ Assume given a Harris system $H$ for the contact process $(\xi'_t)$. For fixed $x \in V_n''$ and $r \in \{0, 1, \ldots\}$, we will now define an auxiliary process $(\Upgamma[x,r]_t:\; r\kappa \leq t \leq (r+1)\kappa)$ on $\{0,1\}^{\Uplambda(x)}$. For $r\kappa \leq t \leq (r+1)\kappa$ and $y \in \Uplambda(x)$, we put $$\Upgamma[x,r]_t(y) = \mathds{1}\left\{\exists z \in \mathcal{N}'(x):\;\xi'_{r\kappa}(z) = 1,\; (z,\kappa r) \leftrightarrow (y,t) \text{ inside } \Uplambda(x) \text{ in } H\right\}.$$ In particular, note that $\Upgamma[x,r]_{\kappa r} \equiv \xi_{\kappa r}'$ on $\mathcal{N}'(x)$ and $\Upgamma[x,r]_{\kappa r} \equiv 0$ on $\Uplambda(x) \backslash \mathcal{N}'(x)$ and $(\Upgamma[x,r]_t:\; r\kappa \leq t \leq (r+1)\kappa)$ evolves as the contact process on $\Uplambda(x)$. Given a set of vertices $U$ and $\omega \in \{0,1\}^U$, we will say that $U$ is \textit{infested} in $\omega$ if $|\{x\in U: \omega(x) = 1\}| \geq \frac{\lambda}{50}|U|$. \begin{lemma} \label{lem6infested} If $\lambda > 0$ is small enough, the following holds. For any $\sigma > 0$, there exists $S_0$ such that, if $S > S_0$, $$\IP\left[\left.\begin{array}{c}\forall y \in \mathcal{N}''(x),\; \mathcal{N}'(y) \text{ is } \medskip\\\text{infested in }\Upgamma[x,r]_{(r+1)\kappa}\end{array}\right| \;\mathcal{N}'(x) \text{ is infested in } \Upgamma[x,r]_{r\kappa}\right] > 1 - \sigma.$$ \end{lemma} \begin{proof} Lemma 3.1(ii.) and Lemma 3.2 in \cite{MVY} respectively imply \begin{eqnarray}\label{eq:mvy1} && \exists c > 0:\;\text{ if $S$ is large enough, } \text{ then }\nonumber\\[-15pt]\\ \nonumber &&\qquad \mathcal{N}'(x) \text{ infested in } \xi_0 \Longrightarrow P\Ll[\mathcal{N}'(x) \text{ infested in } \xi_\kappa\Rr] > 1 - e^{-c\lambda^2 S}; \end{eqnarray} \begin{eqnarray}\label{eq:mvy2} \nonumber &&\exists c>0: \text{ if $S$ is large enough,}\\[-15pt] \\ \nonumber &&\qquad \mathcal{N}'(x) \text{ infested in } \xi_0 \Longrightarrow P\Ll[\mathcal{N}'(y) \text{ infested in } \xi_\kappa\Rr] > 1-e^{-c\lambda^2 S} \end{eqnarray} (in fact, (\ref{eq:mvy1}) and (\ref{eq:mvy2}) are slightly different from the mentioned results in \cite{MVY}, but are readily seen to follow from their proof. We spare the reader the details.) (\ref{eq:mvy1}), (\ref{eq:mvy2}) and a union bound then give the desired result.\end{proof} We now define the Bernoulli random variables $$\{I^r_{(x,y)}: x,y\in V_n'',\;y\in \mathcal{N}''(x),\; r=0,1,\ldots\}$$ from which the growth process will be defined. They will not be independent, but we will be able to argue that the parameter $S$ may be chosen so that they stochastically dominate a family of independent Bernoulli variables. Set $I^r_{(x,y)} = 1$ if one of the following condition holds:\\ $(\mathsf{C1})\;\mathcal{N}'(x)$ is infested in $\xi'_{r \kappa}$ and $\mathcal{N}'(y)$ is infested in $\Upgamma[x,r]_{(r+1)\kappa};$\\ $(\mathsf{C2})\;\mathcal{N}'(x)$ is not infested in $\xi'_{r \kappa}.$\\ Set $I^r_x = 0$ otherwise. (Condition $\mathsf{(C2)}$ is only present to guarantee that the parameters of the Bernoulli random variables are all close to 1). Now define $(\eta_r)$ starting from $\eta_0 \equiv 1$ and as prescribed in (\ref{eq:defCompQ}). Assume that $\eta_r(x) = 1$. Then, there exist a sequence $x_0,\; x_1,\;\ldots,\;x_{r-1},\; x_r = x$ of vertices of $V_n''$ such that $x_{i+1} \in \mathcal{N}''(x_i)$ and $I^r_{(x_i,x_{i+1})} = 1$ for each $i$. Since $\xi'_0 \equiv 1$, $\mathcal{N}'(x_0)$ is infested in $\xi_0'$, so $I^0_{(x_0,x_1)} = 1$ can only hold if condition $\mathsf{(C1)}$ holds, and thus $\mathcal{N}'(x_1)$ is necessarily infested in $\xi_\kappa'$. Arguing recursively, this implies that $\mathcal{N}'(x_i)$ is infested in $\xi'_{\kappa i}$ for each $i$ and, in particular, $\mathcal{N}'(x)$ is infested in $\xi'_{\kappa r}$. This shows that, if $\eta_r \neq \underline{0}$, then $\xi'_{\kappa r} \neq \underline{0}$. Also note that, for fixed $\sigma > 0$, if we choose $S$ corresponding to $\lambda$ and $\sigma$ in Lemma \ref{lem6infested}, and if $x_1, \ldots, x_m \in V_n''$ are vertices such that the sets $\Uplambda(x_1),\ldots, \Uplambda(x_m)$ are disjoint, we have $$\IP\left[\eta_r(x_j) = 0,\; 1 \leq j \leq m \;|\;(\eta_s)_{0\leq s < r}\right] \leq \sigma^m.$$ Now, using a result of Liggett, Schonmann and Stacey \cite{LSchS} (see also Theorem B26 in \cite{lig99}), given $p \in (0,1)$ we can choose $S$ large enough so that the measure of the field $\{I^r_x: r \geq 0,\;x\in V_n''\}$ stochastically dominates i.i.d. Bernoulli($p$) random variables. We then have \begin{corollary}\label{corEnd} For any $p > p_c(1)$, if $S$ is large enough, then $\{\eta_r\}$ dominates a growth process on $G_n''$ defined from i.i.d. Bernoulli($p$) random variables. \end{corollary} \noindent This, the fact that $|V_n''| \geq \delta n$ and Proposition $\ref{discrete}$ give Theorem $\ref{thm1cd1}$. \end{proof} The rest of the section is devoted to the proof of Proposition \ref{prop6goodSubg}. We start with some remarks concerning the random degree sequence $d_1, \ldots, d_n$. Recall that $S$ is the constant in the construction of $G_n'$; we will assume that $S$ is large enough in the sense of Corollary \ref{corEnd}, and will often need to increase its value. Define $$J_n = \{x \in V_n: \deg(x) \geq S\}.$$ Let $\mu = \sum_{m=1}^\infty m\cdot p(m)$. Let us remark that, if the degrees are given by $d_1, \ldots, d_n$ and we choose a half-edge uniformly at random, then the probability that the corresponding vertex has degree $m$ is $$\frac{m \cdot |x:d_x = m|}{\sum_x d_x} \to \frac{m \cdot p(m)}{\mu}\text{ as } n \to \infty.$$ The probability $q(m) = m\cdot p(m)/\mu$ is called the \textit{size biased distribution}. Recall that $c_0$ and $C_0$ are the constants of (\ref{eqn5compInt0}); by reducing $c_0$ and increasing $C_0$ if necessary, a comparison with an integral gives us, for $m$ large enough, \begin{eqnarray} c_0 < m^{a-1}\cdot p([m,\infty)) < C_0,\label{eqn5compInt1}\\ c_0 < m^{a-2} \cdot q([m,\infty)) < C_0.\label{eqn5compInt2}\end{eqnarray} We will also need the following facts. \begin{lemma} \label{lem5degs} For large enough $S$, there exists $\epsilon > 0$ such that, with probability tending to 1 as $n \to \infty$,\medskip\\ $(i.)\;\displaystyle{ |\{x \in V_n: d_x > S\}| > \epsilon n }$\medskip\\ and, for any $A \subset V_n$ with $|A| \leq \epsilon n$,\medskip\\ $(ii.)\;\displaystyle{\frac{\sum_{x \in A}\;d_x}{\sum_{x \in V_n \cap A^c}\; d_x} < S^{-a};}\qquad\qquad (iii.)\;\displaystyle{\frac{\sum_{x \in J_n \cap A^c} d_x}{\sum_{x \in V_n}d_x} > \frac{1}{2}c_0S^{-(a-2)}. }$\medskip\\ \end{lemma} \begin{proof} Assume that $S$ is large enough that \begin{equation} S^{-a} < \frac{c_0\mu}{8}\; S^{-(a-2)},\qquad C_0\mu\;S^{-2a} < \frac{S^{-a}}{2},\label{eq:5degsa} \end{equation} where $c_0, C_0$ are as in (\ref{eqn5compInt0}). Let $K = S^{\frac{2a}{a-2}}$ and $\epsilon < \frac{1}{2}\;p([K,\infty))$. Define the events $$\begin{aligned} &B_1 = \left\{\left|\{x \in V_n: d_x \geq K\} \right| > \epsilon n\right\};&\qquad B_2 = \left\{\frac{\mu}{2}\;n < \sum_{x \in V_n}d_x < \frac{3\mu}{2}\;n \right\};\\ &B_3 = \left\{\sum_{x \in J_n} d_x > \frac{7c_0\mu}{8}\;n S^{-(a-2)} \right\};&\qquad B_4 = \left\{\sum_{x: d_x \geq K} d_x < nS^{-a}\right\}. \end{aligned}$$ Since, for all $x \in \{1,\ldots, n\}$, $$\begin{aligned} &\mathbb{E}(d_x) = \mu,\quad \IP(d_x \geq K) = p([K,\infty)),\\ &\mathbb{E}\left(d_x \cdot \mathds{1}_{\{d_x \geq K\}} \right) = \mu q([K,\infty) <\mu C_0\;K^{-(a-2)} =\mu C_0\;S^{-2a}< \frac{S^{-a}}{2},\\&\mathbb{E}\left(d_x\cdot \mathds{1}_{\{d_x \geq S\}}\right) = \mu q([S,\infty)) > \mu c_0\;S^{-(a-2)}, \end{aligned}$$ we have $\IP(B_1 \cap B_2 \cap B_3 \cap B_4) \to 1$ as $n \to \infty$. If $B_1$ occurs, since $S < K$, the event of $(i.)$ is satisfied. If $B_1$ and $B_4$ occur, we have \begin{equation}\sum_{x\in A}d_x < \sum_{x:d_x \geq K}d_x < nS^{-a}.\label{eq:5degsb}\end{equation} Now, if $B_1,B_2$ and $B_4$ occur, we have $$\frac{\sum_{x\in A} d_x}{\sum_{x\in V_n\cap A^c}d_x} = \frac{\sum_{x\in A} d_x}{\sum_{x\in V_n}d_x - \sum_{x\in A}d_x}\;\stackrel{(\ref{eq:5degsb}),B_2}{<}\; \frac{S^{-a}n}{\frac{1}{2}\;\mu n - S^{-a}n} < S^{-a},$$ since $\mu \geq 3$ and $S^{-a} << 1/2$. If $B_1, B_2, B_3$ and $B_4$ occur, we also have $$\begin{aligned}&\frac{\sum_{x \in J_n \cap A^c}d_x}{\sum_{x \in V_n }d_x} \; \stackrel{(\ref{eq:5degsb}), B_2, B_3}{>}\;\frac{\frac{7}{8}c_0\mu nS^{-(a-2)}-nS^{-a}}{\frac{3}{2}\mu n} \stackrel{(\ref{eq:5degsa})}{>}\; \frac{\frac{3}{4}c_0\mu nS^{-(a-2)}}{\frac{3}{2}\mu n} = \frac{1}{2}c_0S^{-(a-2)}. \end{aligned}$$\end{proof} In what follows, $\epsilon$ is taken corresponding to $S$ as in the lemma. Let us say that a degree sequence $\mathbf{d} = (d_1, \ldots, d_n)$ is \textit{robust} if it satisfies $(i.), (ii.)$ and $(iii.)$. We will henceforth fix a robust sequence $\mathbf{d}$. We will write $\IP_{\mathbf{d}}$ to denote a probability measure under which the random graph $G_n$ is constructed as follows: the degrees of the $n$ vertices are deterministic, given by $\mathbf{d}$, and the half-edges are then matched in a manner that is chosen uniformly at random among all possibilities, as prescribed in the definition of the configuration model. We now describe an alternative matching procedure that produces the same random graph. This procedure consists of matching the half-edges sequentially, pair by pair, so that, in each step, we are free to choose one of the half-edges involved in the matching, and the other is chosen at random. To be more precise, let us introduce some terminology. A \textit{semi-graph} $g = (V_n, \mathcal{H},\mathcal{E})$ is a triple consisting of the set of vertices $V_n$, a set of half-edges $\mathcal{H}$ and a set of edges $\mathcal{E}$ (of course, if $\mathcal{H} = \varnothing$, then $g$ is a graph). The degree of a vertex in a semi-graph is the number of its half-edges plus the number of edges that are incident to it. Given two half-edges $h, h' \in \mathcal{H}$, we will denote by $h+h'$ a new edge produced by ``attaching'' $h$ and $h'$. We will now show how to define a finite sequence of semi-graphs $g_0, g_1, \ldots, g_k$ so that $g_k$ is a graph with the desired distribution. $g_0 = (V_n, \mathcal{H}_0, \mathcal{E}_0)$ is defined with $\mathcal{E}_0 = \varnothing$ and such that each vertex $x$ has $d_x$ half-edges. Assume $g_i = (V_n, \mathcal{H}_i, \mathcal{E}_i)$ is defined and has half-edges. Fix an arbitrary half-edge $h \in \mathcal{H}_i$ (call this an \textit{elected} half-edge) and randomly choose another half-edge $h'$ uniformly in $\mathcal{H}_i \backslash\{h\}$. Then put $g_{i+1} = (V_n, \mathcal{H}_{i+1}, \mathcal{E}_{i+1})$, where $\mathcal{H}_{i+1} = \mathcal{H}_i \backslash \{h, h'\}$ and $\mathcal{E}_{i+1} = \mathcal{E}_i \cup \{h+h'\}$. When no half-edges are left, we are done, and the graph thus obtained is distributed as $G_n$. Often, instead of updating the sets each time, say from $\mathcal{H}_i, \mathcal{E}_i$ to $\mathcal{H}_{i+1}, \mathcal{E}_{i+1}$ as above, we will hold the notation $g = (V_n, \mathcal{H}, \mathcal{E})$ and say (for example) that $h, h'$ are deleted from $\mathcal{H}$ and $h+h'$ is added to $\mathcal{E}$. In each step of the above construction, we are free to indicate the elected half-edge. A full description of how to elect a half-edge given all previous steps in the construction (and thus the present state of the semi-graph) is an algorithm to construct the graph (or a subgraph of it, if we stop before exhausting all half-edges -- this will be the case for us, since our objective is to construct the subgraph $G_n'$). We will present an algorithm that will help us find $G_n'$ with high probability. The robustness property will come into play because we will have to deal with the set of half-edges after some matchings have been made. Other than doing matchings, our algorithm writes labels on edges and vertices. Labels will serve both to guide the order of the matchings and to define $G_n'$ once the algorithm stops running. At any given point while the algorithm is running, each edge may have no label at all or one of the labels: $\mathsf{included}$ or $\mathsf{excluded}$. Vertices may have no label at all or one of the labels: $\mathsf{included}$, $\mathsf{excluded}$ or $\mathsf{queued}$. The label $\mathsf{queued}$ will only be associated to vertices of $J_n$. In the semi-graph $g_0$, from which the algorithm starts, there are no edges (as mentioned above) and vertices have no labels. Once the algorithm finishes running, $\mathsf{included}$ vertices and edges will be the ones which will constitute $G_n'$. A labelled semi-graph $g=(V_n, \mathcal{H}, \mathcal{E}, \{\ell_x\},\{\ell_e\}, \prec)$ is a semi-graph with labels $\ell_x$ attached to some of the vertices $x$, labels $\ell_e$ associated to some of the edges $e$ and a total order $\prec$ on the set of $\mathsf{queued}$ vertices. It is worth remarking that since the algorithm only does matchings and labelling, it does not change the degree of any vertex. In particular, the definition of the set $J_n$ does not change. The algorithm repeatedly follows a subroutine called a \textit{pass}, which is just a sequence of matchings of half-edges and labellings. When a new pass starts, it typically takes a $\mathsf{queued}$ vertex $\bar x \in J_n$ and successively explores the graph around it by performing matchings. A successful pass is one in which, in fewer than $S^{a-1}$ matchings, at least $S/2$ neighbours of $\bar x$ and two new vertices of $J_n$ are found. We interrupt the pass if any of the matchings it produces reveals a vertex that had been previously ``seen'' by the algorithm. This has to do with the requirement that $G_n'$ be a tree. We first define the pass, and later define the full algorithm. We will need the following values: $$N = S^{a-1}, \qquad \epsilon' = \frac{\epsilon}{2N},\qquad \delta = \frac{\epsilon}{4N}.$$ \newpage \noindent\rule[0.5ex]{\linewidth}{1pt} \textbf{The pass\\ Input:} $g = (V_n, \mathcal{H}, \mathcal{E}, \{\ell_x\},\{\ell_e\}, \prec)$ with at least one $\mathsf{queued}$ vertex.\\ \rule[0.5ex]{\linewidth}{1pt} \\ \textbf{(P1)}\\ Let $\bar x$ be the $\mathsf{queued}$ vertex of highest order. Change the label of $\bar x$ to $\mathsf{included}$.\\ $\mathsf{IF}\; \bar x$ has less than $\frac{S}{2}$ half-edges remaining:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&The pass is stopped in status $\mathsf{B}_1$.\end{tabular}\\ $\mathsf{ELSE}:$\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Define the sets $V^*,\;\mathcal{E}^*$ and $\mathcal{H}^*$ as the sets of \textit{relevant} vertices, edges and half-edges of the pass, respectively. Set $V^* = \mathcal{E}^* = \varnothing$ and $\mathcal{H}^*= \{\text{half-edges attached to $\bar x\}$}$. Endow $\mathcal{H}^*$ with a total order $\prec^*$ chosen arbitrarily. Proceed to (P2).\end{tabular}\vspace{0.3cm}\\ \textbf{(P2)}\\ Let $h$ be the half-edge of highest order in $\mathcal{H}^*$. Choose another half-edge $h'$ uniformly at random in $\mathcal{H} \backslash \{h\}$ and let $v'$ be the vertex of $h'$. Delete $h, h'$ from all sets that contain them ($h$ from $\mathcal{H}$ and $\mathcal{H}^*$, $h'$ from $\mathcal{H}$ and possibly $\mathcal{H}^*$) and add $h+h'$ to $\mathcal{E}^*$ and $\mathcal{E}$. \\ $\mathsf{IF}$ $v'$ has been placed in $V^*$ earlier in this pass:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Give the label $\mathsf{excluded}$ to all vertices contained in $V^*$ (this of course includes $v'$) and all edges contained in $\mathcal{E}^*$. The pass is stopped in status $\mathsf{B}_2$.\end{tabular}\vspace{0.3cm}\\ $\mathsf{ELSE IF}$ $v'$ has been given a label by some earlier pass:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Give the label $\mathsf{excluded}$ to all vertices contained in $V^*$ (this does not include $v'$; the label of $v'$ is left unchanged) and all edges contained in $\mathcal{E}^*$. The pass is stopped in status $\mathsf{B}_2$.\end{tabular}\vspace{0.3cm}\\ $\mathsf{ELSE:}$\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Add $v'$ to $V^*$.\\ &$\mathsf{IF}\;$ $v'$ is not in $J_n$:\\ \begin{tabular}{p{1.3cm} p{10cm}} &Add the half-edges of $v'$ to $\mathcal{H}^*$ (note that at this point $h'$ is no longer a half-edge of $v'$) so that, in the order $\prec^*$, they have arbitrary order among themselves but lower order than all half-edges previously in $\mathcal{H}^*$. \end{tabular}\\ &Proceed to (P3).\end{tabular}\vspace{0.3cm}\\ \textbf{(P3)}\\ $\mathsf{IF}\;\;|V^*| \geq N$:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Give the label $\mathsf{excluded}$ to all vertices of $V^*$ and all edges of $\mathcal{E}^*$. Stop the pass in status $\mathsf{B}_3$. \end{tabular}\\ $\mathsf{ELSE}\;\mathsf{IF}\;\;V^*$ contains more than $S/2$ neighbours of $\bar x$ and $|V^* \cap J_n| \geq 2$:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Give the label $\mathsf{queued}$ to the two vertices of $J_n$ that were first included in $V^*$; in the order $\prec$, assign them lower order than all previously existing $\mathsf{queued}$ vertices and arbitrary order among themselves. Give the label $\mathsf{included}$ to all other vertices of $V^*$ and all edges of $\mathcal{E}^*$. Stop the pass in status $\mathsf{G}$. \end{tabular}\\ $\mathsf{ELSE:}$ \\ \begin{tabular}{p{0.6cm} p{10cm}}&Repeat (P2). \end{tabular}\smallskip\\ \rule[0.5ex]{\linewidth}{1pt}\\ \textbf{Output:} updated labeled semi-graph.\\ \noindent\rule[0.5ex]{\linewidth}{1pt} \newpage \noindent\rule[0.5ex]{\linewidth}{1pt} \textbf{Algorithm to find $G_n'$}\\\textbf{Input:} $g_0 = (V_n, \mathcal{H}_0, \mathcal{E}_0)$, the initial semi-graph with $n$ vertices, no edges, no labels and robust degree sequence $\mathbf{d} = (d_1, \ldots, d_n)$.\\ \rule[0.5ex]{\linewidth}{1pt} \\ \textbf{(A1)}\\ $\mathsf{IF}$ there are no $\mathsf{queued}$ vertices:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Replace the label of all vertices that have been labelled so far and all edges that have been constructed so far by the algorithm with the label $\mathsf{excluded}$ (this re-labelling will be called a \textit{clearing}).\\&Choose an arbitrary unlabelled vertex of $J_n$ and label it $\mathsf{queued}$. \end{tabular}\\ Proceed to (A2).\vspace{0.3cm}\\ \textbf{(A2)}\\ Run the pass. Proceed to (A3). \vspace{0.3cm}\\ \textbf{(A3)}\\ $\mathsf{IF}$ there are more than $\delta n + 2$ $\mathsf{queued}$ vertices:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&The algorithm succeeds and stops.\end{tabular}\\ $\mathsf{ELSE}\;\mathsf{IF}\;$ the pass has been run more than $\epsilon' n$ times:\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&The algorithm fails and stops.\end{tabular}\\ $\mathsf{ELSE}:$\\ \begin{tabular}{p{0.6cm} p{11.5cm}}&Proceed to (A1).\end{tabular}\\ \noindent\rule[0.5ex]{\linewidth}{1pt} We remark that, in step (A1), if the algorithm requires the choice of an unlabelled vertex of $J_n$, it is always possible to find one such vertex. This follows from the fact that each pass labels at most $N$ vertices and the algorithm runs at most $\epsilon'n = \frac{\epsilon}{2N}n$ passes; by the definition of robustness, $N\cdot \frac{\epsilon}{2N}n = \frac{\epsilon}{2}n < |J_n|$. Let us introduce some more notation. Let $i_\infty$ be the total number of passes the algorithm runs. For $1 \leq i \leq i_\infty$, let $\bar x(i)$ be the vertex of $J_n$ whose label is changed from $\mathsf{queued}$ to $\mathsf{included}$ in pass $i$. If pass $i$ ends in status $\mathsf{G}$, then it gives the label $\mathsf{queued}$ to two new vertices $y_1, y_2$; we then write $\mathcal{D}(\bar x(i)) = \{y_1, y_2\}$; if the pass ends in any other status, we write $\mathcal{D}(\bar x(i)) = \varnothing$. Also define $$\mathcal{Q}_\mathsf{G} = \{\bar x(i): \text{Pass $i$ ends in status $\mathsf{G}$}\}.$$ Let $W_0 = 0$ and, for $i \geq 1$, $$\begin{aligned} &W_i = \text{Number of $\mathsf{queued}$ vertices at the time pass $i$ is complete},\\ &X_i = \left\{\begin{array}{ll}1 &\text{if pass $i$ ends in status $\mathsf{G}$};\\-1&\text{otherwise.} \end{array}\right.. \end{aligned}$$ Assume that, at the time pass $i-1$ ends, there are no $\mathsf{queued}$ vertices (so that $W_{i-1} = 0$). The algorithm then goes to step (A3). Assume that the pass has been run for less than $\epsilon' n$ times; then the algorithm proceeds to (A1). At this point, the algorithm performs a clearing, gives the label $\mathsf{queued}$ to an arbitrary vertex $\bar x$ of $J_n$ and starts performing pass $i$; this pass first re-labels $\bar x$ as $\mathsf{included}$, then performs its matchings and either ends in status $\mathsf{G}$ (in which case two new vertices are labelled $\mathsf{queued}$, so that $W_i = 2$) or status $\mathsf{B_1}, \mathsf{B_2}$ or $\mathsf{B_3}$ (in which case no new $\mathsf{queued}$ vertices are created and $W_i = 0$). Thus, when $W_{i-1} = 0$, $W_i = 1 + X_i$. Now assume that, at the time pass $i-1$ ends, $W_{i-1} > 0$ and assume once more that the algorithm does not terminate in (A3), so that (A1) is reached. Then pass $i$ is immediately started, the $\mathsf{queued}$ vertex of highest order is re-labelled as $\mathsf{included}$ and again, either zero or two new $\mathsf{queued}$ vertices appear. Thus, when $W_{i-1} > 0$, $W_i = W_{i-1} + X_i$. These considerations show that, for $1 \leq i \leq i_\infty$, $W_i \geq \sum_{j=1}^i X_j$. We define our subgraph $G_n'$ only on the event that the algorithm is successful. Define $V_n'$ and $E_n'$ as the set of vertices and edges that, at the moment the algorithm stops running, have the label $\mathsf{included}$. Also define $$J_n'= V_n' \cap \mathcal{Q}_\mathsf{G}.$$ We are now ready to prove \begin{lemma}\label{lem:Gnwell} $G_n'$ satisfies properties 1, 2, 3 and 4 and $|J_n'| > \delta n$. \end{lemma} \begin{proof} Let $i_0 = 1 + \max\{i: W_i = 0\}.$ Note that $V_n'$ and $E_n'$ are the sets of vertices and edges that are labelled as $\mathsf{included}$ in passes $i_0, i_0+1,\ldots, i_\infty$, since no clearing occurs between these passes. \noindent $\bullet\;$ Property 1: Fix $x \in V_n'$ and let $i$ be the pass in which $x$ was labelled. We can then find vertices $y_1, \ldots, y_k \in J_n'$ such that $y_1 \in \mathcal{D}(\bar x(i_0)),\; y_2 \in \mathcal{D}(y_1), \ldots, y_k \in \mathcal{D}(y_{k-1})$ and $\bar x(i) \in \mathcal{D}(y_k)$. Then, there is a path of $\mathsf{included}$ edges connecting $\bar x(i_0)$ to $y_1$, $y_1$ to $y_2$, $\ldots$, $y_{k-1}$ to $y_k$, $y_k$ to $\bar x(i)$ and finally, $\bar x(i)$ to $x$. This shows that $G_n'$ is connected. The fact that it is a tree is guaranteed by the $\mathsf{IF}$ statement in (P2) in the definition of the pass: any edge that would produce a loop forces the pass to stop and is labelled $\mathsf{excluded}$. \noindent $\bullet\;$ Property 2: Fix $z \in J_n'$. There exists $i \geq i_0$ such that $z = \bar x(i)$ and pass $i$ ends in status $\mathsf{G}$. This implies that at least $S/2$ neighbours of $z$ are in $V_n'$, that is, $\deg'(z) \geq S/2$. \noindent $\bullet\;$ Property 3: If $y,z \in J_n'$ and $y \stackrel{*}{\sim} z$, we must either have $z \in \mathcal{D}(y)$ or $y \in \mathcal{D}(z)$; assume the former is the case and fix $i$ such that $y = \bar x(i)$. Then, pass $i$ ends in status $\mathsf{G}$, so that at most $N$ edges are constructed in this pass and they form no cycles. Since each vertex has degree larger than 2, we have $${\displaystyle \text{dist}'(y,z) \leq \lceil \log_2 N \rceil = \lceil (a - 1)\log_2 S \rceil < \lambda^4 S = D}$$ when $S$ is large enough. \noindent $\bullet\;$ Property 4: This follows immediately from the fact that $G_n'$ is a tree and each pass labels either zero or two vertices as $\mathsf{queued}$. \noindent $\bullet\;\;|J_n'| > \delta n$. By the definition of $i_0$, pass $i_0$ ends in status $\mathsf{G},\;W_{i_0} = 2$ and $W_i > 0$ for all $i \in \{i_0,\ldots, i_\infty\}$. Since the algorithm ends successfully, $W_{i_\infty} > \delta n + 2$, so there must be more than $\delta n + 2 - 2 = \delta n$ values of $i$ in $\{i_0+1,\ldots, i_\infty\}$ such that $X_i = 1$, and hence, $\bar x(i) \in J_n'$. \end{proof} In order to complete the proof of Proposition \ref{prop6goodSubg}, we now need to prove that the probability that the algorithm ends successfully tends to 1 as $n \to \infty$. To this end, let us first treat individual passes. \begin{lemma} \label{lem5goodpass} For $S$ large enough and $n$ large enough (depending on $S$), the following holds. Assume that, when the pass defines $\bar x$, this vertex has more than $\frac{S}{2}$ half-edges. Then, the pass ends in status $\mathsf{G}$ with probability larger than $\frac{9}{10}$. \end{lemma} \begin{proof} Let $\mathcal{L}$ be the set of labelled vertices at the moment the pass starts. Since the whole algorithm runs at most $\epsilon'n$ passes and each pass labels at most $N$ vertices, we have $|\mathcal{L}| < \epsilon'n\cdot N = \epsilon n/2$. Assume the current pass has already made $k$ matchings, with $0 \leq k < N$, and has not yet terminated, and consider the set $V^*$ of vertices the pass has found in its exploration. We have $|\mathcal{L}\cup V^*| < \epsilon n/2 + N$ and this is much smaller than $\epsilon n$ when $n$ is large. We take the set $A$ in the definition of robustness as $\mathcal{L} \cup V^*$. The half-edge chosen for the $(k+1)$-th matching then has probability:\medskip\\ (1) smaller than $\displaystyle{\frac{\sum_{x \in A}\;d_x}{\sum_{x \in V_n \cap A^c}\; d_x} < S^{-a}}$ of belonging to a vertex of $A$;\medskip\\ (2) larger than $\displaystyle{\frac{\sum_{x \in J_n \cap A^c} d_x}{\sum_{x \in V_n }d_x} > \frac{1}{2}c_0\;S^{-(a-2)}} $ of belonging to a vertex of $J_n \cap A^c$.\medskip\\ Using (1), the probability that the pass ends in status $\mathsf{B}_2$ is less than $N\cdot S^{-a} = S^{-1}$, which is less than $1/20$ when $S$ is large. Using (2), the probability that the pass ends in status $\mathsf{B}_3$ is less than $$P\left[\mathsf{Bin}\left(N,\;\frac{1}{2}c_0 \;S^{-(a-2)}\right) < 2\right],$$ which is also less than $1/20$ when $S$ is large, since the expectation of the Binomial is $\frac{1}{2}c_0\;S$. %$(ii.)\;\displaystyle{\frac{\sum_{x \in A}\;d_x}{\sum_{x \in V_n \cap A^c}\; d_x} < S^{-a};}\qquad\qquad (iii.)\;\displaystyle{\frac{\sum_{x \in J_n \cap A^c} d_x}{\sum_{x \in V_n \cap A^c}d_x} > \frac{1}{2}c_0S^{-(a-2)}. }$\medskip\\ \end{proof} Now define $Y_i = \mathds{1}_{\{\text{Pass $i$ ends in status $\mathsf{B}_1$}\}}.$ If $Y_i = 1$, then $X_i = -1$. By the previous lemma, for any $x_1, \ldots, x_{i-1}, y_1, \ldots, y_{i-1}$ we have \begin{equation}\label{eqn5Xaflem}\P_\mathbf{d}\left[\;X_i = 1 \;|\;\{X_j\}_{j=1}^{i-1} = \{x_j\}_{j=1}^{i-1},\; \{Y_j\}_{j=1}^{i-1}=\{y_j\}_{j=1}^{i-1},\;Y_i = 0\;\right] > 9/10.\end{equation} Let us now exclude the possibility that many passes end in status $\mathsf{B}_1$. \begin{lemma} \label{lem5manyB1}For $S$ large enough, ${\displaystyle \mathbb{P}_\mathbf{d}\left[\sum_{i=1}^{\lfloor \epsilon'n\rfloor} Y_i > \frac{1}{10}\lfloor \epsilon'n \rfloor\right] \xrightarrow{n \to \infty} 0.}$ \end{lemma} \begin{proof}We start remarking that, for $\{Y_i = 1\}$ to occur, there must exist a vertex $x \in J_n$ such that\\ $\bullet\;$ the first time a half-edge of $x$ is chosen for a matching occurs before pass $i$;\\ $\bullet\;$ from this time to the beginning of pass $i$, more than $S/2$ half-edges of $x$ are chosen for matchings;\\ $\bullet\;$ $x$ is the $\mathsf{queued}$ vertex of highest order when pass $i$ starts. Let $h_1, \ldots, h_L$ be the sequence of half-edges chosen at random by the algorithm since the beginning of the first pass. We have $L \leq \epsilon n$. By $(ii.)$ of Lemma \ref{lem5degs}, at the moment $h_j$ is chosen, the probability that it belongs to a vertex that has previously been ``seen'' by the algorithm (that is, a vertex that either has been labelled by an earlier pass or is in the set $V^*$ of the current pass) is less than $S^{-a}$. If this occurs, call it a wasted matching. For $\{\sum Y_i > (1/10)\lfloor \epsilon'n \rfloor\}$ to occur, more than $\frac{1}{10} \lfloor \epsilon'n\rfloor \frac{S}{2}$ wasted matchings must occur. The probability of this is less than $$P\left[\mathsf{Bin}\left(\lfloor \epsilon n \rfloor,\;S^{-a} \right) > \frac{1}{10} \lfloor\epsilon'n\rfloor \frac{S}{2}\right].$$ If $S$ is large, this probability vanishes as $n \to \infty$ since $\frac{\epsilon\; S^{-a}}{\frac{1}{10}\; \epsilon'\;\frac{S}{2}} = 10\;\frac{\epsilon}{\epsilon'} \; \frac{1}{S^{a+1}} = 20\;\;\frac{1}{S^2}.$ \end{proof} \begin{proposition}$\displaystyle{\P_\mathbf{d}\left[W_{\lfloor \epsilon'n \rfloor} > \delta n\right] \xrightarrow{n\to\infty} 1}.$ \end{proposition} \begin{proof} We start constructing auxiliary random variables $X_1', \ldots, X_{\lfloor\epsilon'n\rfloor}', Y_1', \ldots, Y_{\lfloor \epsilon'n \rfloor}'$ whose joint distribution is the same as that of $X_1, \ldots, X_{\lfloor\epsilon'n\rfloor}, Y_1, \ldots, Y_{\lfloor \epsilon'n \rfloor}$. Given sequences $\{x_j\}_{j=1}^{i-1},\; \{y_j\}_{j=1}^{i}$ and $s \in (0,1)$, let $$\begin{aligned} &\upphi\left(s,\{x_j\}_{j=1}^{i-1},\{y_j\}_{j=1}^i\right)\\ &=\left|\begin{array}{ll}-1&\text{if }s \leq \IP_\mathbf{d}\left[X_i = -1\;|\;\{X_j\}_{j=1}^{i-1} = \{x_j\}_{j=1}^{i-1},\;\{Y_j\}_{j=1}^{i} = \{y_j\}_{j=1}^{i} \right] \\1&\text{otherwise.} \end{array} \right. \end{aligned}$$ Likewise, let $$\begin{aligned} &\uppsi\left(s,\{x_j\}_{j=1}^{i-1},\{y_j\}_{j=1}^{i-1}\right)\\&=\left|\begin{array}{ll} 0 &\text{ if } s \leq \P_\mathbf{d}\left[Y_i = 0\;|\;\{X_j\}_{j=1}^{i-1} = \{x_j\}_{j=1}^{i-1},\;\{Y_j\}_{j=1}^{i-1} = \{y_j\}_{j=1}^{i-1}\right]\\1&\text{otherwise.}\end{array}\right. \end{aligned}$$ (when we write only $\upphi(s),\; \uppsi(s)$, we mean the functions above for $X_1$ and $Y_1$, with no conditioning in the probabilities that define them). Let $U_1, U_2, \ldots,\;V_1, V_2, \ldots$ be independent random variables with the uniform distribution on $(0,1)$. Set $X_1' =\upphi(U_1),\; Y_1' = \uppsi(V_1)$ and recursively define, for $1 < i < \epsilon'n$, $$\begin{aligned} &Y_{i+1}' = \uppsi\left(V_{i+1}, \{X_j'\}_{j=1}^{i}, \{Y_j'\}_{j=1}^i\right),\quad X_{i+1}' = \upphi\left(U_{i+1},\{X_j'\}_{j=1}^{i}, \{Y_j'\}_{j=1}^{i+1}\right). \end{aligned}$$ Now, clearly $\{X_i', Y_i'\}_{i=1}^{\lfloor \epsilon'n\rfloor}$ has the same distribution as $\{X_i, Y_i\}_{i=1}^{\lfloor \epsilon'n\rfloor}$. By (\ref{eqn5Xaflem}), we have $\{Y_i' = 0,\;X_i' \neq 1 \} \subset \{U_i \leq \frac{1}{10}\}$. We can now estimate $$\begin{aligned} \P_\mathbf{d}\left[W_{\lfloor \epsilon'n\rfloor} < \frac{\epsilon'}{2}n\right] &\leq \P_\mathbf{d}\left[\sum_i Y_i > \frac{1}{10}\epsilon'n\right] + P\left[\left|\{i: Y_i =0, X_i \neq 1\} \right| > \frac{1}{5}\epsilon'n\right]\\ &\leq \P_\mathbf{d}\left[\sum_i Y_i > \frac{1}{10}\epsilon'n\right] + P\left[\left|\left\{i \leq \epsilon'n: U_i \leq \frac{1}{10}\right\}\right| > \frac{1}{5}\epsilon'n\right]. \end{aligned}$$ The first of these probabilities vanishes by Lemma \ref{lem5manyB1}, and the second by the Law of Large Numbers. \end{proof} \appendix \section{Metastability and limit exponential distributions} Here we state and prove a result that is required for the proof of Theorem \ref{thm2main2}. The contents of this appendix are very similar to Proposition 1.2 in \cite{tommeta}; we have simply adapted that proposition to our setting and notation. \begin{lemma}\label{lem:ap} Let $(G_n) = ((V_n, E_n))$ be a sequence of graphs and assume that, in each graph of the sequence, a graphical construction for the contact process with parameter $\lambda$ is defined. Assume that there exist sequences of positive numbers $(a_n),\; (b_n)$ satisfying \begin{enumerate} \item \label{adtom1}${\displaystyle \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n = \infty, \quad \lim_{n \to \infty} \frac{a_n}{b_n} = 0;}$\medskip \item \label{adtom2}${\displaystyle \lim_{n \to \infty} \; \sup_{A \subset G_n} P_{G_n, \lambda}\left[\xi^A_{a_n} \neq \underline{0},\; \xi^A_{a_n} \neq \xi^{\underline{1}}_{a_n} \right]} = 0;$\medskip \item \label{adtom3} ${\displaystyle \lim_{n \to \infty}\; P_{G_n, \lambda}\left[\uptau_{G_n} < b_n \right] = 0.}$\medskip \end{enumerate} Then, $\uptau_{G_n}/\mathbb{E}[\uptau_{G_n}]$ converges in distribution, as $n \to \infty$, to the exponential distribution of parameter 1. \end{lemma} \begin{proof} Fix $\epsilon > 0$. For each $n$, there exists a unique number $w_n$ such that $P[\uptau_{G_n} \le w_n] = \epsilon$. This follows from the fact that the distribution function of $\uptau_{G_n}$ is continuous, which in turn is a consequence of the fact that $\uptau_{G_n}$ is the hitting time of state $\underline{0}$ for the continuous-time Markov chain $(\xi^{V_n}_t)$. Note that, by (\ref{adtom3}), we have \begin{equation}w_n \ge b_n \text{ for $n$ large enough}. \label{eq:wnbn}\end{equation} We will now establish upper and lower bouds for $\E[\uptau_{G_n}]$. Let us start with the upper bound, which is easier. Since for any $m$, \begin{equation}\label{preUp1} P\left[\uptau_{G_n} > m \cdot w_n\right] \le (1-\epsilon)^m, \end{equation} we have \begin{equation}\E[\uptau_{G_n}] \le w_n \cdot \sum_{m=0}^\infty P[\uptau_{G_n} > m \cdot w_n] \le w_n \cdot \sum_{m=0}^\infty (1-\epsilon)^m \le \frac{w_n}{\epsilon}.\label{preExp1} \end{equation} For the lower bound, for each $n, m \ge 1$, define $$r_{n,m} = (m-1)(w_n - a_n), \qquad s_{n,m} = (m-1)(w_n - a_n) + w_n, \qquad J_{n,m} = [r_{n,m},\; s_{n,m}],$$ so that $|J_{n,m}| = w_n$ and $|J_{n,m} \cap J_{n,m+1}| = a_n$. For the contact process on $G_n$ and $A \subset G_n$, recall the notation $$\xi^{A, s}_t = \left\{x: A \times \{s\} \leftrightarrow (x,t) \right\}, \qquad \xi^{\underline{1}, s}_t = \left\{x \in V_n: V_n \times \{s\} \leftrightarrow (x,t) \right\} \qquad s \le t.$$ Define the events $$\begin{aligned} &E_{n,m} = \left\{\xi^{\underline{1}, r_{n,m}}_{s_{n,m}} \neq \underline{0}\right\},\\[0.2cm]&F_{n,m} = \left\{\xi^{\underline{1},r_{n,m}}_{s_{n,m}} = \xi^{\underline{1}, r_{n, m+1}}_{s_{n,m}}\right\}. \end{aligned}$$ By the definition of $w_n$, we have $P[E_{n,m}] = 1-\epsilon$. Also, (\ref{adtom2}) implies that the probability $P[E_{n,m} \cap (F_{n,m})^c]$ (which does not depend on $m$) tends to 0 as $n \to \infty$. Now also fix $\delta < 1$. By (\ref{adtom1}) and (\ref{eq:wnbn}), if $n$ is large enough we have $a_n/w_n < \delta$ and $P[E_{n,m} \cap (F_{n,m})^c] < \delta$ for any $m$. Then, $$\begin{aligned} P[\uptau_{G_n} > m(1-\delta)\cdot w_n] &\ge P[\uptau_{G_n} > m (w_n - a_n)]\\&\ge P[\uptau_{G_n} > s_{n,m}]\\&\ge P\left[\;\cap_{i=1}^m (E_{n,i} \cap F_{n,i}) \;\right] \\&\ge P\left[\cap_{i=1}^m E_{n,i} \right] - \sum_{i=1}^m P\left[E_{n,i} \cap(F_{n,i})^c \right]. \end{aligned}$$ The first probability on the right-hand side is larger than $(1-\epsilon)^m$ by the FKG inequality (the events $(E_{n,i})_{i \ge 1}$ are increasing). We thus get \begin{equation}\label{preUp2}P[\uptau_{G_n} > m (1-\delta) \cdot w_n] \ge (1-\epsilon)^m - \delta m. \end{equation} Then, for any integer $K > 0$, $$\begin{aligned}\E[\uptau_{G_n}] &\ge (1-\delta) w_n \cdot \sum_{m=1}^\infty P[\uptau_{G_n} > m(1-\delta) \cdot w_n]\\&\ge (1-\delta) w_n \cdot \sum_{m=1}^K P[\uptau_{G_n} > m(1-\delta) \cdot w_n]\\&\ge (1-\delta) w_n\cdot \sum_{m=1}^K[(1-\epsilon)^m - \delta m].\end{aligned}$$ Now, if $K$ is large enough and $\delta$ is small enough (depending on the earlier choice of~$\epsilon$), the above finally gives our lower bound \begin{equation} \label{preExp2}\E[\uptau_{G_n}] \ge (1-2\epsilon)\frac{w_n}{\epsilon}.\end{equation} We are now ready to conclude. Fix $t > 0$. On the one hand, (\ref{preExp2}) and (\ref{preUp1}) give \begin{equation}P[\uptau_{G_n}> t \cdot \E[\uptau_{G_n}]] \le P\left[\uptau_{G_n} > \left \lfloor \frac{t(1-2\epsilon)}{\epsilon} \right \rfloor \cdot w_n \right] \le (1-\epsilon)^{\left \lfloor \frac{t(1-2\epsilon)}{\epsilon} \right \rfloor}.\label{preFin1}\end{equation} On the other hand, (\ref{preExp1}) and (\ref{preUp2}) give \begin{eqnarray}\nonumber && P[\uptau_{G_n}> t \cdot \E[\uptau_{G_n}]] \ge P\left[\uptau_{G_n} > \left \lceil \frac{t}{\epsilon(1-\delta)}\right \rceil(1-\delta)\cdot w_n\right]\\&&\qquad\qquad\qquad\qquad\qquad\ge (1-\epsilon)^{\left \lceil \frac{t}{\epsilon(1-\delta)}\right \rceil} -\delta \cdot \left \lceil \frac{t}{\epsilon(1-\delta)}\right \rceil.\label{preFin2}\end{eqnarray} With proper choices of $\epsilon$ and $\delta$, both the right-hand sides of (\ref{preFin1}) and (\ref{preFin2}) can be made arbitrarily close to $e^{-t}$. This completes the proof. \end{proof} \begin{thebibliography}{99} \bibitem[BA99]{ab} A.\ Barabasi, R.\ Albert. Emergence of scaling in random networks. \emph{Science} \textbf{286}, 509--512 (1999). \bibitem[BBCS05]{BBCS} N.\ Berger, C.\ Borgs, J.T.\ Chayes, A. Saberi. On the spread of viruses on the internet. \emph{Proceedings of the sixteenth annual ACM--SIAM symposium on discrete algorithms}, 301--310 (2005). \bibitem[BBCS14]{BBCS2} N.\ Berger, C.\ Borgs, J.T.\ Chayes, A.\ Saberi. Asymptotic behavior and distributional limits of preferential attachment graphs. \emph{Ann. Probab.}\ \textbf{42} (1), 1--40 (2014). \bibitem[BCP13]{tail} M.\ Bogu\~n\'a, C.\ Castellano, and R.\ Pastor-Satorras. Nature of the epidemic threshold for the susceptible-infected-susceptible dynamics in networks. \emph{Phys.\ Rev.\ Lett.}\ \textbf{111}, 068701 (2013) % C.T.\ Butts. Revisiting the foundations of network analysis. Science 24 July 2009. Vol. 325 no. 5939 pp. 414--416. (argues for the analysis of processes on dynamical networks) \bibitem[BR04]{br} B.\ Bollob\'as, O.\ Riordan. The diameter of a scale-free random graph. \emph{Combinatorica} \textbf{24} (1), 5--34 (2004). \bibitem[CGOV84]{eulalia} M. Cassandro, A. Galves, E. Olivieri, M. Vares. Metastable behavior of stochastic dynamics: a pathwise approach. \emph{J. Statist. Phys.} \textbf{35} (5--6), 603--634 (1984). % C.\ Castellano, R.\ Pastor-Satorras. Thresholds for epidemic spreading in networks. Phys. Rev. Lett. 105, 218701 (2010). (contains predictions on how to scale lambda to 0 with the size of the power-law graph) \bibitem[CD09]{CD} S.\ Chatterjee, R.\ Durrett. Contact process on random graphs with degree power law distribution have critical value zero. \emph{Ann. Probab.} \textbf{37}, 2332--2356 (2009). \bibitem[Ch94]{chencp} J.W. Chen. The contact process on a finite system in higher dimensions. \textit{Chinese J. Contemp. Math.} 15 (1994), 13--20. \bibitem[CF03]{cf} C.\ Cooper, A.\ Frieze. A general model of web graphs. \emph{Random Structures Algorithms} \textbf{22} (3), 311--335 (2003). \bibitem[CMMV14]{cmmv} M.\ Cranston, T.\ Mountford, J.-C.\ Mourrat, D.\ Valesin. The contact process on finite homogeneous trees revisited. \emph{ALEA Lat.\ Am.\ J.\ Probab.\ Math.\ Stat.},\ to appear. %\bibitem[DZ]{dembzeit} A.\ Dembo, O.\ Zeitouni. \textit{Large deviations techniques and applications} (2nd ed.). Applications of mathematics \textbf{38}, Springer (1998). \bibitem[Du1]{durprob} R.\ Durrett, \textit{Probability: theory and examples} (4th ed.). Cambridge university press (2010). \bibitem[Du2]{Dur} R.\ Durrett. \textit{Random graph dynamics}. Cambridge university press (2010). \bibitem[DJ07]{dj} R.\ Durrett, P.\ Jung. Two phase transitions for the contact process on small worlds. \emph{Stochastic Process.\ Appl.}\ \textbf{117} (12), 1910--1927 (2007). \bibitem[DL88]{durliu} R.\ Durrett, X.\ Liu. The contact process on a finite set. \emph{Ann. Probab.} \textbf{16}, 1158--1173 (1988). \bibitem[DS88]{dursc} R.\ Durrett, R.H.\ Schonmann. The contact process on a finite set II. \emph{Ann. Probab.} \textbf{16}, 1570--1583 (1988). \bibitem[DST89]{dursctan} R.\ Durrett, R.H.\ Schonmann, N.\ Tanaka. The contact process on a finite set III: the critical case. \emph{Ann. Probab.} \textbf{17}, 1303--1321 (1989). \bibitem[FCP12]{compare} S.C.\ Ferreira, C.\ Castellano, R.\ Pastor-Satorras. Epidemic thresholds of the susceptible-infected-susceptible model on networks: A comparison of numerical and theoretical results. \emph{Phys.\ Rev.\ E} \textbf{86}, 041125 (2012). \bibitem[Li1]{lig85} T. Liggett, \emph{Interacting particle systems}. Grundlehren der mathematischen Wissenschaften \textbf{276}, Springer (1985). \bibitem[Li2]{lig99} T. Liggett, \emph{Stochastic interacting systems: contact, voter and exclusion processes}. Grund\-lehren der mathematischen Wissenschaften \textbf{324}, Springer (1999). \bibitem[LSS97]{LSchS} T.\ Liggett, R.\ Schonmann, A.\ Stacey. Domination by product measures. \emph{Ann. Probab.} \textbf{25}, 71--95 (1997). \bibitem[Mo93]{tommeta} T.\ Mountford. A metastable result for the finite multidimensional contact process, \emph{Canad. Math. Bull.} \textbf{36} (2), 216--226 (1993). \bibitem[Mo99]{tomexp} T.\ Mountford. Existence of a constant for finite system extinction. \emph{J. Statist. Phys.} \textbf{96} (5--6), 1331--1341 (1999). \bibitem[MVY13]{MVY} T.\ Mountford, D.\ Valesin, Q.\ Yao. Metastable densities for contact processes on random graphs. \emph{Electron. J. Probab.} \textbf{18}, no.\ 103, 1--36 (2013). \bibitem[MV14]{contact_reg}. J.-C.\ Mourrat, D.\ Valesin. Phase transition of the contact process on random regular graphs. Preprint, arXiv:1405.0865 (2014). \bibitem[NSW01]{NSW} M.E.J.\ Newman, S.H.\ Strogatz, D.J.\ Watts. Random graphs with arbitrary degree distributions and their applications. \emph{Phys. Rev. E} \textbf{64}, 026118 (2001). \bibitem[Pe92]{P} R.\ Pemantle. The contact process on trees. \emph{Ann. Probab.} \textbf{20}, 2089--2116 (1992). \bibitem[Sc85]{schonmeta} R.\ Schonmann. Metastability for the contact process. \emph{J. Statist. Phys.} \textbf{41} (3--4), 445--464 (1985). \bibitem[St01]{St} A.\ Stacey. The contact process on finite homogeneous trees. \emph{Probab. Theory Related Fields} \textbf{121} (4), 551--576 (2001). \bibitem[vdH]{vdH} R. van den Hofstad. \emph{Random graphs and complex networks}. Available at \url{http://www.win.tue.nl/\string~rhofstad/NotesRGCN.html} (2014). \bibitem[VM14]{vM} P.\ Van Mieghem. Decay towards the overall-healthy state in SIS epidemics on networks. Preprint, arXiv:1310.3980 (2014). \end{thebibliography} \end{document}