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
Rapport (Rapport De Recherche) Année : 2021

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

Résumé

Let $\mathcal{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 following process in which, at every step, each non-infected vertex with at least η infected neighbours becomes infected. The problem consists in determining the minimum size s η (G) of an initially infected vertices set D that eventually infects the whole graph G. Note that s 1 (G) = 1 for any connected graph G. This problem is closely related to cellular automata, to percolation problems and to the Game of Life studied by John Conway. The case when G is the n × n grid G n×n and η = 2 is well known and appears in many puzzles 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 η ∈ {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 4 (G n×n) and of s η (T n×n) when η ∈ {3, 4}.
Fichier principal
Vignette du fichier
virality__contamination_game_(12).pdf (1.08 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03161419 , version 3 (18-03-2021)
hal-03161419 , version 4 (30-03-2021)

Identifiants

  • HAL Id : hal-03161419 , version 3

Citer

Fabricio Benevides, Jean-Claude Bermond, Hicham Lesfari, Nicolas Nisse. Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation. [Research Report] Université Côte d'Azur. 2021. ⟨hal-03161419v3⟩
379 Consultations
223 Téléchargements

Partager

Gmail Facebook X LinkedIn More