• No results found

Phase Transitions and Percolation at Criticality in Enhanced Random Connection Models

N/A
N/A
Protected

Academic year: 2022

Share "Phase Transitions and Percolation at Criticality in Enhanced Random Connection Models"

Copied!
40
0
0

Loading.... (view fulltext now)

Full text

(1)

https://doi.org/10.1007/s11040-021-09409-y

Phase Transitions and Percolation at Criticality in Enhanced Random Connection Models

Srikanth K. Iyer1·Sanjoy Kr. Jhawar1

Received: 11 September 2020 / Accepted: 23 September 2021 /

©The Author(s), under exclusive licence to Springer Nature B.V. 2021

Abstract

We study phase transition and percolation at criticality for three random graph models on the plane, viz., the homogeneous and inhomogeneous enhanced random connec- tion models (RCM) and the Poisson stick model. These models are built on a homo- geneous Poisson point processPλinR2of intensityλ. In the homogeneous RCM, the vertices atx, yare connected with probabilityg(|xy|), independent of everything else, whereg: [0,∞)→ [0,1]and|·|is the Euclidean norm. In the inhomogeneous version of the model, points ofPλare endowed with weights that are non-negative independent random variables with distribution P (W > w) = wβ1[1,)(w), β >0. Vertices located atx, y with weightsWx, Wy are connected with probability 1−exp

ηW|xxyW|αy

,η, α >0, independent of all else. The graphs are enhanced by considering the edges of the graph as straight line segments starting and ending at points ofPλ. A path in the graph is a continuous curve that is a subset of the union of all these line segments. The Poisson stick model consists of line segments of inde- pendent random lengths and orientation with the mid point of each segment located at a distinct point ofPλ. Intersecting lines form a path in the graph. A graph is said to percolate if there is an infinite connected component or path. We derive conditions for the existence of a phase transition and show that there is no percolation at criticality.

Keywords Random geometric graphs·Random connection model· Enhanced random connection model·Percolation·Phase transition· Continuity of the percolation function

Mathematics Subject Classification (2010) Primary: 82B43·60D05;

Secondary: 05C80

SKI’s research was supported in part by SERB Matrics grant MTR/2018/000496 and DST-CAS.

SKJ’s research was supported by DST-INSPIRE Fellowship.

Srikanth K. Iyer srikiyer@gmail.com

Extended author information available on the last page of the article.

(2)

1 Introduction and Main Results

The study of random graphs started with the pioneering work by Erd˝os and R´enyi [15,16] and Gilbert [21] on the Erd˝os-R´enyi model. The random graph in the Erd˝os- R´enyi model is constructed on a set ofn vertices, for somen ∈ Nwith an edge drawn between any two pairs of nodes independently with probabilityp ∈ [0,1]. Detailed work on the Erd˝os-R´enyi graph can be found in [7,30,32]. The Bernoulli lattice percolation model onZd is an extensively studied random graph model [24, 33,34] where the geometry of the underlying space plays an important role. The vertex set isZd with an edge between points at Euclidean distance one with prob- abilitypindependent of other edges. The above geometric model was extended to the continuum by considering a point process inRdwith edges between points that are within a Euclidean distancer >0. Such a model has found wide application in modeling ad-hoc wireless networks and sensor networks. This model is called the Boolean model [22] or the random geometric graph (RGG). The questions of inter- est in such applications are percolation, connectivity and coverage, details of which can be found in [20] and [25]. Rigorous theoretical analysis of the percolation prob- lem in such graphs can be found in [39] while the monograph [42] carries a detailed compilation of the important results on the topic in the sparse, thermodynamic and connectivity regimes. When each point of the underlying point process has an inde- pendent subset ofRdassociated with it, then the union of all such sets is what forms the germ-grain model which is of much interest in stochastic geometry [48].

The main goal of this paper is to derive conditions under which three network models on the plane exhibit a phase transition and show that under some additional conditions the percolation function is continuous. We shall now describe these mod- els and the problem of interest and discuss some applications. All these three models are constructed over a homogeneous Poisson point process denotedPλ inR2 with intensity parameterλ >0. A phase transition refers to the abrupt emergence of an infinite component in the graph, in which case we say that the graph percolates. A phase transition is said to occur if there exists a critical valueλc(0,)ofλsuch that forλ > λcthe random graph under consideration percolates and forλ < λcthe random graph does not percolate. It can be shown using ergodicity that forλ > λc, there is an infinite component with probability one. In many of the percolation mod- els inRd it can also be shown that there is unique infinite component by adapting the Burton-Keane argument [24,39]. The percolation function refers to the proba- bility that a typical vertex in the graph is part of the infinite component. Percolation is equivalent to the percolation function being positive. The continuity of the per- colation function is a problem of much interest in the random graph literature. See for instance, [14] for a new proof showing absence of percolation at criticality in the Bernoulli bond percolation model onZdwithd=2. An entirely different technique known as the lace expansion can be used in higher dimensions. This method was first used by Hara and Slade in [26] and [27] to prove continuity of the percolation function for dimensionsd 19. Fitzner and Hofstad in [18] obtained a significant improvement by showing that the lace expansion works ford 11. The problem still remains open for 3 d 10. We refer the reader to the book by Heydenre- ich and Hofstad [28] for a concise collection of recent results on high-dimensional

