&\int_{x_0=0}^1\int_{x_1 = x_0}^1\int_{x_2 = x_0}^{x_1}\dots \int_{x_k = x_0}^{x_{k-1}} \int_{x_{k+1}=0}^{x_0} \int_{s_1=0}^{+\infty} \int_{s_2 = 0}^{s_1}\int_{s_3 = 0}^{s_1+s_2}\dots \int_{s_{k+1}=0}^{s_1+\dots+s_k}\\
&(1-x_0)\exp(-s_1(1-x_0)) (x_1-x_0)\exp(-s_2(x_1-x_0))\dots (x_{k-1}-x_0)\exp(-s_k(x_{k-1}-x_0)) x_0 \exp(-s_{k+1} x_0) dx_0 \prod_{i=1}^{k+1} dx_i ds_i.
\end{align*}

The construction of the integral is derived from an exploration of the 1-dimensional PPP(1) on $\mathbb T^1_n$ starting from 0 (a more detailed explanation of a similar analysis was given in the previous subsection, where we counted the cherries in $\oPoNN$).

Although we are not able to compute the above sum of multiple integrals, numerical evidence over 100 independent trials with 10000 vertices leads to an empirical average of 4551.7 leaves with standard deviation 34.32. This suggests that the number of leaves is increasing with the dimension due to our analogy with the uniform random tree, as mentioned in the introduction.

§ TYPICAL DISTANCE, HEIGHT AND DIAMETER

In this section we provide several results concerning the metric structure of $G_n$, and in particular give a proof of Theorem <ref>. By abuse of notation, when clear from the context, we identify a vertex with its position.

§.§ Bounding the Euclidean distance between the endvertices of decreasing paths

The aim of this subsection is to provide an answer to the following question: starting from a vertex (with label) $\ell > m$, what can be said about the Euclidean distance between $\ell$ and its nearest ancestor in $[m]_0$ with respect to the graph distance of $G_n$? This is a key step in the analysis of the diameter and the height of the $d$-NN tree, as well as the stretch factor of a uniformly chosen pair of vertices, that is, the ratio of the sum of the Euclidean lengths of the edges on the path (in $G_n$) between the two vertices and the Euclidean distance between their positions.

