# Zero-One Law for Connectivity in Superposition of Random Key Graphs on Random Geometric Graphs

Authors: Y. Tang; Q. L. Li
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

We study connectivity property in the superposition of random key graph on random geometric
graph. For this class of random graphs, we establish a new version of a conjectured zero-one law
for graph connectivity as the number of nodes becomes unboundedly large. The results reported here
strengthen recent work by the Krishnan et al.


---

## Body

## 1. Introduction

Random key graph (RKG), also known as uniform random intersection graph, is a random graph defined below. Consider a set withn nodes and another key pool with Pn keys; we assume each node randomly chooses Kn distinct keys for its key ring; two nodes can establish a secure link between them if they share at least one common key in their key rings.The random key graph is naturally associated with the random key predistribution scheme of Eschenauer and Gligor [1] for wireless sensor networks (WSNs). A WSN is a collection of distributed sensor devices that are able to communicated wirelessly and supports wide range of applications such as health and environment monitoring, imaging, tracking, and biomedical research; see [2]. These applications require all nodes in the network to be within communication range and to be connected with high probability.Some partial results concerning the connectivity of RKGs were given in [3–5]. In [6], Rybarczyk gave asymptotic tight bounds for the thresholds of the connectivity, phase transition, and diameter of the largest connected component in RKGs for all ranges of Kn.With the advent of ad hoc sensor networks, an interesting class of random graphs, namely, random geometric graphs (RGGs), has gained new importance and its properties have been the subject of much study. Here the nodes are randomly distributed in a finite Euclidean space and there is an edge between two nodes if the Euclidean distance between them is below a specified threshold. Much work has been done on graph theoretic properties of such graph, comprehensively summarized in the monograph of [7].Recently, there is interest in random graphs in which an edge is determined by more than one random property, that is, superposition of different random graphs. The superposition of ER random graphs over RGGs has been of interest for quite some time now. Recent work on such random graphs is in [8, 9] where connectivity properties and the distribution of isolated nodes are analyzed. And the superposition of ER random graphs on RKGs is considered in [10]. Such a graph is constructed as follows: a RKG is first formed based on the key distribution and each edge in this graph is deleted with a specified probability.The superposition of RKGs on RGGs is first studied in [11]. The n nodes are distributed in a finite Euclidean space and each node is assigned a key ring of Kn distinct keys drawn randomly from a pool of Pn keys. Two nodes have an edge if and only if they share at least one common key in their key rings and their Euclidean distance is at most rn. Pietro et al. [11] have shown that under the scaling πrn2Kn2/Pn=c(log⁡n/n), the one-law that this class of random graphs is connected follows if rn>0 and c>20π. Another notable work is due by Krzywdziński and Rybarczyk [12], where the authors have improved these results and established the one-law for c>8 without any constraint on rn. Recently, Krishnan et al. [13] have shown that for large n, this class of random graphs will be connected if Kn≥2,rn and Pn are selected such that(1)Kn,Pn⟶∞,Kn2Pn⟶0,Pn≥2Kn,Pn≥σnrn2,πrn2Kn2Pn>2π1-γlog⁡nn,for any σ>0 and 0<γ<1. They also observed that for large n and 0<c1<∞, the probability that this class of random graphs is disconnected is at least e-c1/4 if the scaling satisfies (2)πrn2Kn2Pn=log⁡n+c1n.The connectivity in the superposition of RKGs on RGGs is still studied in this paper. Assuming thatPn≥n, we show that given nπrn2Kn2/Pn=log⁡n+cn, this class of random graphs is disconnected if cn→-∞, and for cn→∞, this class of random graphs is connected.In this paper, we use standard, asymptotic notations:an=Θ(bn), an=ω(bn), an=o(bn), and an~bn for ∃c,C>0cbn≤an≤Cbn, an/bn→∞, an/bn→0, and an/bn→1, respectively, all limits are taken as n→∞. The phrase “with high probability" (abbreviated whp) means with probability tending to one as n tends to infinity.The rest of the paper is organized as follows. Our main result is presented in Section2. Namely, the theorem concerning zero-one law for graph connectivity is presented. Section 3 contains technical proof of Theorem 1. Finally, Section 4 discusses prospects of establishing tighter connectivity thresholds in the superposition of RKGs on RGGs.


