Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue European Journal of Combinatorics Année : 2023

Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation

Résumé

Let r ≥ 1 be any non negative integer and let G = (V, E) be any undirected graph in which a subset D ⊆ V of vertices are initially infected. We consider the process in which, at every step, each non-infected vertex with at least r infected neighbours becomes infected and an infected vertex never becomes non-infected. The problem consists in determining the minimum size s r (G) of an initially infected vertices set D that eventually infects the whole graph G. This problem is closely related to cellular automata, to percolation problems and to the Game of Life studied by John Conway. Note that s 1 (G) = 1 for any connected graph G. The case when G is the n × n grid, G n×n , and r = 2 is well known and appears in many puzzle books, in particular due to the elegant proof that shows that s 2 (G n×n) = n for all n ∈ N. We study the cases of square grids, G n×n , and tori, T n×n , when r ∈ {3, 4}. We show that s 3 (G n×n) = n 2 +2n+4 3 for every n even and that n 2 +2n 3 ≤ s 3 (G n×n) ≤ n 2 +2n 3 + 1 for any n odd. When n is odd, we show that both bounds are reached, namely s 3 (G n×n) = n 2 +2n 3 if n ≡ 5 (mod 6) or n = 2 p-1 for any p ∈ N * , and s 3 (G n×n) = n 2 +2n 3 + 1 if n ∈ {9, 13}. Finally, for all n ∈ N, we give the exact expression of s 3 (T n×n).
Fichier principal
Vignette du fichier
virality__contamination_game_.pdf (1.1 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04368240 , version 1 (31-12-2023)

Licence

Paternité

Identifiants

Citer

Fabricio Benevides, Jean-Claude Bermond, Hicham Lesfari, Nicolas Nisse. Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation. European Journal of Combinatorics, 2023, pp.18. ⟨10.1016/j.ejc.2023.103801⟩. ⟨hal-04368240⟩
28 Consultations
7 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More