# Sharp threshold for embedding balanced spanning trees in random geometric
graphs

Alberto Espuny Díaz<EMAIL_ADDRESS>Institut für
Mathematik, Technische Universität Ilmenau, 98684 Ilmenau, Germany.  ,  Lyuben
Lichev<EMAIL_ADDRESS>Institut Camille Jordan, Univ. Jean
Monnet, Saint-Etienne, France  ,  Dieter Mitsche<EMAIL_ADDRESS>IMC, Pont. Univ. Católica, Chile and Institut Camille Jordan, Univ. Jean
Monnet, Saint-Etienne, France  and  Alexandra Wesolek<EMAIL_ADDRESS>Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada

###### Abstract.

A rooted tree is _balanced_ if the degree of a vertex depends only on its
distance to the root. In this paper we determine the sharp threshold for the
appearance of a large family of balanced spanning trees in the random
geometric graph $\mathcal{G}(n,r,d)$. In particular, we find the sharp
threshold for balanced binary trees. More generally, we show that _all_
sequences of balanced trees with uniformly bounded degrees and height tending
to infinity appear above a sharp threshold, and none of these appears below
the same value. Our results hold more generally for geometric graphs
satisfying a mild condition on the distribution of their vertex set, and we
provide a polynomial time algorithm to find such trees.

The research leading to these results has been supported by the Carl-Zeiss-
Foundation and by DFG grant PE 2299/3-1 (A. Espuny Díaz), by grant GrHyDy
ANR-20-CE40-0002 and by Fondecyt grant 1220174 (D. Mitsche) and by the Vanier
Scholarship Program (A. Wesolek).

##  1\. Introduction

The _random geometric graph_ $\mathcal{G}(n,r,d)$ is a classic model of random
graphs defined as follows. Let $d$ and $n$ be positive integers, and let $r$
be a positive real number. The vertices of the graph are $n$ points sampled
uniformly at random and independently from $[0,1]^{d}$, and two vertices are
connected by an edge if their Euclidean distance is at most $r$. Since their
introduction by Gilbert [11] as a model for telecommunication networks, random
geometric graphs have received a lot of attention both from an applied point
of view [1, 23, 10] and from a theoretical point of view [25, 27]. Moreover,
the original model has been generalized in many different ways; for example,
Waxman [29] introduced a model with additional percolation of the edges, which
has been further studied in [7, 19, 26]. Here, we focus on the classic model
defined above.

One main reason for the substantial interest in random geometric graphs is
their use as a model for wireless networks. Such networks consist of a set of
nodes, each of them equipped with a wireless transceiver to communicate with
their nearest neighbors (in terms of Euclidean distance). The ability of
communication (controlled by the range $r$) depends on the transmitting power
of the transceivers. The goal is to spread information through the network,
which is done in a multi-hop fashion. In many ad hoc networks, like sensor
networks, energy consumption is an issue. Therefore, one of the most important
questions when modeling a network is how to minimize power consumption (see,
for example, [1, 3, 28]). To do this, the transmission range should be made as
small as possible, but at the same time large enough to make sure that a piece
of information transmitted from a node will arrive to all other nodes in the
network. Spanning trees are especially interesting from this application point
of view since they are minimally connected sets. In particular, when
restricting these trees to having a particular structure, this raises the
question of which transmission range is needed in order to ensure such trees
in a graph.

Random geometric graphs are known to exhibit _threshold_ behavior for many
graph properties, meaning that there are some special values of the parameters
of the model around which a drastic change in the behavior of the graph with
respect to these properties takes place. Understanding these thresholds is one
of the main directions of research in the theory of random graphs. In the
current work, we show that such a phenomenon takes place for the property of
containing a wide range of “sufficiently symmetric” spanning trees.

###  1.1. Thresholds in random geometric graphs

Formally, a _graph property_ (or just property) is a set of labeled graphs
which is closed under isomorphism. A property is said to be _monotone
increasing_ (resp. monotone decreasing) if it is preserved under edge addition
(resp. edge deletion). In particular, when thinking of $\mathcal{G}(n,r,d)$,
an increasing (resp. decreasing) property is preserved after increasing (resp.
decreasing) the radius. This leads to the definition of thresholds in random
geometric graphs: a function $r^{*}=r^{*}(n,d)$ is a _threshold_ for some
monotone increasing property $\mathcal{P}$ in $\mathcal{G}(n,r,d)$ if

$\lim_{n\to\infty}\mathbb{P}[\mathcal{G}(n,r,d)\in\mathcal{P}]=\begin{cases}0&\text{if
}r=o(r^{*}),\\\ 1&\text{if }r=\omega(r^{*}).\end{cases}$

Moreover, we say that $r^{*}$ is a _sharp threshold_ for $\mathcal{P}$ if, for
every $\epsilon\in(0,1)$,

$\lim_{n\to\infty}\mathbb{P}[\mathcal{G}(n,r,d)\in\mathcal{P}]=\begin{cases}0&\text{if
}r\leq(1-\epsilon)r^{*},\\\ 1&\text{if }r\geq(1+\epsilon)r^{*}.\end{cases}$

In this context, McColm [20] proved that all monotone increasing properties
have a threshold in $\mathcal{G}(n,r,1)$, and also that any such property
whose threshold is much larger than $\log n/n$ must have a sharp threshold
(throughout the paper, $\log$ stands for the natural logarithm). Goel, Rai and
Krishnamachari [13] gave general upper bounds for the threshold width in
$\mathcal{G}(n,r,d)$ for all $d\geq 1$, and Bradonjić and Perkins [4]
characterized vertex-monotone properties which exhibit a sharp threshold.
While the results in [20, 13, 4] serve to prove the existence of (sharp)
thresholds, they give no indication of where these thresholds actually are.
Determining the (sharp) thresholds for different properties of interest is one
of the main problems in the area, and it has received much attention.

###  1.2. Spanning trees in random geometric graphs

A _spanning_ subgraph of a graph $G$ is a subgraph whose vertex set is $V(G)$.
In this paper, we are interested in determining the (sharp) threshold for the
appearance of different spanning trees in random geometric graphs.

A necessary condition for the containment of any spanning tree is that the
graph must be connected. The sharp threshold for connectivity in
$\mathcal{G}(n,r,1)$ was determined by Godehardt and Jaworski [12], who showed
that it is $\log n/n$. In $\mathcal{G}(n,r,2)$, Gupta and Kumar [15] and
Penrose [24] independently showed that the sharp threshold for connectivity is
$\sqrt{\log n/\uppi n}$. Later, Penrose [25, Theorem 13.2] showed that, for
all $d\geq 2$, the sharp threshold for connectivity in $\mathcal{G}(n,r,d)$ is
$(2^{d-1}\log n/(d\theta_{d}n))^{1/d}$, where $\theta_{d}$ is the volume of a
unit ball in $\mathbb{R}^{d}$. In fact, he even showed that, as $r$ increases,
typically the graph becomes connected exactly when its last isolated vertex
disappears (see [25, Theorem 13.17]). These results are crucial towards
understanding the properties of the _minimum spanning tree_ of
$\mathcal{G}(n,r,d)$. However, they do not give us any information about the
threshold for the appearance of _specific_ spanning trees.

An important special case of the problem of finding a fixed spanning tree is
the containment of a spanning path. On the one hand, Díaz, Mitsche and Pérez-
Giménez [9] showed that the sharp threshold for $\mathcal{G}(n,r,2)$ to
contain a Hamilton cycle (i.e., a spanning cycle) is $\sqrt{\log n/\uppi n}$,
that is, the same as the sharp threshold for connectivity. This result was
later extended by Balogh, Bollobás, Krivelevich, Müller and Walters [2] and
Müller, Pérez-Giménez and Wormald [22], who showed that the sharp threshold
for Hamiltonicity in $\mathcal{G}(n,r,d)$ coincides with the sharp threshold
for connectivity for all $d\geq 2$. In fact, they showed that typically a
Hamilton cycle appears in $\mathcal{G}(n,r,d)$ once all vertices have degree
at least $2$. On the other hand, when $d=1$, scanning the points from left to
right easily shows that the graph contains a spanning path as long as it is
connected. In particular, these results imply that the sharp threshold for
containing a spanning path in $\mathcal{G}(n,r,d)$ is the same as the sharp
threshold for connectivity for all $d\geq 1$.

The question of trying to find the (sharp) threshold for the appearance of
different families of spanning trees pops up naturally. In the case of “path-
like” trees, one may obtain the threshold directly from the threshold for
Hamiltonicity. Indeed, by the triangle inequality, if $\mathcal{G}(n,r,d)$
contains a Hamilton cycle and $k\in\mathbb{N}$, then $\mathcal{G}(n,kr,d)$
contains the $k$-th power of this Hamilton cycle. It immediately follows that
every spanning tree which can be embedded into the $k$-th power of a Hamilton
cycle has the same threshold as Hamiltonicity. This is the case, for instance,
of spanning caterpillars with constant maximum degree.

