# Size of the Largest Component in a Critical Graph

Authors: Bin Wang; Lang Zou
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

In this paper, by the branching process and the martingale method, we prove that the size of the largest component in the critical random intersection graphGn,n5/3,p is asymptotically of order n2/3 and the width of scaling window is n−1/3.


---

## Body

## 1. Introduction and Main Result

Random intersection graphGn,m,p, which was introduced by Singer-Cohen [1] and Karoński et al. [2], is defined as follows. Let V be a set of n vertices and M a set of m elements. For each vertex v∈V, it is assigned a random subset Fv of M, where each element of M is included in Fv randomly and independently with probability p. There is an edge between vertices u and v if and only if Fu∩Fv≠∅. Denote the largest component in Gn,m,p by C1Gn,m,p and its size by C1. In Gn,m,p, Behrisch proved that [3] when m=nα and mp2=c/n, there is a phase transition of C1 in the vicinity of the point c=1 (here, we point out that when m>1 is not an integer, Gn,m,p means Gn,m,p with m being the largest integer less than m). When α>1 with high probability (for a given graph property A, we say that graph Gn possesses A with high probability if the probability that Gn possesses A tends to 1 as n⟶∞) (w.h.p. for brevity), C1 jumps from logarithmic order to linear order in n; Lagerås and Lindholm [4] also got that in Gn,m,p, with m=βn and p=γn−1, C1 exhibits a jump from logarithmic order to linear order in n around the point that βγ2=1. Recently, Wang et al. [5] studied the component evolution in critical Gn,m,p and got that when α>5/3, w.h.p. The order of the largest component in some critical random intersection graphs is n2/3 and the width of scaling window around the critical probability is n−1/3; while when 1<α<5/3 w.h.p. The order of the largest component and the width of the scaling window are n3−α/2 and n−α−1/2, respectively. It is natural to ask what is the order of C1 and what is the width of scaling window in critical Gn,n5/3,p, which is proposed in [5]. The aim of the present paper is to study the critical Gn,n5/3,p. Now our main result, which is not surprising but still interesting, can be stated as follows.Theorem 1.
Letεn be a positive function on n such that εn⟶0 and n1/3εn⟶∞ as n⟶∞. In Gn,m,p with m=n5/3, the following statements hold.(1)
Weakly subcritical case: ifmp2=1−εn/n, then there are two positive constants C1 and C2 such that w.h.p.(1)C1ε−2nlognε3n≤C1≤C2ε−2nlognε3n.(2)
Critical case: ifmp2=1+λn−1/3/n for some constant λ, then there are a positive function ω1n<logn, which tends to infinity as n⟶∞, and a constant C3=C3λ such that w.h.p.(2)ω1−1nn2/3≤C1≤C3n2/3logn.(3)
Weakly supercritical case: ifmp2=1+εn/n, then there are two positive constants C4 and C5 such that w.h.p.(3)C4nεn≤C1≤C5nεn.The following notation will be used. WriteP⋅, E⋅, and Var⋅ for the probability, expected value, and variance of a random event and a random variable, respectively. For any two positive functions fn and gn of a natural-valued parameter n, denote fn=Ogn if there is a positive constant C such that fn≤Cgn when n is large enough, fn=Θgn if fn=Ogn and gn=Ofn, and fn=ogn if limn⟶∞fn/gn=0. Furthermore, all logarithms in this article have the natural base, all inequalities or asymptotic statements have to be understood in terms of n being large enough yet fixed. And for clarity of presentation, floor and ceiling signs are omitted whenever they are not essential.


## 2. Auxiliary Lemmas

To get the bound, we need some properties of random variable with compound binomial distribution. LetX be a compound binomial distribution CBn,m,p with generating function:(4)fXx=ExX=1−p+p1−p+pxnm.Then, we have the following lemma.Lemma 1.
For any natural numbersn1,n2,m, let Zi be random variables with generating function 1−p+p1−p+pxnim, i=1,2. Suppose n1<n2, then(5)Z1≼Z2.Here,Z1≼Z2 means Z1 is stochastically smaller than Z2. It holds if and only if there exists a coupling Z^1,Z^2 of Z1 and Z2 such that PZ^1≤Z^2=1.Proof.
NoteZi can be expressed as Zi=∑k=1NXk, where Xis has the binomial distribution Bni,p and N has the binomial distribution Bm,p which is independent of Xis, i=1,2. Then, it is obvious by the coupling method.Besides the above lemma, we still need the following existing theorems.Theorem 2([6], Theorem 1).
Letp′=mp21−n−2p−mp2/2, np=o1, mp2<1, and A be an increasing graph property. If PGn,p′∈A⟶1, then(6)PGn,m,p∈A⟶1,where G∈A denotes that G has property A, and Gn,p′ is the Erdös–Rényi random graph which is obtained by retaining each edge of the complete graph on n vertices independently with probability p′.By Theorem 2, to give a lower bound forC1, the following theorem on the size of the largest component in the critical Erdös–Rényi random graph is useful.Theorem 3([7], Theorem 5.23, [8, 9]).
LetC1′ denote the size of the largest component in Gn,p′. For any ωn<n1/6 which tends to infinity as n⟶∞, the following statements hold.(a)
InGn,1−εn/n, if ωnn−1/3≤εn≤1/ωn, then w.h.p. C1′=2+o1ε−2nlognε3n(b)
InGn,1+εn/n, if ωnn−1/3≤εn≤n/ωn, then w.h.p. C1′=2+o1nεn(c)
InGn,1±εn/n, if 0≤εn≤ωnn−1/3, then w.h.p. n2/3/ω2n≤C1′≤ωnn2/3


## 3. Proof of Theorem 1

