Strong-majority bootstrap percolation on regular graphs with low dissemination threshold

DOI10.1016/J.SPA.2017.02.001MaRDI QIDQ2402436zbMATH OpenOpenAlexWikidataFDO

Authors Paweł Prałat, D. Mitsche, Xavier Pérez-Giménez

Publication date 7 September 2017

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

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

zbMATH Keywords

bootstrap percolationregular graphsstrong majority rule

Mathematics Subject Classification ID

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

Abstract: Consider the following model of strong-majority bootstrap percolation on a graph. Let r be some positive integer, and p in [0,1]. Initially, every vertex is active with probability p, independently from all other vertices. Then, at every step of the process, each vertex v of degree deg(v) becomes active if at least (deg(v)+r)/2 of its neighbours are active. Given any arbitrarily small p>0 and any integer r, we construct a family of d=d(p,r)-regular graphs such that with high probability all vertices become active in the end. In particular, the case r=1 answers a question and disproves a conjecture of Rapaport, Suchan, Todinca, and Verstraete (Algorithmica, 2011).

Recommendations

• On dissemination thresholds in regular and irregular graph classes
• Majority bootstrap percolation on \(G(n,p)\)
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• Bootstrap percolation on the random regular graph
• On Dissemination Thresholds in Regular and Irregular Graph Classes

Cites work

• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Bootstrap percolation and kinetically constrained models on hyperbolic lattices
• Bootstrap percolation and the geometry of complex networks
• Bootstrap percolation in a polluted environment
• Bootstrap percolation in high dimensions
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation in three dimensions
• Bootstrap percolation on geometric inhomogeneous random graphs
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Critical length for semi-oriented bootstrap percolation
• Discontinuous bootstrap percolation in power-law random graphs
• Domination by product measures
• Finite size scaling in three-dimensional bootstrap percolation
• Finite-size effects for anisotropic bootstrap percolation: Logarithmic corrections
• scientific article; zbMATH DE number 1444756 (Why is no real title available?)
• Majority Bootstrap Percolation on the Hypercube
• Metastability effects in bootstrap percolation
• Monotone cellular automata in a random environment
• On dissemination thresholds in regular and irregular graph classes
• On percolation in random graphs with given vertex degrees
• On the behavior of some cellular automata related to bootstrap percolation
• Percolation
• Probability and Computing
• Proof of Straley's argument for bootstrap percolation.
• Remarks on bootstrap percolation in metric networks
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Stretched exponential fixation in stochastic Ising models at zero temperature
• Strict majority bootstrap percolation in the \textit{r}-wheel
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• Subcritical \(\mathcal{U}\)-bootstrap percolation models have non-trivial phase transitions
• Surface order large deviations for high-density percolation
• The sharp threshold for bootstrap percolation in all dimensions
• The sharp threshold for the Duarte model
• The threshold regime of finite volume bootstrap percolation.
• The time of bootstrap percolation in two dimensions
• The time of bootstrap percolation with dense initial sets
• The time of bootstrap percolation with dense initial sets for all thresholds

Cited in

(6)

• Strict majority bootstrap percolation in the \textit{r}-wheel
• Majority bootstrap percolation on \(G(n,p)\)
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• Color War: Cellular Automata with Majority-Rule
• On dissemination thresholds in regular and irregular graph classes
• The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity

This page was built for publication: Strong-majority bootstrap percolation on regular graphs with low dissemination threshold

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