One may naturally wonder whether all spanning trees with bounded maximum
degree have the same threshold. Incidentally, in the model of binomial random
graphs $\mathcal{G}(n,p)$ where each of the
$\bigl{(}\kern-1.00006pt\genfrac{}{}{0.0pt}{}{n}{2}\kern-1.00006pt\bigr{)}$
possible edges appears independently with probability $p$, Montgomery [21]
proved that this is the case: the threshold for all bounded-degree spanning
trees is $\log n/n$. However, this turns out to be very far from the truth in
random geometric graphs. Indeed, there are bounded-degree trees $T$ whose
diameter is logarithmic in the number of vertices, and this diameter directly
imposes a much higher lower bound on the threshold $r^{*}$ for the property of
containing a copy of $T$: since a spanning subgraph of $\mathcal{G}(n,r,d)$
cannot have smaller diameter than $\mathcal{G}(n,r,d)$ itself, the threshold
for spanning trees of diameter $O(\log n)$ must satisfy $r^{*}=\Omega(1/\log
n)$. This is far larger than the connectivity threshold mentioned above. The
results of Goel, Rai and Krishnamachari [13] imply that, for any such tree,
there is a sharp threshold. Our goal is to determine the value of this
threshold.

Note that, among all trees with logarithmic diameter, binary trees are
especially interesting due to their many applications as data structures (see,
e.g., [6]). Identifying the sharp threshold for embedding these trees in
$\mathcal{G}(n,r,d)$ is thus an important particular case of our study.

###  1.3. Main results

As mentioned above, our focus is on determining the sharp threshold for the
appearance of certain trees having thresholds at large radial values. For a
graph $G$, we denote by $|G|$ the size of the vertex set of $G$.

The trees $T$ we consider will have a special vertex which we will call the
_root_. We may think of the vertices of $T$ as being partitioned into _layers_
$V_{0},V_{1},\ldots$, where $V_{i}$ contains all vertices at (graph) distance
$i$ from the root. The _height_ of $T$ is the maximum $h\in\mathbb{N}$ such
that $V_{h}$ is empty. For any vertex $v\in V(T)$, if $v\in V_{j}$, we refer
to its neighbors in $V_{j+1}$ as its _children_ , and to all vertices which
can be reached by a path from $v$ without going through $V_{j-1}$ as its
_descendants_. Given a positive integer $s$, we say that a tree is an _$s$
-ary tree_ if all its vertices have at most $s$ children. We say that an
$s$-ary tree of height $h$ is _complete balanced_ if all vertices in
$V_{0},V_{1},\ldots,V_{h-1}$ have $s$ children. For simplicity, we will refer
to complete balanced $s$-ary trees simply as _balanced $s$-ary trees_ (except
in Section 4.3). Observe that a balanced $s$-ary tree of height $h$ must have
$n=\sum_{i=0}^{h}s^{i}$ vertices and diameter $2h$.

As typical in random graphs literature, we focus on asymptotic statements. We
state our asymptotic results in terms of the height $h$ of the trees, which
then also yields asymptotic results with respect to the number of vertices.
Our first result determines the sharp threshold for $\mathcal{G}(n,r,d)$ to
contain a spanning copy of the balanced $s$-ary tree for any fixed integer
$s\geq 2$ and $n$ of the form $\sum_{i=0}^{h}s^{i}$.

######  Theorem 1.

Fix positive integers $s\geq 2$ and $d$. Let $h$ be a positive integer, and
set $n\coloneqq\sum_{i=0}^{h}s^{i}$. Let $T_{h}$ be the balanced $s$-ary tree
of height $h$ (and on $n$ vertices). Then, $r^{*}\coloneqq\sqrt{d}/2h$ is the
sharp threshold for $\mathcal{G}(n,r,d)$ to contain a copy of $T_{h}$.

In fact, Theorem 1 is a particular case of a similar result for a larger class
of trees. Given positive integers $h$ and $(s_{i})_{i=1}^{h}$, we say that a
tree $T$ is the _balanced tree over the sequence $(s_{i})_{i=1}^{h}$_ if it
has height $h$ and for each $i\in\\{1,\ldots,h\\}$, every vertex of $T$ in
$V_{i-1}$ has exactly $s_{i}$ children. In particular, such a tree $T$
contains exactly $\sum_{i=0}^{h}\prod_{j=1}^{i}s_{j}$ vertices (where, by
convention, the empty product equals $1$). Moreover, if $M\geq 2$ is an
integer and $s_{i}\in\\{2,\ldots,M\\}$ for every $i\in\\{1,\ldots,h\\}$, we
say that the balanced tree over the sequence $(s_{i})_{i=1}^{h}$ is a balanced
$M$-tree.

Our next result extends Theorem 1 to all balanced $M$-trees, as long as $M$ is
not too large compared to $h$.

######  Theorem 2.

Fix a positive integer $d$, and let $2\leq M=M(h)=o(h/\log h)$. Let
$(T_{h})_{h\geq 1}$ be a sequence of trees where $T_{h}$ is a balanced
$M$-tree of height $h$. Then, $r^{*}\coloneqq\sqrt{d}/2h$ is the sharp
threshold for $\mathcal{G}(|T_{h}|,r,d)$ to contain a copy of $T_{h}$.

Theorem 2 follows from a more general technical result (Theorem 7) which we
state and prove in Section 3.

###  1.4. Outline of proof

In order to prove the upper bound for the threshold, we provide an efficient
algorithm that finds an embedding of a balanced $M$-tree $T$ of height $h$
into $\mathcal{G}(|T|,r,d)$ when $r\geq(1+\epsilon)r^{*}$ for any small (but
fixed) $\epsilon>0$. This embedding is carried out in two steps. The first
part of the proof consists of the analysis of an algorithm that embeds the
first roughly $(1-\epsilon)h$ layers of $T$ into $\mathcal{G}(|T|,r,d)$
(itself seen in its random embedding in $[0,1]^{d}$) in a fractal-like
fashion. The second part of the embedding relies on a version of Hall’s
theorem (for which efficient algorithmic implementations are well known). The
lower bound is comparably much easier and follows from the already mentioned
comparison of the diameters of any connected graph and any of its spanning
subgraphs.

##  2\. Auxiliary results

We recall a variant of the famous Chernoff’s bound (see, e.g., [18, Corollary
2.3]).

######  Lemma 3.

Let $X$ be a binomial random variable and $\mu\coloneqq\mathbb{E}[X]$. Then,
for all $0<\delta<1$, we have that

$\mathbb{P}[|X-\mu|\geq\delta\mu]\leq 2\mathrm{e}^{-\delta^{2}\mu/3}.$

Next, we state a version of the celebrated Hall’s theorem [16] (see also [8,
Chapter 2.1]) and deduce a corollary needed in the proof of Theorem 7.

######  Theorem 4 (Hall [16]).

A bipartite graph with parts $A$ and $B$ contains a matching of size $|A|$ if
and only if for every set $S\subseteq A$, the number of neighbors of $S$ in
$B$ is at least $|S|$.

We refer to a copy of the bipartite graph $K_{1,k}$ in which $v$ constitutes
the part containing exactly one vertex as a _$k$ -star with center $v$_. If we
only specify that the center $v$ lies in some set $A$, we refer to this graph
as a _$k$ -star with center in $A$_.

######  Corollary 5.

Fix a positive integer $k$ and a bipartite graph $G$ with parts $A$ and $B$
such that $k|A|=|B|$. Then, the vertices of $G$ may be partitioned into $|A|$
vertex-disjoint $k$-stars with centers in $A$ if and only if for every set
$S\subseteq A$, the number of neighbors of $S$ in $B$ is at least $k|S|$.

###### Proof.

The proof of the second statement from the first one is trivial. Thus, we
focus on the converse implication. Let $A_{1},\ldots,A_{k}$ be $k$ copies of
the set $A$. For each $u\in A$ and each $i\in\\{1,\ldots,k\\}$, let $u_{i}$ be
the copy of $u$ in $A_{i}$. We define an auxiliary bipartite graph $\Gamma$
with parts $\overline{A}\coloneqq\bigcupdot_{i=1}^{k}A_{i}$ and $B$ where, for
every $i\in\\{1,\ldots,k\\}$, $u\in A$ and $v\in B$, we have $u_{i}v\in
E(\Gamma)$ if and only if $uv\in E(G)$.

Now, for any set $S\subseteq\overline{A}$, let $\alpha(S)\subseteq A$ be the
set of all vertices $u\in A$ such that, for some $j\in\\{1,\ldots,k\\}$, we
have $u_{j}\in S$. Then, for every $S\subseteq\overline{A}$, the neighborhoods
of $S$ in $\Gamma$ and $\alpha(S)$ in $G$ coincide. This means that the
neighborhood of $S$ in $\Gamma$ contains at least $k|\alpha(S)|\geq|S|$
vertices. Hence, an application of Hall’s theorem ensures the existence of a
perfect matching in $\Gamma$. Finally, identifying the sets
$A_{1},\ldots,A_{k}$ shows that one may partition the original graph into
$|A|$ $k$-stars with centers in $A$, as desired. ∎

