Algebraic bounds for heterogeneous site percolation on directed and undirected graphs

DOI10.1016/J.DAM.2016.12.027zbMATH Open1396.05046arXiv1505.03963OpenAlexW2963434582MaRDI QIDQ1786879FDOQ1786879

Authors: Kathleen E. Hamilton, Leonid P. Pryadko 

Publication date: 25 September 2018

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

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.

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

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

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)

Cites Work

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

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)