Fix $d\ge 1$ and $m = m(n) = n^{\Omega(1)}$. Then, with probability at least $1-3/m$, the Euclidean distance between any $\ell > m$ and $m'$ uniquely defined as $m'\in [m]_0$ satisfying $d_{G_n}(\ell,m') = d_{G_n}(\ell, [m]_0)$ is at most $\frac{6\sqrt{d}}{1-2^{-1/d}}\left(\frac{(\log m)^{d+1} n}{m}\right)^{1/d}$.

Fix $d\ge 1$ and any sequence $(x_n)_{n\ge 1}$ of real numbers in $[0,1]$ with $nx_n = n^{\Omega(1)}$. Then, with probability at least $1 - 4/nx_n$, the Euclidean distance between any vertex in $\PoNN$ and its closest ancestor (in terms of graph distance) with arrival time in $[0,x_n]$ is at most $\frac{7\sqrt{d}}{1-2^{-1/d}}\left(\frac{(\log(nx_n))^{d+1} n}{nx_n}\right)^{1/d}$.

Since $|\PoNN|\sim \mathrm{Po}(n)$ and $|\{v\in V(\PoNN): X_v\le x_n\}|\sim \mathrm{Po}(nx_n)$, by (<ref>) one has that $|\PoNN|\in [n-n^{2/3},n+n^{2/3}]$ and $|\{v\in V(\PoNN): X_v\le x_n\}|\in [nx_n-(nx_n)^{2/3}, nx_n+(nx_n)^{2/3}]$ a.a.s. Conditionally on these two a.a.s. events, the corollary follows from Theorem <ref> with $m = \lfloor nx_n-(nx_n)^{2/3}\rfloor \ge 6nx_n/7$.

The rough idea behind the proof of Theorem <ref> is to decompose the path from $l$ to $[m]_0$ into shorter paths whose endvertices have labels within a factor of two, and to bound their lengths from above with (sufficiently) high probability. We defer the formal proof to the end of the section.

Fix $k_0 = \lceil (\log n)^2\rceil$. For every $k\in [k_0, n-1]$ let the event $\mathcal A_k$ be that, after the vertex with label $k-1$ has been embedded in $\mathbb T^d_n$, the Euclidean ball with radius $\frac{\sqrt{d}}{5} \left(\frac{3 n \log k}{k}\right)^{1/d}$ around any of the $k$ vertices contains another vertex as well (note that $k\ge k_0$ ensures that $\frac{\sqrt{d}}{5} \left(\frac{3 n \log k}{k}\right)^{1/d} < \frac{n^{1/d}}{2}$ so that the ball in $\mathbb T^d_n$ coincides with the Euclidean ball). Roughly speaking, one may think of the event $\mathcal A_k$ as having $k$ vertices spread relatively regularly. Also, for every $k\in [k_0-1, n-2]$, define the event $\mathcal B_k = \cap_{i=k+1}^{n-1} \mathcal A_i$. In particular, the event $\mathcal B_k$ implies that every vertex with label in $\{k, \dots, n-1\}$ has its parent “close” to it. We first show that, for all $k\ge k_0-1$, the event $\mathcal B_k$ is “likely to occur”.

For all $k\ge k_0$, the event $\mathcal B_k$ holds with probability at least $1-1/k$.

Fix $k\ge k_0$. Then, for every point $p\in \mathbb T^d_n$ and every $r\le n^{1/d}/2$

\begin{equation}\label{eq:ballvolume}
|B_d(p,r)| = r^d |B_d| = r^d \dfrac{\pi^{d/2}}{\Gamma(d/2+1)}\le r^d\dfrac{\pi^{d/2}}{(d/2e)^{d/2}}\le \left(\dfrac{5 r}{\sqrt{d}}\right)^d.
\end{equation}

\begin{equation*}
\mathbb P(\overline{\mathcal B_k}) \le \sum_{i=k+1}^{n-1}  \mathbb P(\overline{\mathcal A_i})\le \sum_{i=k+1}^{n-1} i \left(1-\dfrac{3 \log i}{i}\right)^{i-1} \le \sum_{i=k+1}^{n-1} \dfrac{1}{i^2}\le \sum_{i=k+1}^{+\infty} \left(\dfrac{1}{i-1} - \dfrac{1}{i}\right) = \dfrac{1}{k},
\end{equation*}

where the second inequality comes from a union bound and the fact that the ball in $\mathbb T^d_n$ with radius $\frac{\sqrt{d}}{5} \left(\frac{3n\log i}{i}\right)^{1/d}\le n^{1/d}/2$ has area $\frac{3n\log i}{i}$, and the third inequality comes from the fact that for every $i\ge 3$

\begin{equation*}
\left(1 - \dfrac{3\log i}{i}\right)^{i-1} \le \dfrac{1}{i^3},
\end{equation*}

which can be checked by taking the logarithm on both sides and expanding it; in particular, for $i\ge 3$

\begin{equation*}
(i-1)\log\left(1 - \dfrac{3\log i}{i}\right) < - \dfrac{3(i-1)\log i}{i} - \dfrac{9(i-1)(\log i)^2}{2i^2} < - 3\log i,
\end{equation*}

and the lemma is proved.

Denote by $a(v)$ the (label of the) parent of the vertex $v$ (by convention set $a(0) = 0$), and by $a^{k}(v)$ (the label of) its $k$-th ancestor. In particular, $a(v) = a^1(v)$, and we state the following observation used several times without explicit mention.

The distribution of $a^k(v)$ conditionally on $(a^i(v))_{i\in [k-1]}$ is uniform among $[a^{k-1}(v)-1]_0$.

Therefore, one may naturally couple the construction of the random path from $v$ to the root with the following process constructed via a family of iid random variables $(U_k)_{k\ge 1}$ distributed uniformly in $[0,1)$. Set $v_0 = v$. Then, for all $k\ge 1$, if $v_{k-1}\neq 0$, connect it by an edge to the vertex $v_k := \lfloor v_{k-1} U_k\rfloor$ (one may easily check that this choice is uniform among $0,1,2,\dots, v_{k-1}-1$). In particular, for all $k\ge 0$ such that $a^{k-1}(v)\neq 0$ we have that $a^{k-1}(v) U_k - 1\le a^{k}(v)\le a^{k-1}(v) U_k$, or also

\begin{equation}\label{eq path constr}
v U_1\dots U_k - k\le a^k(v)\le v U_1\dots U_k.
\end{equation}

Next, we use the above construction to show that the path in $G_n$ from the vertex $k$ to $\left[\lfloor k/2\rfloor\right]_0$ has a “relatively small” Euclidean length (that is, the sum of the lengths of its edges is small).

For every $k\ge 2k_0$, conditionally under the event $\mathcal B_{\lfloor k/2\rfloor}$, the path from $k$ to $\left[\lfloor k/2\rfloor\right]_0$ in $G_n$ is of Euclidean length at most $\frac{9\sqrt{d} \log k}{5} \left(\frac{3n\log(k/2)}{k/2}\right)^{1/d}$ with probability at least $1 - \left(\frac{e\log 2}{3\log k}\right)^{3\log k}$.

Define the hitting time $\tau_k = \min\{t\in \mathbb N:\hspace{0.2em} U_1 U_2\dots U_t\le 1/2\}$. After taking the logarithm and using that $X_i := -\log U_i$ has exponential distribution with mean $1$, we get $\tau_k = \min \{t\in \mathbb N:\hspace{0.2em} X_1+\dots+X_t\ge \log 2\}$. By Lemma <ref> (i), for every $k\ge 2$ we conclude that

\begin{equation*}
\mathbb P(\tau_k\ge \lceil 3\log k\rceil) = \mathbb P\left(\sum_{i=1}^{\lceil 3\log k\rceil} X_i\le \log 2\right)\le \dfrac{2(\log 2)^{\lceil 3\log k\rceil}}{\lceil 3\log k\rceil !}\le \dfrac{(\log 2)^{\lceil 3\log k\rceil}}{(e^{-1}\lceil 3\log k\rceil)^{\lceil 3\log k\rceil}}\le \left(\dfrac{e \log 2}{3\log k}\right)^{3\log k}.
\end{equation*}

This proves the lemma since by (<ref>) we have $\{\tau_k\le \lfloor 3\log k\rfloor\}\subseteq \{a^{\lfloor 3\log k\rfloor}(k)\le k/2\}$, and under $\mathcal B_{\lfloor k/2\rfloor}$ for all $t > k/2$ every vertex in $G_t$ is at Euclidean distance at most $\frac{3 \sqrt{d}}{5} \left(\frac{3 n \log(k/2)}{k/2}\right)^{1/d}$ to the remaining vertices in $G_t$.

Fix $m\in \mathbb N$ sufficiently large and $\ell \ge m+1$. Under the event $\mathcal B_{\lfloor m/2\rfloor}$, the (Euclidean) length of the path from $l$ to $[m]_0$ in $G_n$ is at most $\frac{6\sqrt{d}}{1-2^{-1/d}}\left(\frac{(\log m)^{d+1} n}{m}\right)^{1/d}$ with probability at least $1-\exp(-\log m\log\log m)$.

We regroup the vertices in $[m+1,\ell]$ into groups with indices $[m+1, 2m], [2m+1,4m], \dots, [2^s m+1, l]$ where $s$ is the unique integer satisfying $2^s m + 1\le \ell \le 2^{s+1} m$. For any $k\in [s]_0$ by Lemma <ref> and a union bound over the vertices with indices in $[2^{k} m+1, 2^{k+1} m]$, we deduce that with probability at least $1 - 2^k m \left(\frac{e \log 2}{3\cdot \log(2^{k} m)}\right)^{3\log(2^{k} m)}$, for all $t\in [2^{k} m+1, 2^{k+1} m]$ and $v\in V(G_t)$, the path from $v$ to $[2^k m]_0$ in $G_n$ has (Euclidean) length at most $\frac{9\sqrt{d} \log(2^{k+1} m)}{5} \left(\frac{3 \log(2^{k} m)}{2^{k} m}\right)^{1/d} n^{1/d}$.
For all $\xi > 1$, define the functions

\begin{equation*}
H_1(\xi) = \sum_{k=0}^{+\infty} 2^k \xi\left(\dfrac{e\log 2}{3\cdot \log(2^k \xi)}\right)^{3 \log(2^k \xi)},
\end{equation*}

\begin{equation*}
H_2(\xi) = \sum_{k=0}^{+\infty} \dfrac{9\sqrt{d} \log(2^{k+1} \xi)}{5} \left(\dfrac{3 \log(2^k \xi)}{2^k \xi}\right)^{1/d}.
\end{equation*}

Under the event $\mathcal B_{\lfloor m/2\rfloor}$, a union bound over all $s+1$ groups shows that, with probability at least $1-H_1(m)$, the (Euclidean) length of the path from $\ell$ to $[m]_0$ in $G_n$ is at most $H_2(m) n^{1/d}$.

Note that by standard analysis for all large enough $m$ we have

$$H_1(m) = O_m\left(m\left(\dfrac{e\log 2}{3\log m}\right)^{3\log m}\right) \le \exp\left(-\log m\log\log m \right).$$

\begin{align}
H_2(m) &=\hspace{0.3em} \sum_{k=0}^{+\infty} \dfrac{9\sqrt{d} \log(2^{k+1} m)}{5} \left(\dfrac{3 \log(2^k m)}{2^k m}\right)^{1/d}\nonumber\\
&\le\hspace{0.3em} \sum_{k=0}^{+\infty} \dfrac{9.1 \sqrt{d} \log(2^k m)}{5} \left(\dfrac{3 \log(2^k m)}{2^k m}\right)^{1/d}\nonumber\\
&=\hspace{0.3em} \sum_{k=0}^{+\infty} \dfrac{9.1 \sqrt{d} \log m}{5} \left(\dfrac{3 \log m}{m}\right)^{1/d} \left(\dfrac{1}{2^k}\left(\dfrac{k \log 2}{\log m}+1\right)^{d+1}\right)^{1/d}\nonumber\\
&\le\hspace{0.3em} \dfrac{9.1 \sqrt{d} \log m}{5} \left(\dfrac{3 \log m}{m}\right)^{1/d} \hspace{0.3em}\sum_{k=0}^{+\infty} \left(\dfrac{1}{2^{1/d}+o_m(1)}\right)^k.\nonumber
\end{align}

Hence, for all sufficiently large $m$,

\begin{equation}\label{upper bound eq}
H_2(m)\le \frac{3^{1/d}\cdot 9.1 \sqrt{d}\log m}{5(1-2^{-1/d}+o_m(1))}\left(\frac{\log m}{m}\right)^{1/d}\le \frac{6\sqrt{d}}{1-2^{-1/d}}\left(\frac{(\log m)^{d+1}}{m}\right)^{1/d},
\end{equation}

and this concludes the proof of the lemma.

Fix $m$ as in Theorem <ref>. Let $\mathcal A$ be the event that, for all $\ell \in [m+1, n-1]$, the Euclidean distance between any $\ell$ and $m'$ uniquely defined as $m'\in [m]_0$ satisfying $d_{G_n}(\ell,m') = d_{G_n}(\ell, [m]_0)$ is at most $\frac{6\sqrt{d}}{1-2^{-1/d}}\left(\frac{(\log m)^{d+1} n}{m}\right)^{1/d}$. On the one hand, by Lemma <ref> and a union bound,

\begin{equation*}
\mathbb P(\overline{\mathcal A}\mid \mathcal B_{\lfloor m/2\rfloor})\le \sum_{\ell=m+1}^{n-1} \exp(-\log m\log\log m)\le n \exp(-\log m\log\log m) = o(1/m).
\end{equation*}

On the other hand, by Lemma <ref>, the event $\overline{\mathcal B_{\lfloor m/2\rfloor}}$ holds with probability at most $1/\lfloor m/2\rfloor \le 2.1/m$. This concludes the proof since $\mathbb P(\overline{\mathcal A})\le \mathbb P(\overline{\mathcal A}\mid\mathcal B_{\lfloor m/2\rfloor}) + \mathbb P(\overline{\mathcal B_{\lfloor m/2\rfloor}}) \le 3/m$.

We finish this subsection with an unsurprising though at the same time curious property of the embedded tree $G_n$. Recall that for two vertices $u$ and $v$, the stretch factor between $u$ and $v$ is the ratio of the Euclidean length of the path in $G_n$ between $u$ and $v$ and the Euclidean distance between $u$ and $v$. Clearly, the stretch factor is at least $1$; we show as a consequence of Lemma <ref> that for two uniformly chosen vertices it is indeed $O(1)$ a.a.s.
For every $\varepsilon\in (0, d^{-d/2})$ there exists a constant $c=c(\varepsilon, d) > 0$ such that, with probability at least $1-\varepsilon$, the stretch factor of two uniformly chosen vertices $u$ and $v$ is at most $c$.

Fix $\varepsilon\in (0, d^{-d/2})$ and $M = M(\varepsilon)\in \mathbb N$ sufficiently large so that, first, Lemma <ref> holds for all $m\ge M$ and $\ell\ge m+1$, and second, $\exp(-\log M\log\log M)\le \varepsilon/2$. Set also $c_1 = c_1(\varepsilon, d):= 2\cdot \frac{6\sqrt{d}}{1-2^{-1/d}}\left(\frac{(\log M)^{d+1}}{M}\right)^{1/d} + M \sqrt{d}$. Then, by Lemma <ref> the Euclidean length of the path in $G_n$ from any vertex to $[M]_0$ is at most $\frac{6\sqrt{d}}{1-2^{-1/d}}\left(\frac{(\log M)^{d+1} n}{M}\right)^{1/d}$ with probability at least $1 - \varepsilon/2$. Thus, the Euclidean length of the path between $u$ and $v$ is at most $c_1 n^{1/d}$ with probability at least $1 - \varepsilon/2$.

On the other hand, with probability at least $1-\varepsilon/2$, the Euclidean distance between $u$ and $v$ is at least $c_r = c_r(\varepsilon, d) :=\sqrt{d}(\varepsilon/2)^{1/d}/5 < 1/2$: indeed, by (<ref>) one has $|B_d(u,c_r n^{1/d})| \le \left( \frac{5 c_r}{\sqrt{d}}\right)^d n$, so by our choice of $c_r$ we get $|B_d(u,r)|\le \varepsilon n/2$, and hence the probability that $v$ falls therein is at most $\varepsilon/2$. We deduce that with probability at least $1-\varepsilon$, the stretch factor between $u$ and $v$ is at most $c = c_1/c_r$, which finishes the proof.

Note that the previous corollary cannot be improved in the following sense: for any $d \ge 2$ and any constant $C > 0$ there exists $\varepsilon_C > 0$ such that, with probability at least $\varepsilon_C$, the stretch factor between two uniformly chosen vertices of $G_n$ at least $C$. We provide the following non-rigorous (but hopefully convincing) justification: tessellate $\mathbb T^d_n$ into $d$-cubes of side length $n^{1/d}/K$ for $K=K(C,d)$ large enough, and order the $K^d$ $d$-cubes so that every two consecutive cubes share a common $(d-1)$-side. The following events hold together with constant probability depending only on $K$:

* For every vertex $i \in [K^d-1]_0$, the vertex $i$ is embedded in the cube $i+1$ at distance at least $n^{1/d}/4K$ from its boundary. Moreover, if $i\ge 1$, vertex $i$ connects with an edge to $i-1$.

* The closest ancestor of $u$ among $[K^d-1]_0$ is $0$, and the closest ancestor of $v$ among $[K^d-1]_0$ is $K^d-1$.

Then, the Euclidean distance between $u$ and $v$ is bounded from above by $\sqrt{d} n^{1/d}$, but the Euclidean length of all edges on the path between them is bounded from below by $(K^{d}-1) n^{1/d}/2K$, which is at least $C \sqrt{d} n^{1/d}$ for all sufficiently large $K$.

Recall that, for a rooted tree $T$ and a vertex $v\in T$, we denote by $h(v, T)$ the distance from $v$ to the root of $T$, by $h(T)$ the height of $T$, and by $\mathrm{diam}(T)$ the diameter of $T$. Since $G_n$ may be seen as a tree rooted at the vertex $0$, the question of studying $h(G_n)$ and $\diam(G_n)$ appears naturally. The aim of this section is to provide the a.a.s. correct order of these two parameters, thus proving Theorem <ref>.

We first prove (i). Note that it is equivalent to prove the statement if the path to $0$ starts from an artificially added vertex with label $n$ (by doing this we only increase the length of the path in $G_n$ by one since $a(n)$ is chosen uniformly in $[n-1]_0$). Also, recall the construction of the path from a fixed vertex to the root via $(U_i)_{i\ge 1}$ given just above Lemma <ref>. Let

\begin{align*}
&T_1 = \min\{k: n U_1 U_2\dots U_k < 1\},\\
&T_2 = \min\{k: n U_1 U_2\dots U_k - k < 1\}.
\end{align*}

By Lemma <ref> applied to the random variables $X_i = -\log U_i$ we may conclude that $T_1\le (1+\varepsilon)\log n$ and $T_2\ge (1-\varepsilon) \log n$ a.a.s.: indeed,

\begin{align}
\mathbb P(T_1 > (1+\varepsilon)\log n)
&=\hspace{0.3em} \mathbb P(X_1+\dots+X_{\lfloor (1+\varepsilon)\log n\rfloor}\le \log n)\nonumber\\
&=\hspace{0.3em}\sum_{i=\lfloor (1+\varepsilon)\log n\rfloor}^{+\infty} \dfrac{1}{i!} \exp(-\log n) (\log n)^i\nonumber\\
&\le\hspace{0.3em} \exp(-\log n) \left(\dfrac{e \log n}{\lfloor (1+\varepsilon) \log n\rfloor}\right)^{\lfloor (1+\varepsilon) \log n\rfloor} \sum_{k\ge 0}\dfrac{1}{(1+\varepsilon)^k}\nonumber\\
&\le\hspace{0.3em} \dfrac{1+\varepsilon}{\varepsilon} \left(\dfrac{1}{e}\left(\dfrac{e}{1+\varepsilon+o(1)}\right)^{1+\varepsilon+o(1)}\right)^{\log n}\label{eq bla bla}.
\end{align}

Note that by standard analysis the function $x\in [1, +\infty)\mapsto (e/x)^x$ is decreasing, so $(e/x)^x < e$ for every $x > 1$. Thus, (<ref>) tends to 0 with $n$ for any fixed $\varepsilon > 0$. A similar computation ensures that $\mathbb P(T_2 < (1-\varepsilon) \log n) = o(1)$. This finishes the proof of Theorem <ref> a) since the hitting time of 0 from $n$ is dominated by $T_1$ and dominates $T_2$ due to (<ref>).

For the upper bound in (ii), it is sufficient to show that, for any $\varepsilon > 0$, the path from the artificially added vertex $n$ to $0$ has length at least $(e+\varepsilon) \log n$ with probability $o(1/n)$. Indeed, the length of the path from $n$ to $0$ stochastically dominates the length of any other path to the root: note that for any $j\in [n-1]_0$ one has $a^{k+1}(n) \sim \lfloor U_{k+1}a^k(n)\rfloor$ and $a^{k+1}(j) \sim \lfloor U_{k+1}a^k(j)\rfloor$ for all $k\ge 0$. Moreover, $T_1$ dominates the length of the path from $n$ to $0$, and by Lemma <ref> (i) for $X_i = -\log U_i$ we have

\begin{align*}
\mathbb P(T_1 > (e+\varepsilon)\log n)
&\le\hspace{0.3em} \mathbb P(X_1+\dots+X_{\lfloor(e+\varepsilon)\log n\rfloor}\le \log n)\\
&\le\hspace{0.3em} \dfrac{2}{\lfloor(e+\varepsilon)\log n\rfloor!}\dfrac{(\log n)^{\lfloor(e+\varepsilon)\log n\rfloor}}{n}\\
&\le\hspace{0.3em} \dfrac{2}{n}\left(\dfrac{e\log n}{\lfloor(e+\varepsilon)\log n\rfloor}\right)^{\lfloor(e+\varepsilon)\log n\rfloor} = o\left(\dfrac{1}{n}\right).
\end{align*}

The upper bound now follows from a union bound over all $n$ vertices.

We turn our attention to the lower bound in Theorem <ref> (ii). Recall that the Poisson $d$-NN tree $\PoNN$ is defined by sampling a Poisson random variable $N$ with mean $n$ and constructing the nearest neighbor tree on these $N$ vertices in $\mathbb T^d_n$.

Fix any $\varepsilon > 0$. Then, a.a.s. $\mathrm{diam}(\PoNN)\ge (2e-\varepsilon)\log n$.

We have that

\begin{equation}\label{eq LB poisson}
\mathbb P(N\le n) = \sum_{i=0}^{n} \dfrac{\exp(-n) n^i}{i!}\ge \sum_{i=0}^{n} \dfrac{\exp(i-n)(n/i)^{i}}{e\sqrt{i}},
\end{equation}

where the second inequality follows from the classical bound $i!\le (i/e)^i e\sqrt{i}$ for all $i\ge 1$. Moreover, if $i\in [\lfloor n-\sqrt{n}\rfloor,n]$, there is a constant $C > 0$ such that

\begin{equation*}
\left(\dfrac{n}{i}\right)^i = \exp\left(i \log\left(1 + \dfrac{n-i}{i}\right)\right) \ge \exp(n-i - C),
\end{equation*}

so we conclude that (<ref>) is bounded from below by

\begin{equation*}
\dfrac{1}{e\sqrt{n}}\sum_{i=\lfloor n-\sqrt{n}\rfloor}^{n} \exp(-C) \ge \dfrac{1}{\exp(1+C)} > 0.
\end{equation*}

Thus, since the diameter of a tree is an increasing parameter under addition of new vertices, we have

\begin{align*}
\mathbb P(\diam(G_n)\le (2e-\varepsilon)\log n)
&\le\hspace{0.3em} \mathbb P(\diam(\PoNN)\le (2e-\varepsilon)\log n\mid N\le n)\\
&\le\hspace{0.3em} \dfrac{\mathbb P(\diam(\PoNN)\le (2e-\varepsilon)\log n)}{\mathbb P(N\le n)} = o(1),
\end{align*}

and the proof is completed.

The last part of this section is dedicated to proving Theorem <ref>. We now present a high level overview of the main strategy, which is based on a renormalization argument. Fix a positive integer $k$ (to be properly chosen later) and for each of the $N$ vertices of $\PoNN$, sample independently a vector of $k$ i.i.d. Bernoulli random variables $(Y_{v,1}, Y_{v,2}, \dots, Y_{v,k})$ with parameters $n^{-1/k}$. To every vertex, associate a color $c(v)$ among $\{c_1,c_2,\dots,c_k,c_{k+1}\}$, where $c(v) = c_i$ if $Y_{v,1} = \dots = Y_{v,i-1} = 1$, and if $i \le k$, then in addition we also must have $Y_{v,i} = 0$. The aim of these colors is to regroup the vertices of $\PoNN$ according to their arrival time, where vertices with color $c_i$ arrive before vertices of color $c_j$ if $i > j$, but at the same time keep the sizes of the color classes random to avoid dependencies.

Now, define $R = R(n, d, k) := \lfloor (\log n)^{k(d+2)/d}\rfloor^d$ and $L = L(n, d, k) := R \lfloor R^{-1/d} n^{1/k d} (\log n)^{-(d+2)/d}\rfloor^{d}$, and embed the $N$ vertices in $\mathbb T^d_n$ without revealing anything but their geometric positions, and consider a tessellation $\mathcal T_1$ of $\mathbb T^d_n$ into $R L^{k-1}$ $d$-cubes, each of volume $(1+o(1)) n^{1/k}(\log n)^{d+2}$, but larger than $n^{1/k}(\log n)^{d+2}$. For every cube $q_1$ in $\mathcal T_1$ and every vertex $v_1$ in $q_1$, we assign a label associated to $v_1$ which equals $|\{u \in V(G_{n, Po}: p_u \in q_1, X_u < X_{v_1})\}|$, that is, the number of vertices $u \in q_1$, which arrived before $v_1$. We say that the label of $v_1$ with respect to $q_1$ is its 1-label. Next, in every cube $q_1\in \mathcal T_1$, we look for a decreasing path (with respect to the 1-labels) of length $(e-\varepsilon)(\log n)/k$ inside this cube between an arbitrary vertex in this cube and one of color different from $c_1$. In the construction of such a path, the colors and the 1-labels are revealed consecutively: if the parent of a vertex is detected, first its color is revealed, and if it is $c_1$, then its 1-label is revealed as well. Once a vertex of color different from $c_1$ is found, we stop the construction of the decreasing path without revealing the label of this last vertex (at this point we only know that its color is not $c_1$). We show that a sufficiently large number of cubes contain decreasing paths of length $(e-\varepsilon)(\log n)/k$ in their interior.

Then, we regroup the cubes of $\mathcal T_1$ into larger sets that form a coarser tessellation $\mathcal T_2$ containing $R L^{k-2}$ cubes, each of volume $(1+o(1)) n^{2/k}(\log n)^{2(d+2)}$, but larger than $n^{2/k}(\log n)^{2(d+2)}$. For every cube $q_2$ in $\mathcal T_2$ and every vertex $v_2$ in $q_2$, we assign a 2-label associated to $v_2$ that is equal to the number of vertices that arrived before $v_2$ in $q_2$. Note that the order, induced by the 2-labels on a cube $q_1\in \mathcal T_1$, is the same as the order given by the 1-labels in $q_1$. Thus, the 2-labeling is constructed by shuffling the 1-labels of the cubes $q_1$, contained in $q_2$, uniformly at random while keeping the relative order induced by the separate 1-labelings. Next, we look for decreasing paths (with respect to the 2-labels) between the vertices, which are ends of paths of length $(e-\varepsilon)(\log n)/k$ from the previous stage, to the vertices in colors, different from $c_1$ and $c_2$. Once again, we show that sufficiently many such cubes contain paths with length at least $(e-\varepsilon)(\log n)/k$.

We repeat the above procedure $k-3$ times. By gluing the paths, constructed at all $k-3$ stages, we show that a.a.s. one may find a decreasing path of length $(k-3)(e-\varepsilon)(\log n)/k$ (see Figure <ref>). We keep at least two such disjoint paths to make the transition from $h(\PoNN)$ to $\diam(\PoNN)$.

[line cap=round,scale=0.6,line join=round,x=1cm,y=1cm]
(-9.5,-20.99310136694685) rectangle (34.032489021253255,5.896464733479574);
[line width=0.8pt,dash pattern=on 1pt off 1.5pt] (0.3,-2.5)– (0.3,-2.4);
[line width=0.8pt,dash pattern=on 1pt off 1.5pt] (0.3,-2.4)– (0.5,-2.3);
[line width=0.8pt,dash pattern=on 1pt off 1.5pt] (0.5,-2.3)– (0.6,-2.7);
[line width=0.8pt,dash pattern=on 1pt off 1.5pt] (0.6,-2.7)– (0.8,-2.5);
[line width=0.8pt,dash pattern=on 1pt off 1.5pt] (0.8,-2.5)– (0.6,-2.9);
[line width=0.8pt,dash pattern=on 1pt off 1.5pt] (0.6,-2.9)– (0.2,-2.8);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (0.2,-2.8)– (-1,-2.5);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (-1,-2.5)– (-1,-3.5);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (-1,-3.5)– (0,-4.5);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (0,-4.5)– (1.5,-4);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (1.5,-4)– (2.5,-4.5);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (2.5,-4.5)– (2.5,-3.5);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (2.5,-3.5)– (2,-2.5);
[line width=0.8pt,dash pattern=on 0.8pt off 3pt] (2,-2.5)– (1.5,-1);
[line width=0.8pt,dash pattern=on 0.8pt off 0.8pt] (1.5,-1)– (0,-1);
[line width=0.8pt,dash pattern=on 0.8pt off 0.8pt] (0,-1)– (-1,-0.5);
[line width=0.8pt] (0,-2)– (0,-3);
[line width=0.8pt] (0,-3)– (1,-3);
[line width=0.8pt] (1,-3)– (1,-2);
[line width=0.8pt] (1,-2)– (0,-2);
[line width=0.8pt] (-2,0)– (3,0);
[line width=0.8pt] (3,-5)– (3,0);
[line width=0.8pt] (-2,-5)– (3,-5);
[line width=0.8pt] (-2,-5)– (-2,0);
[line width=0.8pt] (-1,-0.5)– (2,4);
[line width=0.8pt] (2,4)– (6,0);
[line width=0.8pt] (6,0)– (12,2);
[line width=0.8pt] (12,2)– (16,-4);
[line width=0.8pt] (16,-4)– (10,-8);
[line width=0.8pt] (10,-8)– (10,-14);
[line width=0.8pt] (10,-14)– (12,-18);
[line width=0.8pt] (12,-18)– (10,-18);
[line width=0.8pt] (10,-18)– (2,-10);
[line width=0.8pt] (2,-10)– (-2,-16);
[line width=0.8pt] (-2,-16)– (-6,-8);
[line width=0.8pt] (-7,5)– (18,5);
[line width=0.8pt] (18,5)– (18,-20);
[line width=0.8pt] (18,-20)– (-7,-20);
[line width=0.8pt] (-7,-20)– (-7,5);

Gluing together long paths - towards the proof of Theorem <ref> (<ref>).

We now proceed to the formal realization of the above strategy. We start with the formal definition of the tessellations. Define $(\mathcal T_i)_{1\le i\le k-2}$ as the family of tessellations such that, first, $\mathcal T_i$ refines $\mathcal T_{i+1}$ for every $i\in [k-2]$, and second, every cube $q_i \in \mathcal T_i$ has side length $(n R L^{i-k})^{-1/d} = (1+o(1)) n^{i/dk} (\log n)^{i(d+2)/d}$. Moreover, set $S = S(d,n,i) := \frac{7\sqrt{d}}{1-2^{-1/d}} ((\log n)^{d+1} n^{i/k})^{1/d}$, and for any $i\in [k-2]$ and any $q_i\in \mathcal T_i$ define $\intqi$ (respectively $\overline{\intqi}$) to be the central axis-parallel subcube of $q_i$ with boundary formed by the points at distance $2S$ (respectively $S$) from the boundary of $q_i$ (see Figure <ref>).

[line cap=round,scale=0.65,line join=round,x=1cm,y=1cm]
(-6.316028466187328,-5.081302215065078) rectangle (10.282350920657251,2.8003181856064043);
[line width=0.8pt] (-1,2)– (-1,-4);
[line width=0.8pt] (-1,-4)– (5,-4);
[line width=0.8pt] (5,-4)– (5,2);
[line width=0.8pt] (5,2)– (-1,2);
[line width=0.8pt] (-0.5,1.5)– (4.5,1.5);
[line width=0.8pt] (0,1)– (4,1);
[line width=0.8pt] (4.5,-3.5)– (-0.5,-3.5);
[line width=0.8pt] (4,-3)– (0,-3);
[line width=0.8pt] (-0.5,1.5)– (-0.5,-3.5);
[line width=0.8pt] (0,1)– (0,-3);
[line width=0.8pt] (4,1)– (4,-3);
[line width=0.8pt] (4.5,1.5)– (4.5,-3.5);
(5,1.5)– (5,1) node ;
(5,2)– (5,1.5) node ;
[color=black] (5.5,1.25) node $S$;
[color=black] (5.5,1.75) node $S$;

$q_i$ is the largest cube, $\overline{\intqi}$ is the second largest, and $\intqi$ is the smallest cube. The exploration process in $q_i$ is stopped if it leaves $\overline{\intqi}$ before finding a vertex of color among $(c_j)_{j=i+1}^{k+1}$.

Embed $N$ unlabeled and uncolored vertices in $\mathbb T^d_n$ uniformly at random. Our randomized algorithm performs $k-3$ steps. At step $i\in [k-3]$, expose the random variables $(Y_{v,j})_{v\in [N-1]_0, j\in [i-1]}$ and delete all vertices with colors among $c_1, \dots, c_{i-1}$. Then, fix a cube $q_i\in \mathcal T_i$ and an arbitrary vertex $v_i$ (if it exists, otherwise stop the process) remaining in $\intqi$. Start building a decreasing path from $v_i$ by, first, revealing $Y_{a(v_i),i}$, and then, if $Y_{a(v_i),i} = 0$ (that is, if $c(v_i) = c_i$), then return the $i$-label of this vertex in $q_i$ and repeat the analysis for $a(v_i)$ itself, and if not, stop the process in $q_i$. Also, stop the process if $a(v_i)$ leaves $\overline{\intqi}$.

Fix any $\varepsilon > 0$, $i\in [k-2]$ and a cube $q_i\in \mathcal T_i$. Also, fix a vertex $v_i\in \intqi$ satisfying $Y_{v,1} = \dots = Y_{v,i-1} = 1$. Then, there is $\delta  = \delta(\varepsilon) \in (0,1/k)$ such that the following event holds with probability at least $n^{-1/k+\delta}$: when the $i$-th stage of the algorithm terminates, the decreasing path from $v_i$ ends in $\overline{\intqi}$ and has length (with respect to the graph distance) at least $(e-\varepsilon)\log n/k$.

By Corollary <ref> applied with $x_n = n^{-i/k}$ (this corresponds to vertices $v$ with $Y_{v,1}=\dots=Y_{v,i}=1$) the Euclidean length of any path in $\PoNN$, ending at a vertex of color among $\{c_{i+1},\dots,c_{k+1}\}$, is dominated by $S$ with probability at least $1 - 4n^{-(k-i)/k}$. We call this event $\mathcal E_i$.

Now, we estimate the probability that the path from $v_i$ hits the set of vertices in $q_i$ in color among $\{c_{i+1},\dots,c_{k+1}\}$ only after $(e-\varepsilon) (\log n)/k$ or more steps. Recall the construction of the path using the family $(U_i)_{i\ge 1}$. Then, since $\mathcal E_i$ holds a.a.s. by (<ref>) it remains to estimate the probability of the event

\begin{equation}\label{eq good event}
\{ n^{(k-i)/k}U_1U_2\dots U_{\lceil (e-\varepsilon)(\log n)/k\rceil}\ge n^{(k-i-1)/k} + \lceil (e-\varepsilon)(\log n)/k\rceil \}.
\end{equation}

Applying Lemma <ref> to $X_i = -\log U_i$ we obtain that for any small enough $\varepsilon > 0$ there is a sufficiently small $\delta = \delta(\varepsilon)\in (0,1/k)$ such that

\begin{align*}
&\mathbb P(n^{(k-i)/k}U_1U_2\dots U_{\lceil (e-\varepsilon)(\log n)/k\rceil}
\ge n^{(k-i-1)/k} + \lceil (e-\varepsilon)(\log n)/k\rceil)\\
&\mathbb P(X_1 + \dots + X_{\lceil (e-\varepsilon)(\log n)/k\rceil}\le (1+o(1)) (\log n)/k) \\
\ge\hspace{0.2em}
&\dfrac{1}{\lceil (e-\varepsilon)(\log n)/k\rceil!}\exp\left(-(1+o(1))\dfrac{\log n}{k}\right) \left((1+o(1))\log n/k\right)^{\lceil (e-\varepsilon)(\log n)/k\rceil}\ge n^{-1/k+2\delta}.
\end{align*}

This finishes the proof of the lemma since the event $\mathcal E_i$ holds jointly with (<ref>) with probability at least $n^{-1/k+2\delta} - 4n^{-(k-i)/k} \ge n^{-1/k+\delta}$ by our choice of $i$ and $\delta$.

For every $\varepsilon > 0$ there is $\delta = \delta(\varepsilon) > 0$ such that, for all $i\in [k-2]$ and $q_i\in \mathcal T_i$, $q_i$ contains a decreasing path of length at least $(e-\varepsilon) (i-1) (\log n)/k$ with probability at least $n^{-1/k+\delta}/2$.

We argue by induction. Fix $\varepsilon > 0$ and $\delta = \delta(\varepsilon)$ given in Lemma <ref>.

For $i=1$, the statement is trivial. Suppose that the induction hypothesis holds for $j = i-1$. Note that, since $S$ in negligible compared to the side length of $q_i$, $\intqi$ contains at least $(\log n)^{d+1} n^{1/k}$ cubes of $\mathcal T_{i-1}$ (call these smaller cubes central). Then, by Lemma <ref> combined with a Chernoff's bound (<ref>) and a union bound over all cubes in $\mathcal T_i$, a.a.s. for every $q_i\in \mathcal T_i$ we know that $\overline{\intqi}$ contains at least one end of a path of length $(e-\varepsilon) (i-1) (\log n)/k$ which is entirely contained in a central cube. Denote this event by $\mathcal A(q_i)$. Under $\mathcal A(q_i)$, assign to $q_i$ one vertex in $q_i$ with color in $\{c_i, \dots, c_{k+1}\}$ which ends a path of length $(e-\varepsilon)(i-1)(\log n)/k$, and start constructing a decreasing path in $q_i$. Under $\mathcal A(q_i)$, by Lemma <ref> the following event holds with probability at least $n^{-1/k+\delta}$: one reaches a vertex, positioned in $\overline{\intqi}$ and with color in $\{c_{i+1},\dots, c_{k+1}\}$, only after at least $(e-\varepsilon) (\log n)/k$ steps. Denote this event by $\mathcal B(q_i)$. Thus, we get that

\begin{equation*}
\mathbb P(\mathcal B(q_i))\ge \mathbb P(\mathcal B(q_i)\mid\mathcal A(q_i))\mathbb P(\mathcal A(q_i))\ge n^{-1/k+\delta}/2,
\end{equation*}

and this concludes the induction.

Fix two cubes $q'_{k-1}$ and $q''_{k-1}$ in $\mathcal T_{k-1}$. Both $\mathrm{int}(q'_{k-1})$ and $\mathrm{int}(q''_{k-1})$ contain at least $n^{1/k} (\log n)^{d+1}$ cubes in $\mathcal T_{k-2}$, and by Chernoff's bound (<ref>) and Corollary <ref> some of these contain contain decreasing paths of length at least $(e-\varepsilon)(k-3)(\log n)/k$ a.a.s. The fact that these decreasing paths are disjoint (since they are entirely contained in different cubes of $\mathcal T_{k-1}$) finishes the proof of Theorem <ref> up to an appropriate choice of the values of $k$ and $\varepsilon$.