(3)

percolation. In a recent work Heydenreich et al. [29] describe the lace expansion method and mean-field behavior for the random connection model.

The random connection model (RCM) is a generalization of the RGG and a con- tinuum version of the long range percolation on lattices. This model was introduced in [43] and later studied in the context of wireless networks. In such networks com- munication between nodes depends on the distance between the nodes as well as the interference coming from transmissions from other nodes in the network [38, 39]. In the random connection model we consider, the vertex set will be a homoge- neous Poisson point process denotedPλ inRdwith intensity parameterλfor some λ > 0. An undirected edge denoted{x, y}exists between vertices located atx, y with probabilityg(|xy|)independent of everything else, whereg : [0,∞) → [0,1]is non-increasing. We denote this graph byGλ. Penrose in [43] showed that a phase transition occurs in Gλ if and only if the connection function satisfies 0<

Rdg(|x|) dx <∞.

The first model that we consider is the enhanced RCM. To define this model con- sider the RCM described above on the plane(d =2). If an edge{x, y}exists in the RCM then we refer toxandyas direct neighbors. We view each edge as a straight line segment and denote it byxy. For any two edges{x1, x2}and{x3, x4}in the RCM that intersect, we say that the verticesx1, x2are indirect neighbors ofx3, x4and vice versa. We will refer to the resulting graph as theenhanced random connection model (eRCM) and denote it byGeλ. It will be more useful to think of the eRCM as enhanc- ing the available paths in the network rather than introducing additional edges as can be seen from the following applications. Intersecting edges along apathin the RCM allow for switching from one path (in the original graph) to another. The eRCM can be considered as a model for a road or a pipeline network where connections are made locally and intersecting roads or pipelines allow the traffic or the fluid to switch paths. The above could also be used as a model for thin slab of porous media where connections between nodes resemble pipes and crossing of these pipes allow the fluid to flow from one pipe to another. An alternate model for road networks was studied in [2,3]. The construction of an optimal road network by using the trade-off between a measure of shortness of route and normalized network length for a one parameter family of proximity graphs is studied in [3]. In [2] the author introduces scale invari- ant spatial networks whose primitives are the routes between points on the plane. The problems of interest are the existence and uniqueness of infinite geodesics, continu- ity of routes as a function of end points and the number of routes between distant sets on the plane.

In this context it would be more appropriate to consider an inhomogeneous version of the eRCM model where each vertex is endowed with a weight that is indicative of the size, importance of a city or town. In the basic inhomogeneous model we consider, the vertex set is an independent marking ofPλ with weight distribution given byP (W > w)=wβ1[1,)(w)for someβ >0. Vertices located atx, y ∈R2 endowed with random weightsWx, Wyare connected by an edge independently with probability

g(x, y)=1−exp

ηWxWy

|xy|α

(1.1)

(4)

whereη, α are positive constants. The graph thus obtained is then enhanced in the same manner as described above to obtain the inhomogeneous eRCM (ieRCM). This is the second model that we shall study in this paper. We denote the random graph obtained in the inhomogeneous RCM and the enhanced inhomogeneous RCM by Hλ, Hλerespectively. Percolation properties for inhomogeneous random connection model with this type of inhomogeneity was studied for long range percolation model onZdby Deprez et al. in [12] and in the continuum for fixed intensityλby Deprez and W¨uthrich in [13]. Phase transition is expressed in terms of the parameterηinstead ofλ. A simple scaling argument shows that these two are equivalent. In both these models, a phase transition is shown to occur ford=1 only ifαβ >2 and 1< α <2 and ford 2 only ifα > d andαβ > 2d. For alldthe percolation function has been shown to be continuous under the condition thatαβ >2dandα(d,2d). For d2 the case when min{α, αβ}>2dis open.

The third random graph model on the plane we shall analyze is the Poisson stick model. This is an example of a model that satisfies the axiomatic conditions of so called scale invariant spatial networks mentioned above. This model which was intro- duced in [46] consists of sticks of independent random lengths whose mid points are located at points ofPλwith each stick having a random independent orientation.

