# On the local resilience of random geometric graphs with respect to
connectivity and long cycles

Alberto Espuny Díaz<EMAIL_ADDRESS>Institut für
Informatik, Universität Heidelberg, 69120 Heidelberg, Germany.  ,  Lyuben
Lichev<EMAIL_ADDRESS>Institute of Science and Technology Austria
(ISTA), 3400 Klosterneuburg, Austria.  and  Alexandra Wesolek
<EMAIL_ADDRESS>Institut für Mathematik, Technische Universität
Berlin, 10623 Berlin, Germany.

###### Abstract.

Given an increasing graph property $\mathcal{P}$, a graph $G$ is
$\alpha$-resilient with respect to $\mathcal{P}$ if, for every spanning
subgraph $H\subseteq G$ where each vertex keeps more than a
$(1-\alpha)$-proportion of its neighbours, $H$ has property $\mathcal{P}$. We
study the above notion of local resilience with $G$ being a random geometric
graph $G_{d}(n,r)$ obtained by embedding $n$ vertices independently and
uniformly at random in $[0,1]^{d}$, and connecting two vertices by an edge if
the distance between them is at most $r$.

First, we focus on connectivity. We show that, for every $\epsilon>0$, for $r$
a constant factor above the sharp threshold for connectivity $r_{c}$ of
$G_{d}(n,r)$, the random geometric graph is $(1/2-\epsilon)$-resilient for the
property of being $k$-connected, with $k$ of the same order as the expected
degree. However, contrary to binomial random graphs, for sufficiently small
$\epsilon>0$, connectivity is not born $(1/2-\epsilon)$-resilient in
$2$-dimensional random geometric graphs.

Second, we study local resilience with respect to the property of containing
long cycles. We show that, for $r$ a constant factor above $r_{c}$,
$G_{d}(n,r)$ is $(1/2-\epsilon)$-resilient with respect to containing cycles
of all lengths between constant and $2n/3$. Proving
$(1/2-\epsilon)$-resilience for Hamiltonicity remains elusive with our
techniques. Nevertheless, we show that $G_{d}(n,r)$ is $\alpha$-resilient with
respect to Hamiltonicity for a fixed constant $\alpha=\alpha(d)<1/2$.

A. Espuny Díaz was supported by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) through projects no. 447645533 and 513704762. L.
Lichev was supported by the Austrian Science Fund (FWF) grant no.
10.55776/ESP624. A. Wesolek was supported by the DFG under Germany’s
Excellence Strategy – The Berlin Mathematics Research Center MATH+
(EXC-2046/1, project ID: 390685689).

##  1\. Introduction

For a graph $G$ that satisfies a certain property $\mathcal{P}$, how much do
we have to modify $G$ so that it stops satisfying $\mathcal{P}$? This general
question motivated the study of graph resilience with respect to different
properties. A special attention was paid to the following localised version of
the above question. Given a graph $G$ and some $\alpha\in[0,1]$, we say that a
subgraph $H\subseteq G$ is an _$\alpha$ -subgraph_ of $G$ if for every $v\in
V(G)$ we have $d_{H}(v)\geq\alpha d_{G}(v)$. If $G$ satisfies an increasing
property $\mathcal{P}$, we define the _local resilience_ of $G$ with respect
to $\mathcal{P}$ as the supremum of the values $\alpha\in[0,1]$ such that
_every_ $(1-\alpha)$-subgraph of $G$ satisfies $\mathcal{P}$. Alternatively,
one may think that an adversary is allowed to remove edges from $G$ subject to
the condition that the proportion of edges incident to any given vertex cannot
be decreased by more than a factor of $\alpha$. Then, the local resilience of
$G$ with respect to $\mathcal{P}$ is the minimum $\alpha$ such that the
adversary can produce a $(1-\alpha)$-subgraph of $G$ without property
$\mathcal{P}$.

Many natural statements can be expressed in the language of local resilience.
For example, recall the classical theorem of Dirac [17] which asserts that
every graph $G$ on $n\geq 3$ vertices with minimum degree $\delta(G)\geq n/2$
contains a Hamilton cycle, and that this is the best possible minimum degree
condition. This statement can be rephrased in the language of local resilience
of the complete graph. Indeed, fix $\alpha^{*}\coloneqq(\lceil
n/2\rceil-1)/(n-1)$. Then, Dirac’s theorem states that, for every
$\alpha>\alpha^{*}$, every $\alpha$-subgraph of $K_{n}$ contains a Hamilton
cycle and that this is best possible, implying that the local resilience of
$K_{n}$ with respect to Hamiltonicity is $1-\alpha^{*}\sim 1/2$. Likewise, all
classical extremal results with minimum degree conditions guaranteeing some
property $\mathcal{P}$ can be seen as statements about the local resilience of
$K_{n}$ with respect to $\mathcal{P}$.

A lot of research has been done on the local resilience of random graphs with
respect to different properties. The binomial random graph $G(n,p)$, sampled
by including each of the possible
$\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{2}\kern-1.00006pt\bigr{)}$
edges on vertex set $[n]\coloneqq\\{1,\ldots,n\\}$ independently with
probability $p$, received particular attention. (We discuss results in this
context in the coming sections.) In this paper, we focus on the local
resilience of _random geometric graphs_ , which were first introduced by
Gilbert [27]. Given positive integers $d$ and $n$ and a real number $r>0$, the
$d$-dimensional random geometric graph $G_{d}(n,r)$ is a graph on vertex set
$[n]$ whose edges are generated as follows. Consider $n$ mutually independent
uniform random variables $X_{1},\ldots,X_{n}$ on $[0,1]^{d}$. For each pair of
distinct elements $i,j\in[n]$, the edge $ij$ is added to the graph if and only
if $\lVert X_{i}-X_{j}\rVert\leq r$, where $\lVert\cdot\rVert$ denotes the
Euclidean distance.

###  1.1. Local resilience and Hamiltonicity

The systematic study of local resilience was introduced by Sudakov and Vu
[55].111We remark that our definition of local resilience is slightly
different from that in [55] and closer to more recent versions which have
appeared in the literature [38, 42]. Nevertheless, all the results we mention
in our paper hold with our definition as well. In their pioneering paper,
among other results, they considered the local resilience of random and
pseudorandom graphs with respect to Hamiltonicity. In particular, they showed
that, for $p\geq(\log n)^{4}/n$ and any fixed constant $\epsilon>0$,
asymptotically almost surely (that is, with probability tending to $1$ as $n$
grows to infinity, which we abbreviate as a.a.s.) the local resilience of
$G(n,p)$ with respect to Hamiltonicity is at least $1/2-\epsilon$. Since then,
the property of containing a Hamilton cycle has become a benchmark in the
study of local resilience for random graphs.

It is worth noting that the constant $1/2$ in the result of Sudakov and Vu
[55] is best possible in great generality: this is a consequence of a result
of Stiebitz [53], who showed that the vertices of every graph can be
partitioned into two sets in such a way that every vertex $v$ has at least
$d(v)/2-1$ neighbours in the part to which it belongs. In particular, for any
$n$-vertex graph $G$ whose minimum degree tends to infinity with $n$, we may
consider such a partition and delete all edges between the two parts to obtain
a $(1/2-o(1))$-subgraph which is not connected. This implies that the local
resilience of $G$ with respect to any property which necessitates connectivity
is at most $1/2+o(1)$.

On the other hand, the result of Sudakov and Vu [55] is not optimal with
respect to the lower bound on $p$. The problem of determining the local
resilience of $G(n,p)$ with respect to Hamiltonicity for the full range of $p$
was studied further [8, 9, 25] until it was finally resolved by Lee and
Sudakov [36], who proved the following theorem.

######  Theorem 1.1 ([36, Theorem 1.1]).

For every $\epsilon\in(0,1/2]$, there exists a constant $C=C(\epsilon)>0$ such
that, for $p\geq C\log n/n$, a.a.s. every $(1/2+\epsilon)$-subgraph of
$G(n,p)$ is Hamiltonian.

This result can be regarded as a version of Dirac’s theorem for binomial
random graphs. Recently, Montgomery [38] and Nenadov, Steger and Trujić [42]
independently sharpened this result to a “hitting time” result. Moreover,
Theorem 1.1 was recently generalised by Condon, Espuny Díaz, Kim, Kühn and
Osthus [14], who considered a version of the problem where the adversary is
allowed to delete more edges incident to some, but not all, vertices of the
graph, giving an analogue of a classical result of Pósa [50] for random
graphs.

The local resilience with respect to Hamiltonicity has also been studied in
other models of random graphs. One example is the model of random regular
graphs. Given integers $1\leq d<n$, a random $d$-regular graph $G_{n,d}$ is
obtained by sampling an element from the set of all $n$-vertex $d$-regular
graphs uniformly at random. It is well known that the random $d$-regular graph
is a.a.s. Hamiltonian for all $d\geq 3$ [51, 52, 16, 35]. Improving on earlier
work of Ben-Shimon, Krivelevich and Sudakov [8], Condon, Espuny Díaz, Girão,
Kühn and Osthus [13] proved a result analogous to Theorem 1.1 for random
regular graphs.

######  Theorem 1.2 ([13, Theorem 1.2]).

For every $\epsilon\in(0,1/2]$, there exists a constant $D=D(\epsilon)>0$ such
that, for all $d\in[D,n-1]$, a.a.s. every $(1/2+\epsilon)$-subgraph of
$G_{n,d}$ is Hamiltonian.

Just like for binomial random graphs, the constant $1/2$ is best possible.
Moreover, Condon, Espuny Díaz, Girão, Kühn and Osthus [13] also showed that a
polynomial dependency between $D$ and $\epsilon$ in Theorem 1.2 cannot be
avoided.

In this paper, we are concerned with studying the local resilience of random
geometric graphs with respect to Hamiltonicity. This question has been brought
up by Frieze [24, Problem 43]. By analogy with Theorems 1.1 and 1.2, the
following conjecture seems appealing.

######  Conjecture 1.3.

For every $\epsilon\in(0,1/2]$ and integer $d\geq 1$, there exists a constant
$C=C(d,\epsilon)>0$ such that, for $r\geq C(\log n/n)^{1/d}$, a.a.s. every
$(1/2+\epsilon)$-subgraph of $G_{d}(n,r)$ is Hamiltonian.

It is worth noting that, if true, this conjecture is best possible up to the
value of $C$. Indeed, the results about the threshold for Hamiltonicity [48,
18, 5, 40] in random geometric graphs show that the statement fails for
$r=o((\log n/n)^{1/d})$, and the constant $1/2$ cannot be improved. We defer
some further discussion about this to Section 1.2.

While the local resilience of random geometric graphs has not been studied
before, it is worth noting that Petit [48] studied Hamiltonicity of subgraphs
of a random geometric graph under random deletion of its edges. However, this
work does not provide any meaningful insights towards Conjecture 1.3.

We remark here two main challenges that must be addressed when considering
Conjecture 1.3. First, for any increasing property $\mathcal{P}$, when aiming
to prove that a.a.s. $G_{d}(n,r)\in\mathcal{P}$ for all $r\geq r^{*}$, it
suffices to assume that $r=r^{*}$. This is due to the monotonicity of the
problem. One difficulty in the study of local resilience is the absence of
monotonicity: indeed, graphs with larger vertex degrees may still be less
resilient with respect to some increasing property as the adversary has the
right to delete more edges from them. Therefore, when considering this
problem, we must really consider all possible values of $r$. Second, all known
results about Hamiltonicity in $G_{d}(n,r)$ exploit the fact that these graphs
are locally dense, meaning that vertices which are (geometrically) close form
very large cliques [4, 19, 20, 26, 48, 18, 5, 37, 40, 23]. This is not the
case in the local resilience setting, where the adversary may delete all
cliques. To be precise, for any fixed $\epsilon<1/6$ and $r$ in the range
considered in Conjecture 1.3, a.a.s. there are $(1/2+\epsilon)$-subgraphs of
$G_{d}(n,r)$ which are $K_{4}$-free. Indeed, for sufficiently large values of
$r$, such subgraphs can be constructed by splitting the vertices randomly into
three sets and removing all edges contained in each of the sets. Therefore, in
order to solve Conjecture 1.3, new techniques seem necessary.

We are currently unable to resolve Conjecture 1.3, and even the analogous
conjecture for perfect matchings remains interesting and widely open. However,
in this paper, we make progress towards Conjecture 1.3 and several related
problems. We present our main results in the following sections.

###  1.2. Connectivity

We begin with an analysis of the local resilience of random geometric graphs
with respect to connectivity, which is a necessary condition for
Hamiltonicity. We show that this necessary condition holds in our context by
providing the following analogue of Conjecture 1.3 for connectivity.

######  Theorem 1.4.

For every $\epsilon\in(0,1/2]$ and integer $d\geq 1$, there exists a constant
$C_{1}=C_{1}(d,\epsilon)>0$ such that, for every $r\geq C_{1}(\log
n/n)^{1/d}$, a.a.s. every $(1/2+\epsilon)$-subgraph of $G_{d}(n,r)$ is
connected.

Theorem 1.4 provides a local resilience analogue of classical results of
Godehardt and Jaworski [28] and Penrose [45, 46] on the threshold for
connectivity of random geometric graphs. Moreover, we can extend this result
to $k$-connectivity for a large range of values of $k$. We defer the more
technical statement and the proof to Section 3 (see Theorem 3.1). Together
with the aforementioned result of Stiebitz [53], Theorem 1.4 implies that
a.a.s. the local resilience of random geometric graphs $G_{d}(n,r)$ with
respect to connectivity is $1/2\pm o(1)$ whenever $r=\omega((\log
n/n)^{1/d})$. If we restrict our attention to $(1/2-\epsilon)$-subgraphs of
$G_{d}(n,r)$, we can say more about the size of a largest component.

######  Proposition 1.5.

For every $\epsilon\in(0,1/2]$, there exists a constant
$C_{2}=C_{2}(\epsilon)>0$ such that, for every integer $d\geq 1$ and $r\geq
C_{2}(\log n/n)^{1/d}$, a.a.s. there exists a $(1/2-\epsilon)$-subgraph of
$G_{d}(n,r)$ with components of order at most $5rn$.

We believe that Proposition 1.5 holds for all smaller radial values as well.
However, our simple proof requires very good concentration on the number of
vertices of $G_{d}(n,r)$ in certain regions of area $\Theta(r^{d})$. This only
holds when $r\geq C(\log n/n)^{1/d}$ for a suitable constant $C>0$. A question
related to Proposition 1.5 is whether a.a.s. there exists a
$(1/2-\epsilon)$-subgraph of $G_{d}(n,r)$ all whose components have order
$o(rn)$. This is clearly not possible when $d=1$, in which case Proposition
1.5 is best possible. Understanding this problem in higher dimensions seems
appealing.

Going back to Theorem 1.4, we remark that the expression $C_{1}(\log
n/n)^{1/d}$ must be larger than the (sharp) connectivity threshold of
$G_{d}(n,r)$. This implies that, for fixed $\epsilon$, the constant
$C_{1}(d,\epsilon)$ needs to grow at speed $\Omega(\sqrt{d})$ as a function of
$d$ (see, e.g., [47, Theorem 13.2]). In fact, our proof shows that it suffices
to have a constant $C_{1}$ which grows with speed $\Theta(\sqrt{d})$ (see
Theorem 3.1 for more details). The behaviour of $C_{1}$ with respect to
$\epsilon$ is more mysterious. While we are uncertain if $C_{1}$ can be chosen
universally for all $\epsilon\in(0,1/2]$ as a function of $d$ when $d\geq 3$,
we can prove that this is not the case when $d\in\\{1,2\\}$.

######  Theorem 1.6.

The following statements hold.

  1. $(\mathrm{i})$

For every $\epsilon\in(0,1/2]$, if $r\leq\log n/4\epsilon n$, then a.a.s.
there exists a disconnected $(1/2+\epsilon)$-subgraph of $G_{1}(n,r)$.

  2. $(\mathrm{ii})$

For every $C>0$, there exists $\epsilon=\epsilon(C)\in(0,1/2]$ such that, for
every $r\leq C(\log n/n)^{1/2}$, a.a.s. there exists a disconnected
$(1/2+\epsilon)$-subgraph of $G_{2}(n,r)$.

Let us discuss an important consequence of this result. Rather than an
instance of the random graph, let us consider a process which generates random
graphs by adding edges one by one. The corresponding process for binomial
random graphs is the _Erdős-Rényi random graph process_
$(G_{i})_{i=0}^{n(n-1)/2}$, where $G_{0}$ is the graph with vertex set $[n]$
and no edges and, for each
$i\in[\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{2}\kern-1.00006pt\bigr{)}]$,
the graph $G_{i}$ is obtained from $G_{i-1}$ by adding an edge chosen
uniformly at random among those not contained in $G_{i-1}$. For a monotone
increasing graph property $\mathcal{P}$, as the number of edges increases
throughout this process, there must be a least index $i$ such that
$G_{i}\in\mathcal{P}$. This index, which is a random variable, is called the
_hitting time_ for $\mathcal{P}$ in the random graph process. A classical
result of Bollobás and Thomason [10] asserts that a.a.s. the hitting time for
connectivity in this random graph process coincides with the hitting time for
having minimum degree at least $1$. Haller and Trujić [29] showed that a local
resilience version of this result holds: a.a.s. every $G_{i}$ which has
minimum degree at least $1$ in the random graph process satisfies that every
$(1/2+\epsilon)$-subgraph of $G_{i}$ is connected.

A similar process to the random graph process can be defined for random
geometric graphs. Recall that here one considers $n$ independent uniform
random variables on $[0,1]^{d}$. Let these variables be $X_{1},\ldots,X_{n}$.
For each
$e=ij\in\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{[n]}{2}\kern-1.00006pt\bigr{)}$,
consider the random variable $\lVert e\rVert\coloneqq\lVert
X_{i}-X_{j}\rVert$. These define a total order on
$\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{[n]}{2}\kern-1.00006pt\bigr{)}$
(note that all distances are distinct with probability $1$). We label all
pairs as
$e_{1},\ldots,e_{\left(\kern-0.70004pt\genfrac{}{}{0.0pt}{}{n}{2}\kern-0.70004pt\right)}$
so that $\lVert e_{i}\rVert<\lVert e_{j}\rVert$ whenever $1\leq
i<j\leq\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{2}\kern-1.00006pt\bigr{)}$.
Then, for each
$i\in\\{0\\}\cup[\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{2}\kern-1.00006pt\bigr{)}]$,
we let $G_{i}\coloneqq([n],\\{e_{j}:j\in[i]\\})$. This again defines a random
sequence of nested graphs, to which we refer here as the _$d$ -dimensional
random geometric graph process_. A classical result of Penrose [45, 46] shows
that a phenomenon similar to that of the Erdős-Rényi random graph process
occurs when $d\geq 2$: in the random geometric graph process, a.a.s. every
$G_{i}$ which has minimum degree at least $1$ is connected (see also [47,
Theorem 13.17]). The same does not hold when $d=1$: in this case, there is a
positive probability that, as edges are added one by one throughout the
process, all isolated vertices disappear while leaving a disconnected graph.
In fact, the sharp threshold for connectivity and the sharp threshold for
having minimum degree at least $1$ in $G_{1}(n,r)$ differ by a factor of $2$
[28].

Theorem 1.6 $(\mathrm{i})$ provides a range of $r$ above the sharp threshold
for connectivity where $G_{1}(n,r)$ is not $(1/2-\epsilon)$-resilient with
respect to connectivity. This shows a contrasting behaviour with respect to
binomial random graphs, and more in line with the result for random regular
graphs, proving that a polynomial dependency between $C$ and $\epsilon$ cannot
be avoided. More interesting is the consequence of Theorem 1.6
$(\mathrm{ii})$: it implies that, in contrast with the case of the Erdős-Rényi
random graph process, a local resilience version of the hitting time result of
Penrose [45, 46] also fails when $d=2$. It would be interesting to determine
whether this is also the case for larger $d$ or, on the contrary, a hitting
time version holds for sufficiently large $d$.

######  Problem 1.7.

Determine whether there exists a positive integer $d_{0}$ such that the
following holds: for every $d\geq d_{0}$ and every $\epsilon\in(0,1/2]$,
a.a.s. every graph in the $d$-dimensional random geometric graph process with
minimum degree at least one satisfies that each of its
$(1/2+\epsilon)$-subgraphs is connected.

