Geometric scale-free random graphs on mobile vertices: broadcast and percolation times
Peter Gracar Arne Grauer


Improving the Gilbert-Varshamov bound for permutation Codes in the Cayley metric and Kendall τ-Metric
      
The Nguyen


Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, IL 61801, United States

Email:   thevn2@illinois.edu 

    April 29, 2024
=======================================================================================================================================================


We study the phenomenon of information propagation on mobile geometric scale-free random graphs, where vertices instantaneously pass on information to all other vertices in the same connected component. The graphs we consider are constructed on a Poisson point process of intensity λ>0, and the vertices move over time as simple Brownian motions on either ^d or the d-dimensional torus of volume n, while edges are randomly drawn depending on the locations of the vertices, as well as their a priori assigned marks. This includes mobile versions of the age-dependent random connection model and the soft Boolean model. We show that in the ultrasmall regime of these random graphs, information is broadcast to all vertices on a torus of volume n in poly-logarithmic time and that on ^d, the information will reach the infinite component before time t with stretched exponentially high probability, for any λ>0.






§ INTRODUCTION


In recent years scale-free geometric random graphs have been used extensively to study real world networks, such as social or telecommunication networks. A broad collection of literature has emerged, focusing on different connection rules that lead to such networks, such as for example the spatial graph model with local influence regions <cit.>, scale-free percolation <cit.> and more recent work on spatial preferential attachment type models <cit.>. Further work focused on various topological properties of the emerging networks, such as how graph distances scale with respect to the graph size <cit.> (for non-spatial models) or the euclidean distance between two typical vertices (for spatial models), see <cit.>. A related phenomenon of interest is the percolation probability in such networks, studied for example in <cit.>.

As the body of literature on these graphs grew, a parallel interest in the study of dynamics related them started developing. Many authors have studied the contact process and how it behaves on and spatial and non-spatial versions of such graphs, starting with Chatterjee and Durrett <cit.> and more recently Mourrat and Valesin <cit.>, Linker et al <cit.> and others <cit.>. Further dynamics have also been studied in non-spatial networks, where the contact process is evolving on graphs that are themselves evolving, such as  edges of the graph being randomly resampled, see for example the recent work by Jacob et al <cit.>.

In this paper, we approach the question of dynamics from a different direction. Drawing inspiration from the work done by Peres et al <cit.>, where they considered the Boolean model with mobile vertices, we study properties of geometric scale-free random graphs where the underlying point process is allowed to evolve over time. More precisely, we study scale-free random graphs where edges emerge and disappear due to the motion of the vertices, which individually move as Brownian motions on euclidean space. Particle systems of this kind have been studied with the help of multi-scale analysis techniques on lattices by Kesten and Sidoravicius <cit.>, uniformly elliptic lattices by Gracar and Stauffer <cit.>, fractal lattices by Drewitz <cit.> and on euclidean space by Stauffer <cit.>, with the primary focus on how often the particles “interact” with each other by being in close proximity. Recently, Kiwi et al <cit.> applied such a multi-scale framework to hyperbolic graphs, where the location of vertices in hyperbolic space affects not only their relative positions to each other, but also how “powerful” the vertices are, i.e. how large their area of influence is.

Our focus is on geometric random graphs embedded into euclidean space. Here, the vertices form a Poisson point process on ^d (or on the d-dimensional torus of volume n, denoted by 𝕋_n^d) of intensity λ>0 and are each equipped with an independent, uniform on (0,1) random mark. This mark can be thought of as an inverse weight, with marks close to 0 signifying powerful vertices and marks close to 1 signifying weak vertices. Edges are then drawn between pairs of vertices with probability that depends on the pairs' relative locations and their respective  marks (cf. <Ref>), with vertices close to each other and powerful vertices having a higher probability of forming an edge. Unlike in the hyperbolic case studied in  <cit.>, we consider the mark of a vertex to be an innate property which does not evolve over time. In particular, although all vertices move around independently of their marks and each other, powerful vertices are relatively rare and it therefore takes much longer for areas that happen to be empty of such vertices to “recover” and return close to stationarity.



  
Soft Boolean model.
Although we prove our results in more generality, we first state them for a motivating example, the soft Boolean model. Let each vertex x carry an independent, identically distributed random radius R_x, which we assume to be heavy-tailed, i.e. there exists γ∈ (0,1) such that 

    (R_x>r) ≍ r^-d/γ as r→∞.

In the hard version of the model two vertices are connected by an edge if the balls centered at the vertices locations with associated radii intersect. We consider a soft version of this model, where an independent, identically distributed random variable X(x,y) is assigned to each unordered pair of vertices {x,y}. Then, an edge is formed between two vertices x and y if and only if

    x-y/R_x+R_y≤ X(x,y).

The choice X(x,y)=1, for all pairs {x,y}, corresponds to the hard version of the model. Writing X for an independent identically distributed copy of X(x,y), we assume X to be heavy-tailed with decay

    (X>r) ≍ r^-δ d as r→∞,

for some δ>1, leading to a relaxation of the condition to form an edge which can be interpreted in the following way. For any pair of vertices x and y we take a copy of their corresponding balls and expand those by multiplying both radii with X(x,y). Then, we form an edge between the two vertices if and only if the expanded balls intersect.



  
Mobile soft Boolean model.
We next introduce dynamics into the model. To that end, we let each vertex x move over time independently as a Brownian motion. We do not modify the random radius R_x over time, but we do resample the random variables X(x,y) at unit interval times. One can think of this as the signal between two vertices getting “boosted” by a random amount, determining whether a connection between the pair can established or not. Importantly, whereas this boosting changes at discrete times, the rest of the model still evolves in continuous time, be it the movement of vertices or appearance/disappearance of edges according to (<ref>).  See <Ref> for an example of how edges can appear/disappear over time.








				


  
Broadcast time.
In this setup we now study the spread of information. Consider first the mobile soft Boolean model on the 𝕋_n^d, where at time t=0, an arbitrary vertex (without loss of generality located at the origin) starts broadcasting information. This information is immediately transmitted to all vertices in the same connected component (i.e. vertices for which a path to the origin vertex exists), upon which the vertices start broadcasting the information as well. We are interested in the time it takes for the information to reach every single vertex on the torus. 

Denoting this  broadcast time time by T_bc, we prove in <Ref> that for n large enough and if γ>δ/δ+1, information will reach every vertex on the torus 𝕋_n^d in poly-logarithmic time with high probability, for any positive particle intensity.



  
Percolation time.
Next, consider the mobile soft Boolean model on ^d. As above, let at time t=0 information start broadcasting from an arbitrary vertex, with the re-broadcasting rules the same as before. We are now interested in how long it takes for this information to reach the infinite connected component of the graph, which exists almost surely whenever γ>δ/δ+1, see <cit.>. We denote this by T_perc and call it the percolation time. We prove in <Ref>, that with probability stretched exponentially close to 1 in t, the percolation time is smaller than t.

While the above two results might not appear too surprising given what is known for the hard Boolean model with fixed radii covered by <cit.>, note that the soft Boolean model introduces an additional source of randomness arising from the random variables X(x,y) and more generally from the random occurrence of edges according to <Ref> (cf. <Ref>). Furthermore, the fixed nature of the random radii over time introduces additional correlations into the model that could slow down the propagation of information, requiring significant work to overcome them.



  
Further examples of scale-free geometric random graphs
In the age-dependent random connection model each vertex carries a uniform on (0,1) distributed birth time and two vertices x and y with birth times t and s are connected by an edge independently with probability

    φ(β^-1(t∧ s)^γ (t∨ s)^1-γx-y^d),

where γ∈ (0,1), β>0 and φ:(0,∞)→ [0,1] is a non-decreasing function which we assume to satisfy φ(r) ≍ r^-δ as r→∞. This model emerges as a limit graph of a rescaled version of the age-based preferential attachment model introduced in <cit.>. In this model vertices are added to the graph at rate of a Poisson process with unit intensity and placed on a torus of width one. A new vertex x added at time t forms an edge to each existing vertex y with probability given by (<ref>), where s is the time vertex y has been added to the graph. As (t/s)^γ is the asymptotic order of the expected degree at time t of a vertex with birth time s the age-based preferential attachment model mimics the behaviour of spatial preferential attachment networks introduced in <cit.>.

