Minimal percolating sets in bootstrap percolation

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.

Review text

Summary: In standard bootstrap percolation, a subset \(A\) of the grid \([n]^2\) 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 Bollobás, 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

Cited in

(28)

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)