It is worth bringing up the fact that Montgomery [38] and Nenadov, Steger and
Trujić [42] obtained a local resilience version of the hitting time result for
Hamiltonicity (Nenadov, Steger and Trujić [42] also proved an analogous result
for perfect matchings). Theorem 1.6 shows that such a result is impossible for
random geometric graphs when $d\in\\{1,2\\}$. If the answer to 1.7 is
affirmative, it would be interesting to determine whether a local resilience
hitting time result for Hamiltonicity is possible in the random geometric
graph process for sufficiently large $d$.

###  1.3. Long cycles

Next, we turn our attention to the existence of long cycles in $G_{d}(n,r)$.
In view of Proposition 1.5, it would be meaningful to show that every
$(1/2+\epsilon)$-subgraph of $G_{d}(n,r)$ contains cycles of linear length. It
turns out that not only linearly long cycles exist, but for any fixed vertex
$v$ in $G_{d}(n,r)$, at least one such cycle goes through $v$.

######  Theorem 1.8.

For every $\epsilon\in(0,1/2]$ and integer $d\geq 1$, there exist positive
constants $c_{3}=c_{3}(d,\epsilon)$ and $C_{3}=C_{3}(d,\epsilon)$ such that,
if $r\in[C_{3}(\log n/n)^{1/d},c_{3}]$, then a.a.s. $G_{d}(n,r)$ satisfies the
following property: for every integer $L\in[c_{3}^{-1},2n/3]$, every
$(1/2+\epsilon)$-subgraph $H\subseteq G_{d}(n,r)$ and every vertex $v\in
V(G_{d}(n,r))$, there is a cycle of length $L$ in $H$ containing $v$.

We note that, under the assumptions of Theorem 1.8, a.a.s. all vertices are
contained in cycles of any constant even length $L\geq 4$; for more details,
see Remark 4.2.

If Conjecture 1.3 holds, in the light of Theorem 1.8, it is tempting to
believe that well-connected random geometric graphs are $(1/2\pm
o(1))$-resilient with respect to the property of containing a cycle of any
sufficiently large length.

######  Conjecture 1.9.

For a suitable choice of $c_{3}$ and $C_{3}$, Theorem 1.8 holds for all
$L\in[c_{3}^{-1},n]$.

In fact, it is also conceivable that a version of Conjecture 1.3 for
pancyclicity (that is, the property of containing cycles of all lengths
between 3 and $n$) holds as well.

###  1.4. Lower bounds on the local resilience with respect to Hamiltonicity

As a way of making progress towards Conjecture 1.3, we also prove lower bounds
on the local resilience of random geometric graphs with respect to
Hamiltonicity. For each $d\geq 1$, let $\theta_{d}$ denote the volume of a
$d$-dimensional ball with radius 1.

######  Theorem 1.10.

For every constant $\epsilon\in(0,1/(2d^{d/2}\theta_{d})]$ and integer $d\geq
1$, there exists a constant $C_{4}=C_{4}(d,\epsilon)>0$ such that, for
$C_{4}(\log n/n)^{1/d}\leq r=o(1)$, a.a.s. every
$(1-1/(2d^{d/2}\theta_{d})+\epsilon)$-subgraph of $G_{d}(n,r)$ is Hamiltonian.

This shows that a.a.s. every $(3/4+\epsilon)$-subgraph of $G_{1}(n,r)$ is
Hamiltonian, while for $G_{2}(n,r)$ we can only prove the conclusion for
$(c+\epsilon)$-subgraphs, where $c\approx 0.92$. The bound on the local
resilience that we obtain becomes smaller as $d$ grows. This approach can be
improved by a more careful (albeit technical) analysis. We provide a stronger
result for the case $d=1$, where the analysis is simple and already showcases
all the ideas.

######  Theorem 1.11.

For every constant $\epsilon\in(0,1/3]$, there exists a constant
$C_{5}=C_{5}(\epsilon)>0$ such that, for $C_{5}\log n/n\leq r=o(1)$, a.a.s.
every $(2/3+\epsilon)$-subgraph of $G_{1}(n,r)$ is Hamiltonian.

We believe the constant $2/3$ cannot be improved with our current approach.
The analysis here can yield improvements for all $d\geq 1$ in Theorem 1.10,
but the resulting constant will still tend to $0$ as $d$ grows (see Remark
5.4). Of course, we do not believe these results to be tight and would be
interested in seeing improvements upon them.

###  1.5. The one-dimensional torus and powers of cycles

A well-studied variant of the random geometric graph is the _toroidal random
geometric graph_. For positive integers $n$ and $d$ and a positive real number
$r$, the toroidal random geometric graph $T_{d}(n,r)$ is defined analogously
to $G_{d}(n,r)$, the only difference being that the $n$ random points are
sampled from $\mathbb{R}^{d}/\mathbb{Z}^{d}$. This model removes the effect of
the boundary and, therefore, it sometimes results in a more straightforward
analysis. We believe that Conjecture 1.3 should also hold if we replace
$G_{d}(n,r)$ by $T_{d}(n,r)$. Note, moreover, that Theorems 1.4, 1.6, 1.8,
1.10 and 1.11 as well as Proposition 1.5 also hold in the toroidal setting.

Even when $d=1$, Conjecture 1.3 and its analogue for the torus remain open. A
possibility to tackle this problem is to reduce it to a deterministic,
structural problem using the following observation. Given a graph $G$, its
$k$-th power, denoted $G^{k}$, is obtained by adding an edge between any two
vertices of $G$ whose (graph) distance in $G$ is at most $k$. We denote a
cycle on $n$ vertices by $\mathcal{C}_{n}$.

######  Lemma 1.12.

For every constant $\epsilon\in(0,1]$, there exists a constant
$C_{6}=C_{6}(\epsilon)>0$ such that, for $r\in[C_{6}\log n/n,1/2]$, a.a.s.
$\mathcal{C}_{n}^{(1-\epsilon)rn}\subseteq
T_{1}(n,r)\subseteq\mathcal{C}_{n}^{(1+\epsilon)rn}$.

In view of this, in order to prove the case $d=1$ of the toroidal version of
Conjecture 1.3, it would suffice to study the local resilience of (high)
powers of cycles with respect to Hamiltonicity. We propose the following
stronger conjecture, which may be of independent interest.

######  Conjecture 1.13.

For all integers $n\geq 3$ and $k\in[1,n/2]$, every graph
$H\subseteq\mathcal{C}_{n}^{k}$ with $\delta(H)\geq k+1$ is Hamiltonian.

Note that the case $k=1$ holds trivially and the cases $k\geq n/2-1$ follow as
a consequence of Dirac’s theorem. Thus, if true, Conjecture 1.13 would extend
Dirac’s theorem to powers of cycles. Here we prove the first non-trivial case
of the conjecture.

######  Proposition 1.14.

For every integer $n\geq 4$, every graph $H\subseteq\mathcal{C}_{n}^{2}$ with
$\delta(H)\geq 3$ is Hamiltonian.

######  Remark 1.15.

The approach to local resilience of random geometric graphs via local
resilience of powers of graphs is not exclusive to the torus. Indeed, one may
simply observe that the conclusion of Lemma 1.12 can be replaced by
$P_{n}^{(1-\epsilon)rn}\subseteq G_{1}(n,r)\subseteq P_{n}^{(1+\epsilon)rn}$
and, therefore, the case $d=1$ of Conjecture 1.3 could also be derived from a
structural statement. Providing natural analogues of Lemma 1.12 and Conjecture
1.13 for higher dimensions would definitely be of interest.

###  1.6. More related work

In addition to the binomial random graph and the random regular graph, the
local resilience of random graphs with respect to Hamiltonicity has also been
considered in other settings. For example, in the setting of binomial random
directed graphs, Montgomery [39] gave a best possible hitting time result,
improving on earlier work [30, 21]. Hamiltonicity has also been considered in
binomial random hypergraphs; see the works of Clemens, Ehrenmüller and Person
[12] for Hamilton Berge cycles, of Allen, Parczyk and Pfenninger [3] for tight
Hamilton cycles, and of Petrova and Trujić [49] for loose Hamilton cycles in
$3$-uniform hypergraphs.

In addition to Hamiltonicity, other graph properties have been studied in the
context of local resilience. This is the case, for instance, of pancyclicity
[34], (almost) spanning trees [6], different (almost) $F$-factors [7, 15, 41],
squares of (almost) Hamilton cycles [43, 22], or general bounded-degree graphs
[31, 2, 1]. We believe studying these questions in random geometric graphs
would be very interesting.

The study of local resilience of graph properties fits more generally within
the framework of the study of robustness. For more references on this topic,
we refer the reader to the survey of Sudakov [54].

###  1.7. Paper organisation

In Section 2, we introduce the necessary notation for the paper, as well as an
auxiliary probabilistic result. We devote Section 3 to our results on
connectivity, and Section 4 to the results about long cycles. In Section 5, we
prove our lower bounds on the local resilience of random geometric graphs with
respect to Hamiltonicity. Lastly, in the short Section 6, we discuss the
$1$-dimensional case on the torus.

##  2\. Notation and preliminary results

For any $n\in\mathbb{Z}$, we denote $[n]\coloneqq\\{i\in\mathbb{N}:1\leq i\leq
n\\}$. We denote by $\log$ the logarithm with base $\mathrm{e}$. Given any
real numbers $a,b,c\in\mathbb{R}$, we write $a=b\pm c$ to mean that
$a\in[b-c,b+c]$.

We sometimes introduce parameters (say, $a$, $b$ and $c$) with the notation
$0<a\lll b,c\leq 1$; parameters presented in this way are said to appear in a
_hierarchy_. Parameters in a hierarchy are chosen from right to left. Indeed,
when a statement holds for $0<a\lll b,c\leq 1$, we mean that there exists some
unspecified increasing function
$f\colon(0,\infty)\times(0,\infty)\to(0,\infty)$ such that the statement holds
for all $0<b,c\leq 1$ and for all $0<a\leq f(b,c)$. This extends naturally to
longer hierarchies or to hierarchies where some parameter depends on more than
two other parameters. Intuitively, when we use a hierarchy as above, the
reader should simply understand that, for all $b,c\in(0,1]$, we choose $a$
sufficiently small (in terms of $b$ and $c$) for the subsequent claims to
hold. When writing asymptotic statements, we will often implicitly assume that
$n$ is sufficiently large for the claims to hold (and, in particular, much
larger than all parameters defined in a hierarchy, which are always treated as
constants). For asymptotic comparisons, we use the standard ‘big-O’ notation,
where usually all asymptotic statements will be with respect to a parameter
$n$ corresponding to the number of vertices of a graph. When using asymptotic
statements with respect to other variables, the variables in question will
appear as a subindex, such as $O_{x}$ and $o_{t}$. For the sake of
readability, we ignore rounding issues whenever they do not affect the
validity of the claims.

The notation $|\cdot|$ is used to denote either the _size_ of a finite set or
the _$d$ -dimensional volume_ of a region of $\mathbb{R}^{d}$. In particular,
given a finite set of points $V\subseteq\mathbb{R}^{d}$ and a region
$R\subseteq\mathbb{R}^{d}$, we write $|V\cap R|$ for the number of points of
$V$ contained in $R$. Given any point $p\in\mathbb{R}^{d}$ and any
$0<r_{1}<r_{2}$, we will write $B(p,r_{1})$ to denote the (closed) ball of
radius $r_{1}$ centred at $p$, and $B(p,r_{1},r_{2})\coloneqq
B(p,r_{2})\setminus B(p,r_{1})$ denotes the annulus with radii $r_{1}$ and
$r_{2}$. Moreover, for a set $\Lambda\subseteq\mathbb{R}^{d}$, we denote by
$\partial\Lambda$ the topological boundary of the set $\Lambda$. We denote by
$\theta_{d}$ the volume of a $d$-dimensional ball with radius $1$. We will use
the fact that, for all $d\geq 1$,

$\theta_{d}=|B(0,1)|=\frac{\uppi^{d/2}}{\mathrm{Gamma}(d/2+1)}\geq\max\left(\frac{\uppi^{d/2}}{2d^{d/2+1}},\frac{1}{d^{d/2}}\right),$
(2.1)

where $\mathrm{Gamma}(\cdot)$ stands for the Gamma function. Throughout the
paper, vertices of $G_{d}(n,r)$ are often identified with their geometric
positions in $[0,1]^{d}$ without explicit mention.

Given a graph $G$, we denote by $V(G)$ its vertex set and by $E(G)$ its edge
set. As is standard, if $\\{u,v\\}\in E(G)$, we abbreviate the notation to
$uv=\\{u,v\\}$. For any disjoint sets $U,W\subseteq V(G)$, we denote by $G[U]$
the subgraph of $G$ _induced_ by $U$, and by $G[U,W]$ the bipartite subgraph
of $G$ _induced_ by $U$ and $W$. Given a set $U\subseteq V(G)$, we denote by
$G-U\coloneqq G[V(G)\setminus U]$. Given a vertex $v\in V(G)$, we define its
_neighbourhood_ $N_{G}(v)\coloneqq\\{u\in V(G):uv\in E(G)\\}$ and its degree
$d_{G}(v)\coloneqq|N_{G}(v)|$. When talking about the neighbourhood of a
vertex $v$ and considering two or more graphs, if we wish to emphasise that
the graph in which a vertex $u$ is a neighbour of $v$ is $G$, we will say that
$u$ is a _$G$ -neighbour_ of $v$. For any integer $k\geq 1$, we say that $G$
is _$k$ -connected_ if $|V(G)|>k$ and, for every $U\subseteq V(G)$ of size
$|U|<k$, the graph $G-U$ is connected.

A _path_ is a graph $P$ whose vertex set admits a labelling
$V(P)=\\{u_{1},\ldots,u_{\ell+1}\\}$ such that
$E(P)=\\{u_{i}u_{i+1}:i\in[\ell]\\}$. (In particular, we allow for a path to
consist of a single vertex.) A _cycle_ is a graph $C$ which can be obtained
from a path $P$ with $\ell\geq 2$ by setting $V(C)\coloneqq V(P)$ and
$E(C)\coloneqq E(P)\cup\\{u_{1}u_{\ell+1}\\}$. The _length_ of a path or a
cycle is its number of edges. For a graph $G$ and two vertices $u,v\in V(G)$,
we say that $G$ contains a _$(u,v)$ -path_ if it contains a path starting at
$u$ and ending at $v$. Moreover, for two sets $U,V\subseteq V(G)$, we say that
$G$ contains a _$(U,V)$ -path_ if there exist $u\in U$ and $v\in V$ such that
$G$ contains a $(u,v)$-path. Extending the abbreviated notation for edges, a
list of vertices should be understood as a path; for example, for vertices
$u,v,x,y$, we write $P=uvxy$ to denote the path with vertex set
$V(P)=\\{u,v,x,y\\}$ and edge set $E(P)=\\{uv,vx,xy\\}$. This abbreviation
allows to concatenate paths to construct longer paths (or cycles). For the
sake of clarity when using concatenations, if $P$ is a $(u,v)$-path, we write
$uPv$ to emphasise the endpoints of $P$. As an example, if $P$ is a
$(u,v)$-path and $Q$ is a $(v,w)$-path with $V(P)\cap V(Q)=\\{v\\}$, we may
write $uPvQw$ to denote the path obtained by concatenating $P$ and $Q$.
Similarly, if $Q$ is an $(x,y)$-path with $V(P)\cap V(Q)=\varnothing$ and $vx$
is an edge, we write $uPvxQz$ to mean the concatenation of $P$ and $Q$ through
the edge $vx$. We denote iterated concatenations with the symbol $\bigtimes$.

Sometimes, rather than considering a random geometric graph, it is useful to
consider a fixed set of points $V$ on $[0,1]^{d}$ and construct a geometric
graph on this vertex set. Given $r>0$, we denote by $G(V,r)$ the graph with
vertex set $V$ where two vertices $x,y\in V$ are joined by an edge whenever
$\lVert x-y\rVert\leq r$ (we omit the dimension from the notation $G(V,r)$
since it is implied by the set $V$).

Some of our proofs share certain ingredients, and so it is useful to provide
some global definitions here. In particular, it is often the case that we
“split” the hypercube $[0,1]^{d}$ into smaller regions and use them to define
large structures in $G_{d}(n,r)$. To be more precise, we often tessellate the
hypercube $[0,1]^{d}$ with smaller axis-parallel hypercubes of the same side
length (which will be the inverse of an integer). We refer to these smaller
hypercubes as _cells_ , and denote the set of all cells by $\mathcal{Q}$.
Formally, we consider each cell as a closed hypercube, so different cells may
intersect at their boundaries. In practice, these intersections are
negligible: when considering the vertices of $G_{d}(n,r)$, the probability
that any of them lie on the boundary of one of the cells is $0$. Given a
tessellation of $[0,1]^{d}$ with cells, we will often use an auxiliary graph
$\Gamma$ with vertex set $\mathcal{Q}$ where two cells are joined by an edge
whenever they share a common $(d-1)$-dimensional face. (Note that $\Gamma$ is
a $d$-dimensional grid.)

We will make use of the following well-known Chernoff bound (see, e.g., the
book of Janson, Łuczak and Ruciński [33, Corollary 2.3]).

######  Lemma 2.1 (Chernoff’s bound).

Let $X$ be the sum of $n$ independent Bernoulli random variables and let
$\mu\coloneqq\mathbb{E}[X]$. Then, for all $\delta\in[0,1]$, we have that
$\mathbb{P}[|X-\mu|\geq\delta\mu]\leq 2\mathrm{e}^{-\delta^{2}\mu/3}$.

##  3\. Connectivity

###  3.1. The local resilience of random geometric graphs with respect to
connectivity

Our aim in this section is to prove Theorem 1.4 and Proposition 1.5. In fact,
we prove the following stronger result, which clearly implies Theorem 1.4.

######  Theorem 3.1.

For every constant $\epsilon\in(0,1/2]$ and integer $d\geq 1$, there exist
constants $c_{1}=c_{1}(d,\epsilon)>0$ and $C_{1}=C_{1}(d,\epsilon)>0$ such
that, for every $r\in[C_{1}(\log n/n)^{1/d},\sqrt{d}]$, a.a.s. every
$(1/2+\epsilon)$-subgraph of $G_{d}(n,r)$ is $(c_{1}r^{d}n)$-connected.
Moreover, one may take $C_{1}=K\epsilon^{-2/d}\sqrt{d}$, where $K$ is an
absolute constant.

We point out that Theorem 3.1 is optimal simultaneously with respect to the
constant $1/2$, the connectivity of the subgraphs of $G_{d}(n,r)$ (up to the
value of $c_{1}$) and the growth of $C_{1}$ with respect to $d$. For the
second point, note that the connectivity of a graph is always at most its
minimum degree and, in the given range of $r$, a.a.s. the minimum degree of
$G_{d}(n,r)$ is proportional to $r^{d}n$. Moreover, concerning the last point,
for any fixed $\epsilon$, the expression $C_{1}(\log n/n)^{1/d}$ has to be at
least as large as the sharp threshold for connectivity of the random geometric
graph $G_{d}(n,r)$. This shows that $C_{1}=\Omega_{d}(\sqrt{d})$ is necessary
in Theorem 3.1 (see [47, Theorem 13.2] for a concrete expression), which
matches our bound of $C_{1}=O_{d}(\sqrt{d})$ (for fixed $\epsilon$).

The proof of Theorem 3.1 relies on the following ideas. First, divide the
hypercube $[0,1]^{d}$ into cells of side length $s=\Omega(r)$ (and, thus,
volume $\Omega(\log n/n)$). We say that a cell is good if, roughly speaking,
it contains at least $s^{d}n/2$ vertices of $G_{d}(n,r)$ and every two
vertices sufficiently close to the cell share almost the same neighbourhood in
$G_{d}(n,r)$; we say that the cell is bad otherwise. We show that a.a.s. there
are only a few bad cells and these are grouped into clusters of bounded size,
which are far from each other. Then, fixing a $(1/2+\epsilon)$-subgraph $H$ of
$G_{d}(n,r)$, we use this observation to deduce that there is a large cluster
of good cells containing a set of points that spans a
$(c_{1}r^{d}n)$-connected graph $H^{\prime}\subseteq H$. This relies on the
fact that all pairs of vertices in neighbouring good cells have many common
neighbours in any $(1/2+\epsilon)$-subgraph $H$ of $G_{d}(n,r)$. Finally, we
show that the points outside $H^{\prime}$ could be added consecutively to
$H^{\prime}$ so that every vertex has at least $c_{1}r^{d}n$ neighbours among
the vertices already in the graph.

