2025/06/23 by Brešar, Boštjan, Hedžet, Jaka, Henning, Michael A. · 1 citation
#05C35 #05C76 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2506.18345
Given a graph G and assuming that some vertices of G are infected, the r-neighbor bootstrap percolation rule makes an uninfected vertex v infected if v has at least r infected neighbors. The r-percolation number, m(G, r), of G is the minimum cardinality of a set of initially infected vertices in G such that after continuously performing the r-neighbor bootstrap percolation rule each vertex of G eventually becomes infected. In this paper, we continue the study of polluted bootstrap percolation introduced and studied by Gravner and McDonald [Bootstrap percolation in a polluted environment. J. Stat Physics 87 (1997) 915--927] where in this variant some vertices are permanently in the non-infected state. We study an extremal (combinatorial) version of the bootstrap percolation problem in a polluted environment, where our main focus is on the class of grid graphs, that is, the Cartesian product Pm \square Pn of two paths Pm and Pn on m and n vertices, respectively. Given a number of polluted vertices in a Cartesian grid we establish a closed formula for the minimum 2-neighbor bootstrap percolation number of the polluted grid, and obtain a lower bound for the other extreme.