######  Remark 6.

If the condition of Hall’s theorem is satisfied, there exist efficient
algorithms for finding a matching in a bipartite graph. A classic polynomial
time algorithm for iterative construction of such a matching is based on
augmenting paths; see, e.g., [8, Section 2.1]. Hopcroft and Karp’s algorithm
[17] improved on the classic algorithm by processing several augmenting paths
at a time. Later, Chwa and Kim [5], and Goldberg, Plotkin and Vaidya [14] came
up with even faster parallel algorithms. As a consequence, under the
assumptions of Corollary 5, finding a family of $|A|$ disjoint stars with
centers in $A$ can also be done in polynomial time.

##  3\. Balanced trees in random geometric graphs

In this section, we state and prove the more general theorem from which
Theorems 1 and 2 follow. This result is stated in terms of the _random
geometric graph sequence_ defined as follows. Let $r$ be a positive real
number and let $d$ be a positive integer. Given a set of points
$\mathcal{X}\subseteq[0,1]^{d}$, the geometric graph $G(\mathcal{X},r,d)$ is
the graph with vertex set $\mathcal{X}$ and edge set
$\\{xy:x,y\in\mathcal{X},x\neq y,\lVert x-y\rVert\leq r\\}$, where
$\lVert\cdot\rVert$ denotes the Euclidean norm. Let $(X_{i})_{i\geq 1}$ be a
sequence of independent uniform random variables on $[0,1]^{d}$. The _random
geometric graph sequence_ of radius $r$ is a sequence of graphs
$\widehat{\mathcal{G}}(r,d)=(G_{n})_{n\geq 1}$ where
$G_{n}=G(\\{X_{1},\ldots,X_{n}\\},r,d)$. In particular, note that $G_{n}$ is
distributed as $\mathcal{G}(n,r,d)$, but the different graphs in the sequence
are not independent of each other.

Given a probability space $(\Omega,\mathcal{F},\mathbb{P})$ and events
$E_{h}\in\mathcal{F}$ for all $h\geq 1$, we say that $(E_{h})_{h\geq 1}$ holds
_asymptotically almost surely_ , or _a.a.s._ for short, if
$\mathbb{P}(E_{h})\to 1$ as $h\to\infty$. For real numbers $a,b,c$ with $c>0$,
we write $a=b\pm c$ to mean that $a\in[b-c,b+c]$.

Our main result can now be stated as follows:

######  Theorem 7.

Fix a positive integer $d$ and a real number $\epsilon\in(0,1)$. For each
positive integer $h$, let $2\leq M=M(h)=o(h/{\log h})$, set
$r^{*}=r^{*}(h)\coloneqq\sqrt{d}/{2h}$, and define two events
$\mathcal{E}_{h}$ and $\mathcal{F}_{h}$ as follows. Consider the random
geometric graph sequence $\widehat{\mathcal{G}}(r,d)=(G_{n})_{n\geq 1}$. Let
$\mathcal{E}_{h}$ denote the event that each balanced $M$-tree $T$ of height
$h$ appears as a subgraph of $G_{|T|}$. Let $\mathcal{F}_{h}$ denote the event
that, for each balanced $M$-tree $T$ of height $h$, the graph $G_{|T|}$ does
not contain $T$ as a subgraph. Then, the following two statements hold.

  1. $(\mathrm{i})$

If $r\leq(1-\epsilon)r^{*}$, then $\mathcal{F}_{h}$ holds a.a.s.

  2. $(\mathrm{ii})$

If $r\geq(1+\epsilon)r^{*}$, then $\mathcal{E}_{h}$ holds a.a.s.

Note that Theorem 7 is stronger than determining the sharp threshold of one
single balanced $T$-tree: indeed, our events $\mathcal{E}_{h}$ and
$\mathcal{F}_{h}$ consider all balanced $M$-trees of height $h$
simultaneously.

In the remainder of this section we prove Theorem 7. The proof of
$(\mathrm{i})$ is fairly simple, and most of the work will be devoted to
proving $(\mathrm{ii})$. For this, we are going to provide an algorithm which,
under a mild assumption on the distribution of the points finds a copy of any
given balanced $M$-tree $T$ of height $h$ in $G_{|T|}$ in polynomial time. We
will later show that a.a.s. all sufficiently large graphs appearing in the
random geometric graph sequence satisfy this point-distribution property.
Before describing the embedding algorithm (see Theorem 8 below), we introduce
some notation and definitions.

Fix $d\in\mathbb{N}$ and $\epsilon\in(0,1)$. Given $h\in\mathbb{N}$, let
$r^{*}$ be defined as in Theorem 7. Here and below, we refer to balanced
$M$-trees of height $h$ simply as $M$-trees. All cubes
$q\subseteq\mathbb{R}^{d}$ considered throughout will be closed and axis-
parallel (that is, they can all be obtained by some homothety from
$[0,1]^{d}$). For a set $A\subseteq\mathbb{R}^{d}$, we denote by $\partial A$
the topological boundary of $A$. Given a set $\mathcal{W}$ of subsets of
$\mathbb{R}^{d}$, we denote
$\partial\mathcal{W}\coloneqq\bigcup_{A\in\mathcal{W}}\partial A$. For any
$x\in\mathbb{R}^{d}$ and $r>0$, we write $B_{x}(r)$ to denote the closed ball
of radius $r$ and center $x$, that is, the set of all $y\in\mathbb{R}^{d}$
such that $\lVert x-y\rVert\leq r$.

The embedding algorithm will be based on a certain tessellation of
$[0,1]^{d}$. Let $r\coloneqq(1+\epsilon)r^{*}$. Given integers $M\geq 2$ and
$s\in\\{2,\ldots,M\\}$, let $k_{s}$ be the smallest integer which
simultaneously satisfies that

$\sqrt{d}s^{1-k_{s}}\leq r$ (3.1)

and

$\sqrt{d}s^{-k_{s}}<\frac{\epsilon r^{*}}{8}.$ (3.2)

Note that $k_{s}=\Theta({\log h}/{\log s})=O(\log h)$ and that the sequence
$(k_{s})_{s=2}^{M}$ is non-increasing. Then, let $\mathcal{W}_{s}$ be the
tessellation of $[0,1]^{d}$ into $s^{k_{s}d}$ congruent closed axis-parallel
cubes. We remark that (3.1) ensures that, for every point
$x\in\mathbb{R}^{d}$, any cube of side length $s^{1-k_{s}}$ that contains $x$
is itself contained in $B_{x}(r)$. Moreover, (3.2) is imposed to ensure that
we can nicely approximate a ball of radius $r^{*}$ using cubes in
$\mathcal{W}_{s}$: more precisely, for the ball of radius
$(1+{3\epsilon}/{4})r^{*}$ centered at some point $x$, the cubes in
$\mathcal{W}_{s}$ intersecting $\partial B_{x}((1+{3\epsilon}/{4})r^{*})$ are
entirely contained in $B_{x}(r)\setminus B_{x}((1+{\epsilon}/{2})r^{*})$; see
Figure 2. Suppose now that $M$ and $h$ are such that $m^{\prime}\coloneqq
dk_{2}M\leq h$. Consider a sequence $(s_{i})_{i=1}^{h}$ with
$s_{i}\in\\{2,\ldots,M\\}$ for every $i\in\\{1,\ldots,h\\}$, and the balanced
tree $T$ over this sequence. By the pigeonhole principle, there is an integer
in $\\{2,\ldots,M\\}$ appearing at least $dk_{2}$ times among
$(s_{i})_{i=1}^{m^{\prime}}$. Let $s(T)$ denote one such integer.

Our tree embedding algorithm is encoded into (the proof of) the following
theorem:

######  Theorem 8.

For each positive integer $h$, let $2\leq M=M(h)=o(h/\log h)$. For every
positive integer $d$ and $\epsilon\in(0,1)$, there exists some
$h_{0}\in\mathbb{N}$ such that the following holds for all $h\geq h_{0}$:

Let $r^{*}\coloneqq\sqrt{d}/2h$. Let $(s_{i})_{i=1}^{h}$ be a sequence where
$s_{i}\in\\{2,\ldots,M\\}$, let $T$ be the balanced tree over the sequence
$(s_{i})_{i=1}^{h}$, and let $s\coloneqq s(T)$. Let
$\mathcal{X}\subseteq[0,1]^{d}\setminus\partial\mathcal{W}_{s}$ be a set of
$|T|$ points such that each $q\in\mathcal{W}_{s}$ contains
$s^{-k_{s}d}|T|\pm|T|^{2/3}$ points. Then,
$G(\mathcal{X},(1+\epsilon)r^{*},d)$ contains a copy of $T$.

######  Remark 9.