Several technical details of this proof can be simplified significantly if one
does not try to optimise the dependency of $C_{1}$ on $d$. For the sake of the
reader who wants to understand the basic ideas, we include this simpler proof
in Appendix A.

We now proceed to prove Theorem 3.1. We begin with an auxiliary combinatorial
lemma.

######  Lemma 3.2.

Fix an integer $k\geq 1$ and a graph $G$ with vertex set $V$. Suppose that
there is a set $V^{\prime}\subseteq V$ such that the following two properties
hold.

  1. $(\mathrm{A}1)$

For every set $U\subseteq V$ of size $k-1$, any pair of vertices in
$V^{\prime}\setminus U$ is connected by a path in $G-U$.

  2. $(\mathrm{A}2)$

Set $t\coloneqq|V|-|V^{\prime}|$. Then, there is an ordering
$v_{1},\ldots,v_{t}$ of the vertices in $V\setminus V^{\prime}$ such that, for
every $i\in[t]$, $v_{i}$ has at least $k$ neighbours in
$V^{\prime}\cup\\{v_{1},\ldots,v_{i-1}\\}$.

Then, the graph $G$ is $k$-connected.

###### Proof.

Fix an arbitrary set $U\subseteq V$ of size $k-1$. On the one hand, the first
assumption implies that all vertices in $V^{\prime}\setminus U$ belong to the
same connected component of $G-U$. On the other hand, for every $i\in[t]$, if
$v_{i}\notin U$, then $v_{i}$ is adjacent to a vertex among
$(V^{\prime}\cup\\{v_{1},\ldots,v_{i-1}\\})\setminus U$. Thus, an immediate
induction shows that each of the vertices in
$\\{v_{1},\ldots,v_{t}\\}\setminus U$ connects by a path in $G-U$ to
$V^{\prime}\setminus U$, which concludes the proof. ∎

Given $d\geq 1$, $\epsilon\in(0,1/2]$ and $r\leq\sqrt{d}$, let $\mathcal{Q}$
be a tessellation of $[0,1]^{d}$ with cells of side length
$s=s(d,\epsilon,r)=1/\lceil 4\sqrt{d}/\delta r\rceil$, where
$\delta=\delta(d,\epsilon)>0$ is the unique positive solution of the equation

$((1+\delta)^{d}-(1-\delta)^{d})4^{d+1}d^{d/2}=\epsilon.$ (3.1)

We say that two cells in $\mathcal{Q}$ are _neighbours_ (or _neighbouring_) if
they are adjacent in the auxiliary graph $\Gamma$, that is, if their
intersection is a $(d-1)$-dimensional hypercube. Note that, by the definition
of $s$, the union of any pair of neighbouring cells has diameter at most
$\delta r$. Given a set of $n$ points $V\subseteq[0,1]^{d}$ and the geometric
graph $G=G(V,r)$, we call a cell $q\in\mathcal{Q}$ _bad_ (for $G$) if at least
one of the following conditions holds:

  1. $(\mathrm{a})$

$|V\cap q|\leq s^{d}n/2$;

  2. $(\mathrm{b})$

there exist a cell $q^{\prime}\in N_{\Gamma}(q)\cup\\{q\\}$ and distinct
vertices $v\in V\cap q$ and $v^{\prime}\in V\cap q^{\prime}$ such that

$|N_{G}(v)\cap
N_{G}(v^{\prime})|\leq(1-\epsilon)\max(|N_{G}(v)|,|N_{G}(v^{\prime})|),$

that is, the common neighbours of $v$ and $v^{\prime}$ in $G$ are at most a
$(1-\epsilon)$-proportion of all neighbours of $v$ or of all neighbours of
$v^{\prime}$ in $G$.

Otherwise, we say that the cell is _good_. Finally, we construct an auxiliary
graph $\Gamma_{\mathrm{bad}}=\Gamma_{\mathrm{bad}}(G)$ whose vertex set is the
set of bad cells in $\mathcal{Q}$ and where a pair of bad cells form an edge
if they are at (Euclidean) distance at most $4r$ from each other.

######  Lemma 3.3.

The following statements hold.

  1. $(\mathrm{B}1)$

For every fixed integer $d\geq 1$ and $\epsilon\in(0,1/2]$, there exists a
constant $M=M(d,\epsilon)>0$ such that the following holds. If $(\log
n/n)^{1/d}\leq r=o(1)$ and $G\sim G_{d}(n,r)$, then a.a.s. every connected
component of $\Gamma_{\mathrm{bad}}$ has fewer than $M$ vertices.

  2. $(\mathrm{B}2)$

Let $d\geq 1$ and $\epsilon\in(0,1/2]$ be fixed, and let $r=\omega((\log
n/n)^{1/d})$ with $r\leq\sqrt{d}$. Let $G\sim G_{d}(n,r)$. Then, a.a.s. there
are no bad cells.

###### Proof.

Let $d$ and $\epsilon$ be given, and define $\delta=\delta(d,\epsilon)$ as in
(3.1). For each point $x\in[0,1]^{d}$, define the regions

$S_{1}(x)\coloneqq[0,1]^{d}\cap B(x,(1+\delta)r),\quad
S_{2}(x)\coloneqq[0,1]^{d}\cap B(x,(1-\delta)r)\quad\text{and}\quad
S_{3}(x)\coloneqq S_{1}(x)\setminus S_{2}(x).$

Note that, if $u,u^{\prime}$ are two vertices as in $(\mathrm{b})$, then, as
the diameter of the union of two neighbouring cells is at most $\delta r$, we
have that

$S_{2}(x)\subseteq[0,1]^{d}\cap B(u,r)\cap B(u^{\prime},r)\quad\text{ and
}\quad[0,1]^{d}\cap(B(u,r)\cup B(u^{\prime},r))\subseteq S_{1}(x).$ (3.2)

By (3.1), our choice of $\delta$ yields

$\displaystyle|S_{3}(x)|$
$\displaystyle\leq((1+\delta)^{d}-(1-\delta)^{d})|B(x,r)|$
$\displaystyle=((1+\delta)^{d}-(1-\delta)^{d})(4d)^{d/2}\left|B\left(x,\frac{r}{2\sqrt{d}}\right)\right|$
$\displaystyle\leq((1+\delta)^{d}-(1-\delta)^{d})(4d)^{d/2}2^{d}|S_{1}(x)|=\frac{\epsilon|S_{1}(x)|}{4},$
(3.3)

where the second inequality follows from the fact that, for any ball $B$ with
radius $r/2\sqrt{d}\leq 1/2$ centred at a point in $[0,1]^{d}$, $|B|\leq
2^{d}|B\cap[0,1]^{d}|$. Together with (3.3), the following claim ensures that,
if a cell is bad, then there is a nearby region with atypically many or
atypically few vertices.

######  Claim 1.

If a cell $q\in\mathcal{Q}$ with centre $x$ does not satisfy $(\mathrm{a})$,
the presence of a cell $q^{\prime}\in N_{\Gamma}(q)\cup\\{q\\}$ and vertices
$u\in V(G)\cap q$ and $u^{\prime}\in V(G)\cap q^{\prime}$ witnessing
$(\mathrm{b})$ implies that

$|V(G)\cap S_{3}(x)|\geq\frac{\epsilon}{2}|V(G)\cap S_{1}(x)|.$

###### Proof.

By (3.2), we conclude that

$\displaystyle|V(G)\cap S_{2}(x)|$ $\displaystyle\leq|N_{G}(u)\cap
N_{G}(u^{\prime})|+2$ $\displaystyle\leq(1-\epsilon)(\max(|V(G)\cap
B(u,r)|,|V(G)\cap B(u^{\prime},r)|)-1)+2$
$\displaystyle\leq(1-\epsilon)|V(G)\cap S_{1}(x)|+2$
$\displaystyle\leq(1-\epsilon/2)|V(G)\cap S_{1}(x)|,$

where the second inequality uses $(\mathrm{b})$ and the last inequality relies
on $|V(G)\cap S_{1}(x)|$ being sufficiently large, which is guaranteed if
$(\mathrm{a})$ does not hold for $q$. The desired inequality now follows by
substituting this into the equality $|V(G)\cap S_{1}(x)|=|V(G)\cap
S_{2}(x)|+|V(G)\cap S_{3}(x)|$. ∎

We focus on the proof of $(\mathrm{B}1)$. First, since the diameter of a
single cell is bounded from above by $\delta r/2$, given a cell
$q\in\mathcal{Q}$ with centre $x$, the ball $B(x,(16+\delta)r)$ contains all
cells at distance at most $16r$ from $q$. In particular, the number of these
cells is at most

$\frac{|B(0,(16+\delta)r)|}{s^{d}}\leq|B(0,16+\delta)|\bigg{(}\frac{8\sqrt{d}}{\delta}\bigg{)}^{d}\eqqcolon
N.$

Let $\ell\coloneqq\lceil\max\\{15\cdot 4^{d}d^{d/2}/\delta^{d},\ 50\cdot
2^{d}/\theta_{d},\ 25\cdot 8^{d}d^{d/2}/\epsilon\theta_{d}\\}\rceil$. We are
going to show that $M\coloneqq 4N\ell$ satisfies the condition of the lemma.

Suppose that a connected component $\Gamma_{c}$ of $\Gamma_{\mathrm{bad}}$
with $|V(\Gamma_{c})|\geq M$ exists. Given such a component, we
algorithmically construct a set $W\subseteq V(\Gamma_{c})$ of bad cells at
(Euclidean) distance at least $(12-\delta)r$ from each other as follows. Set
$S\coloneqq V(\Gamma_{c})$. At the first step, select an arbitrary cell $q\in
S$, add it to $W$ and delete from $S$ all cells at distance at most
$(12-\delta)r$ from $q$. Then, as long as $S$ is not empty, select a cell
$q\in S$ at smallest distance to $V(\Gamma_{c})\setminus S$, add $q$ to $W$
and delete from $S$ all cells at distance at most $(12-\delta)r$ from $q$.

Observe that the above construction ensures that $|W|\geq 4\ell$ since at most
$N$ cells are deleted from $S$ at every step. Moreover, the graph
$\Gamma_{c}^{\prime}$ with vertex set $W$ obtained by adding an edge between
every two cells in $W$ at distance at most $16r$ from each other is connected:
indeed, by the connectivity of $\Gamma_{c}$, every cell added to $W$ is at
distance at most $4r$ from an already deleted cell, and cells have diameter at
most $\delta r/2$, so the conclusion follows by the triangle inequality. Then,
by pruning a spanning tree of $\Gamma_{c}^{\prime}$, we find a set
$W^{\prime}\subseteq W$ such that $|W^{\prime}|=4\ell$ and
$\Gamma_{c}^{\prime}[W^{\prime}]$ is a connected graph.

The conclusion at this point is that, in order for a connected component
$\Gamma_{c}$ of $\Gamma_{\mathrm{bad}}$ with $|V(\Gamma_{c})|\geq M$ to exist,
one must be able to find a set of cells $W^{\prime}\subseteq V(\Gamma_{c})$ of
size $4\ell$ such that

  1. (1)

every pair of cells in $W^{\prime}$ are at distance at least $(12-\delta)r$
from each other,

  2. (2)

there is a labelling $q_{1},\ldots,q_{4\ell}$ of the cells in $W^{\prime}$
such that, for each $i\in[4\ell]\setminus\\{1\\}$, $q_{i}$ is at distance at
most $16r$ from some cell $q_{j}$ with $j\in[i-1]$, and

  3. (3)

all cells in $W^{\prime}$ are bad.

If this occurs, then all cells in a subset $U_{1}\subseteq W^{\prime}$ of size
$|U_{1}|=2\ell$ are bad because of condition $(\mathrm{a})$, or all cells in a
subset $U_{2}\subseteq W^{\prime}$ of size $|U_{2}^{\prime}|=2\ell$ are bad
because of condition $(\mathrm{b})$ but not because of $(\mathrm{a})$. Our
goal now is to show that the probability that such sets $W^{\prime}$, $U_{1}$
and $U_{2}$ exist tends to $0$. Let $\mathcal{U}$ denote the family of all
possible sets of $2\ell$ cells which are contained in one of the sets
$W^{\prime}$ described above. For each $U\in\mathcal{U}$, let
$\mathcal{B}_{\mathrm{a}}(U)$ be the event that all cells in $U$ are bad
because of condition $(\mathrm{a})$, and let $\mathcal{B}_{\mathrm{b}}(U)$ be
the event that all cells in $U$ are bad because of condition $(\mathrm{b})$
but not because of condition $(\mathrm{a})$. With this notation, from the
discussion above, the probability that $\Gamma_{\mathrm{bad}}$ contains a
connected component with at least $M$ cells is bounded from above by

$\sum_{U\in\mathcal{U}}\mathbb{P}[\mathcal{B}_{\mathrm{a}}(U)]+\mathbb{P}[\mathcal{B}_{\mathrm{b}}(U)].$
(3.4)

The number of choices for sets $U\in\mathcal{U}$ that we need to consider can
be bounded as follows. First, one must construct a set $W^{\prime}$ of $4\ell$
cells satisfying property (2). Such a set can be constructed sequentially in
such a way that each added cell (except the first one) is at distance at most
$16r$ from some previously considered cell. The number of choices for the
first cell is at most $|\mathcal{Q}|$, and for each subsequent cell we have at
most $4\ell N$ choices. Once $W^{\prime}$ is defined, one can choose a subset
of size $2\ell$ from all the chosen cells. Thus, using the lower bound on $r$
given in the statement, we conclude that

$|\mathcal{U}|\leq|\mathcal{Q}|(4\ell
N)^{4\ell-1}\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{4\ell}{2\ell}\kern-1.00006pt\right)=O(|\mathcal{Q}|)=o(n).$
(3.5)

Now, fix $U\in\mathcal{U}$. Consider the probability that all cells in $U$ are
bad because of condition $(\mathrm{a})$. For this to happen, the union of the
cells must contain at most $\ell s^{d}n$ vertices. By Chernoff’s inequality
(Lemma 2.1), we conclude that

$\mathbb{P}[\mathcal{B}_{\mathrm{a}}(U)]\leq\mathbb{P}[\mathrm{Bin}(n,2\ell
s^{d})\leq\ell s^{d}n]\leq 2\exp(-\ell s^{d}n/6)=o(1/n),$ (3.6)

where the last inequality holds by the choice of $\ell\geq 15\cdot
4^{d}d^{d/2}\delta^{-d}$.

Next, we turn our attention to the possibility that all cells in $U$ are bad
because of $(\mathrm{b})$ but not because of $(\mathrm{a})$. Label the cells
in $U$ as $q_{1},\ldots,q_{2\ell}$. For each $i\in[2\ell]$, let $x_{i}$ denote
the centre of $q_{i}$. Note that, by assumption on the set $U$, any pair of
cells in $U$ are at distance at least $(12-\delta)r$ from each other. Thus,
since $\delta\leq 1$, the regions $\\{S_{1}(x_{i})\\}_{i\in[2\ell]}$ are
pairwise disjoint. For each $i\in[2\ell]$, define the events

$\displaystyle\mathcal{A}_{i}$ $\displaystyle\coloneq\left\\{|V(G)\cap
S_{1}(x_{i})|<|S_{1}(x_{i})|n/2\right\\},$ $\displaystyle\mathcal{B}_{i}$
$\displaystyle\coloneq\\{|V(G)\cap S_{3}(x_{i})|\geq\epsilon|V(G)\cap
S_{1}(x_{i})|/2\\}.$

In view of Claim 1, in order to bound
$\mathbb{P}[\mathcal{B}_{\mathrm{b}}(U)]$ from above, it suffices to bound the
probability that all of the events $\mathcal{B}_{i}$ occur:

$\mathbb{P}[\mathcal{B}_{\mathrm{b}}(U)]\leq\mathbb{P}\left[\bigcap_{i\in[2\ell]}\mathcal{B}_{i}\right].$
(3.7)

Let us first consider the events $\mathcal{A}_{i}$. Let $\mathcal{J}$ be the
(random) set of indices $i\in[2\ell]$ for which $\mathcal{A}_{i}$ does not
hold. Note that, if $|\mathcal{J}|<\ell$, then there are $\ell$ indices
$i\in[2\ell]$ for which $\mathcal{A}_{i}$ holds. Thus, using a union bound, we
conclude that

$\mathbb{P}[|\mathcal{J}|<\ell]\leq\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{2\ell}{\ell}\kern-1.00006pt\right)\max_{I\subseteq[2\ell],\,|I|=\ell}\mathbb{P}\left[\bigcap_{i\in
I}\mathcal{A}_{i}\right]\leq
4^{\ell}\max_{I\subseteq[2\ell],\,|I|=\ell}\Bigg{(}\prod_{i\in
I}\mathbb{P}\Bigg{[}\mathcal{A}_{i}\,\,\Bigg{|}\,\bigcap_{j\in
I,\,j<i}\mathcal{A}_{j}\Bigg{]}\Bigg{)}.$ (3.8)

Fix a set $I\subseteq[2\ell]$ with $|I|=\ell$ and an index $i\in I$. Upon
conditioning on the event $\bigcap_{j\in I,j<i}\mathcal{A}_{j}$, and since the
regions $\\{S_{1}(x_{j})\\}_{j\in[2\ell]}$ are pairwise disjoint and $r=o(1)$,
the random variable $|V(G)\cap S_{1}(x_{i})|$ stochastically dominates a
binomial random variable with parameters $3n/4$ and $|S_{1}(x_{i})|$.
Therefore, using Chernoff’s inequality (Lemma 2.1), we conclude that

$\mathbb{P}\Bigg{[}\mathcal{A}_{i}\,\,\Bigg{|}\,\bigcap_{j\in
I,\,j<i}\mathcal{A}_{j}\Bigg{]}\leq\mathbb{P}\left[\mathrm{Bin}\left(\frac{3}{4}n,|S_{1}(x_{i})|\right)\leq|S_{1}(x_{i})|\frac{n}{2}\right]\leq\exp\left(-\frac{|S_{1}(x_{i})|n}{37}\right).$

Recall that for every point $x\in[0,1]^{d}$ we have that
$|S_{1}(x)|\geq|B(0,r)|/2^{d}\geq\theta_{d}r^{d}/2^{d}$. Thus, by our choice
of $\ell>37\cdot 2^{d}/\theta_{d}$, substituting the above bounds into (3.8)
and using the lower bound on $r$ implies that

$\mathbb{P}[|\mathcal{J}|<\ell]=o(1/n).$ (3.9)

Finally, we focus on the events $\mathcal{B}_{i}$. Fix a set
$J\subseteq[2\ell]$ of size $|J|\geq\ell$ and condition on the event
$\\{\mathcal{J}=J\\}$ and on the random variables $|V(G)\cap S_{1}(x_{i})|$
for all $i\in J\subseteq[2\ell]$. Since the regions
$\\{S_{1}(x_{i})\\}_{i\in[2\ell]}$ are pairwise disjoint, in our conditional
space, the events $(\mathcal{B}_{i})_{i\in J}$ are mutually independent.
Combining this with Chernoff’s inequality for the binomial random variables
$(|V(G)\cap S_{3}(x_{i})|)_{i\in J}$ with (conditional) means $(\mu_{i})_{i\in
J}$, we obtain that

$\displaystyle\mathbb{P}\left[\bigcap_{i\in
J}\mathcal{B}_{i}\,\,\middle|\,\mathcal{J}=J,(|V(G)\cap S_{1}(x_{i})|)_{i\in
J}\right]$ $\displaystyle=\prod_{i\in
J}\mathbb{P}\left[\mathcal{B}_{i}\mid\mathcal{J}=J,|V(G)\cap
S_{1}(x_{i})|\right]$ $\displaystyle\leq\prod_{i\in
J}\mathbb{P}\left[\mathrm{Bin}\left(|V(G)\cap
S_{1}(x_{i})|,\frac{|S_{3}(x_{i})|}{|S_{1}(x_{i})|}\right)\geq
2\mu_{i}\right]$ $\displaystyle\leq 2^{2\ell}\exp\left(-\sum_{i\in
J}\frac{\mu_{i}}{3}\right),$ (3.10)

