20.500.12556/DKUM-99516 On polluted bootstrap percolation in Cartesian grids O ojačanem pronicanju v onesnaženih kartezičnih mrežah 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 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. Naj bo ▫$G$▫ graf in predpostavimo, da so nekatera vozlišča v njem okužena. Tedaj pravilo ▫$r$▫-sosednega ojačanega pronicanja povzroči, da neokuženo vozlišče postane okuženo, če ima vsaj ▫$r$▫ okuženih sosedov. Nadalje, ▫$r$▫-sosedno število pronicanja grafa ▫$G$▫ predstavlja najmanjšo kardinalnost množice začetno okuženih vozlišč grafa, ki povzročijo, da so sčasoma vsa vozlišča grafa okužena, ko zaporedoma uporabljamo pravilo ▫$r$▫-sosednega ojačanega pronicanja. V tem članku nadaljujemo obravnavo onesnaženega ojačanega pronicanja, ki sta ga vpeljala Gravner in McDonald [J. Stat Physics 87 (1997) 915--927], pri katerem je nekaj vozlišč grafa ves čas v neokuženem stanju. Raziskujemo ekstremalno (kombinatorično) inačico ojačanega pronicanja v onesnaženem okolju, pri čemer se osredotočamo predvsem na razred kartezičnih mrež, to je, kartezičnih produktov ▫$P_m \Box P_n$▫ poti ▫$P_m$▫ in ▫$P_n$▫ na ▫$m$▫ oziroma ▫$n$▫ vozliščih. Za dano število onesnaženih vozlišč v kartezični mreži predstavimo zaprto formulu za najmanjše ▫$2$▫-sosedno število pronicanja onesnažene mreže in dokažemo spodnjo mejo za ekstremalno vrednost v drugi smeri. ojačano pronicanje mreža onesnaženo okolje podgraf z odstranjenim vozliščem bootstrap percolation grid polluted environment vertex deleted subgraph ojačano pronicanje mreža onesnaženo okolje podgraf z odstranjenim vozliščem true false true Angleški jezik Slovenski jezik Znanstveno delo 2026-08-19 06:48:28 2026-08-20 14:40:07 2026-08-21 03:08:11 0000-00-00 00:00:00 2026 0 0 str. 27-37 št. 1 Letn. 96 Oct. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2025-06-23 0000-00-00 0000-00-00 519.17 287971075 2202-3518 On_polluted_bootstrap_percolation-Bresar-2026.pdf On_polluted_bootstrap_percolation-Bresar-2026.pdf 1 117DAD6A5E6BA694D9176AFB7D06C273 75e0fdc709d3afdc3a629fca3ce5ab58e207cec121df05afac3c2f2c32677466 abe3ccb5-9c94-11f1-b47c-00155d0001be https://dk.um.si/Dokument.php?lang=slv&id=210022 https://ajc.maths.uq.edu.au/pdf/96/ajc_v96_p027.pdf 1 389f037e-9b89-11f1-a6d4-00155d0001be https://dk.um.si/Dokument.php?lang=slv&id=209843 Fakulteta za naravoslovje in matematiko Fakulteta za kemijo in kemijsko tehnologijo 0 0 0