# The Largest Component of Near-Critical Random Intersection Graph with Tunable Clustering

Authors: Shiying Huang; Bin Wang
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, we study the largest component of the near-critical random intersection graphGn,m,p with n nodes and m elements, where m=Θn which leads to the fact that the clustering is tunable. We prove that with high probability the size of the largest component in the weakly supercritical random intersection graph with tunable clustering on n vertices is of order nϵn, and it is of order ϵ−2nlognϵ3n in the weakly subcritical one, where ϵn⟶0 and n1/3ϵn⟶∞ as n⟶∞.


---

## Body

## 1. Introduction and Main Result

Singer-Cohen [1] and Karoński et al. [2] invented the binomial random intersection graph model Gn,m,p. It can be constructed by a random bipartite graph ℬn,m,p, which is a graph with vertex set V=v1,…,vn and element set M=u1,…,um. Any vertex vi and any element uj are independently connected with probability p in ℬn,m,p, i=1,…,n, j=1,…,m. Then Gn,m,p is a random graph with the vertex set V, and the vertices vi and vk are connected if both vi and vk are adjacent to an element in ℬn,m,p. Since then, random intersection graphs have received considerable attention in the past two decades. They have been widely used for classification analysis [3,4], clustering [5,6], wireless sensor networks [7], social networks [8], and so on; refer to the survey [9] and references therein for more information on their application.One of the important issues in random graphs is to determine the size of the largest component. Denote the size of the largest component ofGn,m,p by C1Gn,m,p (C1 for simplicity). Behrisch [10] found that when m=⌊nα⌋ (when m>1 and it is not an integer, Gn,m,p means Gn,⌊m⌋,p with ⌊m⌋ being the largest integer less than m) and p=c/nm, there is a phase transition of C1 at the point c=1. When α>1, if p>1/nm, then with high probability (for a given graph property A, the authors say that graph Gn possesses A with high probability if limn⟶∞PGnpossessesA=1) (w.h.p. for brevity) C1 is linear in n; if p<1/nm, then w.h.p. its order is logn. Meanwhile, when 0<α<1, it jumps from n1−α/2logn to n1+α/2 as c increases. Lagerås and Lindholm [11] extended this result to the case when m=βn and p=γ/n, whose clustering is tunable [6]. For the first rigorous mathematical analysis of clustering in random intersection graphs, see [12]. Recently, Wang et al. [13,14] studied the component evolution in Gn,m,p when p=1±ϵn/nm, where m=nαα>1 and ϵn⟶0 as n⟶∞. They obtained that the order of C1 and the width of the scaling window around the critical probability depend on whether α≥5/3. If α≥5/3, they are n2/3 and n−1/3, respectively, which are independent of α, and the evolution is similar to that in the critical Erdös-Rényi random graph; meanwhile if 1<α<5/3, they are n3−α/2 and n−α−1/2, respectively. Federico [15] obtained that when α>1 (0<α<1, respectively), the sizes of the largest components of critical Gn,m,p, rescaled by n−2/3 (n−3−α/6, respectively), converge to nondegenerated random variables. It is natural to ask what is the order of C1 near the critical window in Gn,⌊βn⌋,γn−1, that is, when βγ2=1±ϵn, where ϵn⟶0 as n⟶∞. Now our main result can be stated as follows.Theorem 1.
Letβ be a positive constant which is independent of n with γ≔γn being a positive function on n. Denote ϵn by a positive function on n such that ϵn⟶0 and n1/3ϵn⟶∞ as n⟶∞. In Gn,m,p with m=⌊βn⌋ and p=γ/n, the following statements hold:(1)
(Weakly supercritical regime). Ifβγ2=1+ϵn, then there are two positive constants C1 and C2 which are independent of n such that w.h.p.(1)C1nϵn≤C1≤C2nϵn.(2)
(Weakly subcritical regime). Ifβγ2=1−ϵn, then there are two positive constants C3 and C4 which are independent of n such that w.h.p.(2)C3ϵ−2nlognϵ3n≤C1≤C4ϵ−2nlognϵ3n.Remark 1.
Letϵn>0 and limn⟶∞ϵn=0. If nϵ3n⟶∞, then in the Erdös-Rényi random graph Gn,1−ϵn/n w.h.p. the size of the largest component is 2+o1ϵ−2nlognϵ3n, and in Gn,1+ϵn/n, w.h.p. it is 2+o1nϵn; while if nϵ3n=O1, then in Gn,1±ϵn/n w.h.p. it is of order n2/3. So it is worth showing that the upper bound and lower bound can be approximately equivalent near the critical window in Gn,⌊βn⌋,γ/n. It is interesting to determine the size of largest component in Gn,⌊βn⌋,γ/n when βγ2=1±ϵn and ϵn=On−1/3. It may be of size approximately n2/3. The method used in this article failed to prove these two problems.Remark 2.
For the upper bound of the size of largest component in random graphs, one of standard methods is to use a branching process to dominate the corresponding exploration process from above. Usually the main problem is how to obtain the lower bound. To boundC1 from below in Gn,⌊βn⌋,p, it does not work by the comparison of Gn,m,p and Erdös-Rényi random graph Gn,p^ for some suitable p^ through the result in [16], as it does not cover the case when m and n are of the same order. Hence, first we converted the problem of bounding C1 from below into the problem of giving a lower bound for the size of the largest component in random bipartite graph ℬn,n,p. Then we analyzed the Depth First Search (DFS) algorithm and an exploration process on ℬn,n,p to achieve our purpose. Note that Johannson [17] only proved that the order of the largest component in the critical ℬn,n,p is of order on. We think this is our main contribution.Remark 3.
When we decided to submit it to a journal for possible publication, Ambroggio [18] proposed an elementary approach to study the upper bound of the component size in some critical random graph. We applied her/his argument in Section 3.1 and found that it is shorter than our proof. While the method in [18] does not work for the case m=nαα>1, the branching process argument works. So we present it here instead of the proof using Ambroggio’s argument.Our notations are standard.P⋅, E⋅, and Var⋅ denote the probability, expected value, and variance, respectively. For any two positive functions fn and gn, write fn=Ogn or gn=Ωfn if fn≤Cgn for some positive constant C when n is large enough; fn=Θgn if fn=Ogn and gn=Ofn ; and fn=ogn or gn≫fn if limn⟶∞fn/gn=0. All logarithms have the natural base, and all inequalities or asymptotic statements are to be understood in terms of n being large enough yet fixed. For clarity of presentation, write ϵn=ϵ, and floor and ceiling signs are omitted whenever they are not essential in the rest of the paper.The remainder of this paper is organized as follows. In Section2, for the lower bound of C1, we first show that it is only needed to give a lower bound for the size of the largest component in ℬn,n,p. Then, we obtain the lower bound by analyzing the DFS algorithm on ℬn,n,p for the weakly supercritical regime in Section 2.1 and by analyzing the standard exploration process on ℬn,n,p for the subcritical one in Section 2.2. We get the upper bound for the weakly supercritical regime in Section 3.1 and that for the weakly subcritical one in Section 3.2 through the branching process method and the coupling technique, respectively.


## 2. The Proof of the Lower Bound

