# On the Isolated Vertices and Connectivity in Random Intersection Graphs

Authors: Yilun Shang
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

We study isolated vertices and connectivity in the random intersection graphG(n,m,p). A Poisson convergence for the number of isolated vertices is
determined at the threshold for absence of isolated vertices, which is equivalent to
the threshold for connectivity. When m=⌊nα⌋ and α>6, we give the asymptotic
probability of connectivity at the threshold for connectivity. Analogous results are
well known in Erdős-Rényi random graphs.


---

## Body

## 1. Introduction

The classical random graphG(n,p), introduced by Erdős and Rényi in the late 1950s, consists of a fixed set of n vertices and edges that exist with a certain probability p, independently from each other. Since then many other random graph models with dependent edges have been developed. Among them, random intersection graph [1, 2] is defined as follows. Consider a set V with n vertices and another universal set W with m elements. Define a bipartite graph B(n,m,p) with independent vertex sets V and W. Edges between v∈V and w∈W exist independently with probability p. The random intersection graph G(n,m,p) derived from B(n,m,p) is defined on the vertex set V with vertices v1,v2∈V adjacent if and only if there exists some w∈W such that both v1 and v2 are adjacent to w in B(n,m,p).Appropriately scaling the parameterm as m=⌊nα⌋ with some α>0, Singer-Cohen [1] establishes connectivity thresholds for G(n,m,p): the threshold lies at p=(lnn)/m and (lnn)/nm for α≤1 and α>1, respectively. The result also reveals an asymptotic equivalence of graph connectivity and absence of isolated vertices in G(n,m,p), that is, the zero-one law for the absence of isolated vertices is equal to that for connectivity. This is familiar in Erdős-Rényi model; see [3, 4] for more details. The study in the present paper is in continuation of Chapter 3 in [1]. Taking our cue from existing results for Erdős-Rényi graphs (e.g., [4, Corollary 3.31] and [3, Theorem 7.3]), we aim to explore similar results for the properties of isolated vertices and connectivity in G(n,m,p).The connectivity thresholds of another class of random intersection graphsG(n,m,k), called random key graphs or uniform random intersection graphs, have been investigated recently [5, 6]. Both G(n,m,p) and G(n,m,k) can be viewed as subclasses of a general model [7]. In [8], the authors determine a zero-one law for the absence of isolated vertices in G(n,m,k), which again turns out to be equivalent to that for graph connectivity [6]. Moreover, they show a Poisson convergence for the number of isolated vertices, which refines the corresponding zero-one law and leads to a “double exponential” result.In this paper, we deal with the asymptotic distribution of the number of isolated vertices and address the connectivity probability inG(n,m,p) with m=⌊nα⌋, α>6. A Poisson approximation result (Theorem 2.1) for the number of isolated vertices is obtained by utilizing the Stein-Chen method, which yields convergence to a Poisson random variable. The isolated vertices threshold [1, Proposition 3.2] now readily follows from our Theorem 2.1 by an easy monotonicity argument. In addition, based on a strong equivalence theorem [9] relating the G(n,m,p) and G(n,p) models we derive an approximation of the probability of connectivity at the threshold when α>6 (see Theorem 2.3), which is analogous to the well-known “double exponential” result of Erdős and Rényi [10].Other related works regardingG(n,m,p) model have been reported. For example, [11, 12] examines the limiting distribution of the degree of a typical vertex, [13] treats the evolution of the order of the largest component, and random weights are assigned to the vertices in [14] to get general degree distributions.The rest of the paper is organized as follows. Our main results are presented in Section2. Sections 3 and 4 contain technical proofs of Theorems 2.1 and 2.3, respectively. Throughout the paper we set m=⌊nα⌋ for some α>0.


## 2. Main Results