Note that given a functionℓn on n, the size of largest component at the least ℓn is an increasing property in Gn,m,p with respect to p. And when m=n5/3, mp2=1±εn/n and εn⟶0, n1/3εn⟶∞ as n⟶∞.(7)p′=mp21−n−2p−mp22=1±εnn+oεnn,when m=n5/3 and mp2=1+λn−1/3/n for some constant λ<0,(8)p′=mp21−n−2p−mp22=1+λ−1n−1/3n+on−4/3.Therefore, keeping Theorems 2-3 in mind, we can determine the lower bounds directly for the weakly subcritical, critical, and weakly supercritical cases. So we only need to prove the upper bounds in the rest of this section. We mainly combine the martingale argument [8] and branching process method [10] to obtain the upper bound. We will make use of the following component exploration process on random bipartite graph ℬn,m,p (see the footnote (note that Gn,m,p usually is constructed through the bipartite graph ℬn,m,p which is a graph with bipartition V,U, the vertices set V=v1,…,vn, and the elements set U=u1,…,um; any vertex in V and any element in U is connected by an edge in ℬn,m,p independently with probability p; an edge between vi and vj in Gn,m,p is present if both vi and vj are adjacent to some element in ℬn,m,p) for its definition), not on Gn,m,p, to get the size of components.Exploration process Ytt≥0. Let Cv be the component containing vertex v in Gn,m,p. In this procedure, we explore the vertices of V on the ℬn,m,p. During the exploration, vertices will be active, inactive, or neutral, and the elements of U are neutral all the time. At the beginning, assuming all the vertices are neutral, we choose a vertex v0∈V uniformly and make it active. At each time t≥1, we choose a vertex vt uniformly from the active vertices and check the vertices v∈V such that the distance between vt and v is two in ℬn,m,p, that is to check all pairs vtu where u runs over all the neutral elements in U. If vtu is an edge in ℬn,m,p, then check uv where v runs over all the neutral vertices. If there is an element u such that vtu and uv are present in ℬn,m,p then make v active; otherwise, keep it neutral. After checking all the neutral vertices in V, let vt be inactive. When there is no active vertex, the component Cv0, which is the set of inactive vertices, is explored. Then, we choose a neutral vertex uniformly from the rest of neutral ones and proceed on.LetXt be the number of vertices which become active due to the exploration of active vertex vt, which is the number of vertices at distance 2 from vt in ℬn,m,p, and denote Yt the total number of active vertices at step t∈0,1,…,n, where Y0=1. It is easy to see that for any t≥1,(9)Yt=Yt−1+Xt−1,ifYt−1>0,Xt,ifYt−1=0.DefineT to be the least t for which Yt=0, i.e.,(10)T=mint:Yt=0=mint:X1+X2+⋯+Xt=t−1.Then, at the timeT, the set of explored vertices is precisely Cv0, which means Cv0=T.


### 3.1. Weakly Subcritical Case

We only need to give an upper bound onT as Cv0=T. For this, we first define a random walk and a stopping time which is stochastically larger than T, then bound the stopping time to determine the desired result. To this end, we need the following lemma.Lemma 2 ([11], Lemma 8).
Letη be an integer random variable with Eη2<∞ such that, for any integer h≥2, we have Pη∈hℤ<1. Let ηii=1∞ be a sequence of i.i.d. Random variables distributed as η and(11)Φt=Φ0+∑i=1tηi,t∈0,1,2,…,where Φ0 is an integer constant. Define t to be its hitting time of 0, i.e.,(12)τ=mint:Φt=0.Ifθ0>0 satisfies(13)Eηeθ0η=0,then for any integer ℓ≥1,(14)Pτ=ℓ=Θℓ−3/2ϕθ0ℓ,where ϕθ=Eeθη and constants in Θ depend only on n and Φ0 but not on ℓ.Proof of the upper bound.
To make use of Lemma 2, letξtt=1∞ be a sequence of i.i.d. Random variables distributed as CBn,m,p. Set(15)Φt=1+∑i=1tξi−1.
Takeς=ξ1−1. Note ς∈−1,0,1,…,n−1 and set Pς=i=pi for i∈−1,0,1,…,n−1. For the simplicity of notation, write εn=ε in the rest of the paper. By these notations, when m=n5/3 and mp2=1−ε/n, where ε⟶0 and n1/3ε⟶∞ as n⟶∞,(16)Eς=Eξi−1=fX′1−1=−ε,(17)Eς2=fX21−fX′1+1=1−ε+n−1/31+o1,(18)Eς3=fX31+fX′1−1=1−4ε+3n−1/31+o1.
Define(19)Fθ=Eςeθςforθ∈ε1+ε,ε1−2ε.
Next, we will prove that there isθ0 satisfying(20)ε1+2ε<θ0<ε1−2εFθ0=Eςeθ0ς=0.
In fact, letan=ε/1+2ε and bn=ε/1−2ε. Note that for any natural number i and x∈0,∞, eix−e−x>i+1x. Then, when n is large enough we can obtain(21)Eςebnς=−e−bnp−1+ebnp1+2e2bnp2+⋯+n−2en−1bnpn−1=16e−bn−ε−∑i=1n−1ipi+∑i=1n−2ieibnpi=−εe−bn+∑i=1n−2ipieibn−e−bn≥−εe−bn+bn∑i=1n−2ii+1pi≥−ε1−bn+b2n+bnEς2−p−1+Eς+p−1>0.
Here, the last inequality holds as, notingbn<1,(22)ε1−bn+b2nEς2+Eς<ε1−2ε+n−1/31+o1<bn.Also, we can get that(23)Eςeanς=∑i=−1n−1eaniipi≤∑i=−1n−11+an+a2niipi≤∑i=−1n−11+ian+ia2n+2i2an31+an2ipi=∑i=−1n−1ipi+an+a2n∑i=−1n−1i2pi+2a2n1+an23∑i=−1n−1i3pi≤Eς+an+a2nEς2+a2nEς3≤16−18−ε+ε1+3ε1+2ε2+ε21+2ε2=−4ε31+2ε2<0.
Third, it is easy to check thatFθ is continuous in θ when θ∈ε/1+2ε,ε/1−2ε. Hence, the intermediate value theorem implies the claim holds. So far, by (16) and (17) and the inequalities ex<1+x+x2, 1+xk<1+kx+2k2x2/3 for any x∈0,2ε; when n is large enough, we can deduce that(24)Eeθ0ς=∑k=−1n−1eθ0kpk≤∑k=−1n−11+θ0+θ02kpk≤∑k=−1n−11+kθ0+θ02+2k23θ0+θ022pk=∑k=−1n−1pk+θ0+θ02∑k=−1n−1kpk+2θ0+θ0223∑k=−1n−1k2pk=1+θ0+θ02Eς+2θ0+θ0223Eς2≤1−ε24+oε2.
Now, we are in the position of exploring components ofℬn,m,p. Suppose that k vertices have been explored at step i in the exploration process. We are in the position of exploration through a vertex, say v. Since the number of neighbors of the initially picked vertex has distribution CBn,m,p and the fact that vertices only can be newly identified one time, the number of newly explored vertices Xi through v has the distribution CBn−k,m,p, by Lemma 1, Xi≼ξi, where ξi distributed as CBn,m,p. That is to say, ∑i=1kXi is dominated above by ∑i=1kξi for all k≤minT,n, where T is defined to be mint:Yt=0 in the exploration process. Let Ctv0 denote total inactive (explored) vertices which are explored from time 0 to t by the exploration process on ℬn,m,p starting from vertex v0 which is chosen uniformly from vertex set V. Define τ=mint:Φt=0,t≤n. Notice that(25)Ctv0=1+∑i=1tXi−1andΦt=1+∑i=1tξi−1.
Hence, there is a couplingC^tv0t,Φ^tt of the processes Ctv0t and Φtt such that(26)C^tv0≤Φ^t,t≤mins:C^sv0=0,which means τ is stochastically larger than T. So by Lemma 2, we get(27)PCv0≥κ0=PT≥κ0≤Pτ≥κ0=∑ℓ≥κ0Pτ=ℓ=∑ℓ≥κ0Oℓ−3/21−ε24+oε2ℓ.
For a positive constantC2>4, set κ0=C2ε−2nlognε3n. Then, by the inequality 1−x≤e−x,x≥0, we obtain that(28)Pτ≥κ0=Oκ0−3/2∑ℓ≥κ01−ε24+oε2ℓ=Oε−2κ0−3/21−ε24+oε2κ0=Oε−2κ0−3/2exp−κ0ε24+oκ0ε2=Oεlognε3−3/2nε3−C2/4+o1.
DenoteZ≥k=∑v∈V1Cv≥k. Then,(29)PC1≥κ0=PZ≥κ0≥κ0≤EZ≥κ0κ0=∑v∈VE1Cv≥κ0κ0=nPCv0≥κ0κ0≤nPτ≥κ0κ0=Onε3−C2/4−1−o1lognε3−5/2=o1.