In this section, the following standard exploration process on the random bipartite graphℬn,m,p will be used.For exploration processYtt≥0, let Cv be the component containing the vertex v∈V in ℬn,m,p. In this procedure, the vertices and the elements will be in an active, inactive, or neutral state. In the beginning, it is assumed that all vertices and elements are neutral. We choose a vertex, say v0, from V uniformly and make it active. At each time t≥1, we choose a vertex vt or element ut uniformly from the active vertices and elements. Suppose that we choose a vertex vt, check the pairs vtu′ where u′ runs over all the neutral elements. If vtu′∈ℬn,m,p, then make u′ active; otherwise, keep it neutral. After checking all the neutral elements, let vt be inactive. Meanwhile if we choose an element ut, check the pairs utv′ where v′ runs over all the neutral vertices. If utv′∈ℬn,m,p, then make v′ active; otherwise, keep it neutral. When there is no active vertex or element, component Cv0 is explored which is composed of vertices and elements in ℬn,m,p. Then, we uniformly choose a neutral vertex (or an element) from the rest of the neutral ones and proceed on.For simplicity, we do not distinguish the vertices and elements and call them vertices in this section. It is natural as we only consider the size of the largest component inℬn,m,p. So let Xt be the number of vertices which become active due to the exploration of vertex vt (vt∈V or vt∈M); and let Yt be 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,(3)Yt=Yt−1+Xt−1,ifYt−1>0,Xt,ifYt−1=0.Now we can obtain the following Lemma1 and Lemma 2 by applying the above process on ℬn,βn,p.Lemma 1.
For anyp∈0,1, let C1Gn,βin,p be the size of the largest component in Gn,βin,p, where βi is a positive constant which is independent of n, i=1,2. If 0<β1≤β2, then(4)C1Gn,β1n,p≺¯C1Gn,β2n,p.Here see the footnote for the relation≺¯ (the authors say random variable X is stochastically smaller than random variable Y and denote it by X≺¯Y, if and only if there exists a coupling X^,Y^ of X and Y such that PX^≤Y^=1).Proof.
LetV≔v1,…,vn which is the vertex set of Gn,β1n,p and Gn,β2n,p. Suppose that the element sets of Gn,β1n,p and Gn,β2n,p are M1 and M2, respectively, where M1=u1,…,uβ1n and M2=u1,…,uβ1n,uβ1n+1,…,uβ2n⊇M1. Given the random bipartite graph ℬn,β2n,p with sets V and M2, the graph ℬn,β1n,p is defined to be the subgraph of ℬn,β2n,p induced by V and M1. By this construction, the probability of vℓ and vk which are adjacent in Gn,β2n,p is larger than that in Gn,β1n,p. Then the conclusion holds obviously.Lemma 2.
LetC1ℬn,βn,p be the size of the largest component in ℬn,βn,p for any p∈0,1, where β is a positive constant which is independent of n. Denote the number of its vertices by C1βV which is just C1Gn,βn,p and the number of its elements by C1βM. If C1ℬn,βn,p≔fn⟶+∞ as n⟶∞, then w.h.p.(5)C1βV=C1Gn,βn,p=ΘfnandC1βM=Θfn.Proof.
In the process of exploringℬn,βn,p, suppose that the explored element set and the active element set at time t are MDt and MAt, respectively, and the explored vertex set and active vertex set are VDt and VAt, respectively. If we choose an active vertex vt from V at time t, then the number of elements which would be explored through vt (denote it by Xt) is distributed as the binomial distribution Binβn−MDt−MAt,p. Therefore, Xt≺¯Υt for any t≤minn,T, where T=mint:Yt=0 and Υt is distributed as Binβn,p.
Now, suppose that we get the largest componentC1ℬn,βn,p in which there are C1βV=gn vertices from V and C1βM elements from M through the exploration process. Conditioned on C1βV=gn, we can determine what the order of C1βM should be. In fact, by the above explanation, the number of elements which would be explored through any vertex v∈V is dominated by Binβn,p at any step t; and remember that we made the assumption that there are gn vertices from V. Hence, for the total number of elements C1βM we explored, we have(6)C1βM=∑t=1gnXt≺¯Υ1+Υ2+⋯+Υgn≺¯Υ.
HereΥ is distributed as Bingnβn,p. It is easy to check(7)EΥ=βγgn⟶∞;VarΥ=oEΥ2.
Chebyshev’s inequality (refer to [[19], Corollary 4.3.3]) implies Υ=1+o1βγgn. Hence w.h.p. C1βM≤1+o1βγgn. Notice βγ=β+o1 under the assumption that βγ2=1+o1. We have(8)gn≤fn=C1ℬn,βn,p=C1βV+C1βM≤gn+1+o1βγgn=1+β+o1gn.
The proof ofC1βM=Θfn can be given similarly.Recall that the component inℬn,m,p consists of some vertices from V and some elements from M. According to Lemma 1, when β≥1, we only need to bound C1Gn,n,p from below; and when β≤1, we choose an element from M and run the exploration process on ℬn,βn,p. Then it boils down to the case where β≥1 by Lemma 2. Therefore, we only need to give a lower bound on C1ℬn,n,p in the rest of this section. Note that in Theorem 1 when m=n, p=1±ϵ/n=1±ϵ/2+oϵ/n. We write p=1±ϵ/n for simplicity as it does not affect the result when ϵ⟶0 and ϵn1/3⟶∞.


### 2.1. Lower Bound in the Weakly Supercritical Regime

Breadth First Search (BFS) and Depth First Search (DFS) are two well-known algorithms in the graph exploration. They are widely used to study the structure of (random) graphs. The DFS has been utilized to investigate random graphs by some scholars such as Ben-Eliezer et al. [20], Krivelevich and Sudakov [21], Joseph [22], and Cooley et al. [23]. In this section, we applied the DFS to the bipartite graph B∈ℬn,n,p to obtain the lower bound according to the ideas in [21,23] which are used to study the largest component in the Erdös-Rényi random graph and the random hypergraph, respectively. Before starting to prove the lower bound, we need a lemma about a sequence of i.i.d. Bernoulli random variables with parameter p.Lemma 3.
Letκii=1n2 be the i.i.d. Bernoulli random variables with parameter p=1+ϵ/n, where ϵ is a positive function on n such that ϵ⟶0 and ϵn1/3⟶∞ as n⟶∞. Then, for any t∈a1ϵn2,a2ϵn2, where ais are positive constants independently of n, i=1,2, w.h.p. we have(9)∑i=1tκi−pt≤ϵ2n4.The following auxiliary lemma is needed to prove Lemma3.Lemma 4 (see Lemma 7 in [24] and Lemma 9 in [23]).
LetZii=1ℓ be a martingale with Z0=0. If there are two positive constants b1 and b2 with b1<b2/10 such that −b1≤Zi−Zi−1≤b2 for any i∈1,ℓ, then, for any 0<C<b1ℓ,(10)PZℓ≥C≤2exp−C23b1b2ℓ.Proof of Lemma 3.
For anyt∈a1ϵn2,a2ϵn2, define Λ0=0, and(11)Λt+1=Λt+κt+1−p,ifΛt≤ϵ2n4,Λt,otherwise.
It is easy to verify that it indeed is a martingale with the stopping timemint:Λt>ε2n/4; and −p≤Λt+1−Λt≤1−p<1. By Lemma 4, we have(12)P∑i=1tκi−pt≥ϵ2n4≤2exp−ϵ2n248pa2ϵn2=2exp−nϵ348a21+ϵ=o1.Now we prove the lower bound ofC1ℬn,n,p.Proof.
We choose a graphB from ℬn,n,p uniformly. Write B=V,M,E, where E is the edge set. Let σV be a linear ordering of V and let σM be a linear ordering of M. In the exploration process, let S be the set of vertices that have been explored; let T be the set of unvisited vertices, and U=V∪M\S∪T in which the vertices of U are put in a stack. We run the following DFS algorithm on B to obtain components (recall that both the vertices and the elements are called vertices in this section). See Algorithm 1.
Consider a sequenceκii=1n2 of the i.i.d. Bernoulli random variables with parameter p which is the sequence of edges in B∈ℬn,n,p. That is, κi is the result of the i-th queried edge. If the queried edge is in B, then κi=1; otherwise κi=0. We have the following claim.Algorithm 1:  DFS on bipartite graph B∈ℬn,n,p starting from a vertex in V.
Input:B=V,M,E, σV–a linear ordering of V, σM– a linear ordering of M.Output:C-set of components of B.C≔∅; The stackU≔∅;repeatLetv0 be the smallest neutral vertex in V according to σV;Makev0 as active, and add v0 to UWheneverU≠∅ doLetx be the top vertices of U. Scanning T.Ifx∈V and there exists the smallest element u according to σMsuch thatxu∈E then delete x from T and put it into U.Otherwise, then takex out of U and put it into S.Ifx∈M and there exists the smallest vertex v according to σVsuch thatxv∈E then delete x from T and put it into U.Otherwise, then takex out of U and put it into S.LetC be the set of vertices explored in the while-loop above;C≔C∪CUntil all vertices are explored.Claim 1.
Between the query4ϵn2/5 and the query ϵn2 w.h.p. the stack U is not empty.Proof.
of Claim. First, we can assume that S<n. In fact, if S≥n, let us consider the time that S=n. By Lemma 3, U<2a2ϵn, which means T=2n−S−U>n−2a2ϵn. Since B is a bipartite graph, when we run the DFS on B, both S and T have half vertices in V and M. Hence, between S and T, at time t the DFS has made queries at least(13)2×S2−1×T2−1≥2n2−1n−2a2ϵn2−1>n24≫ϵn2≥t.
It is a contradiction. Secondly, by Lemma3, we have that, at any time t∈4ϵn2/5,ϵn2, S∪U≥pt−ϵ2n/4. Suppose that stack U is empty which means there are only explored vertices and neutral vertex after some t queries for t∈4ϵn2/5,ϵn2; then S≥pt−ϵ2n/4. Therefore, if stack U is empty, we can assume S∈pt−ϵ2n/4,n. Meanwhile, at time t, the number of edges that have been queried is w.h.p. at least S/2n−S/2×2, which comes from the fact that when we get set S by running DFS on the bipartite graph B we have about S/2 vertices from V and S/2 elements from M, and every vertex (resp. element) has n−S/2 elements (resp. vertices) to be paired. Note that xn−x/2 is an increasing function when x∈pt−ϵ2n/4,n. This means that(14)t≥S2n−S2×2≥pt−ϵ2n4n−pt2+ϵ2n8=1+ϵt−1+ϵ2t22n2+1+ϵϵ2t4−ϵ2n24−ϵ4n232≥t+4ϵ2n25−1+ϵ2ϵ2n22+1+ϵϵ3n25−ϵ2n24−ϵ4n232=t+ϵ2n21120−1+ϵ22+o1>t.
It is a contradiction!Now, we proceed on the proof of the lower bound. The Claim and Lemma3 imply that w.h.p. the number of κi=1 between 4ϵn2/5 and ϵn2 is at least(15)pϵn2−ϵ2n4−p4ϵn25+ϵ2n4=15+o1ϵn.That is, all the number of vertices added toU in the interval 4ϵn2/5,ϵn2 is at least 1/5+o1ϵn. Obviously, these vertices are in the same component. Therefore, C1ℬn,n,p=Ωϵn.