The half-length of the sticks were assumed to have a density with bounded support.

Two points inPλ are neighbors in the resulting graph provided the corresponding sticks intersect. A phase transition was shown to occur in such a graph. The Poisson stick graph appears to be a natural model for a network structure formed by silicon nanowires and carbon and other nanotubes on the surface of substrates. Percolation, conductance and many other significant properties of these nanowire networks are studied in [6,31, 40, 44,49]. In this paper we consider the Poisson stick model with stick-length distribution having unbounded support and orientation distributed according to some arbitrary non-degenerate distribution. We study existence of phase transition and the continuity of the percolation function. The enhancement in our first two models has similarity with the Steiner tree. The Poisson stick model is similar to the Poisson line process on the plane. The Poisson line process and the Steiner tree have been used by Aldous and Kendall in [4] to establish asymptotics of excess route length in arbitrary graphs.

1.1 Notations

We gather much of the notations we need here for easy reference. We define the notations with reference to the RCM and eRCM. However, they carry over to the ieRCM and the Poisson stick models in the obvious way. LetC(x)(Ce(x)) be the connected component containingxPλinGλ(Geλ). Without loss of generality we assume that there is a vertex at the originO, that is, we consider the processPλ

under the Palm measurePo, the probability distribution conditioned on a point being at origin. The distribution ofPλ underPo is the same as that of Pλ∪ {O}under the original measureP. LetC := C(O),Ce := Ce(O)and define the percolation probabilities forGλ, Geλas

θ (λ):=Po(|C| = ∞)andθe(λ):=Po(|Ce| = ∞). (1.2)

(5)

The percolation thresholds denoted byλc, λecfor the graphsGλandGeλrespectively are defined as

λc:=inf{λ >0:θ (λ) >0}andλec :=inf{λ >0:θe(λ) >0}. (1.3) Similarly, letλ˜c˜ec, λP Sbe the percolation thresholds for the random graphsHλ, Hλe andP Sλrespectively.

As mentioned earlier, since we work with paths in the graph, we shall often view the enhanced models as providing additional paths in the original graphs rather than adding edges. In this view, edges in the graphsGλ, Hλ are straight line segments joining the vertices ofPλ.

Definition 1.1(Path) Given any of the graphsGeλ, HλeorP Sλandx, y ∈R2we say that there is apathfromxtoyif there exists a closed continuous curve fromxtoy contained entirely in∪ni=1eifor some edgese1, e2. . . , enin the case ofGλ, Hλand sticks in the case ofP Sλ. Paths thus need not start or end at vertices in the graph.

Definition 1.2(Crossing events) A path is said to cross a box[a, b] × [c, d]if the path is completely contained within the box with end points on opposite sides. We shall refer to these paths as crossings (see Fig.1). Fors >0 andρ >1 letLRs(ρ) be the event that there exists a crossing along the longer side (left-to-right) of the rectangle[0, ρs] × [0, s]andT Ds(ρ)be the event that there exists a crossing along the shorter side (top-to-down) of the rectangle[0, ρs]×[0, s].Cs(ρ):=P (LRs(ρ)).

1.2 Main Results

Our first result is on the existence of a phase transition in the three models described earlier. Penrose [43] showed that there is a non-trivial phase transition in the RCM, that is, 0 < λc < ∞ under the condition 0 <

0 rg(r)dr < ∞. We now prove a similar result for the eRCM albeit under a stronger restriction ong. In case of the ieRCM the condition required is stronger than the one for the iRCM as derived in [13]. Roy [46] showed the existence of a phase transition in the Poisson stick model

Fig. 1 The green curve is a left-right crossing of the box

(6)

under the assumption that the stick length distribution has bounded support, a result which we extend to sticks of unbounded lengths.

Theorem 1.1 A phase transition occurs in the

(i) eRCMGeλif the connection functiongsatisfies0<

0 r3g(r) dr <. (ii) ieRCMHλewith the connection function of the form(1.1)ifα >4andαβ >8.

(iii) graphP Sλwith half-length densityhif0<

0 2h() d <.

The condition for the existence of an infinite component for large intensities is obtained by comparing the enhanced model with the usual non-enhanced version.

For the other side we shall show that the probability that there exists a self avoiding path of lengthnconverges to zero asn→ ∞.

Our next result establishes a RSW lemma which is one of the most useful result in planar percolation models. It states that if the probability of crossing a square is uniformly bounded away from zero then so is the probability of crossing a rectan- gle along the longer side. We demonstrate its utility by establishing that percolation does not occur at criticality. The RSW lemma was first proved for the independent Bernoulli bond percolation model on the Z2 lattice independently by Russo [47]