### 3.2. Inside the Critical Window

As the size of largest component at the leastℓn for a given function ℓn on n is an increasing property in Gn,m,p with respect to p, to give an upper bound, we assume that λ>0 nmp2=1+λn−1/3. Recall ξii=1∞ which is a sequence of the i.i.d. Random variables distributed as CBn,m,p, and(30)Φt=1+∑i=1tξi−1andτ=mint:Φt=0,t≤n.For any real numberα, define(31)ϕα=Eeαξi−1=e−αEeαξiψα=logϕα.LetXt≔Xtα=exp−αΦt−tψ−α. Then, it is easy to check that Xt is a martingale with X0=e−α. By the optimal stopping theorem, we have EXτ=EX0=e−α. Let α0=λn−1/3. Then, by the equality 1−xn≤1−nx+n2x2/2 for any positive x=o1, we can obtain(32)Ee−α0ξt=1−p+p1+e−α0−1pnm≤1−p+p1+npe−α0−1+n2p22e−α0−12m=1+np2e−α0−1+n2p32e−α0−12m≤1+nmp2e−α0−1+mn2p32e−α0−12+m2n2p4e−α0−1221+npe−α0−122≤e−α0+α0e−α0−1+21+α02e−α0−123.Therefore,(33)ϕ−α0=Ee−α0ξi−1=eα0Ee−α0ξi≤1+α01−eα0+21+α02e−α0−11−eα03≤1−α024+oα02,which means ψ−α0<0. So, for any constant C3>4/3λ2, we have(34)Pτ≥C3n2/3logn=Pe−ψ−α0τ≥e−ψ−α0C3n2/3logn≤EXτe−C3ψ−α0n2/3logn=e−α0+C3ψ−α0n2/3logn≤e−α01−α024+oα02C3n2/3logn≤Oe−C3λ2/4logn.As in the proof of (27), we can determine that(35)PCv0≥C3n2/3logn≤Pτ≥C3n2/3logn=On−C3λ2logn/4.RecallZ≥k=∑v∈V1Cv≥k. Hence,(36)PC1≥C3n2/3logn=PZ≥C3n2/3logn≥C3n2/3logn≤EZ≥C3n2/3lognC3n2/3logn≤∑v∈VE1Cv≥C3n2/3lognC3n2/3logn≤nPCv0≥C3n2/3lognC3n2/3logn=On−C3λ2/4−1/3logn=o1.


### 3.3. Weakly Supercritical Case

