Maximal percolation time in hypercubes under 2-bootstrap percolation (Q456290): Difference between revisions

Summary: 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\).