and Seymour and Welsh [50]. A similar result about occupied and vacant crossings was proved for the Boolean model onR2by Roy [45]. In [46] an RSW result has been proved for the Poisson stick model with sticks of bounded lengths. The RSW results in this article are analogous to those in [51] for the percolation model on Poisson-Voronoi tessellations inR2. RSW results, continuity of critical parameter and sharpness of the phase transition for the Boolean model with unbounded radius distribution has been studied by Ahlberg et al. in [1]. For the continuum percolation model with random ellipses on the plane, percolation and connectivity behavior of the vacant and covered set has been studied by Teixeira et al. in [52].

We prove the RSW lemma under the condition that the connection function in the eRCM is of the formg(r)= O(rc)asr → ∞and the half-length densityhsat- isfiesh()= O(c)as→ ∞. This assumption is required in order to derive an estimate on the longest edge/stick length intersecting a large box. By Theorem1.1a phase transition occurs under the above assumptions in the eRCM providedc > 4 and inP Sλifc >3. The first two assertions in Theorem1.2are equivalent formula- tions of the RSW lemma while the third is derived as a (non-trivial) corollary of the first assertion. The RSW results are derived by adapting the technique developed by Tassion in [51] for Poisson-Voronoi percolation. The presence or absence of events in disjoint regions of space that are determined by the color of the cells in those regions are independent provided there are sufficiently many points of the point process in the space surrounding these cells. This argument does not carry over to the case of the random graph models we study here, since the edges are of unbounded lengths.

We first need a control on the length of the long edges. Even so, the absence of long edges in two disjoint regions far apart is not determined by the point process over any suitable disjoint regions. Thus a different argument is required to make the proof work. We then use a renormalization technique similar to the one used in [5] (see also [10]) to show that the parameter set over which percolation occurs is open. We shall

(7)

prove the results in detail for the eRCM. Much of the proof carries over to the other two models for which we will provide only the necessary details.

Theorem 1.2 Suppose the following conditions hold.

(I) In the eRCMGeλthe connection functiongsatisfiesg(r)=O(rc)asr → ∞ withc >4.

(II) In the ieRCM Hλe the connection function g is of the form (1.1) with min{α, αβ}>4.

(III) In the graphP Sλ with half-length density h satisfies h() = O(c) with c >3.

Then the following conclusions hold for all the three graphsGeλ,HλeandP Sλ. (i) If inf

s1Cs(1) >0then for anyρ 1, inf

s1Cs(ρ) >0.

(ii) If lim

s→∞Cs(1)=1then for anyρ1, lim

s→∞Cs(ρ)=1.

(iii) The percolation function is continuous.

Remark 1.1 The inhomogeneous RCM has also been studied in [8,23] and [35] with a slightly different but equivalent connection function. In this alternate set-up two vertices located atx, yare connected with probability

g(x, y)=1−exp

ηWxWy

|xy|2 α

, (1.4)

where the distribution of weights is as defined above (1.1). SettingVx = Wxα and α =2αthe model prescribed by (1.4) reduces to the model specified by (1.1) with parametersα andβ/α. It is then easy to derive the equivalent conditions on the parameters under the connection function given by (1.4). The condition required for Theorem1.1(ii)to hold will beα > 2,β > 4 and for Theorem1.2(II) to hold becomes α > 2 and β > 2. This is the regime in which the weights have finite variance and the random graph has fewer long-range edges.

Remark 1.2 To prove part(iii)of Theorem1.2it suffices to show that there is no percolation at criticality, that is,θeec)=0. Indeed, forλ < λec,θe(λ) ≡0. Conti- nuity of the percolation function in the supercritical regime (λ > λec) follows along the same lines as in the proof of Theorem 8.8 in [24]. Right continuity ofθe(λ)is a simple consequence of monotonicity (see Lemma 8.9 in [24]). Left continuity can be proved by adapting Lemma 8.10 in [24]. The proof relies on the uniqueness of infinite component. Uniqueness can be proved using the same arguments as in Theorem 6.3 in [39].

1.3 Open Problems

A natural first question is to examine whetherλec< λcandλ˜ec˜c. In a recent work [17], sharpness of phase transition has been proved for the RCM under the condition that edge lengths are bounded. Such results are proved on the plane for the Poisson Boolean model with unbounded grain size under certain moment conditions and for

(8)

the Poisson-Voronoi percolation using the RSW Lemma [1]. Under what conditions would such a result hold for the eRCM?

2 The Enhanced Random Connection Model

