Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box
The electronic journal of combinatorics, Tome 25 (2018) no. 3
In $r$-neighbour bootstrap percolation, vertices (sites) of a graph $G$ become "infected" in each round of the process if they have $r$ neighbours already infected. Once infected, they remain such. An initial set of infected sites is said to percolate if every site is eventually infected. We determine the maximal percolation time for $r$-neighbour bootstrap percolation on the hypercube for all $r \geq 3$ as the dimension $d$ goes to infinity up to a logarithmic factor. Surprisingly, it turns out to be $\frac{2^d}{d}$, which is in great contrast with the value for $r=2$, which is quadratic in $d$, as established by Przykucki (2012). Furthermore, we discover a link between this problem and a generalisation of the well-known Snake-in-the-Box problem.
DOI :
10.37236/7307
Classification :
60K35, 05D99, 60C05
Mots-clés : bootstrap percolation, snake-in-the-box, hypercube
Mots-clés : bootstrap percolation, snake-in-the-box, hypercube
Affiliations des auteurs :
Ivailo Hartarsky 1
@article{10_37236_7307,
author = {Ivailo Hartarsky},
title = {Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {3},
doi = {10.37236/7307},
zbl = {1409.60143},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7307/}
}
Ivailo Hartarsky. Maximal bootstrap percolation time on the hypercube via generalised snake-in-the-box. The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/7307
Cité par Sources :