Maximal Percolation Time in Hypercubes Under 2-Bootstrap Percolation

Source abstract

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$.