In this subsection, we appeal to the branching process method [10] to get the upper bounds in the weakly supercritical regime of Gn,m,p. This method is also used by Kang et al. [12] to study other random graphs.Theorem 4 ([13], Theorem 3.7). Consider the Galton–Watson branching process BP with supercritical offspring distribution pkk≥0. Let X be the random variable with the distribution of the number of offsprings. Define(37)ϕs≔Ee−sX,λs≔−logϕs.Assumep0∈0,1; let s∗ be the unique positive solution to λs=s which means the supercritical branching process dies out with probability ρ∗≔e−s∗, and let(38)qk≔pke−s∗k+λs∗=pkρ∗k−1,k≥0.Then∑k≥0qk=1 and(39)∑k≥0kqk=λ′s∗<1.That is,qkk≥0 is an offspring distribution of a subcritical branching process which is often called the dual process of BP. Furthermore, if Tp denotes the branching tree for pkk≥0 and Tq is the corresponding object for qkk≥0, then for any finite tree T,(40)PTp=TBP=PTq=T.Now we can obtain the following Lemma 3 about the supercritical branching process with offspring distributionCBn,m,p and its dual process.Lemma 3.
LetBP denote the branching process with offspring distribution CBn,m,p, BP be its total size, and ρ∗ be its surviving probability, where m=n5/3,mp2=1+ε/n, ε⟶0, and n1/3εn⟶∞. Denote its dual process by BP∗ and the total size of BP∗ by BP∗. Then, the following holds.(1)
The surviving probability is(41)ρ∗=2+o1ε.(2)
There is a positive constantc˜ such that(42)EBP∗≤c˜ε.(3)
For any integerL=Ln,(43)PBP≥L≤1+o12ε+c˜εL.Proof.
(1) It is well known that for the Galton–Watson branching process with offspring distributionX, it survives with the probability ρ∗ which is the unique solution in 0,1 to 1−ρ=fX1−ρ, where fXx is the corresponding probability generating function; (see [14], Theorem 1.6.1). Therefore, we only need to check that for the branching process BP with distribution CBn,m,p,(44)there is  aρ∗∈2ε1+3ε,2ε1−3εsuch thatgρ∗=0,where(45)gρ=ρ−1+fX1−ρ,fX=ExX.In fact, gρ is continuous for ρ∈2ε/1+3ε,2ε/1−3ε, and by the inequality that for small enough x≥0,(46)1−nx+n2x22−n3x3≤1−xn≤1−nx+n2x22,we can obtain that(47)g2ε1+3ε=1−p+p1−2pε1+3εnm+2ε1+3ε−1≤461−p+p1−2npε1+3ε+2n2p2ε21+3ε2m+2ε1+3ε−1=1−2np2ε1+3ε+2n2p3ε21+3ε2m+2ε1+3ε−1≤461−2mnp2ε1+3ε+2mn2p3ε21+3ε2+2m2n2p4ε21+3ε21−npε1+3ε2+2ε1+3ε−1≤2ε1+3ε−2mnp2ε1+3ε+2mn2p3ε21+3ε2+2n2m2p4ε21+3ε2=−2ε21+3ε+2ε21+ε3/2n−1/31+3ε2+2ε21+ε21+3ε2=−2ε2n−1/31+3ε2εn1/3−ε2n1/3−1+ε3/2<0,(48)g2ε1−3ε=1−p+p1−2pε1−3εnm+2ε1−3ε−1≥461−p+p1−2npε1−3ε+2n2p2ε21−3ε2−8n3p3ε31−3ε3m+2ε1−3ε−1=1−2np2ε1−3ε+2n2p3ε21−3ε2−8n3p4ε31−3ε3m+2ε1−3ε−1≥461−2mnp2ε1−3ε+2mn2p3ε21−3ε2−8mn3p4ε31−3ε3+2ε1−3ε−1+m222np2ε1−3ε−2n2p3ε21−3ε2+8n3p4ε31−3ε32−m32np2ε1−3ε−2n2p3ε21−3ε2+8n3p4ε31−3ε33=−2ε21−3ε+2ε21+ε3/2n−1/31−3ε2−8ε31+ε2n−2/31−3ε3+2ε21+ε21−3ε21−ε1+ε1/2n−1/31−3ε+4ε21+εn−2/31−3ε22−8ε31+ε31−3ε31−ε1+ε1/2n−1/31−3ε+4ε21+εn−2/31−3ε23≥−2ε21−3ε+2ε21+ε21−3ε21−ε1+ε1/2n−1/31−3ε2−8ε31+ε31−3ε3≥−2ε21−3ε+2ε21+ε21−3ε21−2ε1+ε1/2n−1/31−3ε−8ε31+ε31−3ε3=10ε3+2ε41−3ε2−8ε31+ε31−3ε3−4ε31+ε5/2n−1/31−3ε3=2ε31+o1>0.Hence, the intermediate value theorem implies the claim holds.
(2)
To estimateEBP∗, we notice the following equalities or inequalities. First, (4) implies(49)EX=fX′1=nmp2=1+ε.Secondly, by Theorem 4,(50)e−s∗=1−ρ∗.And, we have(51)ϕs∗≔Ee−s∗X=E1−ρ∗X=1−p+p1−pρ∗nm≥1−p+p1−npρ∗m=1−np2ρ∗m≥1−nmp2ρ∗=1−2+o1ε1+ε.(52)p1=fX′xx=0=nmp21−pn−11−p+p1−pnm−1≤1+ε1−np+n2p221−np2+n2p32m−1≤1+εe−m−1np2−n2p3/2=1+εe−1+ε+1+ε3/2n−1/31+o1<12.Now, we are in position of estimating EBP∗. Let N∗ be the number of children for each vertex in the dual processes BP∗. Then,(53)EN∗=λ′s∗=∑k≥0kqk=∑k≥0kpke−ks∗+λs∗=∑k≥0kpk1−ρ∗kϕs∗=∑k≥2kpk1−ρ∗k+p11−ρ∗ϕs∗≤∑k≥2kpk1−ρ∗2+p11−ρ∗ϕs∗=∑k≥1kpk1−ρ∗2+p11−ρ∗−p11−ρ∗2ϕs∗=∑k≥1kpk1−ρ∗2+p11−ρ∗ρ∗ϕs∗≤511−3−2p1+o1ε1−2+o1ε≤1−1−2p1+o1ε<521.Hence, there is a positive constant c˜ such that the expectation of the total number of the vertices in the dual branching process is(54)EBP∗=1+EN∗+EN∗2+EN∗3+⋯=5311−EN∗≤11−2p1+o1ε≤c˜ε.
(3)
DenoteS for the event that BP survives and D=Sc for the event that the process BP dies out. Then,
(55)
P
B
P
≥
L
=
P
S
P
B
P
≥
L
S
+
P
D
P
B
P
≥
L
D
=
P
S
+
P
D
P
B
P
∗
≥
L
≤
1
+
o
1
2
ε
+
E
B
P
∗
L
≤
1
+
o
1
2
ε
+
c
˜
ε
L
.To prove the desired result, we still need the following auxiliary lemma. Note that any branching process can be understood as a potentially infinite random rooted tree. And the widthWT of a rooted tree T is the maximum of the sizes of the generations.Lemma 4.
LetBP denote the branching process with offspring distribution CBn,m,p, where m, n, and p, satisfy the conditions in (3) of Theorem 1. Denote S for the event that BP survives and D=SC for the event that the process BP dies out. Then for any function M such that εM⟶∞, we have(56)pWBP≥M∩D=oε.Proof.
DefineWM=WBP≥M and let us construct BP generation by generation and stop as soon as we see the first generation of size at the least M if there is one. Then, the conditional probability which the process dies out given that WM holds is at most(57)PDWM≤1−ρ∗M=1−21+o1εM≤e−εM=o1.
Hence, by(58)PWM=PWM∩S+PWM∩D=PWM∩S+PWMPDWM,
we have that(59)PWM=1−o1PWM∩S≤1−o1PS=2+o1ε,
which means(60)PWBP≥M∩D=PWMPDWM=oε.Given a vertexv of Gn,m,p, let Cv denote the component of Gn,m,p, containing v and Tv be the random spanning tree rooted at v which is obtained as following. First, explore new neighbors starting at v via the breadth-first search. In graph G=V,E, the breadth-first search for exploring vertices is as follows: starting with v, first we find all the neighbors, v1,…,vl; next, we find all the neighbors of v1∈V/v1,…,vl, then the new neighbors of v2different from the vertices explored so far, and so on, ending the second stage with the new neighbor vl. The third stage consists of finding all the neighbors of the vertices found in the second stage, and so on on Bn,m,p; then, contract the edges between the elements whose distance are 2k+1 from v and the vertices whose distances are 2k from v, k=0,1,2,…, i.e., we delete all the edges and v is connected to all the vertices whose distances are two from v in the graph resulting from the exploring process, say v11,…,v1i, and v11 is connected to all the vertices whose distances are two from v11,…; see Figure 1 for this operation. Let BP be the branching process with the distribution CBn,m,p, which can be interpreted as a potentially infinite random rooted tree. So, it is obvious that the following lemma holds.Figure 1Lemma 5.
For anyn,m,p, the random rooted trees Tv and BP can be coupled so that Tv⊆BP.LetSL be the set of all vertices of Gn,m,p, in components that contain at least L vertices, and sL be the cardinality of this set. We can get Lemma 6.Lemma 6.
LetL=Ln be a real function satisfying ε2L⟶∞ and L=oεn. Then,(61)EsL≤2+o1εn.Proof.
In fact, by Lemma 3,(62)EsL=∑vεVPCv≥L=nPCv≥L≤nPBP≥L≤n1+o12ε+c˜εL=2+o1εn.In the next lemma, we shall prove that the number of vertices in large components is concentrated around its expectation.Lemma 7.
SupposeL=Ln satisfies ε2L⟶∞ and L=oεn. Then, w.h.p.(63)sL=2+o1εn.Proof.
By Chebyshev’s inequality, to get the result, we should show(64)VarsL=EsL2−EsL2=oEsL2,which means it suffices to prove(65)EsL2≤4+o1ε2n2.
Fix a vertexv of Gn,m,p. We explore the component Cv by breadth-first search as before which generates a tree Tv′⊂Cv. But, we stop the exploration process immediately if one of the following events occurs:(i)
We have reachedL vertices in total(ii)
There areεL vertices which have been reached (found as a new neighbor of an earlier vertex) but not yet explored (tested for new neighbors)
Here, for anya∈ℝ, [a] is the smallest integer no less than a. We call a vertex reached but not fully explored a boundary vertex. Note that there are εL boundary vertices. Define(66)A=the exploration process stops whenioriioccurs.
Then, we can get thatTv′⊆Tv⊆BP. Also, as we proceed in breadth-first manner, all the boundary vertices are contained in two consecutive generations. Therefore, if A holds, then either BP≥L or the total number of offspring of branching process BP is finite and WBP≥εL/2. Hence, by Lemmas 4 and 5,(67)PA≤PBP≥L+PWBP≥εL/2∩D≤1+o12ε+c˜εL+oε=2+o1ε.
AsCv≥L implies A holds, we get(68)EsL2=∑vεVE1Cv≥LsL≤nE1AsL=nPAEsLA≤2+o1εnEsLA.
In the reminder of the proof, we shall prove that(69)EsLA≤2+o1εn.
Now given au∉Tv′, we explore its component as before in breadth-first search but within G′=BP/VTv′. Also, we couple the resulting tree Tu″ with BP so that Tu″⊂BP. Let Cu′ be the component of u in G′, so Cu′ is spanned by Tu″. Set S be the event that BP is infinite, and D=Sc. Notice that Cu′⊆Cu, and they are equal unless there is an edge connecting a boundary vertex to a vertex of Cu′. As there are εL boundary vertices,(70)PCu≠Tu″D∩A∩Tu″=r≤εLr1−1−p2m≤2εLr1−1−p2m≤3εLrmp2.
Here, the first inequality holds due to that for any finitely many eventsA1,…,Ak, P∪i=1kAi≤∑i=1kPAi, and 1−p2m is the probability that there is no common element for any two vertices vi and vj in Gn,m,p. One should notice that the event A depends only on the (edge) indicator random variables for edges with at least one endpoint in Tv′; on the other hand, the tree Tu″ is constructed in G′=BP/VTv′. This means that any event determined solely by Tu″ is by construction independent of the event A. Furthermore, D is independent of A. Therefore,(71)PCu≠Tu″D∩A=PCu≠Tu″∩D∩APD∩A=∑rPCu≠Tu″∩D∩A∩Tu″=rPD∩A=∑rPCu≠Tu″∩D∩A∩Tu″=r×PD∩A∩Tu″=rPD∩A≤3εLmp2∑rr×PD∩A∩Tu″=rPD∩A≤3εLmp2ETu″D.
Then, it follows that noting thatS is independent of A,(72)PCu≥LA=PCu≥LA∩APA=PCu≥LA∩A∩SPA+PCu≥LA∩D∩APA=PCu≥L∩ASPSPA+PCu≥LD∩APD∩APA=PASPSPA+PCu≥LD∩APD∩APA=PS+PCu≥L∩Cu≠Tu″D∩APD+PCu≥L∩Cu≠Tu″D∩APD≤PS+PCu≠Tu″D∩A+PCu≥LD≤PS+PCu≠Tu″D+PCu≥LD≤2+o1ε+3εLmp2ETu″D+ECuDL≤2+o1ε+3εLmp2EBPD+ECuD/LasTu″≤Cu≤2+o1ε+3εLmp21+o1ε+c˜Lεdue to Lemma7≤2+o1ε.
Thus, as there are at mostL vertices in Cu′,(73)ECu≥LA≤L+n−LPCu≥LA≤L+2+o1εn=2+o1εn,
which gives that(74)EsL2≤2+o1εnEsLA=4+o1ε2n2.Proof of (3) in Theorem 1.
Defineωn=εn1/3 which tends to ∞ as n⟶∞. And let L=εn/logωn, which means ε2L⟶∞ and L=oεn. Then (3) in Theorem 1 follows by Lemmas 5–7.