where the first inequality uses the fact that, by (3.3),

$\mu_{i}=|V(G)\cap
S_{1}(x_{i})|\frac{|S_{3}(x_{i})|}{|S_{1}(x_{i})|}\leq|V(G)\cap
S_{1}(x_{i})|\frac{\epsilon}{4}.$

Moreover, for every $i\in J$, using that the event $\mathcal{A}_{i}$ does not
hold, the bounds on $r$ and the definition of $S_{3}(x_{i})$, we have that

$\displaystyle\mu_{i}=|V(G)\cap
S_{1}(x_{i})|\frac{|S_{3}(x_{i})|}{|S_{1}(x_{i})|}\geq\frac{|S_{1}(x_{i})|n}{2}\frac{|S_{3}(x_{i})|}{|S_{1}(x_{i})|}$
$\displaystyle\geq\frac{((1+\delta)^{d}-(1-\delta)^{d})\theta_{d}r^{d}n}{2^{d+1}}$
$\displaystyle\geq\frac{((1+\delta)^{d}-(1-\delta)^{d})\theta_{d}}{2^{d+1}}\log
n.$

Substituting this into (3.1), together with our choice of $\ell\geq 25\cdot
8^{d}d^{d/2}/\epsilon\theta_{d}$, we have that

$\mathbb{P}\left[\bigcap_{i\in
J}\mathcal{B}_{i}\,\,\middle|\,\mathcal{J}=J,(|V(G)\cap S_{1}(x_{i})|)_{i\in
J}\right]\leq 4^{\ell}\exp\left(-\sum_{i\in
J}\frac{\mu_{i}}{3}\right)=o(1/n).$

Combining this with (3.9) shows that

$\mathbb{P}\left[\bigcap_{i\in[2\ell]}\mathcal{B}_{i}\right]=o(1/n).$ (3.11)

As a result, $(\mathrm{B}1)$ follows by combining (3.4), (3.5), (3.6), (3.7)
and (3.11).

The proof of $(\mathrm{B}2)$ is similar, but much more direct. A combination
of Chernoff’s inequality and a union bound shows that a.a.s. for every cell
$q\in\mathcal{Q}$ we have that $|V(G)\cap q|=(1\pm o(1))s^{d}n$. In
particular, a.a.s. no cell is bad because of condition $(\mathrm{a})$. As for
condition $(\mathrm{b})$, for each $q\in\mathcal{Q}$, let $\mathcal{B}(q)$
denote the event that $q$ is bad because of $(\mathrm{b})$ but not because of
$(\mathrm{a})$. For a fixed cell $q\in\mathcal{Q}$ with centre $x$, we combine
(3.3), Claim 1, the fact that $4/3<2\cdot 3/4$ and Chernoff’s inequality to
bound

$\displaystyle\mathbb{P}[\mathcal{B}(q)]$
$\displaystyle\leq\mathbb{P}\left[|V(G)\cap
S_{3}(x)|\geq\frac{\epsilon}{2}|V(G)\cap S_{1}(x)|\right]$
$\displaystyle\leq\mathbb{P}\left[|V(G)\cap
S_{3}(x)|\geq\frac{4}{3}\mathbb{E}[|V(G)\cap
S_{3}(x)|]\right]+\mathbb{P}\left[|V(G)\cap
S_{1}(x)|\leq\frac{3}{4}\mathbb{E}[|V(G)\cap S_{1}(x)|]\right]$
$\displaystyle\leq 4\exp(-|S_{3}(x)|n/48)=o(1/n),$

where the second inequality follows since the event $\\{|V(G)\cap
S_{3}(x)|\geq\epsilon|V(G)\cap S_{1}(x)|/2\\}$ is contained in the event

$\left\\{|V(G)\cap S_{3}(x)|\geq\frac{4}{3}\mathbb{E}[|V(G)\cap
S_{3}(x)|]\right\\}\cup\left\\{|V(G)\cap
S_{1}(x)|\leq\frac{3}{4}\mathbb{E}[|V(G)\cap S_{1}(x)|]\right\\}.$

The claim follows by a union bound over all $q\in\mathcal{Q}$. ∎

In order to prove Theorem 3.1 as an application of Lemma 3.2, we need one last
auxiliary result.

######  Lemma 3.4.

For every integer $d\geq 1$ and $\epsilon\in(0,1/2]$, fix
$C_{1}^{\prime}=C_{1}^{\prime}(d,\epsilon)\coloneqq
6400\epsilon^{-2/d}\sqrt{d}$. Let $C_{1}^{\prime}(\log n/n)^{1/d}\leq r=o(1)$
and $G\sim G_{d}(n,r)$. Then, a.a.s. the following holds: every vertex $v\in
V(G)$ whose first coordinate $e_{1}=e_{1}(v)$ is at most $2/3$ (resp. at least
$1/3$) has at least $(1/2-\epsilon/2)$-proportion of its neighbours in the
half-space
$h_{v}^{+}\coloneqq\\{(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:x_{1}>e_{1}\\}$
(resp. in the half-space
$h_{v}^{-}\coloneqq\\{(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:x_{1}<e_{1}\\}$).

###### Proof.

We show the statement for $h_{v}\coloneqq h_{v}^{+}$ when $e_{1}\leq 2/3$; the
proof of the statement for $h_{v}^{-}$ when $e_{1}\geq 1/3$ is analogous. Fix
a vertex $v\in V(G)$ and define

$p=p(v)\coloneqq|[0,1]^{d}\cap B(v,r)|\quad\text{ and }\quad
p^{+}=p^{+}(v)\coloneqq|[0,1]^{d}\cap B(v,r)\cap h_{v}|.$

Condition on the event that $e_{1}=e_{1}(v)\leq 2/3$. Then, by our choice of
$v$ and $h_{v}$ and the fact that $r\leq 1/3$, we have that

$p^{+}\geq p/2\geq\theta_{d}r^{d}/2^{d+1}.$ (3.12)

Note, moreover, that, conditionally on the position of $v$, the random
variables $|V(G)\cap B(v,r)|$ and $|V(G)\cap B(v,r)\cap h_{v}|$ have
distribution $\mathrm{Bin}(n-1,p)$ and $\mathrm{Bin}(n-1,p^{+})$,
respectively. Thus, by Chernoff’s inequality,

$\mathbb{P}\left[|V(G)\cap
B(v,r)|\geq\left(1+\frac{\epsilon}{10}\right)p(n-1)\right]\leq
2\exp\left(-\frac{\epsilon^{2}p(n-1)}{300}\right)\leq\exp\left(-\frac{\epsilon^{2}pn}{400}\right)$
(3.13)

and, similarly,

$\mathbb{P}\left[|V(G)\cap B(v,r)\cap
h_{v}|\leq\left(1-\frac{\epsilon}{10}\right)p^{+}(n-1)\right]\leq\exp\left(-\frac{\epsilon^{2}p^{+}n}{400}\right).$
(3.14)

Note that, by (3.12) and (2.1), we have that

$\epsilon^{2}p^{+}n\geq\epsilon^{2}\frac{\theta_{d}r^{d}}{2^{d+1}}n\geq\epsilon^{2}\frac{\theta_{d}}{2^{d+1}}(C_{1}^{\prime})^{d}\log
n\geq 800\log n.$

Thus, using that $p\geq p^{+}$ and that
$(1-\epsilon/10)p^{+}\geq(1+\epsilon/10)(1/2-\epsilon/2)p$, and substituting
the above into (3.13) and (3.14), we conclude that

$\displaystyle\mathbb{P}\left[|V(G)\cap B(v,r)\cap
h_{v}|\leq\left(\frac{1}{2}-\frac{\epsilon}{2}\right)|V(G)\cap B(v,r)|\right]$
$\displaystyle\leq\;$ $\displaystyle\mathbb{P}\left[|V(G)\cap
B(v,r)|\geq\left(1+\frac{\epsilon}{10}\right)p(n-1)\right]+\mathbb{P}\left[|V(G)\cap
B(v,r)\cap h_{v}|\leq\left(1-\frac{\epsilon}{10}\right)p^{+}(n-1)\right]$
$\displaystyle\leq\;$ $\displaystyle
2\exp\left(-\frac{\epsilon^{2}p^{+}n}{400}\right)=o(1/n),$

and the lemma follows from a union bound over all $n$ vertices of $G$. ∎

We now proceed to the main proof in this section.

###### Proof of Theorem 3.1.

Set $C_{1}=C_{1}^{\prime}$ (which is defined in Lemma 3.4), let $G\sim
G_{d}(n,r)$, and condition on the event that $G$ satisfies the properties
described in Lemma 3.3 and, if $r=o(1)$, Lemma 3.4 (which hold a.a.s.). Let
$H\subseteq G$ be a $(1/2+\epsilon)$-subgraph of $G$.

The theorem follows by an application of Lemma 3.2 for $H$ and
$k\coloneqq\lfloor\epsilon s^{d}n/4\rfloor=\Omega(r^{d}n)$, using a suitably
chosen set $V^{\prime}$. Fix a set $U\subseteq V(G)$ of size $k-1$, and
suppose that a good cell $q\in\mathcal{Q}$, a cell $q^{\prime}\in\mathcal{Q}$
neighbouring $q$, and two vertices $v\in V(G)\cap q\setminus U$ and
$v^{\prime}\in V(G)\cap(q\cup q^{\prime})\setminus U$ are given. By
$(\mathrm{a})$ and $(\mathrm{b})$, it follows that $v$ and $v^{\prime}$ have
at least $\epsilon|N_{G}(v)\cap N_{G}(v^{\prime})|\geq\epsilon(|V(G)\cap
q|-2)\geq\epsilon(s^{d}n/2-2)\geq k$ common $H$-neighbours, so they are in the
same connected component of $H-U$. Using that every good cell contains at
least $s^{d}n/2\geq 2k$ vertices of $G$, we conclude that, for any set
$W\subseteq\mathcal{Q}$ of good cells such that $\Gamma[W]$ is connected, if
we let $V^{\prime}$ be the set of all vertices which lie in some cell of $W$,
then $V^{\prime}$ satisfies Lemma 3.2 $(\mathrm{A}1)$. In particular, if
$r=\omega((\log n/n)^{1/d})$, then we may simply set $V^{\prime}=V(G)$ and
conclude the proof since, by Lemma 3.3 $(\mathrm{B}2)$, there are no bad
cells.

Now, suppose that $r=o(1)$ and consider the $d$-dimensional rectangle
$\Pi\coloneqq[1/3,2/3]\times[0,1]^{d-1}$. By Lemma 3.3 $(\mathrm{B}1)$, no bad
cell intersecting $[1/3,1/3+2r]\times[0,1]^{d-1}$ is connected in
$\Gamma_{\mathrm{bad}}$ to any bad cell intersecting
$[2/3-2r,2/3]\times[0,1]^{d-1}$. Using this property, we will show that there
is a set $W$ of good cells contained in $\Pi$ such that
$[0,1]^{d}\setminus(\bigcup_{q\in W}q)$ consists of two (topologically)
connected regions at distance more than $r$ from each other, and
$\\{1/3\\}\times[0,1]^{d-1}$ and $\\{2/3\\}\times[0,1]^{d-1}$ are contained in
different regions (which allows us to refer to them as the left and right
parts, respectively). In particular, $\Gamma[W]$ is a connected graph and, as
discussed above, assumption $(\mathrm{A}1)$ is satisfied for the set
$V^{\prime}$ of all vertices in $W$. The set $W$ can be constructed as follows
(see Figure 1 for a schematic representation of part of the construction).

######  Construction of $\bm{W}$.

Consider the union $U$ of the region $[2/3-2r,1]\times[0,1]^{d-1}$ and the
balls with radius $4r$ centred at the centres of the bad cells connected to
$[2/3-2r,1]\times[0,1]^{d-1}$ in $\Gamma_{\mathrm{bad}}$. The region
$[0,1]^{d}\setminus U$ may have several simply-connected components, but,
since no component of $\Gamma_{\mathrm{bad}}$ has more than $M=\Theta(1)$
vertices (by Lemma 3.3 $(\mathrm{B}1)$) and $r=o(1)$, one of these components
must contain the $d$-dimensional rectangle $[0,1/3]\times[0,1]^{d-1}$. Let the
region containing this rectangle be denoted by $U^{\prime}$. Then, let $W$ be
the set consisting of all cells contained in $[0,1]^{d}\setminus U^{\prime}$
and at distance at most $2r-\sqrt{d}s$ from $U^{\prime}$. Note that all such
cells must be good by the definition of $\Gamma_{\mathrm{bad}}$. Then, the
union of the good cells in $W$ disconnects $[0,1/3]\times[0,1]^{d-1}$ and
$[2/3,1]\times[0,1]^{d-1}$, and the two regions in
$[0,1]^{d}\setminus\bigcup_{q\in W}q$ containing these $d$-dimensional
rectangles remain at distance at least $2r-\sqrt{d}s-\sqrt{d}s>r$ from each
other.

$\tfrac{2}{3}$$\tfrac{2}{3}-2r$ Figure 1. The construction of $W$ in the case
$d=2$. A part of the grid depicting bad cells (in orange) in two connected
components of $\Gamma_{\mathrm{bad}}$ of size $4$ which intersect
$[2/3-2r,1]\times[0,1]$, and the set $W$ (in black). The red circles have
radius $4r$ and the blue ones have radius $2r$. The set $U$ thus consists of
the union of the rectangle $[2/3-2r,1]\times[0,1]$ and the red circles. (This
union may have holes, as in this example). The pink contour leaves the area at
distance at most $2r-\sqrt{d}s$ from $[0,1]^{2}\setminus U^{\prime}$ on its
left.

We will next prove that the vertices in $V(G)\setminus V^{\prime}$ satisfy
Lemma 3.2 $(\mathrm{A}2)$. To this end, let $v_{1},\ldots,v_{m}$ (resp.
$u_{1},\ldots,u_{\ell}$) be an ordering of the vertices in the left part
(resp. right part) by decreasing (resp. increasing) order of their first
coordinate. By Lemma 3.4, and since the left and right parts are at distance
more than $r$ from each other, for every $i\in[m]$ we know that

$|N_{H}(v_{i})\cap(V^{\prime}\cup\\{v_{1},\ldots,v_{i-1}\\})|\geq\epsilon|N_{G}(v_{i})|/2,$

and an analogous statement holds for $u_{1},\ldots,u_{\ell}$. It remains to
show that for every $v\in V(G)\setminus V^{\prime}$ we have $|N_{G}(v)|\geq
2k/\epsilon$: indeed, the ordering $v_{1},\ldots,v_{m},u_{1},\ldots,u_{\ell}$
would then satisfy assumption $(\mathrm{A}2)$ and the proof would be
completed.

We show that every vertex has at least $2k/\epsilon$ neighbours in $G$.
Indeed, for a fixed vertex $v\in V(G)$, its expected degree satisfies

$\mathbb{E}[d_{G}(v)]\geq\frac{\theta_{d}r^{d}n}{2^{d}}\geq\frac{2^{d}d^{d/2}\theta_{d}s^{d}n}{\delta^{d}}\geq\frac{2^{d+2}d^{d/2}\theta_{d}k}{\epsilon\delta^{d}}\geq\frac{4k}{\epsilon},$

where the second inequality uses the definition of $s$, the third one uses the
definition of $k$, and the fourth one uses (2.1) and the fact that $\delta\leq
1$. Note also that

$\mathbb{E}[d_{G}(v)]\geq\frac{\theta_{d}r^{d}n}{2^{d}}\geq\frac{1}{2^{d}d^{d/2}}C_{1}^{d}\log
n\geq 25\log n,$

where the second inequality uses (2.1) and the lower bound on $r$, and the
third uses the definition of $C_{1}$. Now, an application of Chernoff’s
inequality and a union bound conclude the proof. ∎

We close this section by showing that the constant $1/2$ in Theorem 3.1 is
best possible in a strong sense, by proving Proposition 1.5. The proof is
quite simple and shows that, for a suitably large $C_{2}$, one may divide the
hypercube $[0,1]^{d}$ into strips of volume between $2r$ and $4r$ via
hyperplanes orthogonal to the $x$-axis and delete the edges crossing these
hyperplanes to obtain the required $(1/2-\epsilon)$-subgraph of $G_{d}(n,r)$.

###### Proof of Proposition 1.5.

The statement holds trivially if $r\geq 1/5$, so we may assume that $r<1/5$.
We divide $[0,1]^{d}$ into strips $S_{1},\ldots,S_{k}$ which are orthogonal to
the $x$-axis and have width $1/k\in[2r,4r]$ (which is possible since there is
at least one integer in the interval $[1/4r,1/2r]$). Set
$S_{0},S_{k+1}\coloneqq\varnothing$. Then, for every $i\in[k]$ and every $y\in
S_{i}$, we have that

  * •

$B(y,r)\cap[0,1]^{d}\subseteq S_{i-1}\cup S_{i}$ or
$B(y,r)\cap[0,1]^{d}\subseteq S_{i}\cup S_{i+1}$, and

  * •

$|S_{i-1}\cap B(y,r)|,|S_{i+1}\cap B(y,r)|\leq|S_{i}\cap B(y,r)|$.

Let $G\sim G_{d}(n,r)$ and $V\coloneqq V(G)$. An application of Chernoff’s
bound (Lemma 2.1) for the binomial variables $|V\cap S_{i}|$, together with a
union bound, shows that a.a.s. for every $i\in[k]$, we have

$|V\cap S_{i}|\leq 5rn.$ (3.15)

Moreover, for sufficiently large $C_{2}$, an application of Chernoff’s bound
shows that, for every $i\in[k]$ and every vertex $v\in V\cap S_{i}$,

$\mathbb{P}[|V\cap B(v,r)|\geq(1+\epsilon)|B(v,r)\cap[0,1]^{d}|n]=o(1/n)$

and

$\mathbb{P}[|V\cap S_{i}\cap
B(v,r)|\leq(1-\epsilon)|B(v,r)\cap[0,1]^{d}|n/2]=o(1/n).$

Hence, by a union bound over all $v\in V$, for every $i\in[k]$ and every
vertex $v\in V\cap S_{i}$, a.a.s.

$|V\cap S_{i}\cap
B(v,r)|\geq(1-\epsilon)\frac{|B(v,r)\cap[0,1]^{d}|n}{2}\geq\frac{1-\epsilon}{2+2\epsilon}|V\cap
B(v,r)|.$ (3.16)

Condition on the event that $G$ satisfies the properties above. Now, consider
a subgraph $H$ of $G$ obtained by deleting all edges of $G$ which are not
contained in one of the strips $S_{i}$. Clearly, each component of $H$ is
contained in a strip, and so has order at most $5rn$ by (3.15). Moreover, by
(3.16), $H$ is a $(1/2-\epsilon)$-subgraph of $G$. ∎

###  3.2. Connectivity in random geometric graphs is not born resilient

We devote this section to proving Theorem 1.6. First, we focus on the case
$d=1$. The proof relies upon the fact that a.a.s. there is an interval
$I\subseteq[0,1]$ of length $\log n-o(\log n)$ containing no vertex of
$G_{1}(n,r)$. It can then be shown that deleting all edges crossing $I$ a.a.s.
leaves a disconnected $(1/2+\epsilon)$-subgraph of $G_{1}(n,r)$.

###### Proof of Theorem 1.6 $(\mathrm{i})$.

If $r\leq(\log n-(\log n)^{1/3})/n$, then a.a.s. $G\sim G_{1}(n,r)$ is not
connected [28, Theorem 12], so we may assume that $\epsilon\in(0,1/4]$ and
$(\log n-(\log n)^{1/3})/n\leq r\leq\log n/4\epsilon n$.

Fix $\ell=\ell(n)\coloneqq(\log n-(\log n)^{1/2})/n<r$ and consider a family
$\mathcal{I}$ of $\lfloor n/(3\log n+6rn)\rfloor$ pairwise disjoint intervals
of length $\ell+2r$ in the segment $[1/3,2/3]$. Note that, if
$[a-r,b+r]\in\mathcal{I}$, then $a-r<a-r+\ell<a<b<b+r-\ell<b+r$. For every
interval $I=[a-r,b+r]\in\mathcal{I}$, define the event $\mathcal{E}_{I}$ that
$V(G)\cap[a,b]=\varnothing$, and the event $\mathcal{F}_{I}$ that the
intervals $[a-r+\ell,a]$ and $[b,b+r-\ell]$ contain $(r-\ell)n\pm(rn)^{2/3}$
vertices and the intervals $[a-r,a]$ and $[b,b+r]$ contain $rn\pm(rn)^{2/3}$
vertices. By Chernoff’s inequality (for the event $\mathcal{F}_{I}$
conditionally on $\mathcal{E}_{I}$), one can verify that, for every
$I\in\mathcal{I}$,

$\mathbb{P}[\mathcal{E}_{I}\cap\mathcal{F}_{I}]=\mathbb{P}[\mathcal{E}_{I}]\mathbb{P}[\mathcal{F}_{I}\mid\mathcal{E}_{I}]=(1\pm
o(1))(1-\ell)^{n}=(1\pm o(1))\mathrm{e}^{-\ell n}.$

Similarly, for every pair of distinct intervals $I,J\in\mathcal{I}$,

$\displaystyle\mathbb{P}[\mathcal{E}_{I}\cap\mathcal{F}_{I}\cap\mathcal{E}_{J}\cap\mathcal{F}_{J}]=\mathbb{P}[\mathcal{E}_{I}\cap\mathcal{E}_{J}]\mathbb{P}[\mathcal{F}_{I}\cap\mathcal{F}_{J}\mid\mathcal{E}_{I}\cap\mathcal{E}_{J}]=(1\pm
o(1))(1-2\ell)^{n}=(1\pm o(1))\mathrm{e}^{-2\ell n}.$

Thus, a second moment argument shows that a.a.s. the event
$\mathcal{E}_{I}\cap\mathcal{F}_{I}$ holds for at least one interval
$I\in\mathcal{I}$. We condition on this event, and let
$I=[a-r,b+r]\in\mathcal{I}$ be one interval for which
$\mathcal{E}_{I}\cap\mathcal{F}_{I}$ holds.

Let $H\subseteq G$ be obtained by deleting all edges $uv$ with $u\in[0,a)$ and
$v\in(b,1]$. The probability that $V(G)\cap[0,1/3)=\varnothing$ or
$V(G)\cap(2/3,1]=\varnothing$ is exponentially small (both in the original
probability space and in our conditional setting), so a.a.s. $H$ is a
disconnected graph. Moreover, $H$ is a $(1/2+\epsilon)$-subgraph of $G$ since,
for every vertex $v\in V(G)\cap([0,a)\cup(b,1])$, we have that

$\frac{d_{H}(v)}{d_{G}(v)}\geq\frac{rn-(rn)^{2/3}-1}{(2r-\ell)n+2(rn)^{2/3}}\geq(1-o(1))\frac{1}{2-4\epsilon}>\frac{1}{2}+\epsilon,$

which finishes the proof. ∎

Now, we fix $d=2$ and direct our attention to the proof of Theorem 1.6
$(\mathrm{ii})$. The main idea of the proof is similar to the $1$-dimensional
case and goes roughly as follows. We look for an annulus in $[0,1]^{2}$ with
radii of order $\log n/n$ which contains no vertices of $G_{2}(n,r)$. Then,
one can delete all edges of $G_{2}(n,r)$ which cross this annulus to obtain a
disconnected graph. This idea unfortunately fails for two dimensions since the
width of the empty annulus is not sufficient to compensate the fact that, due
to the curvature, some vertices in the ball inside the annulus are still
expected to have more neighbours beyond the empty annulus than inside the
ball, so the resulting graph after those edge deletions will not be a
$(1/2+\epsilon)$-subgraph of $G_{2}(n,r)$. To correct this, we look for two
concentric annuli in $[0,1]^{2}$ with radii of order $\log n/n$ such that (i)
the external boundary of the internal annulus coincides with the internal
boundary of the external annulus; (ii) the external annulus contains no
vertices of $G_{2}(n,r)$, and (iii) the density of vertices in the internal
annulus is atypically high. While this last assumption requires to reduce the
width of the external annulus, careful comparison of large deviations shows
that, by choosing the parameters of the problem in a suitable way, the density
boost in the internal annulus manages to compensate the effect of the
curvature.

We turn to the technical details. First, we prepare the terrain with a couple
of auxiliary lemmas. Set $\zeta=\zeta(n)\coloneqq(\log n/n)^{1/2}$. For any
given constant $A>0$, we define $t_{A}$ as the unique positive solution of the
equation

$\uppi((1+t)A)^{2}-\uppi A^{2}=\uppi A^{2}(t^{2}+2t)=1.$

We define a function $c\colon[0,+\infty)^{4}\to\mathbb{R}$ by setting

$c=c(A,C,t,\nu)\coloneqq 1-\uppi A^{2}(t^{2}+2t)-4\uppi
C(A-C)\left(1-(1+\nu)\log\left(\frac{\mathrm{e}}{1+\nu}\right)\right).$

######  Fact 3.5.

For all fixed $C>0$, $A>C$ and $t\in[0,t_{A}]$, there is a unique non-negative
solution $\nu_{t}$ to the equation

$c(A,C,t,\nu)=0.$ (3.17)

Moreover, if $t\in[0,t_{A})$ and $\nu\in[0,\nu_{t})$, then $c(A,C,t,\nu)>0$.

###### Proof.

The function $f\colon[0,\infty)\to\mathbb{R}$ defined by
$f(\nu)=(1+\nu)\log(\mathrm{e}/(1+\nu))$ is decreasing (so $c$ is also
decreasing as a function of $\nu$), $f(0)=1$ and $f(\nu)$ tends to $-\infty$
when $\nu\to\infty$. Since $c(A,C,t,0)\geq 0$ by the definition of $t_{A}$,
the claim follows. ∎

Let $C>0$ and $A\geq 2C$ be fixed constants. For every $t\geq 0$, define
$Z_{t}\coloneqq((1+t)A+2C)\zeta$. For any point $x\in[0,1]^{2}$ and any
$t,\nu\geq 0$, we define the events

$\displaystyle\mathcal{E}_{x,t}=\mathcal{E}_{x,t}(A)$
$\displaystyle\coloneqq\\{V(G_{2}(n,r))\cap
B(x,A\zeta,(1+t)A\zeta)=\varnothing\\},$
$\displaystyle\mathcal{F}_{x,\nu}=\mathcal{F}_{x,\nu}(A,C)$
$\displaystyle\coloneqq\\{|V(G_{2}(n,r))\cap
B(x,(A-2C)\zeta,A\zeta)|\in[(1+\nu)4\uppi C(A-C)\log n,(\log n)^{2}]\\},$
$\displaystyle\mathcal{G}_{x,t}=\mathcal{G}_{x,t}(A,C)$
$\displaystyle\coloneqq\\{|V(G_{2}(n,r))\cap
B(x,(1+t)A\zeta,Z_{t})|=4\uppi(C+(1+t)A)C\log n\pm(\log n)^{2/3}\\}.$

######  Lemma 3.6.

Fix $C>0$ and $A\geq 2C$. For every $t\in[0,t_{A})$ and every
$\nu\in(0,\nu_{t})$, a.a.s.
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$ holds for some
point $x\in[Z_{t_{A}},1-Z_{t_{A}}]^{2}$.

###### Proof.

Fix $t\in[0,t_{A})$, $\nu\in(0,\nu_{t})$ and a point
$x\in[Z_{t_{A}},1-Z_{t_{A}}]^{2}$. Then,

$\mathbb{P}[\mathcal{E}_{x,t}]=(1-\uppi
A^{2}(t^{2}+2t)\zeta^{2})^{n}=\exp(-(1+o(1))\uppi A^{2}(t^{2}+2t)\log
n)=n^{-\uppi A^{2}(t^{2}+2t)\pm o(1)}.$ (3.18)

Note that, by our assumption that $t\in[0,t_{A})$, we have that $\uppi
A^{2}(t^{2}+2t)\in[0,1)$. At the same time, setting
$i_{0}\coloneqq\lceil(1+\nu)4\uppi C(A-C)\log n\rceil$ and $p\coloneqq 4\uppi
C(A-C)\zeta^{2}/(1-\uppi A^{2}(t^{2}+2t)\zeta^{2})$, we have that

$\mathbb{P}[\mathcal{F}_{x,\nu}\mid\mathcal{E}_{x,t}]=\sum_{i=i_{0}}^{(\log
n)^{2}}\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{i}\kern-1.00006pt\right)p^{i}(1-p)^{n-i}.$
(3.19)

Moreover, as for every $i\geq i_{0}$ we have that

$\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{i+1}\kern-1.00006pt\right)p^{i+1}(1-p)^{n-i-1}\bigg{/}\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{i}\kern-1.00006pt\right)p^{i}(1-p)^{n-i}=\frac{(n-i)p}{(i+1)(1-p)}\leq\frac{1}{1+\nu},$

