Super-exponential extinction time of the contact process on random geometric graphs
Van Hao Can
In this paper, we prove lower and upper bounds for the extinction time of the contact process on random geometric graphs with connecting radius tending to infinity. We obtain that for any infection rate $\lambda >0$, the contact process on these graphs survives a time super-exponential in the number of vertices.
1506.02373.tex
\documentclass[12pt]{amsart}

\usepackage{latexsym,amsfonts,amsmath,amssymb,amsthm,url,graphics,psfrag,amscd,stmaryrd}
\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphics}
\usepackage{graphicx}
%\usepackage[active]{srcltx}
\usepackage{color}
%\usepackage{epic,eepic}

\usepackage{pstricks-add}

\paperheight=29.7cm
 \paperwidth=21cm
 \setlength\textwidth{16cm}
\hoffset=-1in
  \setlength\marginparsep{0.5cm}
 \setlength\marginparwidth{0.5cm}
  \setlength\marginparpush{0.5cm}
  \setlength\evensidemargin{2.5cm}
 \setlength\oddsidemargin{2.5cm}
  \setlength\topmargin{2.4cm}
  \setlength\headheight{0.5cm}
  \setlength\headsep{0.5cm}
  \voffset=-1in
\setlength\textheight{23.5cm}


\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\pp}{\mathbb{P}}
\newcommand{\kD}{\mathcal{D}}
\newcommand{\kA}{\mathcal{A}}
\newcommand{\kB}{\mathcal{B}}
\newcommand{\kC}{\mathcal{C}}
\newcommand{\kR}{\mathcal{R}}
\newcommand{\kO}{\mathcal{O}}
\newcommand{\kP}{\mathcal{P}}
\newcommand{\kQ}{\mathcal{Q}}
\newcommand{\kF}{\mathcal{F}}
\newcommand{\kG}{\mathcal{G}}
\newcommand{\kK}{\mathcal{K}}
\newcommand{\kM}{\mathcal{M}}
\newcommand{\kE}{\mathcal{E}}
\newcommand{\kH}{\mathcal{H}}
\newcommand{\kI}{\mathcal{I}}
\newcommand{\kJ}{\mathcal{J}}
\newcommand{\kS}{\mathcal{S}}
\newcommand{\kN}{\mathcal{N}}
\newcommand{\kX}{\mathcal{X}}
\newcommand{\kL}{\mathcal{L}}
\newcommand{\kV}{\mathcal{V}}
\newcommand{\kT}{\mathcal{T}}
\newcommand{\ka}{\mathfrak{a}}
\newcommand{\kh}{\mathfrak{h}}
\newcommand{\pn}{\mathbb{P} }
\newcommand{\pln}{\mathbb{P}_n ^{\lambda}}
\newcommand{\en}{\mathbb{E} }
\newcommand{\eln}{\mathbb{E}_n ^{\lambda}}
\newcommand{\va}{\textrm{Var}}
\newcommand{\cov}{\textrm{Cov}}
\newcommand{\bin}{\mathcal{B}}
\newcommand{\poi}{\textrm{Poi}}
\newcommand{\pms}{\mathbb{P}^{(S)}}
\newcommand{\pdp}{\mathbb{P}_{p}}
\newcommand{\lmd}{\llbracket 1, \ell \rrbracket ^d}
\newcommand{\nmd}{\llbracket 0, n \rrbracket ^d}
\newcommand{\tpl}{\tilde{\phi}(\lambda)}
\newcommand{\dtv}{\textrm{dist}_{\textrm{TV}}}
\def\l{\ell}
\newcommand{\lin}{\left[\kern-0.15em\left[}
\newcommand{\rin} {\right]\kern-0.15em\right]}
\newcommand{\linf}{[\kern-0.15em [}
\newcommand{\rinf} {]\kern-0.15em ]}
\newcommand{\ilin}{\left]\kern-0.15em\left]}
\newcommand{\irin} {\right[\kern-0.15em\right[}



\newtheorem{lem}{Lemma}[section]
\newtheorem{rema}[lem]{Remark}
\newtheorem{prop}[lem]{Proposition}
\newtheorem{theo}[lem]{Theorem}
\newtheorem{fact}[lem]{Fact}
\newtheorem{cor}[lem]{Corollary}
\newtheorem {assum}[lem] {Assumption}
\newtheorem {defin}[lem] {Definition}
\newtheorem {rem}[lem] {Remark}
\newtheorem {nota}[lem] {Notation}
\newtheorem*{ack}{Acknowledgments}
\title[Contact process on  random geometric graphs ]
       {\bf Super-exponential extinction time of  the contact process on  random geometric graphs }
\author{Van Hao Can}
\address{Aix Marseille Universit\'e, CNRS, Centrale Marseille, I2M, UMR 7373, 13453 Marseille, France}

\email{cvhao89@gmail.com}
       
       
       
 \keywords{Contact process; extinction time ;  random geometric graph.
} 
\subjclass[2010]{82C22; 60K35; 05C80.}
      

\begin{document}
\maketitle
\begin{abstract}
In this paper, we prove  lower and upper bounds for the extinction time of the contact process on  random geometric graphs with connecting radius  tending to infinity. We obtain that for any infection rate $\lambda >0$, the  contact process on these graphs survives a time super-exponential in the number of vertices.
\end{abstract}

\section{Introduction}
We will study the contact process on  random geometric graphs (RGGs) in $d \geq 2$ dimensions  with intensity $g$ and  connecting radius  $R$, denoted by $G(n,R,g)$.

\vspace{0.2 cm}
 A RGG  is constructed as follows.  The vertex set is composed by the atoms of  a Poisson point process with intensity $g$ on $[ 0, \sqrt[d]{n}]^d$.  Then for any two vertices  $v  \neq w $, we draw an edge between them  if $\|v-w \| \leq R $, where $\|\cdot\|$ denotes the Euclidean norm in $\mathbb{R}^d$. We will assume in all this paper  that there are positive constants $b$ and $B$, such that
\begin{align} \label{cdg}
0< b  \leq g(x) \leq B < + \infty  \quad \textrm{ for all } x.
\end{align}

\vspace{0.2 cm}
 The contact process is one of the most studied interacting particle systems and is also often interpreted as a model to describe the spread of a virus in a network (see  for instance \cite{L}). Mathematically, it can be defined as follows: given a locally finite graph $G=(V,E)$ and $\lambda >0,$ the contact process on $G$ with infection rate $\lambda$ is a pure jump Markov process $(\xi_t)_{t\geq 0}$ on $\{0,1\}^V.$ Vertices of $V$ (also called sites) are regarded as individuals which are either infected (state $1$) or healthy (state $0$). By considering $\xi_t$ as a subset of $V$ via $\xi_t \equiv \{v: \xi_t(v)=1\},$ the transition rates are given by
\begin{align*}
\xi_t \rightarrow \xi_t \setminus \{v\} & \textrm{ for $v \in \xi_t$ at rate $1,$ and } \\
\xi_t \rightarrow \xi_t \cup \{v\} & \textrm{ for $v \not \in \xi_t$ at rate }  \lambda |\{w \in \xi_t : \{v,w\} \in E \}|,
\end{align*}
where $|A|$ is the cardinality of a set $A$. 


Originally the contact process was studied on integer lattices or homogeneous trees. More recently, probabilists started  investigating this process on some families of random networks  like  configuration models, or  preferential attachment graphs, see for instance \cite{ BBCS, C,CD, CS, MMVY, MVY}.

\vspace{0.2 cm}
Random geometric graphs have been extensively studied for a long time by many authors, see in particular Penrose's book \cite{P}. Recently, these graphs have also been considered as models of wireless networks (see e.g. \cite{GK}). Therefore,  there has been interest in  processes occurring on it, including the contact process in both theoretical and practical approaches, see for  example  \cite{FSS,G,PJ}.

In this paper, we are in particular interested in the extinction time of the contact process,
\begin{align*}
\tau_n = \inf \{t: \xi^{1}_t = \varnothing\},
\end{align*}
where $(\xi^1_t)$ is the contact process on $G(n,R,g)$ starting with all nodes infected. 

We observe that w.h.p. the number of vertices in this graph is between $b(1-o(1))n$ and $B(1+o(1))n$. On the other hand, the contact process on finite graphs dies out a.s. i.e.  $\tau_n < \infty $ a.s. Now,  it is interesting to determine the order of  magnitude of $\tau_n$. For  sparse graphs, i.e.  graphs in which the number of edges is of order the number of vertices, it is shown that the extinction time is at most exponential in the number of vertices (see Lemma \ref{bgg}). On the other hand, we will show in Section 2.1 that the extinction time of the contact process on a complete graph is super-exponential in the number of vertices.  In random geometric graphs with large connecting radius,  the number of edges is much larger than the number of vertices.  Moreover, the graph locally looks like a complete graph (all vertices in a ball of radius $R/2$ form a clique).  Hence, we can expect that $\log \tau_n$ is super-linear in $n$  as in  the case of the complete graph. (Note that there are graphs which are not sparse but for which $\log \tau_n = \kO(n)$, for example the configuration model with infinite mean degree, see Theorem 1.2 (ii) in \cite{CS}). 

In \cite{G}, more precisely in Theorem 1.2, the author considers the contact process on an equivalent model of $G(n,R,g)$ in $2$ dimensions. Translating to our model, he proves that if $R \rightarrow \infty$ and $R^2=\kO(\log n)$, then there exist  positive constants $c=c(\lambda)$ and $C=C(\lambda)$, such that w.h.p. $C n \log n \geq \log \tau_n \geq c n R^2/ \log n$. 

\vspace{0,2cm}
In our main result, we will  prove that in all dimensions larger than or equal to $2$ if $R \rightarrow \infty$, then w.h.p. $\log \tau_n \asymp n \log (\lambda R^d)$. 
 \begin{theo} \label{trg} 
Let $d\geq 2$ and  $\tau_n$ be the extinction time of the contact process on the graph $G(n,R,g)$ with $g$ satisfying \eqref{cdg} starting from full occupancy. There exist positive constants $c$, $C$ and $K$ depending only on $d,b$ and $B$, such that the following statements hold.
\begin{itemize}
\item[$(i)$] If  $R^d \geq K / ( \lambda \wedge 1) $, then 
 $$\pn(\tau_n \geq \exp(c n \log ( \lambda R^d) )=1 -o(1)$$
 and 
 \[ \frac{\tau_n}{\en(\tau_n)}\ \mathop{\longrightarrow}^{(\mathcal L)}_{n\to \infty}  \  \kE(1), \]
with $\kE(1)$ an exponential random variable with mean one.
  \item[$(ii)$] For all $R>0$
 $$\pn( \tau_n \leq \exp(C n \log ( \lambda R^d)) )=1 -o(1).$$
\end{itemize}   
 \end{theo}
Part (i) implies that when  $R$ tends to infinity, the contact process survives a time super-exponential in $n$ regardless the value of $\lambda$. We usually say that in this case the critical value of the infection rate  is zero. On the other hand, recently in \cite{MS}  the authors show that when $R$ is {\it fixed}, there is a non-trivial phase transition of the contact process on  {\it infinite} random geometric graphs (i.e. the vertices  are  atoms of a Poisson point process on the whole space $\mathbb{R}^d$). More precisely, they prove that there exists a constant $\lambda_c >0$, such that if $\lambda < \lambda_c$, the contact process dies out a.s., whereas if $\lambda > \lambda_c$, it survives forever with positive probability. 

There is a conjecture saying that the contact process on  a sequence of finite graphs, say $(G_n)$, converging locally to some limiting graph, say $G$, exhibits a phase transition at the same critical value of infection rate as on the limit $G$: in the sub-critical regime, the contact process on $G$ dies out a.s. (resp. $\tau_n$-the extinction time of the process on $G_n$ is of order $\log (|G_n|)$), whereas in the super-critical regime, the contact process survives forever with positive probability (resp. $\log \tau_n $ is of order $|G_n|$). This conjecture has been verified in some  examples, see for instance \cite{C,CD,CMMV,MMVY,MV}.  

Hence, for the contact process on   $G(n,R,g)$ with $R$ fixed,  it is natural  to guess that 
$$ \tau_n \asymp \log n \textrm{ when }  \lambda < \lambda_c \,\, \textrm{ and } \,\,\log \tau_n \asymp n \textrm{ when } \lambda>  \lambda_c,  $$
with $\lambda_c$  the critical value of the contact process on the infinite random geometric graphs as in \cite{MS}.

\vspace{0.2cm} 
We now make some comments on the proof of Theorem \ref{trg}. To prove (i), we will find in $G(n,R,g)$ a subgraph composed by many adjacent complete graphs, see Lemma \ref{p2}. Then we can compare the contact process with a super-critical oriented percolation. The proof of (ii) follows from a quite general argument: the extinction of the contact process on a graph $G=(V,E)$ is at most $\exp(C|V| \log (|E|/|V|))$, for some positive constant $C$. 

\vspace{0.2 cm}
The paper is organized as follows. In Section 2, we prove some preliminary results on the contact process on  complete graphs, the oriented percolation in two dimensions and  long paths in a site percolation. The main theorem is proved in Section 3. In the last section, we study some extensions: the case $d=1$ and the equivalent model  considered in \cite{G}. 

\vspace{0.2cm}
We now fix some notation. We call size of a graph $G$ the cardinality of its set of vertices and we denote it by $|G|$.  For $\mu >0$, we denote by $\poi(\mu)$  a Poisson random variable with mean $\mu$ and $\kE(\mu)$ an exponential random variable with mean $1/\mu$. If $f $ and $g$ are two real functions, we write $f= \mathcal{O}(g)$ if there exists a constant $C>0,$ such that $f(x) \leq C g(x)$ for all $x ;$  $f \asymp g $ if $f= \mathcal{O}(g)$ and $g= \mathcal{O}(f);$  $f=o(g)$ if $g(x)/f(x) \rightarrow 0$ as $x \rightarrow \infty$. 
The term  w.h.p. means with probability tending to $1$.  
\section{Preliminairies}
\subsection{Contact process on  complete graphs} We denote by $K_m$ the complete graph of size   $m$. Similarly to the results for the contact process on star graphs in \cite{CD,MVY}, we prove the following.
\begin{lem} \label{l5} Assume that $\lambda \leq 1$ and $m \lambda \geq 640$. Then  the following assertions hold.
\begin{itemize}
\item[(i)] Let $(\xi_t)$ be the contact process on  $K_m$. Then
$$\pp \left(\inf_{T_m/2 \leq t \leq T_m}|\xi_t | \geq m/4 \mid |\xi_0| \geq m/4 \right) \geq 1-2T_m^{-1},$$
with $T_m= \exp(m \log(\lambda m)/16)$.
\item[(ii)] Let $K^1_m$ and $K^2_m$ be two disjoint complete graphs of size $m$, and $K_{m,m}$  be the graph formed by adding an edge between these two graphs. Let $(\xi_t)$ be the contact process on  $K_{m,m}$. Then
$$\pp(|\xi_{T_m} \cap K^2_m| \geq m/4 \mid |\xi_0 \cap K^1_m| \geq m/4) \geq 1-5T_m^{-1}.$$
\end{itemize}
\end{lem}
\begin{proof} Part (i)  follows from the following claims 
 \begin{align}
 \pp \left( \inf\limits_{0 \leq t\leq T_m}|\xi_t| \geq  m/4 \mid |\xi_0| \geq  m/2 \right) & \geq 1 - T_m^{-1}, \label{lg1}\\
   \pp \left( \exists \,t \leq T_m/2 :|\xi_t| \geq  m/2 \mid |\xi_0| \geq m/4 \right) & \geq 1 - T_m^{-1}. \label{lg2}
    \end{align}
 To prove \eqref{lg1}, we note that  $|\xi_t| $  increases by $1$ with rate  $\lambda  |\xi_t| (m -|\xi_t|)$ and decreases by $1$ with rate $|\xi_t|$. Therefore, when   $|\xi_t|\in ( m/4, 3m/4)$, the increasing rate is larger than $3\lambda m^2/16$ and the decreasing rate is less than $3m/4$. 
 
 Thus during the time that  $|\xi_t|\in ( m/4, 3m/4)$, it stochastically dominates a continuous time random walk $(U_t)$ satisfying  $U_0 = m/2$ and
\begin{align*}
U_t \rightarrow U_t -1 & \quad \textrm{ at rate } 3m/4, \\
U_t \rightarrow U_t +1 & \quad \textrm{ at rate } 3\lambda m^2/16.
\end{align*}
To  understand $(U_t)$, let us consider its skeleton, a   random walk $X_r$ satisfying  $X_0 =m/2$ and for $r \geq 0$
\begin{align*}
X_{r+1} = X_r -1 & \quad \textrm{ with probability } \frac{4}{\lambda m +4 }, \\
X_{r+1} = X_r +1 & \quad \textrm{ with probability } \frac{\lambda m}{\lambda m +4 }.
\end{align*}
 Then $\theta^{X_r}$ is a martingale, where 
$$\theta= \frac{4 }{ \lambda m}.$$
Let $q$ be the probability that $X_r$ goes below $ m/4 $ before hitting $3m/4$. It follows from the optional stopping theorem that 
$$q \theta^{ m/4 }+(1-q) \theta^{3 m/4} \leq \theta^{ m/ 2}. $$
Therefore
\begin{align} \label{eqq}
q \leq \theta^{m/4} = (4/ \lambda m)^{m/4} \leq  T_m^{-3}/(2m^2),
\end{align} 
since $\lambda m \geq 640$.

Hence,  the random walk $(X_r)$ (and thus the continuous time random walk $(U_t)$) makes  at least $[m^2 T_m] $ upcrossings between  $ m/2$ and $3 m/ 4$ before hitting $ m/4 $ with probability larger than 
\begin{align} \label{eb1}
1 - [m^2 T_m]T_m^{-3}/(2m^2) \geq 1- T_m^{-1}/2.
\end{align} 
The law of the waiting time between two upcrossings of $(U_t)$ stochastically dominates  $\mathcal{E}(L)$,  with  $L=  3\lambda m^2/16 + 3m/4$, the waiting time between two stages of $(U_t)$. 

Suppose that $(U_t)$ makes  more than [$m^2T_m] $ consecutive upcrossings. Then the time that $(U_t)$ stays above $m/4$  stochastically dominates  $S$, the sum of $[m^2 T_m]$ i.i.d. exponential random variables  with mean $1/L$. By applying Chebyshev's inequality, we get 
\begin{align} \label{eb2}
\mathbb{P}(S < [m^2T_m]/2L) \leq 4/([m^2 T_m]) \leq T_m^{-1}/2.
\end{align}
Since $L \leq m^2/2$ and $(|\xi_t|)$ stochastically dominates $(U_t)$, we deduce \eqref{lg1} from \eqref{eb1} and \eqref{eb2}.

We now  prove \eqref{lg2}. Assume that $|\xi_0| \geq m/4$. Then during the time that $|\xi_t|$ is between $ m/8  $ and $  m/2$, it stochastically dominates a continuous time random walk $Y_t$ satisfying   $Y_0=  m/4$ and
\begin{align*}
Y_ t & \rightarrow Y_t+1 \textrm{ at rate } e_1 = 7 \lambda m^2/64 , \\
Y_ t & \rightarrow Y_t-1 \textrm{ at rate } e_2 = m/2.
\end{align*}
Let us define $$\sigma_Y = \inf \{t: Y_t \geq  m/2\} \qquad \textrm{and} \qquad \tilde{\sigma}_Y = \inf \{t: Y_t \leq  m/8\}. $$
Then similarly to \eqref{eqq}, we have
\begin{align} \label{s1}
  \mathbb{P}(\tilde{\sigma}_Y < \sigma_Y)  \leq (32/(7 \lambda m))^{m/8}\leq T_m^{-1}/3.
\end{align} 
Since $Y_t - (e_1 -e_2 )t$ is a martingale, it follows from the stopping time theorem that
$$m/4 = \mathbb{E}(Y_{\sigma_Y \wedge t}) - (e_1-e_2 ) \mathbb{E}(\sigma_Y \wedge t)  \leq  m/2 - (e_1 -e_2 ) \mathbb{E}(\sigma_Y \wedge t) .$$
Therefore using $m \lambda \geq 640$, we get
$$ \E(\sigma_Y \wedge t)  \leq  \frac{m}{4(e_1- e_2)} \leq 1/6.
$$
Letting $t$ go to infinity, we obtain
\begin{align*} 
\E(\sigma_Y) \leq 1/6.
\end{align*} 
Thus using Markov inequality, we have
\begin{align} \label{s2}
\pp(\sigma_Y > T_m/2) \leq 2\E(\sigma_Y)/T_m \leq T_m^{-1}/3.
\end{align} 
It follows from  \eqref{s1} and \eqref{s2} that 
\begin{align*}
  \pp \left(\sigma_Y \leq \min \{ \tilde{\sigma}_Y, T_m/2 \} \right) \geq 1 -  T_m^{-1},
    \end{align*}
which proves \eqref{lg2} as $(|\xi_t|)$ stochastically dominates $(Y_t)$.

For (ii), let $v$ and $w$ be two vertices in $K^1_m$ and $K^2_m$ respectively, such that there in an edge between $u$ and $v$. Let $(\xi'_t)$ (resp. $(\xi''_t)$) be the contact process on $K^1_m$ (resp. $K^2_m$). By (i), we have
\begin{align} \label{cc1}
\pp(\xi'_{T_m} \neq \varnothing \mid |\xi'_0| \geq m/4) \geq 1- 2 T_m^{-1}. 
\end{align} 
We now claim that 
\begin{align} \label{cl3}
\pp(\exists \, t \leq m/2 : |\xi''_t| \geq m/4  \mid \xi'_{m/2} \neq \varnothing ) \geq e^{-m/4}/m.
\end{align}
To prove \eqref{cl3}, it amounts to show that 
\begin{align} \label{cl1}
\pp(\exists \, t \leq m/4 : |\xi''_t| \geq m/4  \mid |\xi''_0|=1) \geq e^{-m/4},
\end{align}
and 
\begin{align} \label{cl2}
\pp(\textrm{$w$ get infected before } m/4 \mid \xi'_{m/4} \neq \varnothing) \geq 1/m.
\end{align}
For \eqref{cl1}, observe that  when $|\xi''_t| \leq m/4$,  it increases by $1$ in the next stage with probability  
$$\frac{\lambda |\xi''_t|(m-|\xi''_t|)}{\lambda |\xi''_t|(m-|\xi''_t|)+ |\xi''_t| } \geq \frac{3 \lambda m}{4 \lambda m+4} > 0.8 ,$$
as $\lambda m \geq 640$. Moreover,  the waiting time to the next stage is an exponential random variable with mean less than $1$. Therefore, the probability that in all the $[m/4]+1$ first stages, $|\xi''_t|$ increases and the waiting time  is less than $1$, is   larger than 
$$\left( 0.8(1- e^{-1}) \right)^{[m/4]+1} \geq e^{-m/4},$$
which implies \eqref{cl1}.

For \eqref{cl2}, we note that 
\begin{align*}
\{\xi'_{m/4}\neq \varnothing\} \subset \bigcap_{i=1}^{[m/8]} \kE_i,
\end{align*}
 where
\begin{align*}
\kE_i=\{\exists\, v_i \in K^1_m: \xi'_{2i}(v_i)=1\}.
\end{align*}
We define
\begin{align*}
\kI_i = & \{\textrm{there is no recovery at $v_i$ in $[2i,2i+1]$ and there is an infection spread from $v_i$ to $v$ }\\
& \textrm{ in $[2i,2i+1]$, there is no recovery at $v$ in $[2i,2i+2]$ and there is an infection spread } \\ & \textrm{ from $v$ to $w$ in} [2i+1,2i+2] \}.
\end{align*}
If $v_i \equiv v$, we only consider the recovery in $v$ and the infection spread from $v$ to $w$. 
We see that if one of $(\kI_i)$ occurs then $w$ gets infected before $m/4$ and for any $i=0, \ldots, [m/8]$
\begin{align} \label{kii}
\pp(\kI_i \mid \cap_{j=1}^{i}\kE_j) \geq e^{-3}(1-e^{-\lambda})^2 \geq \lambda^2/(4e^3),
\end{align}
as $\lambda \leq 1$. Therefore, by using induction we have 
\begin{align} \label{cpp}
&\pp \left(\textrm{$w$ is not  infected before $m/4$} \mid \xi'_{m/4}\neq \varnothing   \right) \notag \\
& \leq \pp \left( \left( \bigcup_{i=1}^{[m/8]} \kI_i \right)^c\cap \left(\bigcap_{i=1}^{[m/8]} \kE_i\right)\right)\notag\\
 &\leq (1-\lambda^2/(4e^3))^{[m/8]} \notag \\ 
 &\leq 1/m,
\end{align}
since $\lambda m \geq 640$. Thus \eqref{cl2} follows. 

We now prove (ii) by using \eqref{cl3}. Suppose that $\xi'_{T_m} \neq \varnothing$. We divide the time interval $[0,T_m/2]$ into $[T_m/m]$ small intervals of length $m/2$. Then  \eqref{cl3} implies that in each interval with probability larger than $e^{-m/4}/m$, there is a time $s$, such that that $|\xi''_s| \geq m/4$. Hence, similarly to \eqref{cpp} we have  
\begin{align} \label{cc2}
\pp( \exists \, s \leq T_m/2 : |\xi''_s| \geq m/4 \mid \xi'_{T_m/2} \neq \varnothing ) \geq 1- (1-e^{-m/4}/m)^{[T_m/m]} \geq 1-  T_m^{-1}.
\end{align}
Suppose that $|\xi''_s| \geq m/4$ with $s \leq T_m/2$. Then  (i) implies that  $|\xi'_{T_m}| \geq m/4$ with probability larger than $1-2T_m^{-1}$.  Combining this with \eqref{cc1} and \eqref{cc2}, we get (ii).
\end{proof}
\subsection{Oriented percolation on finite sets} 
For any positive integer $\ell$, we consider an oriented percolation process on $[0,  \ell] $ with parameter $q$ defined  as follows. Let 
$$\Gamma = \{(i,k)  \in [ 0,  \ell] \times \mathbb{N} : i+k \textrm{ is even}\}.$$
We then independently draw an arrow from $(i,k)$ to $(j, k+1)$ with probability $q$, where $j=i-1$ or $j=i+1$. Given the initial configuration $A \subset [0, \ell]$, the oriented percolation  $(\eta_t)_{t \geq 0}$  is defined by
  $$\eta_t^A = \{i \in [0, \ell]  : \exists \, j \in A \textrm{ s.t.} \, \,  (j,0) \leftrightarrow (i,t) \} \textrm{ for } t \in \mathbb{N},$$
  where the notation $(j,0) \leftrightarrow (i,t)$ means that there is an oriented path from $(j,0)$ to $(i,t)$. If $A=\{x\}$, we simply write $(\eta_t^x)$. We call $(\eta_t)$ a Bernoulli oriented percolation with parameter $q$.
  
The oriented percolation on $\mathbb{Z} $, denoted  by $(\bar{\eta}_t)$, was investigated  by Durrett in \cite{D}. Using his results and techniques, we will prove the following.
   \begin{lem} \label{lc}
Let $(\eta_t)$ be the oriented percolation on $[ 0, \ell]$ with  parameter $q$.  Then there exist  positive constants $\varepsilon$ and  $c$ independent of $q$ and $\ell$, such that if $q \geq 1- \varepsilon$ then the following statements hold.
\begin{itemize}
\item[(i)] For any $\ell$, 
\begin{align*}
\pp(\sigma_{\ell} \leq 2\ell) \geq c,
\end{align*} 
where 
\begin{align*}
\sigma_{\ell} = \inf\{t: \eta^{0}_t (\ell)=1\}.
\end{align*}
\item[(ii)] For any $\ell$,
$$\pn ( \eta^{{\bf 1}}_{t_{\ell}} \neq \varnothing ) \geq 1 - 1/ t_{\ell},$$
  where 
  $t_{\ell}= \big[ (1-q)^{-c\ell} \big]$ and $(\eta^{{\bf 1}}_t)$ is the oriented percolation starting with $\eta_0^{{\bf 1}}= [0, \ell]$.\\
  \item[(iii)] There exist a positive constant $\beta \in (0,1)$ and an integer  $s_{\ell}\in [\exp( c\ell), 2\exp(c \ell)] $, such that
$$\pn ( |\eta^{{\bf 1}}_{s_{\ell}} \cap [(1-\beta) \ell/2,(1 + \beta) \ell/2 ]| \geq 3\beta \ell/4 ) \geq 1 - \exp(-c \ell).$$
\end{itemize}
  \end{lem}
\begin{proof}
Part (i) is Theorem B.24 (a) in \cite{L} and (ii) can be proved using a contour argument as in Section 10 in \cite{D}.

We now prove (iii). Let  $(\bar{\eta}_t)$ be the oriented percolation on $\mathbb{Z}$. Then   
\begin{align*}
\alpha= \pp(\bar{\eta_t}^{0} \neq \varnothing\, \forall \, t) \rightarrow 1 \quad \textrm{ as } \quad q \rightarrow 1.  
\end{align*}
Hence we can assume that $\alpha >3/4$. Now we define 
\begin{align*}
\ell_1= [(2- \alpha )\ell/4], \quad \quad \ell_2 = [(2+ \alpha )\ell/4] \quad \textrm{ and } \quad \ell_3 =[\ell/4].
\end{align*}
Then for all $t \leq \ell_3$,
\begin{align*}
\bar{\eta}^{[\ell_1, \ell_2]}_{t} \subset [\ell_1 - t, \ell_2+ t] \subset [\ell_1 - \ell_3, \ell_2+ \ell_3] \subset [0, \ell].
\end{align*}
Therefore,
\begin{align*}
\left(\bar{\eta}^{[\ell_1, \ell_2]}_{t} \right)_{0 \leq t \leq \ell_3} \equiv  \left(\eta^{[\ell_1, \ell_2]}_{t} \right)_{0 \leq t \leq \ell_3}.
\end{align*}
Hence, to simplify notation, we use $(\eta_t)$ for the both processes in the interval $[0, \ell_3]$. To prove (iii), our goal is to show that there exists a positive constant $c$, such that for any $A \subset[\ell_1, \ell_2]$ and $|A| \geq 3 \alpha \ell/8$, 
\begin{align} \label{eal}
\pp(|\eta^A_{\ell_3}| \geq 3 \alpha\ell/8) \geq 1 - \exp(-c \ell).
\end{align}
Then repeatedly applying \eqref{eal} implies (iii) with $\beta = \alpha/2$. To prove \eqref{eal}, it suffices to show that there exists a positive constant $c$, such that
\begin{align}
\pp(|\eta^x_{\ell_3}| \geq 3 \alpha \ell/8 \mid \eta^x_{\ell_3}  \neq \varnothing )& \geq 1 -\exp(-c \ell) \textrm{ for all } x \in [\ell_1, \ell_2], \label{eal1}\\
\pp(\eta^A_{\ell_3}  \neq \varnothing ) & \geq 1 -\exp(-c \ell) \textrm{ for all } A \subset [\ell_1, \ell_2] \textrm{ with } |A| \geq 3\alpha \ell/8. \label{eal2}
\end{align}
To prove \eqref{eal1}, we define for any $A \subset \mathbb{Z}$ and $t \geq 0$
\begin{align*}
r^A_t: = \sup \{x: \exists y \in A, (y,0) \leftrightarrow (x,t)\} \\
l^A_t: = \inf \{x: \exists y \in A, (y,0) \leftrightarrow (x,t)\}.
\end{align*}
Then \eqref{eal1} is a consequence of the following. 
\begin{itemize}
\item[$\bullet$] it is not hard to see that if $[\ell_1, \ell_2] \subset [l^x_{\ell_3}, r^x_{\ell_3}]$, then
$$\eta^{{\bf 1}}_{\ell_3} \cap [\ell_1, \ell_2] \equiv \eta^{x}_{\ell_3} \cap [\ell_1, \ell_2], $$
\item[$\bullet$] 
$\pp(|\eta^{{\bf 1}}_{\ell_3} \cap [\ell_1, \ell_2]| \geq 3(\ell_2- \ell_1)/4) \geq 1 - \exp(-c \ell)$, as $3/4 <\alpha$.  \\
\item[$\bullet$]
$\pp \left(  [l^x_{\ell_3}, r^x_{\ell_3}] \supset [\ell_1, \ell_2]  \mid \eta^x_{\ell_3} \neq \varnothing \right) \geq 1 - \exp(-c \ell).$
\end{itemize}
The second claim is a consequence of  Theorem 1 in \cite{DS}. (Note that in \cite{DS} the result is proved for the contact process, but as mentioned by the author the proof works as well for oriented percolation).  In fact, it still holds if we replace $3/4$ by  any $\alpha'< \alpha$. To prove the third one, we observe that if $\eta^x_{\ell_3} \neq \varnothing$ then 
\begin{align*}
r^x_{\ell_3} = r^{(- \infty, x]}_{\ell_3}.
\end{align*} 
Moreover, by the main result of Section 11 in \cite{D}, there is a positive constant $c$, such that for all   integer $x$,
\begin{align*}
\pp \left(r^{(- \infty, x]}_{\ell_3} \leq x + \alpha \ell_3/2 \right) \leq \exp(-c \ell).
\end{align*}
Therefore if $x \in [\ell_1, \ell_2]$, then
\begin{align*}
\pp \left(r^{x}_{\ell_3} \geq \ell_2 \mid \eta^x_{\ell_3} \neq \varnothing  \right) \geq 1- \exp(-c \ell),
\end{align*}
since $x+ \alpha \ell_3/2 \geq \ell_1 + \alpha \ell_3/2 \geq \ell_2$. Similarly
\begin{align*}
\pp \left(l^{x}_{\ell_3} \leq \ell_1 \mid \eta^x_{\ell_3} \neq \varnothing \right)  \geq 1- \exp(-c \ell).
\end{align*}
Then the third claim follows from the last two estimates.

To prove \eqref{eal2}, we use the same argument as in Section 10 in \cite{D}. We say that $A$ is more spread out than $B$ (and write $A \succ B$) if there is an increasing function $\varphi$ from $B$ into $A$ such that  $|\varphi(x) - \varphi(y)| \geq |x-y|$ for all $x,y \in B$. (Note that this implies $|A| \geq |B|$).  In \cite{D}, Durrett proves that there is a coupling such that if $A \succ B$ then 
\begin{align*}
\eta^A_t \succ \eta^B_t \textrm{ for all } t \geq 0,
\end{align*} 
and as a consequence $|\eta^A_t| \geq |\eta^B_t|$ for all $t$. Hence 
\begin{align*}
\pp(\eta^A_t = \varnothing) \leq \pp(\eta^B_t = \varnothing).
\end{align*}
On the other hand, by (ii)
\begin{align*}
\pp(\eta^{[\ell_1, \ell_1+ \ell_4]}_{\ell_3} = \varnothing) \leq \exp(- c \ell),
\end{align*}
with $\ell_4 = [3 \alpha \ell/8]-1$. We observe that $A \succ [\ell_1, \ell_1+ \ell_4]$ for any $A$ with $|A| \geq 3 \alpha \ell/8$. Thus \eqref{eal2} follows from the last two inequalities.
\end{proof}
 \subsection{Long path in a  site percolation.}  The Bernoulli site percolation on $\mathbb{Z}^d$ with parameter $p$ is defined as usual: designate each vertex in $\mathbb{Z}^d$  to be open independently with probability $p$ and closed otherwise. A path in $\mathbb{Z}^d$ is called open if all its sites are open.  Then there is a critical value $p_c^s(d) \in (0,1)$, such that if $p>p_c^s(d)$, then a.s. there exists an infinite open path (cluster), whereas if $p<p_c^s(d)$, a.s. there is no infinite cluster. 
 \begin{lem} \label{lpp}
Consider the Bernoulli site percolation on $[0,n ] ^d$ with $d \geq 2$ and  $p > p^s_c(2)$. Then there exists a positive constant $\rho=\rho(p,d)$, such that w.h.p. there is an open path whose length is larger than $\rho n^{d}$. 
 \end{lem}
 \begin{proof}
We set $m= [n^{1/4}]$. For $n,d \geq 2$, we say that the box $[0,n]^d$ is {\bf  $\rho$-good} if the site percolation cluster on it satisfies: 
 
there exist two vertices $x $ in $ \{m\} \times [0, n]^{d-1}$ and $y $ in $ \{n-m\} \times [ 0, n]^{d-1}$ and  an open path composed of  three parts: the first one  included in $[0,m] \times [ 0, n]^{d-1}$ has length larger than $m$ and ends at  $x$; the second one included in  $[m, n- m] \times [0, n]^{d-1}$ has length larger than $\rho n^{d}$, starts at $x$ and ends at $y$;  the third one  included in $[n-m,n] \times [ 0, n]^{d-1}$ starts at $y$ and has length larger than $m$.
  
  \vspace{0,2 cm}
 We now prove by induction on $d$ that if $p > p^s_c(2)$,  there is  a  positive constant $\rho_d=\rho(p,d)$, such that w.h.p. the box  $[0,n]^d$ is $\rho_d$-good. Then Lemma \ref{lpp} immediately follows. 

\vspace{0,2 cm}
 When $d=2$, the statement follows from the main result  in \cite{G2}.  We will prove it for $d=3$, the proof for $d\geq 4$ is exactly the same and will not be reproduced here.    
 
 \vspace{0,2 cm}
For $1 \leq i \leq n$, let $\Lambda_i = \{i\} \times [ 2 m, n- 2 m ]^2$. We define 
$$n_1= n-4m \quad \textrm{and} \quad m_1=[n_1^{1/4}].$$
We say that the $i^{th}$ plane is  {\bf nice} (or $\Lambda_i$ is nice) if the site percolation on this plane satisfies:  $\Lambda_i$ is $\rho_2$-good (we consider $\Lambda_i$ as a box in $\mathbb{Z}^2$); in each of the rectangles $\{i\} \times [m, 2m+m_1]\times [0,n]$ and $\{i\} \times [n- 2m-m_1,n-m]\times [0,n]$, there is a unique connected component of size larger than $m_1$, see Figure \ref{f1} for a sample of a nice plane.

The result for $d=2$ implies that w.h.p. $\Lambda_i$ is  $\rho_2$-good. On the other hand, we know that w.h.p. in the percolation on a box of size $n$ there is a unique open cluster having diameter  larger than $C \log n$ for some $C$ large enough (see for example Theorem 7.61 in \cite{G1}). Thus w.h.p. there is a unique open cluster of size larger $(C \log n)^d$.  Hence  $\Lambda_i$  is nice w.h.p. for all $i=1, \ldots, n$. Moreover, the events $\{ \Lambda_i \textrm{ is nice}\}$ are independent since the planes are disjoint. Therefore $\kA_n$ holds w.h.p. with 
\begin{align*}
\kA_n = \{ \# \{i: \Lambda_i \textrm{ is nice}\} \geq n/2 \}.
\end{align*}
On $\kA_n$, there are more than $n/2$ disjoint open paths (they are in disjoint planes), each of which has length larger than $\rho_2n_1^2$. Thus, to obtain an open path of length of order $n^3$, we will glue these long paths using  shorter paths in  good boxes of nice planes. To do that, we define  

$\kB_n=\{$ for all $1 \leq i \leq [n/2]$, there exist open paths: $\ell_{2i-1} \subset \{2i-1\} \times [ m, 2m] \times [0,n]$ whose end vertices are $u$ and $v$ with $u_3=0, v_3=n$; $\ell_{2i-1}' \subset \{2i-1\} \times [n- 2m,n-m] \times [0,n]$ whose end vertices are $u'$ and $v'$ with $u'_3=0, v'_3=n$; $\ell_{2i} \subset \{2i\} \times [m,2 m] \times [0,n]$ whose end vertices are $z$ and $t$ with $z_2=m, t_2=2m$; $\ell_{2i}' \subset \{2i\} \times [n- 2m,n-m] \times [0,n]$ whose end vertices are $z'$ and $t'$ with $z'_2=n- 2m, t'_2=n-m \}$.
 
  We observe that  $\ell_{2i-1}$ is a bottom-top crossing and $\ell_{2i}$ is a left-right crossing in two consecutive rectangles. Then they intersect when we consider only the last two coordinates, and the same holds for $\ell'_{2i-1}$ and $\ell'_{2i}$. Hence on $\kB_n$, for all $1 \leq i \leq n-2$, there are $a_i \in [m, 2m] \times [0,n]$, and $ b_i \in [n-2m, n-m] \times [0,n]$ such that 
\begin{align*}
(i,a_i) \in \ell_i \textrm{ and } (i+1,a_i) \in \ell_{i+1}, \\
(i,b_i) \in \ell_i' \textrm{ and } (i+1,b_i) \in \ell_{i+1}'. 
\end{align*}
In other word, we can jump from the $i^{th}$ plane to the next one in two ways. Moreover, on $\kA_n$  for all $i$ such that the $i^{th}$ plane is nice, the first part of the long open path in $\Lambda_i$ is connected to $\ell_i$ (as these paths  are in the same rectangle $\{i\} \times [m,2m+m_1] \times [0,n]$ and have length larger than $m_1$), and similarly the third part is connected to $\ell'_i$, see Figure \ref{f1}.

 
 \begin{center}
\begin{figure}
\begin{center}
\newrgbcolor{uququq}{0.25098039215686274 0.25098039215686274 0.25098039215686274}
\newrgbcolor{sqsqsq}{0.12549019607843137 0.12549019607843137 0.12549019607843137}
\psset{xunit=0.7cm,yunit=0.7cm,algebraic=true,dimen=middle,dotstyle=o,dotsize=3pt 0,linewidth=0.8pt,arrowsize=3pt 2,arrowinset=0.25}
\begin{pspicture*}(-1.,-2.5)(20.5,10.)
\psline[linestyle=dotted](1.,9.)(9.,9.)
\psline[linestyle=dotted](9.,9.)(9.,1.)
\psline[linestyle=dotted](9.,1.)(1.,1.)
\psline[linestyle=dotted](1.,9.)(1.,1.)
\psline[linestyle=dotted](3.,7.)(7.,7.)
\psline[linestyle=dotted](7.,7.)(7.,3.)
\psline[linestyle=dotted](7.,3.)(3.,3.)
\psline[linestyle=dotted](3.,3.)(3.,7.)
\parametricplot{0.0}{0.03}{-3332.73*t^(3.0)+0.0*t^(2.0)+11.24*t+3.75|1034.96*t^(3.0)+0.0*t^(2.0)+9.74*t+6.0}
\parametricplot{0.03}{0.04}{15182.8*t^(3.0)-1799.68*t^(2.0)+69.55*t+3.12|-6246.0*t^(3.0)+707.7*t^(2.0)-13.18*t+6.25}
\parametricplot{0.04}{0.13}{-1113.11*t^(3.0)+397.94*t^(2.0)-29.24*t+4.6|250.08*t^(3.0)-168.34*t^(2.0)+26.2*t+5.66}
\parametricplot{0.13}{0.19}{-1466.15*t^(3.0)+540.88*t^(2.0)-48.53*t+5.47|411.06*t^(3.0)-233.52*t^(2.0)+34.99*t+5.26}
\parametricplot{0.19}{0.24}{1736.0*t^(3.0)-1253.49*t^(2.0)+286.64*t-15.4|309.98*t^(3.0)-176.89*t^(2.0)+24.41*t+5.92}
\parametricplot{0.24}{0.34}{209.14*t^(3.0)-133.07*t^(2.0)+12.58*t+6.95|-626.55*t^(3.0)+510.35*t^(2.0)-143.69*t+19.63}
\parametricplot{0.34}{0.47}{-206.49*t^(3.0)+293.86*t^(2.0)-133.6*t+23.63|1158.81*t^(3.0)-1323.55*t^(2.0)+484.24*t-52.04}
\parametricplot{0.47}{0.53}{248.59*t^(3.0)-343.78*t^(2.0)+164.21*t-22.74|-3476.77*t^(3.0)+5171.65*t^(2.0)-2549.38*t+420.25}
\parametricplot{0.53}{0.62}{-536.13*t^(3.0)+905.05*t^(2.0)-498.26*t+94.41|2629.83*t^(3.0)-4546.58*t^(2.0)+2605.92*t-491.34}
\parametricplot{0.62}{0.69}{-111.02*t^(3.0)+116.16*t^(2.0)-10.28*t-6.21|-2063.66*t^(3.0)+4163.23*t^(2.0)-2781.73*t+619.55}
\parametricplot{0.69}{0.77}{1421.02*t^(3.0)-3061.38*t^(2.0)+2186.52*t-512.46|623.82*t^(3.0)-1410.76*t^(2.0)+1071.85*t-268.52}
\parametricplot{0.77}{0.85}{-1418.78*t^(3.0)+3539.71*t^(2.0)-2928.19*t+808.54|-1072.13*t^(3.0)+2531.47*t^(2.0)-1982.7*t+520.4}
\parametricplot{0.85}{0.88}{-1799.9*t^(3.0)+4515.43*t^(2.0)-3760.84*t+1045.4|1804.35*t^(3.0)-4832.64*t^(2.0)+4301.58*t-1267.2}
\parametricplot{0.88}{0.91}{1473.82*t^(3.0)-4110.81*t^(2.0)+3815.86*t-1172.89|921.71*t^(3.0)-2506.87*t^(2.0)+2258.79*t-669.11}
\parametricplot{0.91}{0.95}{2413.26*t^(3.0)-6679.12*t^(2.0)+6156.33*t-1883.83|267.98*t^(3.0)-719.66*t^(2.0)+630.12*t-174.39}
\parametricplot{0.95}{1.0}{-1725.3*t^(3.0)+5175.89*t^(2.0)-5163.34*t+1719.0|-354.1*t^(3.0)+1062.3*t^(2.0)-1071.36*t+367.16}
\parametricplot{0.0}{0.44}{1.73*t^(3.0)+0.0*t^(2.0)-1.45*t+3.75|-0.32*t^(3.0)+0.0*t^(2.0)-1.66*t+6.0}
\parametricplot{0.44}{1.0}{-1.38*t^(3.0)+4.14*t^(2.0)-3.29*t+4.02|0.25*t^(3.0)-0.76*t^(2.0)-1.32*t+5.95}
\parametricplot{0.0}{0.33}{-0.79*t^(3.0)+0.0*t^(2.0)+1.04*t+6.25|0.33*t^(3.0)+0.0*t^(2.0)+1.49*t+4.0}
\parametricplot{0.33}{1.0}{0.39*t^(3.0)-1.18*t^(2.0)+1.44*t+6.21|-0.17*t^(3.0)+0.5*t^(2.0)+1.32*t+4.02}
\rput[tl](0.6464601477866793,0.965096501028609){$0$}
\rput[tl](2.768363432054545,0.7154608205265065){$2m$}
%\rput[tl](6.48169417952331,0.965096501028609){$n-2m$}
\rput[tl](8.853233144293277,0.765096501028609){$n$}
\rput[tl](-0.04003797359410088,3.3990443859241086){$2m$}
\rput[tl](-0.955846919403344,7.268397433706697){$n-2m$}
\rput[tl](0.552846767598391,9.265482877723517){$n$}
\rput[tl](2.693181272305596,2.7503386405108192){$0$}
\psline[linestyle=dotted](6.25,7.)(6.25,3.)
\psline[linestyle=dotted](3.75,7.)(3.7477787703510566,3.)
\rput[tl](3.610883853749139,2.70557953252337176){$m_1$}
\rput[tl](6.856147700276463,2.709551846688525){$n_1$}
\psline[linestyle=dotted](11.,9.)(19.,9.)
\psline[linestyle=dotted](19.,9.)(19.,1.)
\psline[linestyle=dotted](19.,1.)(11.,1.)
\psline[linestyle=dotted](11.,1.)(11.,9.)
\parametricplot{0.0}{0.36}{7.5*t^(3.0)+0.0*t^(2.0)-1.58*t+2.57|0.11*t^(3.0)+0.0*t^(2.0)-8.13*t+9.0}
\parametricplot{0.36}{0.63}{-31.54*t^(3.0)+42.16*t^(2.0)-16.76*t+4.39|0.2*t^(3.0)-0.1*t^(2.0)-8.09*t+9.0}
\parametricplot{0.63}{0.87}{54.75*t^(3.0)-119.94*t^(2.0)+84.74*t-16.8|0.2*t^(3.0)-0.1*t^(2.0)-8.09*t+9.0}
\parametricplot{0.87}{1.0}{-60.04*t^(3.0)+180.12*t^(2.0)-176.7*t+59.13|-1.12*t^(3.0)+3.35*t^(2.0)-11.1*t+9.87}
\parametricplot{0.0}{0.37}{-0.49*t^(3.0)+0.0*t^(2.0)+1.35*t+2.35|-3.76*t^(3.0)+0.0*t^(2.0)+1.74*t+6.08}
\parametricplot{0.37}{1.0}{0.28*t^(3.0)-0.85*t^(2.0)+1.67*t+2.31|2.17*t^(3.0)-6.52*t^(2.0)+4.13*t+5.79}
\parametricplot{0.0}{0.2}{-23.0*t^(3.0)+0.0*t^(2.0)+4.13*t+7.22|-2.19*t^(3.0)+0.0*t^(2.0)-7.48*t+9.0}
\parametricplot{0.2}{0.6}{18.58*t^(3.0)-25.51*t^(2.0)+9.35*t+6.86|1.3*t^(3.0)-2.14*t^(2.0)-7.04*t+8.97}
\parametricplot{0.6}{1.0}{-6.81*t^(3.0)+20.43*t^(2.0)-18.36*t+12.43|-0.18*t^(3.0)+0.54*t^(2.0)-8.66*t+9.3}
\rput[tl](1.3017538091046965,1.7764124626604423){$(i,a_i)$}
\rput[tl](1.832229630171663,0.7026875809030833){$m$}
%\rput[tl](7.7610770420965824,0.621847440338218){$n-m$}
\psline[linestyle=dotted](13.,7.)(17.,7.)
\psline[linestyle=dotted](17.,7.)(17.,3.)
\psline[linestyle=dotted](17.,3.)(13.,3.)
\psline[linestyle=dotted](13.,3.)(13.,7.)
\psline[linestyle=dotted](13.75,7.)(13.75,3.)
\psline[linestyle=dotted](16.25,7.)(16.25,3.)
\parametricplot{0.0}{0.17}{-95.87*t^(3.0)+0.0*t^(2.0)+13.65*t+13.75|228.42*t^(3.0)+0.0*t^(2.0)-10.21*t+4.15}
\parametricplot{0.17}{0.24}{-319.38*t^(3.0)+116.67*t^(2.0)-6.65*t+14.93|-1765.33*t^(3.0)+1040.73*t^(2.0)-191.3*t+14.65}
\parametricplot{0.24}{0.35}{488.34*t^(3.0)-453.25*t^(2.0)+127.39*t+4.42|1147.62*t^(3.0)-1014.61*t^(2.0)+292.11*t-23.25}
\parametricplot{0.35}{0.44}{157.58*t^(3.0)-105.33*t^(2.0)+5.4*t+18.68|-1277.61*t^(3.0)+1536.47*t^(2.0)-602.38*t+81.3}
\parametricplot{0.44}{0.56}{-437.82*t^(3.0)+687.26*t^(2.0)-346.29*t+70.69|891.08*t^(3.0)-1350.4*t^(2.0)+678.58*t-108.16}
\parametricplot{0.56}{0.61}{-882.72*t^(3.0)+1440.15*t^(2.0)-770.99*t+150.55|-1872.39*t^(3.0)+3326.2*t^(2.0)-1959.47*t+387.87}
\parametricplot{0.61}{0.74}{700.31*t^(3.0)-1458.57*t^(2.0)+998.3*t-209.42|519.24*t^(3.0)-1053.17*t^(2.0)+713.57*t-155.98}
\parametricplot{0.74}{0.79}{265.52*t^(3.0)-490.56*t^(2.0)+279.94*t-31.72|-1134.02*t^(3.0)+2627.54*t^(2.0)-2017.92*t+519.71}
\parametricplot{0.79}{0.89}{-625.67*t^(3.0)+1629.66*t^(2.0)-1401.48*t+412.75|54.98*t^(3.0)-201.22*t^(2.0)+225.4*t-73.3}
\parametricplot{0.89}{1.0}{129.3*t^(3.0)-387.89*t^(2.0)+395.74*t-120.9|165.75*t^(3.0)-497.25*t^(2.0)+489.11*t-151.61}
\parametricplot{0.0}{0.6}{0.95*t^(3.0)+0.0*t^(2.0)-1.01*t+13.75|0.09*t^(3.0)+0.0*t^(2.0)+1.05*t+4.15}
\parametricplot{0.6}{1.0}{-1.4*t^(3.0)+4.19*t^(2.0)-3.51*t+14.25|-0.13*t^(3.0)+0.4*t^(2.0)+0.82*t+4.2}
\parametricplot{0.0}{0.28}{-2.15*t^(3.0)+0.0*t^(2.0)+1.55*t+16.25|-5.08*t^(3.0)+0.0*t^(2.0)+1.46*t+6.0}
\parametricplot{0.28}{1.0}{0.82*t^(3.0)-2.47*t^(2.0)+2.24*t+16.19|1.95*t^(3.0)-5.84*t^(2.0)+3.08*t+5.85}
\rput[tl](13.596311073833213,3.9295202069910764){$x_{i+1}$}
\rput[tl](15.830258958728705,5.864196730882371){$y_{i+1}$}
\parametricplot{0.0}{0.14}{11.94*t^(3.0)+0.0*t^(2.0)+1.16*t+12.0|-2.12*t^(3.0)+0.0*t^(2.0)+3.27*t+1.54}
\parametricplot{0.14}{0.38}{-24.62*t^(3.0)+15.62*t^(2.0)-1.06*t+12.11|2.88*t^(3.0)-2.14*t^(2.0)+3.58*t+1.53}
\parametricplot{0.38}{0.66}{28.53*t^(3.0)-45.56*t^(2.0)+22.42*t+9.1|-3.24*t^(3.0)+4.9*t^(2.0)+0.88*t+1.87}
\parametricplot{0.66}{1.0}{-11.28*t^(3.0)+33.85*t^(2.0)-30.39*t+20.81|1.55*t^(3.0)-4.64*t^(2.0)+7.22*t+0.47}
\parametricplot{0.0}{0.4}{-1.64*t^(3.0)+0.0*t^(2.0)+1.87*t+12.61|0.9*t^(3.0)+0.0*t^(2.0)+1.22*t+2.75}
\parametricplot{0.4}{1.0}{1.09*t^(3.0)-3.28*t^(2.0)+3.18*t+12.43|-0.6*t^(3.0)+1.8*t^(2.0)+0.51*t+2.84}
\rput[tl](12.316928211259942,1.963639223037019){$(i+1,a_i)$}
\rput[tl](11.568749808749432,3.5990443859241086){$A$}
\parametricplot{0.0}{0.24}{-5.89*t^(3.0)+0.0*t^(2.0)+1.51*t+17.0|-2.07*t^(3.0)+0.0*t^(2.0)-2.36*t+8.55}
\parametricplot{0.24}{0.7}{6.9*t^(3.0)-9.07*t^(2.0)+3.66*t+16.83|2.97*t^(3.0)-3.58*t^(2.0)-1.51*t+8.48}
\parametricplot{0.7}{1.0}{-6.2*t^(3.0)+18.6*t^(2.0)-15.83*t+21.41|-3.04*t^(3.0)+9.13*t^(2.0)-10.46*t+10.58}
\parametricplot{0.0}{0.52}{-1.24*t^(3.0)+0.0*t^(2.0)+1.45*t+16.81|0.51*t^(3.0)+0.0*t^(2.0)+0.78*t+5.52}
\parametricplot{0.52}{1.0}{1.32*t^(3.0)-3.96*t^(2.0)+3.5*t+16.46|-0.54*t^(3.0)+1.63*t^(2.0)-0.07*t+5.66}
\rput[tl](17.496868581678555,7.95489555508748){$B$}
\psline[linestyle=dotted](2.,9.)(2.,1.)
\psline[linestyle=dotted](3.,9.)(3.,1.)
\psline[linestyle=dotted](7.,9.)(7.,1.)
\psline[linestyle=dotted](8.,9.)(8.,1.)
\psline[linestyle=dotted](12.,9.)(12.,1.)
\psline[linestyle=dotted](13.,9.)(13.,1.)
\psline[linestyle=dotted](17.,9.)(17.,1.)
\psline[linestyle=dotted](18.,9.)(18.,1.)
\psline[linestyle=dashed,dash=5pt 5pt]{->}(2.392650781186411,8.050691865741532)(3.405292764223347,8.259189777774747)
\rput[tl](3.579679393686376,8.610189216405498){$\ell_i$}
\psline[linestyle=dashed,dash=5pt 5pt]{->}(7.7239941371870895,7.967810400550032)(6.309460831690122,7.757509005134907)
\rput[tl](5.620742537389377,8.110917855401294){$\ell'_i$}
\psline[linestyle=dashed,dash=5pt 5pt]{->}(12.649966871393385,4.33402075578454)(11.692872900834583,5.234034597723436)
\rput[tl](11.349589949314296,5.989014571133422){$\ell_{i+1}$}
\psline[linestyle=dashed,dash=5pt 5pt]{->}(17.63836923918209,6.387819261282242)(18.2328774067093,5.234034597723436)
\rput[tl](18.33938900337315,5.146494149438826){$\ell'_{i+1}$}
\rput[tl](2.50804080326821723,-0.15826406123085238){The $i^{th}$ plane is nice}
\rput[tl](11.847404032326908,-0.16465068104256391){The $(i+1)^{th}$ plane is nice}
\rput[tl](4.847404032326908,-1.6465068104256391){Legend: $A=(i+1,a_{i+1}), B =(i+1,b_{i+1})$.}
\parametricplot{0.0}{0.45}{-0.27*t^(3.0)+0.0*t^(2.0)+0.99*t+6.75|0.95*t^(3.0)+0.0*t^(2.0)-0.39*t+5.05}
\parametricplot{0.45}{1.0}{0.22*t^(3.0)-0.67*t^(2.0)+1.29*t+6.71|-0.78*t^(3.0)+2.33*t^(2.0)-1.43*t+5.2}
\begin{normalsize}
\psdots[dotstyle=*,linecolor=uququq](3.75,6.)
\rput[bl](3.798110614125715,5.396129829940929){\uququq{$x_i$}}
\psdots[dotstyle=*,linecolor=sqsqsq](6.25,4.)
\rput[bl](6.512898639586073,3.4302488459868714){\sqsqsq{$y_i$}}
\psdots[dotstyle=*,linecolor=sqsqsq](2.2,2.)
\psdots[dotstyle=*,linecolor=sqsqsq](13.75,4.147951427430405)
\psdots[dotstyle=*,linecolor=sqsqsq](16.25,6.)
\psdots[dotstyle=*,linecolor=sqsqsq](12.2,2.)
\psdots[dotstyle=*,linecolor=sqsqsq](12.248756618457788,3.6695858245098596)
\psdots[dotstyle=*,linecolor=sqsqsq](17.27998143259639,7.965912632088895)
\end{normalsize}
\end{pspicture*}
\caption{Gluing two long paths.}
\label{f1}
\end{center}
\end{figure}
\end{center}
On $\kA_n \cap \kB_n$, we can find in $[m,n-m] \times [0,n]^2$ a path of length larger than $\rho_2 n^{3}/3$ . Indeed, we start at the first nice plane, say the $i^{th}$ plane, at an end point, from the right for example, of the long path, then go along this long path towards the other end point. Then we can go to $\ell_i$ and arrive at $(i,a_i)$. Now we jump to $(i+1,a_i)$ (recall that it is a neighbor of $(i,a_i)$). If the $(i+1)^{th}$ plane is not nice, we go to $(i+1,a_{i+1})$ to jump to the next plane (note that both $(i+1,a_i)$ and $(i+1,a_{i+1})$ are in $\ell_{i+1}$). If the $(i+1)^{th}$ plane is nice, we now can touch and then go along to the long path in this plane and arrive at $(i+1,b_{i+1})$ to jump to the next plane. By continuing  this procedure, we can go through all the long paths of nice planes. The resulting path is in $[m,n-m] \times [0,n]^2$.

 Moreover, in the slabs $[0,m] \times [0,n]^2$ and $[n-m,n] \times [0,n]^2$, w.h.p. we can find two paths of length larger than $m$ which are connected to the long path we have just found above. These paths  form  the required three-parts long path. Therefore on $\kA_n \cap \kB_n$, w.h.p. the box $[0,n]^3$ is $\rho_3$-good with $\rho_3=\rho_2/3$.
  
Now it remains to show that $\kB_n$ holds w.h.p. We observe that the probability of the existence of such a path $\ell_i$ is larger than $1- \exp(-c m)$ for some $c>0$ (see for instance (7.70) in \cite{G1}). Thus $\kB_n$ holds w.h.p.

We summary here the change of proving the induction  from $d-1$  to $d$ when $d\geq 4$. First, in the definition of a {\it nice} box, we consider 
$$\Lambda_i = \{i \} \times [2m, n-2m]^{d-1},$$
and the uniqueness of the connected component of size larger than $m_1$ in the slabs $\{i\} \times [m,2m+m_1] \times [0,n]^{d-2}$ and $\{i\} \times [n-2m-m_1,n-m] \times [0,n]^{d-2}$. Secondly, in the definition of $\kB_n$, we consider $\ell_i \subset \{i\} \times \{m\}^{d-3} \times [0,n]^2$  and $\ell'_i \subset \{i\} \times \{n-m\}^{d-3} \times [0,n]^2$, two bottom-top (resp. left-right) crossings in the last two coordinates when $i$ is odd (resp. even).  

 \end{proof}

\section{Proof of Theorem \ref{trg}}
\subsection{Proof of (i)}
For $\ell,m \in \mathbb{N}$, we denote by $\kC(\ell, m)$  the graph obtained by attaching a  complete graph of size $ m$  to each vertex in $[ 0, \ell]$. 
\begin{lem} \label{p2}
Suppose that $d\geq 2$ and  $g$ satisfies \eqref{cdg}. Then there exist  positive constants $c_1$ and $C_1$, such that if $R^d \ge C_1$ then w.h.p.  $G(n,R,g)$ contains as a subgraph a copy of $\kC([c_1 n R^{-d}], [c_1 R^d])$.
\end{lem}
\begin{proof} If $n/R^d$ is bounded from above, then w.h.p. $G(n,R,g)$ contains a clique of size of order $n$ and thus the result follows. Indeed, by definition the vertices in $A=[0,R/\sqrt{d}]^d$ form a complete graph. Moreover  the number of vertices in $A$ is a Poisson random variable with mean $\int_{A} g(x) dx \asymp R^d \asymp n$, and hence w.h.p. it is of order $n$.

We now assume that $n/R^d $ tends to infinity. Let $\ell = [ \sqrt[d]{n}/(R/2\sqrt{d})]$, we divide the box $[ 0, \sqrt[d]{n}]^d$ into $\ell^d$  smaller boxes of equal size, numerated by $(E_a)_{a \in [ 1, \ell ] ^d}$, whose side length  is $R/(2\sqrt{d})$. We see that if $v$ and $w$ are  in the same small box or in  adjacent ones, then $\|v-w \| \leq R$, hence these two vertices are connected. This implies that the vertices on a small box form a clique and  two adjacent cliques are connected. 

 For any  $a \in [1, \ell]^d$, let us denote by 
$$X_a = \# \{ v: v \in E_a\}$$ 
the number of vertices located in $E_a$. Then   $(X_a)$ are independent and  $X_a$ is a Poisson random variable with mean 
\begin{align} \label{mua}
\mu_a = \int_{E_a} g(x) dx \geq b \left( \frac{R}{2 \sqrt{d}} \right)^d =: \mu, 
\end{align}
since $g(x) \geq b$ for all $x$. For any $a$, we define
$$Y_a = 1(\{ X_a \geq \mu /2 \}).$$
Since $\pp(\poi(\mu) \geq \mu/2) \rightarrow 1$ as $\mu \rightarrow \infty$, it follows from \eqref{mua} that  $\pp(Y_a =1) \rightarrow 1$ as $R \rightarrow \infty$. Therefore  there is a positive constant $C_1$, such that if $R^d \geq C_1$, then 
\begin{align*}
\pp(Y_a =1) \geq p:= (1+p^s_c(2))/2.
\end{align*}
We note that the Bernoulli random variables $(Y_a)$ are independent. Hence  if we say the small box $E_a$ open when $Y_a=1$ and closed otherwise, then we get a site percolation on $[1,\ell]^d$ which stochastically dominates the Bernoulli site percolation on $[1,\ell]^d$ with parameter $p> p^s_c(2)$. Then  Lemma \ref{lpp} gives that w.h.p. there is an open path of length $c \ell^d \asymp nR^{-d}$. On the other hand, in each open box, there is a clique of size $\mu/2 \asymp R^d$ and these cliques in adjacent open boxes are connected. Hence, the result follows by taking $c_1$ small enough.
 \end{proof}
\begin{lem} \label{tng} Let $\tau_{\ell,M}$ be the extinction time of the contact process on $C(\ell,M)$ starting from full occupancy. Then there exist positive constants $c$ and $K$ independent of $\lambda$, such that if $\lambda M \geq K$, then
\begin{align} \label{taun}
\pp(\tau_{\ell,M} \geq \exp(c \ell M \log (\lambda M))) \rightarrow 1 \quad \textrm{as} \quad \ell \rightarrow \infty.
\end{align}
\end{lem}
\begin{proof}
Let $(\xi_t)$ be the contact process on $\kC(\ell,M)$ with parameter $\lambda >0$. It is sufficient to consider the case  $\lambda \leq 1$, since the contact process is monotone in $\lambda$.
We assume also that $M \lambda \geq 640$. 

For $i \in [0, \ell]$, we say that  it is  {\bf lit} at time $t$ (the term is taken from \cite{CD}) if the number of infected vertices in its attached complete graph at time $t$ is larger than $M/4$.   

 Let $T= \exp(M \log ( \lambda M) /16 )$.   For $r \geq 0 $ and $ i,j \in [ 0, \ell]  $ s.t. $ |i-j| = 1$ and $i+ r$ is even, we define 
\begin{align*}
Z^r_{i,j} = & 1( \{\textrm{$i$ is not lit at time } rT \}) \\
+ & 1( \{\textrm{$i$ is lit at time $rT$ and $i$ makes $j$ lit at time $(r+1)T$} \}),
\end{align*}
where  "$i$ makes $j$ lit at time $(r+1)T $"   means that
\begin{align*}
& \left| \left \{  y \in C(j): \exists \, x \in C(i) \cap \xi_{rT}  \textrm{  s.t. } (x, rT) \leftrightarrow (y,(r+1)T)  
  \textrm{ inside } C(i) \cup C(j) \cup \{i,j\}
 \right \} \right| \\
 & \geq  M/4,
\end{align*}
with $C(i)$ the complete graph attached at $i$.  Then $(Z^r_{i,j})$ naturally define an oriented percolation  by identifying 
\begin{align*}
\{Z^r_{i,j}=1\} \Leftrightarrow \{(i,r) \leftrightarrow (j,r+1)\}.
\end{align*}
It follows from Lemma \ref{l5} (ii) that
$$ \pn \left(Z^r_{i,j}=1 \mid \kF_{rT} \right) \geq 1- 5T^{-1} \quad \forall \, r \geq 0 \textrm{ and } |i-j| = 1,$$
where $\kF_t$ denotes the sigma-field generated by the contact process up to time $t$.

Moreover if $x \neq i$ and $y \neq j,$ then $Z^r_{x,y}$ is independent of $Z^r_{i,j}.$ Hence by a result of Liggett, Schonmann and Stacey \cite{LSS} (see also Theorem B26 in \cite{L})  the distribution of the family $(Z^r_{i,j})$ stochastically dominates the  measure of a  Bernoulli oriented percolation with parameter 
$$q \geq 1- T^{- \gamma},$$ 
with  $ \gamma \in (0,1)$. Moreover, if $\lambda M$  is large enough, then $1- T^{- \gamma} > 1 -\varepsilon $, with $\varepsilon$  as in Lemma  \ref{lc}.

 In summary, when $\lambda M $ is large enough, the distribution of $(Z^r_{i,j})$ stochastically dominates the one of an    oriented percolation on $[0, \ell] $ with density close to $1$. On the other hand, it follows from Lemma  $\ref{lc}$ (ii) that w.h.p. the oriented percolation process survives  up to the step 
$$\left[(1-q)^{-c \ell} \right] \geq [T^{c\gamma \ell}] \geq \exp(c \gamma \ell M\log (\lambda M)),$$
for some constant $c>0$. Combining these, we get the result. 
\end{proof}
We now prove a  metastablity result  for connected graphs containing a copy of  $\kC(\ell,M)$. 
\begin{lem} \label{cvel}
Let $(G_n^0)$ be a sequence of connected graphs, such that $|G_n^0|\le n$, for all $n$. 
Let $\tau_n$ denote the extinction time of the contact process on $G_n^0$ 
starting from full occupancy. Assume that $G^0_n$ contains as a subgraph a copy of $\kC(\ell_n,M)$. Then there exists a positive constant $K$, such that if $M \geq K/ (\lambda \wedge 1)$ and
\begin{align} \label{nas}
\frac{\ell_n}{d_n \vee \log n} \rightarrow \infty,
\end{align}
with  $d_n$ the diameter of $G_n^0$, then 
\begin{align*} 
\frac{\tau_n}{\en (\tau_n)}\quad  \mathop{\longrightarrow}^{(\kL)}_{n\to \infty} \quad  \kE(1).
\end{align*}
\end{lem}  
\begin{proof}
According to Proposition 1.2 in \cite{M}, it suffices to show that there exists a sequence $(a_n)$, such that $a_n=o(\en(\tau_n))$ and 
\begin{eqnarray}
\label{xivxi}
\sup_{v\in V_n}\, \pn(\xi^v_{a_n} \neq \xi_{a_n}, \xi^v_{a_n} \neq \varnothing) = o(1),
\end{eqnarray}
where $(\xi_t)_{t\ge 0}$ denotes the process starting from full occupancy.

Set $\bar{\lambda}= \lambda \wedge 1$. Using Lemma \ref{tng}, we get 
\begin{align}
\label{taunDnmax}
\en(\tau_n) \geq \exp(c \ell_n M \log (\bar{\lambda}  M )), 
\end{align}
with $c$ as in this lemma. 
By \eqref{nas}, there is a sequence $(\varphi_n)$ tending to infinity, such that
\begin{align}
\label{Dnmaxdn}
\frac{\ell_n}{k_n} \rightarrow \infty,
\end{align}
with 
\begin{align*}
k_n = [(\log n \vee d_n)\varphi_n].
\end{align*}
Now define 
\begin{align*}
b_n= s_{k_n} T \quad \textrm{and}\quad a_n=2b_n+1,  
\end{align*}
with $s_{k_n}$ as in Lemma \ref{lc} (iii) and $T= \exp( M \log(\bar{\lambda }M)/16)$.

Then \eqref{taunDnmax} and \eqref{Dnmaxdn} show that $a_n=o(\en(\tau_n))$, so it remains  to prove \eqref{xivxi} for this choice of $(a_n)$. To this end it is convenient to introduce the dual contact process. 
Given some positive real $t$ and 
$A$ a subset of the vertex set $V_n$ of $G_n$,  the dual process $(\hat{\xi}^{A,t}_s)_{s\le t}$ is defined by 
\[\hat{\xi}^{A,t}_s = \{ v\in V_n : (v,t-s)\longleftrightarrow A \times \{ t \} \},\]
for all $s\le t$. It follows from the graphical construction that for any $v$, 
\begin{eqnarray} \label{vkr}
&&\nonumber \pn(\xi^v_{a_n} \neq \xi_{a_n}, \xi^v_{a_n} \neq \varnothing)\\
 &=& \pn (\exists w\in V_n : \xi^v_{a_n}(w) = 0,\, \xi^v_{a_n} \neq \varnothing,\, \hat{\xi}^{w,a_n}_{a_n} \neq \varnothing) \notag\\
&\le & \sum_{w\in V_n} \pn\left(\xi^v_{a_n} \neq \varnothing,\, \hat{\xi}^{w,a_n}_{a_n} \neq \varnothing, \textrm{ and } \hat{\xi}^{w,a_n}_{a_n-t} \cap  \xi^v_t  = \varnothing \textrm{ for all } t\le a_n\right), 
\end{eqnarray}
So let us prove now that the last sum above tends to $0$ when $n\to \infty$.

By the hypothesis, there are vertices  $x_0, \ldots, x_{k_n}$  together with complete graphs of size $M$, $C(x_0), \ldots, C(x_{k_n})$, which form a graph isomorphic to $\kC(k_n, M)$. Now we slightly change the definition of a lit vertex, and say that $x_i$ is lit if the number of its infected neighbors \textit{in $C(x_i)$} is larger than $M/4$ for $i= 0, \ldots, k_n$. 

We first claim that for any $v$
\begin{align}
\pp( \kA(v) ^c, \xi^v_{b_n} \neq \varnothing )  = o(1/n), \label{vbn1}
\end{align}  
with 
\begin{align*}
\kA(v)= \{\xi^v_{b_n} \neq \varnothing,  \,|\{i \in [(1- \beta)k_n/2,(1+ \beta)k_n/2 ]:  x_i \textrm{ is lit at time }b_n \}| \geq 3\beta k_n/4\},
\end{align*}
with $\beta$ as in Lemma \ref{lc}.

Suppose for a moment that \eqref{vbn1} holds. Then we also have 
\begin{align}
\pp( \hat{\kA}(w) ^c, \hat{\xi}^{w, 2b_n+1}_{b_n} \neq \varnothing )  = o(1/n), \label{vbn2}
\end{align}  
with 
\begin{eqnarray*}
\hat{\kA}(w) &= &\{\hat{\xi}^{w, 2b_n+1}_{b_n} \neq \varnothing, \, \, \exists \, S \subset [(1- \beta)k_n/2,(1+ \beta)k_n/2 ] \textrm{ with } |S| \geq 3 \beta k_n /4 \textrm{ and } \\
 & & \quad W_i \subset C(x_i) \textrm{ with } |W_i| \geq M/4 \, \forall \, i \in S:  (x,b_n+1) \leftrightarrow (w, 2b_n+1) \, \forall \, x \in \cup_{i \in S} W_i \}.
\end{eqnarray*}
Note that $\kA(v)$ and $\hat{\kA}(w)$ are independent for all $v$ and $w$. Moreover, on $\kA(v) \cap \hat{\kA}(w)$, there are more than $\beta k_n/2$ vertices which are lit in both the original and the dual processes. More precisely, there is a set $S \subset [(1- \beta)k_n/2,(1+ \beta)k_n/2 ]$ with $|S| \geq \beta k_n/2$ and sets $U_i, W_i \subset C(x_i) $ with $|U_i|, |W_i| \geq M/4$ for all $i \in S$, such that 
\begin{align*}
(v,0) \leftrightarrow (x, b_n) &\quad \textrm{ for all } \quad x \in \cup_{i \in S} U_i \\ 
(y,b_n+1) \leftrightarrow (w, 2b_n+1) &\quad \textrm{ for all } \quad y \in \cup_{i \in S} W_i.
\end{align*}
It is not difficult to show that there is a positive constant $c$, such that for any nonempty sets $U_i, W_i \subset C(x_i)$,  
\begin{eqnarray*} 
\pp(U_i \times \{b_n\} \mathop{\longleftrightarrow}^{C(x_i)} W_i \times \{b_n+1\} ) \geq c,
\end{eqnarray*} 
where the notation 
$$U_i \times \{b_n\} \mathop{\longleftrightarrow}^{C(x_i)} W_i \times \{b_n+1\}$$ 
means that there is an infection path inside $C(x_i)$ from a vertex in $U_i$ at time $b_n$ to a vertex in $W_i$ at time $b_n+1$. 

Moreover, conditionally on the sets $U_i,W_i$, these events are independent. Therefore, 
\begin{align*}
\pp(\exists i: U_i \times \{b_n\} \mathop{\longleftrightarrow}^{C(x_i)} W_i \times \{b_n+1\} \mid U_i,W_i) \geq 1- (1-c)^{\beta k_n/2} = 1 -o(1/n),
\end{align*}
by our choice of $k_n$. This implies that 
\begin{align} \label{vbn3}
\pp(\kA(v), \hat{\kA}(w), \hat{\xi}^{w,a_n}_{a_n-t} \cap  \xi^v_t  = \varnothing \textrm{ for all } t\le a_n) = o(1/n).
\end{align}
Combining \eqref{vbn1}, \eqref{vbn2} and \eqref{vbn3} we obtain \eqref{vkr}. Hence, now it amounts to prove \eqref{vbn1}. 

To see this, we define an oriented percolation $(\tilde{\eta}_r)_{r \geq 0}$ similarly as in Lemma \ref{tng}. For $0 \leq i,j \leq k_n$ and $r \geq 0$, such that  $|i-j|=1$ and $i+r$ is even,  we let $Z^r_{i,j}=1$ (or equivalently $(i,r) \leftrightarrow (j,r+1)$) if either $x_i$ is not lit at time $rT$ or $x_i$ is lit at time $rT$ and $x_i$ makes $x_j$ lit at time $(r+1)T$.

As in Lemma \ref{tng}, there exists a positive constant $K$, such that if $M \bar{\lambda} \geq K$, then $(\tilde{\eta}_r)$ stochastically dominates a Bernoulli oriented percolation with parameter $1- \varepsilon$, with $\varepsilon$ as in Lemma \ref{lc}.
  
Assume that $d_n$ is even, if not we just take the smallest even integer larger than $d_n$. Then we set 
$$\tilde{d}_n= d_n + 2 k_n.$$
Now define for $k\geq 0,$
\begin{align*}
\tilde{\sigma}_{k_n}(k) = \inf \{r \geq k \tilde{d}_n + d_n: \tilde{\eta}^{0, k \tilde{d}_n + d_n}_r (k_n)=1 \},
\end{align*}
where for any $A \subset \{0, \ldots, k_n\}$ and $t \geq s\geq 0$
\begin{align*}
\tilde{\eta}^{A,s}_t = \{x: \exists y \in A, (y,s) \leftrightarrow (x,t)\}.
\end{align*}
Note that $k \tilde{d}_n + d_n + 2k_n=(k+1)\tilde{d}_n$. Then using Lemma \ref{lc} (i), we get
\begin{align} \label{skj}
\pp(\tilde{\sigma}_{k_n}(k) \leq (k+1) \tilde{d}_n \mid \kF_{k \tilde{d}_n + d_n} ) \geq c.
\end{align}
We observe that if $\tilde{\sigma}_{k_n}(k) \leq (k+1) \tilde{d}_n$, then there is a horizontal crossing before $(k+1) \tilde{d}_n$.  Hence, 
\begin{align*}
\tilde{\eta}^{{\bf 1}}_r = \tilde{\eta}^{0,k \tilde{d}_n + d_n }_r \quad \textrm{ for all } r \geq (k+1) \tilde{d}_n.
\end{align*}
Define 
\begin{align*}
\kE= \{|\tilde{\eta}^{{\bf 1}}_{s_{k_n}} \cap [(1- \beta)k_n/2, (1+ \beta)k_n/2]| \geq 3 \beta k_n/4\}.
\end{align*}
On $\{\tilde{\sigma}_{k_n}(k) \leq (k+1) \tilde{d}_n \} \cap \kE$, if $(k+1)\tilde{d}_n \leq s_{k_n}$ then
 \begin{align} \label{egs}
 |\tilde{\eta}^{0,k \tilde{d}_n + d_n }_{s_{k_n}} \cap [(1- \beta)k_n/2, (1+ \beta)k_n/2]| \geq 3 \beta k_n/4.
 \end{align}
Let  $K_n=[s_{k_n}/\tilde{d}_n]$ and for any $0 \leq k \leq K_n-1$
\[A_k:=\{\xi^v_{k\tilde{d}_n}\neq \varnothing\},\] 
and 
\begin{align*}
B_k:= & \left\{ \xi_{k \tilde{d}_n}^v\times\{k\tilde{d}_n\} \longleftrightarrow (x_0,(k \tilde{d}_n + d_n -1)T) \right\} \cap \{x_0 \textrm{ is lit at time } (k \tilde{d}_n + d_n )T\}  \\
& \cap \{\tilde{\sigma}_{k_n}(k) \leq (k+1) \tilde{d}_n \}.  
\end{align*}
We have 
\begin{align} \label{xka}
\{\xi^v_{b_n} \neq \varnothing\} \subset \bigcap_{k=0}^{K_n-1} A_k.
\end{align}
On the other hand, if $x_0$ is lit at time $rT$ and $\tilde{\eta}^{0,r}_{s}(x_i)=1$ for $s>r$, then $x_i$ is lit at time $sT$. Hence by \eqref{egs} on $\kE$, if one of the events $(A_k \cap B_k)$ happens then $\kA(v)$ occurs.  Combing this with \eqref{xka}, we get
\begin{align}
\label{inc.bn}
\{\xi^v_{b_n} \neq \varnothing \} \cap \kA(v)^c  \subset \kE^c \cup  \bigcap_{k=0}^{K_n-1} A_k \cap B_k^c.
\end{align} 
Using Lemma \ref{lc} (iii), we obtain a bound for the first term 
\begin{align} \label{pec}
\pp(\kE^c) \leq \exp(-c k_n) = o(1/n),
\end{align}
by the choice of $k_n$. For the second term,   by using a similar argument as for \eqref{kii}, we have
\begin{eqnarray*}
\pn\left((z,t)\longleftrightarrow (z',t+(d_n-1)T)\right) \ge \exp(-C (d_n-1)T) \quad \textrm{for any $z, z'\in V_n$ and $t\ge 0$},
\end{eqnarray*}
for some constant $C>0$. On the other hand,    if $x_i$ is infected at time $t$ then it is lit at time $t+T$ with probability larger than $\exp(-CT)$.
Therefore combing with \eqref{skj}, we get that for any $k\le K_n-1$, 
$$\pn(B_k^c\mid \kG_k){\bf 1}(A_k) \le 1-c\exp(-Cd_nT),$$
where  $\kG_k = \kF_{k \tilde{d}_n}$.  Iterating this, we get  
\begin{eqnarray} \label{abc}
\pn\left(\bigcap_{k=0}^{K_n-1} A_k \cap B_k^c\right) &\le  & (1-c\exp(-Cd_nT))^{K_n-1} = o(1/n),
\end{eqnarray}
where the last equality follows from the definition of $s_{k_n}$. Combining \eqref{inc.bn}, \eqref{pec} and \eqref{abc}
we get \eqref{vbn1} and finish the proof. 
\end{proof}
  \noindent {\it Proof of Theorem \ref{trg} (i).} We first prove the lower bound on $\tau_n$.  By Lemma \ref{p2},  there are positive constants $c $ and $K$, such that if $R^d \geq K/ (\lambda \wedge 1)$, then w.h.p. $G(n,R,g)$ contains as a subgraph a copy of $\kC(\ell_n, M)$, with $\ell_n=[cnR^{-d}] $ and $M=[c R^d]$. 
  
 If $\ell_n$ is bounded (or $R^d \asymp n$), then $\kC(\ell_n,M)$ contains a complete graph of size of order $n$. Then Lemma \ref{l5} (i) implies that w.h.p. the extinction time is larger than $\exp(c n \log (\lambda n) )$, for some $c>0$.

If $\ell_n$ tends to infinity, then the result follows from Lemma \ref{tng}. 
  
   To prove the convergence in law of $\tau_n/\E(\tau_n)$, we recall some known results about the diameter of the giant component and the size of small components in RGGs. There is a positive constant $R_0$, such that if $R>R_0$, then w.h.p.
\begin{itemize}
\item[(a)] the diameter of the largest component is $d_n = \kO(n^{1/d}/R)$, \\
\item[(b)] the size of the second largest component is $\kO((\log n)^{d/(d-1)})$. 
\end{itemize} 
The first claim is proved in \cite{FSS} (Corollary 6) and the second one is proved in \cite{P} (Theorem 10.18) when $g\equiv 1$. It is  not hard  to generalize these results for our model with $g$ bounded both from below and above. 

The second claim together with Lemma \ref{bgg} below show that w.h.p. the extinction of the contact process on $G_n$ and on its largest component are equal. We are now in a position to complete the proof of (i). 
\begin{itemize}
\item[$\bullet$] If $R^d=o(n/ \log n)$, then by (a)
\begin{align*}
\frac{\ell_n}{d_n \vee \log n} \rightarrow \infty.
\end{align*}
Therefore, Lemmas \ref{p2} and \ref{cvel} imply the convergence in law of $\tau_n/ \en(\tau_n)$. \\
\item[$\bullet$] If $n/ \log n = \kO(R^d)$, then
\begin{align*}
\frac{D_{n,\max}}{d_n \vee \log n} \rightarrow \infty,
\end{align*}
since $R^d = \kO(D_{n,\max})$, with $D_{n,\max}$ the maximum degree in the largest component. Therefore, the result is proved by using Proposition 6.2 in \cite{CS} (see the latest version on arXiv). 
\end{itemize}
  \hfill $\square$
\subsection{Proof of (ii)} We prove an upper bound on  the extinction time of the contact process on an arbitrary graph.
\begin{lem} \label{bgg}
Let $\tau_G$ be the extinction time of the contact process on a graph $G=(V,E)$ starting from full occupancy. Then
\begin{itemize}
\item[(a)] $\pp(\tau_G \leq F(|V|,|E|)) \geq 1- \exp(-|V|)$,\\
\item[(b)]$\en(\tau_G) \leq 2 F(|V|,|E|)$
\end{itemize}
with 
\begin{align*}
F(|V|,|E|)= |V| \left( 2+ \frac{4 \lambda |E|}{|V|} \right)^{|V|}.
\end{align*}
\end{lem}
\begin{proof}   Observe that (b) is a consequence of (a) and the following. For any $s>0$
\begin{align*}
\en(\tau_G) \leq \frac{s}{\pp(\tau_G \leq s)}.
\end{align*}
This result is  Lemma 4.5  in \cite{MMVY}. 

We now prove (a). Let us denote by $(\xi_t)$ the contact process on $G$ starting with full occupancy. By using  Markov's property and the monotonicity of the contact process, it suffices to show that
\begin{align} \label{tpm}
\pp(\xi_1 = \varnothing) \geq \exp(-|V| \log (2+ 4 \lambda |E|/ |V|)).
\end{align}
 Observe that the process dies at time $1$  if for any vertex $v$, it heals before $1$ and does not infect any neighbor.  Let $\sigma_v$ be the time of the first recovery at $v$, then $\sigma_v \sim \kE(1)$. Let $\sigma_{v \rightarrow}$ be the time of the first  infection spread from $v$ to one of its neighbors. Then it is the minimum of $\deg(v)$ i.i.d. exponential random variables with mean $\lambda$ and thus $\sigma_{v \rightarrow} \sim \kE(\lambda \deg(v))$. Moreover $\sigma_v$ and $\sigma_{v\rightarrow}$ are independent. Therefore 
\begin{align*}
\pp(\sigma_v < \min \{\sigma_{v \rightarrow}, 1\})= \frac{1- e^{-(1+ \lambda \deg(v))}}{1+ \lambda \deg(v)}  \geq \frac{1}{2(1 + \lambda \deg(v))}.
\end{align*}
On the other hand, these events $\{\sigma_v < \min \{\sigma_{v \rightarrow}, 1\}\}_v$ are independent. Then using Cauchy's inequality, we get that
\begin{align*} 
\pp(\xi_1 = \varnothing) & \geq \prod_{v \in V} (2 + 2\lambda \deg(v))^{-1} \\
 & \geq \left( \frac{2 |V| + 2 \lambda \sum_{v \in V} \deg(v)}{|V|} \right)^{-|V|} \notag \\
& =  \left( 2+ \frac{4 \lambda |E|}{|V|} \right)^{-|V|},
\end{align*}
which implies \eqref{tpm}.
\end{proof}
  \noindent {\it Proof of Theorem \ref{trg} (ii).} The upper bound on $\tau_n$ follows from Lemma \ref{bgg} and  the following: w.h.p.  $G(n,R,g)=(V_n, E_n)$ with
\begin{itemize}
\item[$\bullet$] $ |V_n| \leq 2B n$\\
\item[$\bullet$] $|E_n| \leq C n R^d,$
for some $C=C(d,B)$.
\end{itemize}
The first claim is clear, since $|V_n|$ is a  Poisson random variable  with mean $$\int_{[0, \sqrt[d]{n}]^d} g(x) dx \leq B n.$$
For the second one, let $\ell = 1 + [\sqrt[d]{n}/R]$. We cover $[0, \sqrt[d]{n}]^d$ using translations by $R/2$ for each coordinate, accounting for $(2 \ell -1)^d$ boxes of volume $R^d$. We observe that   points at distance larger than $R$ are not connected. Hence, $|E_n|$ is less than the sum of the number of edges in the covering small boxes.

 These small boxes are partitioned into $2^d$ groups such that each group contains at most $\ell^d$ disjoint boxes with the same volume $R^d$. 
 
 The number of vertices in each box is stochastically dominated  by $Z$, a  Poisson random variable  with mean $BR^d$, since the integral of $g$ on a box is smaller than $BR^d$ (as $g(x) \leq B$ for all $x$). Hence, the number of edges  in a box is stochastically dominated by $Z^2$.
 
Moreover, in each group the numbers of edges are independent, as the boxes are disjoint. Therefore, using Chebyshev's inequality,  the total number of edges in a group is w.h.p. smaller than 
$$2 \ell^d \E(Z^2) = 2 \ell^d(BR^d)(BR^d+1).$$
Hence,  $|E_n|$ is w.h.p. less than 
$$2^{d+1} \ell^d (BR^d)(BR^d+1) \leq C nR^d,$$
for some $C=C(d,B)$ large enough. \hfill $\square$
\section{Some extensions}
\subsection{The  one-dimensional case} When $d=1$, RGGs are also called  random interval graphs, see for instance \cite{S}. We have the following result. 
\begin{prop} \label{pd1} Let $d=1$. Consider the contact process on  one-dimensional random geometric graphs $G(n,R,g)$ with  $g$ satisfying \eqref{cdg}. Then there exist positive constants $\varkappa, K, c$ and $C$ depending only on $b$ and $B$, such that the following statements hold.
\begin{itemize}
\item[(i)] If $R  \leq \varkappa \log n$, then w.h.p. the number of vertices in the largest component is $o(n^{2/3})$. Thus $\log \tau_n = o(n)$ w.h.p. \\
\item[(ii)] If $R \geq K \log n$, then w.h.p. the graph is connected and 
$$ c n \log (\lambda R) \leq \log ( \tau_n) \leq C n \log (\lambda R),$$
 and 
 \[ \frac{\tau_n}{\en(\tau_n)}\ \mathop{\longrightarrow}^{(\mathcal L)}_{n\to \infty}  \  \kE(1). \]
\end{itemize} 
\end{prop}
\begin{proof}
For (i), it is sufficient to consider  $R= \varkappa \log n$ with $\varkappa$ chosen later. We divide $[0,n]$ into $[n/R]$ intervals of length $R$, denoted by $I_1, \ldots, I_{[n/R]}$. Then the number of vertices in $I_i$ is a Poisson random variable with mean $\int_{I_i} g(x)dx \asymp R$. Therefore  
\begin{align} \label{bd1}
\pp(\#\{\textrm{vertices in } I_i \} \leq R^2 \textrm{ for all } i = 1, \ldots, [n/R]) = 1-o(1),
\end{align}
as $R \asymp \log n$. On the other hand, since $\int_{I_i} g(x) dx \leq BR$ for all $i$, the probability for an interval to be empty is larger than $e^{-BR}$. Hence
\begin{align} \label{bd2}
\pp(\textrm{there are at most $[\sqrt{n}]$ consecutive non-empty intervals}) &\geq 1- [n/R](1-e^{-BR})^{[\sqrt{n}]} \notag \\
& = 1- o(1),
\end{align}
with $R = \varkappa \log n$ and $\varkappa$ small enough.

We observe that if an interval is empty, then there is no edges between vertices in the left-hand side and the right-hand side of this interval. Thus, it follows from  \eqref{bd1} and \eqref{bd2} that w.h.p. the number of vertices in any component is  smaller than $R^2 [\sqrt{n}]=o(n^{2/3})$.

We now prove (ii). If $R \asymp n$, then the graph contains a complete graph of size of order $n$. Thus using Lemma \ref{l5} (i), we get the lower bound on  $\tau_n$. Assume that $R=o(n)$. We divide $[0,n]$ into $[2n/R]$ intervals of length $R/2$, denoted by $J_1, \ldots, J_{[2n/R]}$. Then the numbers of vertices in  these intervals form a sequence of  independent Poisson random variables with mean larger than $bR/2$. For all $i \leq [2n/R]$, we define 
\begin{align*}
\{J_i \textrm{ is good}\}= \{\textrm{the number of vertices in } J_i \geq bR/4\}.
\end{align*} 
We have 
\begin{align*}
\pp(\poi(bR/2) \geq bR/4) \geq 1- \exp(cR),
\end{align*}
for some constant $c=c(b)>0$. Therefore
\begin{align} \label{ji}
\pp( J_i \textrm{ is good for all } i \leq  [2n/R]) \geq 1-[2n/R] e^{-cR} = 1-o(1),
\end{align}
with $R \geq K \log n$ and $K$ large enough. This implies that w.h.p. $G(n,R,g)$ contains as a subgraph a copy of $\kC([2n/R], [bR/4])$ (note that the vertices in the same interval or in adjacent ones are connected). Thus similarly to  Theorem \ref{trg}, we get the lower bound on  $\tau_n$. The upper bound also follows from the same argument as in  Theorem \ref{trg}.    

For the connectivity, since all vertices in an interval $J_i$ or in adjacent ones are connected, we observe that 
\begin{align*}
\{J_i \textrm{ is good for all } i \leq [2n/R]\} \subset \{J_i \textrm{ is non-empty for all } i \leq [2n/R] \} \subset \{G_n \textrm{ is connected}\}.
\end{align*}
Therefore by \eqref{ji}, when $R \geq K \log n$ with $K$  large enough, w.h.p. $G_n$ is connected. In addition,  its diameter is $d_n \leq [2n/R]+1$.

For the convergence in law, we note that  $\kC(\ell,M)$ always contains  a copy of $\kC(\ell[M/M_1], M_1)$   if $M\geq M_1$. Moreover, w.h.p. $G_n$ contains a copy of $\kC([2n/R], [bR/4])$. Therefore, w.h.p. $G_n$ contains a copy of $\kC([cn],M)$ for some $c>0$ and $M$ as in Lemma \ref{cvel}. Hence, $G_n$ satisfies the hypothesis in Lemma \ref{cvel} and  the result follows.
\end{proof}
\subsection{An equivalent model} 
We consider another version of   random geometric graphs  with density function $f$ and connecting radius  $r$, denoted by $G'(n,r,f)$. It is defined as follows: place independently $n$ points in $[0,1]^d$ according to $f$, then connect two points $u$ and $v$ by an edge if $\|u-v\| \leq r$. Suppose that 
\begin{align} \label{eqf}
0< b \leq f(x) \leq B< + \infty \quad \textrm{ for all }x. 
\end{align}
Similarly to the results for $G(n,R,g)$,  we have the following.
\begin{prop}
The results of Theorem \ref{trg} and Proposition \ref{pd1}  hold for the graph $G'(n,r,f)$ with $f$ satisfying \eqref{eqf} by replacing $R^d$ by $nr^d$ in the statements. 
\end{prop}
\begin{proof}
First, we observe that the law of a Poisson point process with intensity $g$ on a set $A$ conditionally  on its number vertices, say $N$, is the same as that  of the process defined by placing independently $N$ points in $A$ with density $g/ \int_A g$. 

 Therefore, the graph  $G(n,R,g)$ conditionally  on its size $|G|$ is isomorphic to  $G'(|G|,r,f)$ with  
\begin{align*}
r = \sqrt[d]{n}/R \qquad \textrm{ and } \qquad f(x) =g  \left( x \sqrt[d]{n}\right).
\end{align*}
To prove the lower bound on $\tau_n$, we consider $G_1 = G(n/(2B), R_1,g_1)$, where 
\begin{align*}
R_1^d = nr^d/(2B) \qquad \textrm{ and } \qquad g_1(x) =f \left( \frac{x}{\sqrt[d]{n/(2B)}}\right).
\end{align*}
Since $|G_1|$ is a Poisson random variable with mean less than $n/2$, w.h.p. $|G_1|$ is less than $ n$. Therefore w.h.p.  $G_1$ can be coupled as a subgraph of  $G'(n, r, f )$. This domination together with Theorem \ref{trg}  and Proposition \ref{pd1}  imply the results for the lower bound on $\tau_n$ and the convergence in law of $\tau_n/\E(\tau_n)$ (note that the results of the connectivity and the diameter  of the largest component or the size of the second largest component also hold in  this model).

Similarly, for the upper bound of $\tau_n$, we consider  $G_2=G(2n/b,R_2,g_2)$ with 
\begin{align*}
R_2^d = (2n/b)r^d \qquad \textrm{ and } \qquad g_2(x) =f \left( \frac{x}{\sqrt[d]{(2n/b)}}\right).
\end{align*}
Then w.h.p. $G_2$ contains as a subgraph a copy of $G'(n,r,f)$. Thus by applying Theorem \ref{trg} and Proposition \ref{pd1}, we get desired results. 
\end{proof}
 \begin{ack} \emph{
 I am deeply grateful to my  advisor Bruno Schapira for his help and many suggestions during the preparation of this work.}
 \end{ack}
\begin{thebibliography}{99}


\bibitem{BBCS}  N. Berger, C. Borgs, J.T. Chayes, A. Saberi. { \it On the spread of viruses on the internet},  
Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, 301-310, (2005). 

\bibitem{C} V.H. Can. {\it Metastability for the contact process on the preferential attachment graph}, arXiv:1502.05633.

\bibitem{CD}  S. Chatterjee, R. Durrett. {\it Contact process on random graphs with degree power law distribution have critical value zero}, Ann. Probab. 37, 2332-2356 (2009). 

\bibitem{CMMV} M. Cranston,  T. Mountford, J.-C. Mourrat, D. Valesin. {\it The contact process on finite homogeneous trees revisited}, ALEA Lat. Am. J. Probab. Math. Stat. {\bf 11}, 385--408, (2014). 


\bibitem{CS} V.H. Can,  B. Schapira. {\it Metastability for the contact process on the configuration model with infinite mean degree}, Electron. J. Probab. {\bf 20} (2015), no. 26, 1--22, arXiv:1410.3061v3.

\bibitem{D} R. Durrett. {\it Oriented percolation in two dimensions}, Ann. Probab. {\bf 12}, 999-1040 (1984). 

\bibitem{DS} R. Durrett, R. H. Schonmann {\it Large deviation for the contact process and two dimensional  percolation}, Probab. Th. Rel. Fields. {\bf 77}, 583--603 (1988). 

\bibitem{FSS} T. Friedrich, T. Sauerwald, A. Stauffer. {\it Diameter and broadcast time of random geometric graphs in arbitrary dimensions}, Algorithmica. {\bf 67}, no. 1, 65--88 (2013). 

\bibitem{G} G. Ganesan. {\it Infection spread in random geometric graphs}, Adv. in Appl. Probab. {\bf 47}, 164--181 (2015).

\bibitem{G1} G. Grimmett. {\it Percolation.} Grundlehren der mathematischen Wissenschaften, {\bf{324}} Springer (1999).

\bibitem{G2} G. Grimmett. {\it Long paths an cycles in a random lattice.} Ann. Discrete Mathematics. 33, 69--76 (1985).

\bibitem{GK} P. Gupta, P. R. Kumar. {\it Critical power for asymptotic connectivity in wireless networks }, In Stochastic Analysis, Control, Optimization and Applications, Boston, MA, 547--566 (1999).

\bibitem{L}  T. Liggett. {\it Stochastic Interacting Systems: Contact, Voter and Exclusion Processes.} Grundlehren der Mathematischen Wissenschaften  {\bf{324}}, Springer (1999). 

\bibitem{LSS}  T. Liggett, R. Schonmann, A. Stacey. {\it Domination by product measure, } Ann. Prob. 25, 71-95 (1997).

\bibitem{M} T. Mountford. {\it A metastable result for the finite multidimensional contact process}, Canad. Math. Bull. {\bf 36}  (2), 216--226 (1993).

\bibitem{MMVY} T. Mountford, J.C.-Mourrat, D. Valesin, Q. Yao. {\it Exponential extinction time of the contact process on finite graphs},  arXiv:1203.2972.  

\bibitem{MVY}  T. Mountford, D. Valesin, Q. Yao. {\it Metastable densities for contact processes on random graphs}, Electron. J. Probab. {\bf 18}(2013), no 103, 1-36.  

\bibitem{MV} J.-C. Mourrat, D. Valesin. {\it Phase transition of the contact process on random regular graphs},  arXiv:1405.0865.  

   
\bibitem{MS} L. M\'enard, A. Singh. {\it Percolation by cumulative merging and phase transition for the contact process on random graphs}, arXiv:1502.06982v1.
   
 \bibitem{P} M. Penrose. {\it Random geometric graph}, Oxford University Press (2003).  
 
 \bibitem{PJ} V. M. Preciado, A. Jababaie. {\it Spectral analysis of virus spreading in random geometric networks}, IEEE Conference on decision and control, 4802--4807 (2009). 

\bibitem{S} E. R. Scheinerman. {\it An evolution of interval graphs}, Discrete Math. 82, 287--302 (1990).
\end{thebibliography}

\end{document}
1506.02373.extracted_bib
{BBCS N. Berger, C. Borgs, J.T. Chayes, A. Saberi. { On the spread of viruses on the internet, Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, 301-310, (2005).
1506.02373.extracted_bib
{C V.H. Can. {Metastability for the contact process on the preferential attachment graph, arXiv:1502.05633.
1506.02373.extracted_bib
{CD S. Chatterjee, R. Durrett. {Contact process on random graphs with degree power law distribution have critical value zero, Ann. Probab. 37, 2332-2356 (2009).
1506.02373.extracted_bib
{CMMV M. Cranston, T. Mountford, J.-C. Mourrat, D. Valesin. {The contact process on finite homogeneous trees revisited, ALEA Lat. Am. J. Probab. Math. Stat. {11, 385--408, (2014).
1506.02373.extracted_bib
{CS V.H. Can, B. Schapira. {Metastability for the contact process on the configuration model with infinite mean degree, Electron. J. Probab. {20 (2015), no. 26, 1--22, arXiv:1410.3061v3.
1506.02373.extracted_bib
{D R. Durrett. {Oriented percolation in two dimensions, Ann. Probab. {12, 999-1040 (1984).
1506.02373.extracted_bib
{DS R. Durrett, R. H. Schonmann {Large deviation for the contact process and two dimensional percolation, Probab. Th. Rel. Fields. {77, 583--603 (1988).
1506.02373.extracted_bib
{FSS T. Friedrich, T. Sauerwald, A. Stauffer. {Diameter and broadcast time of random geometric graphs in arbitrary dimensions, Algorithmica. {67, no. 1, 65--88 (2013).
1506.02373.extracted_bib
{G G. Ganesan. {Infection spread in random geometric graphs, Adv. in Appl. Probab. {47, 164--181 (2015).
1506.02373.extracted_bib
{G1 G. Grimmett. {Percolation. Grundlehren der mathematischen Wissenschaften, {324 Springer (1999).
1506.02373.extracted_bib
{G2 G. Grimmett. {Long paths an cycles in a random lattice. Ann. Discrete Mathematics. 33, 69--76 (1985).
1506.02373.extracted_bib
{GK P. Gupta, P. R. Kumar. {Critical power for asymptotic connectivity in wireless networks , In Stochastic Analysis, Control, Optimization and Applications, Boston, MA, 547--566 (1999).
1506.02373.extracted_bib
{L T. Liggett. {Stochastic Interacting Systems: Contact, Voter and Exclusion Processes. Grundlehren der Mathematischen Wissenschaften {324, Springer (1999).
1506.02373.extracted_bib
{LSS T. Liggett, R. Schonmann, A. Stacey. {Domination by product measure, Ann. Prob. 25, 71-95 (1997).
1506.02373.extracted_bib
{M T. Mountford. {A metastable result for the finite multidimensional contact process, Canad. Math. Bull. {36 (2), 216--226 (1993).
1506.02373.extracted_bib
{MMVY T. Mountford, J.C.-Mourrat, D. Valesin, Q. Yao. {Exponential extinction time of the contact process on finite graphs, arXiv:1203.2972.
1506.02373.extracted_bib
{MVY T. Mountford, D. Valesin, Q. Yao. {Metastable densities for contact processes on random graphs, Electron. J. Probab. {18(2013), no 103, 1-36.
1506.02373.extracted_bib
{MV J.-C. Mourrat, D. Valesin. {Phase transition of the contact process on random regular graphs, arXiv:1405.0865.
1506.02373.extracted_bib
{MS L. M\'enard, A. Singh. {Percolation by cumulative merging and phase transition for the contact process on random graphs, arXiv:1502.06982v1.
1506.02373.extracted_bib
{P M. Penrose. {Random geometric graph, Oxford University Press (2003).
1506.02373.extracted_bib
{PJ V. M. Preciado, A. Jababaie. {Spectral analysis of virus spreading in random geometric networks, IEEE Conference on decision and control, 4802--4807 (2009).
1506.02373.extracted_bib
{S E. R. Scheinerman. {An evolution of interval graphs, Discrete Math. 82, 287--302 (1990).