Tight Lower Bound for Percolation Threshold on an Infinite Graph

We construct a tight lower bound for the site percolation threshold on an infinite graph, which becomes exact for an infinite tree. The bound is given by the inverse of the maximal eigenvalue of the Hashimoto matrix used to count nonbacktracking walks on the original graph. Our bound always exceeds the inverse spectral radius of the graph’s adjacency matrix, and it is also generally tighter than the existing bound in terms of the maximum degree. We give a constructive proof for existence of such an eigenvalue in the case of a connected infinite quasitransitive graph, a graph-theoretic analog of a translationally invariant system.

Figure 1

(a) A $d$-regular tree used for the backbone of the graph in Example 1. (b) The tree ${\mathcal{T}}_{d;r,L}$ is grown from the backbone by placing $r$ chains of fixed length $L$ (shown: $d=3$, $r=1$, $L=2$) at each vertex of the backbone.

Figure 2

Illustration of SCU. (a) A graph $\mathcal{G}$ with a nonbridge bond $b\equiv (u,v)$ highlighted. (b) The two-terminal graph ${\mathcal{G}}^{\prime }$. (c) The resulting graph ${\mathcal{C}}_b\mathcal{G}$ is a series composition of an infinite chain of copies of ${\mathcal{G}}^{\prime }$.