the sum in (3.19) is of the order of its first term, that is,

$\mathbb{P}[\mathcal{F}_{x,\nu}\mid\mathcal{E}_{x,t}]=\Theta\left(\left(\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{i_{0}}\kern-1.00006pt\right)p^{i_{0}}(1-p)^{n-i_{0}}\right)=\Theta\left(i_{0}^{-1/2}\frac{n^{n}}{(n-i_{0})^{n-i_{0}}}\left(\frac{p}{i_{0}}\right)^{i_{0}}\mathrm{e}^{-np}\right),$

where the second equality follows by Stirling’s approximation. In particular,
since we have that $np/i_{0}=(1+o(1))/(1+\nu)$ by definition, then

$\displaystyle\log\mathbb{P}[\mathcal{F}_{x,\nu}\mid\mathcal{E}_{x,t}]$
$\displaystyle=i_{0}\log\left(\frac{\mathrm{e}}{1+\nu}\right)-np+o(\log n)$
$\displaystyle=\left((1+\nu)4\uppi
C(A-C)\log\left(\frac{\mathrm{e}}{1+\nu}\right)-4\uppi C(A-C)\pm
o(1)\right)\log n.$ (3.20)

Finally, an immediate application of Chernoff’s bound (Lemma 2.1) shows that
$\mathbb{P}[\mathcal{G}_{x,t}\mid\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}]=1-o(1)$.
Combining this with (3.18) and (3.2), we have that

$\mathbb{P}[\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}]=\mathbb{P}[\mathcal{E}_{x,t}]\mathbb{P}[\mathcal{F}_{x,\nu}\mid\mathcal{E}_{x,t}]P[\mathcal{G}_{x,t}\mid\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}]=n^{c-1\pm
o(1)}$ (3.21)

with $c=c(A,C,t,\nu)>0$ (see 3.5).

Now, fix $t\in[0,t_{A})$ and $\nu\in(0,\nu_{t})$ and consider a set $S$ of
$k\coloneq\lceil n/(\log n)^{3}\rceil$ points $\\{x_{1},\ldots,x_{k}\\}$ in
$[0,1]^{2}$ at distance at least $2Z_{t_{A}}$ from the boundary and from each
other. We will show that
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$ holds a.a.s.
for at least one of the points $x\in S$. Let $X$ be the sum of the indicator
random variables of the events
$\mathcal{E}_{x_{i},t}\cap\mathcal{F}_{x_{i},t}\cap\mathcal{G}_{x_{i},t}$.
From (3.21), we have that $\mathbb{E}[X]=kn^{c-1\pm o(1)}=\omega(1)$. On the
other hand, since the set $\\{B(x_{i},Z_{t})\\}_{i\in[k]}$ consists of
pairwise disjoint balls, computations similar to the ones above show that, for
every pair of distinct integers $i,j\in[k]$,

$\displaystyle\mathbb{P}[\mathcal{E}_{x_{i},t}\cap\mathcal{E}_{x_{j},t}]$
$\displaystyle=(1\pm o(1))\mathbb{P}[\mathcal{E}_{x,t}]^{2},$
$\displaystyle\mathbb{P}[\mathcal{F}_{x_{i},\nu}\mid\mathcal{E}_{x_{i},t}\cap\mathcal{E}_{x_{j},t}]$
$\displaystyle=(1\pm o(1))\mathbb{P}[\mathcal{F}_{x,\nu}],$
$\displaystyle\mathbb{P}[\mathcal{F}_{x_{j},\nu}\mid\mathcal{E}_{x_{i},t}\cap\mathcal{E}_{x_{j},t}\cap\mathcal{F}_{x_{i},\nu}]$
$\displaystyle=(1\pm o(1))\mathbb{P}[\mathcal{F}_{x,\nu}],$
$\displaystyle\mathbb{P}[\mathcal{G}_{x_{i},t}\mid\mathcal{E}_{x_{i},t}\cap\mathcal{E}_{x_{j},t}\cap\mathcal{F}_{x_{i},\nu}\cap\mathcal{F}_{x_{j},\nu}]$
$\displaystyle=1-o(1),$
$\displaystyle\mathbb{P}[\mathcal{G}_{x_{j},t}\mid\mathcal{E}_{x_{i},t}\cap\mathcal{E}_{x_{j},t}\cap\mathcal{F}_{x_{i},\nu}\cap\mathcal{F}_{x_{j},\nu}\cap\mathcal{G}_{x_{i},t}]$
$\displaystyle=1-o(1).$

In particular, $\operatorname{Var}[X]$ is bounded from above by

$\mathbb{E}[X]+\sum_{\begin{subarray}{c}(i,j)\in[k]^{2}\\\ i\neq
j\end{subarray}}\left(\mathbb{P}[\mathcal{E}_{x_{i},t}\cap\mathcal{E}_{x_{j},t}\cap\mathcal{F}_{x_{i},\nu}\cap\mathcal{F}_{x_{j},\nu}\cap\mathcal{G}_{x_{i},t}\cap\mathcal{G}_{x_{i},t}]-\mathbb{P}[\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}]^{2}\right)=o(\mathbb{E}[X]^{2}),$

so by Chebyshev’s inequality we conclude that a.a.s.
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$ holds for at
least one of the points $x\in S$. ∎

When $t=0$, (3.17) implies that

$1-(1+\nu_{0})\log\left(\frac{\mathrm{e}}{1+\nu_{0}}\right)=\frac{1}{4\uppi
C(A-C)}.$

Note that, for any fixed $C>0$, $\nu_{0}$ decreases to $0$ as $A$ grows to
infinity. Thus, by using Taylor expansion in the regime when $\nu_{0}\to 0$,
we have that

$1-(1+\nu_{0})\log\left(\frac{\mathrm{e}}{1+\nu_{0}}\right)=(1+\nu_{0})\log(1+\nu_{0})-\nu_{0}=\frac{\nu_{0}^{2}}{2}-O_{\nu_{0}}(\nu_{0}^{3}).$

In particular, for all $C>0$ and sufficiently large $A>0$, one may observe
that

$\nu_{0}=\frac{1+o_{A}(1)}{\sqrt{2\uppi C(A-C)}}.$ (3.22)

Fix any $x\in\mathbb{R}^{2}$. For every point $y\in\mathbb{R}^{2}$, every
$t\geq 0$ and $\rho=\rho(n)\geq 0$, define the regions

$\displaystyle R_{1}(y,\rho)$ $\displaystyle\coloneqq B(y,\rho)\cap
B(x,A\zeta),$ $\displaystyle R_{2}(y,t,\rho)$ $\displaystyle\coloneqq
B(y,\rho)\setminus B(x,(1+t)A\zeta).$

We continue with a geometric lemma.

######  Lemma 3.7.

Let $C>0$ and $x\in\mathbb{R}^{2}$ be fixed. For all sufficiently large $A$,
there exist $t\in(0,t_{A})$, $\nu\in(0,\nu_{t})$ and
$\epsilon=\epsilon(C,A,t,\nu)>0$ such that the following hold.

  1. $(\mathrm{i})$

For all $y\in\partial B(x,A\zeta)$ we have that
$(1+\nu)|R_{1}(y,C\zeta)|\geq(1+10\epsilon)|R_{2}(y,t,C\zeta)|$.

  2. $(\mathrm{ii})$

For all $z\in\partial B(x,(1+t)A\zeta)$ we have that
$|R_{2}(z,t,C\zeta)|\geq(1+10\epsilon)(1+\nu)|R_{1}(z,C\zeta)|$.

We remark that this lemma is “scale-free”, in the sense that $\zeta$ could be
replaced (in the statement as well as the definitions of $R_{1}$ and $R_{2}$)
by any positive real number without changing the conclusion. Our choice of
phrasing is adapted to our later application.

###### Proof of Lemma 3.7.

$x$$y$$y_{1}$$y_{2}$$z$$\theta$$\partial B(x,A\zeta)$$\partial
B(x,(1+t)A\zeta)$ Figure 2. The configuration from the proof of Lemma 3.7.

For $y\in\mathbb{R}^{2}$, define for brevity $R_{1}(y)\coloneqq
R_{1}(y,C\zeta)$ and $R_{2}(y,t)\coloneqq R_{2}(y,t,C\zeta)$. Fix a point
$y\in\partial B(x,A\zeta)$ and let $z$ be the intersection point of the ray
$xy$ and $\partial B(x,(1+t)A\zeta)$. Note that $z$ is a function of $t$, but
we omit the dependence from the notation for simplicity. We will show that,
when $t=0$, we have $(1+\nu_{0})|R_{1}(y)|>|R_{2}(y,0)|$ (and hence
$(1+\nu_{0})|R_{1}(z)|>|R_{2}(z,0)|$ ), but when $t=t_{A}$, we have
$|R_{2}(z,t_{A})|>(1+\nu_{t_{A}})|R_{1}(z)|$. Then, by continuity of

$(t,\nu)\mapsto(|R_{2}(y,t)|-(1+\nu)|R_{1}(y)|,|R_{2}(z,t)|-(1+\nu)|R_{1}(z)|)$

and the fact that the second component is strictly larger than the first one
for any choice of parameters $t\in(0,t_{A})$ and $\nu\in(0,\nu_{t})$, we can
find $t$ and $\nu$ for which

$(1+\nu)|R_{1}(y)|>|R_{2}(y,t)|\qquad\text{ and
}\qquad|R_{2}(z,t)|>(1+\nu)|R_{1}(z)|,$

which implies the lemma.

Denote by $y_{1},y_{2}$ the intersection points of the circle $\partial
B(y,C\zeta)$ with $\partial B(x,A\zeta)$, and let $\theta$ be the measure of
the angle $yxy_{1}$, see Figure 2. Then, $R_{1}(y)$ is obtained from the
sector between $yy_{1}$ and $yy_{2}$ in $B(y,C\zeta)$ by adding the caps that
$yy_{1}$ and $yy_{2}$ separate from $B(x,A\zeta)$. Since the angle
$y_{1}yy_{2}$ has measure $\uppi-\theta$,

$|R_{1}(y)|=\frac{\uppi-\theta}{2}C^{2}\zeta^{2}+2\left(\frac{\theta}{2}-\frac{\sin\theta}{2}\right)A^{2}\zeta^{2}=\frac{\uppi-\theta}{2}C^{2}\zeta^{2}+(\theta-\sin\theta)A^{2}\zeta^{2}.$

Using that $x-\sin x=x^{3}/6+O_{x}(x^{5})$ when $x\to 0$, the fact that
$\sin(\theta/2)=C/2A$ (which means that $\theta=C/A+O_{A}(C^{3}/A^{3})$) and
the relation $A=\omega_{A}(C)$, we have that the above expression rewrites as

$|R_{1}(y)|=\frac{\uppi}{2}C^{2}\zeta^{2}-\left(\frac{\theta}{2}C^{2}-\frac{\theta^{3}}{6}A^{2}+O_{A}(\theta^{5}A^{2})\right)\zeta^{2}=\frac{\uppi}{2}C^{2}\zeta^{2}-\left(\frac{C^{3}}{3A}+o_{A}\left(\frac{C^{3}}{A}\right)\right)\zeta^{2}.$
(3.23)

In particular, for all sufficiently large $A$ and using (3.22), we have that

$|R_{2}(y,0)|-|R_{1}(y)|=2\left(\frac{C^{3}}{3A}+o_{A}\left(\frac{C^{3}}{A}\right)\right)\zeta^{2}<\frac{\uppi
C^{2}\zeta^{2}/3}{\sqrt{2\uppi C(A-C)}}<\nu_{0}|R_{1}(y)|,$

