Tight Lower Bound for Percolation Threshold on an Infinite Graph

Abstract

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.