On polluted bootstrap percolation in Cartesian gridsBrešar, Boštjan (Avtor) Hedžet, Jaka (Avtor) Henning, Michael A. (Avtor) ojačano pronicanjemrežaonesnaženo okoljepodgraf z odstranjenim vozliščembootstrap percolationgridpolluted environmentvertex deleted subgraphGiven 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 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 [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 ▫$P_m \Box P_n$▫ of two paths ▫$P_m$▫ and ▫$P_n$▫ 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.20262026-08-19 06:48:28Znanstveno delo99516sl