\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.24}{22(3)}{2015}

\usepackage{amssymb,amsfonts,amsmath,amsthm}
\usepackage{graphicx}
\usepackage{color}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

%\usepackage{setspace}
%\usepackage{showkeys}
%\usepackage{a4wide}
\usepackage{enumerate}
%\usepackage[margin=3cm]{geometry}
%\usepackage{ulem}
\usepackage{graphicx}
\usepackage{tikz}

\tikzstyle{every node}=[color=black, circle, draw, fill=black, inner sep=0pt, minimum width=2pt]
\tikzstyle{s}=[color=black, circle, draw, fill=black, inner sep=0pt, minimum width=1.5pt]
\tikzstyle{l}=[color=black, circle, draw, fill=black, inner sep=0pt, minimum width=3pt]
\tikzstyle{plain}=[color=black, fill=none, draw=none, inner sep=0pt, minimum width=2pt]
\usetikzlibrary{calc}
\usetikzlibrary{decorations.pathreplacing}

\newcommand{\A}{\mathcal{A}}
\newcommand{\La}{\mathcal{L}}
\newcommand{\U}{\mathcal{U}}
\newcommand{\eps}{\varepsilon}
\newcommand{\Pro}[1]{\mathbb{P} \left[\,#1\,\right]}
\newcommand{\Ex}[1]{\mathbb{E} \left[\, #1\,\right]}
\newcommand{\Be}{\mathsf{Be}}
\newcommand{\Bin}{\mathsf{Bin}}
\newcommand{\MP}{\mathsf{MP}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\Geom}{\mathsf{Geom}}


\renewcommand{\P}{\mathbb{P}}
\newcommand{\bP}{\mathbf{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\M}{\mathbf{M}}
\newcommand{\bQ}{\mathbf{Q}}
\newcommand{\bR}{\mathbf{R}}
\newcommand{\Abs}{A^{(k)}_{j,\ell}}
\newcommand{\h}{\mathcal{H}}
\newcommand{\I}{\mathfrak{I}}

\newcommand{\E}{\mathcal{E}}
\newcommand{\Prb}[1]{\mathrm{Pr}\Bigl[\,#1\,\Bigr]}
\newcommand{\Proo}[1]{\mathbf{Pr}[\,#1\,]}
\newcommand{\ex}[1]{\mathbf{E}[\,#1\,]}
\newcommand{\EX}[2]{\mathbf{E}_{#1} \left[\,#2\,\right]}


\newcommand{\cC}{\mathcal{C}}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\Ao}{\mathcal{A}_0}
\newcommand{\Af}{\mathcal{A}_f}
\newcommand{\V}{\mathrm{V}_N}
\newcommand{\N}{\mathcal{N}}
\newcommand{\D}{\mathcal{D}_R}
\newcommand{\G}{\mathcal{G}}
\newcommand{\Gnza}{\mathcal{G}(N;\zeta,\alpha)}
\newcommand{\Gnan}{\mathcal{G}(N;\alpha,\nu)}
\newcommand{\Pnan}{\mathcal{P}(N;\alpha,\nu)}
\newcommand{\Nn}{\mathcal{C}_N}
\newcommand{\NOTE}[1]{$^{\textcolor{red}
\clubsuit}$\marginpar{\setstretch{0.43}\textcolor{red}{\bf\tiny #1}}}

\newcommand{\ve}{\varepsilon}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Tobias' macros 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  \newenvironment{proof}{\vspace{1ex}\noindent{\bf Proof:}}{\hspace*{\fill}$\blacksquare$\vspace{1ex}}
  \newenvironment{proofof}[1]{\vspace{1ex}\noindent{\bf Proof of #1:}}{\hspace*{\fill}$\blacksquare$\vspace{1ex}}
  \def\noproof{\hspace*{\fill}$\blacksquare$}
\newcommand{\Acal}[0]{\ensuremath{{\mathcal A}}}
\newcommand{\Bcal}[0]{\ensuremath{{\mathcal B}}}
\newcommand{\Ccal}[0]{\ensuremath{{\mathcal C}}}
\newcommand{\Dcal}[0]{\ensuremath{{\mathcal D}}}
\newcommand{\Ecal}[0]{\ensuremath{{\mathcal E}}}
\newcommand{\Fcal}[0]{\ensuremath{{\mathcal F}}}
\newcommand{\Gcal}[0]{\ensuremath{{\mathcal G}}}
\newcommand{\Hcal}[0]{\ensuremath{{\mathcal H}}}
\newcommand{\Ical}[0]{\ensuremath{{\mathcal I}}}
\newcommand{\Jcal}[0]{\ensuremath{{\mathcal J}}}
\newcommand{\Kcal}[0]{\ensuremath{{\mathcal K}}}
\newcommand{\Lcal}[0]{\ensuremath{{\mathcal L}}}
\newcommand{\Mcal}[0]{\ensuremath{{\mathcal M}}}
\newcommand{\Ncal}[0]{\ensuremath{{\mathcal N}}}
\newcommand{\Ocal}[0]{\ensuremath{{\mathcal O}}}
\newcommand{\Pcal}[0]{\ensuremath{{\mathcal P}}}
\newcommand{\Qcal}[0]{\ensuremath{{\mathcal Q}}}
\newcommand{\Rcal}[0]{\ensuremath{{\mathcal R}}}
\newcommand{\Scal}[0]{\ensuremath{{\mathcal S}}}
\newcommand{\Tcal}[0]{\ensuremath{{\mathcal T}}}
\newcommand{\Ucal}[0]{\ensuremath{{\mathcal U}}}
\newcommand{\Vcal}[0]{\ensuremath{{\mathcal V}}}
\newcommand{\Wcal}[0]{\ensuremath{{\mathcal W}}}
\newcommand{\Xcal}[0]{\ensuremath{{\mathcal X}}}
\newcommand{\Ycal}[0]{\ensuremath{{\mathcal Y}}}
\newcommand{\Zcal}[0]{\ensuremath{{\mathcal Z}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\eR}[0]{\ensuremath{ \mathbb R}}
\newcommand{\RP}[0]{\ensuremath{{\eR}P}}
\newcommand{\Qu}[0]{\ensuremath{ \mathbb Q}}
\newcommand{\eN}[0]{\ensuremath{ \mathbb N}}
\newcommand{\Zed}[0]{\ensuremath{ \mathbb Z}}
\newcommand{\Cee}[0]{\ensuremath{ \mathbb C}}
\newcommand{\eF}[0]{\ensuremath{ \mathbb F }}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\atil}[0]{\tilde{a}}
\newcommand{\btil}[0]{\tilde{b}}
\newcommand{\ctil}[0]{\tilde{c}}
\newcommand{\mtil}[0]{\tilde{m}}
\newcommand{\ptil}[0]{\tilde{p}}
\newcommand{\qtil}[0]{\tilde{q}}
\newcommand{\rtil}[0]{\tilde{r}}
\newcommand{\xtil}[0]{\tilde{x}}
\newcommand{\ytil}[0]{\tilde{y}}
\newcommand{\Atil}[0]{\tilde{A}}
\newcommand{\Btil}[0]{\tilde{B}}
\newcommand{\Ctil}[0]{\tilde{C}}
\newcommand{\Dtil}[0]{\tilde{D}}
\newcommand{\Etil}[0]{\tilde{E}}
\newcommand{\Itil}[0]{\tilde{I}}
\newcommand{\Otil}[0]{\tilde{O}}
\newcommand{\Ptil}[0]{\tilde{P}}
\newcommand{\Qtil}[0]{\tilde{Q}}
\newcommand{\Stil}[0]{\tilde{S}}
\newcommand{\Ttil}[0]{\tilde{T}}
\newcommand{\Util}[0]{\tilde{U}}
\newcommand{\Vtil}[0]{\tilde{V}}
\newcommand{\Wtil}[0]{\tilde{W}}
\newcommand{\Xtil}[0]{\tilde{X}}
\newcommand{\Ytil}[0]{\tilde{Y}}
\newcommand{\Ztil}[0]{\tilde{Z}}
\newcommand{\Acaltil}[0]{\tilde{\Acal}}
\newcommand{\Lcaltil}[0]{\tilde{\Lcal}}
\newcommand{\Pcaltil}[0]{\tilde{\Pcal}}
\newcommand{\Qcaltil}[0]{\tilde{\Qcal}}
\newcommand{\Vcaltil}[0]{\tilde{\Vcal}}
\newcommand{\Wcaltil}[0]{\tilde{\Wcal}}
\newcommand{\elltil}[0]{\tilde{\ell}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\Ascr}[0]{\ensuremath{{\mathscr A}}}
\newcommand{\Bscr}[0]{\ensuremath{{\mathscr B}}}
\newcommand{\Cscr}[0]{\ensuremath{{\mathscr C}}}
\newcommand{\Dscr}[0]{\ensuremath{{\mathscr D}}}
\newcommand{\Escr}[0]{\ensuremath{{\mathscr E}}}
\newcommand{\Fscr}[0]{\ensuremath{{\mathscr F}}}
\newcommand{\Gscr}[0]{\ensuremath{{\mathscr G}}}
\newcommand{\Hscr}[0]{\ensuremath{{\mathscr H}}}
\newcommand{\Iscr}[0]{\ensuremath{{\mathscr I}}}
\newcommand{\Jscr}[0]{\ensuremath{{\mathscr J}}}
\newcommand{\Kscr}[0]{\ensuremath{{\mathscr K}}}
\newcommand{\Lscr}[0]{\ensuremath{{\mathscr L}}}
\newcommand{\Mscr}[0]{\ensuremath{{\mathscr M}}}
\newcommand{\Nscr}[0]{\ensuremath{{\mathscr N}}}
\newcommand{\Oscr}[0]{\ensuremath{{\mathscr O}}}
\newcommand{\Pscr}[0]{\ensuremath{{\mathscr P}}}
\newcommand{\Qscr}[0]{\ensuremath{{\mathscr Q}}}
\newcommand{\Rscr}[0]{\ensuremath{{\mathscr R}}}
\newcommand{\Sscr}[0]{\ensuremath{{\mathscr S}}}
\newcommand{\Tscr}[0]{\ensuremath{{\mathscr T}}}
\newcommand{\Uscr}[0]{\ensuremath{{\mathscr U}}}
\newcommand{\Vscr}[0]{\ensuremath{{\mathscr V}}}
\newcommand{\Wscr}[0]{\ensuremath{{\mathscr W}}}
\newcommand{\Xscr}[0]{\ensuremath{{\mathscr X}}}
\newcommand{\Yscr}[0]{\ensuremath{{\mathscr Y}}}
\newcommand{\Zscr}[0]{\ensuremath{{\mathscr Z}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%\newcommand{\len}[0]{\ensuremath{{\mu}}}
\newcommand{\iFF}[0]{if and only if }
\newcommand{\norm}[1]{\ensuremath{\|#1\|}}
\newcommand{\abs}[1]{ \ensuremath{ | #1 | }}
\newcommand{\tel}[1]{\ensuremath{ |#1| }}
\newcommand{\boven}[2]{\ensuremath{ { #1 \choose #2 } }}
\newcommand{\pgf}[1]{\ensuremath{ PG_{#1}( \eF ) }}
\newcommand{\Ha}[1]{\ensuremath{ {\cal H}_{#1} }}
\newcommand{\Ie}[0]{\ensuremath{ {\mathbb I}}}
\newcommand{\eS}[0]{\ensuremath{{\cal S}}}
\newcommand{\Bee}[0]{\ensuremath{{\cal B}}}
\newcommand{\Pee}[0]{\ensuremath{{\mathbb P}}}
\newcommand{\Ee}[0]{\ensuremath{{\mathbb E}}}
\newcommand{\doos}[1]{ \begin{tabular}{|c|} \hline #1 \cr \hline \end{tabular} }
\newcommand{\cl}[1]{ \ensuremath{\overline{#1}}}
\newcommand{\lo}[0]{ \ensuremath{{\mathcal L}}}
\newcommand{\drie}[0]{\ensuremath{ \bigtriangleup}}
\newcommand{\kl}[0]{\langle}
\newcommand{\gr}[0]{\rangle}
\newcommand{\isd}[0]{\hspace{.2ex} \raisebox{-.1ex}{$=$} \hspace{-1.5ex} 
\raisebox{1ex}{{$\scriptstyle d$}} \hspace{.8ex} }
\newcommand{\convd}[0]{\hspace{.2ex} \raisebox{-.1ex}{$\rightarrow$} \hspace{-1.5ex} 
\raisebox{1ex}{{$\scriptstyle d$}} \hspace{.8ex} }
\newcommand{\subneq}[0]{\hspace{.2ex} \raisebox{.5ex}{$\subset$} \hspace{-1.5ex} 
\raisebox{-.5ex}{{$\scriptstyle \neq$}} \hspace{.8ex} }
% \newcommand{\eps}{\varepsilon}
\newcommand{\dtv}{d_{\text{TV}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\DeclareMathOperator{\len}{len}
\DeclareMathOperator{\dist}{dist}
\DeclareMathOperator{\mood}{mod}
\DeclareMathOperator{\udg}{udg}
\DeclareMathOperator{\bsize}{bitsize}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\spanH}{span}
\DeclareMathOperator{\clo}{cl}
\DeclareMathOperator{\cross}{cross}
\DeclareMathOperator{\linhull}{linhull}
\DeclareMathOperator{\area}{area}
\DeclareMathOperator{\Po}{Po}
\DeclareMathOperator{\Bi}{Bi}
\DeclareMathOperator{\dd}{d}
\DeclareMathOperator{\Var}{Var}
%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\constr}[1]{{\bf(CPC-#1)}}
\newcommand{\Lcon}[1]{{\bf(\Lcal-#1)}}
\newcommand{\pr}[1]{{\bf(pr-#1)}}
\newcommand{\PP}[1]{{\bf(\Pcal\Pcal-#1)}}
\newcommand{\str}[1]{{\bf(str-#1)}}
\newcommand{\cruc}[1]{{\bf(cruc-#1)}}
\newcommand{\CG}[1]{{\bf(\Ccal-#1)}}
\newcommand{\HamG}[1]{{\bf(\Hcal-#1)}}
\newcommand{\GPo}[0]{\ensuremath{G_{\Pcal}}}
\newcommand{\Qcnr}[0]{\ensuremath{Q_{\text{cnr}}}}
\newcommand{\Qsde}[0]{\ensuremath{Q_{\text{sde}}}}
\newcommand{\Qmdl}[0]{\ensuremath{Q_{\text{mdl}}}}
\newcommand{\Rcnr}[0]{\ensuremath{R_{\text{cnr}}}}
\newcommand{\Rsde}[0]{\ensuremath{R_{\text{sde}}}}
\newcommand{\Rmdl}[0]{\ensuremath{R_{\text{mdl}}}}
\newcommand{\Wcnr}[0]{\ensuremath{W_{\text{cnr}}}}
\newcommand{\Wsde}[0]{\ensuremath{W_{\text{sde}}}}
\newcommand{\Wmdl}[0]{\ensuremath{W_{\text{mdl}}}}
\newcommand{\Zcnr}[0]{\ensuremath{Z_{\text{cnr}}}}
\newcommand{\Zsde}[0]{\ensuremath{Z_{\text{sde}}}}
\newcommand{\Zmdl}[0]{\ensuremath{Z_{\text{mdl}}}}
\newcommand{\mucnr}[0]{\ensuremath{\mu_{\text{cnr}}}}
\newcommand{\musde}[0]{\ensuremath{\mu_{\text{sde}}}}
\newcommand{\mumdl}[0]{\ensuremath{\mu_{\text{mdl}}}}
\newcommand{\Gammatil}[0]{\ensuremath{\tilde{\Gamma}}}
\newcommand{\Haa}[0]{\ensuremath{{\mathbb H}}}
\newcommand{\tobias}[1]{{\red{\bf[Tobias: #1]}}} 
\newcommand{\tnote}[1]{\marginpar{{\red \footnotesize\raggedright#1}}}
\newcommand{\nnote}[1]{\marginpar{{\green \footnotesize\raggedright#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% End of Tobias' macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\newtheorem{theorem}{Theorem}  %[chapter]
\newtheorem{fact}[theorem]{Fact}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observatio}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\numberwithin{theorem}{section}
\numberwithin{equation}{section}

%%% 

\def\red{\color{red}}
\newcommand{\TM}[1]{{\red[{\bf Tobias:} #1]}} 
\newcommand{\NF}[1]{{\green[{\bf Nick:} #1]}} 
\newcommand{\TMnote}[1]{\marginpar{{\red \footnotesize\raggedright#1}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% to remove my comments, you can simply comment out the above and un-comment the below:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newcommand{\TM}[1]{} 
%\newcommand{\TMnote}[1]{}

\def\green{\color{green}}
\newcommand{\MBnote}[1]{\marginpar{{\green \footnotesize\raggedright#1}}}

%%%%


\title{\bf On the largest component of a hyperbolic model of complex networks}

\author{Michel Bode \qquad Nikolaos Fountoulakis\thanks{This research has been supported by a Marie Curie Career Integration Grant
 PCIG09-GA2011-293619.}\\
\small School of Mathematics\\[-0.8ex]
\small University of Birmingham\\[-0.8ex] 
\small United Kingdom\\
\small\tt michel.bode@gmx.de, n.fountoulakis@bham.ac.uk\\
\and
Tobias M\"uller \\
\small Mathematical Institute\\[-0.8ex]
\small Utrecht University\\[-0.8ex]
\small  The Netherlands\\
\small\tt t.muller@uu.nl
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jan 6, 2015}{Aug 5, 2015}{Aug 14, 2015}\\
\small Mathematics Subject Classifications: 05C80, 05C82}


\begin{document}

\maketitle 

 \begin{abstract}
 We consider a model for complex networks that was introduced by Krioukov et al.
 In this model, $N$ points are chosen randomly inside a disk on the hyperbolic plane and any two of them are joined by an 
 edge if they are within a certain hyperbolic distance. 
The $N$ points are distributed according to a \emph{quasi-uniform} distribution, which is a distorted version of 
 the uniform distribution. 
The model turns out to behave similarly to the well-known Chung-Lu model, but without the independence between the 
edges. 
Namely, it exhibits a power-law degree sequence and small distances but, unlike the Chung-Lu model and many other well-known models for complex
networks, it also exhibits clustering. 

 The model is controlled by two parameters $\alpha$ and $\nu$ where, roughly speaking, $\alpha$ controls the exponent of the power-law
and $\nu$ controls the average degree.
 The present paper focuses on the evolution of the component structure of the random graph. 
 We show that {\bf(a)} for $\alpha > 1$ and $\nu$ arbitrary, with high probability, as the number of vertices grows, the largest component
 of the random graph has sublinear order; {\bf(b)} for $\alpha < 1$ and $\nu$ arbitrary with high probability there is a ``giant'' component 
 of linear order, 
 and {\bf(c)} when $\alpha=1$ then there is a non-trivial phase transition for the existence of a linear-sized component in terms of $\nu$. 
 
  \bigskip\noindent \textbf{Keywords:} random graphs on the hyperbolic plane; component structure; giant component; phase transition.
 \end{abstract}

\section{Introduction} 

The term  ``\emph{complex networks}" describes a class of large networks which exhibit the following fundamental properties:
\begin{enumerate}
\item[1.] they are \emph{sparse}, that is, the number of their edges is proportional to the number of nodes; 
\item[2.] they exhibit the \emph{small world phenomenon}: almost all pairs of vertices that are in the same component are within a 
short distance from each other;
\item[3.] \emph{clustering} is present: two nodes of the network that have a common 
neighbour are somewhat more likely to be connected with each other;  
\item[4.] their degree distribution is \emph{scale free}. This means that its tail follows a \emph{power law}. 
There has been extensive experimental evidence (see for example~\cite{BarAlb}) which 
suggests that many networks that emerge in applications have a degree distribution whose tail follows a power law 
with exponent between 2 and 3. 
\end{enumerate}
The books of Chung and Lu~\cite{ChungLuBook+} and of Dorogovtsev~\cite{Dor} are excellent references for a detailed discussion of these
properties. 

During the last 15 years a number of models have been developed in a series of attempts to capture these features. 
Among the first such models is the \emph{preferential attachment model}. 
This is a class of models of randomly growing graphs whose aim is to capture a 
basic feature of such networks: nodes which are already popular tend to become more popular as the network grows. 
It was introduced by Barab\'asi and Albert~\cite{BarAlb} and subsequently defined and studied rigorously 
by Bollob\'as, Riordan and co-authors (see for example~\cite{DegSeq},~\cite{Diam}).

Another extensively studied model was defined by Chung and Lu~\cite{ChungLu1+}, \cite{ChungLuComp+}. 
Here every vertex has a weight which effectively corresponds to its expected degree and every two vertices are joined \emph{independently}
of every other pair with probability that is proportional to the product of their weights. 
If these weights follow a power-law distribution, then it turns out that the resulting random graph has power-law degree distribution. 
This model is a special case of an \emph{inhomogeneous random graph}. 

All these models have their shortcomings. Namely, none of them succeeds in incorporating \emph{all} the above features.
For example, the Chung--Lu model exhibits a power law 
degree distribution (provided the weights of the vertices are suitably chosen)  and average distance of order $O(\log \log N)$ (when
the exponent of the power law is between 2 and 3, see~\cite{ChungLu1+}), but it does not exhibit clustering.
This is also the situation in the Barab\'asi-Albert model. 

In the case of the Chung-Lu model the absence of clustering is essentially due to the fact that pairs of vertices form edges independently. 
On the contrary, the presence of clustering requires the edges not to appear independently. If  two edges share a common endvertex, then 
the probability that their other two endvertices are joined must be higher compared to that where we assume nothing about these 
edges. This property is naturally present in random graphs that are created over metric spaces, such as random geometric graphs. 
In this context, the vertices are a random set of points in a given metric space and any two of them are adjacent if their distance is 
smaller than a certain distance. 

Recently Krioukov et al.~\cite{ar:Krioukov} introduced a model which naturally exhibits these typical features. 
In this model, a random network is created on the hyperbolic plane (we will see the detailed definition shortly). In particular, 
Krioukov et al.~\cite{ar:Krioukov} determined the degree distribution showing that it is \emph{scale free} 
and its tail follows a power law, whose exponent is determined by one of the parameters of the model. 
The exponent can take any value that is at least 2. 
Furthermore, they consider the clustering 
properties of the resulting random network. A numerical approach in~\cite{ar:Krioukov} suggests that the (local) clustering 
coefficient is positive and it is determined by one of the parameters of the model. 
These characteristics have been verified rigorously by Gugelmann, Panagiotou and Peter~\cite{ar:Gugel}. 


The basic hypothesis of Krioukov et al.~\cite{ar:Krioukov} was that the hyperbolic geometry underlies complex networks. In particular, 
the heterogeneity of the nodes, whose expression is the power law degree distribution, is in fact the expression of an underlying 
hyperbolic geometry. Complex networks do exhibit some sort of hierarchy in the sense that their nodes/members form groups which are 
further organised into subgroups etc. Thus, there is a hidden tree-like structure and the hyperbolic geometry is the natural 
space which can accommodate such a structure.  

The aim of the present work is the study the component structure of such a random graph and more specifically the number of vertices 
that are contained in a largest component of the graph. One of our main findings is that for the range of the parameters of the random graph model
where the exponent of the power law is larger than 3, the random graph typically consists of many relatively small components, no matter how 
large the average degree of the graph is. This is in sharp contrast with the classical Erd\H{o}s-R\'enyi model (see~\cite{Bol01}) as well as with
the situation on random geometric graphs on Euclidean spaces (see~\cite{bk:Penrose}) where the dependence on the average degree is
crucial. However, we show that the structure of the random geometric graph is significantly different when the exponent of the power law is
smaller than 3. In fact, we show that in this case a \emph{giant} component exists with high probability, that is, a component containing
a positive fraction of the vertices of the random graph.





\subsection{The model} 

We start by recalling some facts about the hyperbolic plane $\mathbb H$.
The hyperbolic plane is an unbounded surface of constant negative curvature $-1$.
There are several ways to represent it in two dimensions, including the half-plane model, the Beltrami-Klein disk model and the Poincar\'e disk model. 
In the Poincar\'e disk model, we equip the unit disk ${\mathbb D} := \{(x,y) \in \mathbb{R}^2 \ : x^2+y^2 <1 \}$
with the metric determined\footnote{%
%%%%%%%%%
This means that the length of a curve $\gamma : [0,1]\to{\mathbb D}$ is given by 
$\int_0^1\frac{\sqrt{(\gamma_1'(t))^2+(\gamma_2'(t))^2}}{1-\gamma_1^2(t)-\gamma_1^2(t)}{\dd}t$.
%%%%%%%%%%
} by the differential form ${\dd}s^2 = 4~\frac{dx^2 + dy^2}{(1-x^2-y^2)^2}$.
The book of Stillwell~\cite{bk:Stillwell} covers the basic theory of hyperbolic geometry. 
In this paper we find it helpful to draw pictures in the {\em native model} of $\mathbb H$. This is obtained from the Poincar\'e disk model
by multiplying each point $(x,y) \in {\mathbb D}$ by a scalar that equals the ratio of the distance to the origin in the hyperbolic metric, over 
the distance to the origin in the euclidean metric (in the case of the origin itself we define this ratio to equal one). This produces a model of 
$\mathbb H$ that fills all of $\eR^2$. It lacks many of the properties that make the classical models of $\mathbb H$ elegant to work with, but it 
does allow us to see more detail in visualizations of the graph model we are about to introduce.
To the best of our knowledge the native model was first introduced by Krioukov et al.~\cite{ar:Krioukov}.

Basic facts about $\mathbb H$ that we will rely on heavily in the paper are that 
in $\mathbb H$ a disk of radius $r$ (i.e.~the set of points at hyperbolic distance at most $r$ from a given point) has area equal to 
$2\pi(\cosh(r) - 1)$ and circumference length equal to $2\pi\sinh(r)$.  
Another important fact that we will rely on in the paper is the {\em hyperbolic cosine rule}. It 
states that if $A,B,C$ are distinct points on the hyperbolic plane, and we denote by $a$ the distance between $B,C$, by $b$ the distance between 
$A,C$, by $c$ the distance between $A,B$ and by $\gamma$ the angle (at $C$) between the shortest $AC$- and $BC$-paths, then 
$\cosh(c) = \cosh(a)\cosh(b) - \cos(\gamma)\sinh(a)\sinh(b)$.

We are now ready to introduce the model we will be studying in this paper.
We will name it the Krioukov-Papadopoulos-Kitsak-Vahdat-Bogu\~n\'a-model, after its inventors. For convenience we will 
abbreviate this to KPKVB-model throughout the rest of the paper.
The model has three parameters: the number of vertices $N$, which we think of as large, and $\alpha, \nu > 0$ which we think of as 
fixed.
Given $N, \nu, \alpha$, we compute $R := 2\log(N/\nu)$. 
We now select $N$ points independently at random from the disk of radius $R$ centred at the origin $O$, which we denote 
by $\D$, according to the following probability distribution. 
If the random point $u$ has polar coordinates $(r, \theta)$, then $\theta, r$ are independent, 
$\theta$ is uniformly distributed in $(0,2\pi]$ and 
the probability distribution of $r$ has density function given by:

\begin{equation} \label{eq:pdf}
 \rho (r) = \left\{\begin{array}{cl}
 \alpha \frac{\sinh  \alpha r}{\cosh \alpha R - 1} & \text{ if } 0 \leq r \leq R, \\
 0 & \text{ otherwise. }
\end{array} \right.
\end{equation}

\noindent
%%Here $\alpha >0$ is a parameter of the model. 
Note that when $\alpha = 1$, then this is simply the uniform distribution on $\D$. 

An alternative way to view this distribution is as follows. 
If we multiply the differential form in the Poincar\'e disk model by a factor $1/\alpha^2$ then we obtain
(a model of) the hyperbolic plane ${\mathbb H}_\alpha$ of curvature $-\alpha^2$. 
It can be seen that the above probability distribution 
corresponds precisely to a point taken uniformly at random from the disk of radius $R$ around the origin in ${\mathbb H}_\alpha$.
(We however treat these points as points of the ordinary hyperbolic plane.)
The set of $N$ points we have thus obtained will be the vertex set of our random graph and we denote it by $\V$. 
The KPKVB-random graph, denoted $\G (N; \alpha, \nu)$, is formed when we join each pair of vertices, if and only if they are within 
(hyperbolic) distance $R$.
Figure~\ref{fig:KPKVB} shows an example of such a random graph on $N=1000$ vertices.

\begin{figure}[h]
\begin{center}
 \includegraphics[height=8.5cm]{KPKVB.png}
 \end{center}
 \caption{Simulation of the KPKVB-model with $N=1000,\alpha=.9,\nu=2$. (Depicted in the native model.)\label{fig:KPKVB}}
\end{figure}


We should mention that Krioukov et al.~in fact had an additional parameter $\zeta$ in their definition of the model. 
In their definition, the points were taken inside a disk of radius $R_\zeta := (2/\zeta)\log(N/\nu)$ on the hyperbolic plane 
${\mathbb H}_\zeta$ of curvature $-\zeta^2$, and the points were generated according to~\eqref{eq:pdf} with $R_\zeta$ in place of $R$.
In this case the random graph is denoted by $\G(N;\zeta, \alpha,\nu)$. 
%All their results are stated in terms of the ratio $\zeta /\alpha$. 
However, %as it happens, 
it turns out that there is no need for the extra parameter $\zeta$.
The following lemma, which we prove in Appendix~\ref{sec:CouplApp}, shows that we can take $\zeta=1$ without any loss of generality.
We remind the reader that a {\em coupling} of two random objects $X,Y$ is a common probability space for a pair of objects $(X',Y')$ 
whose marginal distributions satisfy $X'\isd X, Y'\isd Y$.

\begin{lemma}\label{lem:CCCoupl}
Let $\alpha,\alpha',\zeta,\zeta'>0$ be such that $\zeta/\alpha = \zeta'/\alpha'$. %%< 2$.
For every $\nu$ and $N\in\eN$, there exists a coupling between
$\G(N; \zeta,\alpha,\nu)$ and $\G(N;\zeta',\alpha', \nu)$ 
such that $G(N;\zeta,\alpha,\nu) = G(N;\zeta',\alpha', \nu)$. 
\end{lemma}

\noindent
Thus, the previous lemma states that one can define $\G(N; \zeta,\alpha,\nu)$ and $\G(N;\zeta',\alpha', \nu)$  on a
common probability space in such a way that the two graphs are isomorphic (with probability one).
Let us also remark that {\em edge-set of $\G(N;\alpha,\nu)$ is decreasing in $\alpha$ and increasing in $\nu$} in the following precise sense.

\begin{lemma}\label{lem:decreasing}
Let $\alpha, \alpha', \nu, \nu' > 0$ be such that $\alpha \geq \alpha'$ and $\nu \leq \nu'$.
For every $N \in \eN$, there exists a coupling such that $G(N;\alpha, \nu)$ is a subgraph of $G(N;\alpha',\nu')$.
\end{lemma}

\noindent
The proof of Lemma~\ref{lem:decreasing} is given in Appendix~\ref{sec:decreasing}.

Krioukov et al.~\cite{ar:Krioukov} focus on the degree distribution of $\G (N; \alpha, \nu)$, showing that when 
$\alpha > \frac12$ this follows a power law with exponent $2\alpha  + 1$. They also discuss clustering on a smooth version of 
the above model. Their results have been verified rigorously by Gugelmann et al.~\cite{ar:Gugel}. 
%Moreover, Gugelmann et al.~\cite{ar:Gugel} have also shown that the clustering coefficient of $\G (N;\alpha, \nu)$ 
%is with high probability as $N$ grows bounded away from 0.   
Note that when $\alpha = 1$, that is, when the $N$ vertices are uniformly distributed in $\D$, the exponent of the power law is equal to 3. 
When $\frac12 <\alpha < 1$, the exponent is between 2 and 3, as is the case in a number of networks that emerge in applications 
such as computer networks, social networks and biological networks (see for example~\cite{BarAlb}).
They have also shown that the average degree of the random graph can be ``tuned" through the parameter $\nu$.
% Krioukov et al.~\cite{ar:Krioukov} introduce this model as a geometric framework for the study of complex networks. In fact, they view the 
% degree distribution as well as the existence of clustering at a local level as ``natural reflections of the underlying hyperbolic geometry". 
% This is made evident as, for example, the exponent of the power law of the degree distribution depends on the curvature of the hyperbolic
% space.

Throughout the paper, we will be using the notion of the \emph{type} of a vertex. For a vertex $u \in V_N$, its \emph{type} $t_u$
is defined to be equal to $R- r_u$ where $r_u$ is the radius of $u$ in $\D$.
Similarly, a point $p\in\D$ of radius $r_p$ has type $t_p=R-r_p$.
We note the following lemma, making it easier to work with the distribution of the types.
\begin{lemma}\label{lem:dist}
Uniformly for $0\leq t<0.99R$ we have
\begin{equation} \label{def_bar_rho}
 \bar{\rho}(t):=\rho(R-t)=(1+o_R(1))\alpha e^{-\alpha t}.
\end{equation}
\end{lemma}
\begin{proof}
	Using the pdf in Equation~\ref{eq:pdf}, we get
	\begin{align*}
		\rho(R-t)&=\alpha \frac{\sinh(\alpha (R-t))}{\cosh(\alpha R) - 1}
			=\alpha \frac{e^{\alpha (R-t)}-e^{-\alpha (R+t)}}{2}\frac{2}{e^{\alpha R}+e^{-\alpha R} - 2}\\
			&=\alpha \frac{e^{\alpha (R-t)}-e^{-\alpha (R+t)}}{e^{\alpha R}+e^{-\alpha R} - 2}
			=\alpha \frac{(1+o(1))e^{\alpha (R-t)}}{(1+o(1))e^{\alpha R}}\\
			&=(1+o(1))\alpha e^{-\alpha t}.
	\end{align*}
\end{proof}


\subsubsection{$\G (N; \alpha, \nu)$ and the Chung-Lu model} \label{sec:geom_asp}
The notion of \emph{inhomogeneous random graphs} was introduced by S\"oderberg~\cite{ar:s02} but
was defined more generally and studied in great detail by Bollob\'as, Janson and Riordan in~\cite{BJR}.
In its most general setting, there is an underlying compact metric space $\mathcal{S}$ equipped with a measure $\mu$ on its 
Borel $\sigma$-algebra. This is the space of \emph{types} of the vertices. A \emph{kernel} $\kappa$ is a bounded real-valued,
non-negative function on $\mathcal{S} \times \mathcal{S}$, which is symmetric and measurable. It is assumed that the vertices of the random 
graph are points in $\mathcal{S}$. If $x, y \in \mathcal{S}$, then the corresponding vertices are joined with probability 
that is equal to ${\kappa (x,y) \over N} \wedge 1$, where $N$ is the total number of vertices, independently of every other pair. 
The points that are the vertices of the graph are approximately distributed according to $\mu$. 
More specifically, the empirical measure induced by the $N$ points converges weakly to $\mu$ as $N \rightarrow \infty$. 

Of particular interest is the case where the kernel function can be factorised and can be written as $\kappa (x,y) = t(x)t(y)$ -- this 
is called a \emph{kernel of rank 1}. 
Here, the function $t(x)$ represents the weight of a vertex of type $x$ and, in fact, it is approximately its expected degree. 
The special case where $t(x)$ follows a distribution that has a power law tail was considered by Chung and Lu in a series of papers
~\cite{ChungLu1+}, \cite{ChungLuComp+} (see also~\cite{bk:vdH}). 

In the random graph $\G (N; \alpha, \nu)$ the probability that two vertices are adjacent has this form.  
The proof of this fact relies on Lemma~\ref{lem:relAngle}, which we will state and prove later. 
This provides an approximate characterization of what it means for two points $u,v$ to
have hyperbolic distance at most $R$ in terms of their \emph{relative angle}, which we denote by $\theta_{u,v}$. 

As we shall see later in Lemma~\ref{lem:relAngle}, two vertices $u$ and $v$ of types $t_u$ and $t_v$ are within distance $R$ 
(essentially) if and only if $\theta_{u,v} < 2 \nu {e^{t_u/2} e^{t_v/2}}/N$. Hence, conditional on their types the probability that $u$ and $v$ are adjacent is 
proportional to ${e^{t_u/2} e^{t_v/2}}/N$. 

But Lemma~\ref{lem:dist} shows that the type of a vertex is approximately exponentially distributed. 
Thus, if we set $t(u)= e^{t_u/2}$, then $\P (t(u) \geq x) = \P (t_u \geq 2 \ln x)\asymp 
e^{-2\alpha \ln x} = 1/x^{2\alpha}$. In other words, the distribution of $t(u)$ has a power-law tail with parameter $2\alpha + 1$. 
Thus, the random graph $\G (N; \alpha, \nu)$ can be seen as a \emph{dependent} version of the Chung-Lu model that emerges naturally from the 
hyperbolic geometry of the underlying space. The fact that this is a random geometric graph gives rise to the existence of local 
clustering, which is missing in the Chung-Lu model. There, most vertices have tree-like neighbourhoods.  

In fact, it can shown that the degree of a vertex $u$ in $\G (N; \alpha, \nu)$ that has type $t_u$ is approximately distributed as 
a Poisson random variable with parameter proportional to $e^{t_u/2}$. 




\subsection{Component structure of $\G(N;\alpha, \nu)$}
This paper focuses on the component structure of $\G (N;\alpha, \nu)$ and, in particular, the size of its largest component. 
% If we identify  the set of vertices $\V$ with the set $\{1,\ldots, N\}$, we let $L_1$ denote the largest lexicographically first component 
% of $\G(N;\zeta, \alpha)$. 
We denote by $|L_1|$ the size of a largest connected component of $\G (N; \alpha,\nu)$.  

 Among the key findings of Erd\H{o}s and R\'enyi on the theory of random graphs is the emergence of a component of linear order 
 in a uniformly chosen random graph on $N$ vertices and $M$ edges, usually denoted by $G(N,M)$.  
 Erd\H{o}s and R\'enyi~\cite{ErRen} showed that $N/2$ is the critical number of edges for the appearance of a component whose number of 
 vertices is proportional to $N$. That is, with probability $1-o(1)$, if $\frac{M}{N}< \frac{1-\eps}{2} $, for $\eps >0$, then every component 
 of $G(N,M)$ contains at most $C\ln N $ vertices, for some $C=C(\eps)>0$, but if $\frac{M}{N}> \frac{1+\eps}{2}$, then there exist
 constants $c_1, c_2$ depending on $\eps$ such that the largest component of $G(N,M)$ has at least $c_1 N$ vertices
 whereas every other component contains at most $c_2 \ln N$ vertices. 
 In the latter case, the largest component is also known as the \emph{giant component}. 
 See~\cite{Bol01} or~\cite{JLR} for a detailed exposition and analysis of the emergence of the giant component.  

 For (euclidean) random geometric graphs it is known %(see~\cite{bk:Penrose}) 
 that there exists a critical value $c$ for the average degree
 such that the size of the biggest component is sublinear if the expected average degree is less than $c$ and linear for expected average degree
 greater than $c$. The exact value of $c$ remains unknown.
 For more information on giant components in random geometric graphs see~\cite{bk:Penrose}.

In this contribution, we show that when $\alpha$ crosses 1 a ``phase transition" occurs. More specifically, if $\alpha > 1$, then 
\emph{asymptotically almost surely (a.a.s.)}, that is, with probability $1-o(1)$ as $N\rightarrow \infty$,  $|L_1|$ is bounded by a function
which is sublinear in $N$, whereas if $\alpha <1$, then $|L_1|$ is proportional to $N$. 
\begin{theorem} \label{thm:main} Let $\alpha, \nu$ be positive real numbers. The following hold:
\begin{itemize}
\item if $\alpha > 1$, then a.a.s. $|L_1| < 8 R^2 \log^3 R~N^{1 /\alpha}$.
\item if $\alpha < 1$, then there exists $c= c (\alpha, \nu)>0$ such that a.a.s. $|L_1| > c N$.
\end{itemize}
\end{theorem}
Recently, Kiwi and Mitsche~\cite{KiwiMitsche} showed that the second largest component is in fact at most poly-logarithmic in $N$, and at least logarithmic in $N$.  

The previous theorem shows there is a phase-change at $\alpha=1$. The next result shows that inside this phase-change, when $\alpha=1$, the existence
or not of a giant component depends on the value of $\nu$.
%The dependence on the parameter $\nu$ comes in when $\alpha = 1$. 

\begin{theorem}\label{thm:crit}
Assume that $\alpha=1$. 
There exist constants $\frac{\pi}{8}\leq\nu_0\leq\nu_1\leq 20\pi$ such that the following hold:
	\begin{itemize}
		\item If $\nu<\nu_0$, then a.a.s. $| L_1 |\leq \frac{N}{\log\log R}$.
		\item If $\nu>\nu_1$, then a.a.s. $|L_1 | \geq N/610$.
	\end{itemize}
\end{theorem}

%Note that the dependence of the size of $L_1$ on the parameters $\alpha$ and $\nu$ goes to opposite directions. 
%One can construct a coupling of the spaces $\G (N;\alpha, \nu)$ for various values of $\alpha$ that shows that as $\alpha$ decreases 
%the size of $L_1$ does not decrease. However, when $\alpha =1$, the size of $L_1$ depends on $\nu$ and it is non-decreasing in $\nu$. 

%The second result of this paper deals with the probability that the random graph is connected.
%A straightforward consequence of the results on the degree sequence~\cite{ar:Gugel}, is that the graph is 
%a.a.s.~disconnected whenever $\alpha > {1\over 2}$ (since there will then be vertices of degree zero).
%As it happens, the probability that the graph is connected becomes bounded away from zero exactly when $\alpha$ crosses $\frac12$.
%Let us also remark that the case $\alpha \leq {1\over 2}$  is a ``dense" regime in the sense that the average 
%degree of $\G (N; \alpha, \nu)$ is no longer constant, but grows with $N$.
% 
%\begin{theorem}\label{thm:connectivity} 
%Let $\alpha, \nu$ be positive real numbers and let $p_{\text{conn}}(N)$ denote the probability that the random graph 
%$\G (N;\alpha, \nu)$ is connected. The following hold: 
%\begin{enumerate} 
%\item\label{itm:lessthantwo} if $\alpha > {1\over 2}$ and $\nu > 0$ arbitrary, then $\displaystyle \lim_{N\to\infty}p_{\text{conn}} (N) = 0$; 
%\item\label{itm:morethantwo} if $\alpha < {1\over 2}$ and $\nu > 0$ arbitrary, then $\displaystyle \lim_{N\to\infty}p_{conn} (N) = 1$;
%\item\label{itm:equaltotwo} if $\alpha = {1\over 2}$ then there exist $\nu^-, \nu^+$ such that:
%\begin{enumerate} 
%\item\label{itm:equaltotowbig} If $\nu > \nu^+$, then $\displaystyle \lim_{N\to\infty} p_{\text{conn}}(N) = 1$;
%\item\label{itm:equaltotwosmall} If $0 < \nu < \nu^-$ then $\displaystyle 0 < \liminf_{N\to\infty} p_{\text{conn}}(N) \leq \limsup_{N\to\infty} p_{\text{conn}}(N) < 1$.
%%for some nondecreasing function $f : (0,\infty) \to (0, 1]$.
%%Moreover, there exists a $0 < \nu_0 < \infty$ such that $f(\nu) = 1$ for all $\nu > \nu_0$ while
%%$0 < f(\nu) < 1$ for all $0 < \nu < \nu_0$.  
%\end{enumerate}
%\end{enumerate}
%\end{theorem}
%
%The last part of this theorem exhibits a curious behaviour of our hyperbolic random geometric graph model that does not
%resemble anything in the literature as far as we are aware. 

We now proceed with some auxiliary results and the proof of the above theorems.

 
\section{Auxiliary results} \label{sec:aux}

We start by deriving some tools that help to approximate the probability that two points are adjacent in the graph.
%To fix our intuition, 
Let us first remark that the shape of the set of all point of $\D$ within 
distance $R$ of a given point varies greatly depending on the type of the point. See Figure~\ref{fig:tubes} for a depiction.

\begin{figure}
	\centering
		\includegraphics[scale=0.5]{drop.jpg}
	\caption{Sets of the points of distance $R$ from certain points. (Depicted in the native model.)\label{fig:tubes}}
\end{figure}

In particular, %as can be seen from the next lemma, 
when the type of the point is small, then the set of points
of $\D$ at distance $R$ from it resembles a ``long and very thin balloon'' in the native model. 
The following lemma is crucial to many computations in the paper.
%Assuming that the points have types $t_u$ and $t_v$, respectively, we give a condition which is effectively 
%an upper bound on the relative angle $\theta_{u,v}$ between $u$ and $v$ so that $d(u,v) < R$.  

\begin{lemma}\label{lem:relAngle}
%Let $\delta \in (-1,1) $ be a real numb.
For any $\eps>0$ there exists an $N_0>0$ and a $c_0>0$ such that for any $N>N_0$ and $u,v\in\D$ with $t_u+t_v < R-c_0$
the following hold.
\begin{itemize}
			\item If $\theta_{u,v} < 2 (1-\eps )\exp\left(\frac{1}{2}(t_u+t_v-R)\right)$, then $d(u,v) < R$.
			\item If $\theta_{u,v}> 2(1+\eps )\exp\left(\frac{1}{2}(t_u+t_v- R)\right)$,
				then $d(u,v) > R$.
		\end{itemize}
\end{lemma}
\begin{proof}
We begin with the hyperbolic law of cosines: 
\[
\begin{split}
\cosh (d(u,v))  = 
& \cosh (R- t_u ) \cosh (R-t_v) \\
& - \sinh (R- t_u) \sinh (R-t_v) 
\cos ( \theta_{u,v} ).
\end{split}
\]
The right-hand side of the above becomes:
\begin{equation} \label{eq:coslaw} 
\begin{split} 
	&\cosh (R- t_u ) \cosh (R-t_v) - \sinh (R- t_u ) \sinh (R-t_v ) \cos ( \theta_{u,v} ) \\
	& = {e^{2R- (t_u + t_v)} \over 4} \left[ \left(1+e^{-2(R-t_u)}\right)\left(1+e^{-2 (R-t_v)}\right) \right.\\
	& \quad \left. -\left(1-e^{-2 (R-t_u)}\right)\left(1-e^{-2 (R-t_v)}\right) \cos (\theta_{u,v}) \right] \\
	& = {e^{ (2R- (t_u + t_v))} \over 4} \left[1- \cos (\theta_{u,v}) + \left(1+ \cos (\theta_{u,v}) \right) 
	\left( e^{-2 (R-t_u)} +  e^{-2 (R-t_v)}\right) \right. \\
	& \quad \left. + O\left( e^{-2 (2R- (t_u + t_v))}\right)\right].
\end{split}
\end{equation}
Therefore,
\begin{equation*}
	\begin{split}
    &\cosh ( d(u,v)) \leq \\
	&  {e^{ (2R-(t_u + t_v))} \over 4} \left[1- \cos (\theta_{u,v}) + 2 
	\left( e^{-2(R-t_u)} +  e^{-2 (R-t_v)}\right)  + O\left( e^{-2 (2R- (t_u + t_v))}\right)\right].
	\end{split}
\end{equation*}
Since $t_u+t_v < R-c_0$, the last error term is $O(N^{-4})$. 
Also, it is a basic trigonometric identity that $1- \cos (\theta_{u,v}) = 2\sin^2 \left( {\theta_{u,v} \over 2} \right)$. 
The latter is at most ${\theta_{u,v}^2 \over 2}$. 
 Therefore, the upper bound on $\theta_{u,v}$ yields:
  \begin{equation*}  
\begin{split}
      &\cosh ( d(u,v))  \\
      &\leq {e^{2R- (t_u + t_v)} \over 4} \left( {\theta_{u,v}^2 \over 2} + 2 
	\left( e^{-2 (R-t_u)} +  e^{-2 (R-t_v)}\right) + O\left( {1\over N^4}\right)\right) \\
	&\leq {e^{ (2R- (t_u + t_v))} \over 4} \left( 2(1-\eps )^2 e^{t_u+t_v - R} + 2 
	\left( e^{-2 (R-t_u)} +  e^{-2 (R-t_v)}\right) \right) + O\left( 1\right) \\
	&= (1-\eps)^2{e^{ R} \over 2} + {1\over 2}\left(e^{t_u-t_v} + e^{t_v-t_u} \right) + O(1)\\
	&< (1-\eps)^2{e^{ R} \over 2} + \eps {e^{ R} \over 2} + O(1) < {e^{ R} \over 2}, 
	\end{split}
 \end{equation*}  
for $N$ sufficiently large and $c_0$ such that $e^{-c_0}<\frac{1}{2}\eps$, since $t_u+t_v <  R-c_0$ and $t_u,t_v\geq0$.  
This implies that $t_u-t_v,t_v-t_u<  R-c_0$ and, therefore, 
${1\over 2}\left(e^{t_u-t_v} + e^{t_v-t_u}\right)<{1\over 2}\left(e^{R-c_0} + e^{R-c_0}\right)<\eps{e^{R}\over 2}$. 
Also, since $\cosh (d(u,v))> {1\over 2} e^{ d(u,v)}$, it follows that $d(u,v) < R$. 

To deduce the second part of the lemma, we consider a lower bound on (\ref{eq:coslaw}) using the lower bound on $\theta_{u,v}$: 
\begin{equation} \label{eq:coslawLow} 
    \begin{split} 
     \cosh ( d(u,v)) & \geq   {e^{2R- (t_u + t_v)} \over 4} \left(1- \cos (\theta_{u,v}) \right) +O(1) \\
     & \geq {e^{2R- (t_u + t_v)} \over 4} \left(1- \cos \left(2(1+\eps){e^{\frac{1}{2}(t_u+t_v- R)}}\right) \right)
+O(1). 
    \end{split}
\end{equation}
Using again that $1- \cos(\theta) = 2\sin^2 \left({\theta  \over 2} \right)$ we deduce that 
 $$ 1- \cos \left(2(1+\eps)e^{\frac{1}{2}(t_u+t_v - R)}\right)  = 2 \sin^2 \left( {1\over 2}~4(1+\eps)^2  
e^{t_u+t_v - R} \right).$$
Since $t_u+t_v < R - c_0$, it follows that $t_u+t_v-  R <- c_0$. 
So the latter is 
    \[ \begin{split}\sin & \left( {1\over 2}~4(1+\eps)^2  e^{t_u+t_v- R}  \right)> 2\left(1+{\eps \over 2}\right)^2
e^{t_u+t_v-  R},
\end{split}\]
for $N$ and $c_0$ large enough, using the Taylor's expansion of the sine function around $0$.
Substituting this bound into (\ref{eq:coslawLow}) we have 
 $$ \cosh ( d(u,v))  \geq \left(1+{\eps \over 2}\right)^2 {e^{R} \over 2} + O(1).$$
Thus, if $d(u,v) \leq  R$, the left-hand side would be smaller than the right-hand side which would lead to a contradiction. 
\end{proof}

We will define approximating areas of the circle of radius $R$ around a given point $u$, motivated by Lemma~\ref{lem:relAngle}.
	We call these bounding areas \textit{inner} and \textit{outer tube} of the point $u$.
	\begin{definition} \label{def:tubes}
      For a given point $u\in\D$ and for $\ve$ and $N_0$ as in Lemma~\ref{lem:relAngle} we call the sets
		\begin{itemize}
			\item $T_u^-:=\left\{v\in\D: \theta_{u,v}\leq2(1-\ve)\exp\left(\frac{1}{2}(t_u+t_v-R)\right)\right\}$ the \textit{inner tube} and
			\item $T_u^+:=\left\{v\in\D: \theta_{u,v}\leq2(1+\ve)\exp\left(\frac{1}{2}(t_u+t_v-R)\right)\right\}$ the \textit{outer tube}
		\end{itemize}
		of the point $u$.
	\end{definition}
	Although by our definition there is no unique inner and outer tube, we will talk of the inner and outer tube.
	These should always be for suitably chosen $\ve$ and $N_0$ in the given context.
	Lemma~\ref{lem:relAngle} shows that, for sufficiently large graphs, all points in the inner tube of a typical vertex $u$ (that is, 
a vertex of low type) are of distance at most $R$ of $u$
	and all vertices of distance at most $R$ of $u$ are within the outer tube of $u$.
We will use outer and inner tubes to derive stochastic bounds on the size of a component.


During our proofs we will also use the following lemma, which states that every vertex in the neighbourhood of a given vertex $u$ will
still be connected to $u$ when we increase $t_u$.
	\begin{lemma}\label{lem:changeType}
		Let $u$, $v$ and $w$ be points in $\D$ with $\theta_{u,v}=0$ and $t_u<t_v$.
		If $d(u,w)<R$ then $d(v,w)<R$.
	\end{lemma}
	\begin{proof}	
		Using basic properties of the geometry of the hyperbolic plane, it follows that the geodesic between two points of radius at most 
        $R$ uses only points of radius at most $R$.
		Also note that the geodesic between the origin and any point is the ray from the origin through the point.
		Let $O$ be the origin, and consider vertices $u,v,w$ as in the statement of the lemma.
		Consider some isometric mapping which maps $w$ to $O$. As $w\in\D$, we have $d(O,w)\leq R$.
		By the requirements of the lemma, $d(u,w)\leq R$.
		So $O$ and $u$ are within the disk of radius $R$ around $w$, and so is their geodesic.
		Since $\theta_{u,v}=0$, it follows that $v$ lies on this geodesic and therefore $d(v,w)\leq R$.
	\end{proof}
% 		To work out hyperbolic distances involves using the hyperbolic law of cosines.
% 		Since we are only interested in whether or not the distance between two points exceeds $R$, we use the following lemma to identify sets 
%     that are within a certain distance from a given vertex. 
%     For two points $u$ and $v$ in $\D$, we denote by $\theta_{u,v} \in [0,\pi]$ the relative angle between $u$ and $v$  (with the centre of $\D$ 
%     being the reference point).
    
%	\begin{lemma}\label{lem:relAngle}
%		For any $\ve>0$ there exists an $N_0>0$ and a $c_0>0$ such that for any $N>N_0$ and $u,v\in\D$ with $t_u+t_v < R-c_0$ the following hold.
%		\begin{itemize}
%			\item If $\theta_{u,v} \leq 2 (1-\ve)\exp\left(\frac{1}{2}(t_u+t_v-R)\right)$, then $d(u,v) < R$.
%			\item If $\theta_{u,v}> 2(1+\ve)\exp\left(\frac{1}{2}(t_u+t_v-R)\right)$,
%				then $d(u,v) > R$.
%		\end{itemize}
%	\end{lemma}
%	\begin{proof}
%     We begin with the hyperbolic law of cosines: 
%	\begin{equation*} \label{eq:CosinesLawInit}
%	\cosh (d(u,v)) = \cosh (R- t_u) \cosh (R-t_v) - \sinh (R- t_u) \sinh (R-t_v) \cos ( \theta_{u,v} ).
%	\end{equation*}
%	The right-hand side of the above becomes:
%	\begin{equation} \label{eq:coslaw} 
%	\begin{split} 
%	&\cosh (R- t_u) \cosh (R-t_v) - \sinh (R- t_u) \sinh (R-t_v) \cos ( \theta_{u,v} ) = \\
%	& {e^{2R- (t_u + t_v)} \over 4} \left( \left(1+e^{-2(R-t_u)}\right)\left(1+e^{-2(R-t_v)}\right) 
%      -\left(1-e^{-2(R-t_u)}\right)\left(1-e^{-2(R-t_v)}\right) \cos (\theta_{u,v}) \right) \\
%	& = {e^{2R- (t_u + t_v)} \over 4} \left(1- \cos (\theta_{u,v}) + \left(1+ \cos (\theta_{u,v}) \right) 
%	\left( e^{-2(R-t_u)} +  e^{-2(R-t_v)}\right) + O\left( e^{-2(2R- (t_u + t_v))}\right)\right) 
%	\end{split}
%	\end{equation}
%	Therefore,
%	\begin{equation*}
%	\begin{split}
%    \cosh &(d(u,v)) \leq \\
%	&  {e^{2R- (t_u + t_v)} \over 4} \left(1- \cos (\theta_{u,v}) + 2 
%	\left( e^{-2(R-t_u)} +  e^{-2(R-t_v)}\right)  + O\left( e^{-2(2R- (t_u + t_v))}\right)\right).
%	\end{split}
%	\end{equation*}
%	Since $t_u+t_v < R-c_0$, the last error term is $O(N^{-4})$. 
%	Also, it is a basic trigonometric identity that $1- \cos (\theta_{u,v}) = 2\sin^2 \left( {\theta_{u,v} \over 2} \right)$. The 
%    latter is at most ${\theta_{u,v}^2 \over 2}$. 
%    Therefore, the upper bound on $\theta_{u,v}$ yields:
%    \begin{equation*}  \begin{split}
%      \cosh &(d(u,v)) \leq \\
%      &{e^{2R- (t_u + t_v)} \over 4} \left( {\theta_{u,v}^2 \over 2} + 2 
%	\left( e^{-2(R-t_u)} +  e^{-2(R-t_v)}\right) + O\left( {1\over N^4}\right)\right) \\
%	&\leq {e^{2R- (t_u + t_v)} \over 4} \left( 2(1-\ve)^2 e^{t_u+t_v -R} + 2 
%	\left( e^{-2(R-t_u)} +  e^{-2(R-t_v)}\right) \right) + O\left( 1\right) \\
%	&= (1-\ve)^2{e^{R} \over 2} + {1\over 2}\left(e^{t_u-t_v} + e^{t_v-t_u} \right) + O(1)\\
%	&< (1-\ve)^2{e^{R} \over 2} + \ve{e^{R} \over 2} + O(1) < {e^{R} \over 2}, 
%	\end{split}
%    \end{equation*}  
%    for $N$ sufficiently large and $c_0$ such that $e^{-c_0}<\frac{1}{2}\ve$, since $t_u+t_v < R-c_0$ and $t_u,t_v\geq0$.  This implies 
%    that $t_u-t_v,t_v-t_u<R-c_0$ and, therefore, 
%    ${1\over 2}\left(e^{t_u-t_v} + e^{t_v-t_u}\right)<{1\over 2}\left(e^{R-c_0} + e^{R-c_0}\right)<\ve{e^{R} \over 2}$. 
%    Also, since $\cosh (d(u,v))> {1\over 2} e^{d(u,v)}$, it follows that $d(u,v) < R$. 
%
%    To deduce the second part of the lemma, we consider a lower bound on (\ref{eq:coslaw}) using the lower bound on $\theta_{u,v}$: 
%    \begin{equation} \label{eq:coslawLow} \begin{split} 
%     \cosh (d(u,v)) & \geq   {e^{2R- (t_u + t_v)} \over 4} \left(1- \cos (\theta_{u,v}) \right) +O(1) \\
%     & \geq {e^{2R- (t_u + t_v)} \over 4} \left(1- \cos \left(2(1+\ve){e^{\frac{1}{2}(t_u+t_v-R)}}\right) \right) +O(1). 
%    \end{split}
%    \end{equation}
%    Using again that $1- \cos (\theta_{u,v}) = 2\sin^2 \left( {\theta_{u,v} \over 2} \right)$ we deduce that 
%    $$ 1- \cos \left( 2(1+\ve)e^{\frac{1}{2}(t_u+t_v-R)}\right)  = 2 \sin^2 \left( (1+\ve)e^{\frac{1}{2}(t_u+t_v-R)} \right).$$
%    Since $t_u+t_v < R - c_0$, it follows that $R-t_u-t_v > c_0$. 
%    So the latter is 
%    \[ \begin{split}2 \sin^2  & \left( (1+\ve)e^{\frac{1}{2}(t_u+t_v-R)} \right)> 2\left(1+{\ve\over 2}\right)^2e^{t_u+t_v-R},
%    \end{split}\]
%     for $N$ and $c_0$ large enough, using the Taylor's expansion of the sine function around $0$.
%     Substituting this bound into (\ref{eq:coslawLow}) we have 
%     $$ \cosh ( d(u,v))  \geq \left(1+{\ve \over 2}\right)^2 {e^{R} \over 2} + O(1).$$
%     Thus, if $d(u,v) \leq R$, the left-hand side would be smaller than the right-hand side which would lead to a contradiction. 
%	\end{proof}
	
	
%	The following lemma is of a great importance for the whole paper as it allows us to change the types of a vertex to get different bounds.
%	\begin{lemma}\label{lem:changeTypeTube}
%		Let $u_1$ and $u_2$ be vertices of types $t_{u_1}<t_{u_2}$, respectively.
%		Then the inner tube of $u_1$ is contained in the inner tube of $u_2$ and the outer tube of $u_1$ is contained in the outer tube of $u_2$.
%	\end{lemma}
%	\begin{proof}
%		For type $t$, the inner tubes cover angles of $4(1-2\ve)\exp\left(\frac{}{2}(t+t_{u_1}-R)\right)$ for $u_1$ and
%		$4(1-2\ve)\exp\left(\frac{}{2}(t+t_{u_2}-R)\right)$ for $u_2$.
%		As $t_{u_1}<t_{u_2}$ and the lines of the inner tubes corresponding to type $t$ have the same midpoint for $u_1$ and $u_2$
%		(as the relative angle is zero), every point of type $t$ in the inner tube around $u_1$ is also contained in the inner tube around $u_2$.
%		The same holds for the outer tubes.
%	\end{proof}
%	The way we will use this is that every point in the inner tube of $u_1$ is of distance at most $R$ of $u_2$ and every point of distance at most $R$
%	of $u_1$ is in the outer tube of $u_2$.
	

  
%	It is not hard to see that when $t_u \leq R/2$ (and indeed for $t_u < \lambda R$, where
%	$\lambda < 1$), then this density can be approximated by an exponential density. 
%	\begin{claim} \label{clm:density_approx} If $u$ is a vertex, then uniformly for any $t_u < R/2$  we have 
%	$$\bar{\rho}_N (t_u) = \alpha e^{-\alpha t_u} (1-o(1)). $$
%	\end{claim}
%	


\section{Theorem~\ref{thm:main}: the subcritical case} \label{sec:subcritical}

	To show the first part of Theorem~\ref{thm:main}, we construct a process that exposes the angle that the component of a given 
  vertex $v$ covers.
  We already discussed that vertices that are close to the centre have a higher expected degree than those close to the periphery.
  The connectivity in a hyperbolic random geometric graph highly depends on the structure of the sub-graph that is 
  induced by vertices of high type. When $\alpha >\frac{1}{2}$, the types of all vertices of $\Gnan$ are bounded away from $R$ a.a.s. 
	This is made precise in the following lemma. 
	\begin{lemma}\label{lem:innerEmpty}
		Let $\omega:\mathbb{N}\rightarrow\mathbb{N}$ be an increasing function such that $\omega (N) \rightarrow\infty$ as $N\rightarrow\infty$.
		With probability $1-o(1)$ all vertices in $V_N$ have type at most $\frac{1}{2\alpha}R+\omega(N)$.
	\end{lemma}
	The proof of this lemma can be found in~\cite{Fount13+} (Corollary 2.2). 
	Thus, it suffices to consider vertices of type no larger than this bound.
	%In the following we will condition on this event so that the disc of radius $R-\frac{1}{2\alpha}R-\omega(N)$ is empty. 
	Note that all vertices have type smaller than and asymptotically bounded away from $R/2$, since $\alpha>1$.
	We will consider a vertex $u$ of type $\frac{1}{2\alpha}R+\omega(N)$ and analyse a \textit{breadth exploration process},
	through which we will bound the \textit{total angle} of the component which contains $u$:
	if $C(u)$ denotes the connected component $u$ belongs to, we define
	$$\Theta(u):= \max \left\{\theta_{u,v} \ : \ v \in C(u) \right\}. $$
  This quantity represents the ``width" of the component $u$ belongs to from the point of view of $u$ itself. 
  When working with this we generally need to double it as it only considers the direction of maximum extent but we need to take both into account.
	%This quantity can be at most $\pi$, although a component that spans the whole disc should intuitively may ``cover" a total angle of $2\pi$.
	%This is of course only a problem for large angles.
	%In fact, if the total angle is less than $2\pi/3$ the definition works.
%	Our aim is to show that components are sub-linearly small, so we will deal with angles that are very small and 
%    the definition serves our purposes.
% 	Our bound for the total angle of the component of any vertex is given by the following lemma.
% 	The total angle of the component will later help us bound the actual size of the the component in terms of vertices using the distribution of angles.
% 	\begin{lemma}\label{lem:area}
% 		Let $v \in V_N$ be a vertex having $t_v = \frac{1}{2\alpha} R + \omega (N)$. Then with probability 
% 		$1 - o\left( \frac{1}{N^{1/\alpha}}\right)$ we have 
% 		$$\Theta(v) \leq C' \frac{R^2 N^{1/\alpha}}{ N}, $$
% 		where $C'= C'(\alpha, \nu)>0$. 
% 	\end{lemma}
	Let $0\leq\theta_c(u,v)<2\pi$ be the angle between the points $u$ and $v$, in clockwise direction from the point $u$.
	We define a \textit{bounding path}, which is a path on $\D$ that is not crossed by any edge.
	The length of a bounding path essentially bounds the number of vertices of the component in which it is rooted. 
	In particular, if a bounding path induces a partition of $\D$ into two parts, one of which covers an angle of at most $o(1)$, then a.a.s. any component in this part
	will be of sublinear size.
	%To see why the breadth exploration process gives an upper bound on the angle of the component we define the following notion of a
	%\textit{bounding path}:
	\begin{definition}
		We call a series of points $P=(p_1,p_2,\dots,p_m)$ in $\D$ a \textit{bounding path} for $\Gnan$, if the following hold:
		\begin{itemize}
			\item[(i)] The points $p_1$ and $p_m$ are on the boundary of $\D$, i.e. their radius is $R$. Also, $\theta_{p_1,p_2}=\theta_{p_{m-1},p_m}=0$.
			\item[(ii)] %If $\theta_c(p_i,p_j)$ is the clockwise angle from $p_i$ to $p_j$
				%then $\theta_c(p_1,p_2)<\theta_c(p_1,p_3)<\dots<\theta_c(p_1,p_{m-1})$.
				For even $i$, we have $\theta_c(p_1,p_i)<\theta_c(p_1,p_{i+1})$ and $t_{p_i}=t_{p_{i+1}}$, while for odd $i$ we have
				$\theta_c(p_1,p_i)=\theta_c(p_1,p_{i+1})$ and $t_{p_i}\neq t_{p_{i+1}}$.
%    			We have $\theta_c(p_1,p_i)<\theta_c(p_1,p_{i+1})$ for even $i$ and $\theta_c(p_1,p_i)<\theta_c(p_1,p_{i+1})$ for odd $i$.
			\item[(iii)] Let $A\cup B$ be the partition of $\D$ incurred by $P$, using radial lines to connect vertices that only differ in type and
				arcs to connect vertices that only differ in angle. Let $B$ be the part containing the origin
				and let $A$ contain all points on the connections.
				There is no pair of adjacent vertices $a\in A$ and $b\in B$ in $\Gnan$.
		\end{itemize}
	\end{definition}
	Note that (ii) ensures that $P$ does not cross itself, so it does partition the disk into two parts and (iii) makes sense.
	Also, for $1<i<m$ and any vertex $v$ with $\theta_{v,p_i}=0$ and $t_v<t_{p_i}$, the component of $\Gnan$ that $v$ belongs to
	covers an angle of at most $\theta_c(p_1,p_m)$.


    We will now proceed with the definition of  the \textit{breadth exploration process} that we will use to get a short bounding path.
	%Let $\lambda=\frac{1}{2\alpha-1}$.
	Note that $\frac{1}{2\alpha-1}<1$ as $1<2\alpha-1\Leftrightarrow\alpha>1$.
	We choose $\ve >0$ small enough so that ${1\over \lambda} := 2\alpha - 1 - \ve >1$.
	Throughout this section we will need several small constants $\ve$.
	We will assume that we choose one $\ve$ for all these and require $N$ to be large enough to satisfy everything.
	Given some constant $C>0$, let $i_0$ be the minimum $i$ such that $\lambda^i\left(\frac{1}{2\alpha}R+\omega(N)\right)<C$.
	Note that $C_\lambda:=\lambda^{i_0}\left(\frac{1}{2\alpha}R+\omega(N)\right)\geq \lambda C$.
	We partition the disk $\D$ into three bands:
	\begin{align*}
		\B_0=&\{v\in\D:\frac{1}{2\alpha}R+\omega(N)<t_v\leq R\}\\
		\B_{C_\lambda}=&\{v\in\D:C_\lambda<t_v\leq\frac{1}{2\alpha}R+\omega(N)\}\\
		\B_-=&\{v\in\D:0\leq t_v\leq C_\lambda\}
	\end{align*}
	By Lemma~\ref{lem:innerEmpty} a.a.s. $\B_0$ does not contain any vertices.
	We define two phases for our random process, one on $\B_{C_\lambda}$ and one on $\B_-$.
	We start the process from a point $u\in\D$ with $0<t_u\leq\frac{1}{2\alpha}R+\omega(N)$; in fact, 
    due to Lemma~\ref{lem:changeType} we may assume that
	$t_u=\frac{1}{2\alpha}R+\omega(N)$.
	\begin{description}
		\item[Phase I] 
		
		\noindent
		Letting $t_i:=\lambda^{i}\left(\frac{1}{2\alpha}R+\omega(N)\right)$, 
			we partition $\B_{C_\lambda}$ into $i_0$ bands
			\[\B_{C_\lambda}^{(i)}=\left\{v\in\D: t_i <
				t_v\leq t_{i-1} \right\}\]
			
			We know that there exists $i_u\in\{1,\dots,i_0\}$ such that $u\in\B_{C_\lambda}^{(i_u)}$.
			We consider the \emph{domain of attraction} around $u$:
			\[\A_u:=T_u^+\cap\B_{C_\lambda}=\left\{v:\theta_{u,v}\leq2(1+\ve)\nu\frac{e^{\frac{1}{2}(t_u+t_v)}}{N},v\in\B_{C_\lambda}\right\}\]
			and for $i=1,\dots,i_0$ we let $\A_u^{(i)}$ denote the set of points in $\A_u\cap\B_{C_\lambda}^{(i)}$ that 
			are in the clockwise direction from $u$. 
			
			By Lemma~\ref{lem:relAngle}, the domain of attraction $\A_u^{(i)}$ contains all points of the band 
            $\B_{C_\lambda}^{(i)}$ that are within distance $R$ in clockwise direction of the point $u$,
						but not every point in $\A_u^{(i)}$ must necessarily be within distance $R$ of $u$.
			We define the first phase of the breadth exploration process in the clockwise direction started at $u$ as follows.
			Note that the auxiliary points defined in the process do not necessarily (in fact, with probability $1$ they do not) correspond to vertices of the graph.
			
			\begin{enumerate}
			\item[1.] $v:=u$ and $\Theta':=0$; let $i_v$ be such that $v \in \B_{C_\lambda}^{(i_v)}$;
			\item[2.] let $j_0$ be the smallest $i$ such that $\A_{v}^{(i)}$ contains a vertex; 
             
			\noindent
             if such an index does not exist, then go to Phase II; 
			
			\noindent
             if $j_0 \leq i_v$, the goto Step 5;
             (we then say that a \emph{backward jump} occurs)
			\item[3.] let $\hat{\Theta}_1:=2\nu (1+\ve)\frac{e^{1/2(t_v+t_{j_0-1})}}{N}$.
			Let $w$ be the point of polar coordinates $(R-t_{j_0-1},\theta_v-\hat{\Theta}_1)$.
			%that has type $t_{j_0-1}$ and relative angle $\hat{\Theta}_1$ with respect to $u_0$ in the clockwise direction; 
            \item[4.] go to Step 2, setting $v:=w$ and $\Theta^\prime:=\Theta^\prime+\hat\Theta_1$;
		     %until we reach a point $u_j$ where $\A_{u_j}^{(i)}$ is empty for every $i$.
		     
		    \item[5.] let $v'$ be the point of polar coordinates $(R-t_0,\theta_v-2\nu (1+\ve) \frac{e^{\frac{1}{2}(t_v + t_0)}}{N})$;
				%of type $t_0$ and relative angle $2\nu (1+\ve) {e^{{1 \over 2}(t_{u_0} + t_0)}\over N}$ with
		      %respect to $u_0$ in the clockwise direction;
					set $v :=v'$;  
   
		     \end{enumerate}
		\item[Phase II]
		\noindent
		\begin{enumerate}
			\item[1.] let $v$ and $\Theta'$ have their final values after the execution of Phase I;
			\item[2.] let $w \in \D$ be the point of type $C_\lambda$ and 
               $\theta_{v,w} = 2\nu (1+\ve )\frac{e^{1/2(t_{v}+C_\lambda)}}{N}$ in the clockwise direction;
		    \item[3.] set $\Theta^\prime:=\Theta^\prime+2\nu (1+\ve )~\frac{e^{1/2(t_v+C_\lambda)}}{N}$ and 
			let $T_w^+$ be the half-tube containing every point $u$ that has relative angle at most 
                     $2\nu (1+\ve )~\frac{e^{1/2(t_{u}+C_\lambda)}}{N}$ with $w$ in clockwise direction; 
			\item[4.] if $T_w^+$ is empty, then exit; 
            
			\noindent 
            else start the process again from Step 2 of Phase I with  $\Theta^\prime:=\Theta^\prime+2\nu (1+\ve )~\frac{e^{1/2(t_0+C_\lambda)}}{N}$
						and $v$ of polar coordinates $(R-t_0,\theta_w-2\nu (1+\ve )~\frac{e^{1/2(t_0+C_\lambda)}}{N})$.
						%,$u_0:=v^\prime$ of type $t_{v^\prime}=t_0$ and  relative angle $2\nu (1+\ve )~\frac{e^{1/2(t_0+C_\lambda)}}{N}$ with respect to $w$.
			\end{enumerate}
	\end{description}
    Note that this process does not involve any points of type higher than $t_0$. Indeed, this is not necessary as by  
    Lemma~\ref{lem:innerEmpty} a.a.s. all vertices in $\V$ have types no more than $t_0$. 
    
    We call a single execution of Steps 2-4 of Phase I a \emph{round}. A maximal series of consecutive rounds is called a \emph{cycle}. 
    Thus, if at the end of a cycle a backward jump occurs, then Phase I proceeds to Step 5, initiating a cycle starting at a 
    point of type $t_0$. This ensures that no matter where the backward jump takes place, vertices that are within distance $R$ from 
    the new root will be covered. 
    
    The set of rounds up to the end of Phase II is called an \emph{epoch}. Hence, an epoch consists of repeated cycles, whose 
    repetitions stop with an execution of Phase II. The \emph{breadth exploration process} starting at a vertex/point $u$ is the process 
    consisting of repeated epochs with the initial root $v$ being the point of type $t_0$ and relative angle with respect to $u$ that is equal 
    to 0.  (Thus, in fact, the process does not start from $u$ but at the ``image" of $u$ that has type $t_0$.)
    
    Recall that $\Theta(u)$ is the maximum relative angle between any two vertices in the component that contains $u$.
		We prove the following lemma:
    
    \begin{lemma} \label{lem:angle_component_u} 
    For any vertex $u \in \V$ of type less than $t_0$, if $\Theta'$ denotes the maximum of the angles gained during the breadth exploration
    process started at $u$ in the clockwise and the anticlockwise direction, then $\Theta (u) \leq 2\cdot\Theta'$.
    \end{lemma}
    \begin{proof}
    Using the breadth exploration process in the clockwise direction, we get a series of root points - these are the vertices in the beginning 
of Phase I.
    Let $u_1,\dots,u_m$ be the part of this series that corresponds to the last cycle,
    i.e. there was a backwards jump before $u_1$ and there is no more backwards jump from there on.
    Let $\hat{u}_i$ be the radial projection of the point $u_i$ to type $t_{u_{i+1}}$.
    The series $u_1,\hat{u}_1,u_2,\hat{u}_2,\dots,\hat{u}_{m-1},u_m$ thus always alters between changing the type and relative angle,
    as required in condition (ii). 
    Similarly, in anticlockwise direction, we get the series
    $u_1^{\prime},\hat{u}_1^{\prime},u_2^{\prime},\hat{u}_2^{\prime},\dots,\hat{u}_{\ell-1}^{\prime},u_\ell^{\prime}$.
    Letting $\hat{u}_m$ and $\hat{u}_\ell^{\prime}$ be the radial projections of $u_{m}$ and $u_\ell^{\prime}$ to the boundary of 
  $\D$, we get the path $P=(\hat{u}_{\ell}^{\prime},u_{\ell}^{\prime},\hat{u}_{\ell-1}^{\prime},\dots,u_1^{\prime},u_1,\dots,\hat{u}_{m-1},u_m,\hat{u}_m)$.
    If the breadth exploration process only uses a total angle that is $o(1)$, which is the case a.a.s., then (i) and (ii) are naturally true
    if $u_1\neq u_1^\prime$. If $u_1=u_1^\prime$ (implying $u_1=u=u_1^\prime$), almost surely (with probability $1$) we can push $u_1$ in clockwise
    direction by some small amount to fix this problem without causing further problems elsewhere (i.e. all the adjacencies of $u_1$ stay the same).
    
    To prove that $P$ is a bounding path for $\Gnan$ we need to show that there is no pair of vertices $(v,w)$ such that $v\in A$,
    $w\in B$ and $v\sim w$.
    Assume for a contradiction that there is such an edge $vw$.
    Without loss of generality we only consider the series $P_1=(u_1,\hat{u}_1,u_2,\hat{u}_2,\dots,\hat{u}_{m-1},u_m)$.
    If $\theta_c(p_1,w)\leq\theta_c(p_1,u_m)$, then there are two consecutive root points, $u_i$ and $u_{i+1}$ such that
    $\theta_c(p_1,u_i)<\theta_c(p_1,w)\leq\theta_c(p_1,u_{i+1})$.
    By Lemma \ref{lem:changeType} and since $t_{u_{i+1}}<t_w$, we have $d(u_i,w)<d(u_i,u_{i+1})\leq R$, a contradiction to the choice of $u_{i+1}$
    as the next root vertex.
%    Note that this covers all cases where $w\in A$, as $w\in A\Rightarrow \theta_c(p_1,w)\leq\theta_c(p_1,p_m)$
    
    Now assume that $\theta_c(p_1,w)>\theta_c(p_1,u_m)$.
    %, then there are two consecutive points, $u_i$ and $\hat{u}_{i}$ such that the lines $u_i\hat{u}_i$ and $vw$
    %intersect or two consecutive points $\hat{u}_i$ and $u_{i+1}$ such that the arc $\hat{u}_i u_{i+1}$ intersects the line $vw$.
    By Lemma \ref{lem:changeType} and as $v\in A$, there is an $i\geq 1$ such that
    $\theta_c(p_1,\hat{u}_{i-1})<\theta_c(p_1,v)\leq\theta_c(p_1,u_i)$(where, for convenience, $\hat{u}_0=u^\prime$).
    But as $v\in A$, we have $t_v\leq t_{u_i}$, so by Lemma \ref{lem:changeType} and the fact that decreasing angles decreases the distance
    we have that $u_i$ is adjacent to $w$.
    By the choice of $u_{i+1}$ in the breadth exploration process, we thus have $\theta_c(p_1,w)\leq\theta_c(p_1,u_{i+1})\leq\theta_c(p_1,u_m)$
    and $t_w<t_{u_{i+1}}$, so $w\in A$, a contradiction.
    Note that $i<m$ since as $u_i$ is adjacent to $w$ the breadth exploration process cannot have stopped at $u_i$.
%    
%     There always is a choice of two vertices such that $t_{u_i}>t_{u_{i+1}}$, so we can assume this is the case.
%    If $t_v<t_{u_{i+1}}$ we must have $t_w>t_{u_{i+1}}$.
%    Since $\theta_c(p_1,w)>\theta_c(p_1,p_m)$ by Lemma \ref{lem:changeType} $d(u_{i+1},w)<d(v,w)=R$ so in the breadth exploration process a backwards
%    jump has to happen.
%    But then this jump goes far enough to include $w$, so $v$ and $w$ are on the same side of the path, a contradiction.
%    So assume $t_v>t_{u_{i+1}}$.
%    If $\theta_c(p_1,u_i)<\theta_c(p_1,v)<\theta_c(p_1,u_{i+1})$, as $d(u_i,v)<R$ must then hold, $u_{i+1}$ was not the choice the algorithm
%    would have made.
%    Lastly, consider $\theta_c(p_1,v)<\theta_c(p_1,u_i)$.
%    Let $j$ be minimal such that $\theta_c(p_1,v)<\theta_c(p_1,u_j)$.
%    Then $t_{u_j}>t_v$ by the choice of the process, so by Lemma \ref{lem:changeType} $d(u_j,w)<d(v,w)\leq R$.
%    But then the algorithm chooses $u_{j+1}$ such that $t_{u_{j+1}}>t_w$ and $\theta_c(p_1,w)<\theta_c(p_1,u_{j+1})$.
%    Then $v$ and $w$ are both on the same side of the path, a contradiction.
    
    So using the breadth exploration process twice we indeed find a bounding path.
    In particular, the angle gained in both direction gives a slice of the disk that contains the entire component of $u$.
		\end{proof}
    We now want to bound from above the angle that can be gained during the execution of the process.
    Note that increasing the type of a vertex $u$ will keep intact all the edges incident to $u$.
    Thus if $u'$ is a vertex replacing $u$, of type $t_{u'}>t_u$ and with relative angle $0$ to $u$, we have $\Theta(u')\geq\Theta(u)$.
    This justifies the choice of the type in the following lemma.  
%    
%    When Phase I finishes (note that this occurs during Step 2), this implies that there are no vertices of type at least 
%    $C_\lambda$ within an angle with respect to the last root point which covers vertices within distance $R$ from it. 
%    
%    However, there may be vertices of type smaller than $C_{\lambda}$ that are within distance $R$ from it. 
%    Their existence is controlled during Phase II. If $u_0$ is the root vertex at the end of Phase I, then 
%    Step 3 of Phase II will add $2\nu (1+\ve )~\frac{e^{1/2(t_{u_0}+C_\lambda)}}{N}$ to $\Theta'$ and 
%    consider the point $v$ which has the above additive factor as its relative angle with respect to 
%    $u_0$ in the clockwise direction. By the second part of Lemma~\ref{lem:relAngle}, the area between $u_0$ and $v$ 
%    contains all points  (and, therefore, all vertices) of type less than $C_{\lambda}$ that are within distance $R$ from $u_0$. 
%    Thereafter, the half-tube consisting of every point $u$ that has relative angle at most 
%    $2\nu (1+\ve )~\frac{e^{1/2(t_{u}+C_\lambda)}}{N}$ with $v$ in clockwise direction is considered. If this is empty of vertices, 
%    then, again by the second part of Lemma~\ref{lem:relAngle}, there are no vertices within distance $R$ from the vertices of 
%    type less than $C_{\lambda}$ which are adjacent to $u_0$. If this is not empty, then 
%    the root $u_0$ is initialised to the point of type $t_0$ which has relative angle 0 with respect to $v$, and Phase I starts again (from Step 2).  
%    Setting the type of $u_0$ equal to $t_0$ ensures that the part of the component consisting of vertices of adjacent to $v$ and type 
%    at least $C_\lambda$ is entirely covered. 
    
%    The above process is an exploration only in the clockwise direction and, hence, it is repeated in the anticlockwise direction.	
    
%      
% 	This process yields an upper bound on the area the component which a vertex $u$ belongs to can occupy.
% 	The way this is achieved is by finding an empty \textit{belt} around the component.
% 	This is an area not containing any vertices and surrounding some area containing $u$ such that any point inside the area containing
% 	$u$ has distance bigger than $R$ to any vertex outside the belt and area containing $u$.
% 	Thus the whole component containing the vertex $u$ must be inside the area surrounded by the belt.
%    We now state the following lemma whose proof can be found in Section~\ref{app:subcritical}.
%		The following Lemma bounds the angle gained during the breadth exploration process.
	\begin{lemma}\label{lem:probPhases}
		%Let $\omega^\prime(N):\N\rightarrow\R$ be such that $\omega^\prime(N)\rightarrow\infty$ as $N\rightarrow\infty$.
		Let $u \in \D$ be a point having $t_u = t_0$.
	  If the breadth exploration process starts at point $u$, then by the end of it $\Theta' \leq R^2 \log^3 R N^{1 / \alpha -1}$ with 
	  probability $1- o\left( N^{1/ \alpha - 1}\right)$
% 		There exists a constant $C=C(\ve)>0$ such that with probability at least $1-\ve^{\omega^\prime(N)}$ Phase I of the breadth exploration
% 		process started at $v$ and with constant $C$ jumps backwards at most $\omega^\prime(N)$ times.
% 		Furthermore, there exists a $\delta=\delta(C)>0$ such that the probability to end Phase II is at least $\delta$.
	\end{lemma}
	\begin{proof}
	Let us consider the breadth exploration process started at a vertex $u$ having type $t_0={1 \over 2\alpha}R + \omega (N)$. 
	For an $\ve >0$ we let $T_{\ve}$ denote the first round at the end of which  $\Theta' \geq \ve$	if there is such a round,
	otherwise $T_{\ve}=\infty$.
	We also denote by $u_0(t)$ the root vertex at the beginning of the $t$th round and let $i_{u_0}\geq 0$ 
  denote the index of the band this vertex belongs to. We will first bound from below the probability that the exploration process 
  does not backtrack during the $t$th round. Let $B_t^{(i_{u_0})}$ be the indicator random variable that is equal to 1 if and only if 
  backtracking \emph{does} occur during the $t$th round assuming that the root vertex is in $i_{u_0}$. 
  
  \begin{claim} \label{clm:prob_no_back} 
	  For $\ve \in (0,2 \pi)$, let $t< T_\ve$. There exists a constant $K = K(\alpha, \nu)>0$ such that for any $N$ that is sufficiently large
		we have 
	  $$\Prb {B_t^{(i_{u_0})} = 0} > \exp \left(- K e^{-{\ve \over 2} t_{i_{u_0}}} \right).$$
  \end{claim}
  \begin{proof}[Proof of Claim~\ref{clm:prob_no_back}]
  Let us write $u_0 = u_0 (t)$. 
  For $t< T_\ve$ we give a stochastic upper bound on 
  the number of vertices that belong to $\cup_{j=0}^{i_{u_0}} \A_{u_0}^{(j)}$. Hence, we will be able to give a lower bound 
  on the probability that this region is empty. In other words, we will bound from below the probability that no backtracking occurs during the
  $t$th round. 
  Let $N_t$ denote the number of vertices that have not been exposed at the beginning of the $t$th round. 
  Using Lemma~\ref{lem:dist}, the probability that one of
  them will belong to $\cup_{j=0}^{i_{u_0}} \A_{u_0}^{(j)}$  is bounded from above by 
  \begin{equation*} 
  \begin{split}
   & {2\nu (1+\eps)  \alpha \over 2\pi - \Theta'} \int_{t_{i_{u_0}}}^{t_{0}} { e^{{1 \over 2}(t_{u_0} + s) } \over N} e^{-\alpha s} ds \leq  
   {2\nu (1+\eps) \alpha \over 2\pi - \ve} \int_{t_{i_{u_0}}}^{t_{0}} { e^{{1 \over 2}(t_{u_0} + s) } \over N} e^{-\alpha s} ds \\
    & \leq {4\nu (1+\eps) \alpha \over (2\pi - \ve)(2\alpha - 1)} {e^{t_{u_0}/2}\over N}~
    e^{(1 /2 - \alpha ) t_{i_{u_0}}} \\
    & \leq {4\nu (1+\eps) \alpha \over (2\pi - \ve)(2\alpha - 1)} {e^{{1 \over 2} ( t_{i_{u_0} - 1} + t_{i_{u_0}}) - 
    \alpha t_{i_{u_0}} }\over N} =:p_{t}^{(i_{u_0})}.
   \end{split}
   \end{equation*}
   
	 Hence, the number of vertices which during round $t$ will fall into $\cup_{j=0}^{i_{u_0}} \A_{u_0}^{(j)}$ is binomially distributed 
	 with parameters $N_t, p_t^{(i_{u_0})}$. In turn, this is stochastically bounded from above by a binomially distributed random variable 
	 with parameters $N, p_t^{(i_{u_0})}$.  Note also that if the number of vertices that 
	 fall into $\cup_{j=0}^{i_{u_0}} \A_{u_0}^{(j)}$ is positive, then backtracking occurs. Hence, the probability of backtracking during 
	 round $t$ is at least $\Prb {\Bin (N, p_t^{(i_{u_0})}) =0}$.

   Recall that $t_{i_{u_0} -1} = {1\over \lambda}t_{i_{u_0}}= \left(2\alpha - 1 - \ve \right) t_{i_{u_0}}$, whereby
	 \[ \begin{split}
      {1 \over 2} ( t_{i_{u_0} - 1} + t_{i_{u_0}}) &= {1 \over 2} \left( 2\alpha - 1 - \ve +1 \right) t_{i_{u_0}}
     ={1 \over 2} \left( 2\alpha - 1 - \ve +1  \right)t_{i_{u_0}} \\
     &= \left(- {\ve \over 2} + \alpha \right) t_{i_{u_0}}. 
     \end{split}
     \]
     This shows that $p_{t}^{(i_{u_0})}=O(\frac1N)$, justifying the following exponential approximation.

     Setting $K'={4\nu (1+\eps) \alpha \over (2\pi - \ve)(2\alpha - 1)}$, we obtain an asymptotic estimate on the probability of backtracking: 
	 \begin{equation*}
	 \begin{split} 
	  & \Prb  {\Bin (N, p_t^{(i_{u_0})}) =0} = \left( 1- p_{t}^{(i_{u_0})}\right)^{N}\\
      & = \exp \left(- K' e^{{1 \over 2} ( t_{i_{u_0} - 1} + t_{i_{u_0}}) - 
      \alpha t_{i_{u_0}} } (1+o(1)) \right).
	 \end{split}
	 \end{equation*}
	 
     Hence, we obtain
     \begin{equation*}
     \begin{split}
      \Prb  {\Bin (N, p_t^{(i_{u_0})}) =0} &= \left( 1- p_{t}^{(i_{u_0})}\right)^{N} = 
      \exp \left(  -(1+o(1)) K'   e^{- {\ve \over 2} t_{i_{u_0}}}\right)  \\
       & > \exp \left(- 2 K'  e^{-{\ve \over 2} t_{i_{u_0}}} \right),
     \end{split}
     \end{equation*}
     for any $N$ sufficiently large, uniformly over all possible values of $i_{u_0}$. (The latter is the case since always $t_{i_{u_0}}< R/2$.)  
     Taking $K=2K'$, the claim now follows. 
     \end{proof}
     Now, observe that the above claim implies that the probability of no backtracking at a certain round can become very close to 1. 
     Indeed, note that $t_{u_0} \geq \lambda C$ and, therefore, the exponent on the right-hand side of the bound obtained in 
     Claim~\ref{clm:prob_no_back} can be made as close to 0 as we want, provided we choose $C$ large enough. Moreover, 
     if $t_{u_0}$ is bounded from below by a function of $N$ that increases as $N \rightarrow \infty$, then the probability of 
     no backtracking is in fact $1-o(1)$. These observations are key to the deduction of the first part of the lemma. 
    
     We first show that provided that $\Theta'$ is much less than $\eps$, the number of cycles within an epoch is essentially stochastically
     dominated by a geometrically distributed random variable that has probability of success $1-\ve$, provided that the parameter 
     $C = C(\ve)$ is large enough. 
     Suppose that an epoch starts with $\Theta' \leq g(N)$ where $g(N) = o(1)$.  
     
     Recall that a cycle starts at a vertex that has type $t_0={1 \over 2\alpha} R + \omega (N)$. 
     Let $T_{C_\lambda}$ denote the random variable that is the length of a cycle.
     We say that a cycle is \emph{successful} if it exits to Phase II.    
     %Also, let us denote by $i_{\omega (N)}$ the index $i$ such that $\B_{C_{\lambda}}^{(i)}$ contains the vertices of type $\omega (N)$. 
     Note that a cycle is successful, that is, no backtracking occurs, if and only if $B_t^{(i_{u_0})} = 0$, for all $t\leq T_{C_\lambda}$. 
     

     We will bound the probability that, conditional on $\Theta' \leq g(N)$ at the beginning of the epoch, the number of cycles is at least 
     $R$. In particular, we will show that for every $\ve$ there exists a $C$ such that this probability is at most $\eps^{R-1}$.
     
     \begin{claim} \label{clm:length_of_epoch} 
     Let $g(N)=o(1)$.
     For every $\ve >0$ there exists a $C = C(\ve)$ such that for any $N$ sufficiently large, conditional on $\Theta'\leq g(N)$ at 
     the beginning of an epoch, with probability at least $1- \eps^{R-1}$ the total angle gained during the epoch is at most 
     $2R\log^2 R {N^{1/\alpha -1}}$. 
     \end{claim}
     \begin{proof}
     To bound this probability, we will repeatedly apply Claim~\ref{clm:prob_no_back}. However, in order to this we need to ensure that 
     $\Theta'$ does not exceed $\eps$ whenever at most $R$ cycles have been executed. 

     Hence, we first need to give an upper bound on the angle that is gained during the execution of a cycle. 
     If $\Theta'_{T_{C_\lambda}}$ denotes this angle, then
     $$\Theta'_{T_{C}} < 2\nu (1+\ve)  \sum_{i=0}^{i_0} {e^{{1 \over 2}(t_{i} + t_{i+1})}\over N}. $$
     But for all $i$ we have $t_i < {1 \over 2\alpha} R + \omega (N)$.
     Hence, $t_i + t_{i+1} < {1  \over \alpha}~R + 2 \omega (N)$, whereby 
     $$ {e^{{1 \over 2}(t_{i} + t_{i+1})}\over N} < {e^{{1 \over 2}R~{1 \over \alpha} + \omega (N) }\over N} = 
      e^{\omega (N)}~N^{{1 \over \alpha} - 1 }.$$
      Using this with $\omega(N)=\log\log^{\frac12}R$, the above sum can be further bounded from above by 
     \begin{equation} \label{eq:initial_gain} \Theta'_{T_C} < 
       2\nu (1+ \ve) (i_0 + 1)e^{\log\log^{\frac12}R} ~N^{{1 \over \alpha} - 1} 
          \stackrel{i_0 = O(\log R)}{\leq} \log^2 R {N^{1 /\alpha} \over N}, 
     \end{equation}
     if $N$ is large enough. 
     Therefore, after $r\leq R$ cycles the angle gained will be at most $ R\log^2 R {N^{1 /\alpha} \over N}< \ve$, 
     for any $N$ that is sufficiently large. Note also that this quantity bounds the total angle that is gained during an epoch 
     consisting of at most $R$ cycles. 
     
     Hence, applying Bayes' rule repeatedly, Claim~\ref{clm:prob_no_back} implies that 
     \begin{equation} \label{eq:prob_back_heavy} \Prb {B_t^{(i_{u_0})} = 0, \ \forall t< T_{C_{\lambda}}}  
      %\geq \prod_{i=0}^{i_0} \Prb { B_i^{(i)} =0 \mid \Theta' < \eps}
     \geq  
     \prod_{i=0}^{i_0} 
     \exp \left(- K e^{-{\ve \over 2} t_i} \right). \end{equation}
     Let $a_i : = e^{-{\ve \over 2} t_i}$ and note that since $t_i = \lambda^i t_0$ we have for $i \leq i_0$
     \[ \begin{split} {a_{i-1} \over a_i} &= e^{-{\ve \over 2} t_0 \left( \lambda^{i-1} - \lambda^i \right)} 
       = e^{-{\ve \over 2} t_0 \lambda^i \left( {1 \over \lambda} - 1 \right)} \leq 
       e^{-{\ve \over 2} t_0 \lambda^{i_0} \left( {1 \over \lambda} - 1 \right)} \\ 
     & \leq e^{-{\ve \over 2} \lambda C \left( {1 \over \lambda} - 1 \right)}.  
\end{split} \]
     Thus, if $C$ is large enough, then
     \[ \begin{split}
        \sum_{i=0}^{i_0} e^{- {\ve \over 2} t_i} &<  e^{-{\ve \over 2} t_{i_0}} 
         \sum_{i=0}^{\infty} e^{-{\ve \over 2} i\cdot C\left( 1  - \lambda \right)} \stackrel{t_{i_0}> \lambda C}{<} 
          2 e^{-{\ve \over 2} \lambda C}.  
        \end{split}\]
      Substituting this bound into the right-hand side of (\ref{eq:prob_back_heavy}) we obtain
    \begin{equation} \label{eq:prob_back_heavy_I} 
       \Prb {B_t^{(i_{u_0})} = 0, \ \forall t\leq  T_{C_\lambda}} \geq    \exp \left(-2K e^{-{\ve \over 2} \lambda C}\right) > 
       1- 2K e^{-{\ve \over 2} \lambda C} > 1 - \ve,
    \end{equation} 
    choosing $C$ large enough so that the last inequality holds. 
    Hence, the probability that backtracking occurs before $T_{C_\lambda}$ is at most $\ve$, for $C = C(\ve)$ that is sufficiently large. 
    In other words, the probability that the cycle is not successful conditional on $\Theta' \leq g(N)$ at the beginning of the epoch 
    is at most $\ve$. Therefore, the conditional probability of having $R$ cycles during the epoch is at most $\eps^{R-1}$. 
    
    As we pointed out above the total angle that was gained above during the execution of the $R$ cycles is no more than 
    $R\log^2 R {N^{1 /\alpha -1}}$. During Phase II, the angle gained is at most 
    $$ 4\nu (1+\ve) {e^{{1 \over 2} (t_0 + C_\lambda)}\over N} \leq 4\nu (1+\ve) e^{{1 \over 2}(C_{\lambda} + \omega (N))} 
    {e^{{1 \over 2\alpha}{1 \over 2}R} \over N} = o\left( {N^{{1 \over \alpha}-1}} \right).$$ 
    Hence, an epoch having at most $R$ cycles adds at most $2R\log^2 R {N^{1 /\alpha -1}}$ to $\Theta'$, provided that $N$ is 
    sufficiently large. 
    \end{proof}
    
    Now, we will show that as long as $\Theta'$ has not grown too much, the probability that an epoch is the final one is asymptotically
    bounded away from 0.  To see this, we will bound from above the probability that $T_v^+$, that was defined in Step 3 of Phase II, contains
    at least one vertex conditional on $\Theta' \leq \ve$. 
    In particular, conditional on this, the probability that a given vertex whose exact position in $\D$ has not been exposed yet 
    belongs to $T_v^+$ is at most 
    \[
     \begin{split} 
      {2\nu \alpha (1+ \ve) \over 2\pi - \ve} & \int_0^{t_0} {e^{{1 \over 2}\left( C_\lambda + t \right)}\over N}~e^{-\alpha t} dt > 
      {2\nu \alpha (1+ \ve)  \over 2\pi - \ve} {e^{C_\lambda /2} \over N} \int_0^{\infty} e^{\left({1 \over 2} - \alpha \right)t}dt \\
     &\stackrel{1/\alpha < 2}{=} {4 \nu \alpha (1+\ve) \over (2\alpha - 1) (2\pi - \ve)}~{e^{C_{\lambda} / 2} \over N}=:p_{II}=O(\frac1N).
     \end{split}
     \]
     Under the above conditioning, the number of vertices that belong to $T_v^+$ is stochastically bounded from above by a binomially 
     distributed random variable with parameters $N, p_{II}$ 
     Hence, the probability that $T_v^+$ is empty conditional on $\Theta' \leq \ve$ is at least 
     \[ 
      \begin{split}
      (1-p_{II})^{N} & = \exp \left(- {4 \nu (1+\ve) \over (2\alpha - 1) (2\pi - \ve)}~e^{C_{\lambda} / 2} (1+o(1)) \right)  \\
     &\geq \exp \left(- {4 \nu (1+\ve) \over \pi (2\alpha - 1) }~e^{C_{\lambda} / 2} \right)=:\delta, 
     \end{split}
     \]
     provided that $\ve < \pi$ and $N$ is sufficiently large. %(Note that the above is less than 1 if $C_\lambda$ is large enough.)
     
     Now, we set $E:= \lfloor - {1- 1/\alpha \over \ln \delta}~R \rfloor $. 
     We will finish the proof by showing that the probability that less than $E$ epochs take place each having at most $R$ cycles is 
     $1-o\left( N^{1 /\alpha -1} \right)$. This together with Claim~\ref{clm:length_of_epoch} imply that with this probability the 
     total angle gained during the process is at most $2E R \log^2 R N^{1/\alpha - 1}$. 
     
     Indeed, the probability of having $E$ epochs each one having at most $R$ cycles is at least 
     \[ 
      \delta^E \geq \delta^{-{1- 1/\alpha \over \ln \delta}~R } = \exp \left((1/\alpha -1)~R \right)=O(N^{2(1/\alpha -1)}),
     \]
     and the latter is $o\left( N^{1 /\alpha -1} \right)$. 
     Also, arguing as in the proof of Claim~\ref{clm:length_of_epoch}, we deduce that the probability that there exists one among the first $E$ 
     cycles having more than $R$ cycles is at most $E\ve^R = o (N^{1 / \alpha -1})$, provided that $\ve$ is chosen small enough. 
    \end{proof}
    
    
    
	The above lemma together with Lemma~\ref{lem:angle_component_u} imply that 
	\begin{lemma} \label{lem:individual_angle} 
    For any $u \in \V$ we have $\Theta (u) \leq R^2 \log^3 R N^{1/ \alpha - 1}$ with probability 
    $1- o\left( N^{1/ \alpha - 1} \right)$. 
	\end{lemma}
% 	(The factor 2 comes from the fact that the breadth exploration process takes place only in the clockwise direction - 
%      hence we need to multiply by 2 in order to take into account the growth of the component of vertex $u$ in the counterclockwise 
%     direction.) 
    We will now deduce the first part of Theorem~\ref{thm:main} from Lemma~\ref{lem:individual_angle}. 
	Let $\B$ denote the set of vertices $u$ for which $\Theta (u) > 2 R^2 \log^3 R N^{1 /\alpha -1}$ - we call 
	these vertices \emph{bad}. Thus, Lemma~\ref{lem:individual_angle} implies that 
	$$ \mathbb{E} \left[|\B |\right] = o (N^{1/ \alpha}).  $$
	Markov's inequality in turn implies that for any $\delta > 0$ we have that with probability $1-o(1)$
	\begin{equation} \label{eq:bad_bound} 
	|\B | < \delta N^{1/\alpha}. 
	\end{equation}
	\noindent
	Assume now that $\G (N;\alpha,\nu)$ has a component $C$ of order greater than $8R^2 \log^3 R  N^{1/\alpha}$. 
	Hence, on the event (\ref{eq:bad_bound}), there is at least one (in fact, many) vertex $u \in C$ in this component that is \emph{not} bad. 
	
	A \emph{sector} of $\D$ is the area between two radii of $\D$ of relative angle which is less than $\pi$ - we call this angle the 
    \emph{angle of the sector}. Hence, since $u$ is not bad, it turns 
    out that there is a sector  of angle at most $2 R^2 \log^3 R N^{1/\alpha-1}$ which contains at least 
    $4 R^2 \log^3 R N^{1/\alpha}$ vertices
    (in fact, our assumption implies that it contains almost twice as many vertices as this). 
    But the next lemma shows that this is not the case with probability $1-o(1)$ and the first part of Theorem~\ref{thm:main} follows. 
    \begin{lemma} \label{lem:dense_sectors}
    Let $\theta: \mathbb{N}  \rightarrow \R$ be a non-negative function such that $\theta (N) = o(1)$ but ${N\theta(N)\over \ln (1/\theta (N))} \rightarrow \infty$ 
    as $N\rightarrow \infty$. Then a.a.s. there is no sector of angle $\theta (N)$ that contains at least $2N\theta (N)$ vertices. 
    \end{lemma}
    	\begin{proof} 
	Consider a partition $\mathcal{P}$ of $\D$ into $2\pi / \theta (N)$ sectors of angle $\theta (N)$. If $\D$ contains a sector as in the
    statement of the lemma, then one of the sectors in $\mathcal{P}$ must contain at least $N\theta (N)$ vertices. Now, note that the 
    number of vertices is a sector $\sigma \in \mathcal{P}$, which we denote by $N_s$, is binomially distributed with parameters $N$ and 
    $\theta (N)/2\pi$. 
	Hence, $\mathbb{E}(N_\sigma) = {1\over 2\pi}~N\theta (N)$ and since $N \theta (N) \rightarrow \infty$ and applying a Chernoff-type bound 
	we deduce that 
	$$\Prb { N_\sigma > N \theta (N)} = \exp \left(- \Omega (N \theta (N)) \right). $$
	Therefore, using Markov's inequality we obtain:
	$$\Prb {\exists~\sigma \in \mathcal{P} \ : \ N_{\sigma} > N \theta (N)} \leq {2\pi \over \theta (N)} 
    \exp \left(- \Omega (N \theta (N)) \right) =o(1), $$
	which concludes the proof of the lemma. 
	\end{proof}
	
\section{Theorem~\ref{thm:main}: the supercritical case} \label{sec:supercritical}
In this section, we will show the second part of Theorem~\ref{thm:main}. Namely, we shall assume that  $\alpha<1$ and with 
    $|L_1|$ denoting the size of a largest component of $\G (N; \alpha, \nu)$, we will show that 
    there exists a $c=c(\alpha,\nu)$ such that a.a.s. $|L_1|>cN$.
	%In what follows, the term ``tube" will be referring to the inner tube (cf. Definition~\ref{def:tubes}).
	
	\subsection{Proof overview}
	We will consider a set of homocentric bands in $\D$.
	The innermost band consists of those vertices of type at least $R/2$. Note that the subgraph of $\G(N;\alpha,\nu)$ that is induced by the 
    vertices which belong to this part of $\D$ is a clique. This follows from the triangle inequality, which implies that the distance between
    any two vertices there is at most $R$. 
	%Starting with this component, we keep track of how many vertices we add in each band to get a lower bound of the vertices in 
    %this component. 
    The remaining bands are determined by a sequence of numbers $t_i$, with $t_0=R/2$ and $t_i$ defined by the following recursion:
	\begin{equation} \label{eq:def_ti}t_i-2\ln\left(\frac{4\pi}{\nu(1-\ve)^4} t_i\right)=\lambda t_{i-1}\text{,}\end{equation}
	if $0<t_i< t_{i-1}$. 
	where now $\lambda:=2\left(\alpha-\frac12\right)$ -- we assume that $\alpha > \frac12$.
    The bands are now as follows:
	\begin{align*}
		\B_0=\{v\in\D:R/2<t_v\leq R\}\ \mbox{and} \ 
		\B_i=\{v\in\D:t_i<t_v\leq t_{i-1}\}\text{.}
	\end{align*}
	We shall assume that $i< T$, where $T=T(\alpha, \nu, \ve)$ and $\ve$ is a positive real number which we will assume to be small 
	enough for the purposes of our calculations. We will determine $T$ in Subsection~\ref{sec:defT}. 
% 	Let $T$ be the largest $i$ such that $e^{-\alpha(t_{i-1}-t_i)}<1/2$ and $t_i>e$.
	Observe that (\ref{eq:def_ti}) implies that provided that $t_i > \nu (1-\ve)^4/(4\pi)$,
	\begin{equation}
		t_i>\lambda^it_0\text{ for }i>0\text{.}
		\label{lowrec}
	\end{equation}
	We denote by $\N_i$ the set of vertices which belong to the $i$th band, for $i\geq 0$, and let $N_i$ denote its size. 
	Furthermore, for $i>0$ we denote by $\N_i'$ the set of vertices in $\B_i$ that have at least one neighbour in $\N_{i-1}'$ -- 
    here we set $\N_{0}' = \N_0$.  We say that these belong to the \emph{active area} of $\mathcal{B}_i$. 
	%By the triangle inequality the distance of any two vertices of $\N_0$ is at most $R/2$, so the graph induced by $\N_0$ is a clique.
	This definition together with the fact that a clique is formed in $\N_0'$ imply that the graph induced by $\bigcup_{i=0}^{T}\N_i'$ is
    connected and contains $\sum_{i=0}^{T} |\N_i'|$ vertices. Our aim is to show that a.a.s. this quantity is linear in $N$. 
    We let $N_i' = |\N_i' |$. 
	

    More specifically, we show that the number of vertices in $\N_i'$ stochastically dominates the number of vertices in a subset of 
    $\B_i$ that has arc $\Theta_i$.
	This makes working with sizes a lot easier, as implications for the size of $\N_i'$ can be deduced from the angle $\Theta_{i-1}$.
	In particular, with probability $1 - o\left( {1\over \ln N} \right)$ 
    \begin{equation} \label{eq:N_i'_hypothesis_clone} N_{i-1}' \geq  N_{i-1} {\Theta_{i-1} \over 2\pi}(1-\ve). \end{equation}
    The proof of this can be found in Section~\ref{sec:Indstep}. 
    Next we argue (cf. Section~\ref{sec:Indstep}) that conditional on $N_{i-1}'$ as above and $\Theta_{i-1}>\pi$ with high probability 
    $\Theta_i$ is at least a certain fraction of $\Theta_{i-1}$. 
    \begin{lemma} \label{lem:Theta_Recursion_clone}
	Conditional on $N_{i-1}\in (1\pm \ve)\mathbb{E} \left[ N_{i-1}\right]$, on $\Theta_{i-1}>\pi$ as well as on $N_{i-1}'$ satisfying 
    (\ref{eq:N_i'_hypothesis_clone}) with probability $1-o\left( {1\over \ln N} \right)$ we have 
	\begin{equation} \label{eq:ThetaRec}\Theta_i \geq \Theta_{i-1} \left( 1- e^{-\gamma t_i}\right), \end{equation}
	for some constant $\gamma = \gamma (\alpha, \nu, \ve)>0$, uniformly for $i=1,\ldots, T$. 
	\end{lemma}
	Note that we take $\Theta_0:=2\pi$.
    % and $\theta^{(i)}:=e^{\frac{1}{2}(t_{i-1}+t_i)}$ (here $t_{-1}:=R$).

	To derive the stochastic domination we will assume that the following conditions hold:
	\begin{itemize}
		\item any vertex of type $t$ with $t_i\geq R/2$ is of type $R/2$;
		\item any vertex of type $t$ with $t_i<t \leq t_{i-1}$ is of type $t_i$.
	\end{itemize}
	Lemma \ref{lem:changeType} ensures that for a vertex $v \in\B_{i-1}$ the area consisting of all points that belong to $\B_i$ and have 
    distance $R$ from $v$ becomes smaller, if the type of $v$ within the bounds of $\B_{i-1}$ decreases. 
    Now, using the first part of Lemma \ref{lem:relAngle}, we can use the inner tubes to obtain a further lower bound on this area.
    In particular, we will consider only vertices that fall within the inner tube of $v \in\N_{i-1}'$ assuming that the type of $v$ is $t_{i-1}$ 
    and deduce a stochastic lower bound on the size of $\N_i'$. 
    
% 	We have discretised the types of the vertices we use.
% 	For each vertex $v$ on one of these bands, using the bounds on the relative angle, we get a region on the next band all vertices
% 	in which are adjacent to $v$.
% 	Given an area all vertices in which belong to our component, we want to extend this component to the next band.
% 	To do this we want to find the area on this next band that is covered by the vertices of our component.
% 	Instead of doing this directly, we find the area that is not covered, the \textit{gaps} and the remainder is covered.
% 	We denote by $\theta^{(i)}$ the lower bound we get using tubes on the angle a vertex of type $t_i$ covers on the band of type $t_{i+1}$.
% 	Then $\theta^{(i)}=2(1-\ve)\exp\left(\frac{1}{2}(t_i+t_{i+1}-R)\right)$.
% 	Note that this makes sense as it is always less than $2\pi$.
%  	Denote by $N_i^\prime$ the number of vertices in a part of $\B_i$ of arc $\Theta_i$.
% 	We radially project the area of angle $\Theta_i$ and its vertices onto type $t_{i+1}$ and find the probability that a point $u$ of 
%     type $t_{i+1}$ that is within this area is not within distance $\theta^(i)$ of one of the projected vertices.
%  	
 	
	
	Using concentration arguments we will show that a.a.s. $N_i'\geq\frac12~N\frac{\Theta_{i}}{2\pi}~
	\left(e^{-\alpha t_{i}}-e^{-\alpha t_{i-1}}\right)$. 
%Note that by (\ref{lowrec}) and (\ref{eq:ThetaRec}) we have 
%%	Using these inequalities and Equation (\ref{lowrec}), we can show that
	%\begin{equation} \label{eq:Theta_Final_Rec}
      %\Theta_i>\Theta_{i-1}\left(1-e^{-\lambda^i t_0}\right).
	%\end{equation}
	Hence, if $T$ is such that \begin{equation}\prod_{i=0}^T\left(1-e^{-\gamma t_i}\right) > {1\over 2}, \end{equation} 
    and for some $C>0$
    \begin{equation} \label{eq:Bound_on_T}
    t_{T} \leq C,
    \end{equation}
    then it will follow by (\ref{eq:ThetaRec}) that  
	\[\sum_{i=0}^T N_i'\geq {1\over 2}~N \left(e^{-\alpha t_T}-e^{-\alpha t_0}\right)\prod_{i=0}^T\left(1-e^{-\gamma t_i}\right)>cN,\]
	for some $c=c(\alpha,\nu)$.
%	In Section~\ref{sec:defT} we show that both conditions are satisfied. Complete details of the proof can be found in 
%    Section~\ref{sec:finalproof}.
\subsection{The definition of $T$} \label{sec:defT}

 Firstly, we will require that $t_i > B_1$ where $B_1= B_1 (\alpha, \nu, \ve) >e$ is large enough so that we have
 \begin{equation}  \label{eq:T_II}
 2 \ln \left( \frac{4\pi}{\nu(1-\ve)^4}  t_i \right) < \left( 1 - \alpha \right) t_i. 
 \end{equation}
 This condition implies that 
 \begin{equation} \label{eq:t_idecay} 
  \begin{split}
 t_i &\leq \lambda t_{i-1} + 2 \ln \left( \frac{4\pi}{\nu(1-\ve)^4} t_i \right) \stackrel{t_i \leq t_{i-1}}{<} 
 \lambda t_{i-1} + 2 \ln \left( \frac{4\pi}{\nu(1-\ve)^4}  t_{i-1} \right) \\ 
&\stackrel{(\ref{eq:T_II})}{<} \left( \lambda + 1 - \alpha \right) t_{i-1} = 
\left( 2\alpha - 1 + 1 - \alpha\right) t_{i-1} = \alpha t_{i-1} < t_{i-1}. 
 \end{split}
 \end{equation}
 
 We use (\ref{eq:t_idecay}) in order to deduce that if $t_i > B_1$, then 
 \begin{equation} \label{eq:exp_decay}
 e^{- \alpha (t_{i-1} - t_i)} < e^{-t_{i-1}\alpha \left(1 - \alpha \right)}. 
 \end{equation}
Given $\ve >0$, let $C = C(\alpha, \nu, \ve) > B_1$ be such that 
\begin{equation} \label{eq:T_C}
\begin{split}
&e^{-C\alpha (1- \alpha)} < \ve, \\
&\frac{\nu(1-\ve)^4}{4\pi} < C,\\
%&{2\over \lambda C} 2 \ln \left( {4 \pi \over \nu (1-\ve)^4} {\lambda C\over 2} \right)< \ve,\\
&\mbox{if}\ \lambda C < t - 2 \ln \left( \frac{4\pi}{\nu (1-\ve )^4} t  \right)=:f(t), \ \mbox{then} \ f(t) <t, \\
& \mbox{for all $t> C$ we have} \ 2 \ln \left( \frac{4\pi}{\nu (1-\ve )^4} t  \right) < \frac{1-\alpha}{2} t, \\
&{e^{-\gamma \lambda C/2} \over 1- e^{-\gamma \left(1- \alpha \right)C}} < {1\over 2},
\end{split}
\end{equation}
where $\gamma = \gamma (\alpha, \ve) >0$ will be specified later. 
Let 
$$T := \min \{ i \ : \  t_i < C \ \mbox{or} \ \Theta_i < \pi\}. $$
Thus, by (\ref{eq:t_idecay}) we deduce that 
\begin{equation} \label{eq:T_log} 
T = O(\log R). 
\end{equation}
Hence, (\ref{eq:exp_decay}) implies that for any $i < T$ we have 
 \begin{equation}  \label{eq:T_1} 
 e^{- \alpha (t_{i-1} - t_i)} \stackrel{t_{i-1} \geq C}{<} \ve. 
 \end{equation}
The definition of $T$ also implies that for $i< T$ 
 $$     t_i > \frac{\nu(1-\ve)^4}{4\pi}, $$
 as required above. 
Recall that this ensures that the second term in the left-hand side of (\ref{eq:def_ti}) is positive as 
 $$ \ln \left( \frac{4\pi}{\nu(1-\ve)^4}  t_i \right) >0, $$ 
and thereby (\ref{lowrec}) holds for all $i < T$. 


Secondly, we will require that 
\begin{equation}\label{eq:Theta_B}\prod_{i=1}^T \left( 1- e^{-\gamma t_i} \right) > {1\over 2}. \end{equation} 
As we shall see in the next section, this will imply that  %(\ref{eq:Theta_Final_Rec}): 
\begin{equation} \label{eq:Theta_i_Recursion} \Theta_i \geq \Theta_0 \prod_{j=1}^{T} \left( 1- e^{- \gamma t_j} \right) > \pi.
\end{equation}
As $\Theta_0 = 2\pi$ we need that the product on the right-hand side of the above  is at least $1/2$. This will be the case 
if 
$$ \sum_{j=1}^{T} e^{-\gamma t_j} < {1\over 2}. $$
To bound the above sum, we will give an upper bound on the difference of $t_j-t_{j-1}$. We have 
\[
\begin{split}
t_j &- t_{j-1} \stackrel{(\ref{eq:t_idecay})}{<} (\alpha -1) t_{j-1} \stackrel{t_{j-1}>C, \alpha < 1}{<} (\alpha -1 )C.
% &(\lambda - 1) t_{j-1} + 2 \ln \left( \frac{4\pi}{\nu(1-\ve)^4}  t_j \right) 
% \leq (\lambda - 1) t_{j-1} + 2 \ln \left( \frac{4\pi}{\nu(1-\ve)^4}  t_{j-1} \right) \\
% & \stackrel{(\ref{eq:T_II})}{<} 
% \left( \lambda - 1 + 1 -\alpha \right) t_{j-1} = \left( 2\alpha -1 - \alpha \right) t_{j-1} = 
% \left( \alpha - 1\right) t_{j-1} \\
% &\stackrel{t_{j-1}>C, \alpha > 1}{<}  \left( \alpha - 1\right) C.
\end{split}
\]

Hence, we can write
$$ \sum_{j=1}^{T} e^{-\gamma t_j} < e^{-\gamma t_T} \sum_{j=0}^\infty e^{-j\gamma \left( 1- \alpha \right) C}.$$
Also by the third condition in (\ref{eq:T_C})
\begin{equation} \label{eq:t_TLow}
\lambda C \leq \lambda t_{T-1} = t_T - 2 \ln \left( \frac{4\pi}{\nu(1-\ve)^4}  t_T \right) < t_{T},
\end{equation}
whereby \begin{equation} \label{eq:t_i_uniform_bound} t_T > \lambda C. \end{equation} 
Therefore, 
$$  \sum_{j=1}^{T} e^{-\gamma t_j} < {e^{-\gamma \lambda C} \over 1- e^{-\gamma \left(1- \alpha \right)C}} \stackrel{(\ref{eq:T_C})}{<} {1\over 2}.$$
%Hence the above sum 
% $$ \sum_{j=1}^T {1 \over \lambda^j} <  {\left(1/\lambda \right)^{T+1} - 1 \over 1/\lambda - 1} <  
% {\lambda \over 1- \lambda}~\left({1\over \lambda} \right)^{T+1} = {1\over 1-\lambda}~\left({1\over \lambda}\right)^T  < {t_0 \over 2}.
%  $$
%  This implies that we need to ensure that
%  $$T < \log_{1/\lambda} \left( {1 - \lambda \over 2}~t_0 \right).$$
%  But for all $i < T$ we have $t_i > \lambda^i t_0$ by (\ref{lowrec}). 
%  So if $i< T$ is such that $$\lambda^i t_0 > C,$$ then 
%  $$i < \log_{1/\lambda} \left( {t_0 \over C}\right).$$
%  So if we choose $C$ to satisfy $C > {2\over 1 -\lambda}$, 
%  it suffices to set 
%  \begin{equation} \label{eq:T_first} 
%  T : = \max \left\{ i \ : \ i < \log_{1/\lambda} \left( {t_0 \over C} \right)  \wedge T_1 \right\}.
%  \end{equation}

 
  
\subsection{Some concentration results}	
In this sub-section, we will show that the number of vertices that belong to each band is almost determined. 
Note that by Lemma~\ref{lem:dist} (since $t_{i} \leq R/2$, for all $i\geq 0$) we have uniformly for all $i$ 
\begin{equation} \label{eq:ExpNi} 
\mathbb{E} \left[ N_{i} \right] = (1-o(1)) N \alpha \int_{t_i}^{t_{i-1}} e^{-\alpha t} dt 
= (1-o(1)) N \left( e^{-\alpha t_i} - e^{-\alpha t_{i-1}} \right). \end{equation}
(Here we take $t_{-1} = R$.)
We need to show that this quantity grows fast enough as a function of $N$. To see that this is indeed the case, we write 
\begin{equation} \label{eq:ExNiLow} \begin{split}  
\mathbb{E} \left[ N_{i} \right] = (1-o(1)) N e^{-\alpha t_i} \left( 1-  e^{-\alpha(t_{i-1}-t_i)}\right) 
\stackrel{(\ref{eq:T_1})}{>}  N e^{-\alpha t_i} (1-\ve).
\end{split}
\end{equation}
Hence, since $t_i \leq R/2$, it follows that 
\begin{equation} \label{eq:ExpNLow}
\mathbb{E} \left[ N_{i} \right] > (1-\ve) \nu e^{{1\over 2}\left(1 - \alpha\right) R} = \Omega (N^{1- \alpha}),
\end{equation}
which tends to infinity as $N$ grows, since $\alpha < 1$. 

%Note also that changing the position of one vertex affects $N_i$ by at most one. 
Hence, applying a standard Chernoff bound 
we deduce that with probability $1- \exp \left(- \Omega \left( N^{1- \alpha} \right) \right)$ we have 
$$ N_i = (1\pm \ve) \mathbb{E} \left[ N_i \right].$$ 
Hence, since $T = O \left( \ln R \right)$ (cf. (\ref{eq:t_idecay})), a simple first-moment argument shows that with probability 
$1- \exp \left(- \Omega \left( N^{1- \alpha} \right) \right)$ we have 
\begin{equation} \label{eq:N}  N_i = (1\pm \ve) \mathbb{E} \left[ N_i \right], 
\end{equation}
for all $0\leq i\leq T$. 
In what follows, we shall condition on this event, which we denote by $\Nn$. 


\subsection{The inductive step} \label{sec:Indstep}

Throughout this section, we will have $\theta^{(i)} = 2(1-\ve) e^{{1 \over 2}(t_i + t_{i-1}-R)}$, for $0 < i \leq T$ and 
$\theta^{(0)}= 2(1-\ve)$. 
Assume that there are $N_{i-1}'$ vertices in the active area of $\B_{i-1}$. For a vertex in $v \in \N_{i-1}'$ let $S(v)$ denote the arc of 
angle $\theta^{(i)}$ around the projection of $v$ on the circle of radius $R-t_i$ (in other words, the set of points of type $t_i$) - we denote this
circle by $\cC_{i}$. 
We call this the \emph{shadow} of $v$. Let $$S_i := \bigcup_{v \in \N_{i-1}'} S(v)$$ denote the union of the shadows of the vertices in 
$\N_{i-1}'$ --- this is the active area of the band $\B_i$. Let $\Theta_{i}$ be the total angle of $S_i$. 

We will determine $\Theta_i$ conditional on $\Theta_{i-1}$, assuming that we have not specified which vertices among those in $\N_{i-1}$ 
belong to $S_{i-1}$. Let $S_{i-1}'$ denote the projection of $S_{i-1}$ on the circle $\cC_{i}$. Note that $S_{i-1}'$ is the disjoint union 
of arcs each of them having angle which is at least $\theta^{(i-1)}$. Moreover, the total angle covered by $S_{i-1}'$ is $\Theta_{i-1}$ as well.  

Assuming that the vertices of $\mathcal{N}_{i-1}$ have all type $t_{i-1}$, we expose their positions on $\cC_{i-1}$ and consider the
shadows of those points that will fall into $S_{i-1}$. Recall that this number is a stochastic lower bound on $N_{i-1}'$, whereby 
$$ \mathbb{E} \left[ N_{i-1}' \mid N_{i-1}, \Theta_{i-1} \right] \geq N_{i-1} {\Theta_{i-1} \over 2\pi}.$$
Furthermore, since $\Theta_{i-1} \geq \pi$, as $i-1< T$ and $N_{i-1} = \Omega (N^{1- \alpha})$, as 
the event $\Nn$ is realised, an application of the Chernoff bound implies that with probability $1 - o\left( {1\over \ln N} \right)$ 
\begin{equation} \label{eq:N_i'_hypothesis} N_{i-1}' \geq  N_{i-1} {\Theta_{i-1} \over 2\pi}(1-\ve). \end{equation}
We will show that conditional on $N_{i-1}'$ as above and $\Theta_{i-1}$ with high probability $\Theta_i$ is at least a certain fraction of 
$\Theta_{i-1}$. 


\begin{lemma} \label{lem:Theta_Recursion}
Conditional on $N_{i-1}$ satisfying $\Nn$, on $\Theta_{i-1}$ as well as on $N_{i-1}'$ satisfying (\ref{eq:N_i'_hypothesis}), with probability $1-o\left( {1\over \ln N} \right)$ we have 
$$\Theta_i \geq \Theta_{i-1} \left( 1- e^{-\gamma t_i}\right), $$
for some constant $\gamma = \gamma (\alpha, \nu, \ve)>0$, uniformly for $i=1,\ldots, T$. 
\end{lemma}
\begin{proof}
To show this statement, we divide each subinterval of $S_{i-1}'$ into segments of angle
$$\ell_{i-1}:= {\Theta_{i-1} \over N_{i-1}^2}.$$
It is possible that each of these subintervals contains at least one segment of smaller angle. 
However, each subinterval of $S_{i-1}'$ contains many segments of angle $\ell_{i-1}$. We denote by $\cP$ the collection of all \emph{those}
segments. We will use a bounded-differences concentration inequality in order to show that with high probability most of them 
are contained in $S(v)$ for some $v \in \N_{i-1}'$. 

Firstly, let us bound from below the size of $\cP$. Recall that each subinterval of $S_{i-1}'$ has angle at least $\theta^{(i-1)}$. 
Therefore, there are at most $\Theta_{i-1}/\theta^{(i-1)}$ subintervals. Each such subinterval contains at most one segment of 
angle less than $\ell_{i-1}$. Hence, 
\begin{equation} \label{eq:size_of_p} 
|\cP| \geq \left\lfloor {\Theta_{i-1} \over \ell_{i-1}} \right\rfloor - {\Theta_{i-1} \over \theta^{(i-1)}} 
\stackrel{\Theta_{i-1} < 2 \pi}{>} 
%{\Theta_{i-1} \over \ell_{i-1}} -1 - {\Theta_{i-1} \over \theta^{(i-1)}} = 
N_{i-1}^2 - {2\pi \over \theta^{(i-1)}}. 
\end{equation}
But
\begin{equation} \label{eq:theta_low} \theta^{(i-1)} = 2(1-\ve) e^{{1\over 2} \left( t_{i-1} + t_{i-2} - R \right)} = 
\stackrel{t_{i-2}>t_{i-1}}{>} 2(1-\ve) e^{{1\over 2} \left( 2t_{i-1} - R \right)} = 2\nu (1-\ve ) \frac{e^{t_{i-1}}}{N}, 
\end{equation}
and also since $\Nn$ is realised (\ref{eq:ExNiLow}) implies that 
$$ N_{i-1} \geq (1-\ve)^2 N e^{-\alpha t_{i-1}}= (1-\ve)^2 \nu e^{R/2 - \alpha t_{i-1}}.$$
Thus, in this case 
$$ N_{i-1}^2 \theta^{(i-1)} \geq N_{i-1} \theta^{(i-1)}  =  2 \nu (1-\ve)^3 e^{ (1 - \alpha) t_{i-1}} \stackrel{t_{i-1}\geq R/2}{\geq}  
2 \nu (1-\ve)^3 e^{ (1 - \alpha) R/2}.$$ 
This together with (\ref{eq:size_of_p}) imply that 
\begin{equation} \label{eq:size_of_p_Finale} 
|\cP| \geq N_{i-1}^2 \left (1  - O\left(N^{\alpha-1} \right)  \right).
\end{equation}
It is now immediate that the total angle covered by the union of the segments in $\cP$, which we denote by $\Theta_{\cP}$, satisfies
\begin{equation} \label{eq:angle_of_p}
\Theta_{\cP}\geq \Theta_{i-1}\left( 1  - O\left(N^{\alpha-1} \right)\right). \end{equation} 


To be more precise, recall that each subinterval has angle that is at least $\theta^{(i-1)}$. 
Since the event $\Nn$ is realised, we have 
$$ \ell_{i-1} = {\Theta_{i-1} \over N_{i-1}^2} \stackrel{(\ref{eq:ExNiLow})}{\leq} {2\pi \over (1-\ve)^2}{e^{2\alpha t_i}\over N^2}. 
$$
Now, (\ref{eq:theta_low}) implies that 
\[\begin{split}{\ell_{i-1} \over \theta^{(i)}} &< {(1-\ve)\pi \over \nu}~{e^{(2\alpha - 1) t_i} \over N} 
\stackrel{1 < 2\alpha, t_i < t_0=R/2}{<} 
 {(1-\ve)\pi \over \nu}~{e^{(2\alpha - 1) R/2} \over N} \\
&= {(1-\ve)\pi \over \nu^2}~e^{(\alpha - 1)R} 
\stackrel{\alpha <1}{=}o(1). 
 \end{split}
 \]
In other words, uniformly for all $i < T$, we have $\theta^{(i-1)} > \theta^{(i)} \gg \ell_{i-1}$.


For a segment $\sigma \in \cP$, let $\E_\sigma$ denote the event that the segment $\sigma$ is not covered by $S (v)$, for 
all $v \in \mathcal{N}_{i-1}'$. The probability that the segment is indeed covered for a certain $v \in \mathcal{N}_{i-1}'$ is at least 
${\theta^{(i)} \over \Theta_{i-1}} \geq  {\theta^{(i)} \over 2\pi}$. 
Hence
\begin{equation} \label{eq:Esigma} 
\begin{split}
&\Prb {\E_{\sigma} \mid N_{i-1}', \Theta_{i-1}} \leq \left( 1 - {\theta^{(i)} \over 2\pi} \right)^{N_{i-1}'} \leq 
\exp \left( - {\theta^{(i)} N_{i-1}' \over 2\pi} \right) \\
& \stackrel{(\ref{eq:N_i'_hypothesis})}{\leq} \exp \left(-  (1-\ve){\theta^{(i)} \Theta_{i-1}N_{i-1} \over 4\pi^2}\right) 
\stackrel{(\Theta_{i-1}>\pi)}{\leq} \exp \left(-  (1-\ve){\theta^{(i)} N_{i-1} \over 4\pi}\right). 
\end{split}
\end{equation}
Now, on the event $\Nn$, the following holds through (\ref{eq:ExNiLow}) and (\ref{eq:N}) 
$$\theta^{(i)} N_{i-1} \geq 2\nu(1-\ve)^3 e^{{1 \over 2}(t_i + t_{i-1}) - \alpha t_{i-1}}.$$
But by (\ref{eq:def_ti}) we have
$$ {1 \over 2}(t_i + t_{i-1}) - \alpha t_{i-1} = \ln \left({4\pi \over 2\nu (1-\ve)^4} t_i \right) $$
which, if substitute in (\ref{eq:Esigma}) implies that 
\begin{equation}  \label{eq:Esigma'} 
\begin{split} 
\Prb {\E_{\sigma} \mid N_{i-1}', \Theta_{i-1}} \leq e^{-t_i}.
\end{split}
\end{equation}
Let $\cP'$ denote the subset of segments of $\cP$ that are covered by $S (v)$, for some $v \in \N_{i-1}'$. 
Therefore, 
\begin{equation} \label{eq:mu_low} 
\mu_{\cP'}:=\mathbb{E} \left[ |\cP'| \mid N_{i-1}', \Theta_{i-1} \right] \geq  |\cP| \left( 1- e^{-t_i} \right). 
\end{equation}
For any vertex $v \in \N_{i-1}'$, $S(v)$ covers at most $2 \theta^{(i)}/\ell_{i-1}$ segments by Lemma~\ref{lem:relAngle}.
Thus changing the position of one vertex in $\N_{i-1}'$ changes the number of covered segments by at most $2 \theta^{(i)}/\ell_{i-1}$. 
Hence, applying the Hoeffding-Azuma concentration bound (cf.~\cite{JLR} Theorem 2.25 p. 37) we deduce that 
$$ \Prb {|\cP'| < (1- e^{-\left(1- \alpha \right) t_{i-1} /8})\mu_{\cP'} \mid  N_{i-1}', \Theta_{i-1}} = 
\exp \left(-  \Omega \left( { \mu_{\cP'}^2 e^{-(1-\alpha )t_{i-1}/4} \ell_{i-1}^2\over N_{i-1}' (\theta^{(i)})^2} \right)\right). $$
We will show now that 
\begin{equation} \label{eq:Exponent_bound}
{ \mu_{\cP'}^2 e^{-(1-\alpha)t_{i-1}/4} \ell_{i-1}^2\over N_{i-1}' (\theta^{(i)})^2} = 
\Omega \left( N^{\frac{5}{4}\left(1 - \alpha \right)} \right).
\end{equation}
We will estimate the above quantity up to absolute multiplicative constants -- we write $A\gtrsim B$ to denote that $A/B$ is 
bounded from below by some constants that depend only on $\alpha, \nu$ and $\ve$. 
To derive the above lower bound we will need to deduce a stronger upper bound on $t_i$ in terms of $t_{i-1}$. 
By (\ref{eq:def_ti}) we have 
\begin{equation} \label{eq:t_i_Upper_New}
\begin{split}
\lefteqn{t_i = \lambda t_{i-1} + 2 \ln \left( \frac{4 \pi}{\nu (1-\ve )^4}t_i \right)} \\
 &\stackrel{t_{i} < t_{i-1}}{\leq} \lambda t_{i-1} + 2 \ln \left( \frac{4 \pi}{\nu (1-\ve )^4}t_{i-1} \right)
\stackrel{t_{i-1} >C,~(\ref{eq:T_C})}{<}\left(\lambda + \frac{1-\alpha}{2} \right) t_{i-1}.
\end{split}
\end{equation}
Now, we have 
\begin{equation*} 
\begin{split}
&{\mu_{\cP'}^2 e^{-(1- \alpha )t_{i-1}/4} \ell_{i-1}^2\over N_{i-1}' (\theta^{(i)})^2} 
\stackrel{(\ref{eq:t_TLow}), (\ref{eq:ExNiLow}), (\ref{eq:size_of_p_Finale})}{\gtrsim} 
{N_{i-1}^4 e^{-(1-\alpha )t_{i-1}/4} \ell_{i-1}^2\over N_{i-1}  (\theta^{(i)})^2}  \\
&\gtrsim 
N_{i-1}^3 e^{-(1-\alpha )t_{i-1}/4} \left( {\Theta_{i-1} \over N_{i-1}^2} \right)^2 {N^2 \over e^{t_i + t_{i-1}}} 
\stackrel{(\ref{eq:Theta_B})}{ \gtrsim} 
{N^2 \over N_{i-1}} e^{-(5-\alpha )t_{i-1}/4 - t_i}  \\
& \stackrel{(\ref{eq:ExNiLow}), \ t_i \leq t_{i-1}}{\gtrsim} N e^{-(5-\alpha )t_{i-1}/4 - t_i+\alpha t_{i-1}} 
\stackrel{(\ref{eq:t_i_Upper_New})}{\gtrsim} N e^{(-(5-\alpha )/4 - \lambda + (1-\alpha)/2 +\alpha ) t_{i-1}}.
\end{split}
\end{equation*}
But 
$$-(5-\alpha )/4 - \lambda + (1-\alpha)/2 +\alpha = -(5-\alpha )/4 - 2\alpha +1 + (1-\alpha)/2 +\alpha = 1/4 - 5 \alpha /4. $$
Hence,
\begin{equation}\label{eq:Exponent_bound_developed} 
\begin{split}
&{\mu_{\cP'}^2 e^{-(1- \alpha )t_{i-1}/4} \ell_{i-1}^2\over N_{i-1}' (\theta^{(i)})^2} \gtrsim 
N e^{(1 - 5 \alpha )t_{i-1}/4}
\stackrel{t_{i-1} \leq R/2, \alpha > 1/2}{\gtrsim} e^{\frac{5}{4}\left(1 - \alpha \right){R\over 2}} 
\gtrsim N^{\frac{5}{4}\left(1 - \alpha \right)}.
\end{split}
\end{equation}

Now,
$$\Theta_i \geq \ell_{i-1} |\cP'|. $$
Hence, conditional on $N_{i-1}'$ and $\Theta_{i-1}$ with probability $1- o\left({1\over \ln N}\right)$ we have 
$$\Theta_i \geq \ell_{i-1}\mu_{\cP'} (1- e^{-\left(\alpha - {1 \over 2}\right) t_{i-1} /2}). $$
We will bound the right-hand side of the above from below as follows:
\begin{equation} \label{eq:Theta_iLow} \begin{split}
&\ell_{i-1}\mu_{\cP'} (1- e^{-\left(\alpha - {1 \over 2}\right) t_{i-1} /2})
\stackrel{(\ref{eq:mu_low})}{\geq} 
\ell_{i-1} |\cP|(1-e^{-t_{i}}) (1- e^{-\left(\alpha - {1 \over 2}\right) t_{i-1} /2}) \\
&\stackrel{(\ref{eq:size_of_p_Finale})}{\geq} \ell_{i-1} N_{i-1}^2 \left( 1- O \left(N^{\alpha-1}\right) \right) 
(1-e^{-t_{i}}) (1- e^{-\left(\alpha - {1 \over 2}\right) t_{i-1} /2}) \\
&= \Theta_{i-1} \left( 1- O \left(N^{\alpha-1}\right) \right) 
(1-e^{-t_{i}}) (1- e^{-\left(\alpha - {1 \over 2}\right) t_{i-1} /2}) \\
&\geq \Theta_{i-1} \left( 1- O \left(N^{\alpha-1}\right) \right)  
\left(1-  e^{-t_{i}} - e^{-\left(\alpha - {1 \over 2}\right) t_{i-1} /2}\right).
\end{split}\end{equation}
But by (\ref{eq:def_ti}) we have 
\begin{equation*}
{1\over 2}\left(\alpha - {1 \over 2}\right) t_{i-1} = {1 \over 4} t_i - {1\over 2}\ln \left( \frac{4\pi}{\nu (1-\ve)^4} t_i\right) 
\stackrel{(\ref{eq:T_C}),(\ref{eq:t_i_uniform_bound})}{>} {1 \over 4}(1-\ve) t_i.
\end{equation*}
We substitute this bound into the last expression of (\ref{eq:Theta_iLow}) and deduce the following: there exists a constant 
$\gamma = \gamma (\ve)>0$ such that for all $N$ sufficiently large and for all $i=1,\ldots, T$ we have 
\[ \Theta_i \geq \Theta_{i-1}\left( 1- e^{-\gamma t_i}\right). \qedhere\]
\end{proof}

\subsection{Proof of Theorem~\ref{thm:main}} \label{sec:finalproof}

For $i=1,\ldots, T$ let $\E_i$ denote the event that for all $0 \leq j\leq i$, we have 
$$ \Theta_j \geq \Theta_{j-1} (1- e^{-\gamma t_j}) $$ 
and 
$$ N_{j}'  \geq N_{j} {\Theta_j \over 2\pi} (1-\ve).$$

Note that conditional on $\Nn$, the latter inequality together with (\ref{eq:ExpNi}) and (\ref{eq:N}) 
implies that for any $N$ sufficiently large 
$$ N_j' \geq (1-\ve)^3 N \left(e^{-\alpha t_j} - e^{-\alpha t_{j-1}}\right)~{\Theta_j \over 2\pi}.$$
Now by (\ref{eq:N_i'_hypothesis}) and Lemma~\ref{lem:Theta_Recursion}, we have 
$$\Prb {\E_i \mid  \E_{i-1}, \Nn} = 1 - o\left( {1\over R} \right).$$ 
But as the sequence $\{t_i \}_{i=1,\ldots, T}$ decreases exponentially fast (cf. (\ref{eq:t_idecay})), we have 
$T= O(\ln R)$. Hence, since the events $\{\E_i \}_{i=1,\ldots, T}$ form a decreasing sequence, we deduce that 
$$ \Prb {\E_{T} \mid \Nn} = 1-o(1). $$
On the event $\E_T$, we have $\Theta_i > \pi$ for all $i=1,\ldots, T$ (cf. (\ref{eq:Theta_i_Recursion})). 
Therefore, 
$$ N_i' \geq {1\over 2}~(1-\ve)^3 N \left( e^{-\alpha t_i} - e^{-\alpha t_{i-1}} \right). $$
which in turn implies that 
$$\sum_{i=1}^T N_{i}' \geq {1\over 2}~(1-\ve)^3 N \left( e^{-\alpha t_T} - e^{-\alpha t_0}\right) > 
{1\over 2}~(1-\ve)^3 N \left( e^{-\alpha \lambda C /2} - o(1)\right).$$ 





\section{Proof of Theorem~\ref{thm:crit}}

In the critical case, that is, when $\alpha=1$, 
the probability of having a giant component turns out to depend on the value of $\nu$.
%The following theorem regards the model where the vertices of the underlying graph are the points of the Poisson point process on $\D$ 
%of rate $N$. Therefore, the number of vertices inside $\D$ is distributed as a Poisson random variable with parameter equal to $N$.
%Furthermore, the number of points in a (Lebesque) measurable subset of $\D$ whose area is a $\lambda$-fraction of the area of $\D$
%follows the Poisson distribution with parameter equal to $\lambda N$. Also, for any collection of pairwise disjoint sets these random 
%variables form an independent family. The following theorem is about the random graph that is formed as $G(N;\nu, \alpha)$ on this 
%vertex set.
It will be convenient to work with the \emph{Poisson model} $\Pnan$ in which the vertex set is the set of points of a Poisson point 
process inside $\D$.
In Lemma~\ref{lem:equivmodels} below, we show that for certain graph properties, if they hold a.a.s. in $\Pnan$, then this is 
also the case in the $\Gnan$ model.

\subsection{Poissonisation}
Sometimes it is easier to work under the setting where instead of $N$ (fixed) random points, our vertex set
consists of $\mathrm{Po}(N)$ points on $\D$ -- of course still sampled independently according to~(\ref{eq:pdf}).
We denote the resulting graph by $\Pnan$.
The benefit is that in this way our vertex set consists of a Poisson point process (see for example~\cite{Kingman}).
In particular, the numbers of points in any finite collection of pairwise disjoint measurable subsets of $\D$ are
independent Poisson-distributed random variables. The term \emph{asymptotically almost surely (a.a.s.)} has the same meaning in this context as before. 
We prove the following lemma that allows us to transfer results from the Poisson model into the $\Gnan$ model.
Let $\mathcal{A}_n$ denote a set of graphs on $\mathrm{V}_n:=\{1,\ldots, n \}$ that is closed under automorphisms.
We call a family $\mathcal{A}=\{\mathcal{A}_n\}_{n \in \mathbb{N}}$ of graphs \emph{(vertex-) non-decreasing}, if $G-v \in \mathcal{A}_{n-1}$ for any
$v\in V(G)$ implies $G\in\mathcal{A}_n$.
Similarly, we call the family \emph{(vertex-) non-increasing}, if $G-v\notin \mathcal{A}_{n-1}$ for any $v\in V(G)$ implies
$G\notin\mathcal{A}_n$.

\begin{lemma}\label{lem:equivmodels}
     Assume that $\alpha>0$ is fixed.
     Let $\mathcal{A}$ be a (vertex-) non-decreasing family of graphs.
     For $N$ large enough we have
$\P(\Gnan\notin\mathcal{A})<4\P(\Pnan\notin\mathcal{A})$.
     The same holds if $\mathcal{A}$ is (vertex-) non-increasing.
\end{lemma}
\begin{proof}
Denote by $E_{\mathrm{Po}}$ and $E$ the events that $\Pnan\notin \mathcal{A}$ and 
$\Gnan\notin \mathcal{A}$, respectively.
     We write
    \begin{align*}
\P(E_{Po})=&\sum_{N'=0}^\infty \P(E_{Po}|Po(N)=N')\cdot\P(Po(N)=N')\\
% =&\sum_{N'=0}^N(\P(E(N',\alpha,\nu)|Po(N)=N')\cdot\P(Po(N)=N'))\\
% &+\sum_{N'=N+1}^\infty(\P(E(N',\alpha,\nu)|Po(N)=N')\cdot\P(Po(N)=N'))\\
\geq&\sum_{N'=N}^\infty \P(E_{Po}|Po(N)=N')\cdot\P(Po(N)=N')\\
 \geq&\sum_{N'=N}^\infty\P(E_{Po}|Po(N)=N)\cdot\P(Po(N)=N'),
   \end{align*}
%      \begin{align*}
% \P(E_{\mathrm{Po}}(N,\alpha,\nu))&=\sum_{N'=0}^\infty\P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po}(N)=N')\cdot
%     \P(\mathrm{Po}(N)=N')\\
%          &\geq\sum_{N'=0}^N \P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po}
% (N)=N')\cdot\P(\mathrm{Po}(N)=N').
%      \end{align*}
where we have used in the last line that, since $\mathcal{A}$ is non-decreasing, we have
  $\P(E_{\mathrm{Po}}|\mathrm{Po}(N)=N')\geq\P(E_{\mathrm{Po}}|\mathrm{Po}(N)=N)$ for $N'\geq N$.
Let us also note that $\P(E_{\mathrm{Po}}|\mathrm{Po}
(N)=N) = \P(E)$.
     Thus,
     \begin{align*}
         \P(E_{\mathrm{Po}})&\geq\sum_{N'=N}^\infty
\P(E)\cdot
\P(\mathrm{Po}(N)=N')\\
         &=\P(E)\cdot\P(\mathrm{Po} (N)\geq N)\\
         &>\frac14\cdot \P(E),
     \end{align*}
     where the last line holds $N$ large enough (by an application of, say, the central limit theorem).
     The second part of the lemma follows similarly, bounding the sum by taking only the terms where $N'\geq N$.
\end{proof}
     This implies that if $\P(\Pnan\notin\mathcal{A})=o(1)$,
then $\P(\Gnan\notin\mathcal{A})=o(1)$.
     The families we consider will be $\mathcal{A}=\{G:\text{ $G$ has a component of order at least } C\}$ or
     $\mathcal{B}=\{G:\text{ $G$ has no component of order at least } C \}$,
     where $C$ does not depend on the number of vertices in $G$.
     In particular, in the second part of Theorem~\ref{thm:crit}, having chosen the parameter $N$, we consider the family
     $\{G:\text{ $G$ has a component of order at least }N/65\}$, where $|G|=N$ is not required.


%%\begin{lemma}
%%	Assume $\alpha$ is fixed.
%%	Let $\mathcal{A}$ be a monotone increasing family of graphs.
%%	If $\mathcal{A}$ holds a.a.s. for $\nu>\nu_c$ in the Poisson model, then $\mathcal{A}$ holds a.a.s. for $\nu>\nu_c$ in the $\Gnan$ model.
%%	Similarly, let $\mathcal{B}$ be a monotone decreasing family of graphs.
%%	If $\mathcal{A}'$ holds a.a.s. for $\nu<\nu_c$ in the Poisson model, then $\mathcal{A}'$ holds a.a.s. for $\nu<\nu_c$ in the $\Gnan$ model.
%%\end{lemma}
%\begin{lemma}\label{lem:equivmodels}
%	Assume that $\alpha>0$ is fixed.
%	Let $\mathcal{A}$ be a monotone non-decreasing family of graphs.
%	If a.a.s. $\Pnan\in\mathcal{A}$, then a.a.s. $\Gnan\in\mathcal{A}$.
%	The same holds if $\mathcal{A}$ is monotone non-increasing.
%\end{lemma}
%\begin{proof}
%	Denote by $E_{\mathrm{Po}}(N,\alpha,\nu)$ and $E(N,\alpha,\nu)$ the events that $\Pnan\notin \mathcal{A}$ and $\Gnan\notin \mathcal{A}$,
%   respectively.
%	We write
%%	\begin{align*}
%%		o(1)=&\P(E_{Po}(N,\alpha,\nu))=\sum_{N'=0}^\infty(\P(E(N',\alpha,\nu)|Po(N)=N')\cdot\P(Po(N)=N'))\\
%%		=&\sum_{N'=0}^N(\P(E(N',\alpha,\nu)|Po(N)=N')\cdot\P(Po(N)=N'))\\
%%		&+\sum_{N'=N+1}^\infty(\P(E(N',\alpha,\nu)|Po(N)=N')\cdot\P(Po(N)=N'))\\
%%		\geq&\sum_{N'=N+1}^\infty(\P(E(N',\alpha,\nu)|Po(N)=N')\cdot\P(Po(N)=N'))\\
%%		\geq&\sum_{N'=N+1}^\infty(\P(E(N',\alpha,\nu)|Po(N)=N)\cdot\P(Po(N)=N'))\\
%%		.
%%	\end{align*}
%	\begin{align*}
%		\P(E_{\mathrm{Po}}(N,\alpha,\nu))&=\sum_{N'=0}^\infty\P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po}(N)=N')\cdot
%   \P(\mathrm{Po}(N)=N')\\
%		&\geq\sum_{N'=0}^N \P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po} (N)=N')\cdot\P(\mathrm{Po}(N)=N').
%	\end{align*}
%	Since $\mathcal{A}$ is non-decreasing, we have   
 %   $\P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po} (N)=N')\geq\P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po}(N)=N)$ for $N'\leq N$.
 %   Also, note that $\P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po} (N)=N) = \P(E(N,\alpha,\nu))$.
	%Thus,
	%\begin{align*}
%		\P(E_{\mathrm{Po}}(N,\alpha,\nu))&\geq\sum_{N'=0}^N \P(E_{\mathrm{Po}}(N,\alpha,\nu)|\mathrm{Po}(N)=N)\cdot 
%\P(\mathrm{Po}(N)=N')\\
%		&=\P(E(N,\alpha,\nu))\cdot\P(\mathrm{Po} (N)\leq N)\\
%		&>\frac14\cdot \P(E(N,\alpha,\nu)),
%	\end{align*}
%	for $N$ large enough. 
%	Hence, if $\P(E_{\mathrm{Po}}(N,\alpha,\nu))=o(1)$, then we also have $\P(E(N,\alpha,\nu))=o(1)$.
%	In other words, $\Gnan\in\mathcal{A}$ a.a.s.
%	The second part of the lemma follows similarly, bounding the sum by taking only the terms where $N'\geq N$.
%\end{proof}


%%With our method the bound on $\nu_0$ could be improved slightly but it is unclear whether the bound that can be reached is tight.

\subsection{The subcritical case}

%We prove the first part of Theorem~\ref{thm:crit} by contradiction.
%Assuming we have a component of size $\eps N$, then at least an $\eps/2$-proportion of the vertices of type at most $T=\log\log\log R$
%must be contained in that component as $(1-o(1))N$ vertices have type less than $T$.

We prove the first part of Theorem~\ref{thm:crit} for $\Pnan$ by contradiction.
Assuming we have a component of size $\frac{N}{\log\log R}$, then at least $\frac{N}{2\log\log R}$ vertices of type at most
$T=\log\log R$ must be contained in that component as a.a.s. at most $\frac{N}{2\log\log R}$ vertices have type larger than $T$.

We will use a \textit{smooth breadth exploration process} starting at a point $v_0$ of type at most $\log \log R$, a continuous-type version of the process
defined in Section~\ref{sec:subcritical}:
\begin{itemize}
	\item Let $T_0=t_{v_0}$.
	\item Recursively for $i\geq1$, if $v_{i-1}$ has a neighbour in clockwise direction,
		let $v$ be the neighbour of $v_{i-1}$ of highest type in clockwise direction and let $T_i$ be the type of $v$.
		Let $\theta_i$ be the maximum relative angle between $v_{i-1}$ and any adjacent point of type $T_i$.
		Define $v_i$ as the point of type $T_i$ with relative angle $\theta_i$ from $v_{i-1}$ in the clockwise direction. We call this 
		the $i$th root vertex. 
	\item There are three stopping conditions for the process:
		\begin{enumerate}[(i)]
			\item $v_i$ has no neighbour in the clockwise direction;
			\item $T_i>\log R$;
			\item $i=\log^2 \log R$ or the angle between $v_i$ and $v_0$ exceeds $\pi$. 
		\end{enumerate}%Stop the process if $i=\log\log R$ or if $v_i$ has no neighbour in clockwise direction.
\end{itemize}

We define stopping times $\tau_1$ and $\tau_2$ as the stopping times that correspond to the first and the second stopping conditions,
respectively.
Because of the third stopping condition, we know that $0\leq\tau_i\leq\log\log R$ or $\tau_i=\infty$ for $i=1,2$.

The following two lemmas show that the process stops quickly for a suitable choice of $\nu$.

\begin{lemma}\label{lem:stop}
	For $\nu<\frac{\pi}{8}$, starting at a vertex of type at most $\log\log R$, we have
	\[\P(\tau_1<\infty)=1-o\left(\left(\frac{\log\log R}{\log R}\right)^c\right)\text{ for some }c>0.\]
%	For $\nu<\frac{\pi}{8}$, starting at a vertex of type at most $\log\log\log R$,we have \[\P(\tau_1<\infty)=1-o(1).\]
%	the probability of not finding a new neighbour in one of the first
%	$\log\log R$ steps of the smooth breadth exploration process is $1-o(1)$.
\end{lemma} 

\begin{lemma}\label{lem:high}
	For $\nu<\frac{\pi}{8}$, starting at a vertex of type at most $\log\log R$, we have 
    \[\P(\tau_2<\infty)=o\left(\frac{\log^2 \log R}{R^c}\right) \text{ for some }0<c<1.\]
%	For $\nu<\frac{\pi}{8}$, starting at a vertex of type at most $\log\log\log R$, we have \[\P(\tau_2<\infty)=o(1).\]
%	the probability of one of the points $v_i$ within the first
%	$\log\log R$ steps of the smooth breadth exploration process having type at least $\log R$ is $o(1)$.
\end{lemma} 
The above process is repeated in the clockwise as well as in the anticlockwise direction. Parametrising with respect to the initial vertex $v$, we
denote the above stopping times by $\tau_1^+(v)$ ($\tau_1^-(v)$, respectively) and $\tau_2^+(v)$ ($\tau_2^-(v)$, resp.). 
Let also $\tau^+(v)$ and $\tau_-(v)$ denote the stopping times of the two processes. 


Using the two lemmas we can prove the first part of Theorem~\ref{thm:crit}.
\begin{proof}[Proof of the first part of Theorem~\ref{thm:crit}]
%	Let $\nu<\frac{\pi}{8}$ and assume there is a component $C$ of size $2\eps N$ for some $\eps>0$.
%	Note that a.a.s. the number of vertices of type at least $\log\log\log R$ is $o(N)$, so $C$ must contain at least
%	$\eps N$ vertices of type at most $\log\log\log R$.
%	For any vertex $v$ of type at most $\log\log\log R$, Lemmas~\ref{lem:high} and~\ref{lem:stop} imply that with probability $1-o(1)$,
%	the smooth breadth exploration process started at $v$ terminates after at most $\log\log R$ steps and has only had root vertices of type
%	at most $\log R$.
%	By Lemma~\ref{lem:relAngle} the angle gained in each step is a.a.s. at most $2(1+\eps)\exp(2\log R-R)$ for some arbitrary $\eps>0$ and the
%	angle gained during the whole process in two directions is at most $2(1+\eps)\exp(2\log R-R)\log\log R=o(1)$.
%	Similar to the proof of Lemma~\ref{lem:dense_sectors}, we can deduce that none of these vertices can belong to a component of size $2\eps N$,
%	a contradiction.
%	Let $\nu<\frac{\pi}{8}$ and assume there is a component $C$ of size at least $???$.
	In what follows, we assume that $N$ is large enough for all our estimates to hold. For simplicity, we shall denote the set of vertices 
    by $\V$ - note that this is now a random set of vertices as described above. 
	Let $V_{high} = \{ v \in \V \ : \ t_v \geq \log \log R \}$ and $V_{low} = \V \setminus V_{high}$. In other words, we partition the set of vertices into two parts: that of vertices of low type and that of vertices of high type. 
Now, we set 
$$V_{small} = \{ v \in V_{low} \ : \ \tau_1^+ (v) < \infty, \tau_2^+ (v)= \infty \ \mbox{and} \ \tau_1^- (v) < \infty, 
\tau_2^- (v)= \infty \},$$
and $V_{large} = V_{low} \setminus V_{small}$. 
The smooth breadth exploration process started at a vertex $v \in V_{small}$ terminates after at most $\log^2 \log R$ steps and has only 
had root vertices of type at most $\log R$.
In this case, by Lemma~\ref{lem:relAngle} the angle gained at every single step is at most $2.5\exp(\log R-R/2)$.
Hence, the total angle gained during the process in both directions is at most $5\exp(\log R-R/2) \log^2 \log R$. 
(This justifies the name $V_{small}$: the total angle of the component of $v$ is bounded by this expression which is a 
decaying function of $N$.)

Now, Lemmas \ref{lem:stop} and \ref{lem:high} imply that there exists a positive constant $c$ such that for a vertex $v \in V_{low}$  	
we have $\P (v \in V_{large} \ | \ v \in V_{low}) =  o \left(\left( \frac{\log\log R}{\log R} \right)^c \right)$. 
Thereby, 
$$ \mathbb{E} (|V_{large}|) = o \left( N\left( \frac{\log\log R}{\log R} \right)^c \right). $$
Hence, by Markov's inequality, a.a.s. 
$$ |V_{large}| \leq \frac{N}{2 \log \log R}. $$
Also, using Lemma~\ref{lem:dist} and the concentration of the Poisson distribution, we can deduce that a.a.s. 
$$ |V_{high}| \leq \frac{N}{2 \log \log R}. $$ 
Thus, a.a.s. 
$$|V_{large}\cup V_{high}| \leq \frac{N}{\log \log N}.$$ 
Now, by Lemma~\ref{lem:dense_sectors}, a.a.s. every vertex in $V_{small}$ is contained in a component with at most 
	$10N\exp(\log R-R/2)\log^2\log R < 10 \nu R \log^2 \log R$ vertices.  
Hence, any component of large size must be induced by vertices in $V_{large} \cup V_{high}$,
whereby $|L_1| \leq \frac{N}{\log \log R}$. 
% 	For any vertex $v$ of type at most $\log\log\log R$, Lemmas~\ref{lem:high} and~\ref{lem:stop} imply that there is some 
%     $0<\hat{c}$ such that with
% 	probability at least $1-o\left(\frac{(\log\log R)^{\hat{c}}}{(\log R)^{\hat{c}}}\right)$ 
% 	Using Markov's inequality, the number of vertices for which the smooth breadth exploration process does not terminate as above is
% 	a.a.s. at most $N\frac{(\log\log R)^{c^\prime}}{(\log R)^{c^\prime}}<\frac{N}{2\log\log\log R}$, where $c^\prime>0$.
% 	Note that by Lemma~\ref{lem:dist} the expected number of vertices of type at least $\log\log\log R$ is $(1+o(1))\frac{N}{\log\log R}$
% 	and so by Markov's inequality a.a.s. the number of vertices of type at least $\log\log\log R$ is at most $\frac{N}{2\log\log\log R}$.
% 	Thus a.a.s. the largest component has size at most $\frac{N}{\log\log\log R}$.
\end{proof}


To prove the lemmas, we simplify the process in a way that allows for any real types, dropping the $0\leq t\leq R$ requirement.
We use the following cdf and pdf for the type $T_i$ of $v_i$ given the type $t_{i-1}$ of $v_{i-1}$:
\begin{align}\label{eqn:cdf}
	F_{T_i}(t)=&\ \exp\left({-4\nu\frac{1.01}{\pi}e^{\frac12(t_{i-1}-t)}}\right)\\
	f_{T_i}(t)=&\ 2\nu\frac{1.01}{\pi}e^{\frac12(t_{i-1}-t)}\exp\left({-4\nu\frac{1.01}{\pi}e^{\frac12(t_{i-1}-t)}}\right).
\end{align}
\begin{claim}
	Lemmas~\ref{lem:stop} and~\ref{lem:high} hold if they hold for the extended and simplified distribution of types in Equation~(\ref{eqn:cdf}),
	where not finding a next neighbour in the original distribution corresponds to a negative type in the extended one.
\end{claim}
\begin{proof}
	We prove the result by showing that the given cdf is a lower bound on the actual cdf at any point.
	This means there is a coupling in which any vertex of the actual distribution is coupled with a vertex of higher or equal type and same angle in
	the simplified distribution.
%	This means that the type of the currently active vertex is never lower than in the original process.
	We later prove that the distance we change the type by does not depend on the type of the active vertex for the vertices that we consider,
	so a higher type cannot have a negative influence on the result we want to prove.
	If the type of a vertex is less than $\log R$, we can use Lemma~\ref{lem:relAngle} with $\eps=0.009$ to get a bound on the relative angle for
	possibly adjacent vertices up to type $R-2\log R<R-\log R-c_0(0.009)$ for sufficiently large $N$.
	Note that the expected number of vertices of type larger than $R-2\log R$ is
	\[N\frac{\cosh(2\log R)-1}{\cosh(R)-1}=o(1).\]
	Thus the probability of having such a vertex is $o(1)$ and we can condition on no such vertex existing.
	We use outer tubes to estimate the expected value of $N_{t_0}^t$, the number of neighbours of type at least $t$ of a vertex of type
	$t_0\leq \log R$, using the outer tubes for $\eps=0.009$ as an upper bound, taking $N$ large enough and using Lemma~\ref{lem:dist}:
	\begin{align*}
		\Ee N_{t_0}^t\lesssim &N\int_t^{R-2\log R}2\frac{1.009}{\pi}e^{\frac12(t_0+t'-R)}e^{-t'}dt'\\
			\leq&\ \nu e^{\frac12 R}\int_t^{R-2\log R}2\frac{1.01}{\pi}e^{\frac12(t_0+t'-R)}e^{-t'}dt'\\
			=&\ 2\nu\frac{1.01}{\pi}e^{\frac{t_0}{2}}\int_t^{R-2\log R}e^{-\frac12t'}dt'\\
			\leq&\ 2\nu\frac{1.01}{\pi}e^{\frac{t_0}{2}}\int_t^{\infty}e^{-\frac12t'}dt'\\
			=&\ 4\nu\frac{1.01}{\pi}e^{\frac12(t_0-t)}.
	\end{align*}
	With this, as we are using the Poisson distribution, we get the following cdf for the distribution of the next type,
	given we are at step $i$ with type $t_0$:
	\begin{align*}
		F_{T_i}(t)&=\P(T_{i}\leq t|T_{i-1}=t_0)=\P(|N_{t_0}^t|=0)\\
			&=\exp(-\Ee(N_{t_0}^t))\geq\exp\left(-4\nu\frac{1.01}{\pi}e^{\frac12(t_0-t)}\right).
	\end{align*}
\end{proof}
To prove the two lemmas we need to introduce new notation.
Instead of looking at the types of the vertices at some step, we analyse the jump $J_i=T_i-T_{i-1}$ in some step,
the difference in types from one step to the next.
This makes sense as $F_{T_i}(t)$ only depends on the difference of $T_i$ and $t$, each jump is distributed as
\begin{align*}
	F_J (j)=&\ \exp\left(-4\nu\frac{1.01}{\pi}e^{-\frac j2}\right)\\
	f_{J} (j) =&\ 2\nu\frac{1.01}{\pi}e^{-\frac j2}\exp\left({-4\nu\frac{1.01}{\pi}e^{-\frac j2}}\right).
\end{align*}
Starting at a vertex of type $T_0(=\log\log R)$, we write
\[T_i=T_0+\sum_{k=1}^i J_k,\]
where we couple with a sequence of independent random variables having as their cdf the function $F_J$.
The type $T_i$ is thus coupled with the sum of independent copies of the jump.

We are now ready to prove Lemma~\ref{lem:high}.
\begin{proof}[Proof of Lemma~\ref{lem:high}]
	We first calculate the following expectation: for $s>0$ we have
	\begin{align*}
		\Ee e^{sJ_k}&=\int_{-\infty}^{\infty}e^{sx}2\nu\frac{1.01}{\pi}e^{-\frac x2}\exp\left({-4\nu\frac{1.01}{\pi}e^{-\frac x2}}\right)dx\\
			&=2\nu\frac{1.01}{\pi}\int_{-\infty}^{\infty}e^{(s-\frac12)x}\exp\left({-4\nu\frac{1.01}{\pi}e^{-\frac x2}}\right)dx.
	\end{align*}
	Changing variables $y=4\nu\frac{1.01}{\pi}e^{-\frac x2}$, $dy=-2\nu\frac{1.01}{\pi}e^{-\frac x2}dx$ we get
	$e^{sx}=\left(4\nu\frac{1.01}{\pi y}\right)^{2s}$ and
	\begin{align*}
		\Ee e^{sJ_k}&=-\int_{\infty}^{0}\left(4\nu\frac{1.01}{\pi y}\right)^{2s}e^{-y}dy
			=\left(4\nu\frac{1.01}{\pi}\right)^{2s}\int_{0}^{\infty}y^{-2s}e^{-y}dy\\
			&=\left(4\nu\frac{1.01}{\pi}\right)^{2s}\int_{0}^{\infty}y^{(1-2s)-1}e^{-y}dy=\left(4\nu\frac{1.01}{\pi}\right)^{2s}\Gamma(1-2s).
	\end{align*}
	
	Given a starting vertex of type $\log\log R$, we calculate, for large $N$, the probability of reaching type at least $\log R$ in any step
	$i<\log\log R$.
	For $s>0$ arbitrary we have
	\begin{align*}
		\P(T_i\geq\log R)&=\P(T_0+\sum_{k=1}^iJ_k\geq\log R)\leq\P(\sum_{k=1}^iJ_k\geq\frac12\log R)\\
			&=\P(e^{s\sum_{k=1}^iJ_k}\geq e^{\frac s2\log R})\\
			&\leq\Ee e^{s\sum_{k=1}^iJ_k}e^{-\frac s2\log R}\\
			&=e^{-\frac s2\log R}\prod_{k=1}^i\Ee e^{sJ_k},
	\end{align*}
	using Markov's inequality.
	Choosing $0<s<\frac12$ arbitrarily, we get some constant $C>1$ such that $\Ee e^{sJ_k}=C$. Thus
	\begin{align*}
		\P(T_i\geq\log R)&\leq e^{-\frac s2\log R}C^i\leq e^{-\frac s2\log R}C^{\log^2\log R}=o(R^{-c}),
	\end{align*}
	for some $0<c=c(s)<1$.
	With this, we can use the union bound to bound the probability that the smooth breadth exploration process has type at least $\log R$
	at one of the first $\log^2\log R$ steps:
	\[
		\P(\exists 0<i\leq\log^2 \log R: T_i\geq\log R)\leq\sum_{i=1}^{\log^2\log R}\P(T_i\geq\log R)=o\left(\frac{\log^2 \log R}{R^c}\right). \qedhere
	\]
\end{proof}
	We use the same technique to prove Lemma~\ref{lem:stop}
\begin{proof}[Proof of Lemma~\ref{lem:stop}]
	We would like to determine the probability that the process $(T_i)_{i\geq 0}$ crosses 0 by step $M:=\log^2\log R$.
	We have
	\begin{align*}
		\P(T_M\geq 0)&=\P(T_0+\sum_{k=1}^MJ_k\geq0)\leq \P(\sum_{k=1}^MJ_k\geq -\log\log R)\\
			&\stackrel{s>0}{=}\P(e^{s\sum_{k=1}^M J_k}\geq e^{-s\log\log R})\\
			&\leq(\log R)^s\prod_{k=1}^M\Ee e^{sJ_k},
	\end{align*}
	again using Markov's inequality.
	As $\nu<\frac{\pi}{8}$ and using the calculations from the proof of Lemma~\ref{lem:high}, we can find $0<s<\frac12$ and $0<\hat c<1$ such that for $1\leq k\leq M$
	\[\Ee e^{sJ_k}\leq\left(4\nu\frac{1.01}{\pi}\right)^{2s}\Gamma(1-2s)=\hat c<1.\]
	With this we have
	\begin{align*}
		\P(T_M\geq 0)&\leq(\log R)^s\hat{c}^{\log^2 \log R}=o\left( \left( \frac{\log\log R}{\log R}\right)^c \right),
	\end{align*}
	for some $c>0$.
	Thus $\P(T_M<0)=1-o\left(\left( \frac{\log\log R}{\log R} \right)^c \right)$.
\end{proof}

\subsection{The supercritical case}
For the second part of Theorem~\ref{thm:crit}, we split the disk $\D$ into cells so that the expected number of vertices in each cell is constant.
Furthermore, the cells are defined so that if two neighbouring cells contain at least one vertex each, then these vertices are adjacent.
With some rules for adjacencies of the cells we can then explore
possible components and estimate the number of vertices in them by the number of cells that correspond to them.

For the discretisation, we define the sequence $t_i=i\log2$ for $0\leq i\leq \left\lceil\frac{R}{4\log2}\right\rceil=:T$.
Using this, we define the bands $B_i=\{p\in\D:t_{i-1}\leq t_p<t_i\}$, for $1\leq i\leq T$.
Let $M=2^T\left\lceil\frac{2\pi}{2^T0.95e^{-R/2}}\right\rceil$.
For each $i$, we split band $B_i$ into $M/2^{i-1}$ cells $C_j^{(i)}$, starting at angle $0$ with $j=1$.
Note that the definition of $M$ implies that the projection of a cell in $B_i$ is exactly split into two in $B_{i-1}$.
See Figure~\ref{fig:discrete} for an example of the discretisation.
\begin{figure}
	\centering
	\begin{tikzpicture}[thick, scale=1.5]
		\begin{scope}
		\clip[draw] (266:50) rectangle (274.45:45);
		\draw[gray]{
		(0:0) circle (45)
		(0:0) circle (46)
		(0:0) circle (47)
		(0:0) circle (48)
		(0:0) circle (49)
		};
		\foreach \x in {266,270,274} {
  		\draw[gray] (\x:44)--(\x:50);
		}
		\foreach \x in {268,272} {
  		\draw[gray] (\x:45)--(\x:50);
		}
		\foreach \x in {267,269,...,273} {
  		\draw[gray] (\x:46)--(\x:50);
		}
		\foreach \x in {266.5,267.5,...,273.5} {
  		\draw[gray] (\x:47)--(\x:50);
		}
		\foreach \x in {266.25,266.75,...,273.75} {
  		\draw[gray] (\x:48)--(\x:50);
		}
		\foreach \x in {266.125,266.25,...,273.875} {
  		\draw[gray] (\x:49)--(\x:50);
		}
		\draw{
		%#1
		(266.5:45.3) node[s]{} (266.89:45.8) node[s]{} (270.2:45.7) node[s]{} (273.9:45.63) node[s]{}
		%#2
		(266.35:46.23) node[s]{} (268.78:46.8) node[s]{} (271.3:46.9) node[s]{} (272.4:46.8) node[s]{} (272.7:46.24) node[s]{} (273.33:46.84) node[s]{}
		%#3
		(266.15:47.53) node[s]{} (267.38:47.84) node[s]{} (267.65:47.93) node[s]{} (268.07:47.84) node[s]{} (268.79:47.23) node[s]{}
		(270.45:47.97) node[s]{} (270.85:47.43) node[s]{} (271.21:47.13) node[s]{} (271.465:47.88) node[s]{} (271.07:47.72) node[s]{}
		(272.26:47.43) node[s]{} (273.18:47.823) node[s]{} (273.9:47.49) node[s]{}
		%#4
		(266.20:48.73) node[s]{} (266.62:48.84) node[s]{} (266.81:48.18) node[s]{} (267.33:48.82) node[s]{} (267.66:48.74) node[s]{}
		(267.94:48.67) node[s]{} (267.79:48.85) node[s]{} (268.43:48.37) node[s]{} (268.70:48.94) node[s]{} (269.06:48.73) node[s]{}
		(269.63:48.71) node[s]{} (269.91:48.93) node[s]{}	(270.14:48.94) node[s]{} (270.58:48.52) node[s]{} (270.69:48.08) node[s]{}
		(271.55:48.73) node[s]{} (271.63:48.61) node[s]{} (271.69:48.94) node[s]{} (271.72:48.87) node[s]{} (272.07:48.98) node[s]{}
		(272.36:48.27) node[s]{} (272.74:48.73) node[s]{} (272.80:48.97) node[s]{} (273.14:48.83) node[s]{}	(273.29:48.43) node[s]{}
		(273.70:48.86) node[s]{} (273.96:48.72) node[s]{}
		%#5
		(266.08:49.84) node[s]{} (266.19:49.94) node[s]{} (266.29:49.73) node[s]{} (266.58:49.84) node[s]{} (266.65:49.10) node[s]{}
		(266.71:49.76) node[s]{} (266.84:49.77) node[s]{} (267.04:49.82) node[s]{} (267.19:49.64) node[s]{} (267.58:49.33) node[s]{}
		(267.52:49.54) node[s]{} (267.69:49.82) node[s]{}	(267.79:49.78) node[s]{} (267.80:49.61) node[s]{} (267.88:49.48) node[s]{}
		(267.96:49.23) node[s]{} (268.29:49.35) node[s]{} (268.36:49.84) node[s]{} (268.39:49.75) node[s]{} (268.48:49.83) node[s]{}
		(268.63:49.64) node[s]{} (268.69:49.78) node[s]{} (268.79:49.59) node[s]{} (268.89:49.72) node[s]{}	(269.19:49.79) node[s]{}
		(269.35:49.75) node[s]{} (269.59:49.64) node[s]{} (269.68:49.32) node[s]{} (269.74:49.81) node[s]{} (269.94:49.72) node[s]{}
		(270.03:49.58) node[s]{} (270.09:49.80) node[s]{} (270.29:49.43) node[s]{} (270.65:49.74) node[s]{} (270.74:49.15) node[s]{}
		(270.79:49.74) node[s]{} (270.89:49.26) node[s]{} (271.05:49.09) node[s]{} (271.09:49.74) node[s]{} (271.11:49.68) node[s]{}
		(271.18:49.81) node[s]{} (271.39:49.69) node[s]{} (271.42:49.83) node[s]{} (271.54:49.74) node[s]{} (271.78:49.65) node[s]{}
		(271.82:49.42) node[s]{} (271.98:49.83) node[s]{} (272.06:49.17) node[s]{} (272.15:49.82) node[s]{} (272.23:49.54) node[s]{}
		(272.33:49.83) node[s]{} (272.45:49.81) node[s]{} (272.51:49.79) node[s]{} (272.59:49.48) node[s]{} (272.79:49.26) node[s]{}
		(272.89:49.90) node[s]{} (273.10:49.83) node[s]{} (273.31:49.92) node[s]{} (273.39:49.73) node[s]{} (273.47:49.38) node[s]{}
		(273.67:49.84) node[s]{} (273.71:49.86) node[s]{} (273.76:49.95) node[s]{} (273.79:49.74) node[s]{} (273.82:49.83) node[s]{}
		};
		\draw (266:50) rectangle (274.45:45);
		\end{scope}
		\draw [decorate,decoration={brace,amplitude=5pt,mirror,raise=4pt},yshift=0pt]
			(274:50) -- ($(274:50)+(0,1)$) node [plain,black,midway,xshift=0.8cm] {\footnotesize$B_1$};
		\draw [decorate,decoration={brace,amplitude=5pt,mirror,raise=4pt},yshift=0pt]
			($(274:50)+(0,1)$) -- ($(274:50)+(0,2)$) node [plain,black,midway,xshift=0.8cm] {\footnotesize$B_2$};
		\draw [decorate,decoration={brace,amplitude=5pt,mirror,raise=4pt},yshift=0pt]
			($(274:50)+(0,2)$) -- ($(274:50)+(0,3)$) node [plain,black,midway,xshift=0.8cm] {\footnotesize$B_3$};
		\draw [decorate,decoration={brace,amplitude=5pt,mirror,raise=4pt},yshift=0pt]
			($(274:50)+(0,3)$) -- ($(274:50)+(0,4)$) node [plain,black,midway,xshift=0.8cm] {\footnotesize$B_4$};
		\draw [decorate,decoration={brace,amplitude=5pt,mirror,raise=4pt},yshift=0pt]
			($(274:50)+(0,4)$) -- ($(274:50)+(0,5)$) node [plain,black,midway,xshift=0.8cm] {\footnotesize$B_5$};
	\end{tikzpicture}
	\caption{The discretisation of $\D$.}\label{fig:discrete}
\end{figure}
As $2^T=o(e^\frac{R}{2})$, it follows that $M = 2^T \frac{2\pi}{2^T0.95e^{-R/2}}(1+ o(1))$, whereby the number of cells in band $i$ is $(1+o(1))\frac{2\pi e^{R/2}}{2^{i-1}0.95}$.
We claim the following property:
\begin{lemma}\label{lem:adjacency}
	Any vertex in cell $C_j^{(i)}$ is adjacent to any vertex in any of the cells $C_{j-1}^{(i)}$, $C_{j+1}^{(i)}$, $C_{2\cdot j-1}^{(i-1)}$,
	$C_{2\cdot j}^{(i-1)}$ and $C_{\lceil j/2\rceil}^{(i+1)}$, where we let $C_{0}^{(i)}=C_{M/2^{i-1}}^{(i)}$ and $C_{M/2^{i-1}+1}^{(i)}=C_{1}^{(i)}$.
\end{lemma}
\begin{proof}
	This configuration of cells is illustrated on the left part of Figure~\ref{fig:neighbours}.
	As we consider vertices of type at most $R/4+\log 2$, Lemma~\ref{lem:relAngle} implies that
	any two of these vertices are connected if their relative angle is at most $1.92 e^{1/2(t_u+t_v-R)}$, provided that $N$ is large enough.
	
	The vertices in $C_{j}^{(i)}$ have type at least $t_{i-1}=(i-1)\log2$ and the relative angle of a vertex $v$ in $C_{j-1}^{(i)}$ and $u$ in
	$C_{j}^{(i)}$ is at most $2^{i-1}~2 \cdot 0.96~e^{-R/2}=1.92e^{-R/2+(i-1)\log2}\leq1.92e^{1/2(t_u+t_v-R)}$, so $v$ and $u$ are
 adjacent.
	The same bounds on the maximum relative angle and minimum type hold for vertices $u'$ in $C_{j}^{(i)}$ and $v'$ in $C_{\lceil j/2\rceil}^{(i+1)}$,
	so $u'$ and $v'$ are adjacent.
	By simple change of variables we get all the desired adjacencies.
\end{proof}

We define two auxiliary graphs, a blue graph $G_b$ and a red graph $G_r$.
The vertices of the blue graph will be those cells that contain at least one vertex, whereas the vertices of the red graph are those that contain no
vertex.
Two vertices of $G_b$ are connected if the corresponding cells share an edge.
This means that vertices of $\Pnan$ in the cells corresponding to adjacent vertices in $G_b$ are themselves adjacent by Lemma~\ref{lem:adjacency}.
Two vertices of $G_r$ are connected if their corresponding cells share at least a point.
This corresponds to the same adjacency as in $G_b$ but with added ``diagonal'' edges.
These adjacencies are illustrated in Figure~\ref{fig:neighbours}.
\begin{figure}
	\centering
	\begin{tikzpicture}[very thick, scale=1.5]
		\clip (268:48) rectangle ($(272.15:45)+(-.85,0)$);
		\draw[gray]{
		(0:0) circle (45)
		(0:0) circle (46)
		(0:0) circle (47)
		};
		\foreach \x in {270} {
  		\draw[gray] (\x:44)--(\x:50);
		}
		\foreach \x in {268,272} {
  		\draw[gray] (\x:45)--(\x:50);
		}
		\foreach \x in {267,269,...,273} {
  		\draw[gray] (\x:46)--(\x:50);
		}
		\foreach \x in {266.5,267.5,...,273.5} {
  		\draw[gray] (\x:47)--(\x:50);
		}
		\draw[blue]{
			(269:45.5) node[l,blue]{} -- (269.5:46.5) node[l,blue]{} (269.5:46.5) node[l,blue]{} -- (268.5:46.5) node[l,blue]{}
			(269.25:47.5) node[l,blue]{} -- (269.5:46.5) (269.5:46.5) -- (269.75:47.5) node[l,blue]{}
			(270.5:46.5) node[l,blue]{} -- (269.5:46.5)
		};
		\draw[thick] (268:48) rectangle ($(272.15:45)+(-.85,0)$);
	\end{tikzpicture}
	\begin{tikzpicture}[very thick, scale=1.5]
		\clip (268:48) rectangle (272.15:45);
		\draw[gray]{
		(0:0) circle (45)
		(0:0) circle (46)
		(0:0) circle (47)
		};
		\foreach \x in {270} {
  		\draw[gray] (\x:44)--(\x:50);
		}
		\foreach \x in {268,272} {
  		\draw[gray] (\x:45)--(\x:50);
		}
		\foreach \x in {267,269,...,273} {
  		\draw[gray] (\x:46)--(\x:50);
		}
		\foreach \x in {266.5,267.5,...,273.5} {
  		\draw[gray] (\x:47)--(\x:50);
		}
		\draw[red]{
			(269:45.5) node[l,red]{} -- (269.5:46.5) node[l,red]{} -- (268.5:46.5) node[l,red]{}
			(269.25:47.5) node[l,red]{} -- (269.5:46.5) -- (269.75:47.5) node[l,red]{}
			(270.5:46.5) node[l,red]{} -- (269.5:46.5) -- (271:45.5) node[l,red]{}
			(268.75:47.5) node[l,red]{} -- (269.5:46.5) -- (270.25:47.5) node[l,red]{}
		};
		\draw[thick] (268:48) rectangle (272.15:45);
	\end{tikzpicture}
	\caption{Blue(left) and red(right) neighbourhood.}\label{fig:neighbours}
\end{figure}
\begin{figure}
	\centering
	\begin{tikzpicture}[thick, scale=1.5]
		\clip[draw] (266:50) rectangle (274.45:45);
		\draw[gray]{
		(0:0) circle (45)
		(0:0) circle (46)
		(0:0) circle (47)
		(0:0) circle (48)
		(0:0) circle (49)
		};
		\foreach \x in {266,270,274} {
  		\draw[gray] (\x:44)--(\x:50);
		}
		\foreach \x in {268,272} {
  		\draw[gray] (\x:45)--(\x:50);
		}
		\foreach \x in {267,269,...,273} {
  		\draw[gray] (\x:46)--(\x:50);
		}
		\foreach \x in {266.5,267.5,...,273.5} {
  		\draw[gray] (\x:47)--(\x:50);
		}
		\foreach \x in {266.25,266.75,...,273.75} {
  		\draw[gray] (\x:48)--(\x:50);
		}
		\foreach \x in {266.125,266.25,...,273.875} {
  		\draw[gray] (\x:49)--(\x:50);
		}
		\draw[blue]{
			(267:45.5) node[blue]{} -- (266.5:46.5) node[blue]{} -- (266.25:47.5) node[blue]{} -- (266.125:48.5) node[blue]{} -- (266.0625:49.5) node[blue]{}
				-- (266.0625+0.125:49.5) node[blue]{} -- (266.125:48.5) (266.0625+2*0.125:49.5) node[blue]{} -- (266.0625+0.125:49.5)
			(266.625:48.5) node[blue]{} -- (266.875:48.5) node[blue]{} -- (266.0625+6*0.125:49.5) node[blue]{} -- (266.0625+5*0.125:49.5) node[blue]{}
				-- (266.0625+4*0.125:49.5) node[blue]{} -- (266.625:48.5) -- (266.0625+5*0.125:49.5)
			(266.0625+8*0.125:49.5) node[blue]{} -- (266.0625+9*0.125:49.5) node[blue]{}
			(268.5:46.5) node[blue]{} -- (268.25:47.5) node[blue]{} -- (268.75:47.5) node[blue]{} -- (268.5:46.5)
			(268.25:47.5) -- (267.75:47.5) node[blue]{} -- (267.25:47.5) node[blue]{} -- (267.375:48.5) node[blue]{} -- (267.625:48.5) node[blue]{}
				-- (267.75:47.5) -- (267.875:48.5) node[blue]{} -- (267.625:48.5) -- (266.0625+12*0.125:49.5) node[blue]{}
				-- (266.0625+13*0.125:49.5) node[blue]{} -- (267.625:48.5) (267.875:48.5) -- (266.0625+15*0.125:49.5) node[blue]{}
				-- (266.0625+14*0.125:49.5) node[blue]{} -- (267.875:48.5) (266.0625+13*0.125:49.5) -- (266.0625+14*0.125:49.5)
			(268.25:47.5) -- (268.375:48.5) node[blue]{} -- (266.0625+18*0.125:49.5) node[blue]{} -- (266.0625+19*0.125:49.5) node[blue]{}
				-- (268.375:48.5) -- (268.625:48.5) node[blue]{} -- (266.0625+21*0.125:49.5) node[blue]{} -- (266.0625+22*0.125:49.5) node[blue]{}
				-- (266.0625+23*0.125:49.5) node[blue]{} (268.625:48.5) -- (268.75:47.5)
			(273:45.5) node[blue]{} -- (271:45.5) node[blue]{} -- (271.5:46.5) node[blue]{} -- (272.5:46.5) node[blue]{}
				-- (273.5:46.5) node[blue]{} -- (273:45.5) -- (272.5:46.5) -- (272.25:47.5) node[blue]{} -- (272.125:48.5) node[blue]{}
				-- (272.0625:49.5) node[blue]{} -- (272.0625+0.125:49.5) node[blue]{} -- (272.125:48.5) -- (272.375:48.5) node[blue]{} -- (272.25:47.5)
			(272.0625+0.125:49.5) -- (272.0625+2*0.125:49.5) node[blue]{} -- (272.0625+3*0.125:49.5) node[blue]{} -- (272.375:48.5)
				-- (272.0625+2*0.125:49.5) (272.0625+3*0.125:49.5) -- (272.0625+4*0.125:49.5) node[blue]{} -- (272.625:48.5) node[blue]{}
				-- (272.375:48.5) (272.625:48.5) -- (272.875:48.5) node[blue]{} -- (272.0625+6*0.125:49.5) node[blue]{}
				-- (272.0625+7*0.125:49.5) node[blue]{} -- (272.875:48.5) -- (273.125:48.5) node[blue]{} -- (273.0625:49.5) node[blue]{}
				-- (272.0625+7*0.125:49.5) (273.375:48.5) node[blue]{} -- (273.125:48.5) -- (273.25:47.5) node[blue]{} -- (273.375:48.5)
				-- (273.0625+2*0.125:49.5) node[blue]{} -- (273.0625+3*0.125:49.5) node[blue]{} -- (273.375:48.5) -- (273.625:48.5) node[blue]{}
				-- (273.0625+5*0.125:49.5) node[blue]{} -- (273.0625+6*0.125:49.5) node[blue]{} -- (273.875:48.5) node[blue]{} -- (273.625:48.5)
				-- (273.75:47.5) node[blue]{} -- (273.25:47.5) -- (273.5:46.5) -- (273.75:47.5) -- (273.875:48.5) (272.0625:49.5)
				-- (272.0625-0.125:49.5) node[blue]{} -- (272.0625-2*0.125:49.5) node[blue]{}
			(271.5:46.5) -- (271.25:47.5) node[blue]{} -- (270.75:47.5) node[blue]{} -- (270.25:47.5) node[blue]{} -- (270.125:48.5) node[blue]{}
				-- (269.875:48.5) node[blue]{} -- (269.625:48.5) node[blue]{} -- (269.5625:49.5) node[blue]{} -- (269.6875:49.5) node[blue]{} -- (269.625:48.5)
			(269.875:48.5) -- (269.6875+2*0.125:49.5) node[blue]{} -- (269.6875+3*0.125:49.5) node[blue]{} -- (270.125:48.5)
			(270.75:47.5) -- (270.625:48.5) node[blue]{} -- (271.0625-3*0.125:49.5) node[blue]{} -- (271.0625-2*0.125:49.5) node[blue]{}
				-- (271.0625-0.125:49.5) node[blue]{} -- (271.0625:49.5) node[blue]{} -- (271.0625+0.125:49.5) node[blue]{}
			(272.0625-5*0.125:49.5) node[blue]{} -- (272.0625-4*0.125:49.5) node[blue]{} -- (271.625:48.5) node[blue]{}
			(269.125:48.5) node[blue]{} -- (269.0625+1*0.125:49.5) node[blue]{} -- (269.0625+2*0.125:49.5) node[blue]{}
			(270.0625+2*0.125:49.5) node[blue]{}
		};
		\draw[red]{
			(266.0625+3*0.125:49.5) node[red]{} -- (266.375:48.5) node[red]{} -- (266.75:47.5) node[red]{} -- (267.125:48.5) node[red]{}
				-- (267.0625-0.125:49.5) node[red]{} (267.0625+3*0.125:49.5) node[red]{} -- (267.0625+2*0.125:49.5) node[red]{} -- (267.125:48.5)
			(266.75:47.5) -- (267.5:46.5) node[red]{} -- (269:45.5) node[red]{} -- (269.5:46.5) node[red]{} -- (270.5:46.5) node[red]{}
				-- (269.75:47.5) node[red]{} -- (269.25:47.5) node[red]{} -- (269.5:46.5) -- (269.75:47.5) -- (269.375:48.5) node[red]{}
				-- (269.0625+3*0.125:49.5) node[red]{} (269:45.5) -- (270.5:46.5) (269.375:48.5) -- (269.25:47.5) -- (268.875:48.5) node[red]{}
				-- (269.0625:49.5) node[red]{}
			(268.5625:49.5) node[red]{}
			(268.0625:49.5) node[red]{} -- (268.1875:49.5) node[red]{} -- (268.125:48.5) node[red]{} -- (268.0625:49.5)
			(269.0625+6*0.125:49.5) node[red]{}
			(270.0625+0.125:49.5) node[red]{} -- (270.375:48.5) node[red]{} -- (270.0625+3*0.125:49.5) node[red]{} -- (270.0625+4*0.125:49.5) node[red]{}
				-- (270.375:48.5)
			(272.75:47.5) node[red]{}
			(270.875:48.5) node[red]{} -- (271.125:48.5) node[red]{} -- (271.0625+2*0.125:49.5) node[red]{} -- (271.375:48.5) node[red]{} -- (271.125:48.5)
			(271.375:48.5) -- (271.75:47.5) node[red]{} -- (271.875:48.5) node[red]{} -- (271.0625+5*0.125:49.5) node[red]{}
			(272.0625+5*0.125:49.5) node[red]{}
			(273.0625+0.125:49.5) node[red]{}
			(273.0625+4*0.125:49.5) node[red]{}
			(273.0625+7*0.125:49.5) node[red]{}
		};
		\draw[thick] (266:50) rectangle (274.45:45);
	\end{tikzpicture}
	\caption{$G_c$ resulting from the Graph in Figure~\ref{fig:discrete}.}\label{fig:Gc}
\end{figure}
%
%\begin{align*}
%	V(G_b)&=\{v_{i,j}:C_{j}^{(i)}\text{ contains at least one vertex}\}\\
%	V(G_r)&=\{v_{i,j}:C_{j}^{(i)}\text{ contains no vertex}\}.
%\end{align*}
%Whenever it helps clarity we will refer to the vertices of the graphs as cells.
%The edge sets are the following:
%\begin{align*}
%	E(G_b)=\{&v_{i,j}v_{i,j+1},v_{i,j}v_{i,j-1},v_{i,j}v_{i-1,2\cdot j},v_{i,j}v_{i-1,2\cdot j-1},v_{i,j}v_{i+1,\lceil j/2\rceil}\}\\
%	E(G_r)=\{&v_{i,j}v_{i,j+1},v_{i,j}v_{i,j-1},v_{i,j}v_{i-1,2\cdot j-2},v_{i,j}v_{i-1,2\cdot j-1},v_{i,j}v_{i-1,2\cdot j},\\
%					&v_{i,j}v_{i-1,2\cdot j+1},v_{i,j}v_{i+1,\lceil j/2\rceil},v_{i,j}v_{i+1,\lceil j/2\rceil+1}\},
%\end{align*}
%if the relevant vertices exist.
%Note that two cells in the blue graph are adjacent if they share an edge, two cells in the red graph are adjacent if they share at least a point,
%i.e. they share an edge or just a corner.
%We can now join the two graphs to form the coloured graph $G_c$ that has red and blue vertices and edges.
We denote by $G_c$ the union of the two graphs.
For the graph resulting from the example in Figure~\ref{fig:discrete}, see Figure~\ref{fig:Gc}.
Whenever necessary we will refer to the vertices of the graphs as cells.
A \textit{blue component} is a component of $G_c$ that consists of blue vertices.
A \textit{red path} is a path in $G_c$ that consists of red vertices.
These are the main structures we use, but we also use the red/blue notation for other structures.
Because of the adjacency rules, a blue component is always surrounded by a red path or a collection of red paths,
the periphery and the inside of the disk.
We are now interested in the probability of a vertex being blue or red.
Note that
\begin{equation} \label{eq:Bound_on_M} 
M=2^T\left\lceil\frac{2\pi}{2^T0.95e^{-R/2}}\right\rceil\leq\frac{2\pi}{0.95e^{-R/2}}+2^T\leq\frac{2\pi+2^Te^{-R/2}}{0.95e^{-R/2}}.
\end{equation}
\begin{claim}\label{clm:prob}
	The probability of a vertex in $G_c$ being red is at most $e^{-\frac{\nu}{5\pi}}$,
	the probability of being blue is at least $1-e^{-\frac{\nu}{5\pi}}$.
\end{claim}
\begin{proof}
	Let $v_{i,j}$ be a vertex of $G_c$ that corresponds to $C_i^{(j)}$. Let $P_i^{(j)}$ be the number of vertices in $C_i^{(j)}$.
	Using Lemma~\ref{lem:dist} and the above upper bound on $M$ (\ref{eq:Bound_on_M}), we have for large $N$ 
	\begin{align*}
		\Ee(P_i^{(j)})&=N\int_{t_{i-1}}^{t_i}\frac{2^{i-1}}{M}(1+o(1))e^{-t}dt\\
									&\geq 0.94\nu e^{R/2}\frac{2^{i-1}e^{-R/2}}{2\pi+2^Te^{-R/2}}\int_{t_{i-1}}^{t_i}e^{-t}dt\\
									&\geq 0.94\nu \frac{2^{i-1}}{2\pi+2^{\frac{R}{4\log2}+1}e^{-R/2}}(e^{-t_{i-1}}-e^{-t_i})\\
									&= 0.94\nu \frac{2^{i-1}}{2\pi+2 e^{-R/4}}(e^{-(i-1)\log2}-e^{-i\log2})\\
									&=0.94\nu \frac{2^{i-1}}{2\pi+2 e^{-R/4}}2^{-i}(2-1)\\
									&\geq\frac{\nu}{5\pi},
	\end{align*}
	for $N$ large enough.
	Since the number of vertices in $C_i^{(j)}$ follows the Poisson distribution with parameter $\Ee ( P_i^{(j)})$, we have
	\begin{align*}
		\P(v_{i,j}\text{ red})&=\P(P_i^{(j)}=0)=e^{-\Ee(P_i^{(j)})}\leq e^{-\frac{\nu}{5\pi}}\\
		\P(v_{i,j}\text{ blue})&=\P(P_i^{(j)}>0)=1-e^{-\Ee(P_i^{(j)})}\geq 1-e^{-\frac{\nu}{5\pi}}
	\end{align*}
\end{proof}
Our aim is now to show that there is a blue component of $\eps N$ cells for some $\eps>0$.
Note that this implies that a giant component in $\Pnan$ exists as each of the $\eps N$ cells contain at least one vertex
and the adjacency rules of the vertices of $G_c$ imply that these vertices induce a connected component in $\Pnan$.
Or main tool for proving this is the following lemma that bounds the maximum length of a red path, using an argument
similar to Peierls' argument from percolation theory(see~\cite{bk:Grimmett}~\cite{bk:Penrose}).
\begin{lemma}\label{lem:boundred}
	Let $\nu>20\pi$. A.a.s. all red paths have length at most $L:=T-1=\left\lceil\frac{R}{4\log2}\right\rceil-1$.
\end{lemma}
\begin{proof}
	Note that any cell in the red graph has at most $8$ neighbours.
	The number of cells is at most $M (1 + 1/2 + 1/4+\cdots) = 2M \stackrel{(\ref{eq:Bound_on_M})}{<} {4 \pi \over 0.94} e^{R/2} < 5 \pi e^{R/2}$. 
	As $\nu>20\pi$, this implies that the number of cells is at most $N$.
% as otherwise the expected number of
	%vertices in all of the cells combined would be strictly larger than $N$, the expected number of vertices overall.
	Let $p=\P(v_{i,j}\text{ blue})\geq 1-e^{-\frac{\nu}{5\pi}}\geq 1-e^{-\frac{20\pi}{5\pi}}>0.98$ by Claim~\ref{clm:prob}.
	Thus $8(1-p)<0.2$.
	Let $P_c(\ell)$ be the number of red paths starting at cell $c$ and having length $\ell$.
	We have
	\[\Ee(P_c(\ell))\leq8^\ell(1-p)^\ell=(8(1-p))^\ell<0.2^\ell.\]
	Since the number of cells is at most $N$ we thus can bound the expected number of red paths of length $\ell$ by $0.2^\ell N$.
	Let $c$ be such that $1+c=\frac{\log5}{2\log2}\simeq1.16$.
	The expected number of paths of length at least $L$ is
	\begin{align*}
		N\sum_{\ell\geq L}0.2^\ell&=O\left( N~0.2^L\right)=O\left( e^{R/2}0.2^{\frac{R}{4\log2}}\right)\\
									&=O\left( e^{R/2}e^{-\log5\left(\frac{R}{4\log2}\right)}\right)\\
									&=O\left( e^{R/2}e^{-(1+c)\frac{R}{2}}\right)=O\left(\nu e^{-c\frac{R}{2}}\right)=o(1).
	\end{align*}
	This means the probability of having a red path of length at least $L$ is $o(1)$.
\end{proof}

With this we are able to make statements on the structure of $G_c$.
We prove that a.a.s. there is a \textit{blue lollipop} $L_b$: a blue cycle surrounding the origin of $\D$ that contains a cell in $B_1$
or is connected to such a cell by a blue path (see Figure~\ref{fig:lolli}).
\begin{figure}
	\centering
	\begin{tikzpicture}[thick, scale=0.2]
	\clip (0:0) circle (14);
	\draw[line width=10pt,blue]{
		(270:5) .. controls (30:15) and (150:12) .. (270:5)
		(270:5) .. controls (275:10) .. (270:15)
	};
	\draw[very thick] {(0,0) node{} (0:0) circle (14)};
%		\draw[line width=10pt] (0:5) .. controls (40:7) .. (90:6) .. controls (135:6) .. (180:5.3) .. controls (225:5) .. (270:4)
%			.. controls (315:6) .. (0:5);
	\end{tikzpicture}
	\caption{Blue lollipop.}\label{fig:lolli}
\end{figure}
We call the relevant cell of $B_1$ the \textit{base} of the lollipop.
\begin{claim}\label{clm:lolli}
	Let $\nu>20\pi$. A.a.s. $G_c$ contains a blue lollipop.
\end{claim}
\begin{proof}
	By Lemma~\ref{lem:boundred}, a.a.s. there is no red path of length $L$.
	The number of bands is $T>L$, so a.a.s. there is no red path connecting $B_1$ and $B_T$.
	This implies that there must be a blue cycle $C$ surrounding the origin of $\D$.
	Now, the number of cells in any band is at least
	\[M/2^{T}\geq\frac{2\pi}{2^Te^{-R/2}}\geq\frac{2\pi}{2^{{\frac{R}{4\log2}}+1}e^{-R/2}}=\pi e^{R/4}\geq L\]
	for $N$ sufficiently large, as $L = O(R)$.
	Thus any red cycle surrounding $C$ would have length at least $L$.
	But by Lemma~\ref{lem:boundred} a.a.s. there is no such cycle.
	This implies that $C$ must either contain a cell of $B_1$ or there must be a blue path $P$ connecting $C$ and some cell in $B_1$.
	In either case we have a blue lollipop.
\end{proof}

Starting at the base $c_1$ of the lollipop we will consider the following process traversing the band $B_1$ in clockwise direction:
\begin{itemize}
	\item Starting with $i=1$, do the following steps until $c_1$ is reached again.
	\item Let $c'_i$ be the first red cell in $B_1$ in clockwise direction from $c_i$.
		Let $S_i$ be the number of blue cells from $c_i$ to $c'_i$, including $c_i$.
	\item Let $r_i$ be the red cell on $B_1$ that is farthest away from $c'_i$ in clockwise direction
		and that is connected to $c'_i$ via a red path - if such a cell does not exist, then $r_i = c_i'$.
		Denote by $R_i$ the number of cells of $B_1$ between $c'_i$ and $r_i$ in clockwise direction, including these two.
		Let $c_{i+1}$ be the cell succeeding $r_i$.
\end{itemize}
The process will end at some index $i=K$. Assume that $S_K$ is the number of blue cells between $c_{K}$ and $c_1$ in clockwise direction,
including $c_{K}$ if $c_{K}\neq c_1$ but excluding $c_1$.
Note that the number of cells in $B_1$ is $M=2^T\left\lceil\frac{2\pi}{2^T0.95e^{-R/2}}\right\rceil\geq \frac{2\pi}{\nu}N$.
This means we have $S_K+\sum_{i=1}^{K-1}(S_i+R_i)=M\geq\frac{2\pi}{\nu}N$.
We will prove that a.a.s. $K$ is linear in $N$. We begin with the following properties:

\begin{claim}\label{clm:blueComp}\ 
	\begin{enumerate}
		\item Any two cells $c_i$ and $c_j$ are connected by a blue path for $1\leq i,j\leq K$.
		\item If the red path connecting $c'_i$ and $r_i$ has length $\ell$, then $R_i< 2^{\ell/2+2}$.
	\end{enumerate}
\end{claim}
\begin{proof}\ 
	\begin{enumerate}
		\item Let $\hat c$ be the blue cell preceding $c'_1$.
			If there was no blue path connecting $\hat c$ to $c_2$ then there would be a red path originating at a red cell between $c'_1$ and $c_2$
			and ending in a red cell $\hat{r}_1$ that is farther in the anticlockwise direction from $c'_1$ than $c_2$, thus also farther than
 $r_1$.
			But this means this red path must meet the path from $c'_1$ to $r_1$, creating a path from $c'_1$ to $\hat{r}_1$ --- a contradiction.
%			If there was no blue path connecting $\hat c$ to $c_2$ then there would be a red path reaching a cell on $B_1$ that is farther away
%			from $c'_1$ in the clockwise direction than $r_1$.
%			Note that this is the case as we have a blue cycle surrounding the origin.
			This means that $\hat c$ is connected to $c_2$ via a blue path. But all the cells between $c_1$ and $\hat c$ are blue, so there is a blue path
			from $c_1$ to $c_2$.
			Similarly, we can show that $c_i$ is connected to $c_{i+1}$.
		\item We fix $\ell$ and want to find the path of length $\ell$ between $c_i'$ and $r_i$ that ``encloses" most cells in $B_1$.
			Note that the cells in a band become half as many when we increase the index of the band by one.
			We claim that the optimal path for this choice increases the band by one with each of its first $\lfloor\ell/2\rfloor$ edges,
			stays in the same band for one edge if $\ell$ is odd, and then decreases the band by one for the remaining 
            $\lfloor\ell/2\rfloor$ edges, such as the one in Figure~\ref{fig:maxred}.
			Assume this is not the case, then at least one of the following must be true:
			\begin{itemize}
				\item There is an edge between two cells at the same band that is not of the highest index among all cells in the path.
					Then, taking away this edge and instead inserting one at the highest index, thus shifting the remaining path,
					means that at least one more cell is covered with a path of the same length, a contradiction.
				\item There is an index $i$ such that there are two cells $c_1$ and $c_2$, both in the band $B_i$, that are connected on the path via a
					subpath of length at least $2$ using only cells in the bands $B_1-B_i$.
					In this case we can create a new subpath of the same length that just uses cells in the band $B_{i+1}$ as inner vertices and leading to
					a new cell $c_2'$.
					Because the number of cells doubles in each band this new subpath must cover more cells than the old one and thus we can create a path
					of length $\ell$ that covers more cells, a contradiction.
			\end{itemize}
			So the optimal path has the desired form, as shown in Figure~\ref{fig:maxred}.
%			This implies that we can spend two edges of our path so that every cell on the next band we use weighs twice as much for the number of
%			cells we cover than it would in the band before.
%			These two edges each contribute at most $2^{i-1}$ to the cells covered if we move from band $i$ to band $i+1$.
%			That means that whenever possible it is better to go up and then use the edges than staying on the band
%			and using the edges there.
%			It is also obvious that going down a band before we have to is worse than staying or going up.
			Note that each cell in band $i$ covers $2^{i-1}$ cells in band $B_1$.
			If $\ell$ is odd, this yields $\frac{\ell-1}{2}$ upward/downward edges each and one edge ($2$ cells) staying at the same level, yielding
			$\sum_{i=1}^{(\ell-1)/2}2^{i-1}+2\cdot2^{(\ell-1)/2}=3\cdot2^{(\ell-1)/2}-1<2^{\ell/2+2}$ covered cells.
			If $\ell$ is even, the path uses $\frac{\ell}{2}$ upward/downward edges each and no edge (one cells) staying at the same level, yielding
			$\sum_{i=1}^{\ell/2}2^{i-1}+2^{\ell/2}=2^{\ell/2+1}-1<2^{\ell/2+2}$ covered cells. \qedhere
	\end{enumerate}
\end{proof}

\begin{figure}
	\centering
	\begin{tikzpicture}[thick, scale=1.5]
		\clip[draw] (266:50) rectangle (274.45:45);
		\draw[gray]{
		(0:0) circle (45)
		(0:0) circle (46)
		(0:0) circle (47)
		(0:0) circle (48)
		(0:0) circle (49)
		};
		\foreach \x in {266,270,274} {
  		\draw[gray] (\x:44)--(\x:50);
		}
		\foreach \x in {268,272} {
  		\draw[gray] (\x:45)--(\x:50);
		}
		\foreach \x in {267,269,...,273} {
  		\draw[gray] (\x:46)--(\x:50);
		}
		\foreach \x in {266.5,267.5,...,273.5} {
  		\draw[gray] (\x:47)--(\x:50);
		}
		\foreach \x in {266.25,266.75,...,273.75} {
  		\draw[gray] (\x:48)--(\x:50);
		}
		\foreach \x in {266.125,266.25,...,273.875} {
  		\draw[gray] (\x:49)--(\x:50);
		}
		\draw[teal, very thick, densely dotted]{
			(266.375:48.5) -- (266.0625+2*0.125:49.5) -- (266.0625+3*0.125:49.5) -- (266.375:48.5)
			(266.75:47.5) -- (266.0625+4*0.125:49.5) -- (266.0625+7*0.125:49.5) -- (266.75:47.5)
			(267.5:46.5) -- (266.0625+8*0.125:49.5) -- (266.0625+15*0.125:49.5) -- (267.5:46.5)
			(269:45.5) -- (266.0625+16*0.125:49.5) -- (266.0625+31*0.125:49.5) -- (269:45.5)
			(271:45.5) -- (266.0625+32*0.125:49.5) -- (266.0625+47*0.125:49.5) -- (271:45.5)
			(272.5:46.5) -- (266.0625+48*0.125:49.5) -- (266.0625+55*0.125:49.5) -- (272.5:46.5)
			(273.25:47.5) -- (266.0625+56*0.125:49.5) -- (266.0625+59*0.125:49.5) -- (273.25:47.5)
			(273.625:48.5) -- (266.0625+60*0.125:49.5) -- (266.0625+61*0.125:49.5) -- (273.625:48.5)
		};
		\draw[red]{
			(266.0625+0.125:49.5) node[red]{} -- (266.375:48.5) node[red]{} -- (266.75:47.5) node[red]{} -- (267.5:46.5) node[red]{}
				-- (269:45.5) node[red]{} -- (271:45.5) node[red]{} -- (272.5:46.5) node[red]{} -- (273.25:47.5) node[red]{} -- (273.625:48.5) node[red]{}
				-- (274.0625-2*0.125:49.5) node[red]{}
		};
	\end{tikzpicture}
	\caption{Red path of length $9$ covering the maximum number of cells.}\label{fig:maxred}
\end{figure}

Let $\ell_i$ be the length of the red path connecting $c'_i$ and $r_i$.
We define independent random variables $K_i$ distributed as $\Geom(1-8e^{-\nu/5\pi})$.
Note that this independence can only make the bound larger as no two of the corresponding paths can meet,
so a path cannot use anything that has been exposed already by a different path.
Also, the number of available next cells in any step can only go down if we consider the dependent case.
Because every red cell has at most $8$ neighbours and every cell is red with probability at most $e^{-\nu/5\pi}$, we have
\[\P(\ell_i\geq k_i)<\left(8e^{-\nu/5\pi}\right)^{k_i}.\]
In other words, $\ell_i$ is stochastically bounded from above by $K_i$. 
Also, by Claim~\ref{clm:blueComp}(ii) $R_i$ is stochastically bounded by $2^{\ell_i/2+2}$, which in turn is stochastically 
bounded from above by $2^{K_i /2 + 2}$. We denote the latter by $Y_i$.  

% Recall that the number of cells in $B_1$ is at least $\frac{2\pi}{\nu}N$. Hence, the number of blue cells in $B_1$ that are 
% belong to the connected component of $G_b$ which contains the blue lollipop graph is stochastically bounded from below by 
% $$ \frac{2\pi}{\nu} N - \sum_{i=1}^{K-1} Y_i. $$

% For a natural number $t$ let 
% \[
% L_t = \sum_{i=1}^t Y_i. 
% \]
% If $\mu$ denotes the expected value of $Y_i$, then 
% \begin{equation*}
% \begin{split}
% \mu &\leq \sum_{k=1}^\infty \left(8e^{-\nu/5\pi}\right)^{k} 2^{k/2 + 2} 
% \stackrel{\nu > 24 \pi}{<}4 \sum_{k=1}^{\infty} \left(8e^{-4}\right)^{k} 2^{k/2} = 
% 4 \sum_{k=1}^{\infty} \left(\sqrt{2} 8 e^{-4} \right)^k < 4 \sum_{k=1}^{\infty} \left(16 e^{-4} \right)^k \\
% & < 4 \sum_{k=1}^{\infty} \left(2/ e \right)^k = \frac{8}{e - 2} < 16.  
% \end{split}
% \end{equation*}
% The second moment is similarly bounded as follows: 
% \[\Ee(Y_1^2)=\sum_{k=1}^{\infty}2^{k+4}(8e^{-\nu/5\pi})^k \leq 16\sum_{k=1}^{\infty}(16e^{-\nu/5\pi})^k
% 	\stackrel{\nu > 24 \pi}{<} 16\sum_{\ell=1}^{\infty}(2/e)^\ell< \frac{32}{e-2}=64.\] 
% as $\nu>24\pi$.

% Let $\hat{t} = \frac{1}{32}~\frac{2\pi}{\nu} N$. Then $\Ee (L_{\hat{t}}) \leq 16~\frac{1}{32}~\frac{2\pi}{\nu} N =
% \frac{1}{2}~\frac{2\pi}{\nu} N$. 
% Also, $\Var (L_{\hat{t}}) < 64 \hat{t}= 2~\frac{2\pi}{\nu} N$.
% Hence, by Chebyschev's inequality we have 
% \[ \P \left( L_{\hat{t}} > \frac{2}{3}~\frac{2\pi}{\nu} N  \right)= O\left( \frac{1}{N} \right). \]
% Thus, 
% \[ \P \left( \sum_{i=1}^{\hat{t}} R_i > \frac{2}{3}~\frac{2\pi}{\nu} N  \right)= O\left( \frac{1}{N} \right).\]

We define independent random variables $X_i$ and $Y_i$, where $X_i=\Geom(e^{-\nu/5\pi})$ and $Y_i=2^{K_i/2+2}$.
With this $S_i$ is stochastically bounded by $X_i$ and $R_i$ is stochastically bounded by $Y_i$.
Define
\[L_t=\sum_{i=1}^{t}(X_i+Y_i)\]
and let $\mathcal{T}:=\max\{t:L_t<\frac{2\pi}{\nu}N\}$.
As the number of cells in $B_1$ is at least $\frac{2\pi}{\nu}N$ and with Claim~\ref{clm:blueComp}, $\mathcal{T}$ is a stochastic lower
bound on the number of steps we need to take to cover $B_1$ with $S_i$ and $R_i$, which we denoted by. $K$. 
But the latter is  also a bound on the vertices of $\Pnan$ which belong to the component that contains the vertices induced by the lollipop.
With $\mu_1=\Ee(X_1)=e^{\nu/5\pi}$ and $\mu_2=\Ee(Y_1)$ we have $\Ee(L_t)=t(\mu_1+\mu_2)$.
Let $\hat{t}=\frac{1.9\pi}{\nu(\mu_1+\mu_2)}N$. 
Note that $\mu_1+\mu_2>1$ as $\mu_2\geq 0$ and $\mu_1=e^{\nu/5\pi}>1$. 
Hence, $\Ee(L_{\hat{t}})\leq \frac{1.9\pi}{\nu}N$.
If $\P(L_{\hat{t}}>\frac{2\pi}{\nu}N)=o(1)$, it follows that a.a.s. $\mathcal{T} >\hat t$. Hence, by the stochastic domination we deduce
that a.a.s. $K > \hat t$. 
\begin{claim}\label{clm:hatTBig}
	Let $\nu>20\pi$. We have \[\P\left(L_{\hat t}>\frac{2\pi}{\nu}N\right)=o(1).\]
\end{claim}
\begin{proof}
	We have
	\begin{align*}
		\Var(L_t)&=t(\Var(X_1)+\Var(Y_1)),\\
		\Var(X_1)&=\Var(\Geom(e^{-\nu/5\pi}))=\frac{1-e^{-\nu/5\pi}}{e^{-2\nu/5\pi}}<e^\frac{\nu}{2\pi}\text{ and}\\
		\Var(Y_1)&=\Ee(Y_1^2)-\Ee^2(Y_1).
	\end{align*}
	But 
	\[\Ee(Y_1^2)=\sum_{k=1}^{\infty}2^{k+4}(8e^{-\nu/5\pi})^k \leq 16\sum_{k=1}^{\infty}(16e^{-\nu/5\pi})^k
	\stackrel{\nu > 20 \pi}{<} 16\sum_{k=1}^{\infty}(2/e)^k< \frac{32}{e-2}=64.\] 

	Thus $\Var(Y_1)<64$ and $\Var(L_{\hat t})< (64 +e^\frac{\nu}{2\pi} ) \hat{t} = O\left( N \right)$.
%	Let $\sigma=\sqrt{\frac{300\pi}{\nu(\mu_1+\mu_2)}e^\frac{\nu}{4\pi}N}$.
%	In particular, $N/\sigma=O(\sqrt(N))$.
	By Chebyshev's inequality,
	\[
		\P\left(L_{\hat t}>\frac{2\pi}{\nu}N\right) =O(1/N).\qedhere
	\]
%	\begin{align*}
%		\P\left(L_{\hat t}>\frac{2\pi}{\nu}N\right)&\leq\P\left(|L_{\hat t}-\frac{1.9\pi}{\nu}N|>\frac{0.1\pi}{\nu}N\right)\\
%			&=\P\left(|L_{\hat t}-\frac{1.9\pi}{\nu}N|>\left(\frac{0.1\pi}{\nu\sigma}N\right)\sigma\right)\\
%			&\leq\frac{1}{\left(\frac{0.1\pi}{\nu\sigma}N\right)^2}=O(1/N).
%	\end{align*}
\end{proof}
Note that $\Ee(X_1)=e^{\frac{\nu}{5\pi}}$ and 
\begin{equation*}
\begin{split}
\Ee (Y_1) &\leq 1+\sum_{k=1}^\infty \left(8e^{-\nu/5\pi}\right)^{k} 2^{k/2 + 2} 
\stackrel{\nu > 20 \pi}{<}1+4 \sum_{k=1}^{\infty} \left(8e^{-4}\right)^{k} 2^{k/2}
 < 1+4 \sum_{k=1}^{\infty}\left(\frac14\right)^k <3.  
\end{split}
\end{equation*}
So $\hat t>\frac{1.9\pi}{\nu(e^{\nu/5\pi}+3)}N$.
We can now prove the second part of the main theorem.

\begin{proof}[Proof of the second part of Theorem~\ref{thm:crit}]
	Let $\nu>20\pi$ and let $G_c$ be defined as above.
	By Claim~\ref{clm:lolli} there is a blue lollipop a.a.s.
	By Claims~\ref{clm:blueComp}.1 and~\ref{clm:hatTBig} a.a.s. the blue lollipop extends into a blue component of order at least
	$\hat t>\frac{1.9\pi}{\nu(e^{\nu/5\pi}+3)}N$.
	Setting $\nu = 20 \pi$, this quantity is at least $\frac{1.9 \pi}{20 \pi ( e^4 + 3)} N > N/610$. 
    Note that increasing $\nu$ can only stochastically increase the order of the largest connected component. Thus, 
    for any such $\nu > 20 \pi$, the order of the largest component is a.a.s. at least $N/610$. 
    % 	By Lemma~\ref{lem:adjacency} this induces a component of at least the same size in $\Pnan$.
% 	Even better, there are $\hat t$ blue cells in the outermost band of $G_c$ that are connected.
% 	Each vertex that belongs to such a blue cell is adjacent to any other vertex above this cell.
% 	Since this band has $M=(1+o(1))\frac{2\pi}{0.95e^{-R/2}}$ cells, the vertices together cover an angle of
% 	\begin{align*}
% 		\Theta_{L_1}&=2\pi \frac{\hat t}{M}>2\pi \frac{0.95\cdot1.9\pi N}{\nu(e^{\nu/5\pi}+3)2\pi e^{R/2}}\\
% 			&=1.8\pi \frac{1}{e^{\nu/5\pi}+3}.
% 	\end{align*}
% 	For $\nu=20\pi$, this yields $\Theta_{L_1}>2\pi\frac{1}{64}= \frac{\pi}{32}$.
% 	Now note that increasing $\nu$ can only increase the angle, so for $\nu>20\pi$ the component covers a sector of angle which is 
%     at least $\frac{\pi}{32}$.
%     Therefore, the total angle that is covered by the inner tubes of these vertices on the periphery of $\D$ is 
% 	also at least $\frac{\pi}{32}$. Hence, a $1/64$-fraction of $\D$ is covered by vertices in this component. 
% 	Using concentration arguments as in the supercritical case of Theorem~\ref{thm:main},
% 	we can show that a.a.s. this component contains at least $\frac{1}{65}N$ vertices.
\end{proof}


\section{Conclusion} In this paper we have studied the component structure of the KPKVB-model, a geometric model of random graphs on 
the hyperbolic plane. 
This can be viewed as a dependent version of the well-known Chung-Lu model of inhomogeneous random graphs. 
The model was recently introduced by Krioukov et al.~\cite{ar:Krioukov}, whose aim is to develop a geometric framework for 
the study of complex networks. We determine the critical parameters which control the typical component structure of such a 
random graph. Namely, we determine the critical parameter which controls the emergence of a giant component. 
We show that in the regime where the random graph 
exhibits power law degree distribution with exponent greater than 3, all components are sub-linear. On the other hand, 
when the exponent of the power law is less than 3, then a component that contains a positive fraction of the vertices exists with 
high probability.

However, our results are not precise as far as the size of the giant component is concerned. Showing, for example, a law of large numbers 
 seems to be a challenging problem, mainly due to the dependencies that are present in this model. Also, for the case $\alpha =1$, we conjecture that there is a critical value for $\nu$ above which the giant component emerges. 

\begin{thebibliography}{99}
\bibitem{AlbBar} R. Albert and A.-L. Barab\'asi,
Statistical mechanics of complex networks, \emph{Reviews of Modern Physics} {\bf 74} (2002), 47--97.

% \bibitem{ar:Bac} F.~Baccelli, B.~Blaszczyszyn and O.~Mirsadeghi, Optimal paths on the space-time SINR random graph, \emph{Advances in 
% Applied Probability} {\bf 43}(1) (2011), 131--150.

%\bibitem{Balogh} J.~Balogh, B.~Bollob\'as, M.~Krivelevich, T.~M\"uller and M. Walters, Hamilton cycles in random geometric graphs, 
%\emph{Annals of Applied Probability} {\bf 21}(3) (2011), 1053--1072.

\bibitem{BarAlb} A.-L. Barab\'asi and R. Albert, Emergence of scaling in random networks, 
\emph{Science} {\bf 286} (1999), 509--512.

%\bibitem{ar:BenjSchramm} I.~Benjamini and O.~Schramm, Percolation in the hyperbolic plane, \emph{Journal of the American Mathematical 
%Society} {\bf 14} (2001), 487--507. 

\bibitem{Bol01} B.~Bollob\'as, \emph{Random graphs}, Cambridge University Press, 2001, xviii+498 pages.

 \bibitem{BJR} B.~Bollob\'as, S.~Janson and O.~Riordan, The phase transition in inhomogeneous random graphs, \emph{Random Structures and Algorithms} {\bf 31}(2007), 3--122. 

 \bibitem{Diam} B.~Bollob\'as and O.~Riordan, The diameter of a scale-free random graph, \emph{Combinatorica} {\bf 24} (2004), 5--34. 

\bibitem{DegSeq} B.~Bollob\'as, O.~Riordan, J.~Spencer and G.~Tusn\'ady, The degree sequence of a scale-free random graph process, 
 \emph{Random Structures and Algorithms} {\bf 18} (2001), 279--290.

\bibitem{Dor} S.~N.~Dorogovtsev, \emph{Lectures on Complex Networks}, Oxford University Press, 2010, xi+134 pages. 
% \bibitem{Boerner04+} K.~B\"orner, J.T.~Maru and R.L.~Goldstone, 
% Colloquium Paper: Mapping Knowledge Domains: The simultaneous evolution of author and paper networks, 
% \emph{Proc. Natl. Acad. Sci. USA} {\bf 101} (2004), 5266--5273.

 \bibitem{ChungLu1+} F.~Chung and L.~Lu, The average distances in random graphs with given expected degrees, 
 \emph{Proc. Natl. Acad. Sci. USA} {\bf 99} (2002), 15879--15882.

 \bibitem{ChungLuComp+}  F.~Chung and L.~Lu, 
 Connected components in random graphs with given expected degree sequences, \emph{Annals of Combinatorics} {\bf 6} (2002), 125--145.

 \bibitem{ChungLuBook+} F.~Chung and L.~Lu, \emph{Complex Graphs and Networks}, AMS, 2006.

\bibitem{Fount13+} N.~Fountoulakis, On an asymptotic geometrization of the Chung-Lu model for complex networks, \emph{Journal of Complex Networks}, to appear. 

%\bibitem{Gilbert61} E.~N.~Gilbert, Random plane networks, \emph{J. Soc. Indust. Appl. Math.} {\bf 9} (1961), 533--543.

\bibitem{ar:Gugel} L.~Gugelmann, K.~Panagiotou and U.~Peter, Random hyperbolic graphs: degree sequence and clustering, 
In \emph{Proceedings of the 39th International Colloquium on Automata, Languages and Programming (A.~ Czumaj et al. Eds.)},
Lecture Notes in Computer Science 7392, 2012, pp. 573--585. 

\bibitem{ErRen} P.~Erd{\H{o}}s and A.~R{\'{e}}nyi,
On the evolution of random graphs, \emph{Pub. Math. Inst. Hungar. Acad.  Sci.} {\bf 5} (1960), 17--61.

%\bibitem{ar:Hafner72} R.~Hafner, The asymptotic distribution of random clumps, \emph{Computing} {\bf 10} (1972), 335--351.

 \bibitem{bk:vdH} R.~van der Hofstad, \emph{Random Graphs and Complex Networks}, preprint available 
 at~\url{http://www.win.tue.nl/~rhofstad/}.

\bibitem{bk:Grimmett} G.~Grimmett, \emph{Percolation}, Grundlehren der mathematischen Wissenschaften, vol 321, Springer, 1999. 

\bibitem{JLR} S.~Janson, T.~\L uczak and A.~Ruci\'nski,  \emph{Random Graphs}, Wiley, New York, 2000.

\bibitem{Kingman} J.~F.~C.~Kingman, \emph{Poisson processes}, Oxford University Press, New York, 1993.

\bibitem{KiwiMitsche} M.~Kiwi and D.~Mitsche, A bound on the diameter of random hyperbolic graphs, preprint available 
at~\arxiv{1408.2947}, 19 pages. 

\bibitem{ar:Krioukov} D.~Krioukov, F.~Papadopoulos, M.~Kitsak, A.~Vahdat and M.~Bogu\~n\'a, Hyperbolic Geometry of Complex Networks, 
\emph{Phys. Rev. E} {\bf 82} (2010), 036106. 

%\bibitem{McDiarmid} C.J.H.~McDiarmid and T.~M\"uller, On the chromatic number of random geometric graphs, \emph{Combinatorica} 
%{\bf 31}(4) (2011), 423--488. 

%\bibitem{ar:Park} J.~Park and M.~E.~J.~Newman, Statistical mechanics of networks, \emph{Phys. Rev. E} {\bf 70} (2004), 066117.

\bibitem{bk:Penrose} M.~Penrose, \emph{Random Geometric Graphs}, Oxford University Press, 2003.

\bibitem{ar:s02} B.~S{\"o}derberg, General formalism for inhomogeneous random graphs, \emph{Phys. Rev. E} {\bf 66}(3) (2002), 066121.

\bibitem{bk:Stillwell} J.~Stillwell, \emph{Geometry of Surfaces}, Springer, 1992.
\end{thebibliography}



\appendix



\section{Proof of Lemma~\ref{lem:CCCoupl}\label{sec:CouplApp}}

	%We close this section giving the proof of Lemma~\ref{eq:equiv}. 
    \begin{proof}[Proof of Lemma~\ref{lem:CCCoupl}]
    Note that $R = (2/\zeta)\log(N/\nu)$ and $R' := (2/\zeta')\log(N/\nu)$ are chosen such that $N = \nu e^{\zeta R/2} = \nu e^{\zeta' R' / 2}$. 
     %, so that  both graphs are on the same number of vertices (otherwise the result would not make sense).

The desired coupling is constructed as follows.
We pick $\theta_1, \dots, \theta_N$ i.i.d.~uniform on $[0,2\pi)$ and we pick
$U_1,\dots, U_N$ i.i.d.~uniform on $[0,1]$.

We now let $\rho_1, \dots, \rho_N$ and $\rho_1', \dots, \rho_N'$ be defined by the equations:

\begin{equation}\label{eq:cdefA}  
F_{\alpha,R}( \rho_i ) = F_{\alpha',R'}( \rho_i' ) = U_i \quad \quad \quad (\text{for $i=1,\dots,N$,}) 
\end{equation}

\noindent
where $F_{\alpha;R}$ is the cdf that goes with the pdf~\eqref{eq:pdf}. That is:

\begin{equation}\label{eq:Fdef} 
F_{\alpha;R}( r ) %= \Pee( \rho \leq r ) 
= \left\{\begin{array}{cl}
0 & \text{ if $r < 0$, } \\
\frac{\cosh( \alpha r) - 1}{\cosh(\alpha R)-1} & \text{ if } 0 \leq r \leq R; \\
1 & \text{ otherwise.}
\end{array}\right.
\end{equation}


(Note that in this way the $\rho_i$s have exactly the distribution with pdf~\eqref{eq:pdf} and
the $\rho_i'$s have the same pdf but with $\alpha', R'$ in place of $\alpha, R$.)
The points used in the construction of  $G(N;\zeta,\alpha, \nu)$ will be
$(\theta_1,\rho_1), \dots, (\theta_N,\rho_N)$ while the points used in the
construction of $G(N;\zeta',\alpha',\nu)$ will be 
$(\theta_1,\rho_1'), \dots, (\theta_N, \rho_N')$.

It remains to be seen that this way we get two isomorphic graphs. %%% (w.h.p.).

%To this end we start with an easy lemma.
%
%\begin{lemma} Suppose that $\zeta/\alpha < 2$ then there exists a
%$\delta = \delta(\zeta,\alpha)$ such that a.a.s.~there are no points
%of type higher than $(1-\delta)R$.
%\end{lemma}
%
%\begin{proof}
%The expected number of points with type $> (1-\delta)R$ equals:
%
%\[ 
%N \cdot \frac{\cosh(\alpha \delta R) - 1}{\cosh(\alpha R) - 1}
%= 
%(\nu+o(1)) \cdot \exp{\Big[} \zeta R/2 + \alpha\delta R - \alpha R {\Big]} 
%= 
%(\nu+o(1)) \cdot \exp{\Big[} (\zeta/2 - (1-\delta) \alpha ) R {\Big]}.
%\]
%
%\noindent
%Since $\zeta/2 < \alpha$ we can take $\delta>0$ such that
%$\zeta/2 - (1-\delta) \alpha < 0$, and hence
%the expected number of points that have type $> (1-\delta) R$ will be $o(1)$.
%\end{proof}

%As usual, we define the ``type" of vertex $i$ by
%
%\[ 
%t_i := R-\rho_i, \quad t_i' := R'-\rho_i'. 
%\]
 
\begin{claim} \label{clm:intermediate}
We have %%%$t_i' = (\alpha/\alpha') t_i$ and 
$\rho_i' = (\alpha/\alpha')\rho_i$ for all $i$. 
\end{claim}

\begin{proof}
Observe that

\[ \alpha' R' = \alpha' \cdot (\zeta/\zeta') R =  \alpha' \cdot (\alpha/\alpha') R
= \alpha R.  \]%%Hence we also have $\cosh(\alpha R) = \cosh(\alpha' R')$.
%
%
%
Thus, the equation~\eqref{eq:cdefA} defining $\rho_i$ and $\rho_i'$ yields:

\[ \cosh( \alpha \rho_i ) = \cosh(\alpha' \rho_i'). \]

\noindent
Since $\cosh(x)$ is strictly increasing for $x\geq 0$, it follows that we must have
$\alpha \rho_i = \alpha' \rho_i'$.
%%%%It immediately follows that $t_i' = (\alpha/\alpha') t_i$, as required.
\end{proof}

Let us write $d_{ij}$ for the distance between $(\theta_i, \rho_i)$ and 
$(\theta_j, \rho_j)$ in the curvature-$\zeta$-surface, and
let $d_{ij}'$ be defined analogously.

\begin{claim}
For all $i,j$ we have $d_{ij}' = (\alpha/\alpha') d_{ij}$.
\end{claim}


\begin{proof}
By the {\em hyperbolic cosine rule} we have that

\[
\cosh( \zeta d_{ij} ) = \cosh( \zeta \rho_i ) \cosh( \zeta \rho_j ) - \sinh(\zeta \rho_i ) \sinh( \zeta \rho_j ) \cos( |\theta_i - \theta_j| ), 
\]%
%
%
and

\[
\cosh( \zeta' d_{ij}' ) = \cosh( \zeta' \rho_i' ) \cosh( \zeta' \rho_j' ) - \sinh(\zeta' \rho_i' ) \sinh( \zeta' \rho_j' ) \cos( |\theta_i - \theta_j| ).
\]%

\noindent
Now observe that 

\[ \zeta \rho_i = \alpha \cdot (\zeta/\alpha) \cdot \rho_i = 
\alpha \cdot (\zeta'/\alpha') \rho_i = 
\zeta' \rho_i', \]%
%
%
using Claim~\ref{clm:intermediate}, and similarly $\zeta \rho_j = \zeta' \rho_j'$.
It follows that 

\[ \cosh( \zeta' d_{ij}' ) = \cosh( \zeta d_{ij} ). \]

\noindent
Again using that $\cosh(x)$ is strictly increasing for $x\geq 0$ (and the distances $d_{ij}, d_{ij}'$ are nonnegative), we see that 
$d_{ij}' = (\zeta/\zeta') d_{ij} = (\alpha/\alpha') d_{ij}$.
\end{proof}

Since $R' = (\zeta/\zeta')R = (\alpha/\alpha') R$, we see that 

\[ d_{ij} \leq R \text{ if and only if } d_{ij}' \leq R', \]

\noindent
which proves the lemma.
\end{proof}




\section{The proof of Lemma~\ref{lem:decreasing}\label{sec:decreasing}}



Very similarly to the proof of Lemma~\ref{lem:CCCoupl}, the coupling is constructed as follows.
We pick $\theta_1, \dots, \theta_N$ i.i.d.~uniform on $[0,2\pi)$ and we pick
$U_1,\dots, U_N$ i.i.d.~uniform on $[0,1]$.
We now let $\rho_1, \dots, \rho_N$ and $\rho_1', \dots, \rho_N'$ be defined by the equations:

\begin{equation}\label{eq:cdef}  
F_{\alpha,R}( \rho_i ) = F_{\alpha',R'}( \rho_i' ) = U_i \quad \quad \quad (\text{for $i=1,\dots,N$.}) 
\end{equation}

\noindent
($F_{\alpha,R}$ is as defined in the proof of Lemma~\ref{lem:CCCoupl}, and $R := 2\log(N/\nu), R' := 2\log(N/\nu')$.)
Again, we note that in this way the $\rho_i$s have exactly the distribution with cdf $F_{\alpha, R}$ and
the $\rho_i'$s have cdf $F_{\alpha',R'}$.
The points used in the construction of  $G(N;\alpha, \nu)$ will be
$(\rho_1,\theta_1), \dots, (\rho_N,\theta_N)$ while the points used in the
construction of $G(N;\alpha',\nu')$ will be 
$(\rho_1',\theta_1), \dots, (\rho_N',\theta_N)$.

We need the following geometric fact.

\begin{lemma}\label{lem:geod}
Suppose that $p = (r,\theta), q = (s,\vartheta)$ are two points in the hyperbolic plane
satisfying $\dist_{\Haa}(p, O), \dist_{\Haa}(q,O), \dist_{\Haa}(p,q) \leq R$ and let
$p' = (r',\theta), q' = (s',\vartheta)$ with $r' \leq r, s' \leq s$.
Then $\dist_{\Haa}(p',q') \leq R$.
\end{lemma}

Before giving the proof of this lemma, let us remind the reader that disks are convex, also in the hyperbolic plane. 
This means that if $D$ is a disk in the hyperbolic plane and $x, y \in D$ then the geodesic between
$x,y$ is contained in $D$.
One way to see this is by noting that every disk can be isometrically mapped to a disk with origin $O$, and that in the projective disk 
model of the hyperbolic plane (a.k.a.~the Beltrami-Klein model) a hyperbolic disk with origin $O$ looks like a Euclidean disk, while geodesics are just line segments in the projective disk model.
(See for instance Section 4.8 of~\cite{bk:Stillwell} for a description of the projective disk model.)


\begin{proofof}{Lemma~\ref{lem:geod}}
It is enough to consider the case when $r' < r$ and $s'=s$. (Another application of this case
will then give the full result.)
Observe that the geodesic between $O$ and $p$ is just the line segment between them.
So in particular, $p'$ lies on the geodesic between $O$ and $p$.
Since $O, p \in B(q;R)$ it follows that also $p' \in B(q;R)$, as required.
\end{proofof}

We also need the following observation, which can be rephrased as stating that the radius under the $(\alpha,R)$-quasi uniform distribution
stochastically dominates the radius under the $(\alpha',R)$-quasi uniform distribution if $\alpha > \alpha'$.

\begin{lemma}
If $\alpha\geq\alpha'$ and $\nu=\nu'$ then $F_{\alpha,R}(r) \leq F_{\alpha',R'}(r)$ for every $r \in \eR$.
\end{lemma}

\begin{proof}
Note that $\nu=\nu'$ implies that also $R=R'$.
Let us thus fix $R > 0$ and $0 < r < R$, and define $\varphi(\alpha) := F_{\alpha,R}(r)$
for every $\alpha > 0$. %%% (with respect to $\alpha$).
Our aim will be to show that $\frac{{\dd}\varphi}{{\dd}\alpha}$ is non-positive for every $\alpha > 0$, which will clearly yield the result.

We obtain:

\[  
\frac{{\dd}\varphi}{{\dd}\alpha} =
\frac{r\sinh(\alpha r) (\cosh(\alpha R)-1) - R\sinh(\alpha R)(\cosh(\alpha r)-1)}{
(\cosh(\alpha R)-1)^2}.
\]

\noindent
Observe that this is non-positive if and only if

 \[ 
 \frac{\alpha R \sinh(\alpha R)}{\cosh(\alpha R)-1} \geq \frac{\alpha r \sinh(\alpha r)}{\cosh(\alpha r) -1}. \]
 
 \noindent
We claim this is the case for all $0 \leq r \leq R$. 
To see this, it suffices to show that 
 $(x\sinh x) / (\cosh x-1)$ is nondecreasing for $x\geq 0$.
 Let us thus compute
 
 \[ \begin{array}{rcl}
 \displaystyle
 \left[\frac{x\sinh x}{\cosh x -1}\right]'
 & = & 
 \displaystyle
 \frac{
(\sinh x+ x\cosh x)(\cosh x - 1) - x\sinh^2 x 
 }{
 (\cosh x -1)^2
 } \\
&  =  & 
\displaystyle
\frac{
\sinh x\cosh x + x \cosh^2 x - \sinh x - x\cosh x - x\sinh^2 x 
 }{
 (\cosh x-1)^2
 } \\
& = & 
\displaystyle
\frac{
\sinh x\cosh x + x(\cosh^2x-\sinh^2x)-\sinh x - x\cosh x
}{
 (\cosh x-1)^2
} \\
& = & 
\displaystyle
\frac{
\sinh x\cosh x + x-\sinh x - x\cosh x
}{
 (\cosh x-1)^2
} \\
& = & 
\displaystyle
\frac{
(\sinh x-x)(\cosh x-1)
}{
 (\cosh x-1)^2
} \\
& \geq & 
0.
\end{array} \]
 
 \noindent
 So our claim holds, and we see that indeed $\frac{{\dd}\varphi}{{\dd}\alpha} \leq 0$ for all $\alpha > 0$. This proves the lemma.
\end{proof}

\begin{lemma}
If $\alpha=\alpha'$ and $\nu \leq \nu'$, then $F_{\alpha,R}(r) \leq F_{\alpha',R'}(r)$ for every $r \in \eR$.
\end{lemma}

\begin{proof}
Observe that $\nu\leq\nu'$ implies that $R\geq R'$.
This also gives $\cosh(\alpha R)-1 \geq \cosh(\alpha R')-1$, and hence the lemma.
\end{proof}
Combining the last two lemmas gives:
\begin{corollary}
If $\alpha \geq \alpha'$ and $\nu \leq \nu'$, then $F_{\alpha,R}(r) \leq F_{\alpha',R'}(r)$ for every $r \in \eR$.
\end{corollary}


Together with the definition of $\rho_i, \rho_i'$ this immediately gives:

\begin{corollary}\label{cor:thislast}
If $\alpha \geq \alpha'$ and $\nu \leq \nu'$, then, in the coupling described above, we have that $\rho_i \geq \rho_i'$ for all $1\leq i \leq N$.
\end{corollary}


Corollary~\ref{cor:thislast} together with Lemma~\ref{lem:geod} yield Lemma~\ref{lem:decreasing}.


\end{document}