Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

作者：Hamilton Kathleen E^*; Pryadko Leonid P

来源：Discrete Applied Mathematics, 2017, 222: 124-142.

DOI：10.1016/j.dam.2016.12.027

• Percolation
• Non-backtracking spectra
• Vertex connectivity
• Infinite graph
• Digraph

We analyze site percolation on directed and undirected graphs with site-dependent open-site probabilities. We construct upper bounds on cluster susceptibilities, vertex connectivity functions, and the expected number of simple open cycles through a chosen arc; separate bounds are given on finite and infinite (di)graphs. These produce lower bounds for percolation and uniqueness transitions in infinite (di)graphs, and for the formation of a giant component in finite (di)graphs. The bounds are formulated in terms of appropriately weighted adjacency and non-backtracking (Hashimoto) matrices. It turns out to be the uniqueness criterion that is most closely associated with an asymptotically vanishing probability of forming a giant strongly-connected component on a large finite (di)graph.

• 出版日期2017-5-11