<figure><img src="image_1.png" /></figure>

HAL
open science

# Random sequential nearest-neighbor coloring on trees

Arvind Singh, Anne-Laure Basdevant

► To cite this version:

Arvind Singh, Anne-Laure Basdevant. Random sequential nearest-neighbor coloring on trees. 2026. [https://hal.science/hal-05445410v1](https://hal.science/hal-05445410v1)

HAL Id: hal-05445410

[https://hal.science/hal-05445410v1](https://hal.science/hal-05445410v1)

Preprint submitted on 7 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Random sequential nearest-neighbor coloring on trees

Anne-Laure Basdevant\*, Arvind Singh\d

January 7, 2026

<figure><img src="image_3.png" /><figcaption>Figure 1: Simulation of the coloring process on a binary tree of height 15.</figcaption></figure>

## Abstract

We study a random sequential coloring process on finite regular trees, where the root is initially colored in blue and the leaves in red. Then, the remaining vertices are selected uniformly at random and colored sequentially, each vertex inheriting the color of its closest previously colored vertex. We prove that, as the height of the tree tends to infinity, blue vertices appear arbitrarily close to the leaves with high probability, while red vertices persist at bounded distance from the root. We also show that this procedure yields a non-degenerate infinite-volume limit on the infinite regular tree, in contrast with the Euclidean Poissonian coloring.

## Introduction

We study a random coloring procedure on regular trees, in which all vertices are colored sequentially at random, each vertex taking, at the time it is picked, the color of one of its closest already colored vertices. This model can be interpreted as a growth process driven by local competition between different species (i.e. colors). Alternatively, it may also be interpreted as a variant of the classical voter model where new settlers take the political opinion of one of their neighbors already settled.

A similar coloring procedure was previously defined and studied in the Euclidean setting in [6, 1, 3]. In these works, the authors consider the unit cube $[-1, 1]^d$. Initially, the origin is colored in blue and the boundary of the cube in red. Subsequently, independent, uniformly sampled random points fall in $[-1, 1]^d$ and, upon arrival, each point takes the color of the nearest point that has appeared so far. This procedure ultimately creates a random coloring of the unit cube<fnref n="1" />.

<footnote>\*LPSM, Sorbonne Université, France, anne.laure.basdevant@normalesup.org</footnote>

<footnote>†CNRS and LMO, Université Paris-Saclay, France arvind.singh@universite-paris-saclay.fr</footnote>

<footnote n="1">¹This construction produces only a countable set of colored sample points but can be subsequently extended to a coloring of the whole cube by assigning to each location the color of the points in its infinitesimal neighborhood (with an additional ‘gray’ interface corresponding to accumulation points from both colors).</footnote>
One of the main results in [6, 3] is that there exists a.s. an open region containing the origin that is fully blue i.e. all red vertices remain at a positive distance from the initial blue vertex. On the other hand, the converse question of whether there may exist blue vertices arbitrarily close to the red boundary with positive probability is more delicate and still remains open, see open Question 1.4 in [3] and the discussion preceding Corollary 1 in [6] for more details. Numerical simulations indicate that, in dimension $d = 2$, the red boundary is “protected” so that, a.s., blue vertices do not reach the red boundary. However, this behaviour may depend finely on the dimension $d$ and may be false when $d$ become large enough as, informally, there are more space and more “directions of attack” for the blue vertices to reach the red boundary.

With this question in mind, we investigate here an analogous problem on trees which, heuristically, may be seen as letting the dimension $d \to \infty$. While our framework is here discrete rather than continuous, the coloring rule remains the same with a mechanism inducing long-range dependencies and complex spatial correlations, even though the underlying graph has a simple hierarchical structure. More precisely, we consider a finite rooted K-ary tree with height $\ell$ whose root is initially colored in blue and whose leaves are colored in red. The remaining vertices are colored one by one, in a random order, by adopting the color of the closest previously colored vertex; ties are broken uniformly at random. The main contribution of the paper is to show that the final red and blue regions exhibit substantial mixing with, as the height $\ell$ of the tree increases to infinity, some blue vertices reaching maximum height $\ell - 1$ (just below a red leaf) while some red vertices remain at a bounded distance from the origin.

## Main results

We now introduce some notation, make a formal definition of the model and state our main results.

Let $\mathcal{T}_\ell$ be a finite tree, rooted at $o$ and with $K \ge 2$ children per vertex and with height $\ell$. For $u, v \in \mathcal{T}_\ell$, we let $d(u, v)$ denote the usual graph distance in $\mathcal{T}_\ell$ and $|v| := d(o, v)$ is the height of the vertex $v$ in the tree. The coloring procedure proceeds as follows:

* Initially, at time $k = 0$, we color the root $o \in \mathcal{T}_\ell$ in blue and each of the $K^\ell$ leaves in red. We will denote by $B_k^{(\ell)}$ the set of blue vertices and by $R_k^{(\ell)}$ the set of red vertices at time $k$. Hence, $B_0^{(\ell)}$ consists only of the root of $\mathcal{T}_\ell$ and $R_0^{(\ell)}$ is the set of leaves.

* At time $k \ge 0$, we pick uniformly at random an uncolored vertex $v$ of $\mathcal{T}_\ell$ and consider the set of vertices $u \in B_k^{(\ell)} \cup R_k^{(\ell)}$ such that $d(u, v) = d(v, B_k^{(\ell)} \cup R_k^{(\ell)})$ i.e. the vertices that are already colored and closest to $v$. We then pick $u$ uniformly at random from this set and color $v$ with the same color as $u$. We then set $R_{k+1}^{(\ell)} = R_k^{(\ell)}$ and $B_{k+1}^{(\ell)} = B_k^{(\ell)} \cup \{v\}$ if $v$ has been colored in blue and $B_{k+1}^{(\ell)} = B_k^{(\ell)}$ and $R_{k+1}^{(\ell)} = R_k^{(\ell)} \cup \{v\}$ if $v$ has been colored in red.

* We continue this procedure until all vertices have been colored and we denote by $B^{(\ell)}$ (resp $R^{(\ell)}$) the final set of blue (resp. red) vertices.

See Figure 1 for an illustration of the coloring procedure. We point out that, as can be seen on this simulation, the blue set $B^{(\ell)}$ (and obviously also the red set $R^{(\ell)}$) need not be connected. We are particularly interested in the following quantities:

$$M_{\ell} := \max\{|v| : v \in B^{(\ell)}\}, \quad m_{\ell} := \min\{|v| : v \in R^{(\ell)}\},$$

i.e. the maximal height reached by the blue region and the minimal height reached by the red region.

**Theorem 1.** We have

$$\lim_{\ell \to \infty} \mathbb{P}(M_{\ell} = \ell - 1) = 1. \qquad (1)$$

$$\inf_{\ell \ge 1} \mathbb{P}(m_{\ell} = 1) > 0. \qquad (2)$$

Equation (1) shows, as stated in the introduction, that even though blue vertices all originate from a single seed at the origin, some blue vertex will eventually reach maximal height as the tree's height increases. This result contrasts with the behavior of the coloring process on Euclidean space where it is known that, at least with some non-zero probability, the blue vertices do not reach the boundary<fnref n="2" />.

<footnote n="2">²The open question mentioned previously is to determine whether this occurs with probability 1.</footnote>
Let us fix $\ell < \ell'$. There is a natural coupling for the coloring processes on $\mathcal{T}_\ell$ and $\mathcal{T}_{\ell'}$ obtained by considering the same ordering of the vertices and simply ignoring vertices $v$ with height $|v| > \ell$ when coloring $\mathcal{T}_\ell$. With this coupling, it is clear that

$$B^{(\ell)} \subset B^{(\ell')} \quad \text{a.s. for all } \ell < \ell'$$

Therefore, we can define a random coloring $(B^{(\infty)}, R^{(\infty)})$ of the infinite rooted K-ary tree $\mathcal{T}_\infty$ by setting the blue set as $B^{(\infty)} := \cup_{\ell \ge 1} B^{(\ell)}$ and the red set as the complement $R^{(\infty)} := \mathcal{T}_\infty \setminus B^{(\infty)}$.

Statement (2) of Theorem 1 shows that, even though the number of red leaves increases with the height of the tree, the coloring remains non-trivial on the limiting infinite tree $\mathcal{T}_\infty$. In fact, we can say a little more.

**Proposition 2.** The sequence $(m_\ell)_{\ell \ge 1}$ converges (almost surely under the natural coupling, and hence in distribution) to a finite random variable $m_\infty$ such that $\mathbb{P}(m_\infty = 1) > 0$. In particular, the limiting coloring process on the infinite rooted K-ary tree $\mathcal{T}_\infty$ is non-degenerate, and we have

$$\mathbb{P}(\text{at least one child of the root is colored red}) > 0.$$

We emphasize that this result contrasts with the Euclidean setting: if one considers the Poissonian coloring in a ball with a red boundary condition and a blue seed at the origin, then letting the radius go to infinity (and using scaling) leads to a trivial limit in which the coloring becomes entirely blue. On the infinite tree $\mathcal{T}_\infty$, the limit remains non-trivial because the red seeds do not disappear but are now pushed to infinity i.e. to the ideal boundary of the tree. This is reminiscent of phenomena in hyperbolic geometry, where infinite-volume limits of random structures may naturally live on the ideal boundary of the space. A related example is the recently introduced model of ideal Poisson–Voronoi tessellations [5]. In fact, our approach on trees can be adapted to Poissonian coloring in hyperbolic space as detailed in the forthcoming work [4].

## Outline of the paper

The proof of (1) is carried out in Section 1 and relies on a recursive renormalization argument. Roughly speaking, we show that with high probability one can find, at intermediate heights, pairs of disjoint subtrees whose roots are colored blue and whose boundary conditions resemble those of the original tree. This allows us to compare the growth of the blue region with a supercritical Galton–Watson process, yielding a quantitative lower bound on the number of blue vertices.

Proposition 2 together with (2) are proved in Section 2. This is done by defining the coloring process directly on the infinite tree $\mathcal{T}_\infty$. In this setting, the color of a given vertex can be determined by an infinite sequence of local comparisons, which naturally leads to the notion of an ancestral path associated with each vertex. We introduce an alternative construction of this path based on record times of an i.i.d. sequence, and we define a random subset of vertices encoding the information required to determine the final color of a given vertex. This construction allows us to characterize the event that a vertex ends up red in terms of the absence of the root from this random subset. Finally, using quantitative estimates on record processes together with geometric properties of regular trees, we prove that every vertex has a strictly positive probability of ending up red from which Proposition 2 and (2) follow.

# 1 The blue vertices reach the leaves

In this section, we establish (1) of Theorem 1. We begin with some convention:

* From now on, to avoid cumbersome notations, we shall simply denote $\mathcal{T}$ instead of $\mathcal{T}_\ell$ the K-ary tree of height $\ell$ (and, when needed, use the notation $|\mathcal{T}|! = \ell$ for the height of $\mathcal{T}$). Likewise, we will write $(B_k, R_k)_{k \ge 1}$ in place of $(B_k^{(\ell)}, R_k^{(\ell)})_{k \ge 1}$.

* We write $o$ for the root of $\mathcal{T}$ and $\partial\mathcal{T}$ for its set of leaves. For $v$ a vertex of $\mathcal{T}$, we denote $\mathcal{T}_v$ the sub-tree of $\mathcal{T}$ rooted at $v$, consisting of all its descendants.
To establish (1), we will need to consider the same coloring process as above except that we allow a more arbitrary initial configuration $(B_0, R_0)$. To obtain more independence in our coloring process, we now consider a continuous-time version of the process in which a vertex $v$ is selected and colored after a random waiting time $\tau_v$ with $(\tau_v, v \in \mathcal{T} \setminus (B_0 \cup R_0))$ are i.i.d. exponential random variables with parameter 1. So this defines two increasing processes $(B_t)_{t \ge 0}$ and $(R_t)_{t \ge 0}$ which are the set of blue and red vertices at time $t$.

Note that for any vertex $v$, the coloring process after time $\tau_v$ restricted to the sub-tree $\mathcal{T}_v$, namely $(B_t \cap \mathcal{T}_v, R_t \cap \mathcal{T}_v)_{t \ge \tau_v}$, is measurable with respect to its initial state $(B_{\tau_v} \cap \mathcal{T}_v, R_{\tau_v} \cap \mathcal{T}_v)$ and the random variables $(\tau_w, w \in \mathcal{T}_v)$.

Let $V_1^T, V_2^T, \dots$, be the vertices of $\mathcal{T}$ selected by the procedure, whose heights are strictly smaller than $|\mathcal{T}|/2$ ordered according to their coloring times. For $C, H \ge 0$ and $i \ge 1$ consider the event $A_i := A_i(\mathcal{T}, C, H, B_0, R_0)$ defined by

$$ A_i := \{ |\mathcal{T}|/2 - H < |V_i^T| < |\mathcal{T}|/2, V_i^T \text{ is colored in blue, and, at time } (\tau_{V_i^T})^{-}, \mathcal{T}_{V_i^T} \text{ contains at most } C \\ \text{colored vertices that are not leaves, and each of them is at a distance at most } 2H \text{ from the leaves.} \} \tag{3} $$

## 1.1 Coupling with a super-critical Galton-Watson process

The purpose of the next proposition is to show that, if we initially start with the root colored blue, the leaves colored red, and a bounded number of vertices close to the leaves also colored red, then, with probability close to one, we can find two vertices whose heights are roughly equal to $|\mathcal{T}|/2$ that are colored blue and such that, at their coloring times, the sub-trees rooted at these vertices have roughly the same initial configuration: the root of each sub-tree is blue, the leaves are red, and a bounded number of vertices near the leaves may also be red. This will allow us to lower bound the number of blue vertices at distance roughly equal to $(|\mathcal{T}|/2^k)_{k \le k_n}$ of the leaves by a supercritical Galton-Watson process.

**Proposition 3.** Recall the definition of the events $A_i$ given by (3). Let $\eta > 0$. Then, there exist $H, C, n_0 \ge 0$ such that if $|\mathcal{T}| \ge n_0$, for any choices of vertices $w_1, \dots, w_C$ of height larger or equal to $|\mathcal{T}| - 2H$, if $B_0 = \{o\}$ and $R_0 = \partial\mathcal{T} \cup \{w_1, \dots, w_C\}$, we have

$$ \mathbb{P}(\exists i < j, \mathcal{T}_{V_i^T} \cap \mathcal{T}_{V_j^T} = \emptyset \text{ and } A_i \cap A_j) \ge 1 - \eta. \tag{4} $$

Let us first explain why Proposition 3 implies (1) of Theorem 1.

*Proof of (1) using Proposition 3.* Set

$$ C_{i,j} := C_{i,j}(\mathcal{T}, C, H, B_0, R_0) := \{ \mathcal{T}_{V_i^T} \cap \mathcal{T}_{V_j^T} = \emptyset \text{ and } A_i \cap A_j \}. $$

Hence, Proposition 3 asserts that, for good choices $(\mathcal{T}, C, H, B_0, R_0)$, with large probability, at least on event $C_{i,j}$ occurs.

Fix $\eta > 0$ and $H, C, n_0 \ge 0$ such that (4) holds. By maybe choosing a larger $n_0$, we can assume that $C < K^{n_0-2H-1}$ and $n_0/2 - 2H > 2H$.

Consider the following process $(\mathcal{V}_l)_{l \ge 0}$ taking value in the subsets of $\mathcal{T}$:

* $\mathcal{V}_0 = \{o\}$. If there exist $i < j$ such that $C_{i,j}(\mathcal{T}, C, H, o, \partial\mathcal{T})$ occurs, then set $\mathcal{V}_1 := \{V_i^T, V_j^T\}$ and call $V_i^T, V_j^T$ the children of $o$. Otherwise, set $\mathcal{V}_1 = \emptyset$. In particular, by definition of the event $A_i$, we observe that for any vertex $v \in \mathcal{V}_1$, at time $(\tau_v)^-$, the sub-tree $\mathcal{T}_v$ contains at most $C$ colored vertices of height larger than $|\mathcal{T}_v| - 2H$ which are not leaves. Note that these vertices are necessarily red since they are at distance at most $2H$ of the leaves and at distance at least $|\mathcal{T}|/2 - 2H \ge n_0 - 2H > 2H$ of a blue vertex. Thus $B_{\tau_v} \cap \mathcal{T}_v = \{v\}$. Moreover, for $v_1 \ne v_2$ in $\mathcal{V}_1$, we have $\mathcal{T}_{v_1} \cap \mathcal{T}_{v_2} = \emptyset$. Thus, conditionally on $(B_{\tau_v}, R_{\tau_v}, v \in \mathcal{V}_1)$, the processes $((B_t \cap \mathcal{T}_v)_{t \ge \tau_v}, (R_t \cap \mathcal{T}_v)_{t \ge \tau_v})$, $v \in \mathcal{V}_1$ are independent.

* Assume that $\mathcal{V}_l = \{U_1^{(l)}, \dots, U_{Z_l}^{(l)}\}$. For each $v \in \mathcal{V}_l$, consider the coloring process on $\mathcal{T}_v$ for $t \ge \tau_v$. By induction, they are independent for $v \in \mathcal{V}_l$. Each of them starts with an initial configuration where only the root $v$ is blue and the red vertices are the leaves and at most $C$ other vertices, each
of them at distance at most $2H$ of the leaves. If there exists $i < j$ such that $C_{i,j}(\mathcal{T}_v, C, H, R_{\tau_v} \cap \mathcal{T}_v)$ occurs, then call $\{V_i^{\mathcal{T}_v}, V_j^{\mathcal{T}_v}\}$ the children of $v$. Then define $\mathcal{V}_{l+1}$ as the union of the children of $v$ for $v \in \mathcal{V}_l$.

By induction, we have that if $v \in \mathcal{V}_l$,

$$ \frac{|\mathcal{T}|}{2^l} \le |\mathcal{T}_v| \le \frac{|\mathcal{T}|}{2^l} + 2H. $$

Let $L \in \mathbb{N}$ such that $\frac{|\mathcal{T}|}{2^L} \ge n_0 > \frac{|\mathcal{T}|}{2^{L+1}}$ i.e.

$$ L := \lfloor \frac{\log(|\mathcal{T}|/n_0)}{\log 2} \rfloor. $$

Thus, for $v \in \mathcal{V}_L$, we have

$$ n_0 \le |\mathcal{T}_v| \le 2n_0 + 2H. $$

Using Proposition 3, we see that $(|\mathcal{V}_l|, l \le L)$ is larger than a Galton-Watson process $(Z_l, l \le L)$ starting at 1 and with reproduction law

$$ \mu(0) = \eta \qquad \mu(2) = 1 - \eta. $$

Such process $(Z_l, l \ge 0)$ survives with probability $(1 - 2\eta)/(1 - \eta)$ and we have, for $l$ large enough

$$ \mathbb{P}(Z_l > (2(1 - 2\eta))^l | Z_l > 0) \ge 1 - \eta. $$

Hence, if $|\mathcal{T}|$ is large enough, we get

$$ \mathbb{P}(|\mathcal{V}_L| \ge (2(1 - 2\eta))^L) \ge \mathbb{P}(Z_L > (2(1 - 2\eta))^L) \ge 1 - 2\eta. $$

Set $\beta := \log(2(1 - 2\eta))/\log 2$ such that

$$ (2(1 - 2\eta))^L = 2^{\beta L} \ge \left(2^{\left(\frac{\log(|\mathcal{T}|/n_0)}{\log 2} - 1\right)}\right)^\beta = \left(\frac{|\mathcal{T}|}{2n_0}\right)^\beta. $$

Hence we get

$$ \mathbb{P}\left(|\mathcal{V}_L| \ge \left(\frac{|\mathcal{T}|}{2n_0}\right)^\beta\right) \ge 1 - 2\eta. $$

This shows that, with probability at least $1 - 2\eta$, there exist at least $(|\mathcal{T}|/2n_0)^\beta$ disjoint sub-trees of height between $n_0$ and $2n_0 + 2H$ such that the coloring process colors their root $v$ blue and, at the time when its root becomes blue, the sub-tree contains at most $C$ red vertices of height larger than $|\mathcal{T}_v| - 2H$ that are not leaves. Each of these sub-trees then evolves independently. Using the facts that $C < K^{n_0 - 2H - 1}$ and that $|\mathcal{T}_v| \ge n_0$, we obtain that the number of vertices in $\mathcal{T}_v$ of height equal to $|\mathcal{T}_v| - 2H$ is strictly larger than $C$. Therefore, at time $\tau_v$, there necessarily exists a connected path from the root $v$ to a leaf consisting of uncolored vertices (except, of course, for the root and the leaf). Hence, the probability that no blue particle reaches distance one from the leaves is strictly less than one. Since the sizes of these $(|\mathcal{T}|/2n_0)^\beta$ trees are uniformly bounded, we in fact obtain a uniform upper bound $\alpha(n_0, H, C) < 1$ for each of them to have no blue vertex at distance one from the leaves. Thus, we get

$$ \mathbb{P}(M_{|\mathcal{T}|} < |\mathcal{T}| - 1) \le 2\eta + \alpha(n_0, H, C)^{(|\mathcal{T}|/2n_0)^\beta} $$

which can be arbitrary close to 0 as $|\mathcal{T}|$ tends to infinity if $\eta$ is chosen sufficiently small. $\square$

## 1.2 Existence of one blue vertex at height $|\mathcal{T}|/2$

To prove Proposition 3, we first establish a weaker version of it by proving that we can find $N$ such that, with high probability, one of the $N$ first colored vertices of height smaller than $|\mathcal{T}|/2$ will be colored in blue with an almost uncolored tree in front of it. This section is devoted to prove such proposition, namely Proposition 4. In the next section, we will reinforce this proposition showing that, in fact, we can find two such vertices instead of one.
**Proposition 4.** Let $\eta > 0$. Then, there exist $H, C, N, n_0 \ge 0$ such that if $|T| \ge n_0$, for any choices of vertices $w_1, \dots, w_C$ of height larger or equal to $|T| - 2H$ if $B_0 = \{o\}$ and $R_0 = \partial T \cup \{w_1, \dots, w_C\}$, we have

$$ \mathbb{P}(\forall i \le [1, N], \mathcal{A}_i^c) \le \eta. $$

*Proof Proposition 4.* For $v \in T$ and $r, h \ge 0$, we denote

$$ B(v, r) := \{w \in T, d(v, w) \le r\} \quad \text{and} \quad B(v, r, h) := \{w \in T, d(v, w) \le r \text{ and } |h| \ge h\} $$

the ball of center $v$ and radius $r$ and the vertices at height larger than $h$ in this ball. For $v_1, v_2 \in T$, we denote $v_1 \wedge v_2$ their common ancestor of maximal height. Recall that $R_0 = \partial T \cup \{w_1, \dots, w_C\}$ denotes the set of initial red vertices and $V_1^T, V_2^T, \dots$, are the vertices of $T$ of height strictly smaller than $|T|/2$ ranked by their coloring time. Since in this section, $T$ is fixed, to lighten the notation, we will just write $V_1, V_2, \dots$, instead of $V_1^T, V_2^T, \dots$, We introduce the following events

$$ \mathcal{E}_1 = \mathcal{E}_1(T, N, H, C, R_0) := \{\exists i \neq j \le N, V_i \wedge V_j \ge |T|/8\} $$

$$ \mathcal{E}_2 = \mathcal{E}_2(T, N, H, C, R_0) := \{\exists i \le N, |V_i| \le |T|/2 - H\} $$

$$ \mathcal{E}_3 = \mathcal{E}_3(T, N, H, C, R_0) := \{\exists i \le N, \exists k \le C, V_i \in B(w_k, |T|/2 + H)\} $$

$$ \mathcal{E}_4 = \mathcal{E}_4(T, N, H, C, R_0) := \{\forall i \le N, \mathcal{A}_i^c\} \cap \mathcal{E}_1^c \cap \mathcal{E}_2^c \cap \mathcal{E}_3^c. $$

Of course

$$ \mathbb{P}(\forall i \le [1, N], \mathcal{A}_i^c) \le \mathbb{P}(\mathcal{E}_1) + \mathbb{P}(\mathcal{E}_2) + \mathbb{P}(\mathcal{E}_3) + \mathbb{P}(\mathcal{E}_4). $$

The three first terms of the right hand side are easy to bound.

Indeed, to bound $\mathbb{P}(\mathcal{E}_1)$, observe that $V_i$ and $V_j$ are distributed as two distinct vertices chosen uniformly at random from the complete $K$-ary of height $\lceil T/2 - 1 \rceil$, excluding the root. It is easy to see that the height of the most recent common ancestor of such vertices is stochastically dominated by a geometric random variable with parameter $(K - 1)/K$. Hence, we get

$$ \mathbb{P}(\mathcal{E}_1) \le N^2 \mathbb{P}(V_1 \wedge V_2 \ge |T|/8) \le N^2 \frac{1}{K^{|T|/8}}. \quad (5) $$

Concerning $\mathbb{P}(\mathcal{E}_2)$, still using that $V_i$ is uniform on the complete $K$-ary of height $\lceil T/2 - 1 \rceil$ excluding the root and counting the number of vertices of height smaller than $|T|/2 - H$, we get

$$ \mathbb{P}(\mathcal{E}_2) \le N \frac{1}{K^H}. \quad (6) $$

For $\mathbb{P}(\mathcal{E}_3)$, recall that by hypothesis, for any $k \le C$, $|w_k| \ge |T| - 2H$ whereas, for any $i \ge 1$, we have $|V_i| \le \lceil T/2 - 1 \rceil$. So, if $z_k$ denotes the ancestor of $w_k$ at height $\lceil T/2 - 1 \rceil$, we have

$$ V_i \in B(w_k, |T|/2 + H) \implies V_i \in B(z_k, 3H). $$

Thus, we get

$$ \mathbb{P}(\mathcal{E}_3) \le CN \mathbb{P}(V_1 \in B(z_1, 3H)) \le CN \frac{K^{3H}}{K^{|T|/2-2}}, \quad (7) $$

still using that $V_1$ is uniform on the complete $K$-ary of height $\lceil T/2 - 1 \rceil$ excluding the root.

It remains to get an upper bound of $\mathbb{P}(\mathcal{E}_4)$, which requires more work. In the following, for a vertex $v$ and a time $t > 0$, we will say that the clock of $v$ has rung before time $t$ if $\tau_v < t$. We introduce the two following events:

(i) $\mathcal{F}_i := \{\text{At time } (\tau_{V_i})^{-}, \text{ strictly more than } C \text{ clocks have rung in } \mathcal{T}_{V_i}\}$

(ii) $\mathcal{G}_i := \{\text{A clock has rung in } B(V_i, |V_i|, |T|/2) \text{ before time } (\tau_{V_i})^{-}\}$.

**Lemma 5.** Assume that $H < |T|/4$. Then we have

$$ \mathcal{E}_4 \subset \{\forall i \le N, \mathcal{G}_i \cup \mathcal{F}_i\} \cap \mathcal{E}_1^c \cap \mathcal{E}_2^c. $$
Proof. Recalling the definition of $\mathcal{A}_i$ given in (3), we have $\mathcal{A}_i := \mathcal{X}_i \cap \mathcal{Y}_i \cap \mathcal{Z}_i$ where

$$ \mathcal{X}_i := \{|V_i| > |\mathcal{T}|/2 - H\} $$

$$ \mathcal{Y}_i := \{V_i \text{ is colored in blue}\} $$

$$ \mathcal{Z}_i := \{ \text{At time } (\tau_{V_i})^{-}, \mathcal{T}_{V_i} \text{ contains at most } C \text{ colored vertices that are not leaves, and each of them is at a distance at most } 2H \text{ from the leaves.} \} $$

Of course, $\mathcal{E}_2^c \subset \mathcal{X}_i$. Assume now that $\mathcal{G}_i^c \cap \mathcal{E}_2^c \cap \mathcal{E}_3^c$ occurs. Let us note that for $i \neq j \leq N$,

$$ d(V_i, V_j) = |V_i| + |V_j| - 2|V_i \wedge V_j| > |V_i| + \frac{|\mathcal{T}|}{2} - H - \frac{|\mathcal{T}|}{4} > |V_i|. $$

Thus, for any $j \leq N$, we have $V_j \notin B(V_i, |V_i|)$. Hence, by definition of the sequence $(V_j)_{j \leq N}$, at time $(\tau_{V_i})^{-}$, no clock of $B(V_i, |V_i|)$ at height smaller than $|\mathcal{T}|/2$ has rung. Moreover, since $\mathcal{G}_i^c$ holds, no clock in $B(V_i, |V_i|)$ at height larger than $|\mathcal{T}|/2$ have rung either. Therefore, no clock in $B(V_i, |V_i|)$ has rung. Using now that $\mathcal{E}_3^c$ holds and that $|V_i| < |\mathcal{T}|/2$, we also deduce that $B(V_i, |V_i|)$ cannot contain any point of $R_0$. Thus, the ball $B(V_i, |V_i|)$ contains no red point at time $(\tau_{V_i})^{-}$ but it does contain the root (which is blue). Consequently, $V_i$ becomes blue. Hence we obtain

$$ \mathcal{G}_i^c \cap \mathcal{E}_3^c \cap \mathcal{E}_2^c \subset \mathcal{Y}_i. $$

Moreover, if $\mathcal{G}_i^c \cap \mathcal{E}_2^c$ occurs, this implies that $|V_i| > |\mathcal{T}|/2 - H$ and no clock have rung in $B(V_i, |V_i|)$ before $\tau_{V_i}$, so in particular, any clock which rang in $\mathcal{T}_{V_i}$ before $\tau_{V_i}$ must have height larger than $|\mathcal{T}| - 2H$. So by definition of $\mathcal{F}_i$, we get that on $\mathcal{E}_2^c \cap \mathcal{G}_i^c \cap \mathcal{F}_i^c$, at most $C$ vertices have rung in $\mathcal{T}_{V_i}$ before $\tau_{V_i}$ and all at distance at most $2H$ of the leaves. Using again that if $\mathcal{E}_3^c$ holds, we get that the initial red points of $\mathcal{T}_{V_i}$ are only the leaves, and so

$$ \mathcal{E}_2^c \cap \mathcal{E}_3^c \cap \mathcal{G}_i^c \cap \mathcal{F}_i^c \subset \mathcal{Z}_i. $$

Combining all these remarks, we deduce that

$$ \mathcal{E}_2^c \cap \mathcal{G}_i^c \cap \mathcal{E}_3^c \cap \mathcal{F}_i^c \subset \mathcal{A}_i $$

which yields

$$ \mathcal{A}_i^c \subset \mathcal{E}_2 \cup \mathcal{G}_i \cup \mathcal{E}_3 \cup \mathcal{F}_i $$

and so

$$ \mathcal{A}_i^c \cap \mathcal{E}_2^c \cap \mathcal{E}_3^c \subset \mathcal{G}_i \cup \mathcal{F}_i. $$

Hence, we get

$$ \mathcal{E}_4 \subset \{\forall i \leq N, \mathcal{G}_i \cup \mathcal{F}_i\} \cap \mathcal{E}_1^c \cap \mathcal{E}_2^c. $$

□

Let us now find an upper bound on the probability of $\{\forall i \leq N, \mathcal{G}_i \cup \mathcal{F}_i\} \cap \mathcal{E}_1^c \cap \mathcal{E}_2^c$. Recall that $\tau_v$ denotes the coloring time of the vertex $v$. Let define $\mathcal{H}$ the sigma field given by the coloring time of the vertex at height strictly smaller than $|\mathcal{T}|/2$ namely

$$ \mathcal{H} := \sigma(\{\tau_v, |v| < |\mathcal{T}|/2\}) $$

so that $\mathcal{E}_1, \mathcal{E}_2, \mathcal{E}_3 \in \mathcal{H}$. Let also denote, for $i \leq N$, $\tau_i$ the coloring time of $V_i$, i.e. $\tau_i = \tau_{V_i}$. Note that $\tau_i$ is $\mathcal{H}$-measurable. Let us note that for any $i \leq N$, if $u \in B(V_i, |V_i|, |\mathcal{T}|/2)$,

$$ 2|u \wedge V_i| = |u| + |V_i| - d(u, V_i) \geq |u| \geq \frac{|\mathcal{T}|}{2} $$

and of course, if $u \in \mathcal{T}_{V_i}$, then $|u \wedge V_i| = |V_i|$. Thus, if we still assume that $H < |\mathcal{T}|/4$, on the event $\mathcal{E}_2^c$, we get for all $u \in B(V_i, |V_i|, |\mathcal{T}|/2) \cup \mathcal{T}_{V_i}$

$$ |u \wedge V_i| > \frac{|\mathcal{T}|}{8}. $$

In particular, this implies that if $\mathcal{E}_1^c \cap \mathcal{E}_2^c$ holds, for any $i \neq j \leq N$, the set of vertices $B(V_i, |V_i|, |\mathcal{T}|/2) \cup \mathcal{T}_{V_i}$ and $B(V_j, |V_j|, |\mathcal{T}|/2) \cup \mathcal{T}_{V_j}$ are disjoint. Therefore, conditionally on $\mathcal{H}$, on the event $\mathcal{E}_1^c \cap \mathcal{E}_2^c$, the events $\mathcal{F}_i \cup \mathcal{G}_i$, $i \leq N$ are independent. Besides, we have

$$ |B(V_i, |V_i|, |\mathcal{T}|/2)| \leq (K+1)K^{|V_i|} \text{ and } |\mathcal{T}_{V_i}| \leq K^{|\mathcal{T}|/2+H+1}. $$
Hence, conditionally on $\mathcal{H}$, on the event $\mathcal{E}_1^c \cap \mathcal{E}_2^c$, the time when the first clock rings in $B(V_i, |V_i|, |\mathcal{T}|/2)$, namely $\min\{\tau_v, v \in B(V_i, |V_i|, |\mathcal{T}|/2)\}$ is stochastically larger than an exponential random variable with parameter $(K+1)K^{|V_i|}$ and the number of clocks that have rung before time $\tau_i$ in $|\mathcal{T}V_i|$ is bounded by a binomial random variable with parameter $(K^{|\mathcal{T}|/2+H+1}, 1-e^{-\tau_i})$. Let $\sigma_h$ denote an exponential random variable with parameter $(K+1)K^h$ and $Z_t$ a binomial random variable with parameter $(K^{|\mathcal{T}|/2+H+1}, 1-e^{-t})$. We get

$$ 
\begin{aligned}
\mathbb{P}(\mathcal{E}_4|\mathcal{H}) &\le 1_{\mathcal{E}_1^c \cap \mathcal{E}_2^c} \prod_{i=1}^N \mathbb{P}(\sigma_{|V_i|} \le \tau_i \text{ or } Z_{\tau_i} \ge C | \mathcal{H}) \\
&= 1_{\mathcal{E}_1^c \cap \mathcal{E}_2^c} \prod_{i=1}^N (1 - \mathbb{P}(\sigma_{|V_i|} > \tau_i | \tau_i) \mathbb{P}(Z_{\tau_i} < C | \tau_i)).
\end{aligned}
$$

We write, for a fixed $A > 0$,

$$ \mathbb{P}(Z_{\tau_i} < C | \tau_i) \ge 1_{\tau_i \le A.K^{-|\tau|/2}} \mathbb{P}(Z_{A.K^{-|\tau|/2}} < C). $$

We set $q_{A,C,|\mathcal{T}|} := \mathbb{P}(Z_{A.K^{-|\tau|/2}} < C)$ so that

$$ \mathbb{P}(\mathcal{E}_4|\mathcal{H}) \le 1_{\mathcal{E}_1^c \cap \mathcal{E}_2^c} \prod_{i=1}^N \left(1 - \exp\left(-\left(K+1\right)K^{|V_i|}\tau_i\right)q_{A,C,|\mathcal{T}|}1_{\tau_i \le A.K^{-|\tau|/2}}\right). $$

Let denote $m$ the largest integer strictly smaller than $|\mathcal{T}|/2$. Note that $(\tau_i)_{i \le N}$ and $(V_i)_{i \le N}$ are independent. Moreover, $V_1, \dots, V_N$ are $N$ distinct vertices of $\mathcal{T}$ uniformly chosen with height smaller or equal to $m$ not equal to the root and the random variables $(\tau_i - \tau_{i-1})_{i \le N}$ are independent and with exponential law of parameter $\text{Vol}(\mathcal{T}_{\le m}) - i$.

Since, $\text{Vol}(\mathcal{T}_{\le m}) := K(K^m - 1)/(K - 1)$, we get, for any $i \ge 1$ and $h < m$

$$ \mathbb{P}(|V_i| = m - h) = \frac{K^{m-h}}{\text{Vol}(\mathcal{T}_{\le m})} = \frac{(K-1)K^{m-h}}{K(K^m - 1)} \ge \frac{1}{2K^h}. $$

Moreover, for any $h_i \ge 1$, we have

$$ 
\begin{aligned}
\mathbb{P}((|V_1|, \dots, |V_N|) = (h_1, \dots, h_N)) &\le \left( \frac{\text{Vol}(\mathcal{T}_{\le m})}{\text{Vol}(\mathcal{T}_{\le m}) - N} \right)^N \prod_{i=1}^N \mathbb{P}((|V_i| = h_i) \\
&\le \left(1 - \frac{N}{K^m}\right)^{-N} \prod_{i=1}^N \mathbb{P}((|V_i| = h_i) \\
&\le \left(1 - \frac{N}{K^{|\mathcal{T}|/2-1}}\right)^{-N} \prod_{i=1}^N \mathbb{P}((|V_i| = h_i).
\end{aligned}
$$

Thus, we get

$$ 
\begin{aligned}
\mathbb{P}(\mathcal{E}_4|(\tau_i)_{i \le N}) &\le \sum_{h_1, \dots, h_N \ge 1} \mathbb{P}((|V_1|, \dots, |V_N|) = (h_1, \dots, h_N)) \prod_{i=1}^N \left(1 - e^{-\tau_i(K+1)K^{h_i}} q_{A,C,|\mathcal{T}|} 1_{\tau_i \le A.K^{-|\tau|/2}}\right) \\
&\le \left(1 - \frac{N}{K^{|\mathcal{T}|/2-1}}\right)^{-N} \sum_{h_1, \dots, h_N \ge 0} \prod_{i=1}^N \left(\mathbb{P}(|V_i| = h_i)(1 - e^{-\tau_i(K+1)K^{h_i}} q_{A,C,|\mathcal{T}|} 1_{\tau_i \le A.K^{-|\tau|/2}})\right) \\
&\le \left(1 - \frac{N}{K^{|\mathcal{T}|/2-1}}\right)^{-N} \prod_{i=1}^N \mathbb{E}\left(1 - e^{-\tau_i(K+1)K^{|V_i|}} q_{A,C,|\mathcal{T}|} 1_{\tau_i \le A.K^{-|\tau|/2}}|(\tau_i)_{i \le N}\right) \\
&= \left(1 - \frac{N}{K^{|\mathcal{T}|/2-1}}\right)^{-N} \prod_{i=1}^N \left(1 - \mathbb{E}\left(e^{-\tau_i(K+1)K^{|V_i|}}|(\tau_i)_{i \le N}\right) q_{A,C,|\mathcal{T}|} 1_{\tau_i \le A.K^{-|\tau|/2}}\right) \\
&\le \left(1 - \frac{N}{K^{|\mathcal{T}|/2-1}}\right)^{-N} \prod_{i=1}^N \left(1 - \left(\sum_{h=0}^L \frac{1}{2K^h} e^{-\tau_i(K+1)K^{m-h}}\right) q_{A,C,|\mathcal{T}|} 1_{\tau_i \le A.K^{-|\tau|/2}}\right)
\end{aligned}
$$
valid for any $L < m$ (recall that $m$ is the largest integer strictly smaller than $|T|/2$).

We now use that the random variables $(\tau_i - \tau_{i-1})_{i \le N}$ are independent and with exponential law of parameter $Vol(T_{\le m}) - i$. If $i \le Vol(T_{\le m})/2$, we have

$$ \mathrm{Vol}(T_{\le m}) - i \ge \mathrm{Vol}(T_{\le m})/2 \ge K^{m-1} \ge K^{|T|/2-2} $$

Thus, if $N \le K^m/2$, the sequence $(K^{|T|/2-2}(\tau_i - \tau_{i-1}))_{i \le N}$ is stochastically larger than a sequence $(\epsilon_i)_{i \le N}$ of i.i.d. exponential random variables with parameter 1. Let $\sigma_i = \sum_{k=1}^i \epsilon_k$. We get

$$ \begin{aligned} \mathbb{P}(\mathcal{E}_4) & \le \left(1 - \frac{N}{K^{|T|/2-1}}\right)^{-N} \mathbb{E} \left( \prod_{i=1}^{N} \left(1 - \left(\sum_{h=0}^{L} \frac{1}{K^h} e^{-\tau_i (K+1) K^{|T|/2-h}}\right) q_{A,C,|T|} 1_{\tau_i \le A \cdot K^{-|T|/2}}\right) \right) \\ & \le \left(1 - \frac{N}{K^{|T|/2-1}}\right)^{-N} \mathbb{E} \left( \prod_{i=1}^{N} \left(1 - \left(\sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}}\right) q_{A,C,|T|} 1_{\sigma_i \le A \cdot K^{-2}}\right) \right). \end{aligned} $$

We then use the following lemma, whose proof is postponed until the end of this section.

**Lemma 6.** Let $\eta > 0$. Then, there exists $N, L > 0$, such that is $(\epsilon_i)_{i \le N}$ of i.i.d. exponential random variable with parameter 1 and $\sigma_i = \sum_{k=1}^i \epsilon_k$, we have

$$ \mathbb{E} \left( \prod_{i=1}^{N} \left( 1 - \sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}} \right) \right) \le \eta/5. \quad (8) $$

We now finish the proof of Proposition 4 assuming that Lemma 6 holds. Fix $\eta > 0$ and $N, L$ such that (8) holds. Since for each $i \le N$, $1_{\sigma_i \le A \cdot K^{-2}}$ tends a.s. to 1 as $A$ tends to infinity, by dominated convergence Theorem, there exists $A$ large enough such that

$$ \mathbb{E} \left( \prod_{i=1}^{N} \left( 1 - 1_{\sigma_i \le A \cdot K^{-2}} \sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}} \right) \right) \le \eta/4. $$