which implies that $(1+\nu_{0})|R_{1}(y)|>|R_{2}(y,0)|$.

It remains to show that
$|R_{2}(z,t_{A})|>(1+\nu_{t_{A}})|R_{1}(z)|=|R_{1}(z)|$. To this end, note
that the angles $xy_{1}y$ and $yy_{2}x$ are acute and, thus, the part of the
annulus between the rays $xy_{2}$ and $xy_{1}$ contains
$B(x,A\zeta,(1+t_{A})A\zeta)\cap B(y,C\zeta)$. Thus, by (3.23) and using the
definition of $t_{A}$,

$\displaystyle|R_{2}(y,t_{A})|\geq\uppi
C^{2}\zeta^{2}-|R_{1}(y)|-\frac{\theta}{\uppi}\zeta^{2}$
$\displaystyle=\frac{\uppi}{2}C^{2}\zeta^{2}+\bigg{(}\frac{C^{3}}{3A}+o_{A}\bigg{(}\frac{C^{3}}{A}\bigg{)}-\frac{C}{\uppi
A}\bigg{)}\zeta^{2}$
$\displaystyle=|R_{1}(y)|+\bigg{(}\frac{2C^{3}}{3A}+o_{A}\bigg{(}\frac{C^{3}}{A}\bigg{)}-\frac{C}{\uppi
A}\bigg{)}\zeta^{2}.$ (3.24)

At the same time, using that $C$ is a fixed constant, $A$ is large and
$t_{A}=1/2\uppi A^{2}+o_{A}(1/A^{2})$, up to lower order terms, the region
$(R_{1}(y)\setminus R_{1}(z))\cup(R_{2}(z,t_{A})\setminus R_{2}(y,t_{A}))$
consists of the symmetric difference of $B(y,C\zeta)$ and $B(z,C\zeta)$.
Setting $w$ to be an intersection point of the last two circles, $\varphi$ to
be the measure of the angle $wyz$ and
$\ell\coloneqq|yz|=At_{A}\zeta=(1+o_{A}(1))\zeta/2\uppi A$ (see Figure 3), a
simple inclusion-exclusion principle and the fact that
$\arccos(x)=\uppi/2-x-o_{x}(x)$ as $x\to 0$, we obtain that

$\displaystyle|B(y,C\zeta)\triangle B(z,C\zeta)|$
$\displaystyle=2\bigg{(}\dfrac{2\uppi-2\varphi}{2\uppi}\uppi(C\zeta)^{2}-\dfrac{2\varphi}{2\uppi}\uppi(C\zeta)^{2}+2\,\dfrac{\ell\cdot
C\zeta\sin\varphi}{2}\bigg{)}$
$\displaystyle=\left(2\uppi-4\arccos\left(\dfrac{\ell}{2C\zeta}\right)\right)(C\zeta)^{2}+2\ell\cdot
C\zeta\sqrt{1-\dfrac{\ell^{2}}{4(C\zeta)^{2}}}$
$\displaystyle=(1+o_{A}(1))\frac{4\ell}{2C\zeta}(C\zeta)^{2}=(1+o_{A}(1))\frac{C\zeta^{2}}{\uppi
A}.$ (3.25)

$z$$w$$y$$\ell$$C\zeta$$\varphi$ Figure 3. An illustration for the computation
in (3.25).

Combining (3.24) and (3.25), we have that

$\displaystyle|R_{2}(z,t_{A})|-|R_{1}(z)|$
$\displaystyle=(|R_{2}(z,t_{A})|-|R_{2}(y,t_{A})|)+(|R_{2}(y,t_{A})|-|R_{1}(y)|)+(|R_{1}(y)|-|R_{1}(z)|)$
$\displaystyle=|R_{2}(y,t_{A})|-|R_{1}(y)|+(1\pm
o_{A}(1))|B(y,C\zeta)\triangle B(z,C\zeta)|$
$\displaystyle=\bigg{(}\frac{2C^{3}}{3A}+o_{A}\bigg{(}\frac{C^{3}}{A}\bigg{)}\bigg{)}\zeta^{2}>0,$

which finishes the proof. ∎

We are now ready to prove Theorem 1.6.

###### Proof of Theorem 1.6 $(\mathrm{ii})$.

First of all, note that, for every $C<1/\uppi^{1/2}$ and $r\leq C\zeta$,
a.a.s. the random graph $G_{2}(n,r)$ is disconnected and the statement
trivially holds (see [47, Theorem 13.2]). Now, fix $C\geq 1/\uppi^{1/2}$ and
$r\in[\zeta/2\uppi^{1/2},C\zeta]$, let $A,t,\nu$ be as in Lemma 3.7, let
$\epsilon\coloneqq\min\\{\epsilon(C,A,t,\nu),1/20\\}$, and fix any
$x\in[Z_{t_{A}},1-Z_{t_{A}}]^{2}$. Let $G\sim G_{2}(n,r)$ and $V\coloneqq
V(G)$. Let $\mathcal{A}_{x}$ be the event that, for every $v\in V\cap
B(x,A\zeta)$, we have that

$|(V\setminus\\{v\\})\cap R_{1}(v,r)|\geq(1+5\epsilon)|V\cap R_{2}(v,t,r)|,$
(3.26)

and let $\mathcal{B}_{x}$ be the event that, for every $v\in V\setminus
B(x,(A+t)\zeta)$, we have that

$|(V\setminus\\{v\\})\cap R_{2}(v,t,r)|\geq(1+5\epsilon)|V\cap R_{1}(v,r)|.$
(3.27)

We are going to show that

$\mathcal{A}_{x}\cap\mathcal{B}_{x}$ holds a.a.s. conditionally on
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$. (3.28)

Consider the probability space conditioned on the event
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$. We write
$\mathbb{P}^{\prime}$ and $\mathbb{E}^{\prime}$ to refer to probabilities and
expectations in this conditional space, respectively. We begin verifying
(3.26) for vertices $v\in V\cap B(x,A\zeta)$. For vertices at distance more
than $C\zeta$ from $\partial B(x,A\zeta)$, (3.26) holds trivially. Moreover,
for every vertex $v\in V\cap B(x,A\zeta)$ at distance at most $C\zeta$ from
$\partial B(x,A\zeta)$, Lemma 3.7 implies that
$(1+\nu)|R_{1}(v,r)|\geq(1+10\epsilon)|R_{2}(v,t,r)|$. Furthermore, by
Chernoff’s bound,

$\mathbb{P}^{\prime}[|(V\setminus\\{v\\})\cap
R_{1}(v,r)|\leq(1-\epsilon)\mathbb{E}^{\prime}[|(V\setminus\\{v\\})\cap
R_{1}(v,r)|]]=n^{-\Omega(1)},$

and

$\mathbb{P}^{\prime}[|V\cap
R_{2}(v,t,r)|\geq(1+\epsilon)\mathbb{E}^{\prime}[|V\cap
R_{2}(v,t,r)|]]=n^{-\Omega(1)}.$

As a result, conditionally on
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$, with
probability $1-n^{-\Omega(1)}$, we have that

$\displaystyle|(V\setminus\\{v\\})\cap R_{1}(v,r)|$
$\displaystyle\geq(1-\epsilon)(1+\nu)|R_{1}(v,r)|(n-1)\geq(1-\epsilon)(1+9\epsilon)|R_{2}(v,t,r)|n$
$\displaystyle\geq(1\pm o(1))(1-\epsilon)(1+9\epsilon)\frac{|V\cap
R_{2}(v,t,r)|}{1+\epsilon}\geq(1+5\epsilon)|V\cap R_{2}(v,t,r)|,$

where the third inequality uses that $\mathbb{E}[|V\cap R_{2}(v,t,r)|]=(1\pm
o(1))|R_{2}(v,t,r)|n$ thanks to $\mathcal{G}_{x,t}$.

Next, we consider (3.27). In the same way as above, if $u\in V\setminus
B(x,((1+t)A+C)\zeta)$, then (3.27) holds trivially. For every vertex $u\in
V\cap B(x,(1+t)A\zeta,((1+t)A+C)\zeta)$, Lemma 3.7 implies that
$|R_{2}(u,t,r)|\geq(1+10\epsilon)(1+\nu)|R_{1}(u,r)|$. Moreover, by Chernoff’s
bound,

$\mathbb{P}^{\prime}[|V\cap
R_{1}(u,r)|\geq(1+\epsilon)\mathbb{E}^{\prime}[|V\cap
R_{1}(u,r)|]]=n^{-\Omega(1)},$

and

$\mathbb{P}^{\prime}[|(V\setminus\\{u\\})\cap
R_{2}(u,t,r)|\leq(1-\epsilon)\mathbb{E}^{\prime}[|(V\setminus\\{u\\})\cap
R_{2}(u,t,r)|]]=n^{-\Omega(1)}.$

Again, conditionally on
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$, with
probability $1-n^{-\Omega(1)}$, we have that

$\displaystyle|(V\setminus\\{v\\})\cap R_{2}(u,t,r)|$ $\displaystyle\geq(1\pm
o(1))(1-\epsilon)|R_{2}(u,t,r)|(n-1)$ $\displaystyle\geq(1\pm
o(1))(1-\epsilon)(1+9\epsilon)(1+\nu)|R_{1}(u,r)|n$ $\displaystyle\geq(1\pm
o(1))(1-\epsilon)(1+9\epsilon)\frac{|V\cap
R_{1}(u,r)|}{1+\epsilon}\geq(1+5\epsilon)|V\cap R_{1}(u,r)|.$

Then, using a union bound over the vertices in $V\cap B(x,(A-C)\zeta,A\zeta)$
for the event $\overline{\mathcal{A}}_{x}$ (which are at most $(\log n)^{2}$
by $\mathcal{F}_{x,\nu}$) and over the vertices in $V\cap
B(x,(1+t)A\zeta,((1+t)A+C)\zeta)$ for the event $\overline{\mathcal{B}}_{x}$
(which are at most $(\log n)^{2}$ by $\mathcal{G}_{x,t}$), we obtain that

$\displaystyle\mathbb{P}[\mathcal{A}_{x}\cap\mathcal{B}_{x}\mid\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}]$
$\displaystyle\geq
1-\mathbb{P}[\overline{\mathcal{A}}_{x}\mid\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}]-\mathbb{P}[\overline{\mathcal{B}}_{x}\mid\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}]$
$\displaystyle\geq 1-(\log n)^{2}n^{-\Omega(1)}=1-o(1),$

so (3.28) holds.

It remains to recall that, by Lemma 3.6, a.a.s. there exists a point
$x\in[Z_{t_{A}},1-Z_{t_{A}}]^{2}$ for which
$\mathcal{E}_{x,t}\cap\mathcal{F}_{x,\nu}\cap\mathcal{G}_{x,t}$ holds. Fixing
such a point $x$, let $H\subseteq G$ be obtained from $G$ by removing all
edges with one endpoint in $B(x,A\zeta)$ and the other outside
$B(x,(1+t)A\zeta)$. Clearly, $H$ is disconnected, and it follows from (3.28)
that a.a.s. $H$ is a $(1/2+\epsilon)$-subgraph of $G$, which finishes the
proof. ∎

##  4\. Long cycles

This section is dedicated to the proof of the following technical result,
which readily implies Theorem 1.8.

######  Theorem 4.1.

For every integer $d\geq 1$, every $\eta\in[1/2,1)$ and every
$\epsilon\in(0,1-\eta]$, there exist positive constants
$c_{3}=c_{3}(d,\epsilon)$ and $C_{3}=C_{3}(d,\epsilon)$ such that, if
$r\in[C_{3}(\log n/n)^{1/d},c_{3}]$, then a.a.s. $G_{d}(n,r)$ satisfies the
following property: for every integer $L\in[c_{3}^{-1},2\eta n/(1+\eta)]$ and
every vertex $v\in V$, every $(\eta+\epsilon)$-subgraph of $G_{d}(n,r)$
contains a cycle of length $L$ containing $v$.

Observe that, compared with Theorem 1.8, Theorem 4.1 can be used to obtain
longer cycles provided that the subgraphs of $G_{d}(n,r)$ have higher degrees,
and that these cycles become almost spanning as $\eta$ approaches $1$. In
fact, the same proof can be used to obtain cycles of lengths up to
$(2\eta/(1+\eta)+\epsilon^{\prime})n$ for a sufficiently small
$\epsilon^{\prime}$ depending on $\epsilon$. As this small improvement does
not yield a more interesting result, we omit the details for the clarity of
our exposition.

######  Remark 4.2.

Under the conditions of Theorem 4.1, for every vertex $v$, we can also prove
the existence of short even cycles going through $v$. In fact, in the proof of
Theorem 4.1, we also construct a cycle of length $L$ through each vertex for
all even $L\in[4,2\eta n/(1+\eta)]$. However, short odd cycles not only seem
more complicated to construct in general, but in some cases the adversary has
the power to destroy all such cycles containing a given vertex. As an example,
the adversary may delete all triangles containing a given vertex if $\eta=1/2$
and $\epsilon$ is sufficiently small.

Indeed, fix a vertex $v$ (at distance at least $2r$ from the boundary of
$[0,1]^{d}$) and define the region $R\coloneqq B(v,r)\setminus B(v,t)$, where
$t<r$ is chosen so that $|R|=(1/2+2\epsilon)|B(v,r)|$. Then, by choosing
$\epsilon$ sufficiently small, one can show that, for every point $x\in R$,
$|B(x,r)\cap R|\leq(1/2-2\epsilon)|B(x,r)|$. Thus, it is not hard to check
using Chernoff’s bound that, when $r\geq C(\log n/n)^{1/d}$ for a suitably
large constant $C>0$, a.a.s. deleting all edges between $v$ and $V\cap B(v,t)$
as well as all edges whose endpoints lie in $V\cap R$ leaves us with a
$(1/2+\epsilon)$-subgraph of $G_{d}(n,r)$ with no triangle containing $v$.

Let us begin with a sketch of the proof of Theorem 4.1. For this sketch, we
consider only Theorem 1.8 (that is, the case $\eta=1/2$), since no new ideas
are required to prove the more general version. The main part of the proof is
to show that we can construct cycles of even length $L\in[4,2n/3]$. To achieve
this, we first tessellate $[0,1]^{d}$ with cells of diameter $\delta r$, for
some small constant $\delta>0$, and consider a $(1/2+\epsilon)$-subgraph $H$
of $G_{d}(n,r)$ and a fixed vertex $v$. Then, we consider a colouring of
$V(H)$ in three colours so that $v$ is blue, roughly $2/3$ of the vertices are
red, roughly $1/3$ of them are blue, and a very small proportion are green.
The idea is to build a cycle of length $L$ in $H$ by starting from $v$ in such
a way that

  1. (i)

every second vertex is blue;

  2. (ii)

many blue vertices contained in a single cell appear in a short segment of the
cycle;

  3. (iii)

red vertices are inserted between blue vertices which lie in the same cell,
and

  4. (iv)

green vertices ensure the transitions between blue vertices in different
cells.

To ensure better control on the places where red and green vertices are
inserted, we associate each red (resp. green) vertex to a unique cell (resp.
pair of cells) within distance $r-\delta r$ from it, and only use it to
connect blue vertices in this cell (resp. pair of cells). We prove the
existence of a colouring and an assignment of cells to vertices satisfying the
properties that we need to construct our cycles by considering random ones and
showing that our desired properties hold with positive probability. The above
associations to cells (for the red vertices) or pairs of cells (for the green
vertices) allow us to avoid repetitions of red and green vertices along the
cycles we aim to construct. For each cell $q$, we ensure the existence of long
red-blue paths containing as many blue vertices in $q$ as we need by using a
theorem of Jackson [32] which provides long paths in bipartite graphs (see
Lemma 4.3). Gluing the ends of such a path (if $L$ is sufficiently small) or
gluing several paths (if $L$ is large) proves that we can construct the
desired cycle of even length $L$. Extending the result to sufficiently long
odd cycles is done by replacing a path of length two in an already constructed
cycle of even length by a suitably long path of odd length.

Before we proceed with the formal proof of Theorem 4.1, we state the theorem
of Jackson [32] which will be important for our proof.

######  Lemma 4.3 ([32, Theorem 1]).

Let $k\in\mathbb{N}$. If $G=(A,B,E)$ is a bipartite graph where $|A|\in[2,k]$,
$|B|\in[k,2k-2]$, and every vertex in $A$ has degree at least $k$, then $G$
contains a cycle of length $2|A|$.

We can use Chernoff’s inequality to obtain several properties about the
distribution of a random set of points over $[0,1]^{d}$. These properties will
be useful for the proof of Theorem 4.1.

######  Lemma 4.4.

Fix $0<1/C\lll\delta\lll\epsilon,1/d\leq 1$ and let $r\in[C(\log
n/n)^{1/d},\sqrt{d}]$. Let $V$ be a set of $n$ points sampled independently
and uniformly from $[0,1]^{d}$. Then, a.a.s. the following properties hold:

  1. $(\mathrm{a})$

If we tessellate $[0,1]^{d}$ with cells of side length $s\geq\delta r/2d$,
then each cell contains $(1\pm\epsilon/100)s^{d}n$ points of $V$, and there
are no points on the boundary of any cell.

  2. $(\mathrm{b})$

For every point $v\in V$, we have that

    1. $(\mathrm{b.1})$

$B(v,r)$ contains at most $(1+\epsilon/50)|B(v,r)\cap[0,1]^{d}|n$ points of
$V$;

    2. $(\mathrm{b.2})$

$B(v,(1-\delta)r)$ contains at least $(1-\epsilon/20)|B(v,r)\cap[0,1]^{d}|n$
points of $V$ other than $v$, and

    3. $(\mathrm{b.3})$

the annulus $B(v,r)\setminus B(v,(1-\delta)r)$ contains at most
$\epsilon\theta_{d}r^{d}n/20$ points of $V$.

  3. $(\mathrm{c})$

For every pair of points $u,v\in V$ such that $\lVert u-v\rVert\leq 2\delta
r$, $B(u,(1-2\delta)r)\cap B(v,(1-2\delta)r)\cap[0,1]^{d}$ contains at least
$(1-\epsilon/20)|B(v,r)\cap[0,1]^{d}|n$ points of $V$ other than $u$ and $v$.

###### Proof.

Property $(\mathrm{a})$ follows from a direct application of Chernoff’s bound
(Lemma 2.1) together with a union bound over all cells and from the fact that
the boundaries of all cells form a set of measure $0$. So let us focus on
$(\mathrm{b})$ and $(\mathrm{c})$.

For any two points $u,v\in[0,1]^{d}$, define the regions

$\displaystyle S_{1}=S_{1}(v)$ $\displaystyle\coloneqq[0,1]^{d}\cap
B(v,(1-\delta)r,(1+\delta)r),$ $\displaystyle S_{2}=S_{2}(v)$
$\displaystyle\coloneqq[0,1]^{d}\cap B(v,r),$ $\displaystyle S_{3}=S_{3}(u,v)$
$\displaystyle\coloneqq[0,1]^{d}\cap B(u,(1-2\delta)r)\cap B(v,(1-2\delta)r).$

Note that

$2^{-d}\delta d\theta_{d}r^{d}\leq
2^{-d}((1+\delta)^{d}-(1-\delta)^{d})|B(v,r)|\leq|S_{1}|\leq((1+\delta)^{d}-(1-\delta)^{d})|B(v,r)|\leq
3\delta d\theta_{d}r^{d}.$ (4.1)

Now, suppose that $\lVert u-v\rVert\leq 2\delta r$. Then, similarly as above,

$|S_{2}\setminus
S_{3}|\leq|B(v,(1-4\delta)r,r)|\leq(1-(1-4\delta)^{d})|B(v,r)|\leq 5\delta
d\theta_{d}r^{d}.$ (4.2)

Moreover, since $S_{3}\subseteq S_{2}$,

$4^{-d}\theta_{d}r^{d}\leq|[0,1]^{d}\cap
B(u,r/2)|\leq|S_{3}|\leq|S_{2}|\leq\theta_{d}r^{d}.$ (4.3)

Combining (4.1), (4.2) and (4.3) with the choice of $\delta$, we conclude that

$|S_{1}|\leq\epsilon|S_{3}|/50\leq\epsilon|S_{2}|/50$ (4.4)

and