This class of geometric random graphs has been studied recently and  exhibits a phase transition in the parameters γ and δ such that these graphs are ultrasmall, i.e. two very distant vertices have a graph distance of doubly logarithmic order of their Euclidean distance, if and only if γ>δ/δ+1, as shown in <cit.>. The same regime boundary depending on the parameters γ and δ is shown to appear in the existence of a subcritical percolation phase by Gracar et al. <cit.>, giving a hint of a universal behaviour of these geometric random graphs that is remarkably different to the behaviour of spatial graph models investigated in <cit.>. In this work we consider the class of geometric random graphs in their ultrasmall regime γ>δ/δ+1, evolving over time through vertex motion and edge updating.



  
Structure of the paper.
The remainder of this paper is structured as follows. In <Ref> we formalise the setup and state <Ref>, the two main results of this paper. In <Ref>, we prove several technical results that will be required to prove the two theorems. More precisely, <Ref> establishes the behaviour of the underlying vertices over time, while <Ref> covers how under these conditions, well-behaved connected components can be constructed. <Ref> then concludes by using these results to prove <Ref>.


§ SETUP AND KEY RESULTS




 §.§ Geometric scale-free random graphs


Let 𝕋_n^d the d-dimensional euclidean torus of volume n and
let  be a geometric random graph on a vertex set given by a Poisson point process 𝒳 of intensity λ on either ^d×(0,1) or 𝕋_n^d×(0,1). We write =(x,u) for a vertex of the graph where we refer to x as the location and u as the mark of the vertex . For _1,…,_n∈^d×(0,1) (resp. 𝕋_n^d×(0,1)), denote by __1,…,_n the law of  given the event that _1,…,_n are points of the Poisson process. We consider geometric random graphs which satisfy the following assumption on the probability of the occurrence of edges in the graph. This assumption is given in terms of two parameters γ∈ (0,1) and δ>1. For two vertices ,∈𝒳 we write ∼ if there exists an edge between them.


	Given 𝒳, edges are drawn independently of each other and there exist α,κ_1>0 such that, for every pair of vertices =(x,u), =(y,v)∈𝒳, it holds
	
    _,(∼)≥α (1∧κ_1   (u ∧ v)^-δγx-y^-δ d)

	where |·| is the euclidean distance on ^d (resp. ^d). Furthermore, _,(∼) is such that it holds
	
    _|{∈: ∼}|<∞.



	The second condition of <Ref> guarantees that we are working with finite degree graphs. An condition on _,(∼) that ensures this is, for example
	
    _,(∼)≥κ_2   (u∧ v)^-δγ (u∨ v)^δ(γ-1)x-y^-δ d

	for some constant κ_2>0. Note that both of the afore mentioned geometric random graphs, the soft Boolean model and the age-dependent random connection model satisfy this inequality, as well as the lower bound from <Ref>.



We will work with the Palm versions of  and 𝒢. More precisely, we add to 𝒳 a vertex (0,U_0), where U_0 is an independent on the interval (0,1) uniformly distributed random variable and denote by 𝒢_ the resulting graph on 𝒳∪{(0,U_0)} determined by the connection rules satisfying Assumption <ref>. We denote the law of 𝒢_ by _ and since U_0 is independent of the underlying Poisson point process 𝒳, it holds _ = _(0,u_0) u_0. We can think of _ of the law of 𝒢 conditioned on the existence of a typical vertex, i.e. a vertex with typical mark, at the origin.

We will denote by 𝒞_∞ the infinite connected component of 𝒢 should it exists. It is known (see <cit.>) that if γ>δ/δ+1, such a component exists almost surely and is unique for any particle intensity of λ>0. Furthermore, as shown in <cit.>, all of the remaining connected components are of finite size. When restricted to a cube of volume n on ^d or when working on the torus 𝕋_n^d, <cit.> also gives that with high probability and for sufficiently large n, there exists a unique giant component, i.e. a connected component of linear size in the volume of the cube/torus, while all other connected components are of logarithmic size. In all of the above cases, we will denote by 𝒞() the connected component containing the vertex  and by |𝒞()| its size, i.e. the number of vertices belonging to it. 

We will write Q_K for a cube of volume K, centred around the origin. We might occasionally consider translates of Q_K, but since we will not be interested in them beyond the number that a larger cube can be tessellated into, we do not introduce any specific notation for them and the locations they are centred around. For ∈^d×(0,1) (or equivalently 𝕋_n^d×(0,1)) will denote by B(,r) the ball of radius r∈_+, centred at x∈^d. On the torus, n will always be assumed to be significantly larger than r so as to avoid any boundary effects.



 §.§ Mobile geometric scale-free random graphs


We allow the vertices underpinning the graph to move over time. To that end, denote by _0:= the intensity λ Poisson point process of vertices with marks, at time 0. Let each vertex of _0 move as an independent Brownian motion on ^d; the mark of the vertex remains unchanged. Define _t to be the point process obtained after the vertices of _0 have moved for time t. More precisely, for each =(x,u)∈_0, let (π_(t))_t≥ 0 be a standard Brownian motion on ^d and define _t={(x+π_(t),u):∈_0}. We also introduce the shorthand notation _t:=(x+π_(t),u) for t≥ 0. It is easy to check that _t remains a Poisson point process of intensity λ on ^d×(0,1) (resp. 𝕋_n^d×(0,1)). That being said, _t and _0 are not independent of each other and due to the fixed marks, even the classical mixing results do not apply directly. 

We will work for the remainder of this paper on the Palm version of the process, i.e. we assume that in _0 there exists a vertex with a mark uniformly distributed on (0,1) at the origin. We will refer to this vertex as the origin vertex and denote it by , even though almost surely, other than at time 0, the vertex is not located at the origin of ^d (resp. 𝕋_n^d).

In analogy to the static case, we define _t to be the general geometric random graph on the vertex set _t. Crucially, we still require the marginal distribution of _t to satisfy <Ref> for every t≥ 0. We do not however assume in general that the events {_t_1∼_t_1} and {_t_2∼_t_2} are conditionally on _t_1, _t_2, _t_1, _t_2 independent of each other. Instead, we sample for every pair of vertices , in _0 a sequence of uniform on (0,1) random variables (U_,^n)_n∈_0 and form an edge between  and  at time 0 if U_,^0<_,(∼). At time t> 0, we assume an edge exists between _t and _t if U_,^n<__t,_t(_t∼_t) where n is the unique integer satisfying n≤ t<n+1. By a standard coupling argument, this construction yields the desired marginal distributions of the graphs _t. We do note that if t_1,t_2∈[n,n+1) for some n∈_0, then even conditionally on _t_1, _t_2, _t_1, _t_2 the events {_t_1∼_t_1} and {_t_2∼_t_2} are not independent. If on the other hand such an n∈_0 does not exist (i.e., there exists some n∈ such that t_1< n≤ t_2 or t_2< n≤ t_1), then conditionally on _t_1, _t_2, _t_1, _t_2 the events {_t_1∼_t_1} and {_t_2∼_t_2} are in fact independent.


	The above defined edge updating mechanism is crucial to allow the dynamic graph to “recover” from unfavourable configurations of  and the edge marks at suitable time scales. One could (and we will in our future work) consider alternative edge mark updating mechanisms, such as updating individual edge marks after exponentially distributed random times, but this would (up to constants) not alter the evolution of the process. If the update times were to occur at longer time scales, we conjecture this would lead to a drastically different process evolution, as seen for example in <cit.>.

	We also extend the definitions of 𝒞_∞ and 𝒞() to the mobile setup. To that end, we write 𝒞_∞^t for the (unique) infinite connected component of 𝒢_t and 𝒞_t() for the connected component containing the vertex  at time t in 𝒢_t. Note that the latter is again well defined both on ^d×(0,1), as well as in the torus case 𝕋_n^d×(0,1). As before, we denote by |𝒞_t()| its size.
	


 §.§ Main results