The boundary condition
$\mathcal{X}\subseteq[0,1]^{d}\setminus\partial\mathcal{W}_{s}$ is a minor
technical restriction clearly satisfied by many point processes such as the
Poisson point process and only needed as an artifact of the proof.

###### Proof of Theorem 8.

First, we note that, by adjusting the value of $h_{0}$, the parameter $s$ in
the statement is well defined. Indeed, since $k_{2}=O(\log h)$ and $M=o(h/\log
h)$, it follows that $m^{\prime}=o(h)$ and, in particular, $s_{m^{\prime}}$ is
defined for all sufficiently large $h$. Specifically, we assume that $h_{0}$
is sufficiently large so that for all $h\geq h_{0}$ we have

$m^{\prime}\leq\epsilon h/20.$ (3.3)

Moreover, letting $k\coloneqq k_{s}$, we also pick $h_{0}$ sufficiently large
so that the following hold for all $h\geq h_{0}$:

$\displaystyle k$ $\displaystyle\leq\epsilon h/12,$ (3.4) $\displaystyle
2^{-\epsilon h/5}$ $\displaystyle\leq s^{-kd}/2,$ (3.5)
$\displaystyle|T|^{2/3}$ $\displaystyle<s^{-2kd}|T|/2.$ (3.6)

Let $r\coloneqq(1+\epsilon)r^{*}$, and consider the tessellation
$\mathcal{W}_{s}$ described before the statement of Theorem 8. For each
$\ell\in\\{0,\ldots,k\\}$, let $\mathcal{S}_{\ell}$ be the tessellation of
$[0,1]^{d}$ into $s^{\ell d}$ congruent closed axis-parallel cubes obtained by
combining the cubes of $\mathcal{W}_{s}$ into groups of size $s^{(k-\ell)d}$.
In particular, $\mathcal{S}_{0}=\\{[0,1]^{d}\\}$ and
$\mathcal{S}_{k}=\mathcal{W}_{s}$. For a cube $q\subseteq[0,1]^{d}$, we denote
its center by $c(q)$. Moreover, for every $i,j\in\\{0,\ldots,k\\}$ with $i<j$
and any cube $q\in\mathcal{S}_{i}$, let $\sigma_{j}(q)$ denote the set of
$s^{d}$ subcubes of $q$ in $\mathcal{S}_{j}$ that form the axis-parallel cube
of side length $s^{1-j}$ and center $c(q)$. In particular, $\sigma_{i+1}(q)$
is a tessellation of $q$ into $s^{d}$ subcubes in $\mathcal{S}_{i+1}$, and for
each $j\in\\{i+2,\ldots,k\\}$, the set $\sigma_{j}(q)$ is obtained from
$\sigma_{j-1}(q)$ by homothety with center $c(q)$ and ratio $1/s$. For
example, Figure 1 (a) illustrates $\mathcal{S}_{1}$, $\mathcal{S}_{2}$ and
$\mathcal{S}_{3}$ when $s=3$ and $d=2$, and Figure 1 (b) depicts the set of
cubes $\sigma_{2}(q)$ for $q=[0,1]^{2}$. Note that we sometimes abuse notation
and identify $\sigma_{j}(q)$ with its geometric realization; in particular, we
identify $\bigcup_{p\in\sigma_{j}(q)}p$ with $\sigma_{j}(q)$ itself.

(a)$q=[0,1]^{2}$(b)$\sigma_{2}(q)\subseteq\mathcal{S}_{2}$

Figure 1. Figure (a) shows a tessellation of $[0,1]^{2}$ into $3^{2\cdot 3}$
subcubes. Figure (b) shows an example of $\sigma_{2}$ applied to
$q=[0,1]^{2}$.

Let $G\coloneqq G(\mathcal{X},r,d)$. Let us give a general description of the
algorithm that we propose for finding a copy of $T$ in $G$. Let $v_{0}$ be the
root of $T$, and consider the partition of the vertices of $T$ into layers
$V_{0},V_{1},\ldots,V_{h}$. We embed the layers of $T$ into $G$ one at a time,
starting from the root. Our algorithm has three main parts which we call
_subroutines_. The first subroutine lasts for $m^{\prime}+1$ steps. It embeds
the layers $V_{0},\ldots,V_{m^{\prime}-1}$ of $T$ into an arbitrary cube
$q_{0}\in\sigma_{k}([0,1]^{d})$, and then all vertices in $V_{m^{\prime}}$ are
evenly distributed among the $s^{d}$ cubes in $\sigma_{k}([0,1]^{d})$. The
second subroutine is used to distribute the vertices in the next roughly
$(1-\epsilon)h$ layers as evenly as possible in $[0,1]^{d}$; more precisely,
for some $m\leq(1-\epsilon/4)h$ (see Claim 1 below), we manage to ensure that
every cube $q\in\mathcal{S}_{k}$ contains exactly the same number of vertices
of $V_{m^{\prime}+m}$. Once this point is reached, in the third subroutine,
the remaining layers are embedded into $G$ by using Corollary 5. In
particular, we associate a vertex $v\in V_{m^{\prime}+m}$ to each of the
vertices of $G$ that are still not covered by $T$ in such a way that $v$ and
the vertices associated with $v$ form a clique whose size is the same for
every $v\in V_{m^{\prime}+m}$. Note that this is sufficient to guarantee that
the embedding can be extended.

Throughout, we refer to the embedding of one of the layers of $T$ as a _step_
of the algorithm (for simplicity, we assume that $V_{0}$ is embedded at the
$0$-th step). For each $i\in\\{0,\ldots,m^{\prime}+m\\}$, at the end of the
$i$-th step, we call a vertex of $G$ into which a vertex on layer $V_{i}$ has
been embedded _active_. Moreover, we refer to the vertices of $G$ into which
no vertex of $T$ has been embedded as _unseen_. For simplicity of notation,
once a vertex of $T$ has been embedded into $G$, we often interchangeably use
the same notation to refer to either of the two vertices. We note here that,
since $m\leq(1-\epsilon/4)h$, it follows that the total number of vertices
embedded during the first two subroutines is

$\sum_{i=0}^{m^{\prime}+m}\prod_{j=1}^{i}s_{j}\leq
2^{-(h-m-m^{\prime})}|T|\leq 2^{-\epsilon h/5}|T|\leq\frac{|T|}{2s^{kd}}.$
(3.7)

(Here, the first inequality follows from the fact that $s_{i}\geq 2$ for all
$i\in\\{1,\ldots,h\\}$, the second inequality follows by combining the upper
bound on $m$ given by Claim 1 below with (3.3), and the third follows by
(3.5).) Therefore, by (3.6) and the condition on the point distribution in the
statement, there are sufficiently many vertices in each $q\in\mathcal{S}_{k}$
at our disposal throughout the first two subroutines, which guarantees that
the choices we make below can indeed be carried out.

The procedure that we follow to embed the layers of $T$ into the cubes of
$\mathcal{S}_{k}$ throughout the first subroutine is very simple. We fix an
arbitrary cube $q_{0}\in\sigma_{k}([0,1]^{d})$. Then, for each
$i\in\\{0,\ldots,m^{\prime}-1\\}$, we arbitrarily embed all vertices of
$V_{i}$ into $q_{0}$. Finally, the vertices of $V_{m^{\prime}}$ are split
(arbitrarily) into $s^{d}$ sets of the same size, and each of these sets is
embedded entirely into a different cube $q\in\sigma_{k}([0,1]^{d})$. Note that
this is possible since $s^{d}$ divides $\prod_{i=1}^{m^{\prime}}s_{i}$ by the
definition of $s$, and since the diameter of $\sigma_{k}([0,1]^{d})$ is at
most $r$ by (3.1).

Let us now describe the algorithm that we use to embed the layers of $T$ into
the cubes of $\mathcal{S}_{k}$ throughout the second subroutine. The $m$ steps
of the second subroutine are grouped into $k-1$ different blocks. For each
$\ell\in\\{1,\ldots,k-1\\}$, we proceed iteratively as follows: Suppose that,
at the beginning of the $\ell$-th block, the algorithm has reached a
configuration in which every cube $q\in\mathcal{S}_{\ell-1}$ contains the same
number of active vertices, and that these are equally distributed among all
subcubes in $\sigma_{k}(q)$ (note that this is verified in the case $\ell=1$).
Then, for each $q\in\mathcal{S}_{\ell-1}$, we proceed to distributing the
descendants of the currently active vertices in a way that we embed them at
non-decreasing distances from $\sigma_{k}(q)$ as described in the sequel.

Iteration: Define $\phi_{\ell}\colon\sigma_{k}(q)\to\sigma_{\ell}(q)$ as the
bijection obtained by homothety with center $c(q)$ and ratio $s^{k-\ell}$.
Note that $\phi_{\ell}$ depends on the cube $q$, which is fixed in our
argument. To each cube $p\in\sigma_{k}(q)$ we associate a sequence of (not
necessarily distinct) cubes $(p_{1},\ldots,p_{t})$ in $\mathcal{S}_{k}$, for
some appropriately chosen $t$ which does not depend on $p$, which satisfies
that

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