### 2.2. Lower Bound in the Weakly Subcritical Regime

Before beginning to prove the lower bound, we need a lemma borrowed from [25].Lemma 5 (see Lemma 3.1 in [25]).
Letχi be a sequence of random variables with the binomial distribution Bink,p, where p=1−ϵ/k. Define a process Wtt≥0 as Wt=Wt−1+χt−1 with W0=1. Set(16)τ:=mint:Wt=0.Then there exist two positive constantsc1,c2 such that, for all T0≥ϵ−2,(17)Pτ≥T0≥c1ϵ−2T0−3/2e−ϵ2+c2ϵ3T0/2.Proof.
of the Lower Bound in the Weakly Subcritical Case. Our proof follows the line in [25]. We analyzed the exploration process defined at the beginning of this section. Recall that Xt is the number of vertices which become active due to the exploration of active vertex vt, and Yt is the total number of active vertices at step t∈0,1,…,n. For the exploration process Ytt≥0, let t1<t2<⋯ be the times at which Yt=0. Then t1,t2−t1,…,ti−ti−1,… are the sizes of the components in ℬn,n,p. It is easy to see that the total neutral vertices at time t are(18)Nt=n−t−Yt.
For small enoughδ∈0,1, define a stopping time Λ with respect to Nt as(19)Λ≔mint:Nt≤n−δϵn.
SetLt≔Yt−Zt, where Zt≔∑i=1t−11Yt=0. We can see that Zt counts the number of components completely explored by the process before time t. For any integer j, let Wtj be a process with increments distributed as Binn−δϵn,p, and its starting point W0j=Ltj=−j−1. Let(20)τj≔mint:Wtj=−j.
Choose a constantδ1<21−δ/δ+22, and take(21)T0=δ1ϵ−2lognϵ3,N=ϵ−1nϵ31−δ.
First, we shall show that w.h.p. the two following eventsA1 and A2 hold:(22)A1≔tN≤Λ;A2≔there existsk1<Nsuch thatτk1>T0.
Note thatA1∩A2⊂C1ℬn,n,p>T0, where C1ℬn,n,p is the size of largest component in ℬn,n,p. In fact, let αii=1t be a sequence of the i.i.d. random variables distributed as Binn,p. It is easy to get that Xi≺¯αi for all i. Hence by (3) and (19) we have Nt≥n−1−t−∑i=1tαi. Meanwhile ∑i=1tαi∼Binnt,p and E∑i=1tαi=1+ϵt<2t. By the Chernoff bounds (refer to Theorem A.1.4 in [19]), there exists a constant c>0 such that(23)P∑i=1tαi>3t≤e−ct,which means PNt≥n−4t with probability at least 1−e−ct leading to PNt≤n−5t≤e−ct. Therefore,(24)PΛ≤δϵn5≤e−cϵn.
Define(25)Wt′=Wt−1′+αi−1=∑i=1tαi−1,with W0′=1; and let τ′≔mint:Wt′=0. Then, by Wald’s equation (refer to Theorem 4.1.5 in [26]), we have Eτ′=ϵ−1. Recall that when t<τ≔mint:Yt=0,Yt=∑i=1tXi−1 by [3]. Hence, Eti+1−ti≤ϵ−1 which means(26)EtN≤Nϵ−1≤ϵ−2nϵ31−δ.
Therefore, by Markov’s inequality,(27)PtN>δϵn5≤5EtNδϵn≤5ϵ−2nϵ31−δδϵn=5nϵ3−δδ⟶0,which implies w.h.p. A1 holds. As for A2, when k=n−δϵn, p=1−ϵk/k=1−ϵn−δϵn/n1−δϵ≥1−δ+2ϵ/n; Lemma 5 indicates that, for any j,(28)Pτj>T0≥c1′ϵlognϵ3−3/2nϵ3−δ1δ+22/2,where c1′=c1′c1,δ. Set pT0=Pτj>T0. Let ζ≔∑i=1Nζi, where ζi=1ifτi>T0; otherwise, ζi=0. Then Eζ=NpT0 and Varζ=NpT01−pT0. Hence, by the Second Moment Method (refer to [[19], Theorem 4.3.1]) and Lemma 5,(29)Pζ=0≤VarζEζ2≤1NpT0≤1c1′lognϵ3−3/2nϵ31−δ−δ1δ+22/2⟶0.
AsA1∩A2⊂C1ℬn,n,p>T0,(30)C1ℬn,n,p≤T0⊆A1¯∪A2¯=tN>Λ∪ζ=0,which indicates(31)PC1ℬn,n,p≤T0≤PtN>Λ+Pζ=0=o1.


## 2.1. Lower Bound in the Weakly Supercritical Regime

