Graph bootstrap percolation

DOI10.1002/rsa.20458zbMath1279.68243arXiv1107.1381OpenAlexW2091222603MaRDI QIDQ3145835

József Balogh, Béla Bollobás, Robert Morris

Publication date: 14 December 2012

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph theoryweak saturationbootstrap percolation

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Cellular automata (computational aspects) (68Q80)

Related Items (25)

\(K_{r,s}\) graph bootstrap percolation ⋮ Burning grids and intervals ⋮ Sharp thresholds for contagious sets in random graphs ⋮ Burning a graph is hard ⋮ The minimum number of clique-saturating edges ⋮ New ordering methods to construct contagious sets and induced degenerate subgraphs ⋮ Burning and \(w\)-burning of geometric graphs ⋮ Transitive closure in a polluted environment ⋮ On the running time of hypergraph bootstrap percolation ⋮ Saturation in the Hypercube and Bootstrap Percolation ⋮ The Zero Forcing Number of Graphs ⋮ Counting restricted orientations of random graphs ⋮ On the number of \(K_4\)-saturating edges ⋮ Percolating sets in bootstrap percolation on the Hamming graphs and triangular graphs ⋮ Bootstrap percolation on the random graph \(G_{n,p}\) ⋮ On the maximum running time in graph bootstrap percolation ⋮ Burning numbers of path forests and spiders ⋮ Burning number of theta graphs ⋮ A sharp threshold for bootstrap percolation in a random hypergraph ⋮ On \(K_{2, t}\)-bootstrap percolation ⋮ Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph ⋮ Burning numbers of \(t\)-unicyclic graphs ⋮ The sharp \(K_4\)-percolation threshold on the Erdős-Rényi random graph ⋮ How to Burn a Graph ⋮ Fuzzification of Zero Forcing Process

Cites Work

• Unnamed Item
• Unnamed Item
• Linear algebra and bootstrap percolation
• A sharper threshold for bootstrap percolation in two dimensions
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)
• Bootstrap percolation on the hypercube
• Bootstrap percolation in three dimensions
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• An extremal problem for sets with applications to graph theory
• Threshold functions
• An extremal problem for two families of sets
• On the behavior of some cellular automata related to bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Finite size scaling in three-dimensional bootstrap percolation
• Stretched exponential fixation in stochastic Ising models at zero temperature
• Threshold models of diffusion and collective behavior
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the random regular graph
• Majority Bootstrap Percolation on the Hypercube
• Metastability effects in bootstrap percolation
• Sharp thresholds of graph properties, and the $k$-sat problem
• A simple model of global cascades on random networks
• Integrals, partitions, and cellular automata
• Bootstrap Percolation in High Dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• On generalized graphs

This page was built for publication: Graph bootstrap percolation