Received: 8 June 2021 Accepted: 8 February 2022 Published on: 30 March 2022
DOI: 10.1002/rsa.21084
RESEARCH ARTICLE
Absenceofpercolationingraphsbased onstationary
point processes with degrees bounded by two
Benedikt Jahnel1,2 András Tóbiás3
1Weierstrass Institute Berlin, Berlin, Germany
2TU Braunschweig, Braunschweig, Germany
3TU Berlin, Berlin, Germany
Correspondence
Benedikt Jahnel, Weierstrass Institute Berlin,
Mohrenstraße 39, 10117 Berlin, Germany.
Email: [email protected]
Funding information
Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under Germany’s
Excellence Strategy MATH+; Berlin Mathematics
Research Center project ID: 390685689,
Grant/Award Number: EXC-2046/1.
Abstract
We consider undirected graphs that arise as determinis-
tic functions of stationary point processes such that each
point has degree bounded by two. For a large class of point
processes and edge-drawing rules, we show that the aris-
ing graph has no infinite connected component, almost
surely. In particular, this extends our previous result for
signal-to-interferenceratiographsbasedonstabilizingCox
point processes and verifies the conjecture of Balister and
Bollobás that the bidirectional k-nearest neighbor graph
of a two-dimensional homogeneous Poisson point process
does not percolate for k=2.
KEYWORDS
bidirectional k-nearest neighbor graph, continuum perco-
lation, degree bounds, deletion-tolerance, stationary point
processes
1INTRODUCTION
ContinuumpercolationwasintroducedbyGilbert[10]inordertomodelconnectivityinlargetelecom-
munication networks. In his graph model, the vertices form a homogeneous Poisson point process
(PPP)inR2,andtwopointsareconnectedwhenevertheirdistanceislessthanafixedconnectionradius
r>0.He showedthatthismodelundergoesaphasetransition:ifthespatialintensity𝜆>0ofthePPP
issufficientlysmall,thenthegraphconsistsoffinitecomponentsonly,almostsurely,whereasforlarge
enough 𝜆,thegraphpercolates, that is, it has an unbounded connected component, also almost surely.
This is an open access article under the terms of the Creative Commons Attribution-NonCommercial-NoDerivs License, which permits use and
distributioninany medium,providedtheoriginalworkisproperlycited,theuseis non-commercialand nomodificationsor adaptationsare made.
© 2022 The Authors. Random Structures and Algorithms published by Wiley Periodicals LLC.
240 wileyonlinelibrary.com/journal/rsa Random Struct Alg. 2023;62:240–255.
JAHNEL AND TÓBIÁS 241
FIGURE 1 Top: Realizations of U-kNN graphs based on a PPP with k=1(left),k=2 (center) and k=3 (right). Bottom:
Realizations of B-kNN graphs based on a PPP with k=2(left),k=4 (center) and k=5 (right)
This model has been widely extended, for instance to the case of random connection radii and
for various point processes, see [2, 4, 8, 12, 16, 17, 21, 22]. A drawback of Gilbert’s model is that it
allows for an arbitrarily large degree of the vertices, whereas for many applications, it is a reasonable
assumption that the vertices should have bounded degree. Incorporating this property, Häggström and
Meester[13]studiedpercolationintheso-calledundirected k-nearest neighbor (U-kNN)graph,based
onastationaryPPPin R𝑑,𝑑≥1,seetop lineofFigure1.Here, allpointsofthepointprocessarecon-
nected to their k-nearest neighbors, for some fixed k∈N. This results in a graph that is the undirected
variant of a directed graph with out-degrees bounded by k, which itself also has degrees larger than
k. Let us write kU,𝑑 for the minimum of all k∈Nsuch that the U-kNN-graph of the stationary PPP
in R𝑑percolates with positive probability. It was shown in [13] that kU,𝑑 >1forall𝑑∈N,however,
kU,𝑑 =2 for all sufficiently large 𝑑. This was complemented in [26] by the assertion that kU,𝑑 <∞for
all 𝑑≥2.
Balister and Bollobás [1] studied the case 𝑑=2. They also introduced another undirected graph,
which is contained in the U-kNN graph, called the bidirectional k-nearest neighbor (B-kNN) graph,
see bottom line of Figure 1. Here, one connects two points of the point process if and only if they
are mutually among the k-nearest neighbors of each other. This graph has in fact degrees bounded
by k, which immediately implies that there is no percolation for k=1, whatever the vertex set is
(note that in the PPP case this also follows from the results of [13]). Define the critical out-degree
kB,𝑑 analogously to kU,𝑑 but with Ureplaced by B.Itwasshownin[1] that kU,2≤11 and kB,2≤15.
Further, “high-confidence results” of [1] indicate kU,2=3andkB,2=5. By “high-confidence
results,” the authors of that paper meant that these assertions follow once one shows that a certain
242 JAHNEL AND TÓBIÁS
deterministic integral exceeds a certain deterministic value; however, the integrals were only evalu-
ated via Monte–Carlo methods so far. Hence, from a mathematical point of view, these are still open
conjectures, but there is very strong numerical evidence that they are true.
Another line of research on percolation of bounded-degree spatial graphs with unbounded-range
dependencies, which is also close to applications in wireless networks, is signal-to-interference plus
noise ratio (SINR) percolation, introduced in [6, 7]. Here, a transmission in the network is considered
successful if and only if, measured at the receiver, the incoming signal power of the transmitter is
larger than a given threshold times the interference (sum of signal powers) coming from all other
users plus some external noise. Then, the SINR graph is constructed by drawing an edge between two
vertices whenever the transmission between them is successful in both directions, see Section 4.2 for
more details. This graph has bounded degrees (see [6, theorem 1]), where the smallest degree bound
kdepends on the model parameters. If the transmitted signal powers are all equal, then the SINR
graph is contained in the corresponding B-kNN graph (see [24, lemma 4.1.13]) and hence also of the
U-kNN graph.
In general, if in an undirected graph all degrees are bounded by k=2, all infinite connected com-
ponentsmustbepathgraphs(nocycles,nobranchings),infiniteinoneor twodirections,whichmakes
thegraphsimilartoa one-dimensionalcontinuumpercolationmodel,indicatingthatunder rather gen-
eral conditions, there should be no infinite connected component. Certainly, there are deterministic
point processes where percolation is possible, but a little bit of randomness can be expected to suffice
for nonpercolation. In our recent paper [15], we showed that in SINR graphs based on general sta-
tionary Cox point processes (CPPs) in any dimension, under rather general choices of the parameters
resulting in degrees bounded by 2, there is no percolation.
In the present paper, moving away from the particular setting of SINR graphs, we present anal-
ogous results in a general framework, extending the methods of the proof of [15, theorem 2.2]. We
consider a generalization of the B-kNN graph, called the f-kNN graph. Here, points of the underly-
ing marked point process are connected by an edge whenever they are mutually among the knearest
neighborsofeachotherwithrespecttoanordering that may also dependonsomemarksofthepoints,
apart from the (not necessarily Euclidean) distance of the points. The ordering is expressed in terms
of a function f, hence the name f-kNN graph. We show that under suitable conditions on the underly-
ing stationary marked point process, the f-kNN graph does not percolate for k=2. This in particular
implies nonpercolation of subgraphs of the f-kNN graph depending on additional randomness. In
fact, our results extend to all stationary point processes that are deletion-tolerant in the sense of [14].
This includes all CPPs satisfying a basic nondegeneracy condition, and a large class of Gibbs point
processes.
As a special case, our results imply that for general stationary CPPs, the B-2NN graph does
not percolate. This in particular implies that kB,2≥3, which provides a partial verification of the
high-confidence results of [1]. Note that this result does not follow from [15, theorem 2.2] because in
general, if the SINR graph is contained in a B-2NN graph, it is a proper subgraph of it with substan-
tially less edges. After stating and proving our main results, we also present examples of graphs with
degrees bounded by 2 that are not contained in an f-2NN graph but where our proof techniques are
also applicable, and also ones where they are not applicable.
Our setting is also related to the line of research on outdegree-one graphs, which were introduced
in [3]. However, our results do not follow from the results of that paper, and also not the other way
around. We will comment on the similarities and differences of the two models in Section 4.4.
The rest of the paper is organized as follows. In Section 2we present our setting and main result.
In Section 3we provide the proofs for our main result. Section 4is devoted to examples, extensions of
our methods, and discussions.
JAHNEL AND TÓBIÁS 243
2MODEL DEFINITION AND MAIN RESULT
In this section we present our model definition and main results. Our setting is as follows. Let 𝑑∈N,
and let ||⋅||be an arbitrary norm on R𝑑.Further,let(R𝑑)denote the Borel-𝜎-algebra of R𝑑(clearly,
||⋅||generatesthestandardtopologyofR𝑑,whichgenerates(R𝑑)).Moreover,considerthemeasurable
space (M,), which serves as a mark space.
Next, let X={(Xi,Pi)}i∈Ibe a marked point process in R𝑑×M,sothatX={Xi}i∈Iis a stationary
point process in R𝑑with finite intensity 𝜆=E[X([0,1]𝑑)],thatisnonequidistant. This means that for
all i,j,k,l∈I,||Xi−Xj||=||Xk−Xl||>0 implies {i,j}={k,l}and ||Xi||=||Xj||implies i=j,
almostsurely.Clearly,thispropertyimpliesthatthepointprocessXissimple,thatis,P(Xi≠Xj,∀i,j∈
Iwith i≠j)=1.Forillustration,notethattherandomlyshiftedlatticeZ𝑑+U,whereUis auniform
random variable in [0,1]𝑑, is a simple stationary but not nonequidistant point process on R𝑑.
Next, we introduce a total ordering of the points. For this, let f∶[0,∞) × M→[0,∞) be a
measurable function such that v→ f(v,q)is monotone decreasing for all q∈M. We call such a
function an ordering function.
Definition2.1. Let fbe an ordering function and (v1,q1),(v2,q2),(v3,q3)∈R𝑑×M.Wesaythatv2
is f-closer to v1than to v3if one of the following conditions is satisfied:
1f(||v1−v2||,q1)<f(||v3−v2||,q3),or
2f(||v1−v2||,q1)=f(||v3−v2||,q3)and ||v1−v2||<||v3−v2||.
Then, it is elementary to verify the following lemma.
Lemma 2.2. Let f be an ordering function. For Xdefined as above and X nonequidistant, almost
surely, the following holds. For all i ∈I, the relation “Xiis f-closer to Xjthan to Xl”isatotalordering
(i.e., irreflexive, antisymmetric and transitive, with any two elements being comparable) on the set
{(j,l)∈I×I∶j≠iand l≠i}, which we call the f-ordering.
Thus, if x={(xi,pi)}i∈Iis a deterministic, locally finite, infinite, and nonequidistant set of
points in R𝑑×M(for some countable index set I)andvo∈x∶= {xi}i∈I, we can represent xas
x={vf
n(vo,x)}n∈N0,wherev
f
0(vo,x)=vo,andv
f
n(vo,x)is the nth nearest neighbor of voin xwith
respect to the f-ordering for any n∈N0. Next, we build a graph based on the f-ordering.
Definition 2.3. Let fbe an ordering function, k∈Nand Xdefined as above with Xnonequidis-
tant, almost surely. The f-k-nearest neighbor (f-kNN) graph gk,f(X)is the random graph having
vertex set Xand for all i∈Iand n∈{1,…,k}an edge between Xiand vf
n(Xi,X)whenever
Xi∈{vf
1(vf
n(Xi,X),X),…,vf
k(vf
n(Xi,X),X)}.
As the next example shows, the B-kNN graph is an f-kNN graph for a point process with trivial
marks. Let us write {⋆}for the one-point measurable space (with ={Ø,{⋆}}).
Example 2.4. Consider a nonequidistant point process Xin R𝑑,𝑑≥1, and equip Xwith trivial
marks in M={⋆}. Then, f(v,q)=f(v)=vyields the B-kNN graph based on X.
We will explain the relations between f-kNN graphs and SINR graphs in Section 4.2.
Apartfromthebasicrequirementofbeingnonequidistant,thepropertyofdeletion-tolerance intro-
duced in [14] is the most important requirement on the marked point process. An X-point is an
244 JAHNEL AND TÓBIÁS
(R𝑑×M)-valued random variable z, defined on the same probability space as X, such that z∈Xa.s.,
and one says that Xis deletion-tolerant if for any X-point z, the distribution of X∖{z}is absolutely
continuous with respect to the one of X.See[14, theorem 1.1] for the equivalent formulations of this
property for nonmarked point processes. We will present examples of marked point processes that are
deletion-tolerantbelow. Equippedwiththe above definitions, we are nowable to state ourmainresult.
Theorem2.5. Let f be an ordering function and let the deletion-tolerant marked point process Xbe
such that the underlying point process X is stationary, nonequidistant and has a finite intensity. Then,
we have
P(g2,f(X)percolates)=0.
TheproofofthistheoremiscarriedoutinSection3.InSection4.2wediscusstherelationbetween
the proof of Theorem 2.5 and the one of [15, theorem 2.2]. In Section 4.3 we will explain how it
extendstoother graphs that aredefinedsimilarly,havedegreesbounded by2,butare notsubgraphsof
f-kNN graphs. A key ingredient in the proof of Theorem 2.5 and its aforementioned extensions is the
so-called edge-preserving property of the underlying graph, which we will introduce in Definition 3.2
below.
Note that deletion-tolerance is satisfied by many point processes, as is shown by the following
proposition, see also [14] for more examples without marks.
Proposition 2.6. Any i.i.d.-marked CPP Xon R𝑑×M is deletion-tolerant. Further, any
infinite-volume Gibbs point process Xon R𝑑×M based on an Hamiltonian H is deletion-tolerant,
whenever M is a Polish space equipped with the associated Borel 𝜎-algebra, and for all bounded
measurable Λ⊂R𝑑and almost-all boundary conditions y
ZΛ(y)=∫Λ(dxΛ)exp(−HΛ(xΛ∪yΛc)) <∞,
where Λis an i.i.d.-marked Poisson point process in Λand yΛc={(v,q)∈y∶v∈R𝑑∖Λ).
The proof of this proposition is presented in Section 4.1. Note that the class of stationarity and
nonequidistant CPPs includes the homogeneous PPPs. The class of Gibbs point processes satisfying
theaboveconditionisveryrichandinparticularincludestheclassicalexamplesofsuperstableHamil-
tonians, see [5] and references therein. Moreover, there are also well-known point processes that are
not deletion-tolerant. A very straightforward class of such processes is the following. As introduced
in [9, 18], we say that the point process Xis number rigid if for any ⊂R𝑑compact, there exists a
deterministic measurable function hsuch that,
#(X∩)=h(X∖),
almostsurely,thatis,XoutsidedeterminesthenumberofpointsofXin.Thefollowingproposition
states that number rigid point processes fail to be deletion-tolerant.
Proposition2.7. IfthenonmarkedversionX ofthemarkedpointprocessXisstationaryandnumber
rigid with positive intensity, then Xis not deletion-tolerant.
This proposition follows immediately from results of [14], see Section 4.1 for a proof.
JAHNEL AND TÓBIÁS 245
According to [9], the Ginibre ensemble and the Gaussian zero process are number rigid point
processes in R2, which are also stationary, nonequidistant, and of positive intensity. Hence, the proof
of Theorem 2.5 is not applicable for them. We nevertheless believe that they satisfy the assertion of
the theorem, but the proof would require additional arguments.
3PROOF OF THEOREM 2.5
The proof of the Theorem 2.5 proceeds along the following line of arguments. We first show that
with probability 1, clusters, that is, maximally connected components, are either finite or they consist
only of points of degree 2, see Lemma 3.1 below. Next, we assume for a contradiction that there
existsaninfiniteclusterwithpositiveprobability.Then,weintroduceaprocedurethatremovesafinite
subprocess from the infinite cluster that is closest to the origin in a certain sense associated with the
f-ordering. (Below we will provide a formal definition of a finite subprocess of X). In the resulting
configuration, the infinite cluster still remains infinite, but it contains a vertex of degree 1. Hence, the
probabilitythattheprocesstakesvaluesinthesetoftheresultingconfigurationsiszero.Thenitremains
to show that also the probability that the process takes place in the set of original configurations is
zero, which leads to the desired contradiction. This last step relies on the deletion-tolerance of Xand
uses a certain result from [14] that we will recall below.
NotethatfortheproofofTheorem2.5,wecanassumethattheintensity𝜆oftheunderlyingstation-
arypointprocessispositive,sinceotherwiseTheorem2.5istriviallytrue.Westartwiththefollowing,
previouslyprovenlemma, whichexcludesexistenceofinfiniteclusters that have adegree-one point in
the case of general random graphs based on stationary marked point processes.
Lemma 3.1. [15, Lemma 5.4]Let g(X)be a random graph based on a marked point process X
such that the degree of all Xi∈X, deg(Xi), is bounded by 2, almost surely. Let X be stationary and
nonequidistant with a finite intensity, and consider the point process of degree-one points in infinite
clusters 0=∑
i∈I𝛿Xi𝟙{deg(Xi)=1,Xiis part of an infinite cluster in g(X)}.
Then, P(0(R𝑑)=0)=1.
The proof is based on a certain variant of the mass-transport principle (see [3, section 4.2] for
instance).Informallyspeaking,theproofgoesasfollows:Iftherewasaninfiniteclusterhavingapoint
of degree one, then by stationarity, the point process of degree-1 points of infinite clusters 0would
have to have a positive density. This, however, leads to a contradiction because any infinite cluster
can only contain at most one degree-1 point and must contain infinitely many degree-2 points, which
implies that the aforementioned density must be equal to zero. We refer the reader to [15, section 5.2]
for further details.
In will be convenient to assume that XtakesvaluesinthesetNof marked point configurations
xin R𝑑×Msuch that x={xi∶(xi,pi)∈x}is an infinite, locally finite, nonequidistant point
configuration on R𝑑. We will denote by Nthe set of such point configurations xand equip Nand N
with the corresponding evaluation 𝜎-fields.
OneessentialpropertythatwewilluseintheproofofTheorem2.5istheso-callededge-preserving
propertyoftheunderlyingf-kNNgraph.Informallyspeaking,thismeansthatifweremovepointsfrom
246 JAHNEL AND TÓBIÁS
aconfiguration,then edgesbetweenremaining points are preserved. Nowwe provide the definition of
this property corresponding to our configuration spaces.
Definition 3.2. Let g∶N→N×(N×N),x→ g(x)=(x,Eg(x)) be a function that maps a marked
point configuration xto a graph with vertex set x.Wesaythatgis edge-preserving if for all y,x∈N
with y⊆x,forall(v1,q1),(v2,q2)∈ysuch that (v1,v2)∈Eg(x), one has (v1,v2)∈Eg(y).
Let us, for the remainder of this section, fix an ordering function f. It is then easy to see that the
f-kNN graph gk,f∶x→ gk,f(x)is edge-preserving for all k∈N. See Sections 4.2 and 4.3 for further
examples of edge-preserving graphs.
Now, for x∈Nand vo∈x, we consider the sequence (vn(vo,x))n∈N0of the marked points
of xordered in increasing f-order of x, measured from vo. Then, nonboldface vi(vo,x), as defined
in Section 2, is the first component of vi(vo,x), which we call the ith nearest f-neighbor of vo.In
particular, recall that v0(vo,x)=vo.
Next, if vohas degree twoin g2,f(x),thenvois connected byanedgetobothv1(vo,x)andv2(vo,x).
Moreover, both v1(vo,x)and v2(vo,x)also have voas one of their first two nearest f-neighbors, that is,
vo∈{v1(vi(vo,x),x),v2(vi(vo,x),x)},
for all i∈{1,2}.Thesek-nearest f-neighbor relations hold almost surely and in particular for every
nonequidistant configuration x. Thanks to the choice of our configuration space N, we can entirely
exclude configurations that offend the degree bound or the k-nearest f-neighbor relations or are not
nonequidistant. In particular, the f-2NN graph g2,f(x)is well-defined for all x∈N.
Given this, for x∈N,wedefine𝓁(x)∈[0,∞] as the number of infinite clusters in g2,f(x),andin
case 𝓁(x)>0, we let z(x)=(z(x),r(x)) denote the closest point of xto the origin such that z(x)has
degreetwoandiscontainedinaninfiniteclustering2,f(x),andwewrite1(x)fortheclustercontaining
z(x).
Now, in order to show that the probability that g2,f(X)percolates is zero, it suffices to verify that
P(𝓁(X)≥1)=0.(3.1)
Next,forx∈Nwith𝓁(x)≥1,wedefinethethird-nearestf-neighborofz(x)withintheinfinitecluster
1(x)by
𝜏(x)=inf{i≥3∶vi(z(x),x)∈1(x)}.
Indeed, among the points vj(z(x),x),j<𝜏(x), precisely two (namely, v1(z(x),x)and v2(z(x),x))are
contained in 1(x). In case 𝓁(x)=0, we put 𝜏(x)=∞. Then, we have the following assertion.
Proposition 3.3. Under the assumptions of Theorem 2.5, for any natural number i ≥3,wehave
P({𝓁(X)≥1}∩{𝜏(X)=i}) = 0.(3.2)
Before proving Proposition 3.3, let us show why it implies Theorem 2.5.
Proof of Theorem 2.5. Noting that {𝓁(X)≥1}⊂{𝜏(X)<∞} and using a union bound,
Proposition 3.3 implies P(𝓁(X)≥1)=0, which is (3.1), and thus finishes the proof of
Theorem 2.5.▪
JAHNEL AND TÓBIÁS 247
In order to verify Proposition 3.3, let us now present a preliminary result. First, we say that a point
process Yis a finite subprocess of Xif Yis defined on the same probability space as X, satisfies
#Y<∞andY⊂Xalmostsurely.Thenwehavethefollowingclaim:IfXisdeletion-tolerant,thenfor
any subprocess Yof X,thelawofX∖Yis absolutely continuous with respect to the one of X. Indeed,
for M=Rl,l≥0, the claim followsfrom [14, theorem 1.1]. Now we verify it in the case of general M
analogously to the proof presented for the case M=Rlin [14, section 3]. Let us assume that for some
measurable subset of Nwe have P(X∖Y∈)>0. Then, there must exist some n∈Nsuch that
P({X∖Y∈}∩{#Y=n}) >0. Set Yn=Yif #Y=nand set Yn=Ø otherwise. Then, it follows
that P(X∖Yn∈)>0. Since Xis deletion-tolerant, it follows that P(X∈)>0, as claimed.
Next, we observe the following. For x∈Nwith 𝓁(x)≥1, by definition, we have that z(x)is
connectedbyanedgebothtov1(z(x),x)andv2(z(x),x)ing2,f(x).Further,sincethedegreesarebounded
by two, for such x,v
1(z(x),x)and v2(z(x),x)have no further joint neighbor in g2,f(x)since otherwise
1(x)hasaloopandcannotbeinfinite.Hence,foranyi≥3,thereexistsl∈{1,2}suchthatvi(z(x),x)
and vl(z(x),x)are not connected by an edge in g2,f(x). Let us denote the corresponding vl(z(x),x)by
mi(x), and define mi(x)=v1(z(x),x)if neither v1(z(x),x)nor v2(z(x),x)is connected to vi(z(x),x)by
an edge. The element of {v1(z(x),x),v2(z(x),x)} not being equal to mi(x)is denoted by ni(x). We will
write qi(x)for the mark of mi(x).
Letusdefinethesetofconfigurationsinwhichtheinfiniteclusterclosesttotheoriginisone-armed
B={x∈N∶𝓁(x)≥1and1(x)contains a point of degree one},
andnotethatB⊂{x∈N∶𝓁(x)≥1}.Withthis,forx∈N,letusdefinethefinitepointconfiguration
y(x)={{v3(z(x),x),…,v𝜏(x)−1(z(x),x),(m𝜏(x)(x),q𝜏(x)(x))} if 𝓁(x)≥1andx∉B,
Ø,if 𝓁(x)=0orx∈B.
Letusfixi≥3.Letx∈Nbesuchthat𝓁(x)≥1and𝜏(x)=i.Then,wedefineathinnedconfiguration
xi=x∖y(x),
and put xi={v∶(v,q)∈xi}for the corresponding nonmarked configuration.
We claim that {𝓁(x)≥1}∩{𝜏(x)=i}is a subset of {𝓁(xi)≥1}. For this, first note that the
removal of finitely many points of the point process can change the edge structure of the remaining
points. Nevertheless, it cannot remove edges that were already present before the removal of points
since g2,fis edge-preserving. Hence, all edges between two points of xiin g2,f(x)also exist in g2,f(xi).
In particular, if g2,f(x)contains an infinite cluster, then g2,f(xi)contains all but at most finitely many
edges of this cluster. This implies that 𝓁(xi)≥1, hence the claim.
Then, the next claim is that for x∈Nwith 𝓁(x)≥1and𝜏(x)=i,wehavethatxiis contained in
B. The proof of this claim is clear if x∈Bsince then xi=x. Thus, we now consider the case x∉B.
This case is illustrated in Figure 2. Recall that for x∈N,z(x)cannot have degree higher than two in
g2,f(xi), whereas it has degree at least one and its cluster 1(xi)is infinite in g2,f(xi).Notealsothat
the edge between z(x)and ni(x)still exists in g2,f(xi).Further,ifz(x)has degree two in g2,f(xi),then
it is connected to the second-nearest f-neighbor toward z(x)in xi,whichisv
2(z(x),xi)=vi(z(x),x),
whereas v1(z(x),xi)=ni(x).Now,sincex∉B,𝓁(x)≥1andv
i(z(x),x)∈1(x), it follows that
vi(z(x),x)has degree equal to two in g2,f(x). Further, it is neither connected to mi(x)by an edge nor to
z(x)in this graph. Hence, both edges adjacent to vi(z(x),x)also exist in g2,f(xi). But since vi(z(x),x)
248 JAHNEL AND TÓBIÁS
FIGURE 2 An illustration of the removal of the finite subconfiguration y(x)={(mi,qi),v3(z(x)),…,vn−1(z(x))} from the
configuration xsatisfying 𝓁(x)≥1, 𝜏(x)=i≥3andx∉B. The point vi=vi(z(x),x)is contained in the infinite cluster
1=1(x)including z=z(x), and it is not a neighbor of mi=mi(x), which equals v1=v1(z(x),x)here, whereas
v2=v2(z(x),x)=ni=ni(x). (In the figure we use the short-hand notations vj=vj(z(x),x)for all values of j.) Hence, if vihas
degree two in 1, then there are various possibilities respecting the degree bound of two to connect vito 1so that it is not
connected to miby an edge. vican either be a direct neighbor of v2(see dashed line) or a further point of the path from zto
infinitystartingwiththe edgefromztov2(dash-dottedlines)oranondirectneighborofv1onthepathfromztoinfinitystarting
with the edge from zto v1(dotted lines). Now, removing the finite subconfiguration y(x)from the realization (the nonmarked
points corresponding to yare colored red in the figure), in the resulting f-2NN graph of xi=x∖y(x), both edges adjacent to vi
are preserved. Also all edges from zto infinity starting with the edge from zto v2are preserved, hence zis still contained in an
infinite cluster, but the edge from zto v1is removed. In the resulting new configuration, the second-nearest f-neighbor toward
zis vi, and hence this is the only point of the configuration that could be connected to zby an edge. But vistill cannot have
degree 3 or more, hence it cannot be connected to z. Thus, in the new configuration, zis in an infinite cluster and has degree 1
has degree at most two in g2,f(xi), it follows that z(x)and vi(z(x),x)are not connected by an edge in
this graph. Hence, xi∈B, which implies the claim.
Note that by Lemma 3.1,thesetBis a P-null set, that is,
P(X∈{xi∶x∈N,𝓁(x)≥1and𝜏(x)=i}) = 0.(3.3)
This implies (3.2). Next, we have the following lemma.
Lemma3.4. Under the assumptions of Theorem 2.5,foranyi≥3,P({𝓁(X)≥1}∩{𝜏(X)=i}) >0
implies P(X∈{xi∶x∈N,𝓁(x)and 𝜏(x)=i}) >0.
Before proving the lemma, let us now explain why it implies Proposition 3.3.
Proof of Proposition 3.3. By Lemma 3.4, where we show that if the collection of thinned configu-
rations is contained in a P-null set, also the nonthinned configurations form a P-null set, we see that
(3.3) implies (3.2), which concludes the proof of Proposition 3.3.▪
Finally, it remains to verify Lemma 3.4. Its proof strongly relies on deletion-tolerance.
Proof of Lemma 3.4. Let us fix i≥3 and assume that P({𝓁(X)≥1}∩{𝜏(X)=i}) >0. For the
finite subprocess Y=y(X)of Xthis means that
0<P({𝓁(X)≥1}∩{𝜏(X)=i}) = P(X∈{x∈N∶𝓁(x)≥1,𝜏(x)=i})
≤P(X∖Y∈{xi∶𝓁(x)≥1,𝜏(x)=i}).
Next, since Xis assumed to be deletion-tolerant and Yis a finite subprocess of X, by the equivalent
characterization of deletion-tolerance as presented below Proposition 3.3, it follows that the law of
X∖Yis absolutely continuous with respect to the one of X. This yields
0<P(X∈{xi∶𝓁(x)≥1,𝜏(x)=i}).
This implies the lemma. ▪
JAHNEL AND TÓBIÁS 249
4EXAMPLES, DISCUSSION, AND EXTENSIONS
4.1 Examples of deletion-tolerance
In this section, we verify Propositions 2.6 and 2.7. We first carry our the proof of Proposition 2.6.
Proof of Proposition 2.6. First, let Xbe an i.i.d. marked CPP, where Xis stationary and
non-equidistant. Then, due to the i.i.d. markings, Xcan be seen as a PPP with random directing mea-
sure Γ(dv)⊗(dq),whereis the distribution of the marks and Γis the (random) intensity of the
unmarked CPP, see for example, [20, section 13]. Consider an event such that P(X∈)=0, then,
bythedefinitionofdeletiontolerance,itsufficestoshowthatforanyboundedmeasurablesetB⊂R𝑑,
we have
E[∑
Xi∈X∩B𝟙{X∖Xi∈}]=0.
But, using the Mecke formula for PPPs in general measurable spaces, see [20, theorem 13.8], we have
that
E[∑
Xi∈X∩B𝟙{X∖Xi∈}]=E[Γ(B)P(X∈|Γ)] = 0,
as desired.
LetnowXbeastationaryGibbspointprocesses.AsintheproofofProposition2.7below,wewant
toemployanequivalentcharacterizationofdeletiontoleranceviaalmost-surepositivityofconditional
void probabilities, see [14, theorem 1.1] for the case of unmarked point processes. In order to lift this
to the level of marked point processes we extend the arguments as exhibited in [14].However,first
note that by our assumptions, for all bounded measurable Λ⊂R𝑑, and almost all realizations XΛcof
Xin Λc,wehave
P(XΛ=Ø|XΛc)≥e−𝜆|Λ|Z−1
Λ(XΛc)>0,
where 𝜆>0 denotes the intensity of the underlying unmarked Poisson point process.
Using this, on a general level, if for some bounded Λ⊂R𝑑and measurable ⊂R𝑑×M,wehave
P(XΛc∈)>0,thenP(X∈)≥P(XΛc∈,XΛ=Ø)=E[𝟙{XΛc∈}P(XΛ=Ø|XΛc)] >0and
hence,thelawofXΛcis absolutelycontinuouswithrespect tothelaw ofX.Inordertodeducedeletion
tolerance from this absolute continuity, we consider open balls B(x,r)in R𝑑×M,wherex∈Q𝑑×D,
withDacountable-densesubsetofthePolishspaceM,andr≥0isrational.WeletCdenotethesetof
unions of finitely many such balls. Then, by the local finiteness of X,forallX-points Z, there exists a
C-valued randomvariable𝚪such that P(X𝚪=𝛿Z)=1. But then, if forsomemeasurable⊂R𝑑×M
we have P(X−𝛿Z∈)>0, it follows that
0<P(X−𝛿Z∈,X𝚪=𝛿Z)=P(X𝚪c∈)=∑
Γ∈CP(X𝚪c∈,𝚪=Γ),
and hence P(XΓc∈)>0forsomeΓ. But this implies P(X∈)>0 by the absolute continuity
asserted above. ▪
Finally, we prove Proposition 2.7. The proof is based on the following lemma.
250 JAHNEL AND TÓBIÁS
Lemma4.1. LetthemarkedpointprocessXbedeletion-tolerant.Then,theunderlyingpointprocess
X is also deletion-tolerant.
In order to keep the proof short, we again assume that Xtakes values in the configuration space N
and Xin the configuration space N, which were defined in Section 3.
Proof. Let Abe any measurable subset of N.Further,letYbe any X-point. Let Pbe the mark of Y
(defined realizationwise). Then (Y,P)is an X-point and we have
P(X∈A)=P(X∈A,(Pi)i∈N∈MN)=P(X∈A×MN).
Since A×MNis a measurable subset of Nand Xis deletion-tolerant, we have
0<P(X∖{(Y,P)} ∈ A×MN)=P(X∖{Y}∈A).
Hence, the distribution of X∖{Y}is absolutely continuous with respect to the one of X,as
wanted. ▪
Proof of Proposition 2.7. Thanks to Lemma 4.1, it suffices to show that Xis not deletion-tolerant.
Further, as already mentioned in the proof of Proposition 2.6, the following assertion is known from
[14,theorem1.1]:IfXisdeletion-tolerant,thenforanyboundedS∈(R𝑑),wehavethatalmostsurely
P(X∩S=Ø|X∩Sc)>0.(4.1)
Assumenowthattheconditionsofthepropositionaresatisfied.Let∈(R𝑑)becompact.Since
Xis stationary with positive intensity, there exists some k∈Nsuch that
P(#(X∩)=k)>0.
Let us now consider the measurable set F=h−1
(k).Wehave
P((X∩c)∈F)>0.
Hence, the conditional probability
P(X∩=Ø|X∩c∈F),(4.2)
is well-defined. However, since {X∩c∈F}⊆{#(X∩)=k},(4.2) equals zero. This shows
that for our choice of Xand for S=, the assertion (4.1) does not hold, and hence Xis not
deletion-tolerant. ▪
4.2 SINR graphs as subgraphs of f-kNN graphs
Let us briefly summarize the relation between Theorem 2.5 and [15, theorem 2.2]. Indeed, the two
proofs are similar, in particular, two steps of the proof, Lemma 3.1 and the part of Proposition 2.6
regarding the Cox case already appeared in [15].However,in[15] we focused on the particular
case of SINR graphs based on stationary and nonequidistant CPPs, having concrete applications in
JAHNEL AND TÓBIÁS 251
telecommunicationsinmind,and wedid notaimat checkingwhether our proofworks also forawider
classofpointprocessesorgraphs.Thus,themainnoveltyinthispaperisnotthatweexploitnewproof
techniques (although the proofs of Proposition 2.7 and the part of Proposition 2.6 regarding Gibbs
point processes have no analogues in [15]). Instead, we highlight that apart from the general combi-
natorial condition of working with undirected and stationary random graphs with degrees bounded by
two, two properties are crucial for a straightforward generalization of the proof in [15]: (1) the dele-
tion tolerance of the underlying point process and (2) the edge-preserving property of the graph. The
latter observation allows for the extensions of Theorem 2.5 presented in Section 4.3.
This puts the result into a general framework and allows for generalizations of the result both with
respect to the type of graph and with respect to the kind of point process. Here, let us note that the
SINR graph is not a special case of an f-kNN graph, but a proper subgraph of an f-2NN graph under
particular choices of the parameters, which is itself edge-preserving. Nonpercolation in f-2NN graphs
was not even known before the present paper in the simplest case represented by the B-2NN graph.
In order to make the relation between f-kNN graphs and SINR graphs explicit we recall the
definitionandinterpretationofthelattergraphs.LetM=N=[0,∞),||⋅||=||⋅||2,Pobeanonnegative
randomvariable, andX={(Xi,Pi)}i∈Iani.i.d.markedpointprocessinR𝑑×[0,∞) suchthatallPiare
distributed as Po.Let𝓁∶(0,∞) →[0,∞), the so-called path-loss function, be a monotone decreas-
ingfunction.Typicalexamples ofpath-lossfunctionscorrespond to Hertzian propagation (see [6, 7]),
for example, for 𝛼>𝑑, the unbounded function 𝓁(r)=r−𝛼, its truncated variant 𝓁(r)=min{1,r−𝛼},
and its “shifted” variant 𝓁(r)=(1+r)−𝛼.Now,definef(x,p)=1∕(p𝓁(||x||)). In a telecommunication
context, for (Xi,Pi)∈Xand x∈R𝑑,Piexpresses the signal power transmitted by a device at spa-
tial position Xi,and𝓁describes propagation of signal strength over distance. Note that 𝓁need not be
strictly decreasing, which gives relevance to Part (2) of Definition 2.1 in order to make the f-ordering
well-defined. We observe that in case Pois almost surely equal to a fixed positive constant, then the
arising f-kNN graph is the B-kNN graph.
In this setting, the SINR graph [6] is usually introduced in the following way. Let Nobe another
nonnegativerandomvariable independent of X. Choose two further parameters 𝛾,𝜏 > 0, the so-called
interference-cancellation factor andthe SINR threshold, respectively, and for i,j∈I,i≠j, connect Xi
and Xjby an edge whenever the SINR constraint is satisfied in both directions, that is,
Pi𝓁(|Xi−Xj|)>𝜏(No+𝛾∑
k∈I∖{i,j}
Pk𝓁(|Xk−Xj|)),(4.3)
andthesameholdswiththerolesofiandjinterchanged.Then,itisknownfrom[6,theorem1]thatifX
isasimplepointprocess (evenifnot stationarityornotnonequidistant),alldegrees in the SINR graph
are less than k=1+1∕(𝜏𝛾). Using the elementary arguments of [24, lemma 4.1.13], one can easily
verify that if X={Xi}i∈Iisalsononequidistant,thentheSINRgraphisasubgraphofthef-kNNgraph
of the present example. Further, if No>0 is deterministic, then the SINR graph has bounded edge
lengths and hence isasubgraph of the Gilbert graph introduced in [10].Thesameassertionholdsalso
for No=0incase𝓁has bounded support. For positive assertions about percolation in SINR graphs
based on various kinds of point processes, we refer the reader, for example to [2, 6, 7, 15, 19, 24, 25].
Hence, for point processes satisfying the conditions of Theorem 2.5, there is no percolation in
the SINR graph if its degrees are bounded by 2, which is always the case if 𝛾≥1∕(2𝜏). Thanks
to Proposition 2.6, in particular, Gibbs point processes are covered by this result. To the best of our
knowledge, there have been no results about SINR percolation for Gibbs point processes before (apart
from the degree bounds themselves). Regarding nonpercolation in case degrees are bounded by two,
the case of CPPs was handled in [15, theorem 2.2]. Here, based on the observation [15, section 5.2,
252 JAHNEL AND TÓBIÁS
proof of proposition 5.8] that SINR graphs are edge-preserving on their own right in the sense of
Definition3.2,wecarriedoutacertainvariantoftheproofofTheorem2.5fortheSINRgraphdirectly,
with no direct reference to f-kNN (or even B-kNN) graphs.
The aforementioned positive results on SINR percolation guarantee that for various kinds of point
processes, the SINR graph percolates with positive probability for some positive 𝛾given that 𝜆is
sufficiently large, while all the other parameters (depending on the type of point process) are fixed. In
other words, we know that k∗<∞holds for the infimum k∗of all degree bounds ksuch that there
existsanSINRgraphwithlargestdegreeequaltokthatpercolates.Therearemultipleinterestingopen
questionsrelatedtothis.First,whatisthesmallestvalueofsuchk∗,andhowdoesitdependonthetype
ofthepointprocess?Themainresultsofthepresentpaperimplythatforstationaryandnonequidistant
point processes that are deletion-tolerant, we have k∗≥3. Further, according to the high-confidence
resultsof[1],k∗≥5forthetwo-dimensionalPPP.Second,isthesmallestsuchdegreeboundthesame
for SINR graphs as for the underlying B-kNN graph? While the relationship between Gilbert graphs
and SINR graphs is clear (viz., Gilbert graphs are increasing limits of SINR graphs as 𝛾↓0), we are
not aware of results stating that the B-kNN graph is an increasing limit of certain SINR graphs with
degree bound k, and such a result may not be true in general. Namely, it may be the case that an SINR
constraint of the form (4.3) with degree bound k∈Nposes stronger restrictions on the edges of the
graph than a B-kNN constraint for the same k. We defer the investigation of such questions to future
work, noting that numerical evidence indicates that the two critical degree bounds are not the same in
general, see for example, Figure 3.
4.3 Extensions and limitations of the proof of Theorem 2.5
We now present examples of graphs with degrees bounded by two that are not contained in an f-2NN
graph but have rather similar properties to it, to the extent that the proof techniques of Theorem 2.5
are applicable to it.
Example 4.2 (Locally furthest neighbors).The edge-preserving property of f-kNN graphs (see
Definition 3.2) also holds if we replace the “k-nearest neighbors with respect to the f-ordering” in
their definition by “k-furthest neighbors in a bounded (possibly random) set shifted to the point,
w.r.t. f-ordering”. For the sake of simplicity of notation, let us explain how this works in the case of
B-kNN graph. The case of general f-kNN graphs can be handled similarly, taking into account also
themarksandusingthef-orderinginsteadoftheorderingofEuclideannorms.Weassumethroughout
this discussion that the point process Xis stationary, nonequidistant, and deletion-tolerant.
Let us fix a deterministic measurable set A⊆R𝑑of finite Lebesgue measure and define a random
graph with vertex set Xvia connecting two different points Xi,Xjof the point process Xby an edge
whenever Xjis one of the k∈Nfurthest neighbors in (A+Xi)∖{Xi}and the same holds with the roles
of iand jinterchanged. It is easy to see that this graph is well-defined and edge-preserving. Clearly,
for k=2 it has degrees bounded by two. Hence, non-percolation of the graph can be verified along
the lines of the proof of Theorem 2.5 also in the case of this graph. If Ais bounded, then the graph has
bounded edge lengths (unlike the B-kNN graph).
This approach can be extended to the case when the deterministic set A+Xiis replaced by a
random set AXiin such a way that {AXi}i∈Iare stationary, since the edge-preserving property and the
degree bound of two are still preserved. E.g., the proof techniques of Theorem 2.5 are still applicable
if {AXi}i∈Iis a Boolean model with random radii based on X={Xi}i∈I[21]. Instead of connecting Xi
tothetwofurthestneighborsinX∩AXibyanedge,onecanalsoconnectittothetwonearestneighbors
in X∩AXiand obtain the same result. We refrain from presenting further details here.
JAHNEL AND TÓBIÁS 253
FIGURE 3 B-kNN graphs (in the first line) and signal-to-interference plus noise ratio (SINR) graphs with degree bound k(in
corresponding order in the second line) for k=2,4,5, for Xbeing a stationary Cox point process. The random intensity
measure Λis given as the edge-length measure (i.e., the one-dimensional Hausdorff measure) of a two-dimensional
Poisson–Voronoi tessellation. The simulation leads to the conjecture that the smallest ksuch that the B-kNN graph percolates
is k=5, which would mean that it equals the one of the two-dimensional PPP (which is 5 according to the high-confidence
results of [1]). Further, it is known from [25] that in this case, for large enough 𝜆and accordingly chosen small 𝛾>0, there is
also percolation in the SINR graph. However, it does not seem to be the case that this already happens when the degree bound
equals 5, as the simulation suggests. Here, 𝛾is just slightly bigger than 1∕(5𝜏), that is, a small further increase of 𝛾would
increase the degree bound to 6, but the SINR graph is still much less connected than the corresponding B-5NN graph
Thenext exampleshows that therearegraphsdefinedverysimilarlytothef-2NNgraphforwhich
our methods are not applicable.
Example 4.3 (k1th and k2th nearest neighbors).Let k1,k2∈Nsuch that k1<k2. Similarly to
Definition 2.3,thef-k1th or k2th-nearest neighbor (f-(k1,k2)NN) graph g(k1,k2),f(X)is defined as the
random graph having vertex set Xand for all i∈Iand n∈{1,2}an edge between Xiand vf
n(Xi,X)
whenever Xi∈{vf
k1(vf
n(Xi,X),X),…,vf
k2(vf
n(Xi,X),X)}. In the case k1=1andk2=2, g(1,2),f(X)is
equaltothef-2NNgraphg2,f(X).However,itiseasytoseethatif(k1,k2)≠(1,2),thenthef-(k1,k2)NN
graph is in general not edge-preserving in the sense of Definition 2.3. This is a major obstacle for
generalizing the proof of Theorem 2.5 to the case (k1,k2)≠(1,2), despite the fact that many of the
proof ingredients of the theorem are still available in this case.
4.4 Relationof our model to outdegree-one graphs
In the setting of outdegree-one graphs [3], one considers directed percolation in a directed graph
arising as a deterministic and stationary function of a PPP in R𝑑, where each vertex has precisely
one out-degree. It was shown in [3] that under certain stabilization and looping conditions of the
254 JAHNEL AND TÓBIÁS
edge-drawing mechanism, this model does not percolate, in the sense that the out-component (or the
in-component) of any vertex is almost-surely finite, see also [11].In[23], it was shown that this result
is applicable for the example of the kth nearest neighbor graph, where the outgoing edge of a vertex
points to the kth nearest neighbor of the vertex in the point process. This setting looks rather similar
to the one that we are considering but is still different from it, for at least two reasons. First, although
it is tempting to think that the B-kNN graph can be obtained as a deterministic transformation of a
(stationary) outdegree-one graph satisfying the conditions of [3], we were not able to find such an
outdegree-one graph. Second, the kth nearest neighbor graph is only contained in the U-kNN graph,
not in the B-kNN one; in particular, the results of [23] cannot be derived from our ones.
ACKNOWLEDGMENTS
TheauthorsthankA. HinsenandC.Hirschfor interestingdiscussions andcommentsandD. Dereudre
for pointing out the reference [23]. The authors thank two anonymous reviewers for useful comments
on an earlier version of the manuscript, in particular for pointing out the reference [14].Further,the
second author thanks a number of participants of the spring school Complex Networks at TU Darm-
stadt for their insightful questions that enlightened that our methods for SINR graphs can be lifted
to the B-2NN graph. This work was funded by the Deutsche Forschungsgemeinschaft (DFG, Ger-
man Research Foundation) under Germany’s Excellence Strategy MATH+: The Berlin Mathematics
ResearchCenter,EXC-2046/1 projectID:390685689.Openaccess funding enabled andorganizedby
Projekt DEAL.
REFERENCES
1. P.BalisterandB.Bollobás,“Percolation in the k-nearest neighbor graphs,”Recentresultsindesignsandgraphs:A
tribute to Lucia Gionfriddo, Quaderni di Matematica, Vol 28, M. Buratti, C. Lindner, F. Mazzocca, and N. Melone
(eds.), Aracne, Aprilia, 2013, pp. 83–100.
2. B.BlaszczyszynandD.Yogeshwaran,Clusteringandpercolationofpointprocesses,Electron.J.Probab.18(2013),
1–20.
3. D. Coupier, D. Dereudre, and S. Le Stum, Absence of percolation for Poisson outdegree-one graphs, Ann. Inst.
Henri Poincaré Probab. Stat. 56 (2020), no. 2, 1179–1202.
4. D.CoupierandD.Dereudre,Continuumpercolationforquermassinteractionmodel,Electron.J.Probab.19(2014),
no. 35, 1–19.
5. D.Dereudre,“IntroductiontothetheoryofGibbs pointprocesses,”Stochasticgeometry,D.Coupier(ed.),Springer,
New York, NY, 2019, pp. 181–229.
6. O.Dousse,F.Baccelli,andP.Thiran,Impact of interferencesonconnectivity in adhocnetworks,IEEE/ACMTrans.
Netw. 1(2005), 425–436.
7. O. Dousse, M. Franceschetti, N. Macris, R. Meester, and P. Thiran, Percolation in the signal to interference ratio
graph, J. Appl. Probab. 43 (2006), 552–562.
8. S.Ghosh,M. Krishnapur,andY.Peres,Continuum percolation for Gaussian zeroes and Ginibre eigenvalues,Ann.
Probab. 44 (2016), no. 5, 3357–3384.
9. S. Ghosh and Y. Peres, Rigidity and tolerance in point processes: Gaussian zeroes and Ginibre eigenvalues,Duke
Math. J. 166 (2017), no. 10, 1789–1858.
10. E. N. Gilbert, Random plane networks, J. Soc. Ind. Appl. Math. 9(1961), 533–543.
11. C.Hirsch,Ontheabsence ofpercolationina line-segmentbasedLilypondmodel,Ann.Inst.HenriPoincaréProbab.
Stat. 52 (2016), no. 1, 127–145.
12. C. Hirsch, B. Jahnel, and E. Cali,Continuum percolation for Cox point processes, Stoch. Process. Their Appl. 129
(2019), no. 10, 3941–3966.
13. O.HäggströmandR.Meester,Nearest neighbor and hard sphere models in continuum percolation,RandomStruct.
Algorithms 9(1996), 295–315.
14. A. E. Holroyd and T. Soo, Insertion and deletion tolerance of point processes, Electron. J. Probab. 18 (2013), no.
74, 1–24.
15. B. Jahnel and A. Tóbiás, SINR percolation for Cox point processes with random powers, Adv. Appl. Probab., 54
(2022), 227–253.
JAHNEL AND TÓBIÁS 255
16. B. Jahnel, A. Tóbiás, and E. Cali, Phase transitions for the Boolean model of continuum percolation for Cox point
processes, Braz. J. Probab. Stat. 36 (2022), no. 1, 20–44.
17. S. Jansen, Continuum percolation for Gibbsian point processes with attractive interactions, Electron. J. Probab. 21
(2016), no. 47, 1–22.
18. M. A. Klatt and G. Last, On strongly rigid hyperfluctuating random measures, 2020, arXiv:2008.10907.
19. R. Löffler, Percolation phase transitions for the SIR model with random powers, Master’s thesis, Technische
Universität Berlin Institute of Mathematics, 2019, arXiv:1908.07375.
20. G. Last and M. Penrose, Lectures on the Poisson process, Cambridge University Press, Cambridge, MA, 2017.
21. R. Meester and R. Roy, Continuum percolation, Cambridge University Press, Cambridge, MA, 1996.
22. K. Stucki, Continuum percolation for Gibbs point processes, Electron. Commun. Probab. 18 (2013), no. 67, 1–10.
23. S. Le Stum, Deterministic walks on Poisson point process, ESAIM Proc. Surv. 60 (2018), 266–275.
24. A.Tóbiás,Messagerouteingand percolationin interferencelimitedmultihop networks,Doctoralthesis,Technische
Universität Berlin Institute of Mathematics. https://depositonce.tu-berlin.de/handle/11303/9293, 2019.
25. A. Tóbiás, Signal to interference ratio percolation for Cox point processes, Lat. Am. J. Probab. Math. Stat. 17
(2020), 273–308.
26. S. H. Teng and F. Yao, k-nearest-neighbor clustering and percolation theory, Algorithmica 49 (2007), 192–211.
How to cite this article: B. Jahnel, and A. Tóbiás, Absence of percolation in graphs based on
stationary point processes with degrees bounded by two, Random Struct. Algorithms. 62
(2023), 240–255. https://doi.org/10.1002/rsa.21084
