# Phase Transition in Long-Range Percolation on Bipartite Hierarchical Lattices

Authors: Yilun Shang
Journal: The Scientific World Journal
 (2013)

---

## Abstract

We propose a family of bipartite hierarchical lattice of orderN governed by a pair of parameters ℓ and γ. We study long-range percolation on the bipartite hierarchical lattice where any edge (running between vertices of unlike bipartition sets) of length k is present with probability pk=1-exp-αβ-k, independently of all other edges. The parameter α is the percolation parameter, while β describes the long-range nature of the model. The model exhibits a nontrivial phase transition in the sense that a critical value αc∈0,∞ if and only if ℓ≥1,1≤γ≤N-1, and β∈N,N2. Moreover, the infinite component is unique when α>αc.


---

## Body

## 1. Introduction

For an integerN≥2, the hierarchical lattice of order N is defined by
(1)ΩN={x=(x1,x2,…):xi∈{0,1,…,N-1},∑i‍xi<∞}.
The hierarchical distance d on ΩN is defined by
(2)d(x,y)={0,ifx=y,max{i:xi≠yi},ifx≠y,
which satisfies the strong (non-Archimedean) triangle inequality:
(3)d(x,y)≤max{d(x,z),d(z,y)},
for any x,y,z∈ΩN. This means that (ΩN,d) is an ultrametric space. Roughly speaking, this corresponds to the leaves of an infinite N-ary tree, with metric distance half the graph distance.Some stochastic models based on hierarchical lattices have been studied. The asymptotic long-range percolation onΩN is analyzed in [1] for N→∞. To the best of our knowledge, this is the first paper devoted to (ΩN,d). For different purpose, the works [2–4] study the long-range percolation on ΩN for fixed N by using different connection probabilities. The contact process and perturbation analysis on ΩN for finite N have been studied in [5, 6], respectively. Random walks on hierarchical lattices have been examined in [7, 8].In this paper, we study percolation on a class of bipartite hierarchical lattices, where edges always run between vertices of unlike type. Bipartite graphs have been studied intensively in the literature (see e.g., [9, 10]) and bipartite structure is popular in many social networks including sexual-contact networks [11] and affiliation networks [12], but we have not seen the setup that we consider here. For two integers ℓ≥1 and 1≤γ≤N-1, consider a partition of ΩN into two sets:
(4)ΩN1=ΩN1(ℓ,γ)={x=(x1,x2,…)∈ΩN:xℓ∈{0,1,…,γ-1}},ΩN2=ΩN2(ℓ,γ)={x=(x1,x2,…)∈ΩN:xℓ∈{γ,γ+1,…,N-1}}.
Vertices in ΩN1 and ΩN2 are said to have types 1 and 2, respectively. For each k≥1, the probability of connection between two vertices x and y of unlike type such that d(x,y)=k is given by
(5)pk=1-exp(-αβk),
where 0≤α<∞ and 0<β<∞, all connections being independent. Vertices of the same type cannot be connected with each other, and hence the resulting graph is a class of random bipartite graph.In the above bipartite hierarchical lattice, denoted by(ΩN1,ΩN2,d), vertices of both types are countable and the shortest distance between vertices in ΩN1 and ΩN2 is ℓ. The vertices in (ΩN1,ΩN2,d) can be represented by the leaves at the bottom of an infinite regular tree, where N branches emerge from each inner node, see Figure 1. The distance between two vertices (leaves at level 0) is the number of levels from the bottom to their most recent common ancestor. The partition of types for vertices is determined by their ancestors at level ℓ; in other words, we need to track back at least ℓ levels to find the most recent common ancestor of two vertices of unlike type.Figure 1
An illustration of bipartite hierarchical lattice(ΩN1(ℓ,γ),ΩN2(ℓ,γ),d) of order N=3, ℓ=2, and γ=2. Vertices of type 1 are represented by solid points while those of type 2 hollow points. The distances between three vertices 0=(0,0,0,…)∈ΩN1, x=(1,0,0,…)∈ΩN1, and y=(0,2,0,…)∈ΩN2 are d(0,x)=1 and d(0,y)=d(x,y)=2.Two verticesx,y∈(ΩN1,ΩN2,d) are in the same component if there exists a finite sequence x=x0,x1,…,xn=y such that each pair of vertices xi-1 and xi has different types and shares an edge for i=1,…,n. In our model, the parameter β>0 describes the long-range nature, while we think of α≥0 as a percolation parameter. We are interested in studying when there is a nontrivial percolation threshold in (ΩN1,ΩN2,d), namely, the critical percolation value αc∈(0,∞). Our results for phase transition are analogous to those in the monopartite counterpart (ΩN,d) (see [3]). The similar (comparable) behavior of phase transitions in bipartite and corresponding monopartite networks has also been observed in other percolation contexts (see the discussion in Section 2).The rest of the paper is organized as follows. The results are stated and discussed in Section2, and the proofs are given in Section 3.


## 2. Results

Let|S| be the size of a vertex set S. The connected component containing the vertex x is denoted by C(x). By definition, the origin 0∈ΩN1(ℓ,γ) for all ℓ≥1 and 1≤γ≤N-1. Since, for all x∈ΩN1(ℓ,γ) and y∈ΩN2(ℓ,N-γ), |C(x)| and |C(y)| have the same distribution, it suffices to consider only |C(0)| without loss of generality. The percolation probability is defined as
(6)θ(ℓ,γ,α,β)=P(|C(0)|=∞),
and the critical percolation value is defined as
(7)αc=αc(ℓ,γ,β)=inf{α≥0:θ(ℓ,γ,α,β)>0},
which is nondecreasing in β for any given ℓ and γ.Theorem 1.
Assume thatℓ≥1, 1≤γ≤N-1 and that 0<β<∞. One has the following: (i)
Ifβ≤N, then αc=0.(ii)
Ifβ≥N2, then αc=∞.(iii)
IfN<β<N2, then 0<αc<∞.Moreover, there is almost surely at most one infinite component when α>αc.Remark 2.
The critical valueαc=αc(ℓ,γ,β) turns out to be a function of only β irrespective of the values of ℓ and γ. Koval et al. [3] showed the same behavior of αc for percolation in the monopartite lattice ΩN. This analogy of phase transition has been recognized in other percolation problems in statistical physics. An example is the AB percolation introduced by Mai and Halley [13] for the study of gelation processes. In this model, each vertex of an infinite connected graph G is assigned one of two states, say A and B, with probability p and 1-p, respectively, independently of all other vertices. Edges with two end-vertices having unlike states (called AB bonds) are occupied. Thus, the AB percolation can be viewed as a bond percolation with occupation probability 2p(1-p) (although some dependence is involved, namely, no odd path of AB bonds exists). Appel and Wierman [14] proved that AB percolation does not occur for any value of p∈[0,1] on a bipartite square lattice with bipartition V1={v=(vx,vy)∈ℤ2:vx-vyisodd} and V2={v=(vx,vy)∈ℤ2:vx-vyiseven} such that ℤ2=V1∪V2. In other words, the bond percolation cannot occur on the above bipartite square lattice for occupation probability 2p(1-p)≤1/2. This is consistent with the classical result which says that bond percolation on ℤ2 does not occur when occupation probability ≤1/2 (see, e.g., [15, 16]). Other comparable AB percolation thresholds for monopartite and bipartite high-dimensional lattices can be found in [17].Another example is the biased percolation [18, 19] on infinite scale-free networks with a power-law degree distribution P(k)∝k-γ. In this model, an edge between vertices with degrees k1 and k2 is occupied with probability proportional to (k1k2)-α. By using generating function method, Hooyberghs et al. [9] showed that biased percolation on a bipartite scale-free network with two bipartition sets following degree distributions PA(k)∝k-γA and PB(k)∝k-γB, respectively, has the same critical behaviors with biased percolation on a monopartite scale-free network when γA=γB=γ.Remark 3.
The uniqueness of the infinite component holds here for the same reason as the uniqueness result for the percolation graph ofΩN (see [3, Theorem 2]). Note that our graph resulting from (ΩN1,ΩN2,d) can be viewed as a spanning subgraph of that from (ΩN,d).We consider Theorem1 as an intermediate step towards the study of percolation on bipartite hierarchical lattices. In particular, one may explore the connectivity at the critical regime β=N2 and the graph distance (chemical distance) between 0 and a vertex x. It is also interesting to study the mean field percolation (N→∞) and compare it with that on ΩN [1]. Directed percolation [20] and other meaningful colorings on ΩN (other than the 2-coloring addressed in this paper) are possible.


## 3. Proofs

We start with some notations. Then we prove Theorem1.For a vertexx∈(ΩN1,ΩN2,d), define Br(x) as the ball of radius r around x; that is, Br(x)={y:d(x,y)≤r}. We make the following observations. Firstly, for any vertex x, Br(x) contains Nr vertices. In particular, if r<ℓ, all vertices in the ball have the same type. Secondly, Br(x)=Br(y) if d(x,y)≤r. Finally, for any x, y, and r, we have either Br(x)=Br(y) or Br(x)∩Br(y)=∅.For a setS of vertices, denote by S-=ΩN∖S its complement. Let Cn(x) be the component of vertices that are connected to x by a path using only vertices within Bn(x). For disjoint sets S1,S2⊆ΩN, we denote by S1↔S2 the event that at least one edge joins a vertex in S1 to a vertex in S2. S1↮S2 means the event that such an edge does not exist. By definition, if S1,S2⊆ΩNi for i=1 or 2, then S1↮S2 occurs with probability 1. Let Cnm(x) be the largest component in Bn(x). If there are more than one such components, just take any one of them as Cnm(x). It is clear that |Cnm(x)|=maxy∈Bn(x)|Cn(y)| [3].Proof of (i).
LetAk be the event that the origin 0∈ΩN1 connects by an edge to at least one vertex at distance k in ΩN2. By construction, for k<ℓ, P(Ak)=0. For k=ℓ, there are ((N-γ)/(N-1))(N-1)Nk-1 vertices in ΩN2 at distance k from 0. Hence,
(8)P(Aℓ)=1-(1-pℓ)(N-γ)Nk-1=1-exp(-αβℓ(N-γ)Nℓ-1),
by using (5). For k>ℓ, there are ((N-γ)/N)(N-1)Nk-1 vertices in ΩN2 at distance k from 0. Similarly, we obtain
(9)P(Ak)=1-exp(-α(N-γ)(N-1)βkNNk-1),
for k>ℓ.
Since all the events{Ak}k≥1 are independent and
(10)∑k=1∞‍P(Ak)≈1-exp(-αβℓ(N-γ)Nℓ-1)+α(N-γ)N∑k=ℓ+1∞‍(Nβ)k
diverges for any 0<β≤N, 1≤γ≤N-1, and α>0, infinitely many of Ak occur with probability 1 by the second Borel-Cantelli lemma. Thus, θ(ℓ,γ,α,β)=1 for any ℓ>1, 1≤γ≤N-1, α>0, and 0<β≤N. The result then follows.Proof of (ii).
We only need to showαc(ℓ,γ,N2)=∞ by virtue of the monotonicity. Note that, for j≥ℓ, there are (γ/N)Nj vertices in Bj(0)∩ΩN1 and ((N-γ)/N)Nj vertices in Bj(0)∩ΩN2. Hence, by the comments in the proof of (i) and taking β=N2, for any j≥ℓ, we obtain
(11)P(Bj(0)⟷Bj(0)¯)=1-(∏k=j+1∞‍(1-pk)((N-γ)/N)(N-1)Nk-1)(γ/N)Nj·(∏k=j+1∞‍(1-pk)(γ/N)(N-1)Nk-1)((N-γ)/N)Nj=1-exp(-2α(N-γ)(N-1)γNjN4hhhhhhhhhhh×∑k=1∞‍Nk+j-1N2(k+j-1))=1-exp(-2α(N-γ)γN3),
which is strictly less than 1 for any finite α≥0.
Letnℓ=0 and ni+1=inf{n≥ni:Bni(0)↮Bn(0)¯}. We have
(12){|C(0)|=∞}⊆⋂i=ℓ∞{Bni(0)⟷Bni(0)¯}.
Since the events {Bni(0)↔Bni(0)¯} are independent and all have the same probability strictly less than 1,
(13)P(Bni(0)⟷Bni(0)¯,foranyi≥ℓ)=0.
Consequently, there exists an i such that Bni(0)↮Bni(0)¯ with probability 1. It follows from (12) that θ(ℓ,γ,α,N2)=0 for all α≥0. This implies αc(ℓ,γ,N2)=∞.Proof of (iii).
The positivity ofαc is a direct consequence of the proof of Theorem 1(b) in [3]. Since the percolation graph of (ΩN1,ΩN2,d) can be viewed as a spanning subgraph of that of (ΩN,d), the percolation cluster C(0) is almost surely finite; namely, θ(ℓ,γ,α,β)=0, for α small enough.Now we turn to the proof of finiteness ofαc. The main technique to be used is an iteration involving the tail probability of binomial distributions [3, 21]. Since β<N2, we choose an integer K and a real number δ such that
(14)β<δ≤(NK-1)1/K.
Clearly, 1<δ<N. For n≥1, let
(15)an=P(|CnKm(0)∩ΩN1|≥γNδnK,hhhhh|CnKm(0)∩ΩN2|≥N-γNδnK),
and analogously,
(16)bn=P(|CnK(0)∩ΩN1|≥γNδnK,hhhhh|CnK(0)∩ΩN2|≥N-γNδnK).
Here, an is the probability that the largest component of a ball of radius nK contains at least (γ/N)δnK vertices in ΩN1 and at least ((N-γ)/N)δnK vertices in ΩN2. Such a ball is said to be good. We set a0=b0=1 by convention. It is clear that, for α>0, all an and bn are positive, since nK is a finite number and the connection probability in (5) is positive.In what follows, we will proveαc<∞ in two steps.Step 1.
We show that there exists someα>0 such that an converges to 1 exponentially fast; namely, 1-an≤exp(-cn) for some c>0.Step 2.
We show that there exists someα>0 such that liminfn→∞bn>0.We start with Step1. To this end, denote by ℕ the nonnegative integers. We can naturally label the vertices in ΩN via the map f:ΩN→ℕ as
(17)f:x=(x1,x2,…)⟼∑i=1∞‍xiNi-1.
This order agrees with the depiction in Figure 1. A ball of radius nK is said to be very good if it is good and its largest component connects by an edge to the largest component of the first (as per the aforementioned order) good subball in the same ball of radius (n+1)K. Clearly, the first good subball of radius nK in a ball of radius (n+1)K is very good. Condition (14) implies that (NK-1)δnK≥δ(n+1)K. Thus we assert that the ball B(n+1)K(0) is good if (a) it contains NK-1 good subballs of radius nK, and (b) all these good subballs are very good.The number of good subballs of radiusnK in a ball of radius (n+1)K has a binomial distribution Bin(NK,an) with parameters NK and an. Given the collection of good subballs, the probability that the first such good subball is very good equals to 1. Fix any of the other good subballs, say B; the probability that B is not very good is upper bounded by
(18)(1-p(n+1)K)ad+bc≤(1-p(n+1)K)(2γ(N-γ)/N2)δ2nK(1-p(n+1)K)ad+bc=exp(-2αγ(N-γ)βKN2(δ2β)nK)(1-p(n+1)K)ad+bc≔εn,
where a and b are the number of vertices in the largest component of the first good subball in ΩN1 and ΩN2, respectively; likewise, c and d are the number of vertices in the largest component of the subball B in ΩN1 and ΩN2, respectively. By definition, we have a,c≥(γ/N)δnK, b,d≥((N-γ)/N)δnK, and the distance between two vertices in a ball of radius (n+1)K is at most (n+1)K.Therefore, the probability for any of the other good subballsB to be very good is at leat 1-εn. Thus, the number of very good subballs is stochastically larger than a random variable obeying a binomial distribution Bin(NK,an(1-εn)). From the above comments (a) and (b) and the definition of an, it follows that
(19)an+1≥P(Bin(NK,an(1-εn))≥NK-1).
In general, we have the following inequality for the tail of binomial random variable:
(20)P(Bin(n,p)≥n-1)≥1-(n2)(1-p)2.
By (19), (20), and writing ξn=1-an, we obtain
(21)ξn+1=1-an+1≤(NK2)(1-an+anεn)2≤(NK2)(1-an+εn)2=(NK2)(ξn+εn)2.
We can choose c>0 large enough so that 4(NK2)≤exp(c), and then we choose α large enough so that (c) εn≤exp(-c(n+1)) and (d) ξ1≤exp(-2c) hold. To see (c), note that β<δ2 and then
(22)εn=exp(-2αγ(N-γ)βKN2(δ2β)nK)≤((βδ2)2Kαγ(N-γ)/βkN2)n.
To see (d), note that limα→∞ε0=0, ξ0=0 and by (21) we obtain
(23)ξ1=1-a1≤(NK2)(ξ0+ε0)2,
which also approaches 0.According to our above choice ofc and α, we have inductively, if ξn≤exp(-c(n+1)), then
(24)ξn+1≤(NK2)(ξn+εn)2≤4(NK2)exp(-2c(n+1))≤exp(-c(2n+1))≤exp(-c(n+2)),
which implies that ξn≤exp(-c(n+1))≤exp(-cn) for all n∈ℕ. We then finish the proof of Step 1.For Step2, recalling the definition of bn, we claim that
(25)bn+1≥bn·P(Bin(NK-1,an(1-εn))≥NK-2).
In deed, if |CnK(0)∩ΩN1|≥(γ/N)δnK and |CnK(0)∩ΩN2|≥((N-γ)/N)δnK, then BnK(0) is the first good subball in the derivation above. If this component is connected to at least NK-2 other large components in B(n+1)K(0) as above, then the component containing the origin in B(n+1)K(0) has (γ/N)δnK(NK-1)≥(γ/N)δ(n+1)K vertices in ΩN1 and ((N-γ)/N)δnK(NK-1)≥((N-γ)/N)δ(n+1)K vertices in ΩN2. Thus, the inequality (25) follows.A simple coupling gives(26)P(Bin(NK-1,an(1-εn))≥NK-2)≥P(Bin(NK,an(1-εn))≥NK-1).
Hence, we derive that the right-hand side of (26) converges to 1 exponentially fast by exploiting (20) and the fact that an(1-εn) converges to 1 exponentially fast. It then follows from (25) that
(27)bn+1≥bn(1-exp(-cn)),
for some c>0. Hence,
(28)bn+1≥b1∏k=1n‍(1-exp(-ck)).
It is direct to check that
(29)ln(∏k=1n‍(1-exp(-ck)))≥ln(1-∑k=1n‍exp(-ck))(∏k=1n‍(1-exp(-ck))ln)≥ln(1-2exp(-c)1-exp(-c))(∏k=1n‍(1-exp(-ck))ln)>-∞,
and hence ∏k=1n‍(1-exp(-ck))>0 for all n. Since b1>0, inequality (28) yields
(30)liminfn→∞bn>0,
as desired.



---

*Source: 172393-2013-10-29.xml*