§ PROOF OF THEOREM <REF> - ON THE PROPERTIES OF

This section is dedicated to showing results on the infinite graph.

Fix any positive integer $M$ and a vertex $v_n$ of $G_n$ (resp. $v_{\infty}$ of $G_{\infty}$) in position $0\in \mathbb T^d_n$ (resp. $0\in \mathbb R^d$). We will construct a local a.a.s. coupling of $G_n$ and $G_{\infty}$ around $v_n$ and $v_{\infty}$, under which the balls $B_{G_n}(v_n, M)$ and $B_{G_{\infty}}(v_{\infty}, M)$ coincide a.a.s. The following argument tacitly assumes the results from Palm theory developed in Subsection <ref>, in particular, although the position of the vertex $v_n$ (resp. $v_{\infty}$) is given, the intensity of the Poisson Point Process remains unchanged.

The construction goes as follows: sample the same PPP(1) in the axis-parallel $d$-cube $Q_n$ (resp. $Q_{\infty}$) of side length $(2d+1) n^{1/2d}$ centered at 0 in $\mathbb T^d_n$ (resp. in $\mathbb R^d$). Moreover, for any pair of vertices $w_n$ and $w_{\infty}$ in $Q_n$ and $Q_{\infty}$ respectively that correspond to each other, sample their arrival times so that $X_{w_n} = X_{w_{\infty}}$ a.s. In the sequel, we refer to both $v_n$ and $v_{\infty}$ (resp. $Q_n$ and $Q_{\infty}$) as $v$ (resp. as $Q$) when the arguments allow to identify the finite with the infinite setting. For all $i\in [M]_0$, denote by $u_i$ the $i$-th ancestor of $v$ (so $u_0 = v$). Denote by $\mathcal A$ the event $X_{u_M}\ge (\log n)^{-M-1}$. One has