Using (6), fix now $H$ such that

$$ \mathbb{P}(\mathcal{E}_2) \le N \frac{1}{K^H} \le \eta/3. $$

Recall that

$$ q_{A,C,|T|} := \mathbb{P}(Z_{A \cdot K^{-|T|/2}} < C) \text{ where } Z_{A \cdot K^{-|T|/2}} \sim \text{Bin}(K^{|T|/2+H+1}, 1 - e^{-A \cdot K^{-|T|/2}}). $$

Thus

$$ 1 - q_{A,C,|T|} = \mathbb{P}(Z_{A \cdot K^{-|T|/2}} \ge C) \le \frac{\mathbb{E}(Z_{A \cdot K^{-|T|/2}})}{C} \le \frac{AK^{H+1}}{C}. $$

Thus, for fixed $A$ and $H$, we can find $C$ large enough such that $q_{A,C,|T|}$ is close to 1. Using again dominated convergence Theorem, we deduce the existence of a $C$, such that

$$ \mathbb{E} \left( \prod_{i=1}^{N} \left( 1 - \left( \sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}} \right) q_{A,C,|T|} 1_{\sigma_i \le A \cdot K^{-2}} \right) \right) \le \eta/3 $$

and so, for this choice of $N, H, C$, we get that $\mathbb{P}(\mathcal{E}_4) \le \eta/2$ if $|T|$ is large enough. Combining this with (5) and (7), we get that for this choice of $H, C, N$ and for $|T|$ large enough,