Breadth First Search (BFS) and Depth First Search (DFS) are two well-known algorithms in the graph exploration. They are widely used to study the structure of (random) graphs. The DFS has been utilized to investigate random graphs by some scholars such as Ben-Eliezer et al. [20], Krivelevich and Sudakov [21], Joseph [22], and Cooley et al. [23]. In this section, we applied the DFS to the bipartite graph B∈ℬn,n,p to obtain the lower bound according to the ideas in [21,23] which are used to study the largest component in the Erdös-Rényi random graph and the random hypergraph, respectively. Before starting to prove the lower bound, we need a lemma about a sequence of i.i.d. Bernoulli random variables with parameter p.Lemma 3.
Letκii=1n2 be the i.i.d. Bernoulli random variables with parameter p=1+ϵ/n, where ϵ is a positive function on n such that ϵ⟶0 and ϵn1/3⟶∞ as n⟶∞. Then, for any t∈a1ϵn2,a2ϵn2, where ais are positive constants independently of n, i=1,2, w.h.p. we have(9)∑i=1tκi−pt≤ϵ2n4.The following auxiliary lemma is needed to prove Lemma3.Lemma 4 (see Lemma 7 in [24] and Lemma 9 in [23]).
LetZii=1ℓ be a martingale with Z0=0. If there are two positive constants b1 and b2 with b1<b2/10 such that −b1≤Zi−Zi−1≤b2 for any i∈1,ℓ, then, for any 0<C<b1ℓ,(10)PZℓ≥C≤2exp−C23b1b2ℓ.Proof of Lemma 3.
For anyt∈a1ϵn2,a2ϵn2, define Λ0=0, and(11)Λt+1=Λt+κt+1−p,ifΛt≤ϵ2n4,Λt,otherwise.
It is easy to verify that it indeed is a martingale with the stopping timemint:Λt>ε2n/4; and −p≤Λt+1−Λt≤1−p<1. By Lemma 4, we have(12)P∑i=1tκi−pt≥ϵ2n4≤2exp−ϵ2n248pa2ϵn2=2exp−nϵ348a21+ϵ=o1.Now we prove the lower bound ofC1ℬn,n,p.Proof.
We choose a graphB from ℬn,n,p uniformly. Write B=V,M,E, where E is the edge set. Let σV be a linear ordering of V and let σM be a linear ordering of M. In the exploration process, let S be the set of vertices that have been explored; let T be the set of unvisited vertices, and U=V∪M\S∪T in which the vertices of U are put in a stack. We run the following DFS algorithm on B to obtain components (recall that both the vertices and the elements are called vertices in this section). See Algorithm 1.
Consider a sequenceκii=1n2 of the i.i.d. Bernoulli random variables with parameter p which is the sequence of edges in B∈ℬn,n,p. That is, κi is the result of the i-th queried edge. If the queried edge is in B, then κi=1; otherwise κi=0. We have the following claim.Algorithm 1:  DFS on bipartite graph B∈ℬn,n,p starting from a vertex in V.
Input:B=V,M,E, σV–a linear ordering of V, σM– a linear ordering of M.Output:C-set of components of B.C≔∅; The stackU≔∅;repeatLetv0 be the smallest neutral vertex in V according to σV;Makev0 as active, and add v0 to UWheneverU≠∅ doLetx be the top vertices of U. Scanning T.Ifx∈V and there exists the smallest element u according to σMsuch thatxu∈E then delete x from T and put it into U.Otherwise, then takex out of U and put it into S.Ifx∈M and there exists the smallest vertex v according to σVsuch thatxv∈E then delete x from T and put it into U.Otherwise, then takex out of U and put it into S.LetC be the set of vertices explored in the while-loop above;C≔C∪CUntil all vertices are explored.Claim 1.
Between the query4ϵn2/5 and the query ϵn2 w.h.p. the stack U is not empty.Proof.
of Claim. First, we can assume that S<n. In fact, if S≥n, let us consider the time that S=n. By Lemma 3, U<2a2ϵn, which means T=2n−S−U>n−2a2ϵn. Since B is a bipartite graph, when we run the DFS on B, both S and T have half vertices in V and M. Hence, between S and T, at time t the DFS has made queries at least(13)2×S2−1×T2−1≥2n2−1n−2a2ϵn2−1>n24≫ϵn2≥t.
It is a contradiction. Secondly, by Lemma3, we have that, at any time t∈4ϵn2/5,ϵn2, S∪U≥pt−ϵ2n/4. Suppose that stack U is empty which means there are only explored vertices and neutral vertex after some t queries for t∈4ϵn2/5,ϵn2; then S≥pt−ϵ2n/4. Therefore, if stack U is empty, we can assume S∈pt−ϵ2n/4,n. Meanwhile, at time t, the number of edges that have been queried is w.h.p. at least S/2n−S/2×2, which comes from the fact that when we get set S by running DFS on the bipartite graph B we have about S/2 vertices from V and S/2 elements from M, and every vertex (resp. element) has n−S/2 elements (resp. vertices) to be paired. Note that xn−x/2 is an increasing function when x∈pt−ϵ2n/4,n. This means that(14)t≥S2n−S2×2≥pt−ϵ2n4n−pt2+ϵ2n8=1+ϵt−1+ϵ2t22n2+1+ϵϵ2t4−ϵ2n24−ϵ4n232≥t+4ϵ2n25−1+ϵ2ϵ2n22+1+ϵϵ3n25−ϵ2n24−ϵ4n232=t+ϵ2n21120−1+ϵ22+o1>t.
It is a contradiction!Now, we proceed on the proof of the lower bound. The Claim and Lemma3 imply that w.h.p. the number of κi=1 between 4ϵn2/5 and ϵn2 is at least(15)pϵn2−ϵ2n4−p4ϵn25+ϵ2n4=15+o1ϵn.That is, all the number of vertices added toU in the interval 4ϵn2/5,ϵn2 is at least 1/5+o1ϵn. Obviously, these vertices are in the same component. Therefore, C1ℬn,n,p=Ωϵn.


## 2.2. Lower Bound in the Weakly Subcritical Regime

Before beginning to prove the lower bound, we need a lemma borrowed from [25].Lemma 5 (see Lemma 3.1 in [25]).
Letχi be a sequence of random variables with the binomial distribution Bink,p, where p=1−ϵ/k. Define a process Wtt≥0 as Wt=Wt−1+χt−1 with W0=1. Set(16)τ:=mint:Wt=0.Then there exist two positive constantsc1,c2 such that, for all T0≥ϵ−2,(17)Pτ≥T0≥c1ϵ−2T0−3/2e−ϵ2+c2ϵ3T0/2.Proof.
of the Lower Bound in the Weakly Subcritical Case. Our proof follows the line in [25]. We analyzed the exploration process defined at the beginning of this section. Recall that Xt is the number of vertices which become active due to the exploration of active vertex vt, and Yt is the total number of active vertices at step t∈0,1,…,n. For the exploration process Ytt≥0, let t1<t2<⋯ be the times at which Yt=0. Then t1,t2−t1,…,ti−ti−1,… are the sizes of the components in ℬn,n,p. It is easy to see that the total neutral vertices at time t are(18)Nt=n−t−Yt.
For small enoughδ∈0,1, define a stopping time Λ with respect to Nt as(19)Λ≔mint:Nt≤n−δϵn.
SetLt≔Yt−Zt, where Zt≔∑i=1t−11Yt=0. We can see that Zt counts the number of components completely explored by the process before time t. For any integer j, let Wtj be a process with increments distributed as Binn−δϵn,p, and its starting point W0j=Ltj=−j−1. Let(20)τj≔mint:Wtj=−j.
Choose a constantδ1<21−δ/δ+22, and take(21)T0=δ1ϵ−2lognϵ3,N=ϵ−1nϵ31−δ.
First, we shall show that w.h.p. the two following eventsA1 and A2 hold:(22)A1≔tN≤Λ;A2≔there existsk1<Nsuch thatτk1>T0.
Note thatA1∩A2⊂C1ℬn,n,p>T0, where C1ℬn,n,p is the size of largest component in ℬn,n,p. In fact, let αii=1t be a sequence of the i.i.d. random variables distributed as Binn,p. It is easy to get that Xi≺¯αi for all i. Hence by (3) and (19) we have Nt≥n−1−t−∑i=1tαi. Meanwhile ∑i=1tαi∼Binnt,p and E∑i=1tαi=1+ϵt<2t. By the Chernoff bounds (refer to Theorem A.1.4 in [19]), there exists a constant c>0 such that(23)P∑i=1tαi>3t≤e−ct,which means PNt≥n−4t with probability at least 1−e−ct leading to PNt≤n−5t≤e−ct. Therefore,(24)PΛ≤δϵn5≤e−cϵn.
Define(25)Wt′=Wt−1′+αi−1=∑i=1tαi−1,with W0′=1; and let τ′≔mint:Wt′=0. Then, by Wald’s equation (refer to Theorem 4.1.5 in [26]), we have Eτ′=ϵ−1. Recall that when t<τ≔mint:Yt=0,Yt=∑i=1tXi−1 by [3]. Hence, Eti+1−ti≤ϵ−1 which means(26)EtN≤Nϵ−1≤ϵ−2nϵ31−δ.
Therefore, by Markov’s inequality,(27)PtN>δϵn5≤5EtNδϵn≤5ϵ−2nϵ31−δδϵn=5nϵ3−δδ⟶0,which implies w.h.p. A1 holds. As for A2, when k=n−δϵn, p=1−ϵk/k=1−ϵn−δϵn/n1−δϵ≥1−δ+2ϵ/n; Lemma 5 indicates that, for any j,(28)Pτj>T0≥c1′ϵlognϵ3−3/2nϵ3−δ1δ+22/2,where c1′=c1′c1,δ. Set pT0=Pτj>T0. Let ζ≔∑i=1Nζi, where ζi=1ifτi>T0; otherwise, ζi=0. Then Eζ=NpT0 and Varζ=NpT01−pT0. Hence, by the Second Moment Method (refer to [[19], Theorem 4.3.1]) and Lemma 5,(29)Pζ=0≤VarζEζ2≤1NpT0≤1c1′lognϵ3−3/2nϵ31−δ−δ1δ+22/2⟶0.
AsA1∩A2⊂C1ℬn,n,p>T0,(30)C1ℬn,n,p≤T0⊆A1¯∪A2¯=tN>Λ∪ζ=0,which indicates(31)PC1ℬn,n,p≤T0≤PtN>Λ+Pζ=0=o1.


