On polluted bootstrap percolation in Cartesian grids

Boštjan Brešar, Jaka Hedžet, Michael A. Henning · 2025

Read On polluted bootstrap percolation in Cartesian grids by Boštjan Brešar, Jaka Hedžet, Michael A. Henning (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-18345.txt.

Introduction

Boštjan Brešar, Jaka Hedžet, and Michael Henning study spread on grids in a 2025 math paper. Their model starts with some infected points on a graph. A healthy point turns infected once at least r of its neighbors are infected, and the process runs until it stalls. In the polluted version, some points stay healthy forever, blocking the spread.

The team asks for the smallest starting set that can still infect every reachable point. They focus on grid graphs, built as the product of two paths. Exact values and bounds for such grids sharpen earlier work on the polluted model from the 1990s. The results feed combinatorics questions about how blockers reshape a spreading process.

Catalog record

CREATORBoštjan Brešar, Jaka Hedžet, Michael A. Henning
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-18345

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On polluted bootstrap percolation in Cartesian grids Boštjan Brešar, Jaka Hedžet, Michael A. Henning Abstract Given a graph G G and assuming that some vertices of G G are infected, the r r -neighbor bootstrap percolation rule makes an uninfected vertex v v infected if v v has at least r r infected neighbors. The r r -percolation number, m ⁡ ( G , r ) m(G,r) , of G G is the minimum cardinality of a set of initially infected vertices in G G such that after continuously performing the r r -neighbor bootstrap percolation rule each vertex of G 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 P m ​ □ ​ P n P_{m}\,\square\,P_{n} of two paths P m P_{m} and P n P_{n} on m m and n n vertices, respectively. Given a number of polluted vertices in a Cartesian grid we establish a closed formula for the minimum 2 2 -neighbor bootstrap percolation number of the polluted grid, and obtain a lower bound for the other extreme. Keywords: bootstrap percolation, grid, polluted environment, vertex deleted subgraph. 2020 Mathematics Subject Classification: 05C35, 05C76. 1 Introduction Bootstrap percolation originated in the work of Chalupa, Leath and Reich in the context of physics of ferromagentism [ 5 ] . The process involving bootstrap percolation seems to be ubiquitous, since it is also closely related to cellular automata [ 12 ] , weak saturation [ 2 ] as well as to the process of obtaining the P_{3} -convex hull [ 4 ] to mention a few well known contexts in which it appears. Given an integer r\geq 2 , the r -neighbor bootstrap percolation process is an update rule in a given graph G , where vertices have two possible states: infected (black) or uninfected (white). From an initial set of infected vertices, an uninfected vertex with at least r infected neighbors becomes infected, while infected vertices never change their state; the central question is whether all vertices of G become infected eventually when this rule is continuously applied. Bootstrap percolation was studied in arbitrary graphs and in various graph classes, while arguably the most popular environment for studying this process are Cartesian grid networks and similar product-like structures; see [ 1 ] for an early study of spreading random disease in square grids. In majority of these studies a parameter p describing the probability that vertices are initially infected is involved, but one can consider also the extremal version of the problem; for instance, see [ 3 ] . In this problem, one looks for a smallest r -percolating set in a graph G , which is a set of vertices in G whose initial infection results in all vertices of G becoming infected after the process is finished. For a given graph G and integer r\geq 2 , the r -percolation number of G , denoted m(G,r) , is the minimum cardinality of an r -percolating set in G , that is, m(G,r)=\min\left\{|S|\colon\,S\subseteq V(G),\>\mbox{$S$ is an $r$-percolating set in $G$}\right\}. (A minimum r -percolating set in G is a r -percolating set S of G satisfying m(G,r)=|S| .) For the Cartesian (square) grid G , the problem of determining m(G,2) is part of folklore; see Bollobás [ 1 ] from 1998. Anyway, several questions concerning m(G,r) remain open, in particular for r>2 , and for grids of bigger dimensions than 2 ; see recent studies [ 6 , 11 ] ; see also a recent study for bounding the threshold for critical probability for the case r=2 in the square grid [ 10 ] . Several variations of bootstrap percolation were considered in the literature. In this note, we are interested in the polluted bootstrap percolation, as introduced by Gravner and McDonald [ 7 ] and studied further in [ 8 , 9 ] . The additional assumption in this variant is that some vertices of a graph are always stuck in the non-infected state. Thus, to every vertex of a graph two parameters, p and q , are assigned, describing probabilities of infection and pollution of its vertices, respectively. The authors in [ 7 ] investigate constants C , which under the condition q<Cp^{2} when p\rightarrow 0 result in the probability that all vertices of a graph are eventually (not) infected. In this note, we propose an extremal (combinatorial) version of the bootstrap percolation problem in polluted environment. Let the vertices of a graph G , as observed in polluted environment, assume one of the three states: infected, uninfected or polluted . If a vertex v\in V(G) is polluted, then it is always in the uninfected state, even if it has enough infected neighbors to satisfy the r -percolation rule. From the definitions it readily follows that m(G,r)=m(G-v,r) for any polluted vertex v . More generally, if A\subset V(G) is the set of polluted vertices in G , then m(G,r)=m(G-A,r) . In other words, considering polluted bootstrap percolation in G can be translated to bootstrap percolation in the induced subgraph of G , where polluted vertices have been removed from G . When considering the r -bootstrap percolation number of a graph G , some vertices that must be included in the initial infection do not contribute much to the spread of the infection (for instance, such vertices are leaves in a tree). The removal of such vertices could therefore reduce the minimum cardinality of a percolating set. On the other hand, vertices of large degree contribute abundantly to the spread of infection; therefore, their removal likely increases the number of vertices needed to infect G . Thus, a natural question arises. Given k\in\mathbb{N} and assuming that G has k polluted vertices, what are the largest and the smallest possible value of m(G,r) ? More precisely, for fixed integers k\in\mathbb{N} and r\geq 2 we are looking for the values of m_{k}^{\min}(G,r)=\min\{m(G-A,r):\,A\subseteq V(G)\,\wedge\,|A|=k\} and m_{k}^{\max}(G,r)=\max\{m(G-A,r):\,A\subseteq V(G)\,\wedge\,|A|=k\}. Our main focus is on the above two invariants when G is the square grid, that is, the Cartesian product of two paths, and when r=2 . The following is our main result: Theorem 1 . If G=P_{m}\square P_{n} is the grid of size m\times n where 2\leq n\leq m , then m_{k}^{\min}(G,2)=\begin{cases}\left\lceil\frac{n+m-\left\lfloor\frac{k}{n}\right\rfloor}{2}\right\rceil,&\text{if }1\leq k\leq(m-n)n;\\ \left\lceil\frac{\left\lceil 2\sqrt{mn-k}\right\rceil}{2}\right\rceil,&\text{if }(m-n)n\leq k\leq mn.\end{cases} 2 Preliminary results In this section, we present some preliminary results on r -neighbor bootstrap percolation in graphs with minimum degree at least r . Lemma 2 . If G is a graph with \delta(G)\geq r , then m(G-x,r)\geq m(G,r) for any x\in V(G) . Proof. Let \delta(G)\geq r and let x\in V(G) . Suppose that m(G-x,r)<m(G,r) and let S be a minimum r -percolating set of G-x . Now, consider the graph G and let the vertices of S be infected. Then eventually S infects the whole G-x , after which

Read the complete text