Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949652 | Discrete Applied Mathematics | 2017 | 19 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kathleen E. Hamilton, Leonid P. Pryadko,