Minimal percolating sets in bootstrap percolation

MaRDI QIDQ1010903zbMATH OpenFDO

Authors Robert Morris

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/math/0702370, https://eudml.org/doc/117288, http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r2.html

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(26)

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