In this section we shall prove the non-trivial phase transition (Theorem 1.1 (i)), the RSW result and non-percolation at criticality (Theorem 1.2) for the eRCM.

Much of the proof carries over to the other two models, i.e., the inhomogeneous eRCM and the Poisson stick model, for which we will provide only the necessary details.

In what followsc0, c1, c2, . . .andC1, C2, . . .will denote constants whose values will change from place to place.| · |will be used to refer to the Euclidean norm, the cardinality of a set as well as the Lebesgue measure.

2.1 Proof of Theorem1.1(i )(Non-trivial phase transition)

It is clear from the definition thatGeλ percolates ifGλ does. So we haveλec λc. From Theorem 1 in Penrose [43] we know thatλc(0,)iff

0 rg(r) dr(0,). Sinceg(r)∈ [0,1],

0 r3g(r) dr(0,)implies

0 rg(r) dr(0,).

It follows from the above observations thatλec<∞.

We now show thatλec > 0. We shall bound the probability that there is aself- avoiding pathformed usingndistinct points ofPλstarting from the origin. For any x= (x1, x2, . . . , xn)ofndistinct points of the Poisson point process, we examine whether there is a path starting atx0 =O and uses edges (or parts of it) with end points fromxin the coordinate order. We shall denote any such path byx0x1x2. . .xn even though some of these points may not be part of the path.

Since we need only an upper bound on the percolation probability, we allow our self-avoiding pathsto have loops. However, each edge or a part of it is used exactly once while traversing the path. For each ordered sequencexas above, there can be several ways in which a path can occur. See Fig.2for self-avoiding paths formed by(x1, x2, x3, x4). Each such possibility gives rise to a uniqueblock structurethat we describe below. In order to carry out the computation we segregate all paths in disjoint block structures.

We now illustrate this via an example. Taken=4,x0=Oandx1, x2, x3, x4be four distinct points inPλ. Suppose thatOx1x2x3x4is a self avoiding path. This can occur in only one way in the RCM (Fig.2(a)) but in the eRCM this can occur in three different ways (see Fig.2). Note that in Fig.2(c) we allow the segmentx3x4to intersect the segmentx0x1.

Let E(Gλ) denote the edge set of the graph Gλ. Fix n ∈ N and let x = (x1, x2, . . . , xn)Pλ,n=be an ordered collection ofndistinct points inPλ. Define the sub-collection of indices

I (x) := {i∈ [n1] : {xi−1, xi},{xi, xi+1} ∈E(Gλ)},

J (x) := {i, i+1:i∈ [n2],{xi−1, xi},{xi+1, xi+2} ∈E(Gλ), xi−1xixi+1xi+2=ziPλ}.

(9)

Fig. 2 All possible configurations of pathsx0x1x2x3x4

The last condition in the definition ofJ (x)requires that the edges intersect at a point interior to both the edges. SupposeI (x) = {i1, i2, . . . , ik}for some 0 k n−1, labeled in the increasing order. Seti0 := 0, ik+1 := nand define the blocks

Bj(x):= {ij1< i < ij :iJ (x)} ∪ {ij1, ij}, 1j k+1.

If x0x1x2. . .xn is a self avoiding path then ∪kj+=10Bj(x) = {0,1,2, . . . , n}. If iI (x) then xi lies on the path whereas if iJ (x) then the path uses a part of an edge one of whose end points is xi. Let B(x) = (B1(x), . . . , Bk+1(x)). With reference to Fig.2, the diagram in (a) consists of four blocksBi(x) = {i−1, i}, 1 i 4. The diagram in (b) has two blocksB1(x)= {0,1,2,3},B2(x)= {3,4}while the one in (c) also has two blocksB1(x)= {0,1}, B2(x)= {1,2,3,4}.

Note that all blocks have even cardinality. For 0kn−1,Bkbe the collection of all block structuresB = (B1, . . . , Bk+1) such that|Bj| is even and for some 0< i1< i2<· · ·< ik < n,Bj := {i:ij1iij}withi0:=0, ik+1:=n. Let Bje= {ij1+2r−1:r=1,2, . . . , (ijij1+1)/2}be the set of indices with an even ordering inBj.

By definition of percolation probability the event that the origin lies in an infinite connected component implies that for eachn ∈ Nthere is a self-avoiding path of lengthnstarting from the origin inGeλ.

θe(λ) Po(there is a self-avoiding path onnvertices inGeλstarting atx0)

Eo

⎢⎣

x∈Pλ,n=

1{x0x1x2→ · · · →xnoccurs}

⎥⎦

=

n1

k=0

B∈Bk

Eo

⎢⎣