$p_{1}=p$;

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

$p_{t}\in\sigma_{k}(\phi_{\ell}(p))$, and

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

for all $i\in\\{1,\ldots,t-1\\}$ we have $\lVert
c(p_{i+1})-c(p_{i})\rVert\leq\left(1+7\epsilon/8\right)r^{*}$.

Note that $(\mathrm{P}3)$ together with the triangle inequality and (3.2)
ensures that, for every $i\in\\{1,\ldots,t-1\\}$ and every choice of points
$x\in p_{i}$ and $y\in p_{i+1}$, we have

$\lVert x-y\rVert\leq\lVert x-c(p_{i})\rVert+\lVert
c(p_{i})-c(p_{i+1})\rVert+\lVert
c(p_{i+1})-y\rVert\leq\frac{\epsilon}{16}r^{*}+\left(1+\frac{7\epsilon}{8}\right)r^{*}+\frac{\epsilon}{16}r^{*}=r.$
(3.8)

Hence, if at some point there is an active vertex $v$ in $p_{i}$, it is
possible to embed all its children in $p_{i+1}$.

Let us prove that the sequences of cubes described above can indeed be
constructed. We will show the construction when starting from a cube
$p\in\sigma_{k}(q)$ whose center is at a maximum distance from $c(q)$ among
all cubes in $\sigma_{k}(q)$ (note that, in this case, $p$ must contain a
corner of the larger cube $\sigma_{k}(q)$). Observe that this choice of $p$
also maximizes the distance between $c(p)$ and $c(\phi_{\ell}(p))$. For every
other $p^{\prime}\in\sigma_{k}(q)$, the construction is the same except that
consecutive cubes are chosen at a smaller distance from each other (or even
coincide in some cases).

Fix $p\in\sigma_{k}(q)$ as above. We construct the sequence of cubes
$(p_{1},\ldots,p_{t})$ in $\mathcal{S}_{k}$ satisfying the desired properties
$(\mathrm{P}1)$–$(\mathrm{P}3)$. We begin by setting $p_{1}\coloneqq p$. For
each $i\geq 1$, while $\lVert
c(p_{i})-c(\phi_{\ell}(p))\rVert>(1+7\epsilon/8)r^{*}$, we choose a cube
$p_{i+1}\in\mathcal{S}_{k}$ such that

$\lVert c(p_{i+1})-c(\phi_{\ell}(p))\rVert\leq\lVert
c(p_{i})-c(\phi_{\ell}(p))\rVert-\left(1+\frac{5\epsilon}{8}\right)r^{*}$
(3.9)

and

$\lVert c(p_{i+1})-c(p_{i})\rVert\leq\left(1+\frac{7\epsilon}{8}\right)r^{*}.$
(3.10)

Finally, when we reach a point where $\lVert
c(p_{i})-c(\phi_{\ell}(p))\rVert\leq(1+7\epsilon/8)r^{*}$, we set $t\coloneqq
i+1$ and choose $p_{t}$ as a cube in $\sigma_{k}(\phi_{\ell}(p))$ at smallest
distance to $c(p_{i})$, ties being broken arbitrarily. Note that (3.8) holds
for $i=t-1$ and this choice of $p_{t}$. It remains to prove that a choice as
prescribed by (3.9) and (3.10) can indeed be carried out.

$c(p_{i})$$w$$c(\phi_{\ell}(p))$$r^{*}$

Figure 2. A one-step transition from $p_{i}$ to $p_{i+1}$ in two dimensions.
The four circles in the figure are all centered at $c(p_{i})$ and have radii
$r^{*}$, $(1+{\epsilon}/{2})r^{*}$, $(1+{3\epsilon}/{4})r^{*}$, and $r$. Note
that $p_{i+1}$ is the square containing $w$; its center as well as the
boundary of the square $p_{i}$ are not presented for reasons of clarity of the
figure.

Assume we have already defined $p_{i}$ so that it satisfies $\lVert
c(p_{i})-c(\phi_{\ell}(p))\rVert>(1+7\epsilon/8)r^{*}$. Then, choose
$p_{i+1}\in\mathcal{S}_{k}$ to be a cube containing the point $w$ on the
segment $c(p_{i})c(\phi_{\ell}(p))$ at distance exactly
$(1+{3\epsilon}/{4})r^{*}$ from $c(p_{i})$ (if more than one such cube exists,
we choose one arbitrarily); see Figure 2. Then, the triangle inequality and
(3.2) imply that

$\displaystyle\lVert c(p_{i+1})-c(\phi_{\ell}(p))\rVert$
$\displaystyle\leq\lVert w-c(\phi_{\ell}(p))\rVert+\lVert c(p_{i+1})-w\rVert$
$\displaystyle=\lVert c(p_{i})-c(\phi_{\ell}(p))\rVert-\lVert
c(p_{i})-w\rVert+\lVert c(p_{i+1})-w\rVert$ $\displaystyle\leq\lVert
c(p_{i})-c(\phi_{\ell}(p))\rVert-\left(1+\frac{3\epsilon}{4}\right)r^{*}+\frac{\epsilon}{16}r^{*}$
$\displaystyle\leq\lVert
c(p_{i})-c(\phi_{\ell}(p))\rVert-\left(1+\frac{5\epsilon}{8}\right)r^{*}$

and

$\displaystyle\lVert c(p_{i})-c(p_{i+1})\rVert\leq\lVert
c(p_{i})-w\rVert+\lVert
w-c(p_{i+1})\rVert\leq\left(1+\frac{3\epsilon}{4}\right)r^{*}+\frac{\epsilon}{16}r^{*}\leq\left(1+\frac{7\epsilon}{8}\right)r^{*},$

so (3.9) and (3.10) are verified.

00001,61,61,61,6$2,5,6$$2,5,6$$2,5,6$$2,5,6$3,43,43,43,44444444444445,65,65,65,65,65,65,65,65,65,65,65,666666666666666666666666666666666666666666666

Figure 3. A graphical representation of the principle we use to distribute the
vertices of $T$ for $(s,k)=(2,4)$ and in two dimensions. The figure shows the
steps in the range $\\{m^{\prime},\ldots,m^{\prime}+6\\}$ (note that squares
containing active vertices after step $m^{\prime}+i$ contain only the index
$i$ for reasons of space). Note that, for $\ell=1$, the big square with
thickened black boundary is the image of the small square $p$ with thickened
black boundary by $\phi_{1}$, and the same holds for the corresponding red
squares. Moreover, $c([0,1]^{2})$, $c(p)$ and $c(\phi_{1}(p))$ are collinear
and $\lVert c(p)-c(\phi_{1}(p))\rVert\leq\lVert
c([0,1]^{2})-c(\phi_{1}(p))\rVert=\sqrt{2}(1-s^{-1})/2$.

Now, once the sequence $(p_{1},\ldots,p_{t})$ is constructed, we can describe
the distribution of the vertices of the tree in each step of the algorithm.
Recall that, at the beginning of the $\ell$-th block, $p_{1}$ contains some
active vertices. Then, for the next $t-1$ steps, we simply embed the children
of all currently active vertices in $p_{i}$ into $p_{i+1}$ arbitrarily (which
is possible thanks to (3.7) and (3.8)). Lastly, in one more step of the
algorithm, we distribute the children of all currently active vertices in
$p_{t}$ equally among the $s^{d}$ subcubes of $\sigma_{k}(\phi_{\ell}(p))$;
note that this is possible since $s^{kd}$ divides
$\prod_{i=1}^{m^{\prime}}s_{i}$ (by the definition of $s$ and since $k\leq
k_{2}$), which itself divides the number of vertices in each of the layers
$V_{i}$ for $i\geq m^{\prime}$. A schematic representation of the first steps
of this process is shown in Figure 3. Finally, if $\ell=k-1$, we terminate the
subroutine, and otherwise we increment the value of $\ell$ by $1$ and proceed
to the next block of the second subroutine.

Following the description of the algorithm, we must prove that it reaches a
desired configuration in a suitable number of steps. We begin by proving a
bound on the number of steps of the process we have described, without regard
to whether it can actually be carried out.

######  Claim 1.

The second subroutine runs for at most $(1-{\epsilon}/4)h$ steps.

###### Proof.

For every $\ell\in\\{1,\ldots,k-1\\}$, we have that

$\lVert c(p)-c(\phi_{\ell}(p))\rVert\leq\lVert
c(q)-c(\phi_{\ell}(p))\rVert\leq\frac{\sqrt{d}(s^{1-\ell}-s^{-\ell})}{2},$
(3.11)

where the first inequality holds since $c(p)$ belongs to the segment
$c(q)c(\phi_{\ell}(p))$ (recall that $\phi_{\ell}(p)$ is obtained from $p$ by
homothety with center $c(q)$ and ratio $s^{k-\ell}>1$), and the second
inequality comes from the fact that the farthest cubes from $c(q)$ in
$\sigma_{\ell}(q)$ are the ones containing a corner of $q$. Hence, by (3.9),
the total number of steps performed by the second subroutine is at most