$|S_{2}|\leq(1+\epsilon/30)|S_{3}|.$ (4.5)

For $(\mathrm{b})$, consider a fixed vertex $v\in V$ and reveal its position.
By the lower bounds in (4.1) and (4.3) and the choice of $C$, direct
applications of Chernoff’s bound show that, with probability $1-o(1/n)$, we
have that

$\lvert|V\cap S_{2}|-|S_{2}|n\rvert\leq\epsilon|S_{2}|n/50$ (4.6)

and

$|V\cap S_{1}|\leq 3|S_{1}|n/2.$ (4.7)

We claim that, conditionally on these two events holding, it follows that
$(\mathrm{b})$ holds for $v$. Indeed, $(\mathrm{b})$$(\mathrm{b.1})$ follows
immediately from (4.6) and, since $B(v,r)\setminus B(v,(1-\delta)r)\subseteq
S_{1}$, $(\mathrm{b})$$(\mathrm{b.3})$ follows immediately from (4.7), the
upper bound in (4.1) and the choice of $\delta$. Lastly,
$(\mathrm{b})$$(\mathrm{b.2})$ can be derived from (4.6) and (4.7) in
conjunction with (4.4). Therefore, $(\mathrm{b})$ follows by a union bound
over all vertices of the complementary events.

Now we focus on $(\mathrm{c})$. Fix two arbitrary vertices $u,v\in V$ and
reveal their positions. If $\lVert u-v\rVert>2\delta r$, there is nothing to
prove, so we may assume that $\lVert u-v\rVert\leq 2\delta r$. Consider the
random variable $X\coloneqq|S_{3}\cap(V(G)\setminus\\{u,v\\})|$ with
distribution $\mathrm{Bin}(n-2,|S_{3}|)$. By (4.3) and the choice of $C$, an
application of Lemma 2.1 implies that, with probability $1-o(n^{-2})$, we have

$X\geq(1-\epsilon/60)|S_{3}|n\geq\frac{1-\epsilon/60}{1+\epsilon/30}|S_{2}|n\geq(1-\epsilon/20)|S_{2}|n,$

where the second inequality follows from (4.5). Therefore, a union bound over
the complementary events for all $O(n^{2})$ pairs of vertices leads to the
desired conclusion. ∎

The proof of Theorem 4.1 relies on several technical lemmas. We first describe
the precise framework in which these lemmas are phrased. We will assume that
$d\in\mathbb{N}$, $\eta\in[1/2,1)$ and $\epsilon\in(0,1-\eta]$ are defined
globally. Let $0<1/C_{3}\lll\delta,c_{3}\lll\epsilon,1/d\leq 1$ (we will
reiterate the necessary relations in each lemma). Consider a tessellation of
the hypercube $[0,1]^{d}$ with cells of side length $s\coloneqq\lceil d/\delta
r\rceil^{-1}$ (so, in particular, each cell has diameter at most $\delta r$).
We denote the set of cells by $\mathcal{Q}$ and recall the auxiliary graph
$\Gamma$ with vertex set $\mathcal{Q}$ where two cells are joined by an edge
whenever they share a common $(d-1)$-dimensional face. Next, we consider a set
of $n$ vertices and assign to each of them a uniformly random position on
$[0,1]^{d}$, independently of each other. This set will play the role of the
vertex set of $G_{d}(n,r)$. Note that Lemma 4.4 applies with our choice of
parameters. Then, we randomly assign to each vertex one of three colours: red,
blue or green. To be precise, we colour each vertex in blue with probability
$\eta/(1+\eta)+\epsilon/40$, in red with probability $1/(1+\eta)-\epsilon/20$,
and in green with probability $\epsilon/40$, independently from all other
vertices (and independently of the position of the vertex in $[0,1]^{d}$).
Moreover, to each red vertex $u$, we associate a cell $q(u)\in\mathcal{Q}$ by
choosing it uniformly at random among all cells that are entirely contained in
the ball $B(u,r)$. Similarly, to each green vertex $z$, we associate a pair of
cells $q_{1},q_{2}\in\mathcal{Q}$ with $q_{1}q_{2}\in E(\Gamma)$ by choosing
uniformly at random one among all such pairs with $q_{1}\cup q_{2}\subseteq
B(z,r)$.

Some parts of our construction become more technical if we consider vertices
which are close to the boundary of $[0,1]^{d}$. For this reason, in the coming
lemmas, we will restrict most of our attention to vertices which are far from
the boundary; we will deal with vertices close to the boundary later on. Let
$\mathcal{Q}_{2r}\subseteq\mathcal{Q}$ denote the subset of cells in
$\mathcal{Q}$ which are at distance at least $2r$ from the boundary of
$[0,1]^{d}$, and let $Q_{2r}\coloneqq\bigcup_{q\in\mathcal{Q}_{2r}}q$. Our
choice of $\mathcal{Q}_{2r}$ ensures that all neighbours of vertices in a cell
of $\mathcal{Q}_{2r}$ are also at distance at least $r$ from the boundary; we
will use this fact throughout.

First, we need some simple properties about how blue vertices are distributed
over $[0,1]^{d}$ and over the neighbours of any vertex. Both results follow
from direct applications of Chernoff’s bound (Lemma 2.1), and so we omit their
proofs.

######  Lemma 4.5.

Let $0<1/C\lll\delta\lll\epsilon,1/d\leq 1$ and suppose that $C(\log
n/n)^{1/d}\leq r\leq\sqrt{d}$. Let $V$ be a set of $n$ vertices on $[0,1]^{d}$
satisfying the property described in Lemma 4.4 $(\mathrm{a})$. Then, a.a.s.
every cell $q\in\mathcal{Q}$ contains at least
$(\eta/(1+\eta)+\epsilon/70)s^{d}n$ and at most
$(\eta/(1+\eta)+\epsilon/3)s^{d}n$ blue vertices.

######  Lemma 4.6.

Let $G$ be an $n$-vertex graph. Colour $V(G)$ in such a way that each vertex
receives colour blue with probability at least $1/3$, independently of every
other vertex. Then, a.a.s. every vertex $v\in V(G)$ with $d_{G}(v)\geq 40\log
n$ has at least $d_{G}(v)/6\geq 1$ blue neighbours.

Our next lemma shows that, after colouring the vertices, we can find large
sets of blue vertices contained in a small number of cells forming a path in
$\Gamma$. Moreover, we can find such sets even if a few of the vertices are
“forbidden”. We will later show that we can construct cycles containing
precisely the sets of blue vertices given by this result.

######  Lemma 4.7.

Let $0<1/C,c\lll\epsilon,1/d\leq 1$. Suppose $r\in[C(\log n/n)^{1/d},c]$, and
let $V$ be a set of $n$ vertices in $[0,1]^{d}$ satisfying the property
described in Lemma 4.4 $(\mathrm{a})$. Then, a.a.s. the following event holds:
for every blue vertex $v\in V\cap Q_{2r}$, every set $A\subseteq(V\cap
Q_{2r})\setminus\\{v\\}$ such that $|A\cap q|\leq 2$ for all
$q\in\mathcal{Q}_{2r}$, and every integer $\ell\in[3,\eta n/(1+\eta)-|A|]$,
there exist

  * •

a positive integer $m\leq(\ell-1)/2$,

  * •

distinct cells $q_{1},\ldots,q_{m}\in\mathcal{Q}_{2r}$, and

  * •

for each $j\in[m]$, a set of blue vertices $S_{j}\subseteq(V\cap
q_{j})\setminus A$

such that $v\in S\coloneqq
S_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\ldots\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}S_{m}$
and $|S|=\ell$, and

  1. $(\mathrm{a})$

for each $j\in[m]$, $|S_{j}\setminus\\{v\\}|\geq 2$ and $S_{j}\subseteq
q_{j}$, and

  2. $(\mathrm{b})$

for each $j\in[m-1]$, $q_{j}q_{j+1}\in E(\Gamma)$.

###### Proof.

Let $0<1/C\lll\delta\lll\epsilon,1/d\leq 1$ and $0<c\lll\epsilon,1/d\leq 1$ so
that $|[0,1]^{d}\setminus Q_{2r}|\leq\epsilon/100$. Thus, by Lemma 4.5, a.a.s.
$Q_{2r}$ contains at least $\eta n/(1+\eta)$ blue vertices and each cell in
$\mathcal{Q}_{2r}$ contains at least six blue vertices. We condition on these
events.

Now fix a blue vertex $v$ in some cell $q\in\mathcal{Q}_{2r}$. As the
auxiliary graph $\Gamma_{2r}\coloneqq\Gamma[\mathcal{Q}_{2r}]$ contains a
Hamilton path, for each $m\in[|\mathcal{Q}_{2r}|]$ it must contain a path of
length $m-1$ which itself contains $q$. Now, let $m$ be the smallest integer
such that $\Gamma_{2r}$ contains a path $P$ of length $m-1$ with $q\in V(P)$
and such that the cells in $V(P)$ contain a total of at least $\ell$ blue
vertices not contained in $A$ (note that, as $Q_{2r}$ contains at least $\eta
n/(1+\eta)$ blue vertices, $m$ is well defined). In particular, since all
cells in $\mathcal{Q}_{2r}$ contain at least four blue vertices outside $A$,
$m\leq\lceil\ell/4\rceil\leq(\ell-1)/2$. Let $V(P)=\\{q_{1},\ldots,q_{m}\\}$,
where the labelling is given by the order in which the cells appear on the
path so that $(\mathrm{b})$ holds. Now, let $S\subseteq(V\setminus
A)\cap\bigcup_{j=1}^{m}q_{j}$ be such that $|S|=\ell$, $v\in S$ and $|(S\cap
q_{j})\setminus\\{v\\}|\geq 2$ for all $j\in[m]$ (the existence of such a set
is guaranteed by the minimality of $m\leq(\ell-1)/2$ in the definition of $P$
and the fact that each cell contains at least four vertices outside $A$). In
order to complete the proof, for each $j\in[m]$, let $S_{j}\coloneqq S\cap
q_{j}$ so that the partition $S=\bigcupdot_{j=1}^{m}S_{j}$ satisfies
$(\mathrm{a})$. ∎

Our next lemma gives us further information on the distribution of red and
green vertices and guarantees that they can be used to string together long
paths.

######  Lemma 4.8.

Let $0<1/C\lll\delta\lll\epsilon,1/d\leq 1$. Suppose $r\in[C(\log
n/n)^{1/d},\sqrt{d}]$, and let $V$ be a set of vertices on $[0,1]^{d}$
satisfying the properties described in Lemma 4.4. Consider the geometric graph
$G=G(V,r)$ and let $H\subseteq G$ be an $(\eta+\epsilon)$-subgraph. Then,
a.a.s. the following properties hold:

  1. $(\mathrm{a})$

For every cell $q\in\mathcal{Q}_{2r}$ and every vertex $v\in V\cap q$, there
are at least $(\eta/(\eta+1)+\epsilon/3)s^{d}n$ red $H$-neighbours $u$ of $v$
satisfying $q(u)=q$.

  2. $(\mathrm{b})$

For every cell $q\in\mathcal{Q}_{2r}$, there are at most
$(1/(\eta+1)+\epsilon/20)s^{d}n$ red vertices $u$ such that $q(u)=q$.

  3. $(\mathrm{c})$

For every pair of cells $q_{1},q_{2}\in\mathcal{Q}$ with $q_{1}q_{2}\in
E(\Gamma)$, each pair of vertices $v_{1},v_{2}\in V\cap(q_{1}\cup q_{2})$ have
at least five common green $H$-neighbours associated to $q_{1},q_{2}$.

###### Proof.

For every point $x\in[r,1-r]^{d}$, the number of cells $q\in\mathcal{Q}$ with
$q\subseteq B(x,r)$ lies in the interval
$[(1-\epsilon/20)\theta_{d}r^{d}/s^{d},\theta_{d}r^{d}/s^{d}]$. Hence, for any
vertex $u\in V\cap[r,1-r]^{d}$ and any cell $q\in\mathcal{Q}$ with $q\subseteq
B(u,r)$, we have that

$\mathbb{P}[u\text{ is red and }q(u)=q]\in[p_{\min},p_{\max}],$ (4.8)

where

$p_{\min}\coloneqq\left(\frac{1}{1+\eta}-\frac{\epsilon}{20}\right)\frac{s^{d}}{\theta_{d}r^{d}}\qquad\text{
and }\qquad
p_{\max}\coloneqq\left(\frac{1}{1+\eta}-\frac{\epsilon}{20}\right)\frac{s^{d}}{(1-\epsilon/20)\theta_{d}r^{d}}.$
(4.9)

We begin by proving $(\mathrm{a})$. Fix a vertex $v\in V\cap Q_{2r}$ and let
$q\in\mathcal{Q}_{2r}$ be the cell containing $v$. By Lemma 4.4
$(\mathrm{b})$$(\mathrm{b.2})$ and $(\mathrm{b})$$(\mathrm{b.3})$,

$\displaystyle|N_{H}(v)\cap B(v,(1-\delta)r)|$
$\displaystyle\geq(\eta+\epsilon)|N_{G}(v)\cap
B(v,r)|-|N_{G}(v)\cap(B(v,r)\setminus B(v,(1-\delta)r))|$
$\displaystyle\geq(\eta+\epsilon)\left(1-\frac{\epsilon}{20}\right)\theta_{d}r^{d}n-\frac{\epsilon}{20}\theta_{d}r^{d}n\geq(\eta+0.9\epsilon)\theta_{d}r^{d}n.$
(4.10)

Now, let $X$ denote the number of red $H$-neighbours $u$ of $v$ with $q(u)=q$.
Since the diameter of $q$ is at most $\delta r$, if $u\in B(v,(1-\delta)r)$,
then $q\subseteq B(u,r)$. Thus, by (4.8) and (4.10), $X$ dominates a binomial
random variable $\mathrm{Bin}((\eta+0.9\epsilon)\theta_{d}r^{d}n,p_{\min})$.
Consequently, Chernoff’s bound (Lemma 2.1) and (4.9) imply that, with
probability $1-o(n^{-1})$,

$X\geq\left(1-\frac{\epsilon}{20}\right)\cdot(\eta+0.9\epsilon)\theta_{d}r^{d}n\cdot
p_{\min}\geq\left(\frac{\eta}{1+\eta}+\frac{\epsilon}{3}\right)s^{d}n.$

A union bound implies that a.a.s. the above holds for every vertex $v\in V\cap
Q_{2r}$, thus proving $(\mathrm{a})$.

We now turn to $(\mathrm{b})$. Fix $q\in\mathcal{Q}_{2r}$ and a point $x$ in
$q$. Observe that, in order for a red vertex $u$ to satisfy $q(u)=q$, the
distance between $u$ and $x$ must be at most $r$. By (4.8) and Lemma 4.4
$(\mathrm{b})$$(\mathrm{b.1})$, the number of red vertices $u$ at distance at
most $r$ from $x$ which also satisfy $q(u)=q$ is dominated by a binomial
random variable $\mathrm{Bin}((1+\epsilon/50)\theta_{d}r^{d}n,p_{\max})$.
Thus, by combining Chernoff’s bound and (4.9) we get that, with probability
$1-o(n^{-1})$, the number of red vertices $u$ with $q(u)=q$ is at most

$\left(1+\frac{\epsilon}{50}\right)\cdot\left(1+\frac{\epsilon}{50}\right)\theta_{d}r^{d}n\cdot
p_{\max}\leq\frac{1+\epsilon/20}{1-\epsilon/20}\left(\frac{1}{1+\eta}-\frac{\epsilon}{20}\right)s^{d}n\leq\left(\frac{1}{1+\eta}+\frac{\epsilon}{20}\right)s^{d}n.$

A union bound over all $O(n)$ cells in $\mathcal{Q}_{2r}$ finishes the proof
of $(\mathrm{b})$.

Lastly, we concentrate on $(\mathrm{c})$. For each point $x\in[0,1]^{d}$, the
number of edges $q_{1}q_{2}\in E(\Gamma)$ with $q_{1}\cup q_{2}\subseteq
B(x,r)$ is at most $2d\theta_{d}r^{d}/s^{d}$. Therefore, for any vertex $z\in
V\cap[0,1]^{d}$ and any edge $q_{1}q_{2}\in E(\Gamma)$ with $q_{1}\cup
q_{2}\subseteq B(z,r)$, we have that

$\mathbb{P}[z\text{ is green and associated to
}\\{q_{1},q_{2}\\}]\geq\frac{\epsilon}{40}\frac{s^{d}}{2d\theta_{d}r^{d}}\geq\frac{\epsilon\delta^{d}}{5\cdot
2^{d+4}d^{d+1}\theta_{d}}\eqqcolon p_{*}.$ (4.11)

Now, for any pair of distinct vertices $v,v^{\prime}\in V$ and any graph
$F\subseteq G$, let $q,q^{\prime}\in\mathcal{Q}$ be such that $v\in q$ and
$v^{\prime}\in q^{\prime}$, and let

$N^{\cap}_{F}(v,v^{\prime})\coloneqq\\{z\in V\cap N_{F}(v)\cap
N_{F}(v^{\prime}):q\cup q^{\prime}\subseteq B(z,r)\\}.$

For every edge $q_{1}q_{2}\in E(\Gamma)$, each pair of vertices
$v_{1},v_{2}\in V\cap(q_{1}\cup q_{2})$ are at distance at most $2\delta r$
from each other. Thus, by Lemma 4.4 $(\mathrm{c})$,
$|N^{\cap}_{G}(v_{1},v_{2})|\geq(1-\epsilon/20)|B(v,r)\cap[0,1]^{d}|n$.
Moreover, by Lemma 4.4 $(\mathrm{b})$$(\mathrm{b.1})$, every vertex $v\in V$
has degree at most $(1+\epsilon/50)|B(v,r)\cap[0,1]^{d}|n$. Since $H\subseteq
G$ is an $(\eta+\epsilon)$-subgraph of $G$ and $\eta\geq 1/2$, it follows that

$|N^{\cap}_{H}(v_{1},v_{2})|\geq|N^{\cap}_{G}(v_{1},v_{2})|-(1-\eta-\epsilon)(d_{G}(v_{1})+d_{G}(v_{2}))\geq\epsilon
2^{-d}\theta_{d}r^{d}n.$ (4.12)

Now, fix an edge $q_{1}q_{2}\in E(\Gamma)$ and a pair of vertices
$v_{1},v_{2}\in V\cap(q_{1}\cup q_{2})$, and let $Z$ denote the number of
green common $H$-neighbours $z$ of $v_{1},v_{2}$ associated to $q_{1},q_{2}$.
By (4.11) and (4.12), $Z$ dominates a binomial random variable
$\mathrm{Bin}(\epsilon 2^{-d}\theta_{d}r^{d}n,p_{*})$. Thus, Chernoff’s bound
implies that, with probability $1-o(n^{-2})$, $v_{1}$ and $v_{2}$ have at
least five green common $H$-neighbours associated to $q_{1},q_{2}$. A union
bound over the $O(n^{2})$ such pairs of vertices completes the proof. ∎

For each cell $q\in\mathcal{Q}$, let $B_{q}$ denote the (random) set of blue
vertices in $q$ and $R_{q}$ be the (random) set of red vertices $u$ such that
$q(u)=q$.

######  Corollary 4.9.

Let $0<1/C\lll\delta\lll\epsilon,1/d\leq 1$. Suppose $r\in[C(\log
n/n)^{1/d},\sqrt{d}]$, and let $V$ be a set of vertices in $[0,1]^{d}$
satisfying all properties described in Lemma 4.4. Consider the geometric graph
$G=G(V,r)$ and let $H\subseteq G$ be an $(\eta+\epsilon)$-subgraph. Then,
a.a.s. the following holds: for every cell $q\in\mathcal{Q}_{2r}$ and every
set $B_{q}^{\prime}\subseteq B_{q}$ with $|B_{q}^{\prime}|\geq 2$, the
bipartite graph $H[B_{q}^{\prime},R_{q}]$ contains a cycle with
$2|B_{q}^{\prime}|$ vertices.

###### Proof.