$$ \mathbb{P}(\forall i \le [1, N], A_i^c) \le \eta. $$

□

**Proof of Lemma 6.** Let us note that $\sigma_i$ is the sum of $i$ i.i.d. exponential random variables, thus $\sigma_i/i$ tends a.s. to 1 as $i$ tends to infinity. Hence, we can find $D > 0$ such that

$$ \mathbb{P}(\exists i \ge 1, K^2(K+1)\sigma_i \ge Di) \le \eta/10. $$
With this choice for $D$, we get

$$ \mathbb{E} \left( \prod_{i=1}^{N} \left( 1 - \sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}} \right) \right) \le \eta/10 + \prod_{i=1}^{N} \left( 1 - \sum_{h=0}^{L} \frac{1}{K^h} e^{-D_i K^{-h}} \right). $$

Let define

$$ M_{L,N} := \prod_{i=1}^{N} \left( 1 - \sum_{h=0}^{L} \frac{1}{K^h} e^{-D_i K^{-h}} \right) $$

and

$$ M_{\infty} := \prod_{i=1}^{\infty} \left( 1 - \sum_{h=0}^{\infty} \frac{1}{K^h} e^{-D_i K^{-h}} \right). $$

Since $M_{L,N}$ tends to $M_{\infty}$ when $L, N$ tend to infinity, it only remains to show that $M_{\infty} = 0$ as it will imply that for $L$ and $N$ large enough, $M_{L,N} \le \eta/10$ as required. Indeed, we have