## 2. Main Result

Then nodes are uniformly and independently distributed in R=[0,1]2. Let xi∈R be the location of point i. A key pool with Pn cryptographic keys is designated for the network of n nodes. Node i randomly chooses a subset Si of keys from the key pool with Si=Kn. Our interest is in the random graph G(Pn,Kn,rn) with n nodes and edges formed as follows. An edge (i,j), 1≤i<j≤n, is present in G(Pn,Kn,rn) if both of the following two conditions are satisfied: (3)E1:xi-xj≤rn,E2:Si∩Sj≠∅,where · represents the Euclidean norm. Condition E1 produces a random geometric graph with the transmission range rn. Imposing condition E2 on E1 retains the edges of the random geometric graph for which the two nodes share at least one common key. Thus G(Pn,Kn,rn) is a superposition of RKG on RGG.In the following, to avoid technicalities which obscure the main ideas, we will neglect edge effects resulting due to the fact thatn nodes are distributed uniformly and independently over a folded unit square R=[0,1]2 with continuous boundary conditions and a node is close to the boundary of R. Throughout the paper, we set nπrn2=dn, where dn=ω(log⁡n) and dn=o(n(1-δ)/4) for any small 0<δ<1. The following theorem gives zero-one law for the connectivity of a superposition of RKG on RGG.Theorem 1.
LetKn≥2, Kn,Pn→∞, Kn2/Pn→0, Pn≥n. Then(i)
ifπrn2Kn2/Pn=(log⁡n+cn)/n and cn→-∞, then with high probability G(Pn,Kn,rn) is disconnected;(ii)
ifπrn2Kn2/Pn=(2log⁡n+cn)/n and cn→∞, then with high probability G(Pn,Kn,rn) is connected.The first part of the Theorem1 is proved by using the second moment method, that is, considering the probability of finding at least one isolated node in the network for a random graph G(Pn,Kn,rn). The second part takes a slightly different approach, we assume that R=[0,1]2 is entirely coved by circle cells of radius rn/2. Connectivity of G(Pn,Kn,rn) is ensured as follows: (1) every circle cell is dense; namely, every circle cell has Θ(nrn2) nodes inside it; (2) the overlapping structure of any two adjacent circle cells has at least one common node; and (3) the nodes in any circle cell form a connected subgraph.


## 3. Proof of Theorem1