\begin{equation*}
\mathbb P(\overline{\mathcal A}) \le \mathbb P\left(\{X_{u_0}\le (\log n)^{-1}\}\cup \bigcup_{i\in [M]}\left\{X_{u_i}\le (\log n)^{-1} X_{u_{i-1}}\right\}\right)\le (M+1)(\log n)^{-1} = o(1).
\end{equation*}

Under the event $\mathcal A$, by Theorem <ref> for $i = \lfloor n (\log n)^{-M-1}\rfloor$ and Corollary <ref> for $x_n = (\log n)^{-M-1}$ there is a constant $C = C(d,M) > 0$ such that the descending tree $T_{u_M}$ of $u_M$ is contained in $B_d(u_M, (\log n)^{C})\subseteq B_d(v, 2(\log n)^{C})$ a.a.s. Thus, the positions of the vertices of $G_n$ in $\mathbb T^d_n\setminus Q_n$ (resp. of $G_{\infty}$ in $\mathbb R^d\setminus Q_{\infty}$) do not influence the structure of the tree $T_{u_M}$ a.a.s. because the ball $B(v, 2(\log n)^{C})$ has diameter $4(\log n)^{C}$ and is at distance $n^{\Omega_d(1)}\gg 4(\log n)^{C}$ from $\mathbb T^d_n\setminus Q_n$, resp. from $\mathbb R^d\setminus Q_{\infty}$ (see Figure <ref>). Thus, for any $M\in \mathbb N$ under the constructed coupling $B_{G_n}(v_n, M) = B_{G_{\infty}}(v_{\infty}, M)$ a.a.s. which proves the local convergence of $(G_n)_{n\ge 1}$ to $G_{\infty}$.