Consider a mobile geometric scale-free random graph on the d-dimensional torus of volume n and recall that we denote by λ the intensity of the Poisson point process of vertices.
Suppose a message originates from the origin vertex , and every vertex that has already received the message broadcasts it continuously to all vertices in the same connected component. Denote by T_bc the time until all vertices have received the message. 
Assume the graph satisfies <Ref>. We then have the following result.


	Let γ>δ/δ+1. On the d-dimensional torus of volume n with d≥ 1, the broadcast time T_bc is with high probability O(log n(loglog n)^ϵ) for any ϵ>0 and any vertex intensity λ>0.


Consider now a mobile geometric scale-free random graph on ^d instead. As above, assume that a message originates at the origin vertex . We define the percolation time as

    T_perc:=inf{t≥ 0:∃∈𝒞_∞^t  s.t. ∼},

that is the first time the origin vertex  belongs to the infinite connected component of 𝒢_t. Suppose that the graph satisfies <Ref>. We then have the following result.

	Let γ>δ/δ+1. Then there exists a constant c>0 such that on the ^d with d≥ 1, the percolation time T_perc satisfies
	
    (T_perc>t)≤exp{-ct^1/c},

	for any vertex intensity λ>0 and any t>0 sufficiently large.





§ TECHNICAL RESULTS


We begin by proving several technical results that will give us control over how vertices of various power behave over time. This in turn will let us construct subgraphs with favourable geometric properties to ensure information can propagate further.


 §.§ Vertex density over time

The proofs in this subsection are inspired by constructions introduced in <cit.>, where the authors studied particle motion and how it affects the emergence of infinite components in the Poisson-Boolean graph model. We note that the introduction of (fixed) vertex marks into the problem presents the biggest difficulty in adapting the technique, in particular since the intensity of the most powerful vertices being considered at any given scale decreases exponentially fast with the size of the region in question. Despite this, we are still able to take advantage of the following mixing time/decoupling time result from <cit.>.


	Fix K>ℓ>0 and consider the cube Q_K^d⊂^d tessellated into subcubes of side length ℓ. Let Π_0 be an arbitrary point process at time 0 that contains at least βℓ^d vertices in each subcube of the tessellation for some β>0. Let Π_Δ be the point process obtained at time Δ from Π_0 after the vertices have moved according to a standard Brownian motion for time Δ. Fix ϵ∈(0,1) and let Ψ be an independent Poisson point process of intensity (1-ϵ)β on ^d. Then there exists a coupling of Ψ and Π_Δ and constants c_1,c_2,c_3 that depend on d only, such that if Δ≥c_1ℓ^2/ϵ^2 and K'≤ K-c_2√(Δlogϵ^-1)>0, the vertices of Ψ are a subset of the vertices Π_Δ inside the cube Q_K' with probability at least
	
    1-K^d/ℓ^dexp{-c_3ϵ^2βΔ^d/2}.




	The proof of this result can be found in <cit.>. Variants of this proposition for weighted lattices and fractal lattices can be found in <cit.> and <cit.>.


We fix now for the remainder of the paper two positive constants, ≪1/log 2 and θ∈(log 2/γ+γ/δ,log 2). Note that by definition θ≪ 1. We will also from here on out observe the process 𝒢_t in discrete time steps t=0,1,… and prove results about the vertex and graph configurations at these discrete observation times. Despite this, the underlying process remains continuous in time, including the appearance/disappearance of edges and motion of particles, both of which can occur between our observation times.


	Let t>0 and I_k:=(1/2e^-(k+1)θ d,1/2e^-kθ d), k∈{0,…,⌊ (log t)/d⌋} and I_-1:=(1/2,1).
	
	
	We say a cube Q⊂^d is t-α-dense, if for every k∈{-1,0,…,⌊ (log t)/d⌋}, the locations of the vertices in Q× I_k contain as a subset an independent Poisson point process of intensity (1-α)λ|I_k| on Q, with marks restricted to I_k.


	Note in the above definition we do not require the marks to be uniformly distributed. In fact, it suffices for the marks to lie deterministically inside the corresponding intervals I_k. We will use this in the proof of the following proposition by disregarding the marks of the vertices in each individual layer and later simply treating them as if they are as small/large as their respective mark interval permits when applying various bounds that depend on the marks.



	Let t>0 be a sufficiently large integer and ξ,ϵ∈(0,1) two constants. Consider the cube Q_L^d, for L=t. Define for i=0,…, t the events
	
    A_i={at time i the cube Q_L is t-ξ-dense}.

	Then, for any vertex intensity λ>0, there exist two positive constants c_1,c_2 such that
	
    (∑_i=0^t-1_A_i≥(1-ϵ)t)≥ 1-exp{-c_1t^c_2}.




	We will argue the proof across each of the ⌊ (log t)/d⌋ layers simultaneously, as we require the cube Q_L^d to be t-ξ-dense for the same (1-ϵ)t time steps. We start with the “thinnest” layer k^*:=⌊ (log t)/d⌋, i.e. the one in which the Poisson point process we are working with has the lowest intensity. The vertices with marks in this layer form a Poisson point process of intensity 
	
    λ|I_k^*|   =λ(1/2e^-(log t)θ-1/2e^-((log t)/d+1)θ d)
       >1/4λ t^-θ.

	We will from here on out disregard the actual marks of the vertices and simply use that they are all bounded to be in the interval I_k^*, which suffices to satisfy the condition of <Ref>. 
	For the remaining layers k∈{0,…,k^*-1} the intensity of the corresponding Poisson point processes with marks in the interval I_k is strictly greater than that of layer k^*. Consequently, the bounds we will show for k^* hold, ceteris paribus, also for the other layers. 
	We will disregard the actual marks of these vertices as well, and only use that the marks belong to the appropriate mark interval I_k.

