Minimal percolating sets in bootstrap percolation

zbMATH Open1178.60070arXivmath/0702370MaRDI QIDQ1010903FDOQ1010903

Authors: Robert Morris 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: In standard bootstrap percolation, a subset A of the n x n grid is initially infected. A new site is then infected if at least two of its neighbours are infected, and an infected site stays infected forever. The set A is said to percolate if eventually the entire grid is infected. A percolating set is said to be minimal if none of its subsets percolate. Answering a question of Bollobas, we show that there exists a minimal percolating set of size 4n^2/33 + o(n^2), but there does not exist one larger than (n + 2)^2/6.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• On slowly percolating sets of minimal size in bootstrap percolation
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Smallest percolating sets in bootstrap percolation on grids
• Largest and smallest minimal percolating sets in trees
• Extremal bounds for bootstrap percolation in the hypercube

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cited In (26)

• Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
• Triggering cascades on undirected connected graphs
• The time of bootstrap percolation with dense initial sets for all thresholds
• Minimum degree conditions for small percolating sets in bootstrap percolation
• Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• Largest and smallest minimal percolating sets in trees
• On the \(P_3\)-hull number of Kneser graphs
• Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
• On slowly percolating sets of minimal size in bootstrap percolation
• The time of bootstrap percolation with dense initial sets
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Neighborhood growth dynamics on the Hamming plane
• Deterministic bootstrap percolation on trees
• A cube dismantling problem related to bootstrap percolation
• The maximum time of 2-neighbor bootstrap percolation: complexity results
• Smallest percolating sets in bootstrap percolation on grids
• Bootstrap percolation in strong products of graphs
• Minimal contagious sets in random regular graphs
• Target set selection with maximum activation time
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• On the maximum running time in graph bootstrap percolation

This page was built for publication: Minimal percolating sets in bootstrap percolation

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