[line cap=round,line join=round,x=1cm,y=1cm]
(-10.4,-4.146057605080144) rectangle (7.90375770354596,5.124930735890613);
[line width=0.8pt] (-6,5)– (-6,-4);
[line width=0.8pt] (-6,-4)– (3,-4);
[line width=0.8pt] (3,-4)– (3,5);
[line width=0.8pt] (3,5)– (-6,5);
[line width=0.8pt] (-1.5,0.5)– (-2,0.5);
[line width=0.8pt] (-2,0.5)– (-1.5,1);
[line width=0.8pt] (-1.5,1)– (-0.5,0.5);
[line width=0.8pt] (-0.5,0.5)– (-1,-0.5);
[line width=0.8pt] (-1,-0.5) circle (1.7cm);
[line width=0.8pt] (-1.5,0.5) circle (3.5355339059327378cm);
[line width=0.8pt] (-1.5,0.5)– (-1.6,0.2);
[line width=0.8pt] (-1.5,0.5)– (-1.4,0.2);
[line width=0.8pt] (-1.6,0.2)– (-1.8,0.2);
[line width=0.8pt] (-1.6,0.2)– (-1.8,0);
[line width=0.8pt] (-1.6,0.2)– (-1.6,0);
[line width=0.8pt] (-2,0.5)– (-2.2,0.2);
[line width=0.8pt] (-1.5,1)– (-1.3,1.1);
[line width=0.8pt] (-1.5,1)– (-1,1);
[line width=0.8pt] (-1,1)– (-0.6,1);
[line width=0.8pt] (-1,1)– (-0.8,0.8);
[line width=0.8pt] (-1.3,1.1)– (-1.1,1.1);
[line width=0.8pt] (-0.5,0.5)– (-0.4,0.8);
[line width=0.8pt] (-0.5,0.5)– (-0.2,0.6);
[line width=0.8pt] (-0.5,0.5)– (-0.2,0.2);
[line width=0.8pt] (-0.2,0.2)– (-0.4,0);
[line width=0.8pt] (-0.4,0)– (-0.2,-0.2);
[line width=0.8pt] (-0.2,0.2)– (0.2,0.2);
[line width=0.8pt] (-1,-0.5)– (-1.4,-0.6);
[line width=0.8pt] (-1,-0.5)– (-1.2,-0.8);
[line width=0.8pt] (-1.4,-0.6)– (-1.8,-1);
[line width=0.8pt] (-1.4,-0.6)– (-1.4,-1);
[line width=0.8pt] (-1.2,-0.8)– (-1.2,-1.2);
[line width=0.8pt] (-1.2,-0.8)– (-1,-1);
[line width=0.8pt] (-1,-0.5)– (-0.4,-0.8);
[line width=0.8pt] (-1,-0.5)– (-0.6,-1.2);
[line width=0.8pt] (-0.6,-1.2)– (-0.2,-1.2);
[line width=0.8pt] (-0.2,-1.2)– (0,-1);
[line width=0.8pt] (-0.4,-0.8)– (-0.4,-0.4);
[line width=0.8pt] (-0.4,-0.8)– (-0.2,-0.6);
[line width=0.8pt] (-1.8,-1)– (-1.6,-1.6);
[line width=0.8pt] (-1.8,-1)– (-2.2,-1);
[line width=0.8pt] (-2.2,-1)– (-2.2,-0.8);
[line width=0.8pt] (-2.2,-1)– (-2.6,-0.6);
[line width=0.8pt] (-1.6,-1.6)– (-1.4,-1.8);
[line width=0.8pt] (-1.2,-1.2)– (-1.2,-1.6);
[line width=0.8pt] (-1.2,-1.2)– (-0.8,-1.6);
[line width=0.8pt] (-0.8,-1.6)– (-1,-1.8);
[line width=0.8pt] (-0.8,-1.6)– (-0.6,-1.8);

[fill=black] (-1.5,0.5) circle (1pt);
[color=black] (-1.4,0.62) node $u_0$;
[fill=black] (-2,0.5) circle (1pt);
[fill=black] (-1.5,1) circle (1pt);
[fill=black] (-0.5,0.5) circle (1pt);
[fill=black] (-1,-0.5) circle (1pt);
[color=black] (-1.2,-0.38) node $u_M$;
[color=black] (2.5,4.5) node $Q$;
[fill=black] (-1.6,0.2) circle (1pt);
[fill=black] (-1.4,0.2) circle (1pt);
[fill=black] (-1.8,0.2) circle (1pt);
[fill=black] (-1.8,0) circle (1pt);
[fill=black] (-1.6,0) circle (1pt);
[fill=black] (-2.2,0.2) circle (1pt);
[fill=black] (-1.3,1.1) circle (1pt);
[fill=black] (-1,1) circle (1pt);
[fill=black] (-0.6,1) circle (1pt);
[fill=black] (-0.8,0.8) circle (1pt);
[fill=black] (-1.1,1.1) circle (1pt);
[fill=black] (-0.4,0.8) circle (1pt);
[fill=black] (-0.2,0.6) circle (1pt);
[fill=black] (-0.2,0.2) circle (1pt);
[fill=black] (-0.4,0) circle (1pt);
[fill=black] (-0.2,-0.2) circle (1pt);
[fill=black] (0.2,0.2) circle (1pt);
[fill=black] (-1.4,-0.6) circle (1pt);
[fill=black] (-1.2,-0.8) circle (1pt);
[fill=black] (-1.8,-1) circle (1pt);
[fill=black] (-1.4,-1) circle (1pt);
[fill=black] (-1.2,-1.2) circle (1pt);
[fill=black] (-1,-1) circle (1pt);
[fill=black] (-0.4,-0.8) circle (1pt);
[fill=black] (-0.6,-1.2) circle (1pt);
[fill=black] (-0.2,-1.2) circle (1pt);
[fill=black] (0,-1) circle (1pt);
[fill=black] (-0.4,-0.4) circle (1pt);
[fill=black] (-0.2,-0.6) circle (1pt);
[fill=black] (-1.6,-1.6) circle (1pt);
[fill=black] (-2.2,-1) circle (1pt);
[fill=black] (-2.2,-0.8) circle (1pt);
[fill=black] (-2.6,-0.6) circle (1pt);
[fill=black] (-1.4,-1.8) circle (1pt);
[fill=black] (-1.2,-1.6) circle (1pt);
[fill=black] (-0.8,-1.6) circle (1pt);
[fill=black] (-1,-1.8) circle (1pt);
[fill=black] (-0.6,-1.8) circle (1pt);
[fill=black] (2.3,0.5) circle (0.5pt);
[fill=black] (2.5,0.5) circle (0.5pt);
[fill=black] (2.7,0.5) circle (0.5pt);
[fill=black] (-5.7,0.5) circle (0.5pt);
[fill=black] (-5.5,0.5) circle (0.5pt);
[fill=black] (-5.3,0.5) circle (0.5pt);
[fill=black] (-1.5,4.7) circle (0.5pt);
[fill=black] (-1.5,4.5) circle (0.5pt);
[fill=black] (-1.5,4.3) circle (0.5pt);
[fill=black] (-1.5,-3.7) circle (0.5pt);
[fill=black] (-1.5,-3.5) circle (0.5pt);
[fill=black] (-1.5,-3.3) circle (0.5pt);

A geometric representation of the proof of Theorem <ref>(<ref>). The smaller ball is $B(u_M, (\log n)^C)$ and the bigger ball is $B(u_0, 2(\log n)^C)$. The tree contained in the smaller ball is $T_{u_M}$.

Fix a vertex $v$ with position $p_v\in \mathbb R^d$ and arrival time $x_v\in (0,1]$ (note that there is a.s. no vertex arriving at time $0$). Set a sequence of real numbers $(\ell_i)_{i\ge 1}$ tending to infinity so that the interiors of all boundary cubes in all cubic nets $(N(p_v, \ell_i))_{i\ge 1}$ are disjoint. For all $i\in \mathbb N$, denote by $\mathcal A_i$ the event that each boundary cube in $N(p_v, \ell_i)$ contains a vertex with arrival time in the interval $(0, x_v)$. Since $\lim_{i\to +\infty} |[-\ell_i, \ell_i]^d|\to +\infty$, we have that $\mathbb P(\mathcal A_i)$ tends to 1 as $i\to +\infty$. Thus,

\begin{equation*}
\mathbb P(\deg_{G_{\infty}}(v) = +\infty) = \mathbb P([p_v-1/2, p_v+1/2]^d\cap V(G_{\infty}) = +\infty) + \mathbb P(\cap_{i\ge 1} \overline{\mathcal A_i})\le 0 + \lim_{i\to +\infty} \mathbb P(\overline{\mathcal A_i}) = 0.
\end{equation*}

We conclude that

\begin{align*}
&\mathbb P(\exists v\in V(G_{\infty}): \deg_{G_{\infty}}(v) = +\infty)\\
&\mathbb P(\exists v\in V(G_{\infty}): \deg_{G_{\infty}}(v) = +\infty\mid |G_{\infty}| \text{ is countable}) + \mathbb P(|G_{\infty}| \text{ is not countable})\\
\le\hspace{0.3em}
&0 + \mathbb P\left(\exists (y_i)_{i=1}^d\in \mathbb Z^d: \prod_{i=1}^d [y_i-1, y_i+1]\cap V(G_{\infty}) = +\infty\right) = 0,
\end{align*}

and this proves Theorem <ref>(<ref>).

To prove Theorem <ref> (<ref>), we need some preparation.

Fix any real number $r\in (0,1]$ and set $\varepsilon = (512 d^2)^{-2d}$ and $M = 16 d^2 r^{-1/d}$. Fix a $d$-cube $Q\subseteq \mathbb R^d$ of side length $M$. Then, $Q$ satisfies with probability at least
$1 - (8d^2)^{-d}$ the following two conditions: it contains no vertex of $G_{\infty}$ with arrival time in the interval $[(1-\varepsilon)r, (1+\varepsilon)r]$, and it contains a vertex with arrival time in the interval $(0, (1-\varepsilon)r)$.

We have

\begin{equation*}
\mathbb P(|Q\cap \{v\in V(G_{\infty}): X_v\in [(1-\varepsilon)r, (1+\varepsilon)r]\}|\ge 1) = 1 - \exp(-2\varepsilon r M^d)\le 1 - \exp(-2(32d^2)^{-d})\le 2(32 d^2)^{-d},
\end{equation*}

where in the last step we used the inequality $1\le t + \exp(-t)$ for all $t\ge 0$, and

\begin{equation*}
\mathbb P(|Q\cap \{v\in V(G_{\infty}): X_v\in (0,(1-\varepsilon)r)\}|= 0) = \exp(-(1-\varepsilon)r M^d)\le \exp(-(16 d^2)^d/2)\le (16 d^2)^{-d},
\end{equation*}

