\documentclass[a4paper]{amsart}

\pdfoutput=1

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
%\usepackage[french,english]{babel}
\usepackage{amsthm, amssymb, amsmath, amsfonts, mathrsfs,upgreek}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue,pagebackref=false]{hyperref}


%\usepackage{a4wide}  %\usepackage{fullpage}
%\usepackage{amscd, graphicx, epsfig, psfrag, enumerate, dsfont}

%\usepackage{color}

%\usepackage[pagewise]{lineno}
%\linenumbers

\usepackage{microtype}

%\usepackage[notcite,notref,color]{showkeys}
%\definecolor{labelkey}{gray}{.8}
%\definecolor{refkey}{gray}{.8}

%\definecolor{darkred}{rgb}{0.9,0.1,0.1}
%\newcommand{\comment}[1]{\marginpar{\raggedright\scriptsize{\textcolor{darkred}{#1}}}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{obs}[thm]{Observation}
%\theoremstyle{definition}


\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\subset}{\subseteq}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\mcl}{\mathcal}
\newcommand{\msf}{\mathsf}
\newcommand{\mfk}{\mathfrak}
\newcommand{\dr}{\partial}
\newcommand{\na}{\nabla}
\newcommand{\Ll}{\left}
\newcommand{\Rr}{\right}
\newcommand{\lhs}{left-hand side}
\newcommand{\rhs}{right-hand side}
\newcommand{\1}{\mathbf{1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ov}{\overline}
\newcommand{\un}{\underline}
\newcommand{\td}{\tilde}
\newcommand{\eps}{\varepsilon}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\d}{{\mathrm{d}}}

\renewcommand{\L}{\mathbb{L}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\PP}{\mathbf{P}}
\newcommand{\T}{\mathbb{T}}
\newcommand{\CT}{\mathbb{CT}}
\newcommand{\X}{\mathcal{W}}

\numberwithin{equation}{section}
\renewcommand{\theequation}{\thesection .\arabic{equation}}

%\newenvironment{proofof}{\noindent {\em Proof of\,\,}}{\hspace*{\fill}$\halmos$\medskip}
%\newcommand{\halmos}{\hfill \ensuremath{\Box}}

\title[Phase transition of contact process on random regular graphs]{Phase transition of the contact process on random regular graphs}
\author{Jean-Christophe Mourrat, Daniel Valesin}

\address[Jean-Christophe Mourrat]{ENS Lyon, CNRS, 46 allée d'Italie, 69007 Lyon, France}

\address[Daniel Valesin]{University of Groningen, Nijemborgh 9, 9747AG Groningen, The Netherlands}

\begin{document}
%

\begin{abstract}

We consider the contact process with infection rate $\lambda$ on a random $(d+1)$-regular graph with $n$ vertices, $G_n$. We study the extinction time $\uptau_{G_n}$ (that is, the random amount of time until the infection disappears) as $n$ is taken to infinity. We establish a phase transition depending on whether $\lambda$ is smaller or larger than $\lambda_1(\T^d)$, the lower critical value for the contact process on the infinite, $(d+1)$-regular tree: if $\lambda < \lambda_1(\T^d)$, $\uptau_{G_n}$ grows logarithmically with $n$, while if $\lambda > \lambda_1(\T^d)$, it grows exponentially with $n$. This result differs from the situation where, instead of $G_n$, the contact process is considered on the $d$-ary tree of finite height, since in this case, the transition is known to happen instead at the \emph{upper} critical value for the contact process on $\T^d$. %As part of the proof of the first statement, we show that if $\lambda < \lambda_1(\T^d)$, then the contact process with parameter $\lambda$ dies out on any graph with degree bounded by $d$.

\bigskip

\noindent \textsc{MSC 2010: 82C22; 05C80} 

\medskip

\noindent \textsc{Keywords: interacting particle system, contact process, random graph, configuration model} 

\end{abstract}
%
\maketitle
%
%
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
\section{Introduction}
\label{s:intro}
Let $G = (V, E)$ be a locally finite and connected graph. 
%The contact process with parameter $\lambda > 0$ on $G$ is a continuous-time Markov process on $\{0,1\}^V$ with generator $\mathcal{L}$ defined, for any local function $f: \{0,1\}^V \to \R$ and any configuration $\xi \in \{0,1\}^V$, by
%$$(\mathcal{L}f)(\xi) = \sum_{x \in V} \Ll[f(\xi^{0\to x}) - f(\xi)\Rr] + \lambda \sum_{x,y\in V}\Ll[\1_{\{\xi(x) = 1\}} \cdot n(x,y) \cdot (f(\xi^{1 \to y}) - f(\xi)) \Rr],$$
%where
%$$\xi^{i \to x}(z) = \begin{cases} i &\text{if } z = x;\\\xi(z)&\text{otherwise},\end{cases}$$
%$\1$ is the indicator function, and $n(x,y)$ is the number of edges between $x$ and $y$ (which we allow to be larger than 1).
%
%Vertices of the graph are interpreted as individuals, and states 0 and 1 indicate that an individual is healthy or infected, respectively. The transitions that appear in the definition of $\mathcal{L}$ are then understood as follows: $\xi \to \xi^{0 \to x}$ means that there is a \textit{recovery} at $x$, and $\xi \to \xi^{1 \to x}$ means that there is a \textit{transmission} to $x$ (this is necessarily triggered by a neighbour $y \sim x$ with $\xi(y) = 1)$. We refer the reader to \cite{lig99} for a thorough introduction to the contact process, including the facts that we state without proof in this introduction.
%
%
The contact process on~$G$ with parameter $\lambda > 0$ is the 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. We identify subsets of $V$ with elements of $\{0,1\}^V$ (through the indicator function).

The contact process is usually thought of as a model for the spread of an infection in a population. Vertices of the graph are interpreted as individuals, and states 0 and 1 indicate that an individual is healthy or infected, respectively. 
%The transitions that appear in the definition of the contact process are then understood as follows: 
An infected site \emph{recovers} with rate $1$ and \emph{infects} a neighbouring site with rate $\lambda$ times the number of connecting edges (we will allow for multiple edges connecting a given pair of vertices). We refer the reader to \cite{lig99} for a thorough introduction to the contact process, including the facts that we state without proof in this introduction.


%We often abuse notation and, for a set $S$, treat an element $\xi \in \{0,1\}^S$ as the same as the set $\{x\in S: \xi(x) = 1\}$; 
%The configuration identically equal to zero is denoted by $\varnothing$. 
We denote by $(\xi^A_t)_{t \geq 0}$ the contact process on $G$ with initial configuration $\xi^A_0 \equiv A$. If $A = \{x\}$, we write $(\xi^x_t)$ instead of $(\xi^{\{x\}}_t)$. We write $P_{G,\lambda}$ for a probability measure under which the contact process with parameter $\lambda$ on $G$ is defined.% (the initial configuration will always be clear from the context). 

The \textit{extinction time} $\uptau^A_G$ for the contact process on $G = (V,E)$ with initial configuration $A \subset V$ is defined by
$$\uptau^A_G = \inf\{t: \xi^A_t = \varnothing\}.$$
Since the dynamics only allows for new infections to appear by transmission, the configuration $\varnothing$ is absorbing, so we have $\xi^A_t = \varnothing$ for any $t \geq \uptau^A_G$. We write $\uptau_G$ instead of $\uptau^G_G$ and $\uptau^x_G$ instead of $\uptau^{\{x\}}_G$.



When the contact process is considered on infinite graphs, a central question is whether we have survival or extinction of the infection. 


\smallskip

For a graph $G = (V, E)$, a finite set $A \subset V$ and $\lambda > 0$, define
$$\begin{aligned}&p_{G,A,\lambda}^{\text{ext}}= P_{G,\lambda}\Ll[\uptau_{G}^A < \infty\Rr]= P_{G,\lambda}\Ll[\exists t_0: \xi^A_t = \varnothing \text{ for all } t \geq t_0\Rr] ,\\
&p_{G,A,\lambda}^{\text{loc ext}} =  P_{G,\lambda}\Ll[\exists t_0: \xi^A_t \cap A = \varnothing \text{ for all } t \geq t_0\Rr],\end{aligned}$$
the probabilities of \textit{extinction} and \textit{local extinction} of the contact process with parameter $\lambda$ on $G$ started from $\xi^A_0 \equiv A$. It can be shown that %, depending on the value of $\lambda$ 
we either have $p^{\text{ext}}_{G,A,\lambda} = 1$ for all $A$ or $p^{\text{ext}}_{G,A,\lambda} < 1$ for all $A$; likewise, either $p^{\text{loc ext}}_{G,A,\lambda} = 1$ for all $A$ or $p^{\text{loc ext}}_{G,A,\lambda} < 1$ for all $A$. We say that the contact process
\begin{itemize}
\item \textit{dies out} if $p^{\text{ext}}_{G,A,\lambda} = 1$ for all $A$;
\item \textit{survives weakly} (or \textit{globally but not locally}) if $p^{\text{ext}}_{G,A,\lambda} < 1$ and $p^{\text{loc ext}}_{G,A,\lambda} = 1$ for all $A$;
\item \textit{survives strongly} (or \textit{locally}) if $p^{\text{loc ext}}_{G,A,\lambda} < 1$ for all $A$.
\end{itemize}
We let $\lambda_1(G) = \sup\{\lambda: p^{\text{ext}}_{G,A,\lambda} = 1\}$ and $\lambda_2(G) = \sup\{\lambda: p^{\text{loc ext}}_{G,A,\lambda} = 1\}$. 


\smallskip



It is well known that for $G = \Z^d$,  $0< \lambda_1(\Z^d) = \lambda_2(\Z^d) =:\lambda_c(\Z^d) < \infty$. For $G = \T^d$, the infinite, $(d+1)$-regular tree (with $d \geq 2$), the situation is quite different, as we then have $0<\lambda_1(\T^d) < \lambda_2(\T^d) <\infty$. In this case, if we take $\lambda$ such that $\lambda_1(\T^d) < \lambda < \lambda_2(\T^d)$ and start the process from a single infection at a vertex $x$, then the infection has a chance of surviving, but it can only do so by propagating outwards from $x$; any finite neighbourhood of $x$ only carries the infection for a finite amount of time, as required in the definition of weak survival.

The contact process on finite graphs (deterministic or random) has also been the subject of much investigation; below we will survey some of the past work that is most relevant to the object of interest of this paper. Let us start noting that for finite graphs, there is no question of survival or extinction: if $G$ is finite, the infection almost surely disappears in finite time. One is thus interested in the behaviour of the infection before it disappears. The typical course of action goes as follows: we fix $\lambda$ and the parameters that define the graph, then take a size parameter (e.g.\ the number of vertices) to infinity, so as to obtain a sequence of graphs $G_n$, and consider the asymptotic behaviour of some random quantity $X_n$ associated with the contact process on $G_n$. Common choices for $X_n$ are the extinction time $\uptau_{G_n}$ and the average proportion of infected vertices before $\uptau_{G_n}$. Of particular interest are the cases in which the asymptotic behaviour of $X_n$ depends sensitively on the choice of~$\lambda$ and the set of parameters that define the graph; this dependency can sometimes be related to a phase transition of the contact process on an infinite graph that is in some sense approximated by $G_n$.

This project has been first carried out for $G_n$ equal to the subgraph of $\Z^d$ induced by the vertices contained in a box of side length $n$; see %\cite{eulalia}, \cite{schonmeta}, \cite{durliu}, \cite{chencp}, \cite{dursc}, \cite{tommeta}, \cite{tomexp}, or Section I.3 of \cite{lig99} 
\cite{eulalia,schonmeta,durliu,chencp,dursc,tommeta,tomexp}, or \cite[Section I.3]{lig99} for an overview. As suggested in the previous paragraph, the behaviour of $\uptau_{G_n}$ exhibits a phase transition that mimics the phase transition of the contact process on $\Z^d$: $\uptau_{G_n}$ grows logarithmically or exponentially with the volume of $G_n$ respectively if $\lambda$ is taken smaller or larger than~$\lambda_c(\Z^d)$.

%Let us now turn to finite trees. Let $\hat{\T}^d_\ell$ denote the subgraph of $\T^d$ induced by the vertex set given by a distinguished vertex $o$ (called the root) and all vertices at graph distance at most $\ell$ from $o$, and let $\T^d_\ell$ denote the sub-graph of $\hat{\T}^d_\ell$ where one of the sub-trees emanating from the root is removed. In \cite{St} and \cite{cmmv13}, the contact process on $\hat{\T}^d_\ell$ is studied (to be precise, these papers rather focus on $\T^d_\ell$, but their results and proofs are unaffected by this modification). In \cite{St}, bounds were obtained on $\uptau_{\hat{\T}^d_\ell}$ for different values of $\lambda$, and these bounds were improved in \cite{cmmv13} to yield the result below. We denote by $|A|$ the cardinality of a set $A$.

Let us now turn to finite trees. Let $\T^d_\ell$ denote the $d$-ary tree of height $\ell$. In other words, $\T^d_\ell$ is a tree with a distinguished vertex $o$ (called the root) so that $o$ has degree $d$, all vertices at distance between 1 and $\ell-1$ from $o$ have degree $d+1$ and all vertices at distance $\ell$ from $o$ have degree 1. %In \cite{St} and \cite{cmmv13}, the contact process on ${\T}^d_\ell$ was studied. 
In \cite{St}, bounds were obtained on $\uptau_{{\T}^d_\ell}$ for different values of $\lambda$, and these bounds were improved in \cite{cmmv13} to yield the result below. %We denote by $|A|$ the cardinality of a set $A$.


\begin{thm} \cite{cmmv13} 
\label{t:cut-trees}
%Recall that $d \geq 2$.
%
\noindent (a) For any $\lambda \in (0,\; \lambda_2(\T^d))$, there exists $c \in (0,\infty)$ such that, as $\ell \to \infty$, $$\frac{\uptau_{ {\T}^d_{\ell}}}{\log | {\T}^d_\ell|} \to c \text{ in probability.}$$


\noindent (b) For any $\lambda \in (\lambda_2(\T^d),\infty)$, there exists $C \in (0,\infty)$ such that, as $\ell \to \infty$,
$$\frac{\log \uptau_{ {\T}^d_\ell}}{|{\T}^d_\ell|} \to C \text{ in probability.}$$
Moreover, $\uptau_{ {\T}^d_\ell}$ divided by its expectation converges in distribution to the exponential distribution with parameter 1.
\end{thm}
In short, the asymptotic behaviour of the extinction time on ${\T}^d_\ell$ has a phase transition at the value $\lambda = \lambda_2(\T^d)$. It is worth mentioning that the above theorem remains true if $\T^d_\ell$ is replaced by $\hat \T^d_\ell$, defined as the subgraph of $\T^d$ induced by the vertex set given by a distinguished root vertex $o$ and all vertices at graph distance at most $\ell$ from $o$ ($\T^d_\ell$ is obtained from $\hat{\T}^d_\ell$ by removing one of the sub-trees emanating from the root of $\hat{\T}^d_\ell$).

The main goal of this paper is to investigate the asymptotic behaviour of the extinction time of the contact process on random $(d+1)$-regular graphs, which we now describe. Fix $n \in \N$, the number of vertices, with the restriction that $n(d+1)$ be even. Let us define a random graph $G_n$ with vertex set $V_n = \{1, \ldots, n\}$. We endow each vertex with $d+1$ half-edges; attaching two half-edges (say, one belonging to vertex $i$ and another to vertex $j$) produces an edge between $i$ and $j$. Then, any perfect matching on the set of half-edges produces a graph (again we note that we allow for multiple edges between two vertices and also edges with both extremities at a single vertex). We choose one perfect matching uniformly at random from all the $(n(d+1)-1)\cdot (n(d+1)-3)\cdots 3 \cdot 1$ possibilities, and this produces the random edge set $E_n$. Obviously, $G_n$ is a $(d+1)$-regular graph; by using an alternate construction of $G_n$ that is described in Section~\ref{s:super}, it is easy to show that, for any $R$, with probability tending to 1 as $n \to \infty$, the ball of radius $R$ around a given vertex has no cycle, and is thus isomorphic to $\hat{\T}^d_R$.

We write $\P_n$ for the law of $G_n$, and $\P_{n,\lambda}$ for a probability measure under which both $G_n$ and the contact process on $G_n$ with parameter $\lambda$ are defined. Our main result is
\begin{thm}\label{t:mainsup}\noindent %Assume $d \geq 3$.
\noindent (a) For every $\lambda \in (0, \lambda_1(\T^d))$ there exists $C < \infty$ such that
$$\lim_{n \to \infty} \P_{n,\lambda}\Ll[\uptau_{G_n} < C\log(n)\Rr] = 1.$$

\noindent (b) For every $\lambda \in (\lambda_1(\T^d), \infty)$ there exists $c > 0$ such that
$$\lim_{n\to \infty}\P_{n,\lambda}\Ll[\uptau_{G_n} > e^{cn}\Rr] = 1.$$  
\end{thm}

Let us stress the most important point: contrary to the situation in Theorem~\ref{t:cut-trees}, the behaviour of the extinction time has here a phase transition at $\lambda_1(\T^d)$ instead of $\lambda_2(\T^d)$. 
%
Although surprising at first, this phenomenon can be understood as follows:
%
%In particular, the order of magnitude of $\uptau_{\T^d_\ell}$ in the weak survival regime is the same as that for the extinction regime. This is not surprising given the comment we have made above concerning weak survival: the infection can only attempt to survive by distancing itself from the root, and on $\T^d_\ell$ this can only happen until the leaves are reached. 
%
when $\ell$ is large, the tree ${\T}^d_\ell$ \emph{as seen from a vertex chosen uniformly at random} does not at all locally look like $\T^d$. For example, with non-vanishing probability, the random vertex is a leaf of ${\T}^d_\ell$. The notion of local limit of a sequence of graphs, as formalized in \cite{bs}, captures such features, and one can check that ${\T}^d_\ell$ does not converge locally to $\T^d$, but rather to another infinite graph called the \textit{canopy tree} $\CT^d$ (see \cite[Example 5.14]{benj} for details). Moreover, one can show that 
\begin{equation}
\label{critct}
\lambda_1(\CT^d) = \lambda_2(\CT^d) = \lambda_2(\T^d)
\end{equation}
(local survival for $\lambda > \lambda_2(\T^d)$ can be derived from \cite[Theorem~1.6]{cmmv13}, while extinction for $\lambda \le \lambda_2(\T^d)$ follows from \cite[Proposition~4.57]{lig99}). In light of this, the logarithmic-exponential phase transition for the extinction time on ${\T}^d_\ell$ does happen at the \emph{lower} critical value of the limiting graph after all, but one must take into account that this limiting graph is the canopy tree.
%reflect an extinction-survival phase transition after all: that of the canopy tree.


It would be very interesting to find wider classes of graphs (such as the configuration model described below, or see \cite{vdH} for an exposition) for which one can prove that the same phase transition occurs at the lower critical value of the limiting graph. This is reminiscent of the question of the locality of the percolation critical probability, see \cite{bnp}, \cite[Section~5.2]{benj}, \cite{mt} and \cite{sxz}.

%Later in this Introduction, we will recall a notion of local graph limit and then note that $\T^d_\ell$ does not converge locally to $\T^d$, but rather to another infinite graph called the \textit{canopy tree} (denoted $c\T^d$). We will also argue that $\lambda_1(c\T^d) = \lambda_2(\T^d)$. In light of this, the logarithmic-exponential phase transition for the extinction time on $\T^d_\ell$ does reflect an extinction-survival phase transition after all: that of the canopy tree.

%Apart from this discussion, it is natural to wonder if, for classes of graphs whose local limit actually is $\T^d$, $\lambda_1(\T^d)$ plays the role of threshold for a change of behaviour of the extinction time. The natural candidate is the random $d$-regular graph, which we now describe. 

The graph $G_n$ is a particular case of the class of graphs known as the \textit{configuration model}. Whereas for $G_n$ we assumed that all degrees are taken equal to $d+1$, in the configuration model one allows for a random degree sequence, typically i.i.d. from some fixed degree distribution. The contact process on these graphs has lately received attention (\cite{cd09,mmvy,mvy}). In particular, it was proved that, if the degree distribution is a power law (and the graph is assumed to be connected), then the extinction time grows exponentially with the number of vertices \textit{regardless of the value of $\lambda$}. In this sense, one can say that the contact process on the configuration model with a power law degree distribution has no phase transition: it is ``always supercritical''. Theorem \ref{t:mainsup} shows that, if the degrees are constant, then there is a phase transition. In fact, putting together Lemma \ref{lem:stdom} below with the main result of \cite{mmvy}, we get

\begin{thm}
Let $\mathcal{G}_{n,d}$ be the set of connected graphs with $n$ vertices and degree bounded by $d+1$.
\begin{itemize}
\item[(a)] For any $\lambda \in (0, \lambda_1(\T^d))$, there exists $C < \infty$ such that 
$$\lim_{n \to \infty} \inf_{G \in \mathcal{G}_{n,d}} P_{G,\lambda}\Ll[\uptau_G < C \log n\Rr] = 1.$$
\item[(b)] For any $\lambda \in (\lambda_c(\Z), \infty)$, there exists $c > 0$ such that
$$\lim_{n \to \infty} \inf_{G \in \mathcal{G}_{n,d}} P_{G,\lambda}\Ll[\uptau_G > e^{cn}\Rr] = 1.$$
\end{itemize}
\end{thm} 
In particular, if we take the contact process on the configuration model with a degree distribution with \textit{bounded support}, the extinction time exhibits a phase transition on $\lambda$. A problem that we believe to be of much interest is whether such a phase transition also occurs if the degree distribution has unbounded support, but a light tail. Equally interesting is the corresponding question for supercritical Erd\H{o}s-R\'enyi random graphs. In this direction, we refer the reader to the very recent remarkable results of \cite{mensin}, where existence of a phase transition for the contact process on certain graphs with unbounded degrees, such as Delaunay triangulations of $\R^d$, is shown.

\medskip


We now comment on the proofs of the two parts of Theorem \ref{t:mainsup}. Part (a) relies on the fact, stated in Lemma \ref{lem:stdom}, that the contact process on any graph of degree bounded by $d+1$ is stochastically dominated (in terms of the number of infected vertices) by a contact process with  the same  $\lambda$ on $\T^d$. Although this is a very elementary and natural statement, we did not find it in the literature, so we give a proof, which relies on the concept of universal covering of a graph. Once Lemma \ref{lem:stdom} has been established, we invoke known bounds for the extinction time of the contact process on $\T^d$ in the extinction regime in order to conclude the proof of part (a).

As a side note, we remark that Lemma \ref{lem:stdom} also applies to infinite graphs, and as a consequence we prove:
\begin{thm}
\label{t:univsub}
If $\lambda \leq \lambda_1(\T^d)$, then the contact process with parameter $\lambda$ on any graph with degree bounded by $d+1$ dies out.
\end{thm}

The proof of part (b) of Theorem \ref{t:mainsup} is more involved,  and relies on a geometric property of $G_n$ (Theorem~\ref{t:regen}). The idea can be roughly summarised as follows. Assume that at time $0$, there are $\delta n$ infected vertices ($\delta > 0$ small) with the property that within distance $r$ of each of these vertices, one can find a copy of $\T^d_\ell$, the copies (and the paths to them) being pairwise disjoint. Let us say that a set satisfying this property is \emph{regenerative}. If $\ell$ can be chosen sufficiently large, then after some time, the infection will spread to $k \delta n$ vertices with $k$ large, except for an event whose probability is exponentially small in $n$. The crucial geometric property of $G_n$ that we need is that if $k$ is sufficiently large, then with probability tending to $1$, \emph{any} subset of size $k\delta n$ contains a regenerative subset of size $\delta n$. This enables to iterate the argument. Since the probability of failure of a given step is exponentially small, the extinction time must be exponentially long.

\medskip

%There exist $\epsilon, \epsilon', r, \ell > 0$ which do not depend on $n$ and such that, with high probability as $n \to \infty$, $G_n$ satisfies the following. For any set  of vertices $A$ with $|A| = \epsilon n$, we can find vertices $y_1, \ldots, y_{\epsilon'n} \in A$ and subgraphs of $T_{y_1},\ldots,T_{y_{\epsilon'}n} \subset G_n$ so that the $T_{y_i}$ are all disjoint copies of $\T^d_\ell$ and the graph distance between $y_i$ and the root of $T_{y_i}$ is less than $r$. With this at hand, we assume that at time 0 the vertices of $A$ are infected and use large deviation estimates for the binomial distribution to argue that the following happens outside of probability exponentially small in $\epsilon'n$. For some subset $\{z_{1},\ldots, z_{\sigma n}\} \subset A'$, with $\sigma < \epsilon'$, the infection initially present at each of the $z_i$'s reaches the root of $T_{z_i}$, and from there propagates in the direction of the leaves, so that at some fixed time $S$, we can find a large number of infected vertices inside each $T_{z_i}$. We show that the resulting total number of infected vertices at time $S$ is larger than $\epsilon n$, and then we redefine $A$ to be this new set of infected vertices and repeat.

In Section \ref{s:prelim}, we give a summary of the notation we use, an exposition of the graphical construction of the contact process and some known results about the contact process on trees.
% and finally some comments regarding the contact process on the canopy tree. 
Sections \ref{s:super} and \ref{s:subcrit} are devoted to proving parts (b) and (a) of Theorem \ref{t:mainsup} respectively.

\section{Notation and preliminary results}\label{s:prelim}
\subsection{Summary of notation for sets and graphs.}
For a set $A$, we write $|A|$ for the cardinality of $A$ and $\1_A$ for the indicator function of $A$.

We will bother the reader with defining graphs, because we want to allow loops (edges between a vertex and itself) and multiple edges with the same endpoints, and this requires some care with the notation.
Given sets $V$ and $E$ and a function 
$$\zeta: E \to \{\text{subsets of $V$ with cardinality 1 or 2}\},$$
the triple $G = (V, E, \zeta)$ is a \textit{graph}; elements of $V$ are \textit{vertices} and elements of $E$ are \textit{edges}. $e \in E$ is said to be an edge between vertices $x$ and $y$ if $\zeta(e) = \{x,y\}$; if such an edge exists, we say that $x$ and $y$ are neighbours. If $\zeta(e) = \{x\}$, we say $e$ is a loop at $x$.

We may abuse notation and write $v \in G$ instead of $v \in V$ when convenient. Also, we will omit the presence of the function $\zeta$, simply writing $G = (V, E)$ as is usual.


The \textit{degree} of a vertex is the number of non-loop edges that contain it plus twice the number of loops that contain it. The \textit{graph distance} between vertices $x$ and~$y$ is the length of a shortest path between $x$ and $y$, and is denoted by $\mathsf{dist}(x,y)$, or $\mathsf{dist}_G(x,y)$ when we want to make the graph explicit. A \textit{cycle} is a sequence of vertices $x_0, \ldots, x_k$ so that $x_0, \ldots, x_{k-1}$ are all distinct, $x_k = x_0$ and for each $i$, $x_i$ and $x_{i+1}$ are neighbours. 

The set $\vec{E}$ of oriented edges of $G$ is defined as follows: for each non-loop $e \in E$, we add to $\vec{E}$ two oriented edges corresponding to the two possible orientations of $e$; for each loop in $e$, we also add to $\vec{E}$ two ``oriented edges'' from $x$ to $x$ (though this will be quite unimportant). A generic element of $\vec{E}$ will be denoted by $\vec{e}$. Note that, if there are $k$ edges containing $x$ and $y$, then there are $2k$ oriented edges containing $x$ and $y$. We write $v_0(\vec{e})$ and $v_1(\vec{e})$ to denote the starting and ending vertex of $\vec{e}$, respectively. We also let $u(\vec{e}) \in E$ denote the unoriented edge to which $\vec{e}$ is associated.

A \emph{rooted graph} is a pair $(\rho,G)$ where $G$ is a graph and $\rho \in G$. Given two rooted graphs $(\rho, G)$ and $(\rho', G')$ with $G = (V, E)$, $G' = (V', E')$, we say that $f : V \to V'$ is an \emph{embedding} of $(\rho,G)$ into $(\rho',G')$ if 
\begin{itemize}
\item $f(\rho) = \rho'$,
\item $f$ is injective,
\item for every $u,v \in V$, the number of edges in $G$ containing $u$ and $v$ is less than or equal to the number of edges of $G'$ containing $f(u)$ and $f(v)$. 
\end{itemize}
(Of course, if $G$ and $G'$ have no loops or multiple edges between vertices, the last property means that $f(u)$ and $f(v)$ are neighbours in $G'$ whenever $u$ and $v$ are neighbours in $G$.)
We say that $(\rho',G')$ \emph{embeds} $(\rho,G)$ if there exists an embedding of $(\rho, G)$ into $(\rho',G')$; that $(\rho,G)$ and $(\rho',G')$ are \emph{isomorphic} if each embeds the other.


For the rest of the paper, we fix $d \geq 2$ and omit $d$ from $\T^d$ and $\T^d_\ell$, thus writing $\T$ and $\T_\ell$ respectively. The root of $\T_\ell$ is denoted by $o$.



\subsection{Graphical construction of the contact process.}
Almost every paper on the contact process contains a brief exposition of its graphical construction, so this is by now quite a redundant addition. We nevertheless include it here because we allow our graphs to contain loops and parallel edges, so we need to be careful with the notation to avoid confusion.  

Fix a graph $G = (V,E)$ and an infection rate $\lambda > 0$. Assume given the following families of independent Poisson point processes on $[0,\infty)$: $(T_{\vec{e}})_{\vec{e} \in \vec{E}}$, all with rate $\lambda$, and $(D_x)_{x \in V}$, all with rate 1.  We now imagine $G$ is embedded on the $xy$-plane and add marks on the vertical lines $(V\cup \vec{E}) \times [0,\infty)$ as follows: for each $x$ and each $t \in D_x$, we add a so-called \textit{recovery mark} at $(x,t)$, and for each $\vec{e}$ and each $t \in T_{\vec{e}}$, we add a so-called \textit{transmission arrow} at $(\vec{e},t)$.

 Given $x,y \in V$ and $0 \leq s \leq t$, we say that $(x,s)$ and $(y,t)$ are connected by an \textit{infection path} (and write $(x,s) \leftrightarrow (y,t)$) if there exists a right-continuous function $\gamma:[s,t] \to V$ such that \begin{itemize}
\item $\gamma(s) = x,\;\gamma(t) = y$,
\item  $(r,\gamma(r)) \notin  D_{\gamma(r)}$ for all $r \in [s,t]$,
\item $\gamma(r-) \neq \gamma(r)$ implies $r \in T_{\vec{e}}$ for some $\vec{e}$ with $v_0(\vec{e}) = \gamma(r-),\;v_1(\vec{e}) = \gamma(r)$.
\end{itemize}
In other words, $(r,\gamma(r))_{s\leq r \leq t}$ must be a path from $(x,s)$ to $(y,t)$ which does not cross any recovery mark and is allowed to traverse transmission arrows.

For $x \in V$, let $\xi^x_t = \{y \in V: (x,0) \leftrightarrow (y,t)\}$; for $A \subset V$, let $\xi^A_t = \cup_{x \in A} \;\xi^x_t$. Then, $(\xi^A_t)_{t\geq 0}$ is a Markov process on $\{0,1\}^V$ with the same distribution as the process defined earlier in \eqref{eq1gen}. The graphical construction has the advantage that all the contact processes $((\xi^A_t)_{t\geq 0})_{A \subset V}$ are defined in the same probability space and, if $A \subset B$, then $\xi^A_t \subset \xi^B_t$ for all $t$. Note also that $\xi^A_{s+t} = \cup_{x\in \xi^A_{t}} \{y:(x,t) \leftrightarrow (y,t+s)\}$.

\subsection{Known results on the contact process on $\T$}
We now list some definitions and results about the contact process on $\T$ which we will need; all of them can be found in Section I.4 of \cite{lig99}. The reader is encouraged to skip this subsection and refer back to it when each result is needed.

We start defining a ``generation number'' function $\ell: \T \to \Z$ as follows. Take an embedding $\kappa: \Z \to \T$ so that $\kappa(0) = o$. If $x \in \kappa(\Z)$, set $\ell(x) = \kappa^{-1}(x)$. If $x \notin \kappa(\Z)$, let $y$ be the first vertex of $\kappa(\Z)$ reached in a path from $x$ to $\kappa(\Z)$; set $\ell(x) = \ell(y) + \mathsf{dist}(x,y)$.

Now, given $\rho > 0$, as in \cite{lig99} equation (4.23), page 87, we put
$$\phi_\lambda(\rho) = \lim_{t \to \infty} \mathbb{E}_{\T, \lambda}\left[\sum_{x \in \T} \xi^o_t(x) \cdot \rho^{\ell(x)}\right]^\frac{1}{t};$$
the limit is shown to exist (page 87). In Proposition 4.27(a) and (b) we respectively have
\begin{equation} \label{eq:clligD}
\phi_\lambda(\rho) = \phi_\lambda\Ll(\frac{1}{\rho d}\Rr)
\end{equation}
and
\begin{equation} \label{eq:clligA}
\mathbb{E}_{\T,\lambda}\Ll[|\xi^o_t|\Rr] \leq C_\lambda \cdot \phi_\lambda(1)^t,\quad t \geq 0,
\end{equation}
for some constant $C_\lambda > 0$. In Proposition 4.44(a), we have
\begin{equation}
\label{eq:clligB}
\frac 1 {\sqrt{d}} \le \rho < \rho' \ \ \text{ and } \  \phi_\lambda(\rho') \geq 1 \quad \implies \quad  \phi_\lambda(\rho) < \phi_\lambda(\rho').
\end{equation}

As in equation (4.48), page  96, we define for $\lambda > 0$
\begin{equation}\label{eq:def_beta}\beta(\lambda) = \lim_{n \to \infty} \P_{\T,\lambda}\left[\exists t: \xi_t(\kappa(n)) = 1\right]^\frac{1}{n};\end{equation}
again the limit is shown to exist (page 96). Regarding $\beta$, we will need the following facts, which can be found in Theorem 4.83, Corollary~4.87 and Theorem 4.130 of \cite{lig99}:
\begin{equation}
\label{eq:clligC}
\beta(\lambda) < \frac 1 {\sqrt{d}} \quad \implies \quad \phi_\lambda(\beta(\lambda)) = \phi_\lambda\Ll(\frac{1}{\beta(\lambda)\cdot d}\Rr) = 1,
\end{equation}
\begin{equation}
\label{eq:clligE} \beta(\lambda_1) = \frac{1}{d},
\end{equation}
\begin{equation}
\label{eq:clligF} \beta \text{ is strictly increasing in } [0,\lambda_2(\T)].
\end{equation}

\section{Supercritical regime}

The goal of this section is to prove part (b) of Theorem~\ref{t:mainsup}. We first state for later usage a classical large deviation result on binomial random variables, whose proof is standard.
\begin{lem}
\label{l:largedev}
Let $\mathsf{Bin}(m,p)$ denote a binomial random variable with parameters $m \in \N$ and $p \in [0,1]$ (defined with respect to the measure $\P$, say). For every $\delta \ge 0$, 
$$
\P[\mathsf{Bin}(m,p) \ge (p+\delta) m] \le e^{-m \psi_p(\delta)},
$$
where
\begin{eqnarray}
\label{defpsip}
\psi_p(\delta) &  = & \sup_{\lambda} \Ll[ \lambda (p+\delta) - \log(1-p+pe^\lambda )  \Rr] \notag \\
& = & (p+\delta) \log\Ll( \frac{p+\delta}{p} \Rr) + (1-p-\delta) \log\Ll( \frac{1-p-\delta}{1-p} \Rr) .
\end{eqnarray}
\end{lem}


We will need the following estimate:
\label{s:super}
\begin{lem}
\label{l:ss}
For every $\lambda > \lambda_1(\T)$, there exist $R$, $p_0 > 0$ and $\alpha_0 > 1$ such that, for $\ell$ large enough,
$$
P_{\T_\ell,\lambda}\Ll[ \left|\xi^o_{R\ell} \right|  \ge \alpha_0^\ell  \Rr] \ge p_0.
$$
\end{lem}
\begin{proof}
Let $\T_\infty$ be the infinite, rooted, $d$-ary tree (that is, the infinite rooted tree in which the root $o$ has degree $d$ and all other vertices have degree $d+1$). In \cite{ss98} it is shown that for every $\lambda> \lambda_1(\T)$, there exist $U> 0$, $\gamma > 1$ and $p > 0$ such that, for  $\ell \in \N$ large enough,
\begin{equation}\label{eq:ss_first_equation}
P_{\T_\infty,\lambda}\Ll[\left| \xi^o_{U\ell} \right| \ge \gamma^\ell  \Rr] \ge p,
\end{equation}
where $\beta(\lambda)$ is defined in \eqref{eq:def_beta}.
We remark that:
\begin{enumerate}
\item the above estimate follows from equation (2.6) in \cite{ss98};
\item the running hypothesis in \cite{ss98} is that $\lambda > \lambda_2(\T)$, but \eqref{eq:ss_first_equation} holds true more generally, for $\lambda > \lambda_1(\T)$. Indeed, its proof depends on two ingredients. First, their Lemma 1, which in fact holds for \textit{any} $\lambda > 0$. Second, an argument involving branching processes (see the paragraphs preceding their equation (2.6)) which is applicable as long as $d \cdot \beta(\lambda) > 1$. By \eqref{eq:clligE} and \eqref{eq:clligF}, this is indeed the case when $\lambda > \lambda_1(\T)$;
\item we can then choose $\gamma$ as any constant between 1 and $d \cdot \beta(\lambda)$.
\end{enumerate}

 Using equation (4.76) in \cite{lig99}, one can readily show that there exists $S > 0$ such that, for all $t > 0$,
\begin{align*}
&P_{\T_\infty,\lambda}\Ll[\xi^o_{s}(y) = 0 \text{ for all } s \leq t \text{ and } y \text{ with } \mathsf{dist}(o,y) \geq St\Rr]\\&\geq P_{\T,\lambda}\Ll[\xi^o_{s}(y) = 0 \text{ for all } s \leq t \text{ and } y \text{ with } \mathsf{dist}(o,y) \geq St\Rr] > 1-\frac{p}{2}.
\end{align*}
Combining these two estimates and setting $R = S^{-1}$ and $\alpha_0= \gamma^{R/U} > 1$ we get
\begin{align*}
\frac{p}{2} &\leq P_{\T_\infty,\lambda}\Ll[|\xi^o_{R\ell}| \geq \alpha_0^\ell,\; \xi^o_s(y) = 0 \text{ for all } s \leq R\ell \text{ and } y \text{ with } \mathsf{dist}(o,y) \geq \ell \Rr]\\
&\leq P_{\T_\ell,\lambda} \Ll[ |\xi^o_{R\ell}| \geq \alpha_0^\ell\Rr]. \qedhere
\end{align*}
\end{proof}

We have the following consequence of the above result:

\begin{lem}
\label{l:ss1}
For every $\lambda > \lambda_1(\T)$ and $r> 0$, there exist $R$, $\sigma > 0$ and $\alpha > 1$ such that for every $\ell$ large enough, the following holds. For any graph $G$ with vertices $x, y$ such that $\mathsf{dist}(x,y) \leq r$ and $(y,G)$ embeds $(o,\T_\ell)$, we have
$$P_{G,\lambda}\Ll[|\xi^x_{R\ell}| \geq \alpha^\ell\Rr] > \sigma.$$
\end{lem}
\begin{proof}
Let $R$, $p_0$ and $\alpha_0$ be as in the previous lemma; we have
$$P_{G,\lambda}\Ll[|\xi^x_{R(\ell + 1)}| \geq \alpha_0^\ell\Rr] \geq P_{G,\lambda}\Ll[\xi^x_R(y)= 1\Rr] \cdot P_{G,\lambda}\Ll[|\xi^y_{R\ell} | \geq \alpha_0^\ell\Rr] \geq P_{G,\lambda}\Ll[\xi^x_R(y)= 1\Rr] \cdot p_0.$$
We can now find $\sigma > 0$  that bounds the right-hand side from below uniformly on $\mathsf{dist}(x,y) \in \{1,\ldots, r\}$ (one can guarantee that the event $\{\xi^x_R(y) = 1\}$ occurs by making finitely many prescriptions on Poisson processes in the graphical construction on a geodesic path connecting $x$ and $y$ and the time interval $[0,R]$). We then pick any $\alpha \in (1,\alpha_0)$; the result follows from observing that $\alpha_0^{\ell - 1} > \alpha^\ell$ for $\ell$ large enough.  
\end{proof}
We say that a set of vertices $W \subset V_n$ is $\ell$\emph{-regenerative} if there exists a family $(G_v')_{v \in W}$ of subgraphs of $G_n$ that are pairwise disjoint and such that for every $v \in W$, the following two conditions hold:
\begin{itemize}
\item $G_v'$ contains $v$,
\item there exists $x \in G_v'$ such that the distance in $G_v'$ between $x$ and $v$ is $4$ and $(x,G_v')$ embeds $(o,\T_\ell)$.
\end{itemize}
%
The crucial geometric property of $G_n$ that we need is 
\begin{thm}[Finding large regenerative subsets]
For any $\ell \in \N$ and $\eps > 0$ sufficiently small (depending on $\ell$), the following holds with $\P_n$-probability tending to $1$ as $n$ tends to infinity. From every $W \subset V_n$ of cardinality at least $\eps n$, one can extract an $\ell$-regenerative subset of cardinality at least $\frac{\eps}{40d^6} n$.
\label{t:regen}
\end{thm}

\begin{rem} In what follows, in order to prevent the notation from getting too heavy, we will pretend that certain quantities, such as $\epsilon n$ in the above proposition, are integers. It should be clear that in a correct but overscrupulous writing, one should take the pertinent integer parts or add or subtract 1 at certain places, but that this does not change our proofs in any relevant way.
\end{rem}

We prove part (b) of Theorem~\ref{t:mainsup} using Theorem~\ref{t:regen}, before turning to the proof of the latter.

\begin{proof}[Proof of part (b) of Theorem~\ref{t:mainsup}]
We fix $\lambda > \lambda_1(\T)$, and choose constants according to the following steps:
\begin{enumerate}\item let $\alpha,R,\sigma$ correspond to $\lambda$ and $r  = 4$, as in Lemma \ref{l:ss1}; 
\item take $\ell$ large enough, as required by Lemma \ref{l:ss1}, and also so that $\alpha^\ell > \frac{80d^6}{\sigma}$;
\item take $\epsilon$ corresponding to $\ell$ as in Theorem~\ref{t:regen}.
\end{enumerate}
Assume $G_n$ satisfies the property stated in Theorem~\ref{t:regen}, namely
$$\text{every }W \subset V_n \text{ with }|W| \geq \epsilon n \text{ has an $\ell$-regenerative subset of cardinality $\frac{\epsilon}{40d^6} n$}.$$
We will now prove that, for some constant $c > 0$ which does not depend on $n$,
\begin{equation}
\label{eq:equiv}\text{for all }W \subset V_n \text{ with } |W| \geq \epsilon n,\; P_{G_n}\Ll[|\xi^W_{R\ell}| \geq \epsilon n\Rr] \geq 1 - e^{-cn}.
\end{equation}
This will imply the statement of Theorem \ref{t:mainsup}.

We fix $W$ with $|W|\geq \epsilon n$ and extract from it an $\ell$-regenerative subset $W'$ of cardinality $n':=\frac{\epsilon}{40d^6} n$; we enumerate its elements, $W'=\{v_1,\ldots, v_{n'}\}$. By the definition of $\ell$-regenerative sets, there exist pairwise disjoint subgraphs of $G$, $G'_{v_1},\ldots, G'_{v_{n'}}$ such that $v_i \in G'_{v_i}$ and there exists $x_i \in G'_{v_i}$ such that $\mathsf{dist}(v_i,x_i) = 4$ and $(x_i,G'_{v_i})$ embeds $(o,\T_\ell)$.

For each $v_i$, let $(\zeta^{v_i}_t)_{t \geq 0}$ be the contact process on $G'_{v_i}$, started from only $v_i$ infected, and built using the same family of Poisson processes as the original contact process on $G$. If $i \neq j$, then $(\zeta^{v_i}_t)$ and $(\zeta^{v_j}_t)$ are independent (since the $G'_{v_i}$'s are disjoint) and moreover, $\xi^W_t \supseteq \xi^{W'}_t \supseteq \cup_{v \in W'}\; \zeta^{v}_t$ for all $t$.

Define the events
$$E_i = \left\{|\zeta^{v_i}_{R\ell} | \geq \alpha^\ell\right\},\qquad 1 \leq i \leq n'.$$
We then have $P_{G_n}\Ll[E_i\Rr] \geq \sigma$. Thus, by standard large deviation estimates for binomial random variables (see Lemma \ref{l:largedev}), we have $$P_{G_n}\Ll[\sum_{i=1}^{n'} \1_{E_i} \geq \frac{\sigma}{2}n'\Rr] \geq 1 - e^{-c(\epsilon,\sigma)n}.$$
Finally, if the event in the above probability occurs, we have
$$|\xi^W_{R\ell}| \geq \alpha^\ell\cdot \sum_{i=1}^{n'} \1_{E_i}  \geq  \alpha^\ell \cdot \frac{\sigma}{2}n'> \epsilon n.$$
This completes the proof.
\end{proof}



We now give some definitions and preliminary results for the proof of Theorem~\ref{t:regen}. We say that a set of vertices $W \subset V$ is \emph{well separated} if the following two properties hold:
\begin{itemize}
\item for every $v \in W$, the 3-neighbourhood of $v$ is cycle-free (for $r \in \mathbb{N}$, the $r$-neighbourhood of a vertex $v \in V$ is the set of vertices $w$ whose distance to $v$ is at most $r$), 
\item for every two distinct $v,w \in W$, the 3-neighbourhoods of $v$ and $w$ are disjoint.
\end{itemize}
The key step of the proof lies in the following proposition.
\begin{prop}[Key estimate]
\label{p:key}
For every $\ell \in \N$, there exists $c > 0$ such that for every $\eps > 0$ suficiently small (depending on $\ell)$ and every $n$ large enough,
$$\P\Ll[\begin{array}{c}\text{the set $\{1,\ldots, \eps n\}$ is well separated but}\\\text{has no $\ell$-regenerative subset of size $\eps n/5$}   \end{array}\Rr] \le (c\eps^\frac{6}{5})^{\eps n}.$$
\end{prop}
\begin{rem}
In order to prove Theorem~\ref{t:regen}, we will use a union bound over all sets of cardinality $\eps n$. Roughly speaking, there are about $\eps^{-\eps n}$ such sets ($\eps \ll 1$). So the crucial point in Proposition~\ref{p:key} is that the exponent $\frac {6}{5}$ appearing there is strictly larger than $1$.
\end{rem}
Before proving this key estimate, we introduce some terminology. A \emph{semi-graph} $g = (V,\mcl{E},\mcl{H})$ is a triple consisting of a set $V$ of vertices, a set $\mcl{E}$ of edges between points of $V$, and a set $\mcl{H}$ of \emph{half-edges}, each half-edge being attached to some vertex in $V$. Given two half-edges $h$ and $h'$, we write $h+h'$ to denote the edge obtained by ``gluing together'' the half-edges $h$ and $h'$ (that is to say, if $h$ is attached to a vertex $v$ and $h'$ to a vertex $w$, then $h+h'$ is an edge connecting $v$ and $w$). The distance in the semi-graph $g$ is simply the distance in the graph $(V,\mcl{E})$.

Consider the semi-graph $g = (V_n, \mcl{E}, \mcl{H})$ such that $\mcl{E} = \emptyset$ and each vertex in $V_n$ has exactly $d+1$ half-edges. We can construct a random regular graph with distribution $\P_n$ by the following recursive procedure. Take an arbitrary half-edge $h$ in $\mcl{H}$ (call it the \emph{elected} half-edge); take a half-edge $h'$ uniformly at random in $\mcl{H} \setminus \{h\}$; add the edge $h+h'$ to the set $\mcl{E}$, remove the half-edges $h$ and $h'$ from $\mcl{H}$; repeat until the set of half-edges is empty. (Recall that we assume $(d+1)n$ to be even, so that there is an even number of half-edges to begin with). The resulting random graph has law $\P_n$. A feature of this procedure that will be crucial in our reasoning is that at each step, we have the freedom to choose the elected half-edge as we wish among the half-edges of $\mcl{H}$. 

It will be convenient to write operations on sets such as those done in the above construction in the more symbolic form
\begin{equation}
\label{update}
\mcl{E} \leftarrow \mcl{E} \cup \{h+h'\}, \qquad \mcl{H} \leftarrow \mcl{H} \setminus\{h,h'\}.
\end{equation}







\begin{proof}[Proof of Proposition~\ref{p:key}]
Fix $\ell \in \N$. Also fix $\epsilon \in (0,1)$ and $n \in \N$; for the moment we do not specify their choice. We take the semi-graph $g = (V_n, \mcl{E}, \mcl{H})$ such that $\mcl{E} = \emptyset$ and such that every site has exactly $(d+1)$ half-edges. We denote by $\mcl{W}$ the set of vertices $\{1,\ldots, \eps n\}$.
 As long as there is a half-edge $h$ attached to a vertex at distance 2 or less from $\mcl{W}$, we choose this as the elected half-edge, pick another half-edge $h'$ uniformly at random from $\mcl{H} \setminus \{h\}$, and do the operations in \eqref{update}. When there is no longer any such half-edge, the graph is still incomplete, but we can already decide if $\mcl{W}$ is well separated, since we have revealed all the 3-neighbourhoods of vertices in $\mcl{W}$ (and nothing more). If the set is not well separated, we can stop. On the event that the set is well separated, we continue our construction of the graph, with the aim of showing that $\mcl{W}$ will contain a good subset of size $\eps n/5$ with high probability. 

Let $\mcl{F}$ be the set of vertices still having $(d+1)$ half-edges at this point. We call elements of $\mcl{F}$ \emph{fresh} vertices (they are still unseen by our construction of the graph). Elements of $\X$ will be called \emph{seeds}. Recall that since we consider only the event that $\X$ is well separated, for every seed $\rho$, the 3-neighbourhood of $\rho$, rooted at $\rho$, is isomorphic to $(o, \mathbb{T}_3)$; moreover, every vertex $x$ at distance 3 from $\rho$ has exactly $d$ half-edges attached to it at this point.

Below we will give a procedure to continue electing half-edges and thus continue the construction of the graph; at any point in the construction, we say that a seed $\rho$ is \emph{active} if there are at least 3 half-edges attached to vertices at distance 3 from $\rho$ (as of now, there are $(d+1)d^3$ such half-edges).

A seed that is not active will be called \emph{quiet}. As of now, every seed is active. We let $\rho$ be any active seed (as of now, this only means that we take $\rho \in \X$), and run the pass described below.
\newpage
%\newpage

\bigskip 
\noindent\rule[0.5ex]{\linewidth}{1pt}

\noindent \textbf{The pass} started from the active seed $\rho$.

\medskip
Let $\ov{V}$ be the set of vertices at distance 3 or less from $\rho$ and let $\ov{\mcl{E}}$ be the set of edges with both extremities in $\ov{V}$. Let $\ov{\mcl{H}}$ be the set of half-edges attached to vertices of $\ov{V}$; by the definition of an active seed, $\ov{\mcl{H}}$ has at least $3$ elements.

\medskip

\noindent  \maltese$\rangle$ Let $v \in \ov{V}$ be at distance strictly less than $\ell + 4$ from $\rho$ as measured in the graph $(\ov{V}, \ov{\mcl{E}})$, and such that there is a half-edge $h \in \ov{\mcl{H}}$ attached to it. If such a $v$ does not exist, then declare that the pass is a \emph{success} and stop. Otherwise, pick $h'$ uniformly at random in $\mcl{H} \setminus \{h\}$, and let $v'$ be the vertex to which it is attached. If $v' \notin \mcl{F}$, then declare that a \emph{collision} occurs (say that it is a \emph{short collision} if moreover, $v' \in \ov{V}$; that it is a \emph{long collision} otherwise).

\begin{itemize}
\item  If it is the second time during the pass that a collision occurs, then declare that the pass is a \emph{failure}, do the updates
\begin{equation}
\label{updatep1}
\mcl{E} \leftarrow \mcl{E} \cup \{h+h'\}, \qquad \mcl{H} \leftarrow \mcl{H} \setminus\{h,h'\},
\end{equation}and stop the pass. 
\item If it is the first time during the pass that a collision occurs, do the updates
\begin{equation}
\label{updatep2}
\mcl{E} \leftarrow \mcl{E} \cup \{h+h'\}, \qquad \mcl{H} \leftarrow \mcl{H} \setminus\{h,h'\},\qquad \ov{\mcl{H}} \leftarrow \ov{\mcl{H}} \setminus \{h,h'\},
\end{equation}
and go back to  \maltese$\rangle$.

\item If a collision does not occur (that is, if $v' \in \mcl{F}$), then do the updates
\begin{eqnarray*}&&\mcl{E} \leftarrow \mcl{E} \cup \{h+h'\}, \quad \mcl{H} \leftarrow \mcl{H} \setminus\{h,h'\},\quad \ov{\mcl{H}} \leftarrow \ov{\mcl{H}} \setminus \{h\},\\&& 
\ov{V} \leftarrow \ov{V} \cup \{v'\},\quad \mcl{F} \leftarrow \mcl{F} \setminus \{v'\},\quad \ov{\mathcal{E}} \leftarrow \ov{\mathcal{E}} \cup \{h + h'\},
\end{eqnarray*}
and finally add the remaining half-edges of $v'$ to $\ov{\mcl{H}}$.
Then go back to  \maltese$\rangle$.

\end{itemize}
\medskip



\noindent\rule[0.5ex]{\linewidth}{1pt}


\medskip
\begin{obs} In (\ref{updatep2}), we only need to remove $h'$ from $\ov{\mcl{H}}$ in case of a short collision; if the collision is long, then $h'$ is not an element of $\ov{\mcl{H}}$ at this point.
\end{obs}

We then iterate this pass, \textbf{always starting with an active seed that has not been the starting point of any previous pass}, until every seed is quiet or has already been used as the starting point of a pass.

%This algorithm is designed to discover an $(h,r)$-good subset of $\X$ ``as fast as possible''. 

We now list some important observations concerning the effect of passes.
\begin{obs}[The effect of a successful pass]
\label{pass_gives_favourable}
If the pass is a success, we define $G_\rho' = (\ov{V},\ov{\mcl{E}})$. This subgraph of $G_n$ is a tree satisfying:
\begin{itemize}
\item[(a)] $\rho$ is in the vertex set,
\item[(b)] there exists $x \in \ov{V}$ such that $\mathsf{dist}_{G_\rho'}(\rho,x) = 4$ and $(x, G_\rho')$ embeds $(o, \T_\ell)$.
\end{itemize}
Let us verify (b); to this end, we introduce some notation. Given a vertex $x \in \ov{V}$, we let $\ov{V}_x$ be the set of vertices $y \in \ov{V}$ such that the unique path in $G_\rho'$ from $y$ to $\rho$ contains $x$, then let $\ov{\mcl{E}}_x$ be the set of edges of $\ov{\mcl{E}}$ with both extremities in $\ov{V}_x$, and finally let $G_{\rho,x}' = (\ov{V}_x, \ov{\mcl{E}}_x)$. Now, if there were no collisions in the pass, then there are at least three distinct vertices $x_1,x_2,x_3$ such that $\mathsf{dist}_{G_\rho'}(x_i, \rho) = 4$ and $(x_i,G_{\rho,x_i}')$ is isomorphic to $(o,\T_\ell)$ for each $i$, so (b) holds. If one collision occurred in the pass, then at most two of these subtrees is compromised by missing edges, so that there still exists some $x$ with $\mathsf{dist}_{G_\rho'}(x, \rho) = 4$ and $(x,G_{\rho,x}')$ isomorphic to $(o,\T_\ell)$.

Apart from satisfying the properties listed above, $G_\rho'$ does not intersect any subgraph $G_{\hat  \rho}'$ obtained from previous passes.
\end{obs}

\begin{obs}[Many fresh sites]
\label{many_fresh}
During one pass, at most 
$$
c_\ell := (d+1)d^3 + (d+1)d^4 + \cdots + (d+1)d^{\ell + 4} 
$$
iterations of the instruction \maltese\ are performed, so in particular at most $c_\ell$ vertices are removed from the set $\mcl{F}$ of fresh vertices. Initially, there are $$
n-|\X|(1+(d+1) + (d+1)d + (d+1)d^2)
$$
fresh vertices. Since we start with $|\X|$ active seed vertices, we can run the pass no more than $|\X|$ times. At any given time, there are thus at least
$
n - c_{\ell}' |\X|
$
fresh vertices, where
$$
c_{\ell}' := 1 + (d+1) + (d+1)d + \cdots + (d+1)d^{\ell + 4}.
$$
\end{obs}
\begin{obs}[Many passes]
\label{many_passes}
It may occur, due to half-edges being removed in collisions, that a seed becomes inactive before it is used in a pass (let us say that it is then \textit{ruined}). Recall that for a seed $\rho$,\begin{itemize}\item there are initially $(d+1)d^3$ half-edges attached to vertices at distance 3 from $\rho$; \item $\rho$ remains active as long as at least 3 of these half-edges are still present; \item any given pass which starts from some other seed $\rho'$ can cause the removal of at most two of these half-edges.\end{itemize} In conclusion, it takes at least $\frac{(d+1)d^3 - 3}{2}$ passes started from other seeds to ruin the seed $\rho$. Taking this into account we see that, if we run the pass $t$ times, then at most
$$
t + t\cdot \frac{2}{(d+1)d^3 -3}
$$
seeds become inactive (namely, those that are being explored by each pass and those that are  ruined by collisions). In other words, since we start with $|\X| = \varepsilon n$ seeds, we can run the pass at least 
$$\Ll(1 + \frac{2}{(d+1)d^3 -3}\Rr)^{-1} |\X| \ge \frac{4}{5}\varepsilon n$$
 times without running out of active seeds (since $d \geq 2$).\end{obs}

Let us now estimate the probability that a pass is a failure. By observation \ref{many_fresh}, the probability to find a collision while running an iteration of instruction \maltese\  (that is, at each moment in the pass in which we pick a half-edge uniformly at random) is bounded above by
$$\frac{dc_\ell'|\X|}{(d+1)(n-c_\ell'|\X|)} \leq \frac{c_\ell'\varepsilon}{1-c_\ell'\varepsilon}.$$
Hence, the probability that a double collision is found during a pass (or in other words: the pass fails due to the occurrence of two collisions) is smaller than
$$
\P\Ll[\mathsf{Bin}\Ll(c_\ell,\frac{c_\ell'\varepsilon}{1-c_\ell'\varepsilon}\Rr) \ge 2 \Rr],
$$
where we used the fact that during one pass, we iterate instruction \maltese\ at most $c_{\ell}$ times. Hence, we can choose $\eps$ sufficiently small (depending on $d$ and $\ell$) so that
\begin{equation}
\label{e:prob_fail}
\begin{array}{c}
\text{the probability for a pass to fail is less than } c' \eps^2,
\end{array}
\end{equation}\vspace{.03cm}
where $c' = (c_\ell c_\ell')^2$.
\vspace{.03cm}

The probability that at least $\frac{3}{5}\eps n$ passes fail due to double collisions is thus bounded by
$$
\P\Ll[ \mathsf{Bin}\Ll( |\X|, c' \eps^2 \Rr) \ge \frac{3}{5}\eps n \Rr] = \P\Ll[ \mathsf{Bin}\Ll(   \eps n, c' \eps^2 \Rr) \ge \frac{3}{5} \eps n \Rr],
$$
using \eqref{e:prob_fail} and the fact that we run at most $|\X|$ passes. Applying Lemma~\ref{l:largedev} with $m =\eps n = |\X|$ , $p = c' \eps^2$ and  $
p+\delta = \frac{3}{5}$, we see that this probability is bounded by
$$
\exp\Ll\{- |\X| \Ll[\frac{3}{5} \log\Ll( \frac{3}{5c'\eps^2} \Rr)  + \frac{2}{5} \log\Ll( \frac{2}{5(1-c'\eps^2)}\Rr)   \Rr] \Rr\}.
$$
Hence, the probability above is bounded by $(c\eps^{\frac{6}{5}})^{|\X|}$ for some constant $c$ independent of $\eps$.

To sum up, we have shown that in our procedure, we 
\begin{itemize}
\item run at least $\frac45\eps n$ passes;
\item have at most $\frac{3}{5}\eps n$ failed passes
 with probability larger than $1-(c\eps^{\frac{6}{5}})^{|\X|}$.
\end{itemize}
This is exactly what we need to conclude, as was explained in Observation~\ref{pass_gives_favourable}.
\end{proof}
\begin{cor}
\label{c:key}
For every $\ell \in \N$ and $\eps > 0$ sufficiently small,
$$\P \left[\begin{array}{l}\text{from every well-separated set $W \subset V_n$ of size $\eps n$,}\\\text{one can extract an $\ell$-regenerative subset of size $\eps n/5$} \end{array}\right] \xrightarrow{n \to \infty} 1. $$
\end{cor}
\begin{proof} Take $c, \eps$ corresponding to $\ell$ as in Proposition~\ref{p:key}. For large enough $n$, the probability for a given well-separated set $W \subset V_n$ of size $\eps n$ not to contain any $\ell$-regenerative subset of size $\eps n/5$ is smaller than $(c \eps^{\frac{6}{5}})^{ \eps n}$. We prove the corollary by a union bound, counting the total number of sets $W \subset V_n$ of size $\eps n$. This number is
$$
{n \choose \eps n} \le \frac{n^{\eps n}}{( \eps n)!}.
$$
Using the fact that $\log n! \ge n \log n - n$ (which can be proved by induction on $n$), we see that
$$
\log {n \choose \eps n} \le  \eps n \log n -  \eps n \log( \eps n) +  \eps n = \eps n\Ll(1+\log\Ll(\frac{1}{\eps}\Rr)\Rr).
$$
By reducing the value of $\eps > 0$ if necessary, we can ensure that
$$
(c \eps^{\frac{6}{5}})^{\eps n} \exp\Ll[ \eps n\Ll(1+\log\Ll(\frac{1}{\eps}\Rr)\Rr)  \Rr]
$$
tends to $0$ as $n$ tends to infinity, and this proves the result.
\end{proof}




\begin{proof}[Proof of Theorem~\ref{t:regen}]
The number of cycles in $G_n$ of size bounded above by $3$ remains tight as $n$ tends to infinity (in order to see this, it suffices to check that the expectation of the number of such cycles remains bounded). In particular, with probability tending to 1, there are less than $\sqrt{n}$ cycles of size bounded by 3. We assume from now on that the event that there are no more than $\sqrt{n}$ cycles of size bounded by 3 is realized.

For any site $v \in V$, the size of its $6$-neighbourhood is no more than
$$
1 + (d+1) + (d+1) d + \cdots + (d+1)d^{5} \leq 4d^6.
$$
We observe that if $m \in \N$ and $U$ is a set of $m$ vertices, we can extract from $U$ a subset of $m/(4d^6)$ vertices whose $3$-neighbourhoods are pairwise disjoint. To see this, let $x_1$ be an arbitrary point of $U$. Then, the set $U'$ obtained by removing from $U$ all points that belong to the $6$-neighbourhood of $x_1$ has size at least $m - 4d^6$. Moreover, the $3$-neighbourhood of any point of $U'$ is disjoint from the $3$-neighbourhood of $x_1$. We then let $x_2$ be an arbitrary point of $U'$, and continue this procedure until $x_{m/(4d^6)}$ is defined. 

Now assume that $W$ is a set of $\varepsilon n$ vertices. By the above, we can find $W' \subset W$ with at least $\varepsilon n/(4d^6)$ vertices so that the 3-neighbourhoods of vertices in $W'$ are all disjoint. As there are no more than $\sqrt{n}$ cycles of size bounded above by 3, assuming $n$ is large enough that $\sqrt{n} < \varepsilon n/(8d^6)$, we can further obtain $W''\subset W'$ with $|W''|> \varepsilon n/(8d^6)$ vertices so that $W''$ is well-separated. The desired conclusion then follows immediately from  Corollary \ref{c:key}.\end{proof}

%
%
%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%
\section{Subcritical regime}
\label{s:subcrit}
%We now turn to the proof of part (a) of Theorem~\ref{t:mainsup}. 
We start from the following consequence of well-known estimates for the subcritical contact process on trees.

\begin{prop}For any $\lambda < \lambda_1(\T)$, there exists $C > 0$ such that
$$\lim_{n \to \infty} \sup_{A \subset \T: |A| = n} P_{\T,\lambda}\Ll[\uptau^A_{\T} > C \log n\Rr] = 0.$$
\end{prop}
\begin{proof}
The proof will depend on the fact that, for any $\lambda < \lambda_1(\T)$, there exist $c_0, C_0 > 0$ such that
\begin{equation} \label{eq:cllig} 
\mathbb{E}_{\T,\lambda}\Ll[|\xi^o_t|\Rr] \leq C_0 e^{-c_0 t},\quad t \geq 0.
\end{equation}
This is proved as follows. For $\lambda < \lambda_1(\T)$, (\ref{eq:clligE}) and (\ref{eq:clligF}) give $\beta(\lambda) < \frac{1}{d}$. Together with (\ref{eq:clligC}), this shows that $\phi_\lambda(\rho) = 1$ for some $\rho > 1$. Then, using (\ref{eq:clligB}), we get $\phi_\lambda(1) < 1$, and then (\ref{eq:clligA}) gives the desired equation (\ref{eq:cllig}).

Let us now show how (\ref{eq:cllig}) completes the proof of our proposition. Noting that $|\xi^A_t| = \left|\cup_{x \in A}\; \xi^x_t\right| \leq \sum_{x \in A}\left|\xi^x_t\right|$, we have
$$P_{\T,\lambda}\Ll[|\xi^A_t| \neq \varnothing\Rr] \leq E_{\T,\lambda}\Ll[|\xi^A_t|\Rr] \leq C_0|A|e^{-c_0t}.$$
The proof is completed by taking $C = 2/c_0$.
\end{proof}

%We will merely show how this can be obtained from results that are stated and proved in \cite{lig99}.


Part (a) of Theorem \ref{t:mainsup} is a consequence of the above proposition and the following result: 
\begin{lem}
\label{lem:stdom}
For any finite graph $G = (V,E)$ with degree bounded by $d+1$, $A \subset V$ and $t > 0$,
$$P_{G,\lambda}\Ll[\uptau^A_G > t\Rr] \leq \sup_{B \subset \T: |B| = |A|} P_{\T,\lambda}\Ll[\uptau^B_{\T} > t\Rr].$$
\end{lem}
\begin{proof}
Since the contact process is unaffected by the presence of edges that start and end at the same vertex (loops), we assume that $G$ has none.

We will now recall the concept of universal covering of the graph $G$; we will construct from $G$ a new graph $\mathcal{T} = (\mathcal{V},\mathcal{E})$ with certain desirable properties. We start fixing a reference vertex $x \in V$. We say that a sequence $\gamma = (\vec{e}_1,\ldots,\vec{e}_n)$ of oriented edges of $\vec{E}$ is a \textit{non-backtracking path from $x$} if $v_0(\vec{e}_1) = x$ and, for $1 \leq i < n $, $v_1(\vec{e}_i) = v_0(\vec{e}_{i+1})$ and $u(\vec{e}_i) \neq u(\vec{e}_{i+1})$ (recall that, for an oriented edge $\vec{e}$, $v_0(\vec{e}),\;v_1(\vec{e})$ and $u(\vec{e})$ respectively denote the starting vertex, ending vertex and undirected edge associated to $\vec{e}$). Let $\mathcal{V}$ be the set of all non-backtracking paths from $x$, including an empty path which we denote by $o$. For any $\gamma,\gamma'\in \mathcal{V}$ with $\gamma = (\vec{e}_1,\ldots, \vec{e}_n)$ and $\gamma' = (\vec{e}_1, \ldots, \vec{e}_n, \vec{e}_{n+1})$, we connect $\gamma$ and $\gamma'$ by an edge; this defines the edge set $\mathcal{E}$ of $\mathcal{T}$. Finally, put $\psi(o) = x$ and, for $\gamma = (\vec{e}_1,\ldots,\vec{e}_n)$, put $\psi(\gamma) = v_1(\vec{e}_n)$, the ending vertex of the path $\gamma$. It is now easy to check that $\mathcal{T}$ and $\psi$ satisfy the properties:
\begin{itemize}
\item[(a)] $\mathcal{T}$ is a tree with degree bounded by $d+ 1$;
\item[(b)] for every $\gamma \in \mathcal{V}$, letting $x = \psi(\gamma) \in V$, we have
\begin{align*}\text{for all } y \in V,\quad
&\left|\{\text{edges of } E \text{ with extremities $x$ and $y$}\} \right| \\&= \left|\{\gamma' \in \mathcal{V}: \gamma \text{ and }\gamma' \text{ are neighbours in }\mathcal{T},\;\psi(\gamma') = y\} \right|.
\end{align*}
(in case $x$ is connected to each of its neighbours by a single edge, this just says that $\psi$ maps the neighbourhood of $\gamma$ bijectively to the neighbourhood of~$x$).
\end{itemize}


For $v \in V$, the set $\psi^{-1}(v)$ is called the \textit{fiber} of $v$. Define the set of configurations of $\{0,1\}^\mathcal{V}$ that have at most one particle per fiber,
$$\Omega_\mathcal{T} = \left\{\zeta \in \{0,1\}^\mathcal{V}: \sum_{\gamma \in \psi^{-1}(v)} \zeta(\gamma) \in \{0,1\} \text{ for all } v \in V\right\}.$$
Define the projection $\pi: \Omega_\mathcal{T} \to \{0,1\}^V$ by $[\pi(\zeta)](v) = \sum_{\gamma \in \psi^{-1}(v)} \zeta(\gamma)$ for $v \in V$. We abuse notation and, for a set $B \subset \mathcal{V}$, we write $B \in \Omega_\mathcal{T}$ if $\1_B \in \Omega_\mathcal{T}$.

Given $B \in \Omega_\mathcal{T}$, we define the \textit{constrained contact process on $\mathcal{T}$}, $(\zeta^B_t)_{t\geq 0}$, as follows. We set $\zeta^B_0 = B$ and let $\zeta$ evolve as a contact process on $\mathcal{T}$ with the restriction that we suppress every transition which would result in a configuration not in $\Omega_\mathcal{T}$, that is, births on vertices belonging to fibers already containing infected vertices. Formally, $(\zeta_t)$ has generator
$$\mathcal{L}f(\zeta) = \sum_{\gamma \in \mathcal{V}} \Ll[f(\zeta^{0 \to \gamma}) - f(\zeta)\Rr] + \lambda \cdot \sum_{\substack{\{\gamma, \gamma'\} \in \mathcal{E}:\\\zeta(\gamma)=1}}\Ll[ \1_{\{\zeta^{1 \to \gamma'} \in \Omega_\mathcal{T}\}}\cdot \Ll(f(\zeta^{1 \to \gamma'}) - f(\zeta) \Rr)\Rr],$$
where $\zeta^{i \to \gamma'}$ is the configuration obtained by modifying $\zeta$ so that $\gamma'$ is set to state $i$. Noting that $G$ is finite, and hence $\zeta$ has at most $|V|$ infected vertices at any given time, it is not hard to see that the above generator indeed gives rise to a Feller process on $\Omega_\mathcal{T}^{[0,\infty)}$. In fact, $\zeta$ can be constructed from a Harris system on $\mathcal{T}$, with the extra care of ignoring any transmission mark which would cause a fiber to become doubly occupied. Also, using property (b) of $\mathcal{T}$ and $\psi$ stated above, it is easy to show that $(\pi(\zeta^B_t))_{t \geq 0}$ has the same distribution as the contact process on $G$ started from $\pi(B)$.

Now, if we start from $A \subset V$, we can choose an arbitrary $B \in \Omega_\mathcal{T}$ such that $\pi(B) = A$ and conclude that $\uptau^A_G$ has the same distribution as $\inf\{t:\zeta^B_t = \varnothing\}$. By seeing $\mathcal{T}$ (and hence $B$) as a subset of $\T$, we have that $\zeta^B$ is stochastically dominated by the contact process on $\T$ started from $B$ infected, and hence $\inf\{t: \zeta^B_t = \varnothing\}$ is stochastically dominated by $\uptau^B_\T$. This completes the proof.
\end{proof}

Let $G$ be a graph and $x$ a vertex of $G$. Given the contact process on $G$ started from a single infection at $x$, $(\xi^x_t)_{t\geq 0}$, define
$$\upkappa^x_G = \sup\{\mathsf{dist}(x,y):y \in \xi^x_t \text{ for some } t \geq 0\}.$$

\begin{lem}
For any finite graph $G$ with degree bounded by $d+1$, any vertex $x$ of $G$ and $k > 0$,
$$\mathbb{P}\Ll[\upkappa^x_G > k\Rr] \leq \mathbb{P}\Ll[\upkappa^o_\T > k\Rr].$$
\end{lem}
\begin{proof}
Repeating the construction in the previous lemma, we note that, if $\psi(\gamma) = x$ and $\psi(\gamma') = y$, then $\mathsf{dist}_\mathcal{T}(\gamma, \gamma') \geq \mathsf{dist}_G(x,y)$, and we then see that $\upkappa^x_G$ is stochastically dominated by $\sup\{\mathsf{dist}_\mathcal{T}(\gamma,\gamma'): \gamma' \in \zeta^{\{\gamma\}}_t \text{ for some } t \geq 0 \}$. The latter is in turn stochastically dominated by $\kappa^o_\T$, completing the proof.
\end{proof}


\begin{proof}[Proof of Theorem \ref{t:univsub}.]
In order to show that the contact process on $G$ dies out, it suffices to show, for any vertex $x$, that $\P\Ll[\uptau^{x}_G < \infty\Rr] = 1.$ Denote by $B_G(x,r)$ the subgraph of $G$ induced by the set of vertices at graph distance at most $r$ from $x$. Then,
$$\P\Ll[\uptau^x_G < \infty\Rr] = \lim_{r \to \infty} \P\Ll[\upkappa^x_G \leq r\Rr] = \lim_{r \to \infty} \P\Ll[\upkappa^x_{B_G(x,r+1)} \leq r\Rr] \geq \lim_{r \to \infty} \P \Ll[ \upkappa^o_\T \leq r\Rr] = 1.$$


\end{proof}

\begin{thebibliography}{99}

\bibitem[Be]{benj} I.\ Benjamini. \textit{Coarse geometry and randomness -- École d'Été de Probabilités de Saint-Flour 2011}. Lecture Notes in Mathematics \textbf{2100}, Springer (2013). 

\bibitem[BNP11]{bnp} I.\ Benjamini, A.\ Nachmias, Y.\ Peres. \textit{Is the critical percolation probability local?} Probab. Theory Related Fields \textbf{149} (1-2), 261–269 (2011).

\bibitem[BS01]{bs} I.\ Benjamini, O.\ Schramm. \textit{Recurrence of distributional limits of finite planar graphs}. Electron. J. Probab. \textbf{6} (23), 13 pp.\ (2001).

\bibitem[CGOV84]{eulalia} M. Cassandro, A. Galves, E. Olivieri, M. Vares. \textit{Metastable behavior of stochastic dynamics: a pathwise approach.} J. Statist. Phys. \textbf{35} (5-6), 603-634 (1984).

\bibitem[CD09]{cd09} S. Chatterjee, R. Durrett. \textit{Contact processes on random graphs with power law degree distributions have critical value 0.} Ann. Probab. \textbf{37}, 2332 - 2356 (2009).

%\bibitem[CD13]{cd13} S. Chatterjee, R. Durrett. \textit{A first order phase transition in the threshold-$\theta \geq 2$ contact process on random $r$-regular graphs and $r$-trees.} Stochastic Processes and Their Applications 123, no. 2, 561-578 (2013).


\bibitem[Ch94]{chencp} J.W. Chen. \textit{The contact process on a finite system in higher dimensions}. Chinese J. Contemp. Math. 15, 13-20 (1994).

\bibitem[CMMV13]{cmmv13} M. Cranston, T. Mountford, J.C. Mourrat, D. Valesin, \textit{The contact process on finite trees revisited}. ALEA Vol XI, 385–408 (2014).

%\bibitem[Du1]{durprob} R.\ Durrett, \textit{Probability: theory and examples} (4th ed.). Cambridge university press (2010).

\bibitem[DL88]{durliu} R.\ Durrett, X.\ Liu. \textit{The contact process on a finite set}. Ann. Probab. \textbf{16}, 1158-1173 (1988).

\bibitem[DS88]{dursc} R.\ Durrett, R.H.\ Schonmann. \textit{The contact process on a finite set II}. {Ann. Probab.} \textbf{16}, 1570-1583 (1988).

%\bibitem[DST89]{dursctan} R.\ Durrett, R.H.\ Schonmann, N.\ Tanaka. \textit{The contact process on a finite set III: the critical case}. Ann. Probab. \textbf{17}, 1303-1321 (1989).

%\bibitem[Li85]{lig85} T.\ Liggett, \emph{Interacting particle systems}. Grundlehren der mathematischen Wissenschaften \textbf{276}, Springer (1985).

%\bibitem[Li96]{lig96} T.\ Liggett, \emph{Multiple transition points for the contact process on the binary tree}. Ann. Probab. \textbf{24}, 1675-1710 (1996).

\bibitem[Li99]{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. \emph{Domination by product measures}. Ann. Probab. \textbf{25}, 71-95 (1997).

\bibitem[MT13]{mt} S.\ Martineau, V.\ Tassion. \textit{Locality of percolation for abelian Cayley graphs}. Preprint, arXiv:1312.1946 (2013).

\bibitem[MS15]{mensin} L.\ M\'enard, A.\ Singh. \textit{Percolation by cumulative merging and phase transition for the contact process on random graphs}. Preprint, arXiv:1502.06982 (2015).

\bibitem[Mo93]{tommeta} T.\ Mountford. \textit{A metastable result for the finite multidimensional contact process.} Canad. Math. Bull. \textbf{36} (2), 216-226 (1993).

\bibitem[Mo99]{tomexp} T.\ Mountford. \textit{Existence of a constant for finite system extinction.} J. Statist. Phys. \textbf{96} (5-6), 1331-1341 (1999).

\bibitem[MMVY12]{mmvy} T. Mountford, J.C. Mourrat, D. Valesin, Q. Yao. \textit{Exponential extinction time of the contact process on finite graphs}.  Preprint, arXiv:1203.2972 (2012).

\bibitem[MVY13]{mvy} T. Mountford, D. Valesin, Q. Yao. \textit{Metastable densities for the contact process on power law random graphs}. Electronic Journal of Probability, Vol 18 1-36 (2013).

%\bibitem[Pe92]{pemantle} R. Pemantle. \textit{The contact process on trees}. Ann. Probab. \textbf{20}, 2089-2116 (1992).

\bibitem[vdH]{vdH} vd Hofstad, R. \textit{Random graphs and complex networks}. Available at http://www.win.tue.nl/$\sim$rhofstad/

\bibitem[SS98]{ss98} M. Salzano, R. Schonmann. \textit{A new proof that for the contact process on homogeneous trees, local survival implies complete convergence}. Ann. Probab. \textbf{26}, 1251-1258 (1998).

\bibitem[Sc85]{schonmeta} R.\ Schonmann. \textit{Metastability for the contact process}. J. Statist. Phys. \textbf{41} (3-4), 445-464 (1985).

\bibitem[SXZ14]{sxz} H.\ Song, K.-N.\ Xiang, S.-C.-H.\ Zhu. \textit{Locality of percolation critical probabilities: uniformly nonamenable case}. Preprint, arXiv:1410.2453 (2014).


\bibitem[St01]{St} A.\ Stacey. \textit{The contact process on finite homogeneous trees}.Probab. Theory Related Fields. \textbf{121} (4), 551-576 (2001).


\end{thebibliography}


\end{document}