## 3. The Upper Bound

In this section, we distinguish the vertices and the elements ofℬn,m,p, not like what we do in Section 2. We will make use of the following exploration process on ℬn,m,p. This process is a little different from the exploration process Ytt≥0.For exploration processYt∗t≥0 ([14]), let Cv be the component containing vertex v in Gn,m,p. In this process, we only care about the vertices from V in ℬn,m,p. So the vertices will be active, inactive, or neutral, but all the elements in M will always be neutral. At the beginning, assuming all the vertices are neutral, we uniformly choose a vertex v0∈V and make it active. At each time t≥1, we uniformly choose a vertex vt from the active vertices and check all pairs vtu where u runs over all the neutral elements in M. If vtu is an edge in ℬn,m,p, then check uv where v runs over all the neutral vertices. If vtu and uv for some element u, both are present in ℬn,m,p and then make v active; otherwise, keep it neutral. After checking all the neutral vertices, let vt be inactive. When there is no active vertex, component Cv0 is explored. Then, we choose a neutral vertex uniformly from the rest of the neutral ones in V and proceed on.LetXt∗ be the number of vertices which become active due to the exploration of vertex vt. Note that Xt∗ is the number of vertices at distance 2 from vt in ℬn,m,p. Denote by Yt∗ the total number of active vertices at step t, where Y0∗=1. It is easy to see that, for any t≥1,(32)Yt∗=Yt−1∗+Xt∗−1,ifYt−1∗>0,Xt∗,ifYt−1∗=0.Define(33)T∗=mint:Yt∗=0=mint:X1∗+X2∗+⋯+Xt∗=t−1.At timeT∗, the set of explored vertices is precisely Cv0, which means Cv0=T∗.The following auxiliary contents would be used in the proof:(i)
LetX˜∗ be a random variable with compound binomial distribution CBn,m,p which has probability generating function(34)fX˜∗x=ExX˜∗=1−p+p1−p+pxnm.Lemma 6 (see Lemma 2 in [14]).
LetX˜i∗ be a random variable distributed as CBni,m,p, i=1,2. If n1≤n2, then X˜1∗≺¯X˜2∗.(ii)
For small enoughx>0,(35)1−nx+n2x22−n3x3<1−xn<1−nx+n2x22,(36)ex<1+x+x2,(37)1+xk<1+kx+2k2x23.


### 3.1. Upper Bound in the Weakly Supercritical Regime