where at the last step we used that $\exp(-t/2)\le t^{-1}$ for all $t\ge 16$. The observation follows by a union bound.

Fix a tessellation $\mathcal T$ of $\mathbb R^d$ into $d$-cubes. Up to rescaling, the centers of the cubes of $\mathcal T$ form a copy of $\mathbb Z^d$, and thus one may equip $\mathcal T$ with the following distance: for any cubes $Q_1,Q_2\in \mathcal T$ with centers $q_1,q_2$, set $d_{\mathcal T}(Q_1,Q_2) = d_{L^1(\mathbb Z^d)}(q_1,q_2)$.

The descending tree of any vertex in $G_{\infty}$ is finite a.s.

We argue by contradiction. Fix a rational number $r\in (0,1]$ and define $M$ and $\varepsilon$ as in Observation <ref>. Denote by $\mathcal A_r$ the event that there is an infinite descending path $(u_i)_{i\ge 0}$ in $G_{\infty}$ such that $\lim_{i\to +\infty} X_{u_i}\in [r-\varepsilon/2, r+\varepsilon/2]$ (note that the arrival times of $u_i$ decrease with $i$ and thus the limit is well defined). We show that for all rational $r\in (0,1]$ the event $\mathcal A_r$ has probability 0.

Fix a tessellation $\mathcal T$ of $\mathbb R^d$ into cubes of sidelength $M$ and color in blue the $d$-cubes of $\mathcal T$ (the vertices therein are also colored in blue) that do not satisfy the conditions from Observation <ref>. Thus, all cubes are colored in blue independently and with the same probability. Note that a vertex $u_i$ with arrival time in $[(1-\varepsilon)r, (1+\varepsilon)r]$ must belong to a blue cube $Q$, and if there are no other blue cubes at distance at most $d^2$ from $Q$ (with respect to $d_{\mathcal T}$), then $u_{i+1}$ must be positioned in $B_{\mathcal T}(Q, d^2)$: indeed, fix any point $p_1$ outside $B_{\mathcal T}(Q,d^2)$, any point $p_2\in Q$ and set $p_4$ as the intersection point of the segment $p_1p_2$ with $B_{\mathcal T}(Q,d^2)$, which is closest to $p_1$. Also, let $p_3$ by an arbitrary point in some cube of $\mathcal T$, containing $p_4$ on its boundary (see Figure <ref>). Then, by the fact that every point outside $B_{\mathcal T}(Q,d^2)$ is at distance at least $Md$ from $Q$, together with the triangle inequality we have

\begin{equation*}
|p_1p_2| = |p_1p_4|+|p_4p_2| > |p_1p_4| + Md\ge |p_1p_4|+|p_4p_3|\ge |p_1p_3|.
\end{equation*}

[line cap=round,line join=round,x=1cm,y=1cm]
(-5.3,-7.02) rectangle (16,2.02);
[line width=0.8pt] (3,2)– (3,-7);
[line width=0.8pt] (3,-7)– (4,-7);
[line width=0.8pt] (4,-7)– (4,2);
[line width=0.8pt] (4,2)– (3,2);
[line width=0.8pt] (2,1)– (2,-6);
[line width=0.8pt] (2,-6)– (5,-6);
[line width=0.8pt] (5,-6)– (5,1);
[line width=0.8pt] (5,1)– (2,1);
[line width=0.8pt] (1,0)– (1,-5);
[line width=0.8pt] (1,-5)– (6,-5);
[line width=0.8pt] (6,-5)– (6,0);
[line width=0.8pt] (6,0)– (1,0);
[line width=0.8pt] (0,-1)– (0,-4);
[line width=0.8pt] (0,-4)– (7,-4);
[line width=0.8pt] (7,-4)– (7,-1);
[line width=0.8pt] (7,-1)– (0,-1);
[line width=0.8pt] (-1,-2)– (-1,-3);
[line width=0.8pt] (-1,-3)– (8,-3);
[line width=0.8pt] (8,-3)– (8,-2);
[line width=0.8pt] (8,-2)– (-1,-2);
[line width=0.8pt] (3.66,-2.64)– (7.7,-5.56);
[line width=0.8pt] (5.38,-4.48)– (6,-4.331287128712872);
[line width=0.8pt] (5.38,-4.48)– (7.7,-5.56);

[fill=black] (3.66,-2.64) circle (1pt);
[color=black] (3.6,-2.45) node $p_2$;
[fill=black] (7.7,-5.56) circle (1pt);
[color=black] (8,-5.5) node $p_1$;
[fill=black] (6,-4.331287128712872) circle (1pt);
[color=black] (6.3,-4.2) node $p_4$;
[fill=black] (5.38,-4.48) circle (1pt);
[color=black] (5.3,-4.3) node $p_3$;

A representation of the geometric part of the proof of Lemma <ref> in the case $d = 2$.

Now, we show that the blue cubes in $\mathcal T$ together with all cubes at distance at most $d^2$ from a blue cube form a.s. only finite clusters. Indeed, let $H$ be the $d^2$-th power of the copy of $\mathbb Z^d$ with vertices at the centers of the cubes in $\mathcal T$. Thus, every vertex has less than $(4d^2)^d$ neighbors. However, by Observation <ref> a vertex is blue with probability at most $(8d^2)^{-d}$. Thus, a comparison with a branching process shows that the component of any vertex in $H$ is a.s. finite. Hence, on this a.s. event the sequence $(u_i)_{i\ge 0}$ may intersect only finitely many blue cubes, since blue cubes whose centers are not connected in $H$ cannot contain consecutive terms of the sequence which both have arrival times in the interval $[r-\varepsilon, r+\varepsilon]$. This means that $(u_i)_{i\ge 0}$ must contain an accumulation point, which happens with probability 0. Thus, for any rational number $r\in [0,1]$ the event $\mathcal A_r$ has probability 0. Since the intervals $[(1-\varepsilon/2)r, (1+\varepsilon/2)r]_{r\in \mathbb Q; r\in (0,1]}$ cover the interval $(0,1]$ itself, we have

\begin{equation*}
\mathbb P(\text{there is an infinite descending path $(u_i)_{i\ge 0}$ in $G_{\infty}$}) \le \mathbb P(\cup_{r\in \mathbb Q; r\in (0,1]} \mathcal A_r) \le \sum_{r\in \mathbb Q; r\in (0,1]} \mathbb P( \mathcal A_r) = 0,
\end{equation*}

and the lemma is proved.

Fix an arbitrary vertex $v_0$ and let $(v_i)_{i\ge 0}$ be a sequence of vertices of $G_{\infty}$ such that $v_i$ is the parent of $v_{i-1}$ for all $i\ge 1$. Then, by Lemma <ref> the connected component of $v_0$ is a.s. isomorphic to a copy of $\mathbb N_0$ with a finite tree attached to every node $i\in \mathbb N$ (where $i\in \mathbb N_0$ corresponds to $v_i$). The last graph is recurrent for the simple random walk since $\mathbb N_0$ is itself recurrent.

Before moving on with the proof of Theorem <ref> (<ref>), let us first briefly justify that there exists $k\in \mathbb N\cup \{\infty\}$ such that the number of connected components of $G_{\infty}$ is a.s. $k$. The proof of this weaker statement is independent from the proof of Theorem <ref> (<ref>), it is given here as a meaningful application of a well-known argument in percolation theory. Tessellate $\mathbb{R}^d$ into unit $d$-cubes and generate $\mathrm{Po}(1)$ many points independently in each of them. Then, assign independently to each point a random variable with distribution $\Un$, corresponding to its arrival time. It can be shown that the events, invariant by all translations of $\mathbb R^d$ that preserve the tessellation, have probability either 0 or 1 (see e.g. Lemma 2.8 in [33], the same proof holds by replacing “edges” with “unit $d$-cubes”). In particular, for all $k\in \mathbb N\cup \{\infty\}$, $G_{\infty}$ has $k$ connected components with probability 0 or 1.

Now, we show the more precise result that a.s. the number of components is $1$, but before we need to prepare the terrain. Fix a real number $t\ge 1$. For any vertex $u\in V(G_{\infty})$, let $A_t(u)$ be the closest ancestor of $u$ (with respect to the graph distance in $G_{\infty}$) with arrival time $X_{A_t(u)} \le t^{-d}$. Moreover, set

$$C_d := \dfrac{64}{|B_d|^{1/d}(1-2^{-1/d})} \int_{y=0}^{+\infty} \exp(-y^d) dy.$$

Fix a real number $t\ge 1$ and condition on the position $p_u$ and the arrival time $X_u$ of a vertex $u\in V(G_{\infty})$. Then, with probability at least $3/4$, the sum of the Euclidean distances of all edges on the path between $p_u$ and $p_{A_t(u)}$ is less than $C_d t/4$.

We show that the expected distance between $p_u$ and $p_{A_t(u)}$ is at most $C_d t/16$. If $X_u\le t^{-d}$, the statement is clear, so suppose that $X_u > t^{-d}$. Set $j_{\max} = \lceil \log_2(t^d X_u)\rceil$. First, for all $j\in [j_{\max}]$ and any vertex $v$ with $X_v\in [2^{-j} X_u, 2^{-j+1} X_u]$ one has that $X_{a(v)}\le X_v/2$ with probability $1/2$ since, conditionally on $X_v$, $X_{a(v)}\sim \mathrm{Unif}([0, X_v])$. Thus, for all $j\in [j_{\max}]$, the number of vertices with arrival time in $[2^{-j} X_u, 2^{-j+1} X_u]$ is bounded from above by a geometric random variable (starting from 1) with mean 2. Therefore, since for any vertex $v$ with given arrival time $x_v$ the value of $\mathbb E |p_v p_{a(v)}|$ (that is, the expected length of the edge to its parent) is a decreasing function of $x_v$, one has

\begin{align*}
\mathbb E |p_u p_{A_t(u)} \mid X_u, p_u|\le\hspace{0.3em}
& \mathbb E\left[\sum_{v \text{ ancestor of }u:\hspace{0.2em} X_{A_t(u)} < X_v < X_u} |p_v p_{a(v)} \mid X_u, p_u|\right]\\
\le\hspace{0.3em}
& \sum_{j=1}^{j_{\max}} \mathbb E\left[\sum_{v \text{ ancestor of }u:\hspace{0.2em} 2^{-j} X_u \le X_v < 2^{-j+1} X_u} |p_v p_{a(v)} \mid X_u, p_u|\right]
\\
\le\hspace{0.3em}
& \sum_{j=1}^{j_{\max}} 2\; \mathbb E[|p_v p_{a(v)}|\mid X_u, p_u, X_{v} = 2^{-j} X_u]\\
\le\hspace{0.3em}
& 2\sum_{j=1}^{j_{\max}} \int_{s=0}^{+\infty} s\cdot \exp(-2^{-j} X_u |B_d| s^d) 2^{-j} X_u d |B_{d}| s^{d-1} ds\\
& 2\sum_{j=1}^{j_{\max}} \int_{s=0}^{+\infty} \exp(-2^{-j} X_u |B_d| s^d) ds\\
\le\hspace{0.3em}
& 2\sum_{j=1}^{j_{\max}} (2^{-j} X_u |B_d|)^{-1/d}\int_{y=0}^{+\infty} \exp(-y^d) dy\\
& 2 \left(\int_{y=0}^{+\infty} \exp(-y^d) dy\right) (2^{j_{\max}} X_u^{-1}|B_d|^{-1})^{1/d} \sum_{i=0}^{+\infty} 2^{-i/d}\\
\le\hspace{0.3em}
& 4 \left(\int_{y=0}^{+\infty} \exp(-y^d) dy\right) \dfrac{t}{1-2^{-1/d}} = \dfrac{C_d t}{16}.
\end{align*}