x∈Pλ,n=

1{B(x)=B}

⎥⎦. (2.1)

Recall that eachBBk is of the form(B1, . . . , Bk+1). For a block of the form Bj := {i:ij1iij}of size larger than two, let

Aj= {y=(y1, . . . , yn):yij1+2r−2yij1+2r−1intersectsyij1+2ryij1+2r+1for allr=1, . . . , (ij−ij−1−1)/2}.

(10)

The intersection above is understood to be at an interior point of the line segments.

For a block of size two we set 1Aj ≡1. Conditioning onPλ and then applying the Campbell-Mecke formula we obtain

Eo

x∈Pλ,=n

1{B(x)=B}

= Eo

x∈Pλ,=n

Eo

k+1

j=1

1{Bj(x)=Bj} Pλ

= Eo

x∈Pλ,=n k+1 j=1

l∈Bje

g(xl1, xl)1Aj(x)

= λn · · ·

ntimes k+1

j=1

lBej

g(xl1, xl)1Aj(x) n l=1

dxl. (2.2)

We now evaluate the contribution to (2.2) from blocks of various sizes. By contri- bution from a block we refer to the outcome of evaluating the integrals in (2.2) with respect to all variables with index in that block except for the one corresponding to the first index. We shall integrate the variables in the descending order starting with those in the blockBk+1. Blocks of size four and higher yield a nice formula for the upper bound. To see this one needs to compute the bound for a block of size six. We start with the simplest block of size two. The contribution from a block of size two will be of the form

R2g(|x1x2|) dx2=

R2g(|x|) dx=2π

0

r g(r) dr. (2.3) Next we compute the contribution from a block of size four. Fora= (a1, a2), b= (b1, b2), letH+(a, b) :=

(c1, c2)∈R2: cc21aa21 aa21bb21

. ForcH+(a, b), let D(a, b, c):=

d∈R2:cdintersectsab

. The contribution to (2.2) from a block of size four equals

R2g(|y1y2|)

H+(y1,y2)

D(y1,y2,y3)

g(|y4y3|) dy4dy3

dy2. (2.4) The regionD(y1, y2, y3)is the region enclosed by the rays−−→

y1A,−−→

y2Aand the line segmenty1y2(see Fig.3). Suppose|y1y2| =. By a translation and rotation (so thaty1is translated to the origin andy2to the point(,0)), we can write

H+(y1,y2)

D(y1,y2,y3)

g(|y4y3|) dy4dy3=

R×{a2>0}

D(O,(,0),a)

g(|ab|) db da, (2.5) wherea=(a1, a2)andb=(b1, b2). Changing the variablesa, btou, v, r, θaccord- ing toa=(u+vcosθ, vsinθ ), b=(u(rv)cosθ,(rv)sinθ )and noting that the determinant of the Jacobian satisfies|J1| = rsinθ we can rewrite the right-hand side of (2.5) as

0

π 0

0

r 0

g(r) r sinθ dv dr dθ du=2

0

r2g(r) dr. (2.6)

(11)

Fig. 3 D(y1, y2, y3)is the unbounded region enclosed by the rays−−→y1A,−−→

y2Aand the line segmenty1y2

By changing to polar coordinates and using (2.6) the expression in (2.4) equals

0

0

g()

2

0

r2g(r) dr

dθ d=4π

0

r2g(r) dr 2

. (2.7) We shall writeHi,j forH+(yi, yj)andDi,j,k for D(yi, yj, yk)for notational sim- plicity. The contribution from a block of size six can be found by applying the above procedure twice. Using (2.5), (2.6) we get

R2g(|y1y2|)

H1,2

D1,2,3

g(|y4y3|)

H3,4

D3,4,5

g(|y6y5|) dy6dy5

dy4dy3

dy2

R2g(|y1y2|)

H1,2

D1,2,3

g(|y4y3|)2|y4y3|dy4dy3

dy2

0

r2g(r) dr

= 2

R2g(|y1y2|)2|y2y1|dy2

0

r3g(r) dr

0

r2g(r) dr

=

0

r2g(r) dr

0

r3g(r) dr

0

r2g(r) dr

. (2.8)

By iterating the above procedure the contribution from the block of size 2m+2 on the vertices{y1, y2, . . . , y2m+2}where the edgeyi, yi+1intersectsyi+2, yi+3for alli=1,2, . . . ,2m−1 can be shown to be

2m+1π

0

r2g(r) dr

0

r3g(r) dr

m1

0

r2g(r) dr

. (2.9) For a path with blocksB1, B2, . . . , Bk+1let

kp:= |{j : |Bj| =2p}|andk¯=