The branching process method is widely used to show the upper bound of the size of largest component in random graphs; see [27,28] and references therein. In this section, we applied the branching process argument [29] to obtain the upper bound in the weakly supercritical regime. Kang et al. [30] and Wang and Zou [14] used this technique to get the upper bound of the size of largest component in the corresponding random graphs.Outline of the proof is as follows: given a vertexv of Gn,m,p, let Cv denote the component of Gn,m,p containing v; and let Tv be the random spanning tree rooted at v which is obtained by exploring new neighbors in Cv via the exploration process Yt∗t≥0. Let ℬP be the branching process whose offspring distribution is CBn,m,p. This process can be interpreted as a potentially infinite random rooted tree. Suppose that there are ℓ active vertices and k explored vertices at the time step t in the exploration process on ℬn,m,p. We can see that the number of newly explored vertices Xt∗ through the current vertex, say vi, has the distribution CBn−k−ℓ,m,p. Therefore, by Lemma 6, Xt∗≺¯ξt, where ξt is distributed as CBn,m,p, which means the random rooted trees Tv and ℬP can be coupled so that Tv⊆ℬP. Hence, Cv=Tv≤ℬP, where ℬP is the size of total offspring in ℬP. Therefore, we only need to give the upper bound of ℬP.Before we state some properties about the processℬP, recall Theorem 2.Theorem 2 (see Theorem 3.7 in [28]).
LetℬP be the Galton–Watson branching process with supercritical offspring distribution pkk≥0. Here “supercritical” means ∑k≥0kpk>1. Suppose that p0∈0,1, and let η∗ be the extinction probability of ℬP. Define(38)qk≔pkη∗k−1,k≥0.Then(39)∑k≥0qk=1and∑k≥0kqk=∑k≥0kpkη∗k−1<1.Henceqkk≥0 is an offspring distribution of a subcritical branching process which is often called the dual process of ℬP. 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=T|ℬPis extincted=PTq=T.Now we can get Lemma7.Lemma 7.
LetℬP be a branching process with offspring distribution CBn,m,p, let ℬP be its total size, and let ρ∗ be its surviving probability, where m,n,p satisfy the conditions in Theorem 1. Denote its dual process by ℬP∗ and the total size of ℬP∗ by ℬP∗. Then(1)
ρ∗=2+o1ϵ/1+γ(2)
EℬP∗≤2/ϵ(3)
For any integerL=Ln, PℬP≥L≤1+o12ϵ/1+γ+2/ϵLProof.
(1)
Theorem 1.6.1 in [31] states that, for the Galton–Watson branching process with offspring distribution Fx, the surviving probability ρ∗ is the minimal solution in 0,1 to the equation 1−ρ=fF1−ρ. Here fFx=ExZ,Zdistribited asFx. Hence, we will prove that, for the process ℬP with offspring distribution CBn,m,p, there is aρ∗∈2ϵ/1+γ+3+γϵ,2ϵ/1+γ−10γ+10ϵsuch thatgρ∗=0, where(41)gρ=ρ−1+fCB1−ρ,fCB=ExX∗,X∗ditributed asCBn,m,p.In fact,gρ is continuous on 2ϵ/χ1,2ϵ/χ2, where(42)χ1≔1+γ+3+γϵ,χ2≔1+γ1−10ϵ.By inequality (35), we have(43)g2ϵχ1=1−p+p1−2pϵχ1nm+2ϵχ1−1≤351−p+p1−2npϵχ1+2n2p2ϵ2χ12m+2ϵχ1−1=1−2np2ϵχ1+2n2p3ϵ2χ12m+2ϵχ1−1≤351−2mnp2ϵχ1+2mn2p3ϵ2χ12+2m2n2p4ϵ2χ121−npϵχ12+2ϵχ1−1≤2ϵχ1−2mnp2ϵχ1+2mn2p3ϵ2χ12+2n2m2p4ϵ2χ12=−2ϵ31−ϵχ12<0;g2ϵχ2=1−p+p1−2pϵχ2nm+2ϵχ2−1≥351−p+p1−2npϵχ2+2n2p2ϵ2χ22−8n3p3ϵ3χ23m+2ϵχ2−1=1−2np2ϵχ2+2n2p3ϵ2χ22−8n3p4ϵ3χ23m+2ϵχ2−1≥351−2mnp2ϵχ2+2mn2p3ϵ2χ22−8mn3p4ϵ3χ23+2ϵχ2−1+m222np2ϵχ2−2n2p3ϵ2χ22+8n3p4ϵ3χ232−m32np2ϵχ2−2n2p3ϵ2χ22+8n3p4ϵ3χ233=−2ϵ2χ2+2ϵ21+ϵγχ22+2ϵ21+ϵ2χ221−γϵχ2+4γ2ϵ2χ222−8ϵ31+ϵ3χ231−γϵχ2+4γ2ϵ2χ223−8ϵ31+ϵγ2χ23=−2ϵ21−11γ+10ϵχ22+2ϵ21+ϵ2χ221−γϵχ2+4γ2ϵ2χ222−8ϵ31+ϵχ23γ2+1+ϵ21−γϵχ2+4γ2ϵ2χ223≥−2ϵ21−11γ+10ϵχ22+2ϵ21+ϵ2χ221−γϵχ22−8ϵ31+ϵχ23γ2+1+ϵ2≥−2ϵ21−11γ+10ϵχ22+2ϵ2χ221−γϵχ22−8ϵ31+ϵχ23γ2+1+ϵ2≥2ϵ3χ2211γ+10−2γχ2−8ϵ31+ϵχ23γ2+1+ϵ2=2ϵ3χ2311γ+10χ2−2γ−4γ2+1+ϵ21+ϵ>0.Hence, the claim holds by the Intermediate Value Theorem.(2)
LetD∗ be the number of children for each vertex in the dual processes ℬP∗.(44)ED∗=∑k≥0kqk=∑k≥0kpkη∗k−1=fCB′η∗=nmp21−p+p1−pρ∗nm−11−pρ∗n−1≤35nmp21−p+p1−npρ∗+n2p2ρ∗22m−11−n−1pρ∗+n−12p2ρ∗22≤35nmp21−m−1np2ρ∗+m−1n2p3ρ∗22+m−12n2p4ρ∗22×1−n−1pρ∗+n−12p2ρ∗22≤1+ϵ1−2ϵ1+γ+Oϵ21−2γϵ1+γ+Oϵ2=1−ϵ+Oϵ2.Therefore,(45)EBPF∗=1+ED∗+ED∗2+ED∗3+⋯=4311−ED∗≤2ϵ.(3)
Denote the event thatℬP survives by S and the event that it dies out by Sc(46)PℬP≥L=PSPℬP≥L|S+PScPℬP≥L|Sc=PS+PScPℬP∗≥L≤2+o1ϵ1+γ+EℬP∗L≤1+o12ϵ1+γ+2ϵL.LetSL be the set of all vertices in the components that contain at least L vertices, and let sL be the cardinality of this set. We have the following.Lemma 8.
LetL=Ln be a real function satisfying ϵ2L⟶∞.(47)EsL≤2+o1ϵn1+γ.Proof.
By Lemma7,(48)EsL=∑v∈VPCv≥L=nPCv≥L≤nPℬP≥L≤n1+o12ϵ1+γ+2ϵL=2+o1ϵn1+γ.In the next lemma, we prove the size of large components is concentrated around its expectation.Lemma 9.
Suppose thatL=Ln satisfies ϵ2L⟶∞ and L=oϵn. Then w.h.p. sL=2+o1ϵ/1+γ.The proof of Lemma9 follows the part of the proof of Lemma 7 in [14] verbatim except that some constants need to be changed. We omit it here.Proof.
of Upper Bound in Weakly Supercritical Case in Theorem 1. Let ωn=ϵn1/3 and L=ϵn/logωn. Then the upper bound of (1) in Theorem 1 is obtained from Lemma 9.


### 3.2. Upper Bound in the Weakly Subcritical Regime

Outline of the proof is as follows: We first use exploration processYt∗t≥0 to explore the components of ℬn,m,p. Then, for the upper bound of C1, we only need to give the upper bound on the stop time T∗ as Cv0=T∗. For this, we follow the ideas in [[32], Proposition 1]. Recall Lemma 10.Lemma 10 (see Lemma 8 in [32]).
Letη be an integer-valued random variable with Eη2<∞ such that, for any integer h≥2, Pη∈hℤ<1. Let ηii=1∞ be a sequence of the i.i.d. random variables distributed as η and(49)Wt=W0+∑i=1tηi,t∈0,1,2,…,,where W0 is an integer constant. Define τ≔mint:Wt=0. If θ0>0 and it satisfies Eηeθ0η=0, then, for any integer ℓ≥1,(50)Pτ=ℓ=Θℓ−3/2ϕθ0ℓ,where ϕθ=Eeθη and the constants in Θ depend only on η and W0 but not ℓ.Proof.
of Upper Bound in Weakly Subcritical Case in Theorem 1. To utilize Lemma 10, set(51)St=1+∑i=1tξi−1,where ξtt=1∞ is a sequence of the i.i.d. random variables distributed as CBn,m,p. Take ς=ξ1−1 for brevity. Note that ς takes values in −1,0,1,…,n−1. Write(52)Pς=i=pifori∈−1,0,1,…,n−1.When m=βn, p=γ/n, and βγ2=1−ϵ, where ϵ⟶0 and n1/3ϵ⟶∞ as n⟶∞,(53)Eς=Eξi−1=fX∗′1−1=−ϵ,(54)Eς2=fX∗21−fX∗′1=1−ϵ1+γ+ϵ21+o1,(55)Eς3=fX∗31+fX∗′1−1=γ2+3γ+1−γ2+3γ+3ϵ+ϵ21+o1.
Setan=ϵ/1+γ1−ϵ+γ2+3γ+2ϵ and bn=ϵ/1+γ1−ϵ−2ϵ. Define Fθ=Eςeθςforθ∈an,bn. In the following, we check that there is θ0 such that(56)an<θ0<bn,Fθ0=Eςeθ0ς=0.
Note that, for any natural numberi and x∈0,∞, eix−e−x>i+1x; and (53) implies p−1=ϵ+∑i=1n−1ipi. We can obtain(57)Eςebnς=−e−bnp−1+ebnp1+2e2bnp2+⋯+n−1en−1bnpn−1=53e−bn−ϵ−∑i=1n−1ipi+∑i=1n−1ieibnpi=−ϵe−bn+∑i=1n−1ipieibn−e−bn≥−ϵe−bn+bn∑i=1n−1ii+1pi≥−ϵ1−bn+b2n+bnEς2+Eς=−ϵ+bn1+γ1−ϵ−ϵ+oϵ>0.
by (53)–(55), we can obtain(58)Eςeanς=∑i=−1n−1eaniipi≤36∑i=−1n−11+an+a2niipi≤37∑i=−1n−11+ian+ia2n+2i2a2n31+an2ipi=∑i=−1n−1kpk+an∑i=−1n−1i2pi+2a2n1+an23∑i=−1n−1i3pi≤Eς+anEς2+a2nEς3≤−ϵ+ϵ1+γ1−ϵ+oϵ1+γ1−ϵ+γ2+3γ+2ϵ+ϵ2γ2+3γ+11+γ1−ϵ+γ2+3γ+2ϵ2≤−γ2+3γ+2ϵ2+oϵ21+γ1−ϵ+γ2+3γ+2ϵ+ϵ2γ2+3γ+11+γ1−ϵ+γ2+3γ+2ϵ2<0.
Third, it is obvious thatFθ is continuous on an,bn. Hence, together with (57) and (58), this implies (56) holds by the Intermediate Value Theorem.
Now we estimateEeθ0ς. By (53) and (54), we can deduce that(59)Eeθ0ς=∑k=−1n−1eθ0kpk≤36∑k=−1n−11+θ0+θ02kpk≤37∑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−ϵ2n31+γ+oϵ2.
Suppose that there areℓ active vertices and k explored vertices have been explored at the time step t in the exploration process on ℬn,m,p. We can see that the number of newly explored vertices Xt∗ through the current vertex, say v, has the distribution CBn−k−ℓ,m,p. Therefore, by Lemma 6, Xt∗≺¯ξt, where ξt is distributed as CBn,m,p. That is to say, for all k≤minT∗,n,(60)∑i=1kXi∗≺¯∑i=1kξi,where T∗=mint:Yt∗=0. Let Ctv0 denote total explored vertices which are explored from time 0 to t by the exploration process on ℬn,m,p starting from vertex v0. Define τS=mint:St=0,t≤n. Note that(61)Ctv0=1+∑i=1tXi∗−1andSt=1+∑i=1tξi−1.
This meansCtv0≺¯St implying T∗≺¯τS. Therefore, by Lemma 10,(62)PCv0≥M0=PT∗≥M0≤PτS≥M0=∑ℓ≥M0PτS=ℓ=∑ℓ≥M0Oℓ−3/21−ϵ231+γ+oϵ2ℓ.
SetM0=41+γϵ−2nlognϵ3n. By the inequality 1−x≤e−x, for x≥0,(63)PτS≥M0=OM0−3/2∑ℓ≥M01−ϵ231+γ+oϵ2ℓ=Oϵ−2M0−3/21−ϵ231+γ+oϵ2M0=Oϵ−2M0−3/2exp−M0ϵ231+γ+oM0ϵ2=Oϵlognϵ3−3/2nϵ3−4/3+o1.
DenoteZ≥k=∑v∈V1Cv≥k.(64)PC1≥M0=PZ≥M0≥M0≤EZ≥M0M0=∑v∈VE1|Cv|≥M0M0=nPCv0≥M0M0≤nPτS≥M0M0=Onϵ3−1/3−o1lognϵ3−5/2=o1.