Note that from the fourth to the fifth line we used integration by parts, and from the fifth to the sixth line we used a change of variable $y = (2^{-j} X_u |B_d|)^{1/d} s$. Also, between the last and the penultimate line we use that $2^{j_{\max}} X_u^{-1}\le 2 (t^d X_u) X_u^{-1} = 2t^d$, and the fact that $|B_d(1)|=1$. The lemma follows by Markov's inequality.

Fix a real number $t\ge 1$ and condition on the position $p_u$ and the arrival time $X_u$ of a vertex $u\in V(G_{\infty})$. Moreover, assume that $p_u$ is outside a $d$-cube $Q$ which itself is conditioned on not containing any ancestor of $u$ in $G_{\infty}$. Then, the sum of the Euclidean distances of all edges on the path between $p_u$ and $p_{A_t(u)}$ is less than $C_d t/2$ with probability at least $3/4$.

First, fix any ancestor $v$ of $u$ satisfying $p_v\notin Q$ and a hyperplane $h$ passing through $v$ such that $Q$ is entirely contained in one of the two connected half-spaces in $\mathbb R^d\setminus h$ (since $Q$ is convex, by the well known hyperplane separation theorem such a hyperplane exists). For concreteness, call these two half-spaces $A$ and $B$ with $Q\subseteq B$. Moreover, denote by $\mathcal P'$ the Poisson Point Process, obtained by restricting the original PPP(1) to the half-space $A$, denote by $G'_{\infty}$ be the associated random NN tree and by $\mathbb P'$ the probability measure, associated to this restricted online NN process (we also write $\mathbb E'$ for the associated expectation). One may roughly think of $G'_{\infty}$ as $G_{\infty}$ conditioned on $B\cap V(G_{\infty}) = \emptyset$ (although $B\cap V(G_{\infty}) = \emptyset$ has in fact probability 0). Then,

\begin{align*}
& \mathbb E[|p_v p_{a(v)}|\mid \text{no ancestor of } v \text{ is positioned in } Q]\\
\le\hspace{0.3em}
& \mathbb E[|p_v p_{a(v)}|\mid Q\cap V(G_{\infty}) = \emptyset]\\
\le\hspace{0.3em}
& \mathbb E'[|p_v p_{a(v)}|].
\end{align*}

Indeed, deleting one point (different from $p_v$) cannot decrease the expected value of $|p_v p_{a(v)}|$ (deleting the point, corresponding to the original parent $a(v)$ of $v$, increases the distance to the next vertex that arrived before $v$, and deleting any other point does not influence the length of  $|p_v p_{a(v)}|$). It remains to justify that $\mathbb E'[|p_u p_{A_t(u)}|]\le C_d t/2$. The proof of this fact is the same as the one of Lemma <ref> except that the density of $|p_v p_{a(v)}|$ conditionally on $X_v$ is not $\exp(-X_v |B_d| s^d) X_v d|B_d| s^{d-1} ds$ but instead is given by the density with respect to an exploration of the closed half-space $A\cup h$ from $v$, that is, $\exp(-X_v 2^{-1} |B_d| s^d) X_v 2^{-1} d|B_d| s^{d-1} ds$ (then, by redoing the same computation as in the proof of Lemma <ref>, we arrive at the same result at the price of an additional factor of $2^{1/d} \le 2$).

Now, condition on the positions $p_{u_0},p_{v_0}$ and the arrival times $X_{u_0},X_{v_0}$ of two vertices $u_0,v_0\in V(G_{\infty})$. Let $\kappa_0 = |p_{u_0}p_{v_0}|$ and $t_0 = \kappa_0 C_d^{-1}/3$. Fix an axis-parallel $d$-cube $H_0$ of side length $2\kappa_0$ containing both $p_{u_0}$ and $p_{v_0}$ in its central $d$-cube of side length $\kappa_0$, and a tessellation $\mathcal{T}_0$ of $\mathbb{R}^d$ into $d$-cubes satisfying $H_0\in \mathcal T_0$.

The vertices $u_0$ and $v_0$ are connected in $G_{\infty}$ and their closest common ancestor $w$ satisfies $p_w\in H_0$ with probability at least $2^{-1} \exp(-((5d)^d-2^d) (3C_d)^d)$.

Define $\hat{H}_0$ as the axis-parallel $d$-cube of sidelength $5d \kappa_0$ having the same center as $H_0$, and let $\mathcal{L}$ be the event that $\hat{H}_0 \setminus H_0$ contains no other vertex $z$ with $X_z \le t_0^{-d}$. Note that the open balls around $u$ and $v$ with radii $\kappa_0/2$ and the region $\hat{H}_0\setminus H_0$ are all disjoint. Thus, since $C_d t_0/4 = \kappa_0/12 < \kappa_0/6$, the events “the sum of the Euclidean distances of all edges on the path between $p_u$ and $p_{A_{t_0}(u)}$ (resp. between $p_v$ and $p_{A_{t_0}(v)}$) is less than $C_d t_0/4$” together with $\mathcal L$ form an independent family - indeed, note that the first two events depend only on the Poisson Point Process in the open balls $B_d(u, \kappa_0/2)$ and $B_d(v, \kappa_0/2)$, which are disjoint from one another and disjoint from the region $\hat{H}_0\setminus H_0$. Moreover, the three events combined imply the event from the statement of the lemma: indeed, this would mean that $p_{A_{t_0}(u)}$ and $p_{A_{t_0}}(v)$ are both situated in $H_0$, and since $\hat{H}_0\setminus H_0$ contains no vertex with arrival time at most $t_0^{-d}$ and moreover the diameter of $H_0$ is $2\sqrt{d}\kappa_0 < (5d-2)\kappa_0$, $A_{t_0}(u)$ and $A_{t_0}(v)$ must share a common ancestor in $H_0$. By Lemma <ref> the first two hold with probability at least $3/4$ and the last one holds with probability $\exp(-((5d)^d-2^d)\kappa_0^d t_0^{-d}) = \exp(-((5d)^d-2^d) (3C_d)^d)$. The product of the three terms is more than $2^{-1} \exp(-((5d)^d-2^d) (3C_d)^d)$, which proves the lemma.

Fix an axis-parallel cube $Q\subseteq H_0$ at distance at least $\kappa_0/2$ from the boundary of $H$. Condition on the event that $p_{u_0}, p_{v_0} \notin Q$, and moreover $Q$ does not contain any ancestor of $u_0$ or $v_0$ in $G_{\infty}$. Then, with probability at least $2^{-1} \exp(-((5d)^d-2^d) (3C_d)^d)$, $p_w \in H_0$.

Denote by $\mathcal M$ the event “$p_{u_0}, p_{v_0} \notin Q$ and $Q$ does not contain any ancestor of $u_0$ or $v_0$ in $G_{\infty}$”. Replace in the proof of Lemma <ref> the application of Lemma <ref> by an application of Corollary <ref>, and the event $\mathcal L$ by the event $\mathcal L' = \mathcal L\cap \mathcal M$. The corollary follows by noticing that the three regions $B_d(u, \kappa_0/2)\setminus Q, B_d(v, \kappa_0/2)\setminus Q$ and $(\hat{H}_0\setminus H_0)\cup Q$ are all disjoint from one another.

First, apply Lemma <ref> to $u_0$ and $v_0$. If the event from Lemma <ref> holds, terminate. Else, adopt the following iterative approach. For all $i\ge 1$, define $u_i$ (resp. $v_i$) as the nearest ancestor of $u_{i-1}$ (resp. of $v_{i-1}$) in $G_{\infty}$ which is outside $H_{i-1}$ and has no ancestor in $H_{i-1}$. Then, by Corollary <ref> applied with $u_0 := u_i, v_0 := v_i$, $H_0:=H_i$ and $Q := H_{i-1}$, with probability at least $2^{-1}\exp(-((5d)^d-2^d)(3C_d)^d)$ the following event holds: $u_i$ and $v_i$ have a common ancestor $w_i$ positioned in a $d$-cube $H_i$ with side length $2|p_{u_i}p_{v_i}|$ and containing both $p_{u_i}$ and $p_{v_i}$ at distance at least $|p_{u_i}p_{v_i}|/2$ from its boundary. Moreover, the outcome of this step is independent from the outcome of the previous steps. Since every step happens with the same constant probability, a.s. at some step $i\ge 1$ $u_i$ and $v_i$ get connected within $H_i$. Thus,

\begin{align*}
& \mathbb P(\exists u,v\in V(G_{\infty}), u \text{ is not connected to }v)\\
\le\hspace{0.3em}
& \mathbb P(\exists u,v\in V(G_{\infty}), u \text{ is not connected to }v\mid |G_{\infty}| \text{ is countable}) + \mathbb P(|G_{\infty}| \text{ is not countable}) = 0.
\end{align*}

Thus, $G_{\infty}$ is a.s. connected.

§ CONCLUSION AND OPEN QUESTIONS

In this paper, we conducted a rigorous analysis of the online $d$-dimensional $NN$-tree, that is, apart from the complementary paper of Aldous [4] mentioned above, the first of its kind. Furthermore, we introduced and analyzed a natural infinite counterpart of this model. Needless to say, besides the already mentioned Conjecture <ref>, many questions remain for further thought:

* We firmly believe that some of our techniques extend to the model of $d$-dimensional $k$-$NN$ graphs. It might be interesting to analyze them in more depth.

* Can the number of leaves (or cherries) be used for detecting the dimension of the underlying tree solely from its combinatorial structure? Our partial results and simulations indicate that both quantities should be increasing with the dimension, and therefore should yield a good estimator for detecting the dimension.

* As we pointed out in Subsection <ref>, a lot of work on similar models has been done to find the root of the tree. More precisely, one might wonder if for any fixed $\varepsilon > 0$ there is a set of vertices of constant size $K=K(\varepsilon)$ that contains the root of the graph with probability $1-\varepsilon$. It is not clear to us whether statistics, which provide good estimators in other models, can be used in our model as well. In particular, we do not know whether in our model there is a function $f$ as in the paper of Rácz and Sridhar [61] mentioned in Subsection <ref> that can be used for detection: for example, it could be that some centrality statistics such as the global balancedness measure $H(T)$ used in [20] and also described in Subsection <ref> could be used to find the root. We also do not know whether the centroid with respect to this measure a.s. changes only finitely many times during the graph process, as shown in [47, 48] for other models.

* An interesting question in the infinite setup could be to study the asymptotic rate of expansion of the graph $G_{\infty}$. For any $v\in V(G_{\infty})$, how fast does the number of vertices at graph distance $k$ from $v$ grow as $k\to +\infty$?

§ ACKNOWLEDGEMENTS
The authors would like to thank Gábor Lugosi and Vasiliki Velona for bringing this topic to our attention and for discussions in an early stage of this paper. The authors also would like to thank Bas Lodewijks for careful proofreading and David Aldous for bringing reference [4] to our attention. The first author would like to thank Ivailo Hartarsky for a discussion around the connectivity of $G_{\infty}$.

[1]
H. Acan.
Perfect matchings and Hamilton cycles in uniform attachment graphs.
http://arxiv.org/pdf/1908.03659.pdf, 2019.

[2]
L. Addario-Berry, L. Devroye, G. Lugosi, and V. Velona.
Broadcasting on random recursive trees.
Annals of Applied Probability, 2021.