Before proceeding, we first introduce some definitions and auxiliary lemmas. Fori=1,2,…,n, let Xi=1 if node i is isolated in G(Pn,Kn,rn) and X=∑i=1nXi. Then, X is exactly the number of isolated nodes in G(Pn,Kn,rn). Let S denote the cardinality of a set S and let  E(X), Var(X) denote the expectation and variance of random variable X, respectively. As a special case of Markov’s inequality the first moment method states that(4)PrX≥1≤EX,and the second moment method (special case of Tschebyscheff’s inequality) states that (5)PrX=0≤VarXEX2.If X is a binomial distributed random variable, λ=EX and for any t≥0, then we will use the following variants of Chernoff’s inequality (see [14]): (6)PrX≥λ+t≤exp⁡-t22λ+t/3,PrX≤λ-t≤exp⁡-t22λ.Of course, it is easy to check that(7)βn=1-Pn-KnKnPnKn~Kn2Pn,under the assumption that limn→∞⁡(Kn2/Pn)=0, where βn is the probability that two nodes share at least one common key. Throughout, we make use of the standard bounds (8)nu≤enuu,valid for all u,n=1,2,… with u≤n. Finally, we note the equation (9)1-pm~e-mpholds if mp2→0.Proof of Statement (i) of Theorem1.
Letαn=πrn2, βn=1-Pn-KnKn/PnKn, where βn is the probability that two nodes share at least one common key in their key rings. By linearity of expectation, EX=E(∑i=1nXi)=nEXi; hence (10)EX=nEXi=n1-αnβnn-1~nexp⁡-n-1αnβn=nexp⁡-n-1log⁡n+cnn=nexp⁡-log⁡n-cnexp⁡log⁡n+cnn~nexp⁡-log⁡nexp⁡-cn=exp⁡-cn⟶∞,as cn→-∞. The second moment method now implies the result we require, provided that we can show that VarX=o((EX)2). Now (11)VarX=EX2-EX2≥0,and so it suffices to show that E(X2)=(1+o(1))(EX)2. Note that (12)EX2=EX+nn-1EX1X2,where 1, 2 are fixed nodes. Since EX→∞, it therefore suffices to prove that(13)nn-1EX1X2EX2⟶1asn⟶∞.Note that X1X2 take the value 1 exactly when node 1 and node 2 are both isolated. Consider two discs of radius rn centered at x1 and x2; let d=x1-x2; the cross term n(n-1)E(X1X2) is shown to be given by(14)nn-1EX1X2=nn-1PrX1X2=1=nn-1PrX1X2=1∣d>2rnPrd>2rn+nn-1PrX1X2=1∣rn<d≤2rnPrrn<d≤2rn+nn-1PrX1X2=1∣0≤d≤rnPr0≤d≤rn.
Conditional on the range ofd, we consider the following three cases. In each case, the conditional joint probability of two nodes being isolated can be obtained from [13].
(
1
)
d
>
2
r
n: this case happens with the probability 1-4αn, and(15)PrX1X2=1∣d>2rn=1-2αnβnn-2.
(
2
)  rn<d≤2rn: this case happens with the probability 3αn, and (16)PrX1X2=1∣rn<d≤2rn≤Kn+1exp-n-22-γnβn-2αnβn,where γn=1-Pn-2KnKn/PnKn.
(3)0≤d≤rn: this case happens with the probability αn, and(17)PrX1X2=1∣0≤d≤rn≤exp-n-22-γnβn-2αnβn.
The upper bound onn(n-1)E(X1X2) that nodes 1 and 2 are isolated if rn<d≤2rn and 0≤d≤rn is obtained together using (16) and (17). So 3n(n-1)αnPr(X1X2=1∣rn≤d≤2rn)+n(n-1)αnPr(X1X2=1∣0≤d≤rn) is upper-bounded as follows:(18)3nn-1αnPrX1X2=1∣rn≤d≤2rn+nn-1αnPrX1X2=1∣0≤d≤rn≤nn-1Kn+1αnn2exp⁡log⁡nγnβn-2-cn2-γn/βn-2log⁡n+4-2γn/βn-2αnβnlog⁡n≤1n.See [13] for details.
From (14), (15), and (18), the term n(n-1)E(X1X2) is bounded as (19)nn-11-4αn1-2αnβnn-2≤nn-1EX1X2.The term n(n-1)E(X1X2) also satisfies (20)nn-1EX1X2≤nn-11-4αn1-2αnβnn-2+1n.Since EX=n(1-αnβn)n-1, if n→∞, we find that (21)nn-11-4αn1-2αnβnn-2EX2⟶1nn-11-4αn1-2αnβnn-2+1/nEX2⟶1.The above two convergence formulas are true since αn=dn/n, where dn=ω(log⁡n), dn=o(n(1-δ)/4), and αnβn=(log⁡n+cn)/n. We see that (13) holds as required, which implies that (22)PrX=0≤VarXEX2⟶0,as n→∞, which concludes the proof.Ifnαnβn=log⁡n+cn for any cn→∞, we have EX→0. Then using the first moment method, we see that the probability Pr(X≥1)≤EX→0 holds; this implies a.a.s. there are no isolated nodes in random graph G(Pn,Kn,rn). The upcoming corollary is immediate from the proof of statement (i) of Theorem 1.Corollary 2.
In the modelG(Pn,Kn,rn), let Kn≥2, Kn,Pn→∞, Kn2/Pn→0, Pn≥n, and (23)πrn2Kn2Pn=log⁡n+cnn.(i)
Ifcn→-∞ as n→∞, then whp G(Pn,Kn,rn) contains at least an isolated node.(ii)
Ifcn→∞ as n→∞, then whp G(Pn,Kn,rn) does not contain an isolated node.Proof of Statement (ii) of Theorem1.
We consider the unit-area square onR=[0,1]2; R is divided into square cells of size sn×sn, where 1/sn is an integer. Let the center of square cell be the center of the circle cell and let the diagonal line of the square cell be the diameter of the circle cell. In this way, R is entirely covered by the circle cells. Also we let rn=2sn; this means that two nodes in the same circle cell are within communicating range of each other.
Recall thatnαn=dn, where αn=πrn2,dn=ω(log⁡n) and dn=o(n(1/4)(1-δ)). In order to complete the proof, we show the following two lemmas.
Lemma 3.(i) Every circle cell is dense; specifically, whp every circle cell hasΘ(nrn2)nodes in it.
(ii) The overlapping structure of any two adjacent circle cells whp has
Θ
(
n
s
n
2
)
nodes.
Proof. (i) First, we analyze the denseness of every circle cell; let Ni denote the number of nodes in circle cell i, 1≤i≤1/sn2. Obviously, Ni is a binomial random variable with parameters (n,(π/2)sn2). Let Wi denote the event that the circle cell i is not dense, in other words, for any 0<δ1<1/2, δ1≤δ, Ni-π/2nsn2≥δ1(π/2)nsn2. Using Chernoff’s inequalities on Ni, we have(24)PrNi≤1-δ1π2nsn2≤exp⁡-π4nsn2δ12,PrNi≥1+δ1π2nsn2≤exp⁡-π8nsn2δ12.Consequently(25)PrWi=1≤2exp⁡-πnsn2δ128=2exp⁡-dnδ1216,Pr⋃i=11/sn2Wi=1≤1sn2PrWi=1≤exp-dnδ1232⟶0,which implies that every circle cell is dense.
(ii) Now we consider the nodes in the overlapping structure of any two adjacent circle cells. LetN′ denote the number of nodes in the overlapping structure of any two adjacent circle cells. Clearly N′ is a binomial random variable with parameters (n,((π-2)/4)sn2). For any 0<δ2<1, we also use Chernoff’s inequalities on N′:(26)PrN′≤1-δ2π-24nsn2≤exp⁡-π-28nsn2δ22,PrN′≥1+δ2π-24nsn2≤exp⁡-π-216nsn2δ22.From the two above inequalities we may easily get (27)PrN′-π-24nsn2≥δ2π-24nsn2≤2exp⁡-π-216nsn2δ22=2exp⁡-π-232πdnδ22⟶0.The above expression implies that N′ is very likely close to its expectation ((π-2)/4)nsn2. So we get our result that whp the overlapping structure of any two adjacent circle cells has at least one common node.
Lemma 4.The nodes in any circle cell form a connected subgraph; that is, for any fixed1≤i≤1/sn2circle cellicontains no components of sizel,1≤l≤Ni/2, whereNiis the number of nodes in circle celli.
Proof. This part takes a slightly different approach; we consider the subgraph formed by the nodes in circle cell i; denote this subgraph by Gi. We will show that for any circle cell i there are no components of size 1,2,…,Ni/2 in Gi.
Consider any fixed circle celli, 1≤i≤1/sn2, for any nonempty subset L of nodes in circle cell i; that is, L⊆{1,2,…,Ni}, with 1≤L≤Ni/2; define the following events.
C
i
(
L
): a subgraph induced by nodes in L is connected.
B
i
(
L
): L is isolated in circle cell i; that is, there are no edges between the nodes in L and the nodes in the complement LC={1,2,…,Ni}-L. Consider(28)AiL=BiL∩CiL,Di=⋃l=1Ni/2⋃L:L=lAiL.Further, let Ci,l and Ai,l denote Ci(L) and Ai(L) with L=l, respectively. Then the sufficient condition for every circle cell a.a.s. containing no components of size l (1≤l≤Ni/2) is to have Pr(Di)/sn2→0. Conditioned on Wi, we have (29)PrDi=∑j∈0,1PrDi∣Wi=jPrWi=j≤PrDi∣Wi=0+PrWi=1.The above inequality uses bounds on the factorial, Pr(Wi=0)≤1 and Pr(Di∣Wi=1)≤1; from Lemma 3, we get Pr(Wi=1)/sn2→0; thus we focus on showing that Pr(Di∣Wi=0)/sn2→0. Note that(30)PrDi∣Wi=0=Pr⋃l=1Ni/2⋃L:L=lAi,l≤∑l=1Ni/2NilPrAi,l.
We letUi,l denote the number of distinct keys in the component of size l in Gi. Adapting [5], for any x=Kn,…,min⁡{lKn,Pn}, we have(31)PrAi,l≤PrUi,l≤xexp⁡-Ni-lKn2Pn+PrCi,lexp-Ni-lKnx+1Pn.From [5], we know that (32)PrUi,l≤x≤PnxxPnlKnPrCi,l≤ll-2βnl-1.
First we use the standard Poissonization technique [7, 15] to show the probability of having isolated nodes in any of the circle cells. Denote the circle i by Ai; let Ii=1 be the event that node i is isolated in Ai, and let Drn(v^i) be the intersection of Ai and the disk centered at position v^i∈Ai with radius rn, where node i is at position v^i. Similar to the discussion in [16], the number of nodes within Drn(v^i) follows a Poisson distribution with mean nDrn(v^i); and to have an edge with i, a node not only has to be within a Drn(v^i) but also has to share at least a key with node i, so the number of nodes neighboring to i follows a Poisson distribution with mean nβnDrn(v^i). Integrating v^i over Ai, the probability that node i is isolated in Ai is given by(33)PrIi=1=∫Aie-nβn∣Drnv^i∣dv^i.The probability that there are no isolated nodes in any of the circle cells is bounded below: (34)1sn2NiPrIi=1≤1sn21+δ12nπsn2∫Aie-nβn∣Drnv^i∣dv^i≤1+δ12nπexp⁡-nβnπ2sn2Ai≤1+δ12nπexp⁡-2log⁡n+cn4π2sn2≤1+δ18πdnexp⁡-2log⁡n+cn4≤1+δ18πexp⁡-12log⁡n+log⁡dn.The second step and the third step are obtained since Drn(v^i)=(π/2)sn2 and Ai=(π/2)sn2, respectively. Since dn=o(n(1/4)(1-δ)), we get(35)1sn2NiPrIi=1⟶0.
Next we prove that every circle celli contains no component of size l, 2≤l≤Ni/2. The sum term in (30) is evaluated in following three cases based on the size of the component L.
Case
1
(
2
≤
l
≤
R
). In the case, fewer than (1-ϵ)lKn keys are assigned to the component L, where 0<δ1/(1-δ1)<ϵ<1, and R is an integer. Note that(36)PrAi,l≤PrUi,l≤xexp⁡-Ni-lKn2Pn+PrCi,lexp⁡-Ni-lKnx+1Pn.
First, we will give an upper bound onPr(Ui,l≤x) because(37)PrUi,l≤x=PrUi,l≤1-ϵlKn≤Pn1-ϵlKn1-ϵlKnPnlKn≤ePn1-ϵlKn1-ϵlKn1-ϵlKnPnlKn≤elKnlKnPnϵKnl.Since Pn≥n and nπrn2=dn, where dn=ω(log⁡n), dn=o(n(1/4)(1-δ)), we have (38)KnlPn=Pn2log⁡n+cndnlPn≤ldn2log⁡n≤Rlog⁡n-1/2.Since Kn→∞ we have ɛKn→∞ and thus for sufficiently large n(39)PrUi,l≤x=PrUi,l≤1-ϵlKn≤e1/ɛKnlPnɛKnl≤n-l.Then we have (40)1sn2∑LPUi,l≤xexp⁡-Ni-lKn2Pn≤1sn2∑l=2RNilPUi,l≤xexp⁡-Ni-lKn2Pn≤1sn2∑l=2RNiln-ln-1-δ1/2+2R/dn≤1sn2n-1-δ1/2+2R/dnNi2n-2+⋯+NiRn-R≤1sn2n-1-δ1/2+2R/dn1+δ12nπsn22n-21+o1≤π1+δ128dnn-1-δ1/2+2R/dn-1⟶0.The second inequality is true since Ni≥((1-δ1)/2)nπsn2 and 2nπsn2=dn. The last step holds since dn satisfies dn=ω(log⁡n) and dn=o(n(1/4)(1-δ)).
The following term satisfies(41)1sn2∑LPrCi,lexp⁡-Ni-lKnx+1Pn=1sn2∑l=2RNilPrCi,lexp⁡-Ni-lKnx+1Pn.Because Ni-(π/2)nsn2≤δ1(π/2)nsn2, we also have(42)1sn2∑LPrCi,lexp⁡-Ni-lKnx+1Pn≤1sn2∑l=2ReNillll-2Kn2Pnl-1exp⁡-1-ϵlNi-lNiKn2NiPn≤1sn2∑l=2Re1+δ1/2ll2nπsn2nπsn2Kn2Pnl-1exp⁡-1-ϵNi-lNilKn2Pn1-δ1nπsn22≤∑l=2Re1+δ1/2ll2nπ2log⁡n+cn2l-1exp⁡-1-δ11-ϵ2lNi-lNi2log⁡n+cn2≤∑l=2Re1+δ1/2ll2πexp⁡l-1log⁡2log⁡n+cn2-l1-δ11+ϵ2log⁡n+log⁡n.
Sinceδ1/(1-δ1)<ϵ, we get (1-δ1)(1+ϵ)>1. Then for sufficiently large n, from above discussion, we have (43)1sn2∑l=2RNilPrCi,lexp⁡-Ni-lKnx+1Pn⟶0.
Hence the probability that the subgraphGi has a component of size l, 2≤l≤R is(44)1sn2∑l=2RNilPrAi,l⟶0.
Case
2
R
+
1
≤
l
≤
L
1
n
. Here L1(n)=min⁡{Pn/Kn,Ni/2}. In this case, we assume that the component L is assigned at most (1/4)Knl keys. The probability that the subgraph Gi contains a component of size l, R+1≤l≤min⁡{Pn/Kn,Ni/2}, is(45)∑LPrAi,l≤∑LPr⁡Ui,l≤x+∑LPr⁡Ci,lexp⁡-Ni-lKnx+1Pn.The above bound is true since the expression exp⁡-(Ni-l)Kn2/Pn≤1, where we are summing over all subsets of nodes of size l, R+1≤l≤min⁡{Pn/Kn,Ni/2}. We wish to prove that this sum tends to 0 as n→∞.
Now we prove that∑LPr(Ui,l≤x)→0 as n→∞. Similar to the argument in the proof of case 1, we get (46)∑LPrUi,l≤x≤∑l=R+1L1nNilPn14lKnlKn4PnlKn≤∑l=R+1L1nPnlPn14lKnlKn4PnlKn≤∑l=R+1L1nPn14lKn2lKn4PnlKn≤∑l=1minPn/Kn,Ni/2eKnl4PnKnl/2.The summand in this last expression may be written in the form (yy)t, where y=eKnl/4Pn and t=2Pn/e. Since yy has no internal maximal value, our summand is maximized at the extremes of its range. Let μ denote the maximum of the summand; here (47)μ=max⁡eKn4PnKn/2,e4Pn/2,e4NiKn/4=on-1.As Kn→∞, we have (48)1sn2∑l=R+1L1nNilPrUi,l≤x≤1sn2Ni2+1μ≤1sn21+δ12nπsn2μ≤1+δ12nπμ=o1.
Now consider the second term in (45)(49)1sn2∑l=R+1L1nNilPr⁡Ci,le-Ni-lKnx+1/Pn≤1sn2∑l=R+1L1nNilll-2βnl-1exp⁡-Ni-llKn24Pn≤1sn2∑l=R+1L1n1+δ1ell2π2nsn2π2nsn2Kn2Pnl-1exp⁡-Ni-llKn24Pn≤∑l=R+1L1n1+δ1ell2πn22log⁡n+cn4l-1exp⁡-1-δ1-2lπnsn2l-1log⁡n8.Rewrite the above using the notation(50)anl=1+δ1e2log⁡n+cn4exp⁡1-δ1-2l/πnsn2log⁡n/8,and then (51)∑l=R+1L1n1+δ1ell2πn22log⁡n+cn4l-1exp⁡-1-δ1-2lπnsn2l-1log⁡n8≤πn2∑l>Ranll-1≤πn2anlR1-anl.The last step is true since 1-δ1-2l/πnsn2>0, so for some appropriate a>0,(52)1sn2∑l=R+1L1nNilPrCi,lexp⁡-Ni-lKnx+1Pn≤1na.
Case
3
(
L
1
(
n
)
<
l
≤
N
i
/
2: L1(n)=min⁡{Pn/Kn,Ni/2}). In this case, the component L of circle cell i is assigned at most Pn/4 keys; we have that(53)∑LPrAi,l≤∑LPrUi,l≤x+∑LPrCi,lexp⁡-Ni-lKnx+1Pn.Now we first show (1/sn2)∑LPr(Ui,l≤x)→0 as n→∞: (54)1sn2∑LPrUi,l≤x≤1sn2∑l=L1nNi/2NilPn14Pn14lKn≤1sn2∑l=L1nNi/2Nil4ePn/44-Pn≤1sn22Niexp⁡Pn4-32Pnlog⁡2≤exp⁡1+δ14dnlog⁡2-32Pnlog⁡2+Pn4-log⁡dn2π+log⁡n≤exp⁡-Pn32log⁡2-14+1+δ14dnPnlog⁡2-logdn/2πPn+log⁡nPn.
The third inequality uses∑l=L1(n)Ni/2Nil≤2Ni. Since Pn>n,dn=o(n(1/4)(1-δ)), the final expression tends to 0.
The term1/sn2∑LPrCi,lexp⁡-(Ni-l)Knx+1/Pn is bounded as follows. (55)1sn2∑l=L1nNi/2NilPrCi,lexp⁡-Ni-lKnx+1Pn≤1sn2∑l=L1nNi/2Nilexp⁡-KnNi8≤exp⁡-18NiKn+Nilog⁡2-log⁡sn2≤exp⁡-1-δ12nπsn2Kn8-log⁡2-log⁡dn2π+log⁡n≤exp⁡-dn41-δ1Kn8-log⁡2-log⁡dn2π+log⁡n≤exp⁡-dn1-δ14Kn8-log⁡2-log⁡dn/2πdn+log⁡ndn.The first inequality uses Pr(Ci,l)≤1 and l<Ni/2. Since dn=ω(log⁡n) and dn=o(n(1/4)(1-δ)), then for any Kn>8log⁡2, the last expression tends to 0.
Therefore the probability that the subgraphGi has a component of size l, L1(n)<l≤Ni/2, L1(n)=min⁡{Pn/Kn,Ni/2} is(56)1sn2∑l=L1nNi/2NilPrAi,l⟶0.From the above discussions, we have shown that for every circle cell i, 1≤i≤1/sn2, the probability for the existence of component of size l, 1≤l≤Ni/2, tends to 0 as n tends to infinity, which concludes Lemma 4.
We have proved that the overlapping structure of two adjacent circle cells contains at least one node and every circle cell is connected. The above two conditions ensure thatG(Pn,Kn,rn) is connected. Combining Lemma 3 with Lemma 4, the statement (ii) of Theorem 1 is established.


