On slowly percolating sets of minimal size in bootstrap percolation
type: Item
instance of: scholarly article
title: On slowly percolating sets of minimal size in bootstrap percolation
zbMATH Open document ID: 1298.05297
author: Michał Przykucki
author: F. S. Benevides
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: v20i2p46
review text: 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\).
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 92D30
zbMATH DE Number: 6330254
zbMATH Keywords: bootstrap percolation
zbMATH Keywords: grid
zbMATH Keywords: maximum time
MaRDI profile type: Publication
cites work: Metastability effects in bootstrap percolation
cites work: The sharp threshold for bootstrap percolation in all dimensions
cites work: Random disease on the square grid
cites work: Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
cites work: The time of bootstrap percolation with dense initial sets
cites work: Sharp metastability threshold for two-dimensional bootstrap percolation
cites work: Minimal percolating sets in bootstrap percolation
cites work: Maximal percolation time in hypercubes under 2-bootstrap percolation
cites work: Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
cites work: Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
description: scientific article; zbMATH DE number 6330254