[3]
D. Ahlberg, V. Tassion, and A. Teixeira.
Sharpness of the phase transition for continuum percolation in
Probab. Theory Relat. Fields, 172(1-2):525–581, 2016.

[4]
D. Aldous.
Random partitions of the plane via poissonian coloring and a
self-similar process of coalescing planar partitions.
Annals of Probability, 46(4):2000–2037, 2018.

[5]
N. S. Altman.
An introduction to kernel and nearest-neighbor non-parametric
The American Statistician, 46(3):175–185, 1992.

[6]
F. Baccelli and C. Bordenave.
The radial spanning tree of a Poisson Point Process.
The Annals of Applied Probability, 17(1):305–359, 2007.

[7]
F. Baccelli, D. Coupier, and V. C. Tran.
Semi-infinite paths of the two-dimensional radial spanning tree.
Advances in Applied Probability, 45(4):895–916, 2013.

[8]
A. Bagchi and S. Bansal.
On the metric distortion of nearest-neighbour graphs on random point
http://arxiv.org/pdf/0804.3784.pdf, 2008.

[9]
T. Bailey and A. Jain.
A note on distance-weighted $k$-nearest neighbor rules.
IEEE Transactions on Systems, Man, and Cybernetics,
8(4):311–313, 1978.

[10]
P. N. Balister and B. Bollobás.
Percolation in the $k$-nearest neighbor graphs.
https://www.memphis.edu/msci/people/pbalistr/kperc.pdf, 2011.

[11]
P. N. Balister, B. Bollobás, A. Sarkar, and M. J. Walters.
Connectivity of random $k$-nearest neighbour graphs.
Advances in Applied Probability, 37:1–24, 2005.

[12]
P. N. Balister, B. Bollobás, A. Sarkar, and M. J. Walters.
A critical constant for the $k$-nearest neighbour model.
Advances in Applied Probability, 41:1–12, 2009.

[13]
E. Banerjee and S. Bhamidi.
Root finding algorithms and persistence of Jordan centrality in
growing random trees.
Annals of Applied Probability, to appear.

[14]
A. Barabási and R. Albert.
Emergence of scaling in random networks.
Science, 286:509–512, 1999.

[15]
S. Bermejo and J. Cabestany.
Adaptive soft $k$-nearest neighbour classifiers.
Pattern Recognition, 33(12):1999–2005, 2000.

[16]
B. Bollobás and O. Riordan.
The diameter of a scale-free random graph.
Combinatorica, 24:5–34, 2004.

[17]
B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády.
The degree sequence of a scale-free random graph process.
Random Structures and Algorithms, 18:279–290, 2001.

[18]
C. Bordenave.
Navigation on a Poisson Point Process.
The Annals of Applied Probability, 18(2):708–746, 2008.

[19]
S. Bubeck, L. Devroye, and G. Lugosi.
Finding Adam in random growing trees.
Random Structures and Algorithms, 50(2):158–172, 2017.

[20]
S. Bubeck, R. Eldan, E. Mossel, and M. Z. Rácz.
From trees to seeds: on the inference of the seed from large trees in
the uniform attachment model.
Bernoulli, 23(4A):2887–2916, 2017.

[21]
S. Bubeck, E. Mossel, and M. Z. Rácz.
On the influence of the seed graph in the preferential attachment
IEEE Transactions on Network Science and Engineering,
2(1):30–39, 2015.

[22]
C. Canonne.
A short note on Poisson tail bounds, 2019.

[23]
D. Coupier.
Sublinearity of the number of semi-infinite branches for geometric
random trees.
Electronic Journal of Probability, 23:1–33, 2018.

[24]
T. Cover and P. Hart.
Nearest Neighbor Pattern Classification.
IEEE Trans. Inf. Theor., 13(1):21–27, September 2006.

[25]
N. Curien, T. Duquesne, I. Kortchemski, and I. Manolescu.
Scaling limits and influence of the seed graph in preferential
attachment trees.
Journal de l’École polytechnique – Mathématiques,
2(1):1–34, 2015.

[26]
L. Devroye.
Branching processes in the analysis of the heights of trees.
Acta Informatica, 24(3):277–298, 1987.

[27]
L. Devroye.
Applications of the theory of records in the study of random trees.
Acta Informatica, 26:123–130, 1988.

[28]
L. Devroye, O. Fawzi, and N. Fraiman.
The height of scaled attachment random recursive trees.
Discrete Mathematics and Theoretical Computer Science, pages
129–142, 2010.

[29]
L. Devroye and J. Lu.
The strong convergence of maximal degrees in uniform random recursive
trees and dags.
Random Structures & Algorithms, 7(1):1–14, 1995.

[30]
L. Devroye and T. Reddad.
On the discovery of the seed in uniform attachment trees.
Internet Mathematics, 1(1), 2019.

[31]
M. Drmota.
Random trees: an interplay between combinatorics and
Springer Science & Business Media, 2009.

[32]
S. A. Dudani.
The distance-weighted $k$-nearest neighbor rule.
IEEE Transactions on Systems, Man, and Cybernetics,
SMC-6(4):325–327, 1976.

[33]
H. Duminil-Copin.
Introduction to Bernoulli percolation.
Lecture notes at IHES available at
https://www.ihes.fr/ duminil/publi/2017percolation.pdf, 2018.

[34]
D. Eppstein, M. S. Paterson, and F. F. Yao.
On nearest-neighbor graphs.
Disc. Comput. Geom., 17:263–282, 1997.

[35]
G. Fanti, P. Kairouz, S. Oh, K. Ramchandran, and P. Viswanath.
Rumor Source Obfuscation on Irregular Trees.
ACM SIGMETRICS, 44:153–164, 2016.

[36]
G. Fanti, P. Kairouz, S. Oh, K. Ramchandran, and P. Viswanath.
Hiding the Rumor Source.
IEEE Transactions on Information Theory, 63(10):6679–6713,

[37]
G. Fanti, P. Kairouz, S. Oh, and P. Viswanath.
Spy vs. Spy: Rumor Source Obfuscation.
ACM SIGMETRICS, 43:271–284, 2015.

[38]
E. Fix and J. L. Hodges Jr.
Discriminatory analysis-nonparametric discrimination: consistency
Technical report, Univ. Berkeley, California, 1951.

[39]
A. Flaxman, A.M. Frieze, and T. Fenner.
High degree vertices and eigenvalues in the preferential attachment
Internet Mathematics, 2:1–20, 2005.

[40]
A. Frieze and M. Karoński.
Introduction to Random Graphs.
Cambridge University Press, 2016.

[41]
A. Frieze, X. Pérez-Giménez, P. Prałat, and B. Reiniger.
Perfect matchings and Hamiltonian cycles in the preferential
attachment model.
Random Structures and Algorithms, 54(2):258–288, 2019.

[42]
E. N. Gilbert.
Random plane networks.
Journal of the Society for Industrial and Applied Mathematics,
9(4):533–543, 1961.

[43]
O. Häggström and R. Meester.
Nearest neighbor and hard sphere models in continuum percolation.
Random Structures and Algorithms, 9:295–315, 1996.

[44]
B. Jahnel and A. Tóbiás.
SINR percolation for Cox point processes with random powers.
https://arxiv.org/pdf/1912.07895.pdf, 2020.

[45]
B. Jahnel and A. Tóbiás.
Absence of percolation in graphs based on stationary point processes
with degrees bounded by two.
https://arxiv.org/pdf/2010.03187.pdf, 2021.

[46]
S. Janson, T. Łuczak, and A. Ruciński.
Random graphs.
Wiley-Interscience Series in Discrete Mathematics and Optimization.
Wiley-Interscience, New York, 2000.

[47]
V. Jog and P.-L. Loh.
Analysis of centrality in sublinear preferential attachment trees via
the Crump-Mode-Jagers branching process.
IEEE Transactions on Network Science and Engineering,
4(1):1–12, 2016.

[48]
V. Jog and P.-L. Loh.
Persistence of centrality in random growing trees.
Random Structures and Algorithms, 52(1):136–157, 2018.

[49]
J. Khim and P.-L. Loh.
Confidence sets for the source of a diffusion in regular trees.
IEEE Transactions on Network Science and Engineering,
4:27–40, 2016.

[50]
G. Last and M. Penrose.
Lectures on the Poisson process.
Cambridge University Press, 2017.

[51]
E. Levy.
On the density for sums of independent exponential, Erlang and
gamma variates.
Statistical Papers, pages 1–29, 2021.

[52]
G. Lugosi and A.S. Pereira.
Finding the seed of uniform attachment trees.
Electronic Journal of Probability, 24:1–15, 2019.

[53]
H. Mahmoud.
Limiting distributions for path lengths in recursive trees.
Probability in the Engineering and Informational Sciences,
5(01):53––59, 1991.

[54]
H. Mahmoud.
Distances in random plane-oriented recursive trees.
Journal of Computational and Applied Mathematics,
41(1-2):237–245, 1992.

[55]
R. Meester and R. Roy.
Continuum Percolation.
Cambridge University Press, 1996.

[56]
T.F. Móri.
The maximum degree of the Barabási-Albert random tree.
Comb., Prob. and Comp., 14(3):339–348, 2005.

[57]
S. Navlakha and C. Kingsford.
Network archaeology: uncovering ancient networks from present-day
PLoS Computational Biology, 7(4):e1001119, 2011.

[58]
M. Pain and D. Sénizergues.
Correction terms for the height of weighted recursive trees.
Annals of Applied Probability, to appear.

[59]
M. Penrose.
Random Geometric Graphs.
Oxford University Press, 2003.

[60]
B. Pittel.
Note on the heights of random recursive trees and random $m$-ary
search trees.
Random Structures and Algorithms, 5:337–348, 1994.

[61]
M. Z. Rácz and A. Sridhar.
Correlated randomly growing graphs.
Annals of Applied Probability, to appear.

[62]
M. Schulte and J. E. Yukich.
Multivariate second order Poincaré inequalities for Poisson
Electronic Journal of Probability, 24, 2019.

[63]
D. Sénizergues.
Geometry of weighted recursive and affine preferential attachment
Electronic Journal of Probability, (26):1–56, 2021.

[64]
D. Shah and T. Zaman.
Detecting Sources of Computer Viruses in Networks: Theory
and Experiment.
ACM SIGMETRICS, 38:203–214, 2010.

[65]
D. Shah and T. Zaman.
Rumors in a network: Who’s the culprit?
IEEE Transactions on Information Theory, 57(8):5163–5181,

[66]
S.H. Teng and F. Yao.
$k$-nearest neighbor clustering and percolation theory.
Algorithmica, 49:192–211, 2007.

[67]
R. van der Hofstad.
Random graphs and complex networks, Volume 1.
Cambridge University Press, 2016.

[68]
R. van der Hofstad.
Random graphs and complex networks, Volume 2.
https://www.win.tue.nl/ rhofstad/NotesRGCN.html, 2021.

[69]
L. Warnke.
On the method of typical bounded differences.
Combinatorics, Probability and Computing, 25(2):269–299, 2016.

[70]
F. Xue and P. R. Kumar.
The number of neighbors needed for connectivity of wireless networks.
Wireless Networks, 10:169–181, 2004.

[71]
G. U. Yule.
A Mathematical Theory of Evolution, based on the Conclusions
of Dr. J. C. Willis, F.R.S.
Philosophical Transactions of the Royal Society B,
213(402-410):21–87, 1925.