|1jnBj|6

|Bj| 2 −2

. (2.10)

(12)

Since each vertex can be in at most two adjacent blocks we have that k¯

k+1

j=1

|Bj|

2 n. (2.11)

Substituting the contributions from each blockB1, B2, . . . , Bk+1, that is, the expres- sion in (2.3), (2.7)–(2.9) in the expression on the right in (2.2) yields

Eo

x∈Pnλ,=

1{B(x)=B}

=λn n2 m=0

(2m+1π )km

0 rg(r)dr

k1 0

r2g(r)dr

2(k−k1) 0

r3g(r)dr k¯

. (2.12)

Using (2.11) in (2.12) and then using (2.2), (2.12) in (2.1) we obtain θe(λ)λn

n1

k=0

B∈Bk

n2

m=0

(2m+1π )km

C14n, (2.13)

whereC1=max

0 rjg(r) dr, j =1,2,3

. Sincen2

m=1

(m+1)kmn2

m=1

2m km 2nand|Bk| = nk1!

, there exists a constantCsuch that θe(λ)(Cλ)n→0

as n → ∞ for all λ(0, λ0), for some λ0 > 0 provided max

0 rjg(r) dr, j =1,2,3}<∞.

2.2 Proof of Theorem1.2(i ) (RSW)

Before proceeding with the proof we recall some tools from Stochastic geometry, namely the Fortuin-Kasteleyn-Ginibre (FKG) inequality and the square-root trick that will be used in several places.

Increasing and Decreasing Events An eventAis said to be an increasing event if it continues to occur under addition of edges. An eventAis said to be a decreasing event ifAcis increasing.

Theorem 2.1 (FKG inequality) IfA1, A2 are both increasing or both decreasing events, then

P (A1A2)P (A1)P (A2). (2.14)

Corollary 2.2(Square-root trick) Let A1, A2, . . . , Ak be increasing events having equal probability. Then

P (A1)1− 1−P

ki=1Ai

1k

. (2.15)

(13)

We shall provide a more general statement of the FKG inequality and its proof in Section 5 (Appendix). Some standard reference to the FKG inequality is [19] for discrete case and Theorem 2.2 in [39] for the continuum case. To prove the FKG inequality for increasing functionals on random geometric graphs we will need to combine the discrete FKG inequality with that for increasing functionals on Poisson point processes (Theorem 20.4, Last and Penrose [36]). For the square-root trick see Lemma 2.3 in [9].

Consider the graphGeλwith connection functiong(r)=O(rc)asr→ ∞where c > 4 is arbitrary. Later we shall borrow some key results from Tassion [51] and hence will adopt many of the notations from that paper. A key ingredient in the proof is the following result on the length of the longest edge inGλ which allows us to localize the analysis. LetBs := [−s, s]2and fort > sletAs,t:=Bt\Bs.

Proposition 2.3 For anys > 0 let Ms be the length of the longest edge in Gλ

intersecting the boxBs = [−s, s]2. Suppose that the connection functiongsatisfies g(r) = O(rc)asr → ∞. Then for anyc > 4,t > 0andτ > c22 we have P (Mt s> sτ)→0ass→ ∞.

Proof of Proposition2.3 Fixc >4,t >0. LetB(O, s):= {x∈R2: |x|s}be the ball of radiusscentered at the origin. Recall that for any two pointsx, y ∈ R2,xy denotes the line segment joiningxandy. Define the eventsDs(l)= {Ms > l},

Os(τ )=

XPλ: there is an edge of length longer thansτincident onXinGλ

and

¯ Ot,s(τ )=

(X, Y )Pλ2:there is an edge inGλjoiningX, Y,|XY|sτ, XYintersectsB(O, 2s)

.

Then,

P Dts(sτ)!

E

X,Y∈Pλ

1

XYintersectsBts 1

|XY|sτ

E

X∈Pλ∩B(O, 2ts)

1{XOs(τ )}

+E

X,Y∈Pλ∩B(O, 2ts)c

1

(X, Y )∈ ¯Ot,s

⎦. (2.16)

The Campbell-Mecke formula applied to the first term on the right-hand side of the last inequality in (2.16) yields

E

X∈PλB(O, 2t s)

1{XOs(τ )}

= Cλ(ts)2Po(OOs(τ ))

= Cλ(ts)2 1−Po none of the edges incident on O is of lengthsτ!!

= Cλ(ts)2

1−exp

λ

B(O,sτ)c

g(|x|)dx

C(λts)2

B(O,sτ)c

g(|x|)dx=C1s2

sτ

rg(r) drC2s2τ (c2), (2.17)

(14)