In this section we provide our main results. LetX denote the number of isolated vertices in G(n,m,p) and let Poi(λ) be a Poisson random variable with parameter λ. Denote by E(X) and Var(X) the mean and variance of random variable X, respectively. Recall that the Poisson random variable has the unusual property that the mean and variance are both equal to the parameter λ.Theorem 2.1.
In the modelG(n,m,p), let
(2.1)p={ln⁡n+βnm,α≤1,ln⁡n+βnnm,α>1,
where βn∈ℝ. If limn→∞βn=β∈ℝ, then one has
(2.2)X⟶DPoi(e-β)
as n→∞, where →D represents convergence in distribution.The upcoming corollary is immediate from Theorem2.1.Corollary 2.2.
In the modelG(n,m,p) with p determined through (2.1), suppose limn→∞βn=β∈ℝ. Then one gets
(2.3)lim⁡n→∞P(G(n,m,p)containsnoisolatedvertices)=e-e-β.For a parallel “double exponential” result for connectivity whenα is large, we have the following.Theorem 2.3.
In the modelG(n,m,p) with α>6 and p determined through (2.1) (i.e., p=(lnn+βn)/nm), assume that limn→∞βn=β∈ℝ. Then one has
(2.4)lim⁡n→∞P(G(n,m,p)isconnected)=e-e-β.These results complement those presented in [1] and get further insight into the evolutionary similarities and differences between G(n,m,p) and G(n,p) models. A natural question would be to ask what happens for connectivity probability when α is small. This is currently under investigation.


## 3. Proof of Theorem2.1

Fori=1,…,n, let Xi=1[vertexiisisolatedinG(n,m,p)] and X=∑i=1nXi. Therefore, X counts the number of isolated vertices in G(n,m,p) as defined in Section 2. We will demonstrate the asymptotic Poisson distribution of X by employing the Stein-Chen method [15].Before proceeding, we first introduce some definitions and notations. Letq=1-p and |S| denote the cardinality of a set S. For two integer-valued random variables X and Y, the total variation distance between them (more correctly, between their distributions ℒ(X) and ℒ(Y)) is given by (3.1)dTV(X,Y)=dTV(L(X),L(Y))=sup⁡A⊆Z|P(X∈A)-P(Y∈A)|.
Let Γ be a finite set of indices and let (Ia)a∈Γ be a family of random indicator variables. We say (Ia)a∈Γ are positively related (c.f. [15]) if, for each a∈Γ, there exist random indicator variables (Jba)b∈Γ∖{a} with the distributions (3.2)L((Jba)b∈Γ∖{a})=L((Ib)b∈Γ∖{a}∣Ia=1),
such that Jba≥Ib for every b≠a. It is notable that “positively related” is much stronger than “positively correlated”. Suppose (an)n≥1 and (bn)n≥1 are sequences of positive real numbers. We write an~bn if limn→∞an/bn=1.A useful result obtained by the Stein-Chen method is the following.Lemma 3.1 (see [4, 15]).
Suppose thatY=∑a∈ΓIa, where the (Ia)a∈Γ are positively related random indicator variables. Then one has
(3.3)dTV(Y,Poi(EY))≤1-e-EYEY[Var⁡Y-EY+2∑a∈Γ(EIa)2].The next lemma collects some well-known approximations that are used in this paper.Lemma 3.2.
Ifmp→0, then  (1-p)m~1-mp; and if  mp2→0, then  (1-p)m~e-mp.In the sequel, we estimate the expectation of random variableX.Lemma 3.3.
Supposeα>0. Under the assumptions of Theorem 2.1, one gets
(3.4)lim⁡n→∞EX=e-β.Proof.
The probability that a vertexi is isolated can be computed as
(3.5)EXi=∑s=0m(ms)ps(1-p)m-s(1-p)(n-1)s=[1-p+p(1-p)n-1]m,
where the index s represents the number of vertices in W which are adjacent to i in B(n,m,p). Hence
(3.6)EX=n[1-p+p(1-p)n-1]m.
Forα≤1, we have
(3.7)mp2(1-qn-1)2≤mp2=(ln⁡n+βn)2m⟶0,pmqn-1=(ln⁡n+βn)(1-ln⁡n+βnm)n-1≤(ln⁡n+βn)e-((n-1)/m)(ln⁡n+βn)⟶0
as n→∞. Thus by Lemma 3.2, we obtain
(3.8)EX~ne-pm(1-qn-1)=ne-pmepmqn-1~ne-pm=ne-(ln⁡n+βn)⟶e-β,
as n→∞.
Forα>1, note that
(3.9)np=nln⁡n+βnnm=ln⁡n+βnnα-1⟶0,m(np2)2=m(ln⁡n+βnm)2=(ln⁡n+βn)2m⟶0
as n→∞. By using Lemma 3.2, we have
(3.10)EX~n[1-p+p(1-np)]m=n(1-np2)m~ne-np2m=ne-(ln⁡n+βn)⟶e-β,
as n→∞. The proof is then complete.Proof of Theorem2.1.
The triangular inequality for the total variation distance implies(3.11)dTV(X,Poi(e-β))≤dTV(X,Poi(EX))+dTV(Poi(EX),Poi(e-β)).
By a coupling argument ([16, page 58]) and Lemma 3.3, we have
(3.12)dTV(Poi(EX),Poi(e-β))≤|EX-e-β|⟶0
as n→∞. Combining this with (3.11), we now only need to prove
(3.13)lim⁡n→∞dTV(X,Poi(EX))=0.
First, we claim that(Xi)i=1n are positively related. To see this, define
(3.14)Xji=1[vertexjisisolatedinG(n,m-|Si|,p)]
for every j≠i, where Si⊆W represents the elements in W which are adjacent to i in B(n,m,p) (Si is possibly empty). The random graphs G(n,m-|Si|,p) and G(n,m,p) are coupled in a natural way. Conditional on the isolation of vertex i in G(n,m,p), any vertex j(j≠i) is not adjacent to vertices of Si in B(n,m,p). Hence, we have
(3.15)L((Xji)j=1,j≠in)=L((Xj)j=1,j≠in∣Xi=1).
For every j≠i, if Xj=1 then Xji=1. Consequently, we get Xji≥Xi.
By Lemma3.1, the binary nature and exchangeability of the random variables involved, we find that
(3.16)dTV(X,Poi(EX))≤1-e-EXEX[Var⁡X-EX+2∑i=1n(EXi)2]≤1EX[Var⁡X-EX+2∑i=1n(EXi)2]=1EX[E(X2)-(EX)2-EX+2n(EX1)2]=1EX[n(n-1)E(X1X2)-n(n-2)(EX1)2].
The cross term E(X1X2) in (3.16) is shown to be given by
(3.17)E(X1X2)=∑s=0m2m-s(ms)(1-p)2s(1-p)(m-s)(n-2)[p(1-p)]m-s=[(1-p)2+2p(1-p)n-1]m,
where s counts the number of vertices in W adjacent to neither 1 or 2 in B(n,m,p), leaving m-s vertices in W adjacent to exactly one of 1, 2.
Combining (3.5), (3.16), and (3.17) readily gives
(3.18)dTV(X,Poi(EX))≤(n-1)[(1-p)2+2p(1-p)n-1]m-(n-2)[1-p+p(1-p)n-1]2m[1-p+p(1-p)n-1]m.
Forα≤1, we have similarly as in the proof of Lemma 3.3,
(3.19)mp2(2-p-2qn-1)2≤4mp2⟶0,pmqn-1⟶0
as n→∞. Thereby, it follows from Lemma 3.2 that
(3.20)(n-1)[(1-p)2+2p(1-p)n-1]m=(n-1)[1-p(2-p-2qn-1)]m~ne-mp(2-p-2qn-1)=ne-2mpemp(p+2qn-1)~ne-2mp.
Applying this to (3.18), we obtain
(3.21)dTV(X,Poi(EX))≤(1+o(1))ne-2mp-(1+o(1))ne-2mp(1+o(1))e-mp=o(1)ne-mp=o(1)e-βn⟶0,
as n→∞.
Forα>1, we get as in the proof of Lemma 3.3,
(3.22)np⟶0,m(np2)2⟶0
as n→∞. Hence, from Lemma 3.2 we have
(3.23)(n-1)[(1-p)2+2p(1-p)n-1]m=(n-1)[1-2p+p2+2p(1-p)n-1]m~n[1-2p+p2+2p(1-np)]m~n(1-2np2)m~ne-2nmp2.
Applying this to (3.18), we have
(3.24)dTV(X,Poi(EX))≤(1+o(1))ne-2nmp2-(1+o(1))ne-2nmp2(1+o(1))e-nmp2=o(1)ne-nmp2=o(1)e-βn⟶0,
as n→∞, which concludes the proof.


## 4. Proof of Theorem2.3

Let(4.1)p̂=1-(1-p2q2+npq+(n2)p2)m.
The following lemma drawn from [9] states an equivalence of G(n,m,p) and G(n,p̂) models.Lemma 4.1 (see [9]).
Letα>6 and p be such that
(4.2)ωnm≤p≤2ln⁡n-ωm
for some ω→∞. For any a∈[0,1] and any graph property 𝒜, as n→∞ if it follows that
(4.3)P(G(n,m,p)∈A)⟶aifandonlyifP(G(n,p̂)∈A)⟶a.We recall the following classical result for connectivity threshold ofG(n,p).Lemma 4.2 (see [10]).
Letc∈ℝ be fixed and p=(lnn+c+o(1))/n. Then
(4.4)P(G(n,p)isconnected)⟶e-e-c,
as n→∞.Proof of Theorem2.3.
In view of Lemmas4.1 and 4.2, it suffices to prove that
(4.5)np̂-ln⁡n⟶β,
as n→∞.
By the assumptions, we find that(4.6)np̂-ln⁡n~n[1-(1-D(1-D)2+nD(1-D)+n2/2(D))m]-ln⁡n~n[1-(1-ln⁡n+βnnm+nnm(ln⁡n+βn)+(ln⁡n+βn)(1-n+n2/2))m]-ln⁡n,where 𝔇  denotes (lnn+βn)/nm. Since
(4.7)m(ln⁡n+βnnm+nnm(ln⁡n+βn)+(ln⁡n+βn)(1-n+n2/2))2⟶0
as n→∞, by Lemma 3.2, the right-hand side of (4.6)
(4.8)~nm(ln⁡n+βn)nm+nnm(ln⁡n+βn)+(ln⁡n+βn)(1-n+n2/2)-ln⁡n=βn-ln⁡nn(ln⁡n+βn)/m-ln⁡n(ln⁡n+βn)(1/nm-1/m+n/2m)1+n(ln⁡n+βn)/m+(ln⁡n+βn)(1/nm-1/m+n/2m)=βn+o(1)1+o(1)⟶β,
which concludes the proof.



---

*Source: 872703-2011-05-30.xml*