Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

Kathleen E. Hamilton; Leonid P. Pryadko

doi:10.1016/j.dam.2016.12.027

Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

Kathleen E. Hamilton, Leonid P. Pryadko

Quantum Computational Science

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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.

Original language	English
Pages (from-to)	124-142
Number of pages	19
Journal	Discrete Applied Mathematics
Volume	222
DOIs	https://doi.org/10.1016/j.dam.2016.12.027
State	Published - May 11 2017

Keywords

Digraph
Infinite graph
Non-backtracking spectra
Percolation
Vertex connectivity

Access to Document

10.1016/j.dam.2016.12.027

Cite this

@article{eb91e55661e9444ab162a401742c4530,

title = "Algebraic bounds for heterogeneous site percolation on directed and undirected graphs",

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.",

keywords = "Digraph, Infinite graph, Non-backtracking spectra, Percolation, Vertex connectivity",

author = "Hamilton, {Kathleen E.} and Pryadko, {Leonid P.}",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier B.V.",

year = "2017",

month = may,

day = "11",

doi = "10.1016/j.dam.2016.12.027",

language = "English",

volume = "222",

pages = "124--142",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

AU - Hamilton, Kathleen E.

AU - Pryadko, Leonid P.

PY - 2017/5/11

Y1 - 2017/5/11

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

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

KW - Digraph

KW - Infinite graph

KW - Non-backtracking spectra

KW - Percolation

KW - Vertex connectivity

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

U2 - 10.1016/j.dam.2016.12.027

DO - 10.1016/j.dam.2016.12.027

M3 - Article

AN - SCOPUS:85012031534

SN - 0166-218X

VL - 222

SP - 124

EP - 142

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this