Fig. 4 Dxis the unbounded region enclosed by the rays−→T A, and−−→

TAand the arc

where we have used the fact that the points ofPλ from which there is incident on O an edge that is of length longer thansτ is a Poisson point process of intensity λg(|x|)1{xB(O, sτ)c}, the inequality 1−ey y and the assumption ong.

Similarly, we can bound the second term on the right-hand side in the last inequality in (2.16) as follows (see Fig.4),

E

X,Y∈PλB(O, 2t s)c

1

(X, Y )∈ ¯Ot,s

=λ2

B(O, 2t s)c

Dx∩B(x,sτ)c

g(|xy|) dy dx, (2.18)

whereDx is the unbounded region enclosed by the rays−→T A, and−−→

TA and the arc as shown in Fig.4. Changing to polar coordinates and using the obvious bounds for the range of they-variable we can bound the expression on the right in (2.18) by

C3

2t s

0

R

sτ

R22t2s2

rg(r) dr

dφ dR C4

2t s

sτ∨"

R2−2t2s22c

R dR

= C4

2t2s2+s t s

sτ (2c)R dR+C4

2t2s2+s

R2−2t2s22−c2 R dR

= C5sτ (c4)+C6

sτ

u3cdu=C7sτ (c4), (2.19)

(15)

where we have used the assumption thatg(r)Crc. Substituting from (2.17) and (2.19) in (2.16) we obtain

P Dt s(sτ)!

C2s2τ (c2)+C7sτ (c4). Hence,P (Dt s(sτ))→0 ass→ ∞, sinceτ > c22 andc >4.

The following corollary gives us the precise form in which we will be using Proposition2.3. Recall thatA2t s,4t sis the annulus[−4ts,4ts]2\ [−2ts,2ts]2. Corollary 2.4 For the graphGλwith the connection functiongsatisfyingg(r) = O(rc)asr→ ∞, letLt s(τ )be the event that there exists an edge of length longer thansτintersecting the annulusA2t s,4t s. Then for anyc >4,t >0andτ > c22we haveP (Lt s(τ ))→0ass→ ∞.

By assumption in part (i) of Theorem1.2, we have for somec0>0,

Cs(1)c0for alls1. (2.20)

Proposition2.5below is a restatement of the first assertion in Theorem1.2for the caseρ =2. We shall first use this proposition to extend the result for generalρand then follow it up with the proof of the proposition.

Proposition 2.5 Suppose(2.20)holds for the graphGeλwith the connection function gsatisfyingg(r)=O(rc)asr→ ∞for somec >4. Then inf

s1Cs(2) >0.

Proof of Theorem1.2(i) Lets1. Assuming that Proposition2.5holds, it suffices to prove the result forρ > 2. We need to build a left to right crossing in[0, ρs] × [0, s]. Observe that

[0, ρs] × [0, s] ⊂

nρ

#

j=0

((j s,0)+ [0,2s] × [0, s]) , (2.21) wherenρ ρ. Let Fs(ρ)be the event that there exists left to right crossing in (j s,0)+ [0,2s] × [0, s] for allj = 0,1,2, . . . , nρ and top to down crossing in (j s,0)+[0, s]×[0, s]for allj =1,2, . . . , nρ. From (2.21) we haveFs(ρ)LRs(ρ) (see Fig.5). Using this inclusion and applying the FKG inequality (Theorem2.1) we obtain

Cs(ρ)P[LRs(2)]nρ+1P[T Ds(1)]nρ.

Fig. 5 A realization of the eventFs(ρ)

References

Related documents

We will refer to our graphs, in the percolation context as the AB Poisson Boolean model, and as the AB random geometric graph while investigating the connectivity problem...

The ordering of extended defects in radiation environment can be understood as a non-equilibrium phase transition. An initially random or homogeneous state

Amorphous semiconductors ; structural models ; continuous random net- work ; microcrystallite

In Figure 3, the system morphology is shown for a system of width L = 64 at time steps t = 2 11 The solution is represented by light gray scale and the random solid is represented

p s (p,L) describing the geometrical quantities here in percolation is then expected to be a &#34;generalized homogeneous function at the percolation threshold p c. In order to

Keywords Minimal spanning tree · Gromov–Hausdorff distance · Critical percolation · Real tree · Random regular graphs · Graphs with prescribed degree sequence · Configuration

We shall study, for the inhomogeneous random graph considered in [6], the asymp- totic behavior of the number of isolated nodes and vertices of arbitrary degree in the

In 、 double random phase encoding method' [Refflegier and Javidi 1995a,b], a VanderLugt 4-f optical system encrypts a primary image to a noise like image by using two random