## 3.1. Upper Bound in the Weakly Supercritical Regime

The branching process method is widely used to show the upper bound of the size of largest component in random graphs; see [27,28] and references therein. In this section, we applied the branching process argument [29] to obtain the upper bound in the weakly supercritical regime. Kang et al. [30] and Wang and Zou [14] used this technique to get the upper bound of the size of largest component in the corresponding random graphs.Outline of the proof is as follows: given a vertexv of Gn,m,p, let Cv denote the component of Gn,m,p containing v; and let Tv be the random spanning tree rooted at v which is obtained by exploring new neighbors in Cv via the exploration process Yt∗t≥0. Let ℬP be the branching process whose offspring distribution is CBn,m,p. This process can be interpreted as a potentially infinite random rooted tree. Suppose that there are ℓ active vertices and k explored vertices at the time step t in the exploration process on ℬn,m,p. We can see that the number of newly explored vertices Xt∗ through the current vertex, say vi, has the distribution CBn−k−ℓ,m,p. Therefore, by Lemma 6, Xt∗≺¯ξt, where ξt is distributed as CBn,m,p, which means the random rooted trees Tv and ℬP can be coupled so that Tv⊆ℬP. Hence, Cv=Tv≤ℬP, where ℬP is the size of total offspring in ℬP. Therefore, we only need to give the upper bound of ℬP.Before we state some properties about the processℬP, recall Theorem 2.Theorem 2 (see Theorem 3.7 in [28]).
LetℬP be the Galton–Watson branching process with supercritical offspring distribution pkk≥0. Here “supercritical” means ∑k≥0kpk>1. Suppose that p0∈0,1, and let η∗ be the extinction probability of ℬP. Define(38)qk≔pkη∗k−1,k≥0.Then(39)∑k≥0qk=1and∑k≥0kqk=∑k≥0kpkη∗k−1<1.Henceqkk≥0 is an offspring distribution of a subcritical branching process which is often called the dual process of ℬP. 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=T|ℬPis extincted=PTq=T.Now we can get Lemma7.Lemma 7.
LetℬP be a branching process with offspring distribution CBn,m,p, let ℬP be its total size, and let ρ∗ be its surviving probability, where m,n,p satisfy the conditions in Theorem 1. Denote its dual process by ℬP∗ and the total size of ℬP∗ by ℬP∗. Then(1)
ρ∗=2+o1ϵ/1+γ(2)
EℬP∗≤2/ϵ(3)
For any integerL=Ln, PℬP≥L≤1+o12ϵ/1+γ+2/ϵLProof.
(1)
Theorem 1.6.1 in [31] states that, for the Galton–Watson branching process with offspring distribution Fx, the surviving probability ρ∗ is the minimal solution in 0,1 to the equation 1−ρ=fF1−ρ. Here fFx=ExZ,Zdistribited asFx. Hence, we will prove that, for the process ℬP with offspring distribution CBn,m,p, there is aρ∗∈2ϵ/1+γ+3+γϵ,2ϵ/1+γ−10γ+10ϵsuch thatgρ∗=0, where(41)gρ=ρ−1+fCB1−ρ,fCB=ExX∗,X∗ditributed asCBn,m,p.In fact,gρ is continuous on 2ϵ/χ1,2ϵ/χ2, where(42)χ1≔1+γ+3+γϵ,χ2≔1+γ1−10ϵ.By inequality (35), we have(43)g2ϵχ1=1−p+p1−2pϵχ1nm+2ϵχ1−1≤351−p+p1−2npϵχ1+2n2p2ϵ2χ12m+2ϵχ1−1=1−2np2ϵχ1+2n2p3ϵ2χ12m+2ϵχ1−1≤351−2mnp2ϵχ1+2mn2p3ϵ2χ12+2m2n2p4ϵ2χ121−npϵχ12+2ϵχ1−1≤2ϵχ1−2mnp2ϵχ1+2mn2p3ϵ2χ12+2n2m2p4ϵ2χ12=−2ϵ31−ϵχ12<0;g2ϵχ2=1−p+p1−2pϵχ2nm+2ϵχ2−1≥351−p+p1−2npϵχ2+2n2p2ϵ2χ22−8n3p3ϵ3χ23m+2ϵχ2−1=1−2np2ϵχ2+2n2p3ϵ2χ22−8n3p4ϵ3χ23m+2ϵχ2−1≥351−2mnp2ϵχ2+2mn2p3ϵ2χ22−8mn3p4ϵ3χ23+2ϵχ2−1+m222np2ϵχ2−2n2p3ϵ2χ22+8n3p4ϵ3χ232−m32np2ϵχ2−2n2p3ϵ2χ22+8n3p4ϵ3χ233=−2ϵ2χ2+2ϵ21+ϵγχ22+2ϵ21+ϵ2χ221−γϵχ2+4γ2ϵ2χ222−8ϵ31+ϵ3χ231−γϵχ2+4γ2ϵ2χ223−8ϵ31+ϵγ2χ23=−2ϵ21−11γ+10ϵχ22+2ϵ21+ϵ2χ221−γϵχ2+4γ2ϵ2χ222−8ϵ31+ϵχ23γ2+1+ϵ21−γϵχ2+4γ2ϵ2χ223≥−2ϵ21−11γ+10ϵχ22+2ϵ21+ϵ2χ221−γϵχ22−8ϵ31+ϵχ23γ2+1+ϵ2≥−2ϵ21−11γ+10ϵχ22+2ϵ2χ221−γϵχ22−8ϵ31+ϵχ23γ2+1+ϵ2≥2ϵ3χ2211γ+10−2γχ2−8ϵ31+ϵχ23γ2+1+ϵ2=2ϵ3χ2311γ+10χ2−2γ−4γ2+1+ϵ21+ϵ>0.Hence, the claim holds by the Intermediate Value Theorem.(2)
LetD∗ be the number of children for each vertex in the dual processes ℬP∗.(44)ED∗=∑k≥0kqk=∑k≥0kpkη∗k−1=fCB′η∗=nmp21−p+p1−pρ∗nm−11−pρ∗n−1≤35nmp21−p+p1−npρ∗+n2p2ρ∗22m−11−n−1pρ∗+n−12p2ρ∗22≤35nmp21−m−1np2ρ∗+m−1n2p3ρ∗22+m−12n2p4ρ∗22×1−n−1pρ∗+n−12p2ρ∗22≤1+ϵ1−2ϵ1+γ+Oϵ21−2γϵ1+γ+Oϵ2=1−ϵ+Oϵ2.Therefore,(45)EBPF∗=1+ED∗+ED∗2+ED∗3+⋯=4311−ED∗≤2ϵ.(3)
Denote the event thatℬP survives by S and the event that it dies out by Sc(46)PℬP≥L=PSPℬP≥L|S+PScPℬP≥L|Sc=PS+PScPℬP∗≥L≤2+o1ϵ1+γ+EℬP∗L≤1+o12ϵ1+γ+2ϵL.LetSL be the set of all vertices in the components that contain at least L vertices, and let sL be the cardinality of this set. We have the following.Lemma 8.
LetL=Ln be a real function satisfying ϵ2L⟶∞.(47)EsL≤2+o1ϵn1+γ.Proof.
By Lemma7,(48)EsL=∑v∈VPCv≥L=nPCv≥L≤nPℬP≥L≤n1+o12ϵ1+γ+2ϵL=2+o1ϵn1+γ.In the next lemma, we prove the size of large components is concentrated around its expectation.Lemma 9.
Suppose thatL=Ln satisfies ϵ2L⟶∞ and L=oϵn. Then w.h.p. sL=2+o1ϵ/1+γ.The proof of Lemma9 follows the part of the proof of Lemma 7 in [14] verbatim except that some constants need to be changed. We omit it here.Proof.
of Upper Bound in Weakly Supercritical Case in Theorem 1. Let ωn=ϵn1/3 and L=ϵn/logωn. Then the upper bound of (1) in Theorem 1 is obtained from Lemma 9.


