On slowly percolating sets of minimal size in bootstrap percolation (Q396751)

From MaRDI portal
Revision as of 18:09, 20 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
On slowly percolating sets of minimal size in bootstrap percolation
scientific article

    Statements

    On slowly percolating sets of minimal size in bootstrap percolation (English)
    0 references
    14 August 2014
    0 references
    Summary: Bootstrap percolation, one of the simplest cellular automata, can be seen as a model of the spread of infection. In \(r\)-neighbour bootstrap percolation on a graph \(G\) we assign a state, infected or healthy, to every vertex of \(G\) and then update these states in successive rounds, according to the following simple local update rule: infected vertices of \(G\) remain infected forever and a healthy vertex becomes infected if it has at least \(r\) already infected neighbours. We say that percolation occurs if eventually every vertex of \(G\) becomes infected. A well known and celebrated fact about the classical model of 2-neighbour bootstrap percolation on the \(n \times n\) square grid is that the smallest size of an initially infected set which percolates in this process is \(n\). In this paper we consider the problem of finding the maximum time a 2-neighbour bootstrap process on \([n]^2\) with \(n\) initially infected vertices can take to eventually infect the entire vertex set. Answering a question posed by Bollobás we compute the exact value for this maximum showing that, for \(n \geq 4\), it is equal to the integer nearest to \((5n^2-2n)/8\).
    0 references
    bootstrap percolation
    0 references
    grid
    0 references
    maximum time
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references