$$ \log M_{\infty} = \sum_{i=1}^{\infty} \log \left( 1 - \sum_{h=0}^{\infty} \frac{1}{K^h} e^{-D_i K^{-h}} \right) \le - \sum_{i=1}^{\infty} \sum_{h=0}^{\infty} \frac{1}{K^h} e^{-D_i K^{-h}} $$

and

$$ \sum_{h=0}^{\infty} \sum_{i=1}^{\infty} \frac{1}{K^h} e^{-D_i K^{-h}} = \sum_{h=0}^{\infty} \frac{1}{K^h} \frac{e^{-D K^{-h}}}{1 - e^{-D K^{-h}}} = \infty $$

since

$$ \lim_{h \to \infty} \frac{1}{K^h} \frac{e^{-D K^{-h}}}{1 - e^{-D K^{-h}}} = \frac{1}{D}. $$

This yields that $M_{\infty} = 0$ and so that $M_{L,N}$ tends to 0 as $N$ and $L$ tends to infinity. $\square$

## 1.3 Proof of Proposition 3

Hence, we have established Proposition 4 which shows that, with high probability, one of the $N$-first colored vertices of height smaller than $|T|/2$ will be colored in blue with an almost uncolored tree in front of it. In fact, Proposition 3 asserts that, with high probability, two such vertices exist. So we reinforce Proposition 4 proving the following proposition.