Let κ=O(log t) be the number of scales we will use in the multi-scale argument that follows. Next, set L^2=L_1>L_2>⋯>L_κ=L. We will tessellate the cubes of side-length L_i into subcubes of side length ℓ_i, to which end we let ℓ_1>ℓ_2>⋯>ℓ_κ, with their precise values to be determined later (see <Ref>). At this stage we only assume that lim_t→∞ℓ_i=∞ for all i∈{1,…,κ}. 
	
	
	
	
	We say that a subcube is good at a given time step for scale j, if it contains at least 
	
	
    (1-ξ_j)λ|I_k|

	vertices at the time in layer k, for k∈{0,…,k^*}, with ξ_j chosen to satisfy
	
    ξ/2=ξ_1<ξ_2<⋯<ξ_κ=ξ,

	and
	
    ξ_j-ξ_j-1=ξ/2(κ-1),∀ j.

	
	
	Let D_1 be the event that all subcubes of side-length ℓ_1 inside the cube of side length L_1 are good for all time steps in [0,t]. 
	For a fixed subcube and a fixed time step, the number of vertices in a given layer k is given by a Poisson random variable with mean 
	
	λ|I_k|ℓ_1^d.
	Using <Ref>, we obtain that there are more than 
	
	(1-ξ_i)λ|I_k|ℓ_1^d
	vertices in this subcube in layer k at the given time with probability larger than 1-exp{-ξ_1^2 λ |I_k|ℓ_1^d/2}. 
	The number of subcubes of side-length ℓ_1 inside Q_L_1^d is O(t^2d) by the choice of L_1 and our assumption on ℓ_1. Before taking a union bound across all of the layers, note that 
	
    λ|I_k|≥λ|I_k^*|>14λ t^-θ,  ∀ k∈{0,1,…,k^*-1}.

	Therefore taking the union bound across all the subcubes, all the time steps, and across all the k^*-many layers by using (<ref>), we obtain that there exist two positive constants c_1 and c_2 such that
	
    (D_1)≥ 1-⌊ (log t)/d⌋ t^2d+1 exp{-ξ_1^2 λ t^-θℓ_1^d/8}≥ 1-exp{-c_1t^c_2},

	where the last inequality holds for large enough t if ℓ_1>C t^. Here, C is a large enough constant and  is a constant satisfying θ< d<1. Note that this assumption is in line with our previous assumption on the values ℓ_i increasing with t. We will later set ℓ_1=Θ(√(t)), which is in agreement with the above.
	
	We now proceed to smaller scales of the multi-scale argument. Let s_j be the number of time steps considered for scale j. We start with s_1=t so that at scale 1, all time steps are considered. We will group the time steps into blocks of m_j consecutive steps for each scale j, starting with m_1=t, i.e. we consider all the t many steps at scale 1 as a single block.
	
	At scale j-1, we will subdivide each interval [b,b+m_j-1) into four subintervals of length m_j separated by Δ_j-1 time steps (which we will determine below), of the form
	
    [b+kΔ_j-1+(k-1)m_j,b+kΔ_j-1+km_j), k∈{1,2,3,4},

	where m_j=m_j-1-4Δ_j-1/4. Put into words, when going from scale j-1 to j, we split each existing interval into four subintervals of equal length, each subinterval preceded by a “gap” of Δ_j-1 many steps (see <Ref>). We will use these gaps to apply <Ref>. Note that the above construction gives that s_j=s_j-1(1-4Δ_j-1/m_j-1).
	Similarly to the spatial definition of good subcubes, we say that a time interval of scale j is good, if all the subcubes are good for scale j during all of the time steps contained in the time interval.
	
	
	
	Let now 0=ϵ_1<ϵ_2<⋯<ϵ_κ=ϵ satisfy ϵ_j-ϵ_j-1=ϵ/κ-1. We define for each scale j∈{2,…,κ-1} the event D_j to be the event that a fraction of at least (1-ϵ_j/2) time intervals of scale j are good. 
	We define D_κ to be the event that for a fraction of at least (1-ϵ_κ/2) time intervals of scale κ, the locations of the vertices in Q_L_κ^d with marks in the layer k contain as a subset an independent Poisson point process of intensity 
	
	(1-ξ_κ)λ|I_k|,
	for all k∈{0,…,k^*} simultaneously.
	
	In order to obtain the (1-ϵ)t many time steps from the claim of the proposition, we note that if D_κ holds, for at least
	
    (1-ϵ_κ/2)s_κ   =(1-ϵ_κ/2)s_1∏_j=1^κ-1(1-4Δ_jm_j)
       ≥(1-ϵ2)t(1-∑_j=1^κ-14Δ_jm_j)

	of the time steps the locations of the vertices in Q_L_κ^d=Q_L^d with marks in the layer k contain as a subset an independent Poisson point process of intensity (1-ξ_κ)λ|I_k|, for all k∈{0,…,k^*} simultaneously. Setting Δ_j/m_j=ϵ/8κ will therefore give the desired bound.
	
	We next proceed to set the value Δ_j to be sufficiently large to allow vertices to move over a distance ℓ_j. To that end, we set ℓ_j via
	
    Δ_j=C'ℓ_j^2κ^2,

	with C' some large enough constant. Combined with the above, this gives
	
    ℓ_j^2/m_j=ϵ/8C'κ^3

	and
	
    ℓ_j+1=ℓ_j√(1/4-ϵ/8κ).

	Since m_1=t, we get ℓ_1^2=ϵ/8C'κ^3t, 
	and since κ=O(log t), we also have ℓ_κ^d≥ Clog^3 t for any arbitrary constant C, if t is large enough. Consequently, all of our preceding assumptions on the sequence ℓ_1,…,ℓ_κ hold, in particular the assumption on ℓ_1.
	
	We now argue that if at time b':=b-Δ_j-1 all subcubes were good for scale j-1, and if ℓ_κ^d≥ Clog^3 t for C large enough, then the interval [b,b+m_j) of scale j is good with probability larger than 1-exp{-cλ t^-θℓ_j^d/κ^2} for some positive constant c, uniformly across all events that are measurable with respect to the σ-algebra induced by particle behaviour up to and including time b'.
	
	To that end, let 
	
    E={at time b' all subcubes are good for the scale j-1}

	and let F be any event measurable with respect to the above σ-algebra. If E∩ F=∅, then 
	
    ([b,b+m_j) is not good,E|F)=0,

	and the claimed bound holds. Therefore, let E∩ F≠∅ and let π_b'^k be the point process of vertices in layer k, obtained at time b' after conditioning on E∩ F. Fix now some time step b^*∈[b,b+m_j). We can then bound
	
    (at time b^* not all subcubes are good for scale j | E,F)

	as follows. We have by E that all subcubes are good for the scale j-1 at time b'. We now set a constant c_ϵ such that (1-c_ϵ)^2(1-ξ_j-1)=1-ξ_j, giving that c_ϵ=θ(ξ_j-ξ_j-1). We also choose a constant c' and set C' from (<ref>) so that
	
    L_j≤ L_j-1-c'√(Δ_j-1log1/c_ϵ),

	which allows us to apply <Ref> with K=L_j-1 and K'=L_j across each of the k^*+1 many layers.
	By using (<ref>) a second time, we therefore obtain for all layers k∈{0,…,k^*} a fresh Poisson point process Ξ^k with intensity 
	
	(1-c_ϵ)(1-ξ_j-1)λ|I_k| 
	which can be coupled with π^k_b^* in such a way that Ξ^k is stochastically dominated by π^k_b' for all k∈{0,…,k^*} (i.e. the process after the vertices of π^k_b^* have moved for time b^*-b') inside Q_L_j with probability at least
	
    1-⌊ (log t)/d⌋exp{-c_1c_ϵ^2λ(1-ξ_j-1)t^-θℓ_j^d}

	for some constant c_1>0. Observe that the choice L_1=t^2 and κ=O(log t), together with (<ref>) gives that it is always possible to choose L_j satisfying (<ref>) and L_κ=t, provided t is large enough. 
	
	Recall that D_κ is defined differently than the remaining events D_j, j<κ and we already have the desired bound for D_κ from the above, so the following is only necessary for j<κ. A given subcube is good for scale j at time b^* if for all k∈{0,…,k^*}, Ξ^k contains at least 
	
	(1-ξ_j)λ |I_k|ℓ_j^d  
	vertices in that subcube, which by our choice of c_ϵ and by applying <Ref>, occurs with probability at least 
	
    1-⌊ (log t)/d⌋exp{-c_2c_ϵ^2(1-c_ϵ)(1-ξ_j-1) λ t^-θℓ_j^d},

	where we have once more used (<ref>) and a union bound over the k^*-many layers.
	Using that ℓ_κ^d≥ Clog^3 t with t large and taking a union bound across the time steps in [b,b+m_j) and all subcubes of scale j, we obtain that there exists a positive constant c such that
	
    ([b,b+m_j) is good,  E | F)≥ 1-exp{-cλ t^-θℓ_j^d/κ^2},

	with this bound trivially holding also for scale κ by the previous comment about D_κ.
	
	Using (<ref>), we now give an upper bound on the probability of the event D_j^c∩ D_j-1 for j≥ 2.
	If D_j-1 occurs, then by its definition there are at least (1-ϵ_j-1/2)s_j-1/m_j-1 intervals that are good for scale j-1. Going to scale j, these intervals subdivide into 4(1-ϵ_j-1/2)s_j-1/m_j-1 subintervals of scale j for us to consider. If the event D_j^c is to hold, there should be fewer than (1-ϵ_j/2)s_j/m_j intervals that are good for scale j. Let w be the difference between these two values, i.e.
	
    w=s_j/m_j(ϵ_j-ϵ_j-1/2).

	Let Z be the number of subintervals of [b,b+m_j) of scale j that are not good for scale j, but are such that at the time step b-Δ_j-1 all subcubes were good for scale j-1. We obtain that if D_j-1 and D_j^c hold simultaneously, Z has to be at least w.
	
	Z can be written as a sum of s_j/m_j indicator random variables χ_r, each one representing a time interval of scale j. Note that although the χ_r are not independent of each other, (<ref>) gives that the probability that χ_r=1, given any realisation of the previous r-1 intervals, is smaller than ρ_j:=exp{-cξ^2t^-θλℓ_j^d/κ^2} for some constant c. Consequently, Z is stochastically dominated by a random variable Z', distributed as a Binomial random variable with parameters s_j/m_j and ρ_j. Using <Ref> leads to
	
    (Z'≥ w)   =(Z'-[Z']≥s_jm_j(ϵ_j-ϵ_j-12-ρ_j))
       ≤exp{-s_jm_j(ϵ_j-ϵ_j-12)(log(ϵ_j-ϵ_j-12ρ_j)-1)}.

	Recall that ϵ_j-ϵ_j-1=ϵ/κ-1 and -log(ρ_j)=θ(ξ^2λ t^-θℓ_j^d/κ^2). Furthermore recall that ℓ_j^d≥ℓ_κ^d≥ Clog^3 t and κ=O(log t), which together gives that for t large enough, we can find a positive constant c for which
	
    (Z'≥ w)≤exp{-cλξ^2 s_jt^θℓ_j^dm_jϵκ^3}.

	Recall next that by (<ref>) we have ℓ_j^2/m_j=ϵ/8C'κ^3 and note that by its definition s_j-1=θ(t) for all j. We therefore obtain
	
    (Z'≥ w)≤exp{-cλϵ^2ξ^2κ^6t^-θℓ_j^d-2t}

	for some (new) constant c.
	Together, this yields that 
	
    (D_j^c∩ D_j-1)≤exp{-ct^c_3κ^6},

	where we used that ℓ_j≥ℓ_κ and ℓ_κ^d≥ Clog^3 t, and c,c_3>0 are some positive constants.
	
	We are now ready to conclude the proof. To that end, we first want to bound the probability (D_κ^c). We have that 
	
    (D_κ^c)≤(D_κ^c∩ D_κ-1)+(D_κ-1^c)

	and applying this recursively, it follows that
	
    (D_κ^c)≤∑_j=2^κ(D_j^c∩ D_j-1)+(D_1^c).

	Each term in this sum can be bounded from above by exp{-c/κ^6t^c_3} and the last term by exp{-c_1 t^c_2}, which gives the stated claim, using that κ=O(log t). 





 §.§ Evenly spread subgraphs



	We call a finite connected subgraph of  contained inside Q_K an evenly spread subgraph of  inside Q_K, if it contains at least b· K vertices for some constant b>0 and if every subcube of Q_K of the form ×_i=1^d(2^k_p v_i,(2^k_p+1)v_i), v_i∈, k_p=⌊log K/d⌋ contains a vertex with mark smaller than 1/2e^-k_pθ d belonging to the evenly spread component. We call these vertices the bottom vertices of the evenly spread component.



	Fix the vertex intensity λ>0, fix K large enough and consider the cube Q_K⊂^d. Assume that Q_K is K-α-dense for some α>0 and let γ>δ/δ+1. Then, there exists ϵ>0 such that for K large enough, there exists an evenly spread subgraph of  inside Q_K with probability at least
	
    1-exp{-K^ϵ}.

	



	Recall the values ∈(0,1/log 2) and θ∈(log 2/γ+γ/δ,log 2). Set ϵ_1>0 small enough that θ>ϵ_1+log 2/γ+γ/δ.
		Let n_p=⌊ K^(1-log 2)/d⌋ and k_p=⌊log K/d⌋. For k=0,…,k_p define
	
    V_k:={0,…,n_p 2^k_p-k-1}^d

	and
	
    A_k,𝐯:=_i=1^d(2^k v_i,2^k(v_i+1)) for k=0,… k_p and 𝐯=(v_1,…,v_d)∈ V_k.

	
	For each k=0,…,k_p, the cubes {A_k,𝐯:𝐯∈ V_k} give a tessellation of Q_K into (n_p 2^k_p-k)^d cubes of volume 2^kd, with the finest tessellation at k=0 and the coarsest at k=k_p. Note that the cubes across layers are nested inside each other in a tree-like structure with every A_k+1, tessellating into the 4 cubes A_k,2+̌𝐞:𝐞∈{0,1}^d.
	
	Define
	
    B_k,:=A_k,×(12e^-(k+1)θ d,12e^-kθ d) for k=0,… k_p and =̌(v_1,…,v_d)∈ V_k.

	We use the parameter k=0,…,k_p to signify the layer of the boxes {B_k,:∈̌V_k}, which defines the range of the marks of points of  inside the boxes and the level of the coarseness of the tessellation of space. Note that the ranges of the marks correspond with the ones given by <Ref>. Note further that at the “lowest layer”, i.e. for k=k_p, the boxes have width of order K^log 2 and the corresponding mark range is of order K^-θlog 2. Due to the nested structure of the boxes A_k, and disjoint nature of the intervals (12e^-(k+1)θ d,12e^-kθ d), the system of boxes {B_k,:k=0,…,k_p,∈̌V_k} has the structure of a 2^d-regular tree when treating B_k+1, as the common parent of the 2^d boxes B_k,2+̌𝐞 with 𝐞∈{0,1}^d; see <Ref> for an example.
	
	
	
	Due to the assumption of K-α-density, the number of vertices in any box B_k, stochastically dominates a Poisson random variable with parameter
	
    (1-α)2^kdλ(12e^-kθ d-12e^-(k+1)θ d)>(1-α)λ ce^kd(log 2-θ)

	for some constant c>0 not depending on k and $̌. If we therefore setϵ_2=log2-θ>0, it follows that
	
    (B_k, is not empty)≥ 1-exp{(1-α)λ ce^kdϵ_2}.

	On the event thatB_k,is non-empty, we denote by_k,an arbitrarily chosen vertex (say, with the smallest mark) in the box. 
	
	We will use the boxesB_k,to build the linear sized component. We will then use the even spatial distribution of these vertices to ensure that the vertices can form connections with each other through connectors. To this end, we colour all of the vertices with marks greater than1/2. Chooseϵ_3∈(0,θγ∧δϵ_1)such that∑_k=0^∞e^-kd(θγ∧δϵ_1-ϵ_3)converges and colour the points ofon^d×[1/2,1)by the colour setindependently and such that the points with colourk∈form a Poisson point process^kon^d×[1/2,1)with intensity proportional toe^-kd(θγ∧δϵ_1-ϵ_3). We now use this colouring to assign the coloured vertices different roles. Fork=0,…,k_pand∈̌V_k, we denote as
	
  * C_k,=^k∩ A_k,×[1/2,1) the potential connectors (if B_k, is non-empty).
	
	We will useC_k,to ensure with high probability that the vertices we consider belong to the same connected component.  Note that the intensity of ofC_k,is decreasing ink, since it is much easier for vertices with small marks (i.e. largek) to successfully form connections as opposed to vertices with large marks (i.e. smallk), which require a larger number of candidates to compensate for the lower probability of forming edges.
	
	Using thatθγ<log2, there existsc>0such that, for allk=0,…,k_p, on the event thatB_k,is not empty,ct_k,^-γ/d<2^k, wheret_k,is the mark of_k,. Consequently, for eachk=0,…,k_p, the volume ofB(_k,,ct_k,^-γ/d)∩A_k,represents a positive proportionρ>1/2^dof the volume of the ballB(_k,,ct_k,^-γ/d). 
	
	
	
	
	
	This has the following consequence on how two vertices can connect. Given that the boxB_k+1,and one of its “children”B_k,2+̌𝐞(with𝐞∈{0,1}^d) are not empty, the corresponding vertices_k+1,and_k,2+̌𝐞lie at distance at most√(d)2^k+1and both have marks smaller than1/2e^-kθd. Using <Ref>, there exists a constantc>0such that the number of vertices inC_k,which form an edge to both_k+1,and_k,2+̌𝐞is Poisson-distributed with parameter greater than
	
	
    cλ e^kd(θγ∧δϵ_1-ϵ_3)t_k,2+̌𝐞^-γ(1∧ t_k+1,^-γδ(|x_k,2+̌𝐞-x_k+1,|+t_k,2+̌𝐞^γ/d)^-dδ)>cλ e^kdϵ_3,

	wherecchanges throughout the calculation, but does no depend onkand$̌. We have used above that θ>ϵ_1+log 2/γ+γ/δ. Write {_k+1,↔_k,2+̌𝐞} for the event that the boxes B_k+1, and B_k,2+̌𝐞 are not empty and the vertices _k+1, and _k,2+̌𝐞 are connected via a vertex in C_k,2+̌𝐞. Then, we have due to the above, for all k∈ and ∈̌V_k that
	
    (_k+1,↔_k,2+̌𝐞|B_k+1, and B_k,2+̌𝐞 are not empty)≥ 1-exp{-cλ e^kdϵ_3}.

	
	We now proceed to use <Ref> together with the tree-like structure of the boxes to prove that with high probability, there exist of order K distinct vertices belonging to the same connected component. We will do this in two steps. First, we will show that the vertices in the most powerful layer k_p form a connected subgraph containing n_p^d distinct vertices, where each box B_k_p, contains one of these vertices. Second, we will use that that each box B_k_p, for ∈̌V_k_p represents the root of a 2^d-regular tree. We will show that the trees resulting only from boxes that are not empty and connected to their “parent” box through a connector are percolated 2^d-regular trees with a depth of order k_p and containing 2^k_p d vertices. Since there are n_p^d many trees like this, the resulting connected subgraph of  contains at least of order K^d distinct vertices.
	
	To keep notation concise, we redefine the labelling of the boxes of layer k_p. Let 
	
    σ:{0,…,n_p^d-1}→ V_k

	be any bijection such that B_k_p,σ(0)=B_k_p, and the boxes B_k_p,σ(i) and B_k_p,σ(i+1) are adjacent to each other for i=0,…,n_p^d-2. We also relabel the corresponding vertices with the smallest mark inside each box, so that on the event that B_k_p,σ(i) is not empty, _k_p,σ(i) is the vertex with the smallest mark inside it. We say B_k_p,σ(0) is good if and only if the box is not empty. By (<ref>), there exists c>0 such that
	
    (B_k_p,σ(0) is good)≥ 1-exp{-ce^k_p dϵ_2}.

	For i=0,…,n_p^d-2, we say B_k_p,σ(i+1) is good if
	
		
  * B_k_p,σ(i) is good,
		
  * B_k_p,σ(i+1) is not empty, and
		
  * _k_p,σ(i+1) and _k_p,σ(i) are connected via a connector in C_k_p,σ(i+1).
	
	Otherwise B_k_p,σ(i+1) is considered bad. Let ϵ_4<ϵ_2∧ϵ_3. By <Ref>, there exists c>0 such that for i=0,…,n_p^d-2 we have
	
    (B_k_p,σ(i+1) is good|B_k_p,σ(i) is good)≥ 1-exp{-cλ e^k_p dϵ_4}.

	This yields that
	
    (B_k_p, is good for all ∈̌V_k_p)≥ 1-n_k_p^dexp{-cλ e^k_p dϵ_4}≥ 1-K^1-log 2exp{-cλ K^ϵ_4}.

	
	We now proceed to the remaining layers. For ∈̌^d, denote by ⌊/2⌋ the vector (⌊v_1/2⌋,…,⌊v_d/2⌋). With this notation, for each k=0,…,k_p-1 and ∈̌V_k, the parent box of B_k, is given by B_k+1,⌊/2⌋. We now say, for each k=0,…,k_p-1 and ∈̌V_k, that the box B_k, is good if
	
		
  * B_k+1,⌊/2⌋ is good,
		
  * B_k, is not empty, and
		
  * _k, and _k+1,⌊/2⌋ are connected via a connector in C_k,.
	
	As before, we otherwise say B_k, is bad. Just like in the case of k_p, equations (<ref>) and (<ref>) imply the existence of a constant c>0 such that for k=0,…,k_p-1, ∈̌V_k and 𝐞∈{0,1}^d, such that
	
    (B_k,2+̌𝐞 is good|B_k+1, is good)≥ 1-exp{-cλ e^k dϵ_4}.

	Importantly, given that B_k+1, is good, the events that B_k,2+̌𝐞 is good are all independent of each other and of any other box on this layer, due to only depending on disjoint subsets of . Consequently, the number of good children of B_k+1,, given that this box is good, is a binomially distributed random variable with parameters 2^d and p_k≥ 1-exp{-cλ e^kdϵ_4}. Furthermore, given the good boxes in the layer k+1, the number of good children of each of those good boxes are independent of each other by the above observation. As such, if we denote by |B_k| the number of good boxes in layer k, given |B_k+1|, |B_k| is binomially distributed with parameters 2^d|B_k+1| and p_k.
	
	We can now estimate the number of good boxes in each layer and show that with high probability, sufficiently many are good. For k=0,…,k_p-1, denote by E_k:={|B_k|>2^d(1-k^-2)|B_k+1|} the event that layer k has sufficiently many good boxes when compared to layer k+1. Furthermore, denote by E_k_p the event that all boxes in layer k_p are good. Then, given the event E_k∩ E_k+1∩…∩ E_k_p we have that
	
    |B_k|>|B_k_p|∏_i=k^k_p-12^d(1-i^-2)>cn_p^d2^d(k_p-k-1)>c2^-kdK,

	where c=∏_i=1^∞(1-i^-2)>0. It is therefore sufficient to show that there exists a k_0 such that E_k_0∩… E_k_p holds with high probability. We choose k_0 large enough that 1-exp{ce^k_0 dϵ_4}>1-k_0^-2. Then, using a simple Chernoff bound for binomially distributed random variables we get
	
    (E_k^c | |B_k+1|)≤exp{-2^d-1|B_k+1|cλ e^kdϵ_4/k^2}

	for all k≥ k_0. Consequently, there exists c>0 such that
	
    (E_k|E_k+1∩…∩ E_k_p)≥ 1-exp{-cλe^kdϵ_42^-kdK^d/k^2}≥1-exp{-cλK^ dϵ_4/(log K)^2},

	provided k_p is sufficiently large.
	Together with (<ref>), it follows that
	
    (E_k_0∩…∩ E_k_p)≥(E_k_p)(1-⌊log K⌋exp{-cλK^ dϵ_4/(log K)^2})≥ 1-exp{-K^ϵ}

	for some ϵ>0 not depending on K, as long as K and consequently k_p are large enough. As E_k_0∩…∩ E_k_p implies the existence of, up to a constant, at least 2^-k_0K good boxes and therefore the existence of an evenly spread component inside Q_K, the proof is complete.




	We call the evenly spread subgraph constructed in <Ref> the distinguished subgraph of  inside Q_K.
	We call the b· K vertices used in the construction of the evenly spread subgraph from <Ref> the distinguished vertices of the distinguished subgraph.



	Given a distinguished subgraph and a vertex with mark from , 
	the event that this vertex belongs to the same connected component inside Q_K as the distinguished subgraph is an increasing event. Note that this does not hold if the distinguished subgraph is not given, nor does it necessarily hold for the event “the vertex belongs to an evenly spread subgraph”, since the monotonicity of the event might fail depending on how the subgraph is chosen.
	 



For the following arguments, we will have to use sprinkling. To that end, we split the particle system (_t)_t≥ 0 into two parts, (^1-ε_t)_t≥ 0 and (^ε_t)_t≥ 0 for some arbitrary ε∈(0,1). We do this by using the thinning property of Poisson point processes to thin _0 into the Poisson point processes ^1-ε_0 of intensity (1-ε)λ and ^ε_0 of intensity ελ and let the two evolve (independently) over time using the same rules as before. We outline several useful facts about the resulting particle systems and graphs, most of them direct consequences of properties of Poisson point processes.


	
  * The systems (^1-ε_t)_t≥ 0 and (^ε_t)_t≥ 0 are stationary and independent of each other.
	
  * The graph ^ε_t induced by ^ε_t is independent of the graph ^1-ε_t induced by ^1-ε_t.
	
  * A cube Q_K that is t-α-dense for _s is t-εα-dense for _s^ε and t-(1-ε)α-dense for _s^1-ε.
	
  * If s,t≥ 0 are such that ⌊ s⌋≠⌊ t⌋ and ,∈^ϵ, then conditionally on _s,_t,_s,_t, the events {_s∼_s} and {_t∼_t} are independent. The equivalent statement holds for vertices from ^1-ϵ_t as well.




	Let λ>0 and assume that Q_K is K-α-dense for some α>0 and let γ>δ/δ+1. Let furthermore G be the distinguished subgraph of ^1-ε inside Q_K. Then, a given vertex  with a mark in (0,1) and arbitrary location within Q_K belongs to the same connected component of  as G with probability bounded uniformly in K away from 0, if K is large enough.
	
	
	
	For the duration of the proof, we consider only vertices located inside Q_K even when we do not explicitly say this. We will argue the claim in 3 steps:
	
		
  * For large enough K,  has a probability bounded away from 0 of connecting to a vertex with mark smaller than 1/log K belonging to ^ε.
		
  * For large enough K, any vertex with mark s<1/log K (and in particular the vertex from Step 1) of ^ε starts, with probability bounded away from 0, a path of vertices from ^ε with ever decreasing marks (alternating through connectors), the final vertex having mark smaller than K^-θlog 2.
		
  * The final vertex of the path from Step 2 forms, for K large enough, with probability bounded away from 0 a connection via a connector from ^ε to the closest distinguished vertex in the bottom layer of G.
	
	Note that at every step, save for  and the distinguished vertex belonging to the bottom layer of G, every vertex considered belongs to ^ε and as such its location and mark are independent of G.
	
	Step 1 is an immediate consequence of <Ref>. The vertices with mark smaller than 1/log K that form a connection to =(x,t) stochastically dominate a Poisson point process with intensity ελα(1∧κ_1 s^-δγ|x-y|^-δ d) on Q_K×(0,1/log K). Consequently, the number of neighbours of  in ^ε∩ Q_K stochastically dominates a Poisson random variable with intensity
	
    ∫_Q_K y∫_0^1/log K s ελα(1∧κ_1 s^-δγ|x-y|^-δ d).

	Since the above integral can easily be checked to be increasing in K and therefore bounded away from 0 for large values of K, Step 1 follows by noting that a Poisson random variable with intensity bounded away from 0 has probability of being equal 0 bounded away from 1. We denote the vertex with the smallest mark of these vertices by .
	
	In order to prove Step 2, we use a similar construction as in the proof of <Ref>. To that end, let y∈ Q_K be the location of . Next, similar to the proof of <Ref>, let n_p=⌊ K^(1-log 2)/d⌋ and k_p=⌊ (log K)/d⌋ and define
	
    B_k:=A_k×(12e^-(k+1)θ d,12e^-kθ d) for k=0,… k_p,

	with 
	
    A_k:=_i=1^d(2^k v_i,k,2^k(v_i,k+1)),

	where _̌k=(v_1,k,…,v_d,k) are chosen such that y∈ A_k. Note that by construction, A_k⊂ A_k+1 for every k∈{0,…,k_p-1}. As in the proof of <Ref>, we also colour all of the vertices of ^ε with marks greater than 1/2. Let ϵ_1>0 small enough that θ>ϵ_1+log 2/γ+γ/δ.
	Choose ϵ_2∈(0,θγ∧δϵ_1) such that ∑_k=0^∞ e^-kd(θγ∧δϵ_1-ϵ_2) converges and colour the vertices of ^ε on ^d×[1/2,1) by the colour set  independently and such that the vertices with colour k∈ form a Poisson point process ^k on ^d×[1/2,1) with intensity proportional to e^-kd(θγ∧δϵ_1-ϵ_2). For k=0,…,_̨p, we denote by
	
    C_k:=^k∩ A_k×[1/2,1)
	
	the potential connectors (if B_k is not empty). Then, using the same computation as in the proof of  <Ref> and setting ϵ_3=log 2-θ>0 as there, the probability that B_k is not empty is greater than
	
    1-exp{(1-α)cελ e^kdϵ_3}.

	Likewise, given that B_k and B_k+1 are not empty, the probability that there exists a connector vertex from C_k that is connected to the oldest vertex in B_k and the oldest vertex in B_k+1 is greater than
	
    1-exp{-cελ e^kdϵ_2}.

	Note that this bound also holds if instead of the oldest vertex inside B_k one uses an arbitrary given vertex from B_k, which we implicitly use next.
	
	Let now s be the mark of  and k^* chosen such that ∈ B_k^*. Then, using the above bounds, the probability that there exists a path of vertices alternating between B_k and C_k  as k goes from k=k^* to k_p-1, starting from  is greater than
	
    1-∑_k=k^*^k_p-1exp{-cελ e^kd(ϵ_2∧ϵ_3)}>1-∑_k=k^*^∞exp{-c ελ e^kd(ϵ_2∧ϵ_3)}.

	Since the infinite sum above is summable and k^* is increasing in K, this probability is bounded can be made strictly positive for large enough K. We denote by  the vertex of this path that lies in B_k_p, i.e. the final vertex of the path.
	
	For Step 3, we begin by noting that the bottom vertices of G have marks smaller than K^-θ d. Similarly,  has a mark smaller than K^-θ d. By construction of G, there exists at least one vertex among the bottom vertices that is at distance at most 2^(log K) from , and by the same argument as in the proof of <Ref>, the probability that the two vertices are connected via a connector from C_k_p+1 grows exponentially close to 1 as K is made large and is therefore bounded away from 0 for K large enough.
	
	Combined, this gives the desired claim.
	



	Let G_i, i∈{1,2} be the distinguished subgraphs of ^1-ε inside Q_K at times t_1 and t_2 such that ⌊ t_1⌋≠⌊ t_2⌋. Then, the probability that there exists at least one vertex ∈^ε inside Q_K that belongs to the same connected component of  as G_i at time t_i, for i∈{1,2}, is larger than
	
    1-exp{-c(1-exp{-K^2/dt_2-t_1})ελ K},

	for some constant c>0.



	
	We first consider the probability that a vertex that is located inside the middle (say at distance at least K^1/d/4 from the boundary) of Q_K at t_1 is located inside Q_K at time t_2. Using the bound on the probability that a vertex moves further than (K^1/d/4) in t_2-t_1 time, this probability is larger than
	
    1-exp{-cK^2/dt_2-t_1},

	for some positive constant c.
		
	We can, without loss of generality, sample ∈^ε independently of any other vertices from ^ε used in the rest of the arguments, by simply splitting ^ε further into two disjoin Poisson point processes, each with intensity ε/2 and sampling  from the first of the two, with the rest of the vertices used in the other sprinkling arguments being sampled from the second. We omit this detail in the rest of the argument to keep notation concise.
	
	By <Ref>, any vertex of  inside Q_K belongs to the same connected component as G_1 (resp. G_2) with probability at least p>0, with p bounded away from 0. By the independence of the point processes ^1-ε_t_1, ^1-ε_t_2, ^ε_t_1 and ^ε_t_2, a given vertex ∈^1-ε belongs to the connected component of G_t_1 at time t_1 and G_t_2 at time t_2 with probability at least p^2. Therefore, using the thinning property of Poisson point processes, the vertices of _0^ε that are located in the middle of Q_K at t_1  and are inside Q_K at t_2, that belong to both connected components at their respective times, stochastically dominate a Poisson point process in Q_K of intensity (1-exp{-K^2/d/t_2-t_1})p^2ελ. The probability of at least one such vertex existing is therefore at least 1-exp{-(1-exp{-K^2/d/t_2-t_1})p^2ελ K}.




















§ PROOFS OF THEOREMS



 §.§ Broadcast time

Recall that we consider broadcast time on 𝕋_n^d, the d-dimensional torus of volume n.




	Let t=Clog n(loglog n)^ε for some sufficiently large constant C and any ε>0. Let ϵ_1>0 be small but fixed. We will consider the broadcast of information over times i∈[0,t]. Note that if we want to apply <Ref> with this choice of t, the cube Q_L will have side-length t≪ n. We will therefore apply <Ref> across a tessellation of the torus into cubes of side length t. For each such cube Q_L, at the (1-ϵ_1)t times when the cube Q_L is dense, using <Ref>, the cube Q_L contains a distinguished subgraph with probability at least 1-exp{-L^ϵ_2}. 
	
	Taking a union bound across the n/t^d many cubes in the torus, the probability that each of the n/t^d cubes contains a distinguished subgraph at all of the (1-ϵ_1)t times when the cube is t-ϵ_1-dense is greater than
	
    1-n/t^dexp{-c_1t^c_2}-t(1-ϵ_1)n/t^dexp{-t^ϵ_2},

	where c_1 and c_2 are the constants from <Ref>.
	Furthermore, by <Ref>, the probability that inside the given cube Q_L, all of the distinguished components always share at least one vertex with their preceding distinguished component is at least
	
    1-texp{-c(1-exp{-t^2ϵ_1 t})t}

	where we have omitted the sprinkling parameter from the lemma, since it is arbitrary and constant, in order to not confuse notation. Note that the term ϵ_2t in the expression represents the worst case time difference between two subsequent observations of the distinguished component inside of a given cube. 
	
	
	Next, from <cit.> we have that the probability the second largest connected component of the torus of volume n is larger than k is
	
    (|C_n^(2)|≥ k)≤n/cexp{-ck^ζ_hh,}

	where ζ_hh depends only on the model parameters.
	Consequently, for our choice of t, the probability that any of the distinguished components at time i does not belong to the largest connected component on the torus is smaller than
	
    n/cexp{-c (bClog n(loglog n)^ε)^ζ_hh/d}=n/cn^-c (bC)^ζ_hh/d(loglog n)^εζ_hh/d,

	which for C chosen large enough can be made decreasing (and even summable) in n. We therefore have that the largest connected component on the torus contains in every cube of the tessellation, for at least (1-ϵ_2)t times, a distinguished subgraph of size at least b· t^d with probability at least 
	
    1-n/texp{-c_1t^c_2}-t(1-ϵ_1)n/texp{-t^ϵ_2}
         -n/ttexp{-c(1-exp{-t^2ϵ_1 t}) t}-tn/cn^-c (bC)^ζ_hh/d(loglog n)^εζ_hh/d,

	which tends to 1 as n grows large.
	
	We now finally consider the propagation of information. First, the probability that the origin vertex does not belong to the largest connected component at any time during [0,t/2) is smaller than the probability that it does not belong to the same connected component as the distinguished subgraph inside the cube Q_L to which the origin belongs, for all of the at least (1/2-ϵ)t times in [0,t/2) when the distinguished subgraph exists. Let p be the probability from <Ref> that a vertex with an arbitrary mark belongs to the same connected component as the distinguished subgraph. Then, due to the above, the probability that the origin does not belong to the largest connected component during [0,t/2) is smaller than (1-p)^(1/2-ϵ)t.
	Consequently, we have with probability
	
    1-(1-p)^(1/2-ϵ)t

	that the largest connected component on the torus has already received the broadcast by time t/2. Each vertex of the graph therefore has t/2 time to receive the information by connecting to the largest connected component. Using a simple Chernoff bound, the number of vertices on the torus is at most (1+δ)n with probability larger than 1-e^-Ω(n) and on this event, the probability that each of the vertices belongs to the largest connected component at least once during [t/2,t] is at least
	
    1-(1+δ)n(1-p)^(1/2-ϵ)t.

	Combining this with (<ref>) and (<ref>), recalling that t=Clog n(loglog n)^ε and setting C large enough then gives the result.	




 §.§ Percolation time



	For j∈_0 define
	
    A_j:={_j does not belong to 𝒞_∞^j},

	that is the event that at time j, the origin vertex  does not belong to the infinite connected component 𝒞_∞^j. It then follows, that
	
    (T_perc>t)≤(∩_j=0^⌊ t⌋ A_j)=:(B_t).

	
	Consider now the cube Q_L^d for L=t. On the event that at time j there exists a distinguished subgraph inside of Q_L^d, let Ã_j to be the event that the origin vertex  does not belong to the same connected component as the distinguished subgraph at time j. In analogy to B_t, define B̃_t to be the event that  does not belong to the same connected component as the distinguished subgraph for any of the discrete time steps j=0,1,…,⌊ t⌋. Next, let C_j be the event that at time j, the distinguished subgraph belongs to the infinite connected component 𝒞_∞^j and let D_t:=∩_j=0^⌊ t⌋C_j be the event that at all discrete times j=0,1,…,⌊ t⌋, the distinguished subgraph inside Q_L^d is a subgraph of the infinite component.
	
	Let ϵ_t>0 be a small constant and let E_t be the event that for at least (1-ϵ_t)t time steps, the cube Q_L^d is L^d-ξ-dense, where ξ∈(0,1) can be chosen arbitrarily, but should be thought of as small. Finally, let F_t be the event that an evenly spread component exists at each of the at least (1-ϵ_t)t times when the cube Q_L^d is dense.
	
	We then first note that
	
    (B_t)   ≤(B_t∩ F_t∩ E_t) + (F_t^c∩ E_t)+ (E_t^c)
       ≤(B_t∩ F_t∩ E_t) + texp{-L^dϵ} + exp{-c_1 t^c_2},

	where we used <Ref> and a union bound across the at most ⌊ t⌋ time steps in the second inequality.
	
	Next, if Ã_j^c holds for some j∈{0,…,⌊ t⌋} and D_t holds, then B_t cannot hold and consequently
	
    (B_t∩ F_t∩ E_t)≤((B̃_t∪ D_t^c)∩ F_t∩ E_t)≤(B̃_t∩ F_t∩ E_t)+(D_t^c∩ F_t∩ E_t).

	We can bound (D_t^c∩ F_t∩ E_t) using the results of <cit.> by
	
    (D_t^c∩ F_t∩ E_t)≤ t cexp{-c^-1(b L^d)^ζ_hh},

	where c and ζ_hh are two positive constants that depend on the model parameters only, and the t term comes from taking a union bound across the ⌊ t⌋ time steps. Note that by <cit.> the above bound holds for any λ>0.
	
	We next proceed to bound (B̃_t∩ F_t∩ E_t). By <Ref>, 
	
    (B̃_t∩ F_t∩ E_t)≤ (1-p)^(1-ϵ_t)t,

	where p is the (uniformly in L^d) positive probability that an arbitrary vertex belongs to the same connected component as the distinguished subgraph. Putting (<ref>), (<ref>), (<ref>) and (<ref>) together, we obtain
	
    (B_t)≤exp{-ct^1/c}

	for some sufficiently large constant c, where we have used that L=t, which completes the proof.
	




§ KNOWN RESULTS



Given two vertices =(x,u) and =(y,v) with marks smaller than 1/2, the number of vertices with mark larger than 1/2 which form an edge to both  and  is Poisson-distributed with parameter larger than 

    C u^-γ(1∧ v^-γδ(y-x + u^-γ/d)^-dδ),

where C>0 is a constant that does not depend on k.


We consider the vertices = (z,w) with x-z^d < u^-γ. Note that these vertices lie close enough to  that they form an edge to it with probability at least α(1∧κ_1). Then, the number of those vertices which form an edge to  and  is Poisson-distributed with parameter bounded from below by

    ∫_1/2^1∫_B(x,u^-γ/d)   α^2(1∧κ_1)(1∧κ_1 v^-γδz-y^-dδ)
    ≥   V_d α^2(1∧κ_1)/2u^-γ(1∧κ_1 v^-γδ(y-x + u^-γ/d)^-dδ),

where V_d is the volume of the d-dimensional unit ball and α comes from Assumption <ref>. Thus, there exist a constant C>0 sufficiently small such that (<ref>) holds.




Let P be a Poisson random variable with mean λ. Then, for any 0<ϵ<1,

    ℙ(P<(1-ϵ)λ) < exp{-λϵ^2/2}

and

    ℙ(P > (1 + ϵ)λ) < exp{-λϵ^2/4}.




	
Let B be a binomial random variable with parameters n and p. Then,

    (B≥ np+a)≤exp{a-(pn+a)log(1+apn)}





Acknowledgment: This research was supported by the Deutsche Forschungsgemeinschaft (DFG) as Project Number 425842117.


