Maximal percolation time in hypercubes under 2-bootstrap percolation
The electronic journal of combinatorics, Tome 19 (2012) no. 2
Bootstrap percolation is one of the simplest cellular automata. In $r$-bootstrap percolation on a graph $G$, an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least $r$ already infected neighbours become infected. Percolation occurs if eventually every vertex is infected. In this paper we prove that in the case of $2$-bootstrap percolation on the $n$-dimensional hypercube the maximal time the process can take to eventually infect the entire vertex set is $\lfloor \frac{n^2}{3} \rfloor$.
DOI :
10.37236/2412
Classification :
82B43, 68Q80, 60K35
Mots-clés : percolation, \(n\)-dimensional hypercube
Mots-clés : percolation, \(n\)-dimensional hypercube
Affiliations des auteurs :
Michał Przykucki 1
@article{10_37236_2412,
author = {Micha{\l} Przykucki},
title = {Maximal percolation time in hypercubes under 2-bootstrap percolation},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2412},
zbl = {1254.82017},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2412/}
}
Michał Przykucki. Maximal percolation time in hypercubes under 2-bootstrap percolation. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2412
Cité par Sources :