## 4. Conclusion and Future Work

Connectivity inG(Pn,Kn,rn) is the core subject of our paper. We obtain the zero-one law for graph connectivity in G(Pn,Kn,rn) under the given conditions. In order to get zero-one law for graph connectivity, we initially use the second moment method to get the 0-statement; then we show that any two adjacent circle cells share at least one common node and prove that any circle cell is connected to get the 1-statement.We conjecture that it is possible to prove a sharper connectivity threshold for random graphG(Pn,Kn,rn). Indeed, we believe that the following conjecture is true.Conjecture 5.
LetKn≥2, Kn,Pn→∞, Kn2/Pn→0, Pn≥n, and (57)πrn2Kn2Pn=log⁡n+cnn.(i)
Ifcn→-∞, then whp G(Pn,Kn,rn) is disconnected.(ii)
Ifcn→c, then the probability that G(Pn,Kn,rn) is connected tends to e-e-c.(iii)
Ifcn→∞, then whp G(Pn,Kn,rn) is connected.The results in this paper hold under the condition thatdn=ω(log⁡n) and dn=o(n(1-δ)/4). It would be interesting to see whether such results could be established under the condition that dn=ω(log⁡n) and dn=o(n), which remains an open research challenge.



---

*Source: 982094-2015-11-16.xml*