Threshold behavior of bootstrap percolation

DOI10.1016/J.DISC.2020.112211MaRDI QIDQ2214063zbMATH OpenOpenAlexFDO

Authors Ahad N. Zehmakan

Publication date 4 December 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

\(d\)-dimensional torus\(r\)-threshold modelbiased majoritybootstrap percolationcellular automataphase transition

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: Consider a graph $G$ and an initial random configuration, where each node is black with probability $p$ and white otherwise, independently. In discrete-time rounds, each node becomes black if it has at least $r$ black neighbors and white otherwise. We prove that this basic process exhibits a threshold behavior with two phase transitions when the underlying graph is a $d$-dimensional torus and identify the threshold values.

Recommendations

• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation on the random regular graph
• Bootstrap percolation on the product of the two-dimensional lattice with a Hamming square
• Existence and region of critical probabilities in bootstrap percolation on inhomogeneous periodic trees
• Bootstrap percolation on the random graph \(G_{n,p}\)

Cites work

• A sharp threshold for a modified bootstrap percolation with recovery
• Bootstrap percolation in three dimensions
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Bounding the sizes of dynamic monopolies and convergent sets for threshold-based cascades
• Color War: Cellular Automata with Majority-Rule
• Concentration of Measure for the Analysis of Randomized Algorithms
• Contagious sets in random graphs
• Convergence in (social) influence networks
• Dynamic monopolies in tori.
• Dynamic monopolies in two-way bootstrap percolation
• Extremal bounds for bootstrap percolation in the hypercube
• Finite size scaling in three-dimensional bootstrap percolation
• Local frequency dependence and global coexistence
• Majority dynamics on trees and the dynamic cavity method
• Majority model on random regular graphs
• Metastability effects in bootstrap percolation
• Minimal contagious sets in random regular graphs
• On the behavior of some cellular automata related to bootstrap percolation
• Opinion forming in Erdős-Rényi random graph and expanders
• Periodic behaviour of generalized threshold functions
• Random disease on the square grid
• Random majority percolation
• Rumor spreading: A trigger for proliferation or fading away
• Sharp metastability threshold for two-dimensional bootstrap percolation
• The metastability threshold for modified bootstrap percolation in d dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• The threshold regime of finite volume bootstrap percolation.
• The time of bootstrap percolation in two dimensions
• Threshold behavior of democratic opinion dynamics
• Tight bounds on the minimum size of a dynamic monopoly
• Transient length in sequential iteration of threshold functions

Cited in

(15)

• Dependence of the percolation threshold on the size of the percolating species
• On the spread of influence in graphs
• Bootstrap percolation on the stochastic block model
• Bootstrap percolation on the product of the two-dimensional lattice with a Hamming square
• Polluted bootstrap percolation with threshold two in all dimensions
• Dynamic monopolies in two-way bootstrap percolation
• Generalized \(k\)-core percolation on higher-order dependent networks
• The time of bootstrap percolation with dense initial sets for all thresholds
• Are the tails of percolation thresholds Gaussians?
• A sharp threshold for a modified bootstrap percolation with recovery
• A note on bootstrap percolation thresholds in plane tilings using regular polygons
• Bootstrap percolation via automated conjecturing
• Target set in threshold models
• On the size of immune sets in the k-PULL infection model
• Calculation of percolation threshold and analysis on fractal dimension of percolation path in 2-D porous lattice

This page was built for publication: Threshold behavior of bootstrap percolation

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