$\sum_{\ell=1}^{k-1}\left(\frac{\sqrt{d}(s^{1-\ell}-s^{-\ell})/2}{(1+5\epsilon/8)r^{*}}+1\right)\leq
k+\frac{\sqrt{d}/2}{(1+5\epsilon/8)r^{*}}\leq
k+\left(1-\frac{\epsilon}{3}\right)h\leq\left(1-\frac{\epsilon}{4}\right)h,$

where in the second inequality we used that $\epsilon<1$, and in the last we
applied (3.4). ∎

Now, recall that $m^{\prime}+m$ denotes the index of the last step carried out
by the second subroutine. As mentioned before describing the precise
algorithm, (3.6), (3.7) and the condition on the point distribution in the
statement guarantee that the process must succeed. That is, we have an
embedding of the layers $V_{0},\ldots,V_{m^{\prime}+m}$ of $T$ into $G$ and,
moreover, each $q\in\mathcal{S}_{k}$ contains the same number of vertices of
$V_{m^{\prime}+m}$.

Next, we make sure that the remaining layers can also be embedded into $G$.
For each cube $q\in\mathcal{S}_{k}$, let us denote by $\hat{q}$ the _enlarged
copy of $q$_ obtained from $q$ by intersecting the image of $q$ under
homothety with center $c(q)$ and ratio $3$ with $[0,1]^{d}$ (that is,
$\hat{q}$ is the union of all the cubes in $\mathcal{S}_{k}$ that share at
least one corner with $q$). We show that all remaining layers of the tree can
be embedded so that the following property holds: for every vertex $v\in V(G)$
that is active at the end of the second subroutine, if $v$ lies in a cube
$q\in\mathcal{S}_{k}$, then all descendants of $v$ lie in $\hat{q}$. Observe
that, by the definition of $\hat{q}$ and (3.2), for every
$q\in\mathcal{S}_{k}$ we have that

$\mathrm{diam}(\hat{q})\leq 3\sqrt{d}s^{-k}\leq\epsilon r^{*}\leq r,$

so the vertices which lie in the enlarged copy of each cube in
$\mathcal{S}_{k}$ span a clique in $G$. Therefore, it suffices to prove that
all unseen vertices can be partitioned into $|V_{m^{\prime}+m}|$ sets of equal
sizes in such a way that each of the resulting sets is contained in a single
$\hat{q}$ and can be assigned to one of the vertices in $V_{m^{\prime}+m}$.

We achieve the above by considering an auxiliary bipartite graph $\Gamma$ with
vertex partition $(\mathcal{S}_{k},\widehat{V})$, where $\widehat{V}$ is the
set of unseen vertices at the end of step $m^{\prime}+m$. We connect
$q\in\mathcal{S}_{k}$ and $v\in\widehat{V}$ by an edge whenever $v\in\hat{q}$.
Note that $|\widehat{V}|=\sum_{i=m^{\prime}+m+1}^{h}\prod_{j=1}^{i}s_{j}$, so
in particular $|\mathcal{S}_{k}|=s^{kd}$ divides $|\widehat{V}|$. For a
positive integer $a$, recall the definition of an $a$-star with center $v$, or
with center in a set $V$, from Section 2.

######  Claim 2.

Let $a\coloneqq|\widehat{V}|/|\mathcal{S}_{k}|$. Then, the vertices of
$\Gamma$ may be partitioned into $s^{kd}$ vertex-disjoint $a$-stars with
centers in $\mathcal{S}_{k}$.

###### Proof.

Let $n\coloneqq|T|$ and note that, for each non-empty set of cubes
$S\subseteq\mathcal{S}_{k}$ with $S\neq\mathcal{S}_{k}$, the set
$\mathcal{A}_{S}\coloneqq\bigcup_{q\in S}\hat{q}$ contains at least one cube
in $\mathcal{S}_{k}\setminus S$. Therefore, by the point-distribution property
from the statement, (3.6) and (3.7), we have that

$\displaystyle|\mathcal{A}_{S}\cap\widehat{V}|\geq(|S|+1)(s^{-kd}n-n^{2/3})-|V(G)\setminus\widehat{V}|\geq|S|s^{-kd}n+s^{-kd}n-s^{kd}n^{2/3}-s^{-kd}n/2\geq
a|S|.$

Thus, Corollary 5 implies that $\Gamma$ contains the desired family of
disjoint $a$-stars. ∎

As a direct consequence of Claim 2, one can partition the vertices in
$\widehat{V}$ into $s^{kd}$ disjoint sets, each spanning a clique in $G$ and
contained in a different enlarged cube. Now, each of these sets can be
arbitrarily partitioned into $|V_{m^{\prime}+m}|/s^{kd}$ subsets of equal
sizes, and each of these smaller sets can be assigned to a distinct vertex $v$
in $V_{m^{\prime}+m}$. Then, for every $v\in V_{m^{\prime}+m}$, the
descendants of $v$ can be embedded greedily into the complete graph associated
to it, and the embedding of $T$ into $G$ is completed. ∎

######  Remark 10.

By retracing the proof of Theorem 8, and taking into account Remark 6, one can
readily verify that our approach results in a polynomial time algorithm to
find a copy of an $M$-tree in the corresponding geometric graph.

With this, we can complete the proof of Theorem 7.

###### Proof of Theorem 7.

Suppose that $r\leq(1-\epsilon)r^{*}$. First, fix a tree $T$ of height
$h=O(\log|T|)$ (which holds for every $M$-tree). Set $G=\mathcal{G}(|T|,r,d)$.
To show that $\mathbb{P}[T\subseteq G]=o(1)$, we first claim that a.a.s. there
are vertices $u,v\in V(G)$ at Euclidean distance $(1-o(1))\sqrt{d}$ from each
other. Note that, since the graph sequence $(G_{n})_{n\geq 1}$ is increasing
with respect to inclusion, it is sufficient to show the previous statement for
the smallest graph hosting an $M$-tree of height $h$, that is,
$G_{2^{h+1}-1}$.

To this end, consider the cubes $c_{0},c_{1}\subseteq[0,1]^{d}$ of side length
$1/h$ containing the corners $\\{0\\}^{d}$ and $\\{1\\}^{d}$, respectively.
Then, we have that $\operatorname{dist}(c_{0},c_{1})=(1-o(1))\sqrt{d}$ and,
moreover, $|c_{0}\cap V(G_{2^{h+1}-1})|$ and $|c_{1}\cap V(G_{2^{h+1}-1})|$
both follow a binomial distribution with parameters $2^{h+1}-1$ and $1/h^{d}$.
Thus, the probability that $c_{0}$ or $c_{1}$ do not contain any vertices is
at most

$2(1-1/h^{d})^{2^{h+1}-1}\leq 2\mathrm{e}^{-2^{h}/h^{d}}.$

Now, condition on the event that $c_{0}$ and $c_{1}$ each contain at least one
vertex and suppose that $G$ admits $T$ as a spanning tree. Since $T$ has
diameter $2h$, $u$ and $v$ must be at distance at most $2h$ in $G$. Thus, by
the triangle inequality, the Euclidean distance between them must be at most
$2hr$, so we must have
$2hr\geq\operatorname{dist}(c_{0},c_{1})=(1-o(1))\sqrt{d}$, which is a
contradiction with our choice of $r$. Hence, with probability at least
$1-2\mathrm{e}^{-2^{h}/h^{d}}$, there is no $M$-tree $T$ of height $h$ such
that $T\subseteq\mathcal{G}(|T|,r,d)$. This concludes the proof of
$(\mathrm{i})$.

Next, suppose that $r\geq(1+\epsilon)r^{*}$. Using that $T\subseteq G$ is an
increasing property, it suffices to prove the result for
$r=(1+\epsilon)r^{*}$. In fact, it suffices to verify that a.a.s. the
conditions of the statement of Theorem 8 hold for every sufficiently large
graph in the random geometric graph sequence. The next claim asserts that the
point-distribution property from Theorem 8 holds a.a.s.

######  Claim 3.

A.a.s. for every $s\in\\{2,\ldots,M\\}$, every cube $q\in\mathcal{W}_{s}$ and
every $n\geq 2^{h}$, $q$ contains $s^{-k_{s}d}n\pm n^{2/3}$ vertices of
$\mathcal{G}(n,r,d)$.

###### Proof.

Fix $s$ and $n$ as above and consider a fixed cube $q\in\mathcal{W}_{s}$. Let
$X$ denote the number of vertices of $\mathcal{G}(n,r,d)$ inside $q$. Then,
$X$ is a binomial random variable with parameters $n$ and $p=s^{-k_{s}d}$.
Therefore, $\mathbb{E}[X]=s^{-k_{s}d}n$ and, by Lemma 3,