## 3.1. Weakly Subcritical Case

We only need to give an upper bound onT as Cv0=T. For this, we first define a random walk and a stopping time which is stochastically larger than T, then bound the stopping time to determine the desired result. To this end, we need the following lemma.Lemma 2 ([11], Lemma 8).
Letη be an integer random variable with Eη2<∞ such that, for any integer h≥2, we have Pη∈hℤ<1. Let ηii=1∞ be a sequence of i.i.d. Random variables distributed as η and(11)Φt=Φ0+∑i=1tηi,t∈0,1,2,…,where Φ0 is an integer constant. Define t to be its hitting time of 0, i.e.,(12)τ=mint:Φt=0.Ifθ0>0 satisfies(13)Eηeθ0η=0,then for any integer ℓ≥1,(14)Pτ=ℓ=Θℓ−3/2ϕθ0ℓ,where ϕθ=Eeθη and constants in Θ depend only on n and Φ0 but not on ℓ.Proof of the upper bound.
To make use of Lemma 2, letξtt=1∞ be a sequence of i.i.d. Random variables distributed as CBn,m,p. Set(15)Φt=1+∑i=1tξi−1.
Takeς=ξ1−1. Note ς∈−1,0,1,…,n−1 and set Pς=i=pi for i∈−1,0,1,…,n−1. For the simplicity of notation, write εn=ε in the rest of the paper. By these notations, when m=n5/3 and mp2=1−ε/n, where ε⟶0 and n1/3ε⟶∞ as n⟶∞,(16)Eς=Eξi−1=fX′1−1=−ε,(17)Eς2=fX21−fX′1+1=1−ε+n−1/31+o1,(18)Eς3=fX31+fX′1−1=1−4ε+3n−1/31+o1.
Define(19)Fθ=Eςeθςforθ∈ε1+ε,ε1−2ε.
Next, we will prove that there isθ0 satisfying(20)ε1+2ε<θ0<ε1−2εFθ0=Eςeθ0ς=0.
In fact, letan=ε/1+2ε and bn=ε/1−2ε. Note that for any natural number i and x∈0,∞, eix−e−x>i+1x. Then, when n is large enough we can obtain(21)Eςebnς=−e−bnp−1+ebnp1+2e2bnp2+⋯+n−2en−1bnpn−1=16e−bn−ε−∑i=1n−1ipi+∑i=1n−2ieibnpi=−εe−bn+∑i=1n−2ipieibn−e−bn≥−εe−bn+bn∑i=1n−2ii+1pi≥−ε1−bn+b2n+bnEς2−p−1+Eς+p−1>0.
Here, the last inequality holds as, notingbn<1,(22)ε1−bn+b2nEς2+Eς<ε1−2ε+n−1/31+o1<bn.Also, we can get that(23)Eςeanς=∑i=−1n−1eaniipi≤∑i=−1n−11+an+a2niipi≤∑i=−1n−11+ian+ia2n+2i2an31+an2ipi=∑i=−1n−1ipi+an+a2n∑i=−1n−1i2pi+2a2n1+an23∑i=−1n−1i3pi≤Eς+an+a2nEς2+a2nEς3≤16−18−ε+ε1+3ε1+2ε2+ε21+2ε2=−4ε31+2ε2<0.
Third, it is easy to check thatFθ is continuous in θ when θ∈ε/1+2ε,ε/1−2ε. Hence, the intermediate value theorem implies the claim holds. So far, by (16) and (17) and the inequalities ex<1+x+x2, 1+xk<1+kx+2k2x2/3 for any x∈0,2ε; when n is large enough, we can deduce that(24)Eeθ0ς=∑k=−1n−1eθ0kpk≤∑k=−1n−11+θ0+θ02kpk≤∑k=−1n−11+kθ0+θ02+2k23θ0+θ022pk=∑k=−1n−1pk+θ0+θ02∑k=−1n−1kpk+2θ0+θ0223∑k=−1n−1k2pk=1+θ0+θ02Eς+2θ0+θ0223Eς2≤1−ε24+oε2.
Now, we are in the position of exploring components ofℬn,m,p. Suppose that k vertices have been explored at step i in the exploration process. We are in the position of exploration through a vertex, say v. Since the number of neighbors of the initially picked vertex has distribution CBn,m,p and the fact that vertices only can be newly identified one time, the number of newly explored vertices Xi through v has the distribution CBn−k,m,p, by Lemma 1, Xi≼ξi, where ξi distributed as CBn,m,p. That is to say, ∑i=1kXi is dominated above by ∑i=1kξi for all k≤minT,n, where T is defined to be mint:Yt=0 in the exploration process. Let Ctv0 denote total inactive (explored) vertices which are explored from time 0 to t by the exploration process on ℬn,m,p starting from vertex v0 which is chosen uniformly from vertex set V. Define τ=mint:Φt=0,t≤n. Notice that(25)Ctv0=1+∑i=1tXi−1andΦt=1+∑i=1tξi−1.
Hence, there is a couplingC^tv0t,Φ^tt of the processes Ctv0t and Φtt such that(26)C^tv0≤Φ^t,t≤mins:C^sv0=0,which means τ is stochastically larger than T. So by Lemma 2, we get(27)PCv0≥κ0=PT≥κ0≤Pτ≥κ0=∑ℓ≥κ0Pτ=ℓ=∑ℓ≥κ0Oℓ−3/21−ε24+oε2ℓ.
For a positive constantC2>4, set κ0=C2ε−2nlognε3n. Then, by the inequality 1−x≤e−x,x≥0, we obtain that(28)Pτ≥κ0=Oκ0−3/2∑ℓ≥κ01−ε24+oε2ℓ=Oε−2κ0−3/21−ε24+oε2κ0=Oε−2κ0−3/2exp−κ0ε24+oκ0ε2=Oεlognε3−3/2nε3−C2/4+o1.
DenoteZ≥k=∑v∈V1Cv≥k. Then,(29)PC1≥κ0=PZ≥κ0≥κ0≤EZ≥κ0κ0=∑v∈VE1Cv≥κ0κ0=nPCv0≥κ0κ0≤nPτ≥κ0κ0=Onε3−C2/4−1−o1lognε3−5/2=o1.


