Percolation thresholds under coverings.

Using the Critical Threshold to Characterize a Tree

This project was carried out as part of the Visiting Students Research Programme, at the Tata Institute of Fundamental Research under the guidance of Prof. Subhajit Goswami. I gave a presentation at TIFR, which could be found here.

It is a well known fact that for a d-regular graph \(G, p_c(G) \geq \frac{1}{d-1}\). Now if for a d-regular graph we set \(p_c = \frac{1}{d-1}\) does it imply that the graph is a tree? We answer this question here.

Abstract: In this article, we study the critical threshold for an arbitrary quasi-transitive d-regular graph. We show that for such graphs G, p_c(G) = 1/(d-1) if and only if G is a tree. This gives a neat probabilistic characterization for regular trees. We also give counterexamples for the non-quasi-transitive case.

1 Introduction

We consider independent bond percolation on a graph G, i.e., we retain edges with probability p and throw them away with probability 1-p. By a simple first moment, a graph with maximal degree Δ < ∞ satisfies p_c(G) ≥ 1/(Δ-1). For trees of degree Δ, by a dual second moment upper bound, we can get p_c ≤ 1/(Δ-1), thus implying that p_c = 1/(Δ-1).

The question we ask is the following: Consider percolation on a Δ-regular graph G, are trees the only graphs with p_c = 1/(Δ-1)? For the rest of this article, we restrict ourselves to percolation on regular graphs. In light of our question, we show that if one assumes quasi-transitivity, then for any Δ-regular graph G which is not a tree, p_c > 1/(Δ-1).

Theorem 1

Let G be a quasi-transitive regular graph of degree Δ. Then p_c(G) ≥ 1/(Δ-1), and equality holds if and only if G is a tree. It is important to note that the requirement of being a quasi-transitive graph is essential.

2 Percolation on Trees

2.1 Branching number and the critical point for trees

Suppose T = (V,E) is an infinite locally finite tree with root O. We imagine the tree T as growing downward from the root O. For x, y ∈ V, we write x ≤ y if x is on the shortest path from O to y; and T_x for the subtree of T containing all the vertices y with y ≥ x.

For a vertex x ∈ V, we denote by d(x,O) the graph distance from O to x. We want to understand the critical point for a tree, motivated by the comparison from Galton-Watson branching processes. This naturally leads us to the study of the average number of branches coming out of a vertex, which is called the branching number of a tree. To rigorously define this, we use conductances and flows on trees. For each edge e, we define the conductance of an edge to be c(e) := λ^-|e|, where |e| denotes the distance of the edge e from the root O. It is natural to define conductances decreasing exponentially with the distance since trees grow exponentially.

If λ is very small, then due to large conductances, there is a non-zero flow on the tree satisfying 0 ≤ θ(e) ≤ λ^-|e|. While increasing the value of λ, we observe a critical value λ_c above which such a flow does not exist. This is precisely the branching number.

Theorem 2. (R. Lyons, [Lyo90])

Let T be a tree, then p_c(T) = 1/br(T), where br(T) is the branching number of the tree.

3 Non-quasi-transitive Counterexamples

Let T = (V,E) be the graph of black edges shown in the figure, define G := T∪{e} = (V,E∪{e}) to be the graph obtained after adding the red edge e. In the figure, T is the underlying tree rooted at O and G is a 3-regular graph. We claim that p_c(G) = 1/(Δ-1), for Δ = 3. Similar counters can be constructed for d ≥ 4. Now for the tree T, |T₁| = 3, |T₂| = 6, |T₃| = 10, after this point, every point has 2 branches coming out, so |T_3+n| = 10× 2ⁿ. Therefore, grT = 2.

T is obviously subperiodic since for all x from Level 3 onwards, T_x is exactly T_A, so we can define the function f(v) = ϕ(v), where ϕ is the isomorphism between T_x and T_A. For the rest of the vertices, we can simply choose the identity map. Thus, T is 2-subperiodic. Now by Theorem 3, brT = grT = 2. Thus, p_c(T) = 1/2, but p_c(G) ≤ p_c(T) = 1/2. However, by a first moment bound, p_c(G) ≥ 1/2. Thus, p_c(G) = 1/2.

4 Proof of the Theorem

We now show that if G is a quasi-transitive Δ-regular graph, then p_c(G) > 1/(Δ-1). The idea is to cover every Δ-regular graph by a Δ-regular tree. The proof of this does not require quasi-transitivity. Next, we use the strict monotonicity (under coverings) result of Martineau and Severo [MS19]. To apply this result, we want our covering map to satisfy certain properties.

References

• R. Lyons, [Lyo90], Random walks and percolation on trees. The Annals of Probability, 18(3):931–958, 1990.
• F. Severo, S. Martineau, [MS19], Strict monotonicity of percolation thresholds under covering maps, 2019.