Abstract: In this article, we study the critical threshold for an arbitrary quasi-transitive d-regular graph. We show that for such graphs G, pc(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.
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 pc(G) ≥ 1/(Δ-1). For trees of degree Δ, by a dual second moment upper bound, we can get pc ≤ 1/(Δ-1), thus implying that pc = 1/(Δ-1).
The question we ask is the following: Consider percolation on a Δ-regular graph G, are trees the only graphs with pc = 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, pc > 1/(Δ-1).
Let G be a quasi-transitive regular graph of degree Δ. Then pc(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.
[...additional content here...]