$\displaystyle\mathbb{P}[X\neq s^{-k_{s}d}n\pm n^{2/3}]$
$\displaystyle=\mathbb{P}\left[|X-\mathbb{E}[X]|>\frac{n^{2/3}}{s^{-k_{s}d}n}s^{-k_{s}d}n\right]$
$\displaystyle\leq
2\exp\left(-\left(\frac{n^{2/3}}{s^{-k_{s}d}n}\right)^{2}\frac{s^{-k_{s}d}n}{3}\right)\leq
2\exp\left(-\frac{n^{1/3}}{3}\right).$

A union bound over the $M-1=o(h)$ possible values of $s$, the
$s^{k_{s}d}=O(r^{-2})=O(h^{2d})$ cubes in $\mathcal{W}_{s}$ and all $n\geq
2^{h}$ shows that the event of the lemma holds with probability at least

$1-O\left(\sum_{n=2^{h}}^{\infty}2h^{2d+1}\exp\left(-\frac{n^{1/3}}{3}\right)\right)=1-o(1),$

as desired. ∎

Since with probability $1$ none of the vertices of any of the graphs in the
random geometric graph sequence is on the boundary of any cube
$q\in\mathcal{W}_{s}$, the proof of Theorem 7 is completed. ∎

##  4\. Extensions and concluding remarks

###  4.1. Other metric spaces

As a first remark, we note that all our results can be extended to other
$\ell_{p}$ norms where $1\leq p\leq\infty$. Indeed, the notion of random
geometric graph can be adapted to each norm simply by replacing the Euclidean
distance in the definition with the distance in the $\ell_{p}$ norm. Then, by
retracing the proof of our main theorem, the sharp threshold becomes
$d^{1/p}/2h$.

###  4.2. Threshold width

As mentioned in the introduction, Goel, Rai and Krishnamachari [13] gave upper
bounds on the threshold width for any monotone increasing property in
$\mathcal{G}(n,r,d)$. Let us state their result. For any positive integer $n$,
real number $x\in[0,1]$, and increasing property $\mathcal{P}$, let

$r_{\mathcal{P}}(n,x)\coloneqq\inf\\{r\geq
0:\mathbb{P}[\mathcal{G}(n,r,d)\in\mathcal{P}]\geq x\\}.$

For each $\epsilon\in(0,1/2)$, define the _$\epsilon$ -threshold width_ of
property $\mathcal{P}$ as $\delta_{\mathcal{P}}(n,\epsilon)\coloneqq
r_{\mathcal{P}}(n,1-\epsilon)-r_{\mathcal{P}}(n,\epsilon)$. Goel, Rai and
Krishnamachari [13] showed that, for any monotone increasing property
$\mathcal{P}$, for $d=1$ we have
$\delta_{\mathcal{P}}(n,\epsilon)=O(\sqrt{\log\epsilon^{-1}/n})$ (in fact,
this bound is also sharp), for $d=2$ we have
$\delta_{\mathcal{P}}(n,\epsilon)=O(\log^{3/4}n/\sqrt{n})$, and for $d\geq 3$
we have $\delta_{\mathcal{P}}(n,\epsilon)=O(\log^{1/d}n/n^{1/d})$. (Some
references, such as the paper by Goel, Rai and Krishnamachari [13], refer to
the fact that $\delta_{\mathcal{P}}(n,\epsilon)=o(1)$ as property
$\mathcal{P}$ having a sharp threshold. We note, however, that this is
different from the notion of a sharp threshold we have considered throughout.)

The threshold width for the property of containing a complete balanced $s$-ary
tree that can be derived from our methods is far from the upper bound of Goel,
Rai and Krishnamachari [13]. In fact, by retracing our proof, it only follows
that the width is $O(\log\log h/(h\log h))$. Since the bounds given by Goel,
Rai and Krishnamachari are tighter, it is natural to wonder about the exact
width of the threshold window. The following problem addresses this question:

######  Problem 11.

Determine the threshold width for the property that $\mathcal{G}(n,r,d)$
contains a spanning balanced $s$-ary tree.

###  4.3. Balanced $s$-ary trees of all orders

In the introduction we defined a (complete) balanced $s$-ary tree to be a tree
with layers $V_{0},\ldots,V_{h}$ where all vertices in layers
$V_{0},\ldots,V_{h-1}$ have exactly $s$ children. One weakness of this
definition is the fact that these trees are only defined for certain orders:
indeed, any such tree must have $\sum_{i=0}^{h}s^{i}$ vertices. One may
consider a more general definition which works for all possible orders as
follows. Given any positive integers $n$ and $s$, let $h=h(n)$ be the unique
positive integer such that

$\sum_{i=0}^{h-1}s^{i}<n\leq\sum_{i=0}^{h}s^{i}.$ (4.1)

A _pre-balanced $s$-ary tree_ on $n$ vertices is then a tree with layers
$V_{0},\ldots,V_{h}$ such that all vertices in layers $V_{0},\ldots,V_{h-2}$
have exactly $s$ children and every vertex in layer $V_{h-1}$ has at most $s$
children. Note that, when (4.1) is not satisfied with equality in the upper
bound, there may be multiple non-isomorphic pre-balanced $s$-ary trees.

One would expect that our results extend to this more general definition of
pre-balanced trees. This, however, is not immediate. Intuitively, the reason
for this is that pre-balanced $s$-ary trees can be quite “unbalanced” in the
following sense: For any $s$-ary tree, let us define the _weight_ of a vertex
as the number of descendants it has. Then, in complete balanced $s$-ary trees,
all vertices in the same layer have the same weight. In pre-balanced $s$-ary
trees, however, the weights of vertices in the same layer may differ by a
factor of $s$. (Indeed, consider the pre-balanced $s$-ary tree obtained by
taking $s$ complete balanced $s$-ary trees, with $s-1$ of height $h-1$ and one
of height $h-2$, and having the roots of each of these be the children of a
new root).

Our proof extends directly to pre-balanced $s$-ary trees of height $h$ where,
for some integer $m^{\prime\prime}=m^{\prime\prime}(h)=h-o(h)$, all vertices
in $V_{m^{\prime\prime}}$ have the same weight. On the other extreme, consider
a pre-balanced $s$-ary tree that has vertices of arbitrarily different weights
in the same layer but satisfies the following property for some integer
$\widehat{m}=\widehat{m}(h)=o(h)$: for every vertex $v\in V_{\widehat{m}}$, if
we consider the tree induced by $v$ together with all of its descendants, then
all vertices in the same layer of this subtree have the same weight (this case
contains the example of $s$ complete balanced trees with an added common root
mentioned above). In this case, we can greedily embed all vertices in layers
$V_{0},\ldots,V_{\widehat{m}}$ into a square in $\sigma_{k}([0,1]^{d})$, and
then apply the algorithm to each of the $|V_{\widehat{m}}|$ trees rooted at
the vertices in layer $V_{\widehat{m}}$ simultaneously. However, if the
conditions described above are not met (e.g., if all vertices in the first
$\epsilon h$ layers have the same weight but then weights become very
different), it is unclear how to extend our proof.

Despite this, we still believe that the thresholds should be the same, and
even that all pre-balanced $s$-ary trees of height $h$ on $n$ vertices should
appear essentially simultaneously. We therefore propose the following
universality conjecture:

######  Conjecture 12.

Fix positive integers $s\geq 2$ and $d\geq 1$. For a positive integer $n$, set
$h$ to be the unique integer satisfying (4.1). Then,
$r^{*}\coloneqq\sqrt{d}/2h$ is the sharp threshold for the event that
$\mathcal{G}(n,r,d)$ contains a copy of every pre-balanced $s$-ary tree of
height $h$ on $n$ vertices.

We note that the discussion in this section can also be extended to balanced
trees over a sequence $(s_{i})_{i\geq 1}$, where the extension of the
definition is analogous to the extension for $s$-ary trees.

###  4.4. Bounded-degree trees

As mentioned in the introduction, a class of trees of particular interest is
the class of bounded-degree trees. This class contains some of the trees we
have considered in this paper. For instance, let $T^{s}_{h}$ be the balanced
tree of height $h$ over the sequence $(s_{i})_{i=1}^{h}$ where $s_{1}=s$ and
$s_{i}=s-1$ for all $i\in\\{2,\ldots,h\\}$. The following is an immediate
consequence of Theorem 2.

######  Corollary 13.

Let $d$ and $s\geq 3$ be fixed integers. Let $h$ be an integer and $n$ be the
number of vertices of $T_{h}^{s}$. The sharp threshold for the appearance of
$T_{h}^{s}$ as a subgraph of $\mathcal{G}(n,r,d)$ is

$\frac{\sqrt{d}}{2h}\sim\frac{\sqrt{d}\log(s-1)}{2\log n}.$

We suspect that, for each fixed value of $s$, among all trees with degrees
bounded by $s$, the tree $T_{h}^{s}$ is the hardest to embed in the sense that
it has the highest threshold. Thus, we propose the following universality
conjecture:

######  Conjecture 14.

Fix positive integers $d$ and $s\geq 3$. For any $\epsilon>0$, if

$r\geq(1+\epsilon)\frac{\sqrt{d}\log(s-1)}{2\log n},$

then a.a.s. $\mathcal{G}(n,r,d)$ contains _every_ spanning tree of maximum
degree at most $s$.

As discussed in the introduction, though, we know that there exist trees of
bounded degree whose thresholds are far smaller than those discussed here. It
would be interesting to understand which properties of a tree can be used to
determine their threshold. We note that, while the diameter has resulted to be
a good estimator throughout this paper, this is not the correct parameter in
general. Indeed, consider a tree on $2n$ vertices defined as follows: take a
balanced binary tree on $n$ vertices, and add a path on $n$ vertices appended
to the root. The resulting tree has linear diameter, but it is not hard to see
that the threshold for its appearance is $\Omega(1/\log n)$. As a step towards
the general problem of determining the threshold of each family of bounded-
degree trees, we propose the following problem:

######  Problem 15.

Given any tree $T$, let $\mathrm{diam}(T)$ denote the diameter of $T$. Give
general sufficient conditions which guarantee that, for a sequence
$(T_{i})_{i\geq 1}$ of trees, the sharp threshold for their appearance in
$\mathcal{G}(n,r,d)$ is $\sqrt{d}/\mathrm{diam}(T_{i})$.

## References

  * Akyildiz, Su, Sankarasubramaniam and Cayirci [2002] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, Wireless sensor networks: a survey. _Comput. Netw._ 38.4 (2002), 393––422, doi: 10.1016/S1389-1286(01)00302-4.
  * Balogh, Bollobás, Krivelevich, Müller and Walters [2011] J. Balogh, B. Bollobás, M. Krivelevich, T. Müller and M. Walters, Hamilton cycles in random geometric graphs. _Ann. Appl. Probab._ 21 (2011), 1053–1072, doi: 10.1214/10-AAP718.
  * Bharathidasan and Ponduru [2002] A. Bharathidasan and V. A. S. Ponduru, _Sensor networks: An overview_. Tech. rep., Dept. of Computer Science, University of California at Davis (2002).
  * Bradonjić and Perkins [2014] M. Bradonjić and W. Perkins, On sharp thresholds in random geometric graphs. _Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 17th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2014) and the 18th international workshop on randomization and computation (RANDOM 2014), Universitat Politècnica de Catalunya, Barcelona, Spain, September 4–6, 2014_ , 500–514, Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik, ISBN 978-3-939897-74-3 (2014), doi: 10.4230/LIPIcs.APPROX-RANDOM.2014.500.
  * Chwa and Kim [1987] K.-Y. Chwa and T. Kim, An $O(n\log n\log\log n)$ parallel maximum matching algorithm for bipartite graphs. _Inf. Process. Lett._ 24.1 (1987), 15–17, doi: 10.1016/0020-0190(87)90193-1.
  * Cormen, Leiserson, Rivest and Stein [2022] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, _Introduction to algorithms_. MIT Press, Cambridge, MA, 4th ed. (2022), ISBN 978-0-262-04630-5.
  * Dettmann and Georgiou [2016] C. P. Dettmann and O. Georgiou, Random geometric graphs with general connection functions. _Phys. Rev. E_ 93.3 (2016), paper n. 032 313, doi: 10.1103/PhysRevE.93.032313.
  * Diestel [2017] R. Diestel, _Graph Theory_. Springer Publishing Company, Incorporated, 5th ed. (2017), ISBN 3662536218.
  * Díaz, Mitsche and Pérez [2007] J. Díaz, D. Mitsche and X. Pérez, Sharp Threshold for Hamiltonicity of Random Geometric Graphs. _SIAM J. Discrete Math._ 21 (2007), 57–65, doi: 10.1137/060665300.
  * Funke, Lamm, Meyer, Penschuck, Sanders, Schulz _et al._ [2019] D. Funke, S. Lamm, U. Meyer, M. Penschuck, P. Sanders, C. Schulz, D. Strash and M. von Looz, Communication-free massively distributed graph generation. _J. Parallel Distrib. Comput._ 131 (2019), 200–217, doi: 10.1016/j.jpdc.2019.03.011.
  * Gilbert [1961] E. N. Gilbert, Random Plane Networks. _J. Soc. Ind. Appl. Math._ 9 (1961), 533–543, doi: 10.1137/0109045.
  * Godehardt and Jaworski [1996] E. Godehardt and J. Jaworski, On the connectivity of a random interval graph. _Random Struct. Algorithms_ 9.1-2 (1996), 137–161, doi: 10.1002/(SICI)1098-2418(199608/09)9:1/2<137::AID-RSA9>3.0.CO;2-Y.
  * Goel, Rai and Krishnamachari [2005] A. Goel, S. Rai and B. Krishnamachari, Monotone properties of random geometric graphs have sharp thresholds. _Ann. Appl. Probab._ 15.4 (2005), 2535–2552, doi: 10.1214/105051605000000575.
  * Goldberg, Plotkin and Vaidya [1993] A. V. Goldberg, S. A. Plotkin and P. M. Vaidya, Sublinear-time parallel algorithms for matching and related problems. _J. Algorithms_ 14.2 (1993), 180–213, doi: 10.1006/jagm.1993.1009.
  * Gupta and Kumar [1999] P. Gupta and P. R. Kumar, Critical power for asymptotic connectivity in wireless networks. W. M. McEneaney, G. G. Yin and Q. Zhang (eds.), _Stochastic analysis, control, optimization and applications. A volume in honor of Wendell H. Fleming, on the occasion of his 70th birthday_ , 547–566, Birkhäuser, Boston, ISBN 0-8176-4078-9 (1999), doi: 10.1007/978-1-4612-1784-8_33.
  * Hall [1935] P. Hall, On representatives of subsets. _J. Lond. Math. Soc._ 10 (1935), 26–30, doi: 10.1112/jlms/s1-10.37.26.
  * Hopcroft and Karp [1973] J. E. Hopcroft and R. M. Karp, An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs. _SIAM J. Comput._ 2.4 (1973), 225–231, doi: 10.1137/0202019.
  * Janson, Łuczak and Ruciński [2000] S. Janson, T. Łuczak and A. Ruciński, _Random graphs_. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York (2000), doi: 10.1002/9781118032718.
  * Lichev, Lodewijks, Mitsche and Schapira [2022] L. Lichev, B. Lodewijks, D. Mitsche and B. Schapira, Bernoulli percolation on the Random Geometric Graph. _arXiv e-prints_ (2022). arXiv: 2205.10923.
  * McColm [2004] G. L. McColm, Threshold functions for random graphs on a line segment. _Comb. Probab. Comput._ 13.3 (2004), 373–387, doi: 10.1017/S0963548304006121.
  * Montgomery [2019] R. Montgomery, Spanning trees in random graphs. _Adv. Math._ 356 (2019), 92, doi: 10.1016/j.aim.2019.106793. Id/No 106793.
  * Müller, Pérez-Giménez and Wormald [2011] T. Müller, X. Pérez-Giménez and N. Wormald, Disjoint Hamilton cycles in the random geometric graph. _J. Graph Theory_ 68 (2011), 299–322, doi: 10.1002/jgt.20560.
  * Nekovee [2007] M. Nekovee, Worm epidemics in wireless ad-hoc networks. _New J. Phys._ 9.6 (2007), paper n. 189, doi: 10.1088/1367-2630/9/6/189.
  * Penrose [1997] M. Penrose, The longest edge of the random minimal spanning tree. _Ann. Appl. Probab._ 7.2 (1997), 340–361, doi: 10.1214/aoap/1034625335.
  * Penrose [2003] ———, _Random geometric graphs_ , _Oxf. Stud. Probab._ , vol. 5. Oxford: Oxford University Press (2003).
  * Penrose [2016a] ———, Connectivity of soft random geometric graphs. _Ann. Appl. Probab._ 26.2 (2016a), 986–1028, doi: 10.1214/15-AAP1110.
  * Penrose [2016b] ———, Lectures on random geometric graphs. _Random graphs, geometry and asymptotic structure_ , 67–101, Cambridge: Cambridge University Press (2016b), doi: 10.1017/CBO9781316479988.004.
  * Simić and Sastry [2003] S. N. Simić and S. Sastry, Distributed Environmental Monitoring Using Random Sensor Networks. F. Zhao and L. Guibas (eds.), _Information Processing in Sensor Networks_ , _Lecture Notes in Computer Science_ , vol. 2634, Springer, Berlin, Heidelberg (2003) 582–592, doi: 10.1007/3-540-36978-3_39.
  * Waxman [1988] B. M. Waxman, Routing of multipoint connections. _IEEE J. Sel. Areas Commun._ 6.9 (1988), 1617–1622, doi: 10.1109/49.12889.