**Proposition 7.** Let $\eta > 0$. Then, there exist $H, C, N, N', n_0 \ge 0$ such that if $|T| \ge n_0$, for any choices of vertices $w_1, \dots, w_C$ of height larger or equal to $|T| - 2H$ if $B_0 = \{o\}$ and $R_0 = \partial T \cup \{w_1, \dots, w_C\}$, we have

$$ \mathbb{P}(\forall i \le [1, N], \mathcal{A}_i^c) \le \eta. \qquad (9) $$

$$ \mathbb{P}(\forall i \in [N+1, N'], \mathcal{A}_i^c) \le \eta. \qquad (10) $$

*Proof.* For $N < N'$, we introduce the following events

$$ \mathcal{E}_1' = \mathcal{E}_1(\mathcal{T}, N', H, C, R_0) := \{\exists i \neq j \le N', V_i \wedge V_j \ge |\mathcal{T}|/8\}, $$

$$ \mathcal{E}_2' = \mathcal{E}_2(\mathcal{T}, N', H, C, R_0) := \{\exists i \le N', |V_i| \le |\mathcal{T}|/2 - H\}, $$

$$ \mathcal{E}_3' = \mathcal{E}_3(\mathcal{T}, N', H, C, R_0) := \{\exists i \le N', \exists k \le C, V_i \in B(w_k, |\mathcal{T}|/2 + H)\}, $$

$$ \mathcal{E}_4' = \mathcal{E}_4'(\mathcal{T}, N, N', H, C, R_0) := \{\forall i \le N, \mathcal{A}_i^c\} \cap \mathcal{E}_1'^c \cap \mathcal{E}_2'^c \cap \mathcal{E}_3'^c, $$

$$ \mathcal{E}_5' = \mathcal{E}_5'(\mathcal{T}, N, N', H, C, R_0) := \{\forall N < i \le N', \mathcal{A}_i^c\} \cap \mathcal{E}_1'^c \cap \mathcal{E}_2'^c \cap \mathcal{E}_3'^c. $$

Note that $\mathbb{P}(\mathcal{E}_4') \le \mathbb{P}(\mathcal{E}_4)$ and using the same arguments as in the proof of Proposition 4, we can show that

$$ \mathbb{P}(\mathcal{E}_5') \le \left(1 - \frac{N'}{K^{|T|/2-1}}\right)^{-N'} \mathbb{E} \left( \prod_{i=N+1}^{N'} \left(1 - \left(\sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}}\right) q_{A,C,|T|} 1_{\sigma_i \le A \cdot K^{-2}}\right) \right) $$
where $\sigma_i = \sum_{k=1}^i \varepsilon_k$ with $(\varepsilon_i)_{i \le N'}$ i.i.d. exponential random variables with parameter 1. Let $\eta > 0$ and let $N, N', L > 0$ with $N' > N$ such that is $(\varepsilon_i)_{i \le N'}$ of i.i.d. exponential random variable with parameter 1 and $\sigma_i = \sum_{k=1}^i \varepsilon_k$, we have

$$ \mathbb{E} \left( \prod_{i=1}^{N} \left( 1 - \sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}} \right) \right) \le \eta/5, $$

