Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

DOI10.1016/J.DAM.2016.12.027MaRDI QIDQ1786879zbMATH OpenOpenAlexFDO

Authors Kathleen E. Hamilton, Leonid P. Pryadko

Publication date 25 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.03963

zbMATH Keywords

digraphpercolationinfinite graphvertex connectivitynon-backtracking spectra

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Infinite graphs (05C63)

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.

Recommendations

• Percolation on sparse random graphs with given degree sequence
• Percolation in general graphs
• Percolation on dense graph sequences
• Percolation on finite graphs and isoperimetric inequalities.
• Critical probabilities for site and bond percolation models

Cites work

• scientific article; zbMATH DE number 4165188 (Why is no real title available?)
• scientific article; zbMATH DE number 5722221 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• scientific article; zbMATH DE number 3996823 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• A simple model of global cascades on random networks
• Comparison of Atom and Bond Percolation Processes
• Contagion in financial networks
• Estimates for norms of resolvents and an application to the perturbation of spectra
• Isoperimetric Constants of (d,f)-Regular Planar Graphs
• Multiparty entanglement in graph states
• On the critical behavior of the general epidemic process and dynamical percolation
• Percolation beyond \(\mathbb{Z}^ d\), many questions and a few answers
• Percolation in general graphs
• Percolation on dense graph sequences
• Percolation on finite graphs and isoperimetric inequalities.
• Percolation on heterogeneous networks as a model for epidemics
• Percolation, renormalization, and quantum computing with nondeterministic gates
• Phase transitions on nonamenable graphs.
• Random graphs.
• Random walks and percolation on trees
• Self-Avoiding Walks on Hyperbolic Graphs
• Sharp threshold for percolation on expanders
• Some properties of line digraphs
• Statistical mechanics of complex networks
• The Coincidence of Critical Points in Poisson Percolation Models
• The non-backtracking spectrum of the universal cover of a graph
• Uniqueness and non-uniqueness in percolation theory

This page was built for publication: Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786879)