TY - JOUR

T1 - Tight lower bound for percolation threshold on an infinite graph

AU - Hamilton, Kathleen E.

AU - Pryadko, Leonid P.

N1 - Publisher Copyright:
© 2014 American Physical Society.

PY - 2014/11/12

Y1 - 2014/11/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84910650245&partnerID=8YFLogxK

U2 - 10.1103/PhysRevLett.113.208701

DO - 10.1103/PhysRevLett.113.208701

M3 - Article

AN - SCOPUS:84910650245

SN - 0031-9007

VL - 113

JO - Physical Review Letters

JF - Physical Review Letters

IS - 20

M1 - 208701

ER -