## 3.2. Upper Bound in the Weakly Subcritical Regime

Outline of the proof is as follows: We first use exploration processYt∗t≥0 to explore the components of ℬn,m,p. Then, for the upper bound of C1, we only need to give the upper bound on the stop time T∗ as Cv0=T∗. For this, we follow the ideas in [[32], Proposition 1]. Recall Lemma 10.Lemma 10 (see Lemma 8 in [32]).
Letη be an integer-valued random variable with Eη2<∞ such that, for any integer h≥2, Pη∈hℤ<1. Let ηii=1∞ be a sequence of the i.i.d. random variables distributed as η and(49)Wt=W0+∑i=1tηi,t∈0,1,2,…,,where W0 is an integer constant. Define τ≔mint:Wt=0. If θ0>0 and it satisfies Eηeθ0η=0, then, for any integer ℓ≥1,(50)Pτ=ℓ=Θℓ−3/2ϕθ0ℓ,where ϕθ=Eeθη and the constants in Θ depend only on η and W0 but not ℓ.Proof.
of Upper Bound in Weakly Subcritical Case in Theorem 1. To utilize Lemma 10, set(51)St=1+∑i=1tξi−1,where ξtt=1∞ is a sequence of the i.i.d. random variables distributed as CBn,m,p. Take ς=ξ1−1 for brevity. Note that ς takes values in −1,0,1,…,n−1. Write(52)Pς=i=pifori∈−1,0,1,…,n−1.When m=βn, p=γ/n, and βγ2=1−ϵ, where ϵ⟶0 and n1/3ϵ⟶∞ as n⟶∞,(53)Eς=Eξi−1=fX∗′1−1=−ϵ,(54)Eς2=fX∗21−fX∗′1=1−ϵ1+γ+ϵ21+o1,(55)Eς3=fX∗31+fX∗′1−1=γ2+3γ+1−γ2+3γ+3ϵ+ϵ21+o1.
Setan=ϵ/1+γ1−ϵ+γ2+3γ+2ϵ and bn=ϵ/1+γ1−ϵ−2ϵ. Define Fθ=Eςeθςforθ∈an,bn. In the following, we check that there is θ0 such that(56)an<θ0<bn,Fθ0=Eςeθ0ς=0.
Note that, for any natural numberi and x∈0,∞, eix−e−x>i+1x; and (53) implies p−1=ϵ+∑i=1n−1ipi. We can obtain(57)Eςebnς=−e−bnp−1+ebnp1+2e2bnp2+⋯+n−1en−1bnpn−1=53e−bn−ϵ−∑i=1n−1ipi+∑i=1n−1ieibnpi=−ϵe−bn+∑i=1n−1ipieibn−e−bn≥−ϵe−bn+bn∑i=1n−1ii+1pi≥−ϵ1−bn+b2n+bnEς2+Eς=−ϵ+bn1+γ1−ϵ−ϵ+oϵ>0.
by (53)–(55), we can obtain(58)Eςeanς=∑i=−1n−1eaniipi≤36∑i=−1n−11+an+a2niipi≤37∑i=−1n−11+ian+ia2n+2i2a2n31+an2ipi=∑i=−1n−1kpk+an∑i=−1n−1i2pi+2a2n1+an23∑i=−1n−1i3pi≤Eς+anEς2+a2nEς3≤−ϵ+ϵ1+γ1−ϵ+oϵ1+γ1−ϵ+γ2+3γ+2ϵ+ϵ2γ2+3γ+11+γ1−ϵ+γ2+3γ+2ϵ2≤−γ2+3γ+2ϵ2+oϵ21+γ1−ϵ+γ2+3γ+2ϵ+ϵ2γ2+3γ+11+γ1−ϵ+γ2+3γ+2ϵ2<0.
Third, it is obvious thatFθ is continuous on an,bn. Hence, together with (57) and (58), this implies (56) holds by the Intermediate Value Theorem.
Now we estimateEeθ0ς. By (53) and (54), we can deduce that(59)Eeθ0ς=∑k=−1n−1eθ0kpk≤36∑k=−1n−11+θ0+θ02kpk≤37∑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−ϵ2n31+γ+oϵ2.
Suppose that there areℓ active vertices and k explored vertices have been explored at the time step t in the exploration process on ℬn,m,p. We can see that the number of newly explored vertices Xt∗ through the current vertex, say v, has the distribution CBn−k−ℓ,m,p. Therefore, by Lemma 6, Xt∗≺¯ξt, where ξt is distributed as CBn,m,p. That is to say, for all k≤minT∗,n,(60)∑i=1kXi∗≺¯∑i=1kξi,where T∗=mint:Yt∗=0. Let Ctv0 denote total explored vertices which are explored from time 0 to t by the exploration process on ℬn,m,p starting from vertex v0. Define τS=mint:St=0,t≤n. Note that(61)Ctv0=1+∑i=1tXi∗−1andSt=1+∑i=1tξi−1.
This meansCtv0≺¯St implying T∗≺¯τS. Therefore, by Lemma 10,(62)PCv0≥M0=PT∗≥M0≤PτS≥M0=∑ℓ≥M0PτS=ℓ=∑ℓ≥M0Oℓ−3/21−ϵ231+γ+oϵ2ℓ.
SetM0=41+γϵ−2nlognϵ3n. By the inequality 1−x≤e−x, for x≥0,(63)PτS≥M0=OM0−3/2∑ℓ≥M01−ϵ231+γ+oϵ2ℓ=Oϵ−2M0−3/21−ϵ231+γ+oϵ2M0=Oϵ−2M0−3/2exp−M0ϵ231+γ+oM0ϵ2=Oϵlognϵ3−3/2nϵ3−4/3+o1.
DenoteZ≥k=∑v∈V1Cv≥k.(64)PC1≥M0=PZ≥M0≥M0≤EZ≥M0M0=∑v∈VE1|Cv|≥M0M0=nPCv0≥M0M0≤nPτS≥M0M0=Onϵ3−1/3−o1lognϵ3−5/2=o1.



---

*Source: 2284300-2021-11-09.xml*