## 3.2. Inside the Critical Window

As the size of largest component at the leastℓn for a given function ℓn on n is an increasing property in Gn,m,p with respect to p, to give an upper bound, we assume that λ>0 nmp2=1+λn−1/3. Recall ξii=1∞ which is a sequence of the i.i.d. Random variables distributed as CBn,m,p, and(30)Φt=1+∑i=1tξi−1andτ=mint:Φt=0,t≤n.For any real numberα, define(31)ϕα=Eeαξi−1=e−αEeαξiψα=logϕα.LetXt≔Xtα=exp−αΦt−tψ−α. Then, it is easy to check that Xt is a martingale with X0=e−α. By the optimal stopping theorem, we have EXτ=EX0=e−α. Let α0=λn−1/3. Then, by the equality 1−xn≤1−nx+n2x2/2 for any positive x=o1, we can obtain(32)Ee−α0ξt=1−p+p1+e−α0−1pnm≤1−p+p1+npe−α0−1+n2p22e−α0−12m=1+np2e−α0−1+n2p32e−α0−12m≤1+nmp2e−α0−1+mn2p32e−α0−12+m2n2p4e−α0−1221+npe−α0−122≤e−α0+α0e−α0−1+21+α02e−α0−123.Therefore,(33)ϕ−α0=Ee−α0ξi−1=eα0Ee−α0ξi≤1+α01−eα0+21+α02e−α0−11−eα03≤1−α024+oα02,which means ψ−α0<0. So, for any constant C3>4/3λ2, we have(34)Pτ≥C3n2/3logn=Pe−ψ−α0τ≥e−ψ−α0C3n2/3logn≤EXτe−C3ψ−α0n2/3logn=e−α0+C3ψ−α0n2/3logn≤e−α01−α024+oα02C3n2/3logn≤Oe−C3λ2/4logn.As in the proof of (27), we can determine that(35)PCv0≥C3n2/3logn≤Pτ≥C3n2/3logn=On−C3λ2logn/4.RecallZ≥k=∑v∈V1Cv≥k. Hence,(36)PC1≥C3n2/3logn=PZ≥C3n2/3logn≥C3n2/3logn≤EZ≥C3n2/3lognC3n2/3logn≤∑v∈VE1Cv≥C3n2/3lognC3n2/3logn≤nPCv0≥C3n2/3lognC3n2/3logn=On−C3λ2/4−1/3logn=o1.


## 3.3. Weakly Supercritical Case