$$ \mathbb{E} \left( \prod_{i=N+1}^{N'} \left( 1 - \sum_{h=0}^{L} \frac{1}{K^h} e^{-\sigma_i (K+1) K^{2-h}} \right) \right) \le \eta/5. $$

Fixing $A, H$, and $C$ large enough in the same way as in the proof of Proposition 4, we get that, for this choice of $(N, N', H, C)$, if $|T|$ is large enough, (9) and (10) hold simultaneously. $\square$

*Proof of Proposition 3.* We can now conclude the proof of Proposition 3. Let $H, C, N, N', n_0$ such that Proposition 7 holds. This shows that, if $|T| \ge n_0$, with probability larger than $1 - 2\eta$, there exist $i < N < j$ such that $A_i$ and $A_j$ hold. Moreover, recall that $V_1, V_2, \dots$ are the vertices of height smaller than $|T|/2$ ranked by their coloring time. Thus, we have

$$ \mathbb{P}(\exists i < j \le N', \mathcal{T}_{V_i} \cap \mathcal{T}_{V_j} \neq \emptyset) \le N'^2 \mathbb{P}(\mathcal{T}_{V_1} \cap \mathcal{T}_{V_1} \neq \emptyset) \le \frac{|T|N'^2}{K^{|T|/2-1}}. $$

Hence, when $|T|$ tends to infinity, the probability that the sub-trees rooted at the $N'$ first colored vertices of height smaller than $|T|/2$ are all disjoint tends to 1. Hence, we get, for $|T|$ large enough

$$ \mathbb{P}(\exists i < j, \mathcal{T}_{V_i} \cap \mathcal{T}_{V_j} = \emptyset \text{ and } A_i \cap A_j) \ge 1 - 3\eta. $$

$\square$

# 2 The red vertices have a positive probability to reach the root

The aim of this section is to prove (2) of Theorem 1 i.e. to show that a child of the root ends up red with a probability bounded from below independently of the size of the tree. As explained in the introduction, we establish this result by considering the coloring process on the infinite K-ary tree and by proving Proposition 2.

The proof is independent of the results obtained in Section 1, and the only common notation between the two sections is the following:

* $\mathcal{T}_\ell$ denotes the finite regular tree with $K$ children per vertex and height $\ell$ and $\mathcal{T}_\infty$ the infinite regular tree with $K$ children per vertex.

* $o$ denotes the root of the tree.

* For $v \in \mathcal{T}_\infty$, $\mathcal{T}_v$ denotes the sub-tree rooted at $v$, consisting of all its descendants.

Moreover, we still consider the coloring process in continuous time and for $v$ a vertex, we denote $\tau_v$ its coloring time.

## 2.1 The path of ancestors

Let us consider the coloring process on $\mathcal{T}_\ell$ the finite regular tree with $K$ children per vertex and height $\ell$. For a vertex $v_1$ in $\mathcal{T}_\ell$, the coloring process naturally defines a path of ancestors $\Gamma_\ell(v_1) := (v_1^\ell, v_2^\ell, v_3^\ell, \dots, v_{L_\ell}^\ell)$ such that, for each $i$, the vertex $v_i^\ell$ has inherited the color of $v_{i+1}^\ell$. Note that, by definition of the model, $v_{i+1}^\ell$ satisfies the following two properties:

* $v_{i+1}^\ell$ is a vertex of $\mathcal{T}_\ell$ that has been colored before $v_i^\ell$.

* At time when $v_i^\ell$ is colored, no vertex in the ball $\{u \in \mathcal{T}_\ell, d(v_i^\ell, u) < d(v_i^\ell, v_{i+1}^\ell)\}$ has already been colored.
• The vertex $v_{i+1}^\ell$ is chosen uniformly at random among the vertices satisfying the two properties above.

By construction, the last step $v_{L_\ell}^\ell$ of this path is a vertex with no ancestor, so $v_{L_\ell}^\ell$ is either a leaf of $\mathcal{T}_\ell$ or the root. Note that $v_1$ ends up red if the path $\Gamma_\ell(v_1)$ ends at a leaf of $\mathcal{T}_\ell$ and blue if the path ends at the root. Hence, if $m_\ell$ denotes the minimal height of a red vertex as defined in Theorem 1, we get

$$m_\ell = \inf\{|v|, \Gamma_\ell(v) \text{ does not end up at the root}\}.$$

Moreover, note that for $\ell < \ell'$, $\Gamma_\ell(v_1)$ and $\Gamma_{\ell'}(v_1)$ coincide until $\Gamma_\ell(v_1)$ reaches a leaf of $\mathcal{T}_\ell$. This remark allows us to define the path of ancestors of $v_1$ on the infinite K-ary tree $\Gamma(v_1) = (v_1, v_2, \dots, v_L)$ by

$$L := \lim_{\ell \to \infty} L_\ell \in [1, \infty],$$

$$v_i := v_i^\ell \quad \text{for } i < L \text{ for } \ell \text{ such that } i < L_\ell,$$

$$v_L := o \quad \text{if } L < \infty,$$

(if $L = \infty$, then $\Gamma(v_1)$ is the sequence $(v_i)_{i \ge 1}$). We get that $v_1 \in B^{(\infty)}$, the final blue set on the infinite tree if $L < \infty$ and $v_1 \in R^{(\infty)}$ otherwise. Note also that $(m_\ell)_{\ell \ge 1}$ converges a.s. to

$$m_\infty = \inf\{|v|, \Gamma(v) \text{ does not end up at the root}\}.$$

So Proposition 2 is equivalent to

$$\lim_{|v| \to \infty} \mathbb{P}(\Gamma(v) \text{ does not end up at the root}) = 1 \quad (11)$$

and if $v$ is a child of the root,

$$\mathbb{P}(\Gamma(v) \text{ does not end up at the root}) > 0. \quad (12)$$

We begin by proving that for any $v \neq o$, (12) holds. In Section 2.3, then we explain how to adapt our argument to show that the probability that $\Gamma(v)$ does not end up at the root in fact tends to 1 as the height of $v$ increases.

## 2.2 A slightly different construction

For a vertex $v_1 \in \mathcal{T}_\infty$, we present a construction of a random set of vertices $W_\infty := W_\infty(v_1)$ associated with $v_1$. If $v_1$ ends up red, this random set coincides with the set of vertices whose coloring time must be known in order to determine the path of ancestors of $v_1$. In particular, we will see that the probability that $v_1$ ends up red is equal to the probability that this random set does not contain the root. We begin with a definition.

**Definition 8.** Let $v \in \mathcal{T}_\infty$ and let $\mathcal{S}$ be an infinite subset of $\mathcal{T}_\infty$. We say that $(u_j)_{j \ge 1}$ is a uniform increasing indexing of the vertices of $\mathcal{S}$ centered at $v$ if it is chosen uniformly at random among all sequences $(u_j)_{j \ge 1}$ such that

• (indexing of $\mathcal{S}$) $\{u_j : j \ge 1\} = \mathcal{S}$ and $u_j \neq u_i$ for $j \neq i$;

• (increasing) $j < i \implies d(v, u_j) \le d(v, u_i)$.

Fix $v_1 \in \mathcal{T}_\infty$ and set $V_1 := v_1$, $W_1 := \{v_1\}$. Let $(\tau_i)_{i \ge 1}$ be an i.i.d. sequence with exponential law, and let $(T_n)_{n \ge 1}$ denote its lower record process, that is,

$$T_1 = 1 \quad \text{and for } n \ge 1, \quad T_{n+1} := \inf\{k > T_n, \tau_k < \tau_{T_n}\}.$$

Finally, let $I_1 = 1$ and $I_n := T_n - T_{n-1}$ the time between two successive records.

Let $(u_j^1, j \ge 1)$ be a uniform increasing indexing of the vertices of $\mathcal{T}_\infty \setminus W_1$ centered at $v_1$. Set

$$V_2 = u_{I_2}^1 \quad W_2 := W_1 \cup \{u_j^1, j \le I_2\}.$$
By induction, assume that $V_n$ and $W_n$ have been constructed. Let $(u_j^n, j \ge 1)$ be a uniform increasing indexing of the vertices of $T_\infty \setminus W_n$ centered at $V_n$. Set

$$V_{n+1} = u_{I_{n+1}}^n \quad W_{n+1} := W_n \cup \{u_j^n, j \le I_{n+1}\}.$$

Finally, set

$$W_\infty := W_\infty(v_1) := \bigcup_{n \ge 1} W_n.$$

We claim the following proposition.

**Proposition 9.** We have

$$\mathbb{P}(v_1 \text{ ends red in the infinite model}) = \mathbb{P}(o \notin W_\infty).$$

*Proof.* Recall that $v_1$ ends red in the infinite model if its path of ancestors does not end at the root. To determine the first vertex $v_2$ in the path of ancestors of $v_1$, it is sufficient to look at the sequence of vertices $(u_j^1, j \ge 1)$ in increasing order and to stop as soon as we found a vertex with coloring time smaller than the coloring time of $v_1^3$. Let $j_0$ the unique integer such that $u_{j_0}^1$ is the root. Let $Y$ be the set of vertices whose time we need to reveal to find $v_2$ and $J$ the cardinal of this set. Note that $J \le j_0$ and $v_2 = o$ i.f.f. $J = j_0$. Moreover, $v_2 \in Y$. Since the sequence of coloring times of the vertices are i.i.d. with exponential distribution except for the root, we can consider that $\tau_{v_1} = \tau_1$ and $\tau_{u_j^1} = \tau_{j+1}$ for $j < j_0$ so that $J = I_2 \wedge j_0$ and $Y \subset W_2$. In particular

$$o \notin W_2 \implies o \notin Y \implies v_2 \neq o.$$

On the other hand,

$$o \in W_2 \implies I_2 \ge j_0 \implies J = j_0 \implies v_2 = o.$$

Thus, we get

$$o \notin W_2 \iff v_2 \neq o.$$

Using can easily repeat these arguments to prove by induction that

$$o \notin W_n \iff v_n \neq o \text{ (with the convention } v_n = o \text{ if } n > L)$$

and so

$$o \notin W_\infty \iff \forall n \ge 1 \ v_n \neq o.$$

□

To establish (12) we need now to prove that with positive probability $W_\infty$ does not contain the root. For $n \ge 1$, let define $R_n$ as the graph distance between $V_n$ and $V_{n-1}$:

$$R_n := d(V_n, V_{n-1}). \qquad (13)$$

Note that $R_n$ is the unique integer such that

$$\#\{u \in T_\infty \setminus W_{n-1}, d(V_{n-1}, u) \le R_n\} \ge I_n,$$

$$\#\{u \in T_\infty \setminus W_{n-1}, d(V_{n-1}, u) < R_n\} < I_n.$$

Using these equations, we can give a precise estimate of $R_n$ in terms of $I_n$.

**Lemma 10.** For any $n \ge 1$, we have the following properties

* $V_n \in W_n$.

* $W_n$ is a connected subset of $T_\infty$.

* There exists at least a child $u$ of $V_n$ such that $T_u \cap W_n = \emptyset$.

<footnote n="3">³since ties are broken uniformly at random and the increasing indexing $(u_j^1, j \ge 1)$ is also uniform among the increasing indexing.</footnote>
Moreover, we have, for any $n \ge 1$

$$ \frac{I_n}{K+1} \le K^{R_n} \le K^2 I_n. \qquad (14) $$

*Proof.* Let us first note that by construction $V_n \in W_n$ for all $n \ge 1$. Let us now prove by induction on $n$ that $W_n$ is connected and there exists at least a child $u$ of $V_n$ such that $T_u \cap W_n = \emptyset$. It holds for $W_1$. Assume it holds for $n-1$. Let

$$ Z_l := W_{n-1} \cup \{u_j^{n-1}, j \le l\} $$

so that $Z_0 = W_{n-1}$ and $Z_{I_n} = W_n$. Since $V_{n-1} \in W_{n-1}$ and $u_j^{n-1}$ is an increasing indexing centered at $V_{n-1}$, we see by induction on $l$ that $Z_l$ is a connected subset for all $0 \le l \le I_n$ and so $W_n$ is connected. Moreover, $W_n = V_n \cup Z_{I_n-1}$ and $Z_{I_n-1}$ is a connected subset which does not contain $V_n$. So necessarily at most one sub-tree $T_u$, for $u$ child of $V_n$ intersects $W_n$. Since all vertices of $T$ have at least two children, this yields the result.

Let us now prove (14). On one hand, we have

$$ \begin{aligned} I_n &\le \#\{u \in T_\infty \setminus W_{n-1}, d(V_{n-1}, u) \le R_n\} \\ &\le \#\{u \in T_\infty \setminus \{V_{n-1}\}, d(V_{n-1}, u) \le R_n\} \\ &\le \sum_{i=0}^{R_n-1} (K+1) \cdot K^i \le (K+1)K^{R_n}. \end{aligned} $$

On the other hand, denoting $w$ a child of $V_{n-1}$ such that $T_w$ does not intersect $W_{n-1}$, we write

$$ \begin{aligned} I_n &> \#\{u \in T_\infty \setminus W_{n-1}, d(V_{n-1}, u) < R_n\} \\ &\ge \#\{u \in T_w, d(V_{n-1}, u) < R_n\} \\ &= \sum_{i=0}^{R_n-2} K^i \ge K^{R_n-2}. \end{aligned} $$

□

Let $v$ is a fixed vertex of $T_\infty$ not equal to the root. To give a lower bound of the probability of $\{o \notin W_\infty(v)\}$, we use the following proposition.

**Proposition 11.** Let $(V_i)_{i \ge 1}$ and $(W_i)_{i \ge 1}$ the vertices and the set of vertices associated to $v$. For $1 \le i \le 5$, let $w_i$ be a vertex of $T_\infty$ such that $w_1 = v$, $|w_i| = 2|w_{i-1}|$ and $w_i \in T_{w_{i-1}}$. Let

$$ A := \{ \text{For } 1 \le i \le 5, \ V_i = w_i \text{ and } W_i = W_{i-1} \cup B(V_{i-1}, |V_{i-1}| - 1) \cup \{w_i\} \}, $$

$$ B := \{ \forall n > 5, \frac{n}{2} \le \log(K)R_n \le 2n \text{ and } |V_n| \ge |V_{n-1}| + \frac{R_n}{2} \}. $$

Then, we have

$$ A \cap B \subset \{o \notin W_\infty\}. $$

*Proof.* The event $A$ insures that $W_5$ does not contain the root and that $|V_5| \ge 2^5$. Assume now that $B$ also holds and let us prove by induction that $\{o \notin W_n\}$. For $n > 5$, we have

$$ |V_n| \ge |V_{n-1}| + \frac{n}{4 \log K} $$

which yields

$$ |V_n| \ge |V_5| + \sum_{i=6}^{n} \frac{i}{4 \log K} \ge 2^5 + (n(n+1) - 30) \frac{1}{8 \log K}. $$

Thus, using that $R_n \log K \le 2n$, we get

$$ |V_n| - R_{n+1} \ge 32 + (n(n+1) - 30 - 16(n+1)) \frac{1}{8 \log K}. $$
The right part of the previous equation attains its minimum for $n = 7$, thus we get

$$|V_n| - R_{n+1} \geq 32 - \frac{95}{8 \log K} \geq 32 - \frac{95}{8 \log 2} > 0.$$

Since $R_{n+1} = d(V_n, V_{n+1})$, this implies in particular that $o \notin W_{n+1} \setminus W_n$ and so, by induction that $o \notin W_{\infty}$. $\square$

It remains now to prove that $\mathbb{P}(A \cap B) > 0$. To this aim, We introduce the filtration $(\mathcal{F}_n)_{n \geq 1}$ given by

$$\mathcal{F}_n := \sigma((I_k)_{k \geq 1}, (u_j^i)_{j \geq 1}, i < n) \qquad (15)$$

where we recall that $(I_k)_{k \geq 1}$ are the inter-arrivals of the record process such that $I_k$ is equal to the number of vertices we must examine to determine the ancestor of $V_{k-1}$ and $(u_j^i)_{j \geq 1}$ is the increasing indexing centered at $V_k$ which determines the ordering for the discovery of the vertices around $V_k$.

**Lemma 12.** For any $n \geq 1$ $V_n$, $W_n$ and $R_{n+1}$ are $\mathcal{F}_n$-measurable. In particular, $A \in \mathcal{F}_5$. Moreover the law of $V_{n+1}$ knowing $\mathcal{F}_n$ is the uniform law on the set of vertices $u \in \mathcal{T}_{\infty} \setminus W_n$ such that $d(V_n, u) = R_{n+1}$.

*Proof.* The measurability with respect to $\mathcal{F}_n$ of $V_n$, $W_n$ and $R_{n+1}$ is a direct consequence of the construction. Since $A \in \sigma(V_i, W_i, i \leq 5)$, this yields that $A \in \mathcal{F}_5$. The fact that $V_{n+1}$ knowing $\mathcal{F}_n$ is uniform on the set of vertices $u \in \mathcal{T}_{\infty} \setminus W_n$ such that $d(V_n, u) = R_{n+1}$ is due to the fact that $(u_j^i)_{j \geq 1}$ is chosen uniformly among increasing indexing of the vertices of $\mathcal{T}_{\infty} \setminus W_n$ centered at $V_n$ and the rule we chose to break the ties when two colored vertices are at the same distance of $V_n$. $\square$

**Proposition 13.** For any $n \geq 1$

$$\mathbb{P}(|V_{n+1}| \geq |V_n| + \frac{R_{n+1}}{2} | \mathcal{F}_n) \geq 1 - K^{-\frac{R_{n+1}}{4}+1}.$$

*Proof.* Conditionally on $\mathcal{F}_n$, $V_{n+1}$ is uniform on the set of vertices $u \in \mathcal{T}_{\infty} \setminus W_n$ such that $d(V_n, u) = R_{n+1}$. Hence,

$$\mathbb{P}(|V_{n+1}| < |V_n| + \frac{R_{n+1}}{2} | \mathcal{F}_n) = \frac{\#\{u \in \mathcal{T}_{\infty} \setminus W_n, d(V_n, u) = R_{n+1}, |u| < |V_n| + \frac{R_{n+1}}{2}\}}{\#\{u \in \mathcal{T}_{\infty} \setminus W_n, d(V_n, u) = R_{n+1}\}} \qquad (16)$$

First, recalling that there exists a child $w$ of $V_n$ such that $\mathcal{T}_w$ does not intersect $W_n$, we get

$$\#\{u \in \mathcal{T}_{\infty} \setminus W_n, d(V_n, u) = R_{n+1}\} \geq \#\{u \in \mathcal{T}_w, W_n, d(V_n, u) = R_{n+1}\} \geq K^{R_{n+1}-1}.$$

Let now $u$ such that $d(u, V_n) = R_{n+1}$ and $|u| < |V_n| + \frac{R_{n+1}}{2}$. Given two vertices $u, w$, we denote $w \wedge u$ its first common ancestor. Using that $d(u, w) = |u| + |w| - 2|w \wedge u|$, we get

$$d(u, V_n) - |V_n| + 2|V_n \wedge u| \leq |V_n| + \frac{R_{n+1}}{2}.$$

Using that $R_{n+1} = d(u, V_n)$, we also get

$$2|V_n \wedge u| \leq 2|V_n| - \frac{R_{n+1}}{2} \text{ and so } |V_n \wedge u| \leq |V_n| - \frac{R_{n+1}}{4}.$$

Thus, denoting $w$ the ancestor of $|V_n|$ such that $|w| = |V_n| - \frac{R_{n+1}}{4}$, we obtain $d(w, u) \leq \frac{3R_{n+1}}{4}$. Thus,

$$\#\{u \in \mathcal{T}_{\infty} \setminus W_n, d(V_n, u) = R_{n+1}, |u| < |V_n| + \frac{R_{n+1}}{2}\} \leq \#\{u \in \mathcal{T}_{\infty} W_n, d(w, u) < \frac{3R_{n+1}}{4}\} \leq K^{\frac{3R_{n+1}}{4}}.$$

Plugging this in (16), we conclude that

$$\mathbb{P}(|V_{n+1}| < |V_n| + \frac{R_{n+1}}{2} | \mathcal{F}_n) = \frac{K^{\frac{3R_{n+1}}{4}}}{K^{R_{n+1}-1}} = K^{-\frac{R_{n+1}}{4}+1}.$$

$\square$
Recall now that $(I_n)_{n \ge 1}$ is simply the inter-arrival times of a record process. Such processes have been well studied and we will use, in particular, the following result:

**Proposition 14** ([2], p.28). Let $(I_n)_{n \ge 1}$ be the inter-arrival time of a record process of an i.i.d. sequence with diffuse distribution. Then, we have

$$ \lim_{n \to \infty} \log I_n / n = 1 \text{ a.s.} $$

Moreover, for any $n \ge 1$ and $i_2, \dots, i_n \ge 1$

$$ \mathbb{P}(I_2 = i_2, \dots, I_n = i_n, 2^k \le I_k \le 3^k \text{ for all } k > n) > 0. $$

The first part of the proposition is a classical result and the second one follows from the fact that for $k > 1$, $I_k$ has positive probability to take any integer value and $2 < e < 3$. We now have all the tools required to prove the following lemma.

**Lemma 15.** Recall the definition of the events $\mathcal{A}$ and $\mathcal{B}$ given in Proposition 11. We have

$$ \mathbb{P}(\mathcal{A} \cap \mathcal{B}) > 0. $$

*Proof of Lemma 15.* Let first note that $\mathcal{A}$ is $\mathcal{F}_5$-measurable and has positive probability. For $N > 5$, define

$$ \mathcal{B}_N := \{\forall 6 \le n \le N, \frac{n}{2} \le \log(K)R_n \le 2n \text{ and } |V_n| \ge |V_{n-1}| + \frac{R_n}{2}\}. $$

By monotone convergence, $\mathbb{P}(\mathcal{B} | \mathcal{F}_5) = \lim_{N \to \infty} \mathbb{P}(\mathcal{B}_N | \mathcal{F}_5)$. Moreover, using Lemma 10, we see that

$$ (K+1)e^{\frac{n}{2}} \le I_n \le \frac{1}{K^2}e^{2n} \implies e^{\frac{n}{2}} \le K^{R_n} \le e^{2n} \implies \frac{n}{2} \le \log(K)R_n \le 2n. $$

Then, using that $B_{N-1}$ and $R_N$ are $\mathcal{F}_{N-1}$-measurable, we write

$$ \begin{aligned} \mathbb{P}(\mathcal{B}_N | \mathcal{F}_5) &= \mathbb{E}\left(1_{B_{N-1}} \frac{1}{2} \le \log(K)R_N \le 2N \mathbb{E}\left(1_{|V_N| \ge |V_{N-1}| + \frac{R_N}{2}} | \mathcal{F}_{N-1}\right) | \mathcal{F}_5\right) \\ &\ge \mathbb{E}\left(1_{B_{N-1}} \frac{1}{2} \le \log(K)R_N \le 2N \left(1 - K^{-\frac{R_N}{4}} + 1\right) | \mathcal{F}_5\right) \\ &\ge \mathbb{E}\left(1_{B_{N-1}} \frac{1}{2} \le \log(K)R_N \le 2N \left(1 - K^{-\frac{N}{8 \log K}} + 1\right) | \mathcal{F}_5\right) \\ &\ge \left(1 - K^{-\frac{N}{8 \log K}} + 1\right) \mathbb{E}\left(1_{B_{N-1}} \frac{1}{(K+1)e^{\frac{n}{2}} \le I_N \le \frac{1}{K^2}e^{2N}} | \mathcal{F}_5\right) \\ &= \left(1 - K^{-\frac{N}{8 \log K}} + 1\right) \mathbb{E}\left(1_{(K+1)e^{\frac{n}{2}} \le I_N \le \frac{1}{K^2}e^{2N}} \mathbb{P}(\mathcal{B}_{N-1} | \mathcal{F}_5)\right). \end{aligned} $$

Hence, we get

$$ \mathbb{P}(\mathcal{B} | \mathcal{F}_5) \ge \left( \prod_{n \ge 6} \left(1 - K^{-\frac{n}{8 \log K} + 1}\right) \right) 1_{\forall n \ge 6, (K+1)e^{\frac{n}{2}} \le I_n \le \frac{1}{K^2}e^{2n}} := c 1_{\forall n \ge 6, (K+1)e^{\frac{n}{2}} \le I_n \le \frac{1}{K^2}e^{2n}} $$

for some $c > 0$. Finally, we write

$$ \mathbb{P}(\mathcal{A} \cap \mathcal{B}) = \mathbb{E}\left(\left(1_{\mathcal{A}} \mathbb{P}(\mathcal{B} | \mathcal{F}_5)\right) \ge c \mathbb{E}\left(1_{\mathcal{A}} 1_{\forall n \ge 6, (K+1)e^{\frac{n}{2}} \le I_n \le \frac{1}{K^2}e^{2n}}\right)\right). $$

Since the event $\mathcal{A}$ only depends on the value of $I_k$ and on the indexing $(u_j^k)_{j \ge 1}$ for $k \le 5$, using Proposition 14, we conclude that $\mathbb{P}(\mathcal{A} \cap \mathcal{B}) > 0$. $\square$

## 2.3 Proof of (11)

We now explain how to adapt the previous argument to show that for a vertex $v$ with large height, the probability that $o \notin W_\infty$ gets close to 1.
**Lemma 16.** Let $v$ a vertex of height $n$ with $n > 1024$. Define the events $\tilde{\mathcal{A}}_n$ and $\tilde{\mathcal{B}}_n$ by

$$ \tilde{\mathcal{A}}_n := \{\forall k \le \sqrt{n}/2, R_k \le \sqrt{n}\}, $$

$$ \tilde{\mathcal{B}}_n := \{\forall k > \sqrt{n}/2, \frac{k}{2} \le \log(K)R_k \le 2k \text{ and } |V_k| \ge |V_{k-1}| + \frac{R_k}{2}\}. $$

Then, we have

$$ \tilde{\mathcal{A}}_n \cap \tilde{\mathcal{B}}_n \subset \{o \in W_\infty\}. $$

*Proof.* Lemma 16 is very similar to Proposition 11. Assume that $\tilde{\mathcal{A}}_n$ holds. Using that $|V_1| = n$ and $|V_i| - |V_{i-1}| \le R_i$, we get for $k \le \sqrt{n}/2$,

$$ |V_k| \ge n - \frac{\sqrt{n}}{2}\sqrt{n} \ge \frac{n}{2} $$

and $W_{\sqrt{n}/2}$ does not contain the root. Now, if $\tilde{\mathcal{B}}_n$ also holds, we get, for $k > \sqrt{n}/2$,

$$ |V_k| \ge |V_{\sqrt{n}/2}| + \sum_{i=\lfloor\sqrt{n}/2\rfloor+1}^{k} \frac{R_i}{2} \ge \frac{n}{2} + \sum_{i=\lfloor\sqrt{n}/2\rfloor+1}^{k} \frac{i}{4\log(K)} > \frac{2k}{\log(K)} \ge \frac{n}{2} - \frac{\frac{\sqrt{n}}{2}(\frac{\sqrt{n}}{2}+1)}{8\log(K)} + \frac{k(k+1)}{8\log(K)} > \frac{2(k+1)}{\log(K)} $$

for $k > \sqrt{n}/2$ if $\sqrt{n}/2 > 16$. Thus, we get $|V_k| > R_{k+1}$ and we conclude as in the proof of Proposition 11 that $o \notin W_k$. $\square$

Let us explain briefly how to prove that

$$ \lim_{n \to \infty} \mathbb{P}(\tilde{\mathcal{A}}_n \cap \tilde{\mathcal{B}}_n) = 1, $$

which, in view of Lemma 16 and Proposition 9, implies (11). Recall that $(\log(K)R_k/k)_{k \ge 1}$ converges a.s. to 1. So we get

$$ \lim_{n \to \infty} \mathbb{P}(\tilde{\mathcal{A}}_n) = 1. $$

Using similar arguments as in the proof of Lemma 15, we get

$$ \mathbb{P}(\tilde{\mathcal{B}}_n | \mathcal{F}_{\sqrt{n}/2}) \ge \left( \prod_{k > \sqrt{n}/2} (1 - K^{-\frac{k}{8 \log K} + 1}) \right) 1_{\forall k > \sqrt{n}/2, (K+1)e^{\frac{k}{2}} \le I_k \le \frac{1}{K^2} e^{2k}} := c_n 1_{\forall k > \sqrt{n}/2, (K+1)e^{\frac{k}{2}} \le I_k \le \frac{1}{K^2} e^{2k}} $$

for some $c_n$ which tends to 1 as $n$ tends to infinity. Since $(\log I_k)/k$ tends to 1 a.s., then we deduce that

$$ \lim_{n \to \infty} \mathbb{P}(\tilde{\mathcal{B}}_n) = 1 $$

and so

$$ \lim_{n \to \infty} \mathbb{P}(\tilde{\mathcal{A}}_n \cap \tilde{\mathcal{B}}_n) = 1. $$

**Acknowledgements.** The authors warmly thank Nicolas Broutin and Guillaume Chapuy for insightful discussions during the early stages of this work.

## References

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

[2] B. C Arnold, N. Balakrishnan, and H. N Nagaraja. *Records*. John Wiley & Sons, 2011.

[3] A-L. Basdevant, G. Blanc, N. Curien, and A. Singh. Fractal properties of the frontier in Poissonian coloring. *ALEA Lat. Am. J. Probab. Math. Stat.*, 20:1565–1586, 2023.

[4] A-L. Basdevant and A. Singh. Ideal Poissonian coloring on hyperbolic spaces. In preparation, 2026.

[5] M. d'Achille, N. Curien, N. Enriquez, R. Lyons, and M. Ünel. Ideal Poisson–Voronoi tessellations on hyperbolic spaces. Revised version, 49 pages, 12 figures, March 2023.

[6] J. Preater. A species of voter model driven by immigration. *Statistics & Probability Letters*, 79(20):2131–2137, 2009.