Reveal the colours of each vertex in $V$ and, for each red vertex, reveal the
cell it is associated to. Condition on the events from Lemma 4.5 and from
Lemma 4.8 $(\mathrm{a})$ and $(\mathrm{b})$, which hold a.a.s. We are going to
verify that, conditionally on these events, for every cell
$q\in\mathcal{Q}_{2r}$ and every set $B_{q}^{\prime}\subseteq B_{q}$ with
$|B_{q}^{\prime}|\geq 2$, the graph $H[B_{q}^{\prime},R_{q}]$ satisfies the
assumptions of Lemma 4.3 for $k\coloneqq(\eta/(\eta+1)+\epsilon/3)s^{d}n$.
Indeed, fix $q\in\mathcal{Q}_{2r}$ and assume $B_{q}^{\prime}$ plays the role
of $A$ and $R_{q}$ plays the role of $B$ from Lemma 4.3. On the one hand,
Lemma 4.5 readily ensures that $|B_{q}|\leq k$. On the other hand, the minimum
degree assumption on the vertices of $B_{q}^{\prime}$ follows from Lemma 4.8
$(\mathrm{a})$, which immediately implies that $|R_{q}|\geq k$. Lastly, by
Lemma 4.8 $(\mathrm{b})$ and since $\eta\geq 1/2$ we have that

$|R_{q}|\leq\left(\frac{1}{\eta+1}+\frac{\epsilon}{20}\right)s^{d}n\leq\left(\frac{2\eta}{\eta+1}+\frac{\epsilon}{20}\right)s^{d}n\leq
2k-2.$

Thus, by Lemma 4.3, $H[B_{q}^{\prime},R_{q}]$ contains a cycle of length
$2|B_{q}^{\prime}|$. ∎

We are now ready to prove Theorem 4.1.

###### Proof of Theorem 4.1.

Let $0<1/C_{3}\lll c_{3}\lll\delta\lll\epsilon,1/d\leq 1$ be such that Lemmas
4.4, 4.5, 4.7 and 4.8 (and thus also Corollary 4.9) hold with $C_{3}$ and
$c_{3}$ playing the roles of $C$ and $c$, respectively. Consider $G\sim
G_{d}(n,r)$ and condition on the event that $V\coloneqq V(G)$ satisfies the
properties described in Lemma 4.4 (which hold a.a.s.). Fix any vertex $v\in
V$, and let $H$ be an $(\eta+\epsilon)$-subgraph of $G$. We are going to show
that $H$ contains a cycle of each of the desired lengths which itself contains
$v$.

Consider the random colouring of the vertices and the random assignment of
cells and pairs of cells to red and green vertices. Since the conclusions of
Lemma 4.5, Lemma 4.6 (for $H$ with minimum degree at least $40\log n$ and
probability $\eta/(1+\eta)\geq 1/3$ that a vertex is blue), Lemmas 4.7, 4.8
and 4.9 hold a.a.s., they also hold a.a.s. conditionally on $v$ being blue.
Hence, we can (and do) fix a colouring of $V$ where the vertex $v$ is blue and
an assignment of cells and pairs of cells to red and green vertices satisfying
the conclusions of Lemmas 4.5, 4.6, 4.7, 4.8 and 4.9.

The following claim allows us to construct cycles of any even length
$2\ell\leq 2\eta n/(1+\eta)$ whose vertices are not too close to the boundary.
Moreover, it ensures that the cycles satisfy certain additional properties
with respect to the colouring, which will be useful later to construct the
cycles we want.

######  Claim 2.

Let $v^{\prime}\in Q_{2r}$ be a blue vertex, let $A\subseteq
V\setminus\\{v^{\prime}\\}$ be a set of blue vertices such that $|A\cap q|\leq
2$ for all $q\in\mathcal{Q}$, and let $q^{\prime}\in\mathcal{Q}_{2r}$ be the
cell containing $v^{\prime}$. Then, for every integer $\ell\in[2,\eta
n/(1+\eta)-|A|]$, there exists a cycle $\mathfrak{O}^{\prime}\subseteq H-A$ of
length $2\ell$ with $v^{\prime}\in V(\mathfrak{O}^{\prime})$ such that

  1. $(\mathrm{P}1)$

every blue vertex in $\mathfrak{O}^{\prime}$ is contained in $Q_{2r}$;

  2. $(\mathrm{P}2)$

every green vertex in $\mathfrak{O}^{\prime}$ joins two blue vertices which
lie in distinct cells sharing a $(d-1)$-dimensional face and is associated to
this pair of cells;

  3. $(\mathrm{P}3)$

for every pair of cells in $\mathcal{Q}_{2r}$ which share a
$(d-1)$-dimensional face, the number of green vertices of
$\mathfrak{O}^{\prime}$ associated to this pair of cells is at most $2$, and

  4. $(\mathrm{P}4)$

$\mathfrak{O}^{\prime}$ contains a subpath of length $2$ whose endpoints are
$v^{\prime}$ and another blue vertex in $q^{\prime}$.

###### Proof.

By Lemma 4.5, $q^{\prime}$ contains at least four blue vertices. Let
$v^{\prime\prime}\in V\setminus A$ be a blue vertex in $q^{\prime}$ other than
$v^{\prime}$. By Corollary 4.9, $v^{\prime}$ and $v^{\prime\prime}$ are
contained in a cycle of length $4$ in $H$ which satisfies
$(\mathrm{P}1)$–$(\mathrm{P}4)$. Thus, we may assume that $\ell\in[3,\eta
n/(1+\eta)-|A|]$.

Fix $\ell\in[3,\eta n/(1+\eta)-|A|]$. Consider the integer $m$, the cells
$q_{1},\ldots,q_{m}\in\mathcal{Q}_{2r}$ and the set of blue vertices
$S=S_{1}\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}\ldots\mathbin{\mathchoice{\leavevmode\vtop{\halign{\hfil$\m@th\displaystyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\textstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}{\leavevmode\vtop{\halign{\hfil$\m@th\scriptscriptstyle#$\hfil\cr\cup\cr\cdot\crcr}}}}S_{m}\subseteq
V\setminus A$ with $S_{j}\subseteq q_{j}$, $|S|=\ell$ and $v^{\prime}\in S$
given by Lemma 4.7 with $v^{\prime}$ playing the role of $v$. For each
$j\in[m]$, by Corollary 4.9 and since $|S_{j}|\geq 2$ by Lemma 4.7
$(\mathrm{a})$, the set $S_{j}$ is contained in a cycle
$\mathfrak{O}_{j}\subseteq H-A$ of length $2|S_{j}|$ where blue vertices and
red vertices associated to $q_{j}$ alternate. Since each red vertex is
assigned to a single cell, the cycles
$\mathfrak{O}_{1},\ldots,\mathfrak{O}_{m}$ are vertex-disjoint. Now, for every
$j\in[m]$, fix an orientation of $\mathfrak{O}_{j}$ and choose two distinct
paths $P_{j},P_{j}^{\prime}\subseteq\mathfrak{O}_{j}$ of length $2$ whose
endpoints are blue and such that, for the value of $j$ satisfying
$q_{j}=q^{\prime}$, at least one of them does not contain $v^{\prime}$ (which
can be done by Lemma 4.7 $(\mathrm{a})$ applied with $v^{\prime}$ playing the
role of $v$ and since $\ell\geq 3$). For every $j\in[m]$, let $w_{1,j}$ be the
starting point and $w_{2,j}$ be the endpoint of $P_{j}$, let
$w_{1,j}^{\prime}$ be the starting point and $w_{2,j}^{\prime}$ be the
endpoint of $P_{j}^{\prime}$, and let
$T_{j},T_{j}^{\prime}\subseteq\mathfrak{O}_{j}$ be the
$(w_{2,j},w_{1,j}^{\prime})$-subpath and $(w_{2,j}^{\prime},w_{1,j})$-subpath
of $\mathfrak{O}_{j}$, respectively. Then, by Lemma 4.7 $(\mathrm{b})$ and
Lemma 4.8 $(\mathrm{c})$, for every $j\in[m-1]$, there exist two distinct
green vertices $z_{j,j+1}$ and $z_{j,j+1}^{\prime}$ associated to $q_{j}$ and
$q_{j+1}$ such that
$w_{1,j}^{\prime}z_{j,j+1},z_{j,j+1}w_{2,j+1},w_{1,j+1}z_{j,j+1}^{\prime},z_{j,j+1}^{\prime}w_{2,j}^{\prime}\in
E(H)$. Moreover, since each green vertex is associated to a single pair of
cells, the collection $\\{z_{j,j+1},z_{j,j+1}^{\prime}:j\in[m-1]\\}$ has size
$2m-2$. Thus, $H-A$ contains the cycle

$\mathfrak{O}^{\prime}\coloneqq
w_{1,1}P_{1}\bigg{(}\\!\bigtimes_{j=1}^{m-1}w_{2,j}T_{j}w_{1,j}^{\prime}z_{j,j+1}\bigg{)}w_{2,m}T_{m}w_{1,m}^{\prime}P_{m}^{\prime}w_{2,m}^{\prime}T_{m}^{\prime}w_{1,m}\bigg{(}\\!\bigtimes_{j=1}^{m-1}z_{m-j,m-j+1}^{\prime}w_{2,m-j}^{\prime}T_{m-j}^{\prime}w_{1,m-j}\bigg{)},$

which contains $S$ (and no other blue vertices) and alternates between blue
vertices and vertices of other colours, and thus has length $2\ell$. Now,
$(\mathrm{P}1)$, $(\mathrm{P}2)$ and $(\mathrm{P}3)$ hold by construction.
Finally, in order to verify $(\mathrm{P}4)$, assume that $q^{\prime}=q_{j}$
and note that, by Lemma 4.7 $(\mathrm{a})$ and the fact that at least one of
$P_{j},P_{j}^{\prime}$ does not contain $v^{\prime}$, the path among
$T_{j},T_{j}^{\prime}$ containing $v^{\prime}$ has length at least 2. ∎

Now, fix an integer $\ell\in[2,\eta n/(1+\eta)]$. First, we are going to show
that $H$ contains a cycle of length $2\ell$ which contains $v$. If $v\in
Q_{2r}$, then a cycle of length $2\ell$ containing $v$ is given immediately by
Claim 2 (with $v$ playing the role of $v^{\prime}$ and $A=\varnothing$). Thus,
suppose that $v\in[0,1]^{d}\setminus Q_{2r}$ and let
$q\in\mathcal{Q}\setminus\mathcal{Q}_{2r}$ be the cell containing $v$. Let $t$
be the length of a shortest $(q,\mathcal{Q}_{2r})$-path in $\Gamma$, and let
the cells of one such path be
$q=q^{\prime}_{0},q^{\prime}_{1},\ldots,q^{\prime}_{t}$, where the labelling
follows the order in which they appear in the path. We now consider two cases
depending on the values of $\ell$ and $t$.

_Case 1: $\ell\in[2t]$._ In this case, fix a sequence
$v=v_{0},v_{1},\ldots,v_{\ell-1}$ of distinct blue vertices such that
$v_{0}\in q_{0}^{\prime}$, $v_{j},v_{\ell-j}\in q_{j}^{\prime}$ for all
$j\in[\lfloor\ell/2\rfloor-1]$, and $v_{\lfloor\ell/2\rfloor}$ and
$v_{\lceil\ell/2\rceil}$ (which coincide when $\ell$ is even) lie in
$q_{\lfloor\ell/2\rfloor}^{\prime}$. (The existence of such a sequence is
guaranteed by Lemma 4.5.) For the sake of notation, let $v_{\ell}\coloneqq v$.
Then, by Lemma 4.8 $(\mathrm{c})$, for each $i\in[\ell]$, the blue vertices
$v_{i-1},v_{i}$ lying in a pair of consecutive cells can be connected by a
path of length two via distinct green vertices associated to these cells.
Moreover, when $\ell=2k+1$ is odd, the vertices $v_{k},v_{k+1}\in
q_{k}^{\prime}$ have an unused common green neighbour associated to the cells
$q_{k}^{\prime}$ and $q_{k-1}^{\prime}$ (which is ensured by Lemma 4.8
$(\mathrm{c})$).

_Case 2: $\ell>2t$._ In this case, by Claim 2 with $A=\varnothing$, we may
find a cycle of length $2\ell-4t+2$ satisfying $(\mathrm{P}1)$–$(\mathrm{P}4)$
such that the endpoints of the path $P$ of length $2$ guaranteed by
$(\mathrm{P}4)$ are contained in $q_{t}^{\prime}$. Let us label the endpoints
of $P$ as $v_{t}$ and $v_{t}^{\prime}$, and let us denote the path resulting
from the cycle after deleting the middle vertex of $P$ by $P_{1}$. Now, by
Lemma 4.5, for every $j\in[t-1]$, we can choose two distinct blue vertices
$v_{j}$ and $v_{j}^{\prime}$ in $q_{j}^{\prime}$. Also, set
$v_{0}=v_{0}^{\prime}\coloneqq v$. Then, by Lemma 4.8 $(\mathrm{c})$, for
every $j\in[t]$, we can find distinct green vertices that join $v_{j-1}$ to
$v_{j}$ and $v_{j-1}^{\prime}$ to $v_{j}^{\prime}$ and are associated to
$q_{j-1}^{\prime}$ and $q_{j}^{\prime}$. This results in a
$(v_{t},v_{t}^{\prime})$-path $P_{2}$ of length $4t$ which, by $(\mathrm{P}1)$
and $(\mathrm{P}2)$ and since green vertices are assigned to a unique pair of
cells, satisfies that $V(P_{1})\cap V(P_{2})=\\{v_{t},v_{t}^{\prime}\\}$.
Hence, $P_{1}\cup P_{2}$ is a cycle containing $v$ of length $L=2\ell$, as
desired.

Finally, we have to consider cycles of odd length containing a vertex $v$ in a
cell $q$. Fix any odd $L\in[c_{3}^{-1},2\eta n/(1+\eta)]$. By Lemmas 4.5 and
4.6 and the fact that $d_{H}(v)>6(\eta/(1+\eta)+\epsilon/3)s^{d}n$, there is
an edge incident to $v$ whose other endpoint is a blue vertex outside $q$. Let
this other endpoint be denoted $v^{\prime}$, and let
$q^{\prime}\in\mathcal{Q}$ be the cell containing $v^{\prime}$.

We begin by choosing a set of cells where we will pick blue vertices for our
construction. Consider a shortest $(q,q^{\prime})$-path
$\mathfrak{P}\subseteq\Gamma$, let $t$ be its length, and label its cells as
$q=q_{0},q_{1},\ldots,q_{t}=q^{\prime}$ following the order in which they
appear in $\mathfrak{P}$. Note that, by the choice of the side length $s$, we
must have $t\leq 2d^{2}/\delta$. Moreover, consider a shortest
$(V(\mathfrak{P}),\mathcal{Q}_{2r})$-path
$\mathfrak{P}^{\prime}\subseteq\Gamma$, and let $t^{\prime}$ be its length.
Let $i^{*}\in[0,t]$ denote the index such that $q_{i^{*}}\in
V(\mathfrak{P}^{\prime})$ and label the cells in $V(\mathfrak{P}^{\prime})$ as
$q_{i^{*}}=q_{0}^{\prime},q_{1}^{\prime},\ldots,q_{t^{\prime}}^{\prime}$,
following the order in which they appear in $\mathfrak{P}^{\prime}$. (We
remark here that our choice of $c_{3}$ ensures that the paths we look for are
long enough that we will always reach $Q_{2r}$, thus not requiring the same
case distinction as the cycles of even length.) Note that, similarly as above,
we must have that $t^{\prime}\leq 4d^{2}/\delta$. See Figure 4 for a
representation.

Next, we are going to choose vertices in the cells picked above and use them
to construct a short path of odd length containing $v$ and whose endpoints are
in $Q_{2r}$. Recall that, by Lemma 4.5, every cell contains $\Theta(\log n)$
blue vertices. Define $v_{0}\coloneqq v$, $v_{t}\coloneqq v^{\prime}$ and, for
every $i\in[t-1]$, choose an arbitrary blue vertex $v_{i}\in V\cap q_{i}$. Let
$w_{0}\coloneqq v_{i^{*}}$. For every $i\in[t^{\prime}]$, choose a blue vertex
$w_{i}\in V\cap q_{i}^{\prime}$. Finally, for every $i\in[0,t^{\prime}-1]$,
choose a blue vertex $w_{i}^{\prime}\in(V\cap
q_{i}^{\prime})\setminus\\{w_{i}\\}$. All of these vertices will be used to
construct a path later. Let
$B\coloneqq\\{v_{i}:i\in[0,t]\setminus\\{i^{*}\\}\\}\cup\\{w_{i},w_{i}^{\prime}:i\in[0,t^{\prime}-1]\\}$
denote the set of all vertices defined above except $w_{t^{\prime}}$. Observe
that, by the minimality of $\mathfrak{P}$ and $\mathfrak{P}^{\prime}$ and our
choices above, $B$ contains at most two vertices in each cell. Define
$\ell_{P}\coloneqq 2t+4t^{\prime}+1=2|B|+1$ so that $\ell_{P}\leq
20d^{2}/\delta+1\leq c_{3}^{-1}-2\leq L-2$.

$v^{\prime}$$v$$Q_{2r}$$q_{t}$$q^{\prime}_{t^{\prime}}$$q_{0}$$q_{i^{*}}$
Figure 4. Sketch for the construction of a short odd cycle containing $v$, in
the case $d=2$, when both $v$ and its blue neighbour $v^{\prime}$ lie outside
$Q_{2r}$. The highlighted cells are used to construct paths from $v$ and
$v^{\prime}$ to $q^{\prime}_{t^{\prime}}$, where an application of Claim 2
allows to close them into a cycle.

By applying Claim 2 (with $w_{t^{\prime}}$, $q_{t^{\prime}}^{\prime}$ and $B$
playing the roles of $v^{\prime}$, $q^{\prime}$ and $A$), one may find a cycle
$\mathfrak{O}^{\prime}$ of length $L-\ell_{P}+2\geq 4$ satisfying
$(\mathrm{P}1)$–$(\mathrm{P}4)$. Let $w_{t^{\prime}}^{\prime}$ be the other
(blue) endpoint of the subpath of length $2$ given by $(\mathrm{P}4)$, let
$P^{\prime}$ be the other subpath of $\mathfrak{O}^{\prime}$ between
$w_{t^{\prime}}$ and $w_{t^{\prime}}^{\prime}$ (which has length
$L-\ell_{P}$), and let $\mathcal{G}$ denote the set of all green vertices of
$\mathfrak{O}^{\prime}$.

By Lemma 4.8 $(\mathrm{c})$ in conjunction with $(\mathrm{P}3)$, for each
$i\in[t]\setminus\\{i^{*}+1\\}$, we may find a green vertex $z_{i}\in
V\setminus\mathcal{G}$ which is joined by an edge to both $v_{i-1}$ and
$v_{i}$ and is associated to $q_{i-1}$ and $q_{i}$; additionally, for
$i=i^{*}+1$, we may find a green vertex $z_{i^{*}+1}\in V\setminus\mathcal{G}$
associated to $q_{i^{*}}$ and $q_{i^{*}+1}$ joined to both
$v_{i^{*}}^{\prime}$ and $v_{i^{*}+1}$. Similarly, by Lemma 4.8 $(\mathrm{c})$
and $(\mathrm{P}3)$, for each $i\in[t^{\prime}]$ we may find two green
vertices $y_{i}$ and $y_{i}^{\prime}$, both associated to $q_{i-1}^{\prime}$
and $q_{i}^{\prime}$, such that $y_{i}$ is joined by an edge to both $w_{i-1}$
and $w_{i}$, $y_{i}^{\prime}$ is joined to both $w_{i-1}^{\prime}$ and
$w_{i}^{\prime}$, and all these vertices are pairwise distinct and distinct
from the $z_{j}$’s and the vertices in $\mathcal{G}$. This results in the path

$P\coloneqq\bigtimes_{j=0}^{t^{\prime}-1}(w_{t^{\prime}-j}^{\prime}y_{t^{\prime}-j}^{\prime})v_{i^{*}}^{\prime}\bigtimes_{j=i^{*}+1}^{t}(z_{j}v_{j})v_{0}\bigtimes_{j=1}^{i^{*}}(z_{j}v_{j})\bigtimes_{j=1}^{t^{\prime}}(y_{j}w_{j}).$

Observe that, by construction, $P$ is a path of length $\ell_{P}$. Moreover,
by the construction of $\mathfrak{O}^{\prime}$ and $B$, and since $P$ has no