In this subsection, we appeal to the branching process method [10] to get the upper bounds in the weakly supercritical regime of Gn,m,p. This method is also used by Kang et al. [12] to study other random graphs.Theorem 4 ([13], Theorem 3.7). Consider the Galton–Watson branching process BP with supercritical offspring distribution pkk≥0. Let X be the random variable with the distribution of the number of offsprings. Define(37)ϕs≔Ee−sX,λs≔−logϕs.Assumep0∈0,1; let s∗ be the unique positive solution to λs=s which means the supercritical branching process dies out with probability ρ∗≔e−s∗, and let(38)qk≔pke−s∗k+λs∗=pkρ∗k−1,k≥0.Then∑k≥0qk=1 and(39)∑k≥0kqk=λ′s∗<1.That is,qkk≥0 is an offspring distribution of a subcritical branching process which is often called the dual process of BP. Furthermore, if Tp denotes the branching tree for pkk≥0 and Tq is the corresponding object for qkk≥0, then for any finite tree T,(40)PTp=TBP=PTq=T.Now we can obtain the following Lemma 3 about the supercritical branching process with offspring distributionCBn,m,p and its dual process.Lemma 3.
LetBP denote the branching process with offspring distribution CBn,m,p, BP be its total size, and ρ∗ be its surviving probability, where m=n5/3,mp2=1+ε/n, ε⟶0, and n1/3εn⟶∞. Denote its dual process by BP∗ and the total size of BP∗ by BP∗. Then, the following holds.(1)
The surviving probability is(41)ρ∗=2+o1ε.(2)
There is a positive constantc˜ such that(42)EBP∗≤c˜ε.(3)
For any integerL=Ln,(43)PBP≥L≤1+o12ε+c˜εL.Proof.
(1) It is well known that for the Galton–Watson branching process with offspring distributionX, it survives with the probability ρ∗ which is the unique solution in 0,1 to 1−ρ=fX1−ρ, where fXx is the corresponding probability generating function; (see [14], Theorem 1.6.1). Therefore, we only need to check that for the branching process BP with distribution CBn,m,p,(44)there is  aρ∗∈2ε1+3ε,2ε1−3εsuch thatgρ∗=0,where(45)gρ=ρ−1+fX1−ρ,fX=ExX.In fact, gρ is continuous for ρ∈2ε/1+3ε,2ε/1−3ε, and by the inequality that for small enough x≥0,(46)1−nx+n2x22−n3x3≤1−xn≤1−nx+n2x22,we can obtain that(47)g2ε1+3ε=1−p+p1−2pε1+3εnm+2ε1+3ε−1≤461−p+p1−2npε1+3ε+2n2p2ε21+3ε2m+2ε1+3ε−1=1−2np2ε1+3ε+2n2p3ε21+3ε2m+2ε1+3ε−1≤461−2mnp2ε1+3ε+2mn2p3ε21+3ε2+2m2n2p4ε21+3ε21−npε1+3ε2+2ε1+3ε−1≤2ε1+3ε−2mnp2ε1+3ε+2mn2p3ε21+3ε2+2n2m2p4ε21+3ε2=−2ε21+3ε+2ε21+ε3/2n−1/31+3ε2+2ε21+ε21+3ε2=−2ε2n−1/31+3ε2εn1/3−ε2n1/3−1+ε3/2<0,(48)g2ε1−3ε=1−p+p1−2pε1−3εnm+2ε1−3ε−1≥461−p+p1−2npε1−3ε+2n2p2ε21−3ε2−8n3p3ε31−3ε3m+2ε1−3ε−1=1−2np2ε1−3ε+2n2p3ε21−3ε2−8n3p4ε31−3ε3m+2ε1−3ε−1≥461−2mnp2ε1−3ε+2mn2p3ε21−3ε2−8mn3p4ε31−3ε3+2ε1−3ε−1+m222np2ε1−3ε−2n2p3ε21−3ε2+8n3p4ε31−3ε32−m32np2ε1−3ε−2n2p3ε21−3ε2+8n3p4ε31−3ε33=−2ε21−3ε+2ε21+ε3/2n−1/31−3ε2−8ε31+ε2n−2/31−3ε3+2ε21+ε21−3ε21−ε1+ε1/2n−1/31−3ε+4ε21+εn−2/31−3ε22−8ε31+ε31−3ε31−ε1+ε1/2n−1/31−3ε+4ε21+εn−2/31−3ε23≥−2ε21−3ε+2ε21+ε21−3ε21−ε1+ε1/2n−1/31−3ε2−8ε31+ε31−3ε3≥−2ε21−3ε+2ε21+ε21−3ε21−2ε1+ε1/2n−1/31−3ε−8ε31+ε31−3ε3=10ε3+2ε41−3ε2−8ε31+ε31−3ε3−4ε31+ε5/2n−1/31−3ε3=2ε31+o1>0.Hence, the intermediate value theorem implies the claim holds.
(2)
To estimateEBP∗, we notice the following equalities or inequalities. First, (4) implies(49)EX=fX′1=nmp2=1+ε.Secondly, by Theorem 4,(50)e−s∗=1−ρ∗.And, we have(51)ϕs∗≔Ee−s∗X=E1−ρ∗X=1−p+p1−pρ∗nm≥1−p+p1−npρ∗m=1−np2ρ∗m≥1−nmp2ρ∗=1−2+o1ε1+ε.(52)p1=fX′xx=0=nmp21−pn−11−p+p1−pnm−1≤1+ε1−np+n2p221−np2+n2p32m−1≤1+εe−m−1np2−n2p3/2=1+εe−1+ε+1+ε3/2n−1/31+o1<12.Now, we are in position of estimating EBP∗. Let N∗ be the number of children for each vertex in the dual processes BP∗. Then,(53)EN∗=λ′s∗=∑k≥0kqk=∑k≥0kpke−ks∗+λs∗=∑k≥0kpk1−ρ∗kϕs∗=∑k≥2kpk1−ρ∗k+p11−ρ∗ϕs∗≤∑k≥2kpk1−ρ∗2+p11−ρ∗ϕs∗=∑k≥1kpk1−ρ∗2+p11−ρ∗−p11−ρ∗2ϕs∗=∑k≥1kpk1−ρ∗2+p11−ρ∗ρ∗ϕs∗≤511−3−2p1+o1ε1−2+o1ε≤1−1−2p1+o1ε<521.Hence, there is a positive constant c˜ such that the expectation of the total number of the vertices in the dual branching process is(54)EBP∗=1+EN∗+EN∗2+EN∗3+⋯=5311−EN∗≤11−2p1+o1ε≤c˜ε.
(3)
DenoteS for the event that BP survives and D=Sc for the event that the process BP dies out. Then,
(55)
P
B
P
≥
L
=
P
S
P
B
P
≥
L
S
+
P
D
P
B
P
≥
L
D
=
P
S
+
P
D
P
B
P
∗
≥
L
≤
1
+
o
1
2
ε
+
E
B
P
∗
L
≤
1
+
o
1
2
ε
+
c
˜
ε
L
.To prove the desired result, we still need the following auxiliary lemma. Note that any branching process can be understood as a potentially infinite random rooted tree. And the widthWT of a rooted tree T is the maximum of the sizes of the generations.Lemma 4.
LetBP denote the branching process with offspring distribution CBn,m,p, where m, n, and p, satisfy the conditions in (3) of Theorem 1. Denote S for the event that BP survives and D=SC for the event that the process BP dies out. Then for any function M such that εM⟶∞, we have(56)pWBP≥M∩D=oε.Proof.
DefineWM=WBP≥M and let us construct BP generation by generation and stop as soon as we see the first generation of size at the least M if there is one. Then, the conditional probability which the process dies out given that WM holds is at most(57)PDWM≤1−ρ∗M=1−21+o1εM≤e−εM=o1.
Hence, by(58)PWM=PWM∩S+PWM∩D=PWM∩S+PWMPDWM,
we have that(59)PWM=1−o1PWM∩S≤1−o1PS=2+o1ε,
which means(60)PWBP≥M∩D=PWMPDWM=oε.Given a vertexv of Gn,m,p, let Cv denote the component of Gn,m,p, containing v and Tv be the random spanning tree rooted at v which is obtained as following. First, explore new neighbors starting at v via the breadth-first search. In graph G=V,E, the breadth-first search for exploring vertices is as follows: starting with v, first we find all the neighbors, v1,…,vl; next, we find all the neighbors of v1∈V/v1,…,vl, then the new neighbors of v2different from the vertices explored so far, and so on, ending the second stage with the new neighbor vl. The third stage consists of finding all the neighbors of the vertices found in the second stage, and so on on Bn,m,p; then, contract the edges between the elements whose distance are 2k+1 from v and the vertices whose distances are 2k from v, k=0,1,2,…, i.e., we delete all the edges and v is connected to all the vertices whose distances are two from v in the graph resulting from the exploring process, say v11,…,v1i, and v11 is connected to all the vertices whose distances are two from v11,…; see Figure 1 for this operation. Let BP be the branching process with the distribution CBn,m,p, which can be interpreted as a potentially infinite random rooted tree. So, it is obvious that the following lemma holds.Figure 1Lemma 5.
For anyn,m,p, the random rooted trees Tv and BP can be coupled so that Tv⊆BP.LetSL be the set of all vertices of Gn,m,p, in components that contain at least L vertices, and sL be the cardinality of this set. We can get Lemma 6.Lemma 6.
LetL=Ln be a real function satisfying ε2L⟶∞ and L=oεn. Then,(61)EsL≤2+o1εn.Proof.
In fact, by Lemma 3,(62)EsL=∑vεVPCv≥L=nPCv≥L≤nPBP≥L≤n1+o12ε+c˜εL=2+o1εn.In the next lemma, we shall prove that the number of vertices in large components is concentrated around its expectation.Lemma 7.
SupposeL=Ln satisfies ε2L⟶∞ and L=oεn. Then, w.h.p.(63)sL=2+o1εn.Proof.
By Chebyshev’s inequality, to get the result, we should show(64)VarsL=EsL2−EsL2=oEsL2,which means it suffices to prove(65)EsL2≤4+o1ε2n2.
Fix a vertexv of Gn,m,p. We explore the component Cv by breadth-first search as before which generates a tree Tv′⊂Cv. But, we stop the exploration process immediately if one of the following events occurs:(i)
We have reachedL vertices in total(ii)
There areεL vertices which have been reached (found as a new neighbor of an earlier vertex) but not yet explored (tested for new neighbors)
Here, for anya∈ℝ, [a] is the smallest integer no less than a. We call a vertex reached but not fully explored a boundary vertex. Note that there are εL boundary vertices. Define(66)A=the exploration process stops whenioriioccurs.
Then, we can get thatTv′⊆Tv⊆BP. Also, as we proceed in breadth-first manner, all the boundary vertices are contained in two consecutive generations. Therefore, if A holds, then either BP≥L or the total number of offspring of branching process BP is finite and WBP≥εL/2. Hence, by Lemmas 4 and 5,(67)PA≤PBP≥L+PWBP≥εL/2∩D≤1+o12ε+c˜εL+oε=2+o1ε.
AsCv≥L implies A holds, we get(68)EsL2=∑vεVE1Cv≥LsL≤nE1AsL=nPAEsLA≤2+o1εnEsLA.
In the reminder of the proof, we shall prove that(69)EsLA≤2+o1εn.
Now given au∉Tv′, we explore its component as before in breadth-first search but within G′=BP/VTv′. Also, we couple the resulting tree Tu″ with BP so that Tu″⊂BP. Let Cu′ be the component of u in G′, so Cu′ is spanned by Tu″. Set S be the event that BP is infinite, and D=Sc. Notice that Cu′⊆Cu, and they are equal unless there is an edge connecting a boundary vertex to a vertex of Cu′. As there are εL boundary vertices,(70)PCu≠Tu″D∩A∩Tu″=r≤εLr1−1−p2m≤2εLr1−1−p2m≤3εLrmp2.
Here, the first inequality holds due to that for any finitely many eventsA1,…,Ak, P∪i=1kAi≤∑i=1kPAi, and 1−p2m is the probability that there is no common element for any two vertices vi and vj in Gn,m,p. One should notice that the event A depends only on the (edge) indicator random variables for edges with at least one endpoint in Tv′; on the other hand, the tree Tu″ is constructed in G′=BP/VTv′. This means that any event determined solely by Tu″ is by construction independent of the event A. Furthermore, D is independent of A. Therefore,(71)PCu≠Tu″D∩A=PCu≠Tu″∩D∩APD∩A=∑rPCu≠Tu″∩D∩A∩Tu″=rPD∩A=∑rPCu≠Tu″∩D∩A∩Tu″=r×PD∩A∩Tu″=rPD∩A≤3εLmp2∑rr×PD∩A∩Tu″=rPD∩A≤3εLmp2ETu″D.
Then, it follows that noting thatS is independent of A,(72)PCu≥LA=PCu≥LA∩APA=PCu≥LA∩A∩SPA+PCu≥LA∩D∩APA=PCu≥L∩ASPSPA+PCu≥LD∩APD∩APA=PASPSPA+PCu≥LD∩APD∩APA=PS+PCu≥L∩Cu≠Tu″D∩APD+PCu≥L∩Cu≠Tu″D∩APD≤PS+PCu≠Tu″D∩A+PCu≥LD≤PS+PCu≠Tu″D+PCu≥LD≤2+o1ε+3εLmp2ETu″D+ECuDL≤2+o1ε+3εLmp2EBPD+ECuD/LasTu″≤Cu≤2+o1ε+3εLmp21+o1ε+c˜Lεdue to Lemma7≤2+o1ε.
Thus, as there are at mostL vertices in Cu′,(73)ECu≥LA≤L+n−LPCu≥LA≤L+2+o1εn=2+o1εn,
which gives that(74)EsL2≤2+o1εnEsLA=4+o1ε2n2.Proof of (3) in Theorem 1.
Defineωn=εn1/3 which tends to ∞ as n⟶∞. And let L=εn/logωn, which means ε2L⟶∞ and L=oεn. Then (3) in Theorem 1 follows by Lemmas 5–7.



---

*Source: 1731802-2019-09-10.xml*