3-Neighbor bootstrap percolation on two-dimensional grids
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "3-Neighbor bootstrap percolation on two-dimensional grids".
Emmy: Here's the gist of the paper. In this paper, the authors exactly determine the size of the minimum percolating set for 3-neighbor bootstrap percolation on rectangular grid graphs and toroidal grids The results extend earlier work and provide precise answers in many divisibility cases Problem Definition and Scope The process is defined as a vertex becoming infected if at least three of its neighbors are infected, where an initial configuration percolates if eventually all vertices are infected The core question addressed is determining the minimum possible cardinality of a percolating set under k-neighbor bootstrap on graphs G.
Ada: The authors focus specifically on rectangular grids Pm□Pn and toroidal grids Cm□Cn Results for Rectangular Grids The first main result fully determines s3(m, n) for all pairs m, n where it was not previously known The authors establish a lower bound LB based on the parity of m and n Theorem 2.1 states that s3(m, n) ≥ LB for all pairs m, n Specific cases are resolved in Theorem 1.4 for s3(4, n) and Theorem 2.5 for s3(6, n) Results for Toroidal Grids For the toroidal grids Cm□Cn, upper and lower bounds are proven which are at most one apart Theorem 1.7 states that t3(m, n) = mn + 1/3 for many cases where m, n ≥ 5 Theorem 1.8 provides bounds of the form mn + 1/3 ≤ t3(m, n) ≤ mn + 1/3 + 1 for remaining cases The lower bound for all m, n is established by Theorem 3.1 as t3(m, n) ≥ mn + 1/3 General Bounds and Tools The paper introduces tools such as the Four Rectangle Trick to establish upper bounds for s3(m, n) The proof for Theorem 1.5 uses these tools to find a matching upper bound to the lower bound values whenever m, n ≥ 7 Further theorems establish bounds like t3(m, n) ≤ mn + 2/3 for specific conditions on m and n The analysis involves detailed case-by-case examination based on the values of m and n modulo 6 Open Problems The authors pose open questions regarding the strong product Pm ⊠ Pn under the same process Specifically, they ask about the minimum number of infected cells needed to fully infect Pm ⊠Pn They also question whether other cases exist where t3(m, n) > mn + 1/3 for the toroidal grid The paper concludes with several references to prior work in graph theory and percolation References
1: Sarah Spence Adams, Denise Sakai Troxell, and S.
Emmy: Luke Zinnen.
Ada: Dynamic monopolies and feedback vertex sets in hexagonal grids
2: Joan Adler and Uri Lev.
Paper summary: Ada: So we're looking at this paper about "three-Neighbor bootstrap percolation on two-dimensional grids" <ref:2608.06133#pg1,3-Neighbor bootstrap percolation on two-dimensional grids>. Essentially, the authors are exactly figuring out the size of the smallest set of starting infected vertices that will eventually infect every single cell on these grids.
Emmy: It sounds like they're tackling a problem where a vertex gets infected if three of its neighbors are already infected, and they're doing this for rectangular grids and toroidal grids. The main goal is to determine the size of this minimum set, which they call s3(m, n) for the rectangular grid and t3(m, n) for the toroidal grid.
Kolya: That sounds like a very hard problem because determining that minimum size is NP-hard even for just two neighbors on grids of bounded degree seven eight eleven <ref:2608.06133#pg2,of bounded degree 7, 8, 11>. So they're going into some deep territory there.
Ada: Right, and what they claim is that this paper fully determines s3(m, n) for all pairs of dimensions m and n where it wasn't known before. They set a lower bound based on the parity of those dimensions using this expression LB which is mn plus m plus n over three for odd dimensions, or with some slight adjustments if one or both are even.
Emmy: And they also look at the toroidal grids,Cm□Cn, where they prove that the upper and lower bounds they find are at most one apart in many cases. They manage to determine the answer precisely in a lot of those divisibility cases too.
Kolya: I'm interested in how these results might translate to something more practical than just math on a page. If we think about the toroidal grids, that's like wrapping things around, which is often relevant for things that tile or repeat.
Ada: Exactly. And while they give some precise answers for specific small cases, like s3(four n) in Theorem one point four and s3(six n) in Theorem two point nine, the real work seems to be getting those general formulas right for all m and n <ref:2608.06133#pg3>.
Emmy: The paper introduces some tools they use to establish upper bounds for rectangular grids called the Four Rectangle Trick, which they then use in Theorem one point five to find a matching upper bound for the lower bound values whenever m and n are seven or larger <ref:2608.06133#pg3>.
Kolya: And what this means is that even with these complex bounds, the paper is still using these tools to show that s3(m, n) equals LB except for specific residue classes modulo six. That's a pretty tight characterization of when things deviate from the simple lower bound.
Ada: It sounds like they've been very systematic about this case-by-case examination based on the values of m and n modulo six, which is what they use to figure out those exceptions. They also established some bounds for the toroidal grids, like t3(m, n) less than or equal to mn plus two over three under certain conditions.
Paper summary: Emmy: That gap of size one between the upper and lower bounds they found for the toroidal case is interesting because it tells you how much uncertainty there is in that specific problem when you're dealing with wrapping grids.
Kolya: If we think about what this says about percolation in general, it suggests that for these grid structures, the structure of the dimensions m and n modulo six really dictates whether you hit the theoretical minimum or if you have to add one more cell.
Ada: That's a big point because it tells us exactly where the structural constraints of the grid topology matter most when trying to find that minimum set size. And they also posed some open questions about stronger products of grids, like Pm times Pn.
Emmy: And those open questions about the strong product are interesting because they suggest that even with these precise answers for simple grids, there might be deeper complexity when you start combining them in different ways. It points toward future research directions for this area.
Kolya: So what the paper really does is provide a very precise answer for rectangular grids and tight bounds with a gap of one on toroidal grids, all by carefully analyzing the relationship between the dimensions and some fundamental lower bound LB.
Ada: It’s about nailing down those exact values for s3(m, n) and t3(m, n), extending earlier work done by Dukes, Noel, and Romer. It's a lot of detailed case analysis to get there.
Emmy: And the authors are very clear about their limitations too; they mention that they are focusing specifically on rectangular grids and tori, so we shouldn't expect these exact results to apply to other types of graphs like random graphs or trees.
Kolya: That's a fair limitation because bootstrap percolation is a graph-theoretic model, and the structure of the graph is everything. It’s about the connectivity imposed by that grid layout.
Ada: So, in conclusion, this paper provides an exact determination for rectangular grids and strong bounds with a gap of one for toroidal grids on three-neighbor bootstrap percolation. It's a lot of detailed number theory applied to percolation theory.
Emmy: It shows how structure matters when you look at these infection models on these specific graph types. We need to keep an eye on those open questions about the strong product because that’s where the next layer of complexity lies.
Kolya: Yeah, so if you're interested in the probabilistic side, this means that for large grids, we can get very close to these exact bounds even though finding the absolute minimum is hard. That's what I found interesting about their bounds on t3(m, n).
Conclusion: Ada: So we've been looking at how complicated it is to find the absolute minimum number of cells you need to start infected so that eventually every single cell gets infected on these grids and toroidal shapes.
Emmy: Right, this paper, "three-Neighbor bootstrap percolation on two-dimensional grids," by Fabricio Benevides and others, they are basically giving us the exact answers for those minimum sizes.
Ada: Exactly. They've worked through all the cases for rectangular grids and found a way to precisely determine that number—the size of that smallest starting set—for almost every possible pair of dimensions you can pick.
Emmy: And for the toroidal grids, they didn't just give some rough estimate; they proved that their upper and lower bounds are at most one apart in many places, and they nailed the exact answer in a lot of those cases.
Ada: It means for these specific types of grids, you can get very close to knowing the minimum size without having to test every single starting configuration.
Emmy: That's the point. The structure of the grid—whether it’s rectangular or toroidal—really dictates how much flexibility there is in your initial setup before you hit that percolation threshold.
Ada: It shows that even though finding these minimum sets is a hard problem generally, for these specific two-dimensional structures, we can get very specific numbers and tight bounds.
Emmy: And they didn't stop at just the grids; they looked ahead to things like the strong product of grids and asked some tough questions about that.
Ada: That points toward what comes next in this field, because once you solve the simple cases like these, you start looking at how those pieces fit together in more complex ways.
Emmy: Exactly. And that's where we're going next, because understanding how these different grid structures combine is the real challenge for the researchers.
Department of Math. & Appl. Math., Virginia Commonwealth University · Department of Theoretical Computer Science, Czech Technical University in Prague
math.CO, math.PR
Submitted: 2026-08-06
Updated: 2026-11-10
Comments: 25 pages, 14 figures
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Importance score: 78/100
The gist: In this paper, the authors exactly determine the size of the minimum percolating set for 3-neighbor bootstrap percolation on rectangular grid graphs and toroidal grids The results extend earlier work…
Key concepts
- 3-neighbor bootstrap percolation
- This is a graph-theoretic infection model where a vertex becomes infected if at least three of its immediate neighbors are already infected. The process continues until no new vertices can be infected, and the goal is to find the smallest starting set that causes the entire grid to eventually become infected.
- Minimum percolating set size
- This refers to finding the absolute smallest number of vertices you need to initially select as 'infected' so that, through repeated infection based on the 3-neighbor rule, every single vertex in the entire grid gets infected. This is an extremal question in percolation theory.
- Rectangular and Toroidal Grids
- The study focuses on two specific types of grid structures: rectangular grids ($P_m imes P_n$) and toroidal grids ($C_m imes C_n$). Rectangular grids have fixed boundaries, while toroidal grids wrap around, meaning the edges connect to the opposite sides.
- Lower and Upper Bounds
- The authors establish mathematical inequalities (lower bounds like $LB$ and upper bounds) for the minimum set size ($s_3(m, n)$ or $t_3(m, n)$). By proving these bounds are very close to each other—often differing by only one unit—they precisely determine the exact size of the minimum set in many specific scenarios.
Terminology
Summary
In this paper, the authors exactly determine the size of the minimum percolating set for 3-neighbor bootstrap percolation on rectangular grid graphs and toroidal grids The results extend earlier work and provide precise answers in many divisibility cases
Problem Definition and Scope
The process is defined as a vertex becoming infected if at least three of its neighbors are infected, where an initial configuration percolates if eventually all vertices are infected The core question addressed is determining the minimum possible cardinality of a percolating set under k-neighbor bootstrap on graphs G. The authors focus specifically on rectangular grids Pm□Pn and toroidal grids Cm□Cn
Results for Rectangular Grids
The first main result fully determines s3(m, n) for all pairs m, n where it was not previously known The authors establish a lower bound LB based on the parity of m and n Theorem 2.1 states that s3(m, n) ≥ LB for all pairs m, n Specific cases are resolved in Theorem 1. p. 5 To prove the lower bound of LB + 1 in the remaining cases, we revisit the proof of Theorem 2. 1 to
note that if there are at least c pairs of adjacent infected vertices, then |S0| ≥ 7n+6+c
3
. For m = 2 see, e. Building on work of Benevides, Bermond, Lesfari, and Nisse [4] who studied the case of m = n,
Dukes, Noel, and Romer showed the following in [12, Theorem 1.Where the paper says it
Where the paper says it
Results for Toroidal Grids
For the toroidal grids Cm□Cn, upper and lower bounds are proven which are at most one apart Theorem 1.7 states that t3(m, n) = mn + 1/3 for many cases where m, n ≥ 5 Theorem 1. p. 0 This extends earlier work of Dukes, Noel, and
Romer. Additionally, we consider the same question for the toroidal grids Cm□Cn, proving
upper and lower bounds which are at most one apart and determining the answer precisely in
many divisibility cases. It is then easy to verify that any uninfected cells in the remaining three columns eventually become infected. To prove the lower bound of LB + 1 in the remaining cases, we revisit the proof of Theorem 2.Where the paper says it
Where the paper says it
General Bounds and Tools
The paper introduces tools such as the Four Rectangle Trick to establish upper bounds for s3(m, n) The proof for Theorem 1.5 uses these tools to find a matching upper bound to the lower bound values whenever m, n ≥ 7 Further theorems establish bounds like t3(m, n) ≤ mn + 2/3 for specific conditions on m and n The analysis involves detailed case-by-case examination based on the values of m and n modulo 6
Open Problems
The authors pose open questions regarding the strong product Pm ⊠ Pn under the same process Specifically, they ask about the minimum number of infected cells needed to fully infect Pm ⊠Pn They also question whether other cases exist where t3(m, n) > mn + 1/3 for the toroidal grid The paper concludes with several references to prior work in graph theory and percolation
References
[1] Sarah Spence Adams, Denise Sakai Troxell, and S. Luke Zinnen. Dynamic monopolies and feedback vertex sets in hexagonal grids
[2] Joan Adler and Uri Lev. Bootstrap percolation: Visualizations and applications
[3] Gary Antonick. B´ela Bollob´as: The Spread of Infection on a Square Grid
[4] Fabricio Benevides, Jean-Claude Bermond, Hicham Lesfari, and Nicolas Nisse. Minimum lethal sets in grids and tori under 3-neighbour bootstrap percolation
[5] St´ephane Bessy, Stefan Ehard, Lucia Draque Penso, and Dieter Rautenbach. Dynamic monopolies for interval graphs with bounded thresholds
[6] B´ela Bollob´as. The Art of Mathematics: Coffee Time in Memphis
[7] Carmen C. Centeno, Mitre C. Dourado, Lucia Draque Penso, Dieter Rautenbach, and Jayme L. Szwarcfiter. Irreversible conversion of graphs
[8] Ning Chen. On the approximability of influence in social networks
[9] Chun-Ying Chiang, Liang-Hao Huang, Bo-Jr Li, Jiaojiao Wu, and Hong-Gwa Yeh. Some results on the target set selection problem
[10] Will Dolphin and Peter J. Dukes. Three-neighbour bootstrap percolation in thin three-dimensional grids
[11] Paul A. Dreyer and Fred S. Roberts. Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
[12] Peter J. Dukes, Jonathan A. p. 0 We exactly determine the size of the
minimum percolating set for the 3-neighbor bootstrap percolation process on all remaining
open cases for rectangular grid graphs Pm□Pn. This extends earlier work of Dukes, Noel, and
Romer. We exactly determine the size of the
minimum percolating set for the 3-neighbor bootstrap percolation process on all remaining
open cases for rectangular grid graphs Pm□Pn. This extends earlier work of Dukes, Noel, and
Romer.Where the paper says it
Where the paper says it
[13] Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, and Nicola Santoro. Dynamic monopolies in tori
[14] Jaka Hedˇzet and Michael A. Henning. 3-Neighbor bootstrap percolation on grids
[15] Robert Morris. Bootstrap percolation, and other automata
[16] Eric Riedl. Largest and smallest minimal percolating sets in trees
[17] Peter Winkler. Mathematical Puzzles: A Connoisseur’s Collection
Page 1
In the 3-neighbor bootstrap percolation process, a vertex becomes (and remains) infected if at least three of its neighbors are infected We say that an initial configuration of infected vertices percolates if eventually all vertices are infected We exactly determine the size of the minimum percolating set for the 3-neighbor bootstrap percolation process on all remaining open cases for rectangular grid graphs Pm□Pn This extends earlier work of Dukes, Noel, and Romer Additionally, we consider the same question for the toroidal grids Cm□Cn, proving upper and lower bounds which are at most one apart and determining the answer precisely in many divisibility cases
Page 2
Bootstrap percolation is a graph-theoretic infection model whose origins lie in statistical physics It is a simple model of the cellular automata first introduced by Von Neumann, spurred by a suggestion of Ulam We think of some vertices of a graph as being infected, and that this infection spreads over time whenever an uninfected vertex is a neighbor to many (at least k) infected vertices To be precise in our combinatorial setting, we define the k-bootstrap percolation process on a graph G starting from an initially infected set of vertices I0 ⊆ V (G) We then inductively define the set of infected vertices at each successive discrete time step, setting It+1 = It ∪ [x ∈ V (G) − It: N(x) ∩ It ≥ k] We are interested in the long term behavior of these initially infected sets In particular, does the infection stop with some vertices remaining uninfected, or does it spread to eventually infect every vertex? In the latter case, we say that I0 percolates With this long term behavior in mind, we set ⟨I0⟩ = S t≥0 It, and say that I0 percolates when ⟨I0⟩ = V (G) Due to bootstrap percolation’s origins in statistical physics, a great deal of research has investigated the case where I0 is chosen randomly among the vertices of an n-dimensional grid – for a quite general survey, see e. p. 0 With this long term behavior in mind, we
set ⟨I0⟩ =
S
t≥0
It, and say that I0 percolates when ⟨I0⟩ = V (G). Due to bootstrap percolation’s origins in statistical physics, a great deal of research has investigated the case where I0 is chosen randomly among the vertices of an n-dimensional grid – for
a quite general survey, see e.Where the paper says it
Page 3
While this problem sounds innocent, determining the minimum is NP-hard, even in the case of 2-neighbor percolation on graphs of bounded degree [7, 8, 11] Determining the minimum size of a percolating set has been studied for many classes of graphs, including trees [7, 11, 16], chordal graphs [5, 7, 9], hexagonal grids [1], and others In this manuscript, we focus on rectangular grids and tori For the m × n rectangular grid Pm□Pn, we let sk(m, n) denote the minimum number of initial infected cells required to percolate under the k-neighbor bootstrap percolation process; we use tk(m, n) to denote this minimum on the m × n toroidal grid Cm□Cn Determining s2(n, n), the minimum size of a 2-percolating set on the square grid, is a very well-known special case which has often been given as a puzzle, dating back to at least the 1980s [3, 6, 17] There is an easy perimeter argument showing that s2(n, n) = n; we use this idea in a considerably more general setting in Section 2
Page 4
Recall that LB = ⌈mn+m+n/3⌉ for m, n odd, ⌈mn+m+n/3 + 2/3⌉ if one is even, and ⌈mn+m+n/3 + 4/3⌉ if both are even Our first main result is to fully determine s3(m, n) for all pairs m, n, where it was not previously known We will compare these to a version of a folklore general lower bound which depends on the number of even dimensions For completeness, we provide a proof in Section 2 Rather than repeatedly writing out these cases, we will use the following shorthand: LB:= mn + m + n/3 for m, n odd, mn + m + n/3 + 2/3 for exactly one of m, n even, and mn + m + n/3 + 4/3 for both even We summarize values of s3(m, n) that were previously known Because s3(m, n) = s3(n, m), some values are included implicitly
Page 5
Theorem 1.1 states that s3(m, n) = LB when m ≡ 2 (mod 3) or m ≡ n ≡ 0 (mod 6) Also, s3(1, n) = n, s3(2, n) = n + 2 for n ≥ 2, and s3(3, n) = [ceil(n+1)/2] for n ≥ 3 Theorem 1. p. 1 6], it follows that s3(m, n) = mn+m+n
3 + 1 when m ≡ n ≡ 1
(mod 6) but either m ̸= n or m + 1 is not a power of 2. Before stating our general result, we resolve a few small cases:
Theorem 1.Where the paper says it
Page 6
Theorem 1.5 states that for m, n ≥ 7, s3(m, n) = LB except: s3(m, n) = LB + 1 when m, n ≡ 1 (mod 6) and m, n ≡ 3 (mod 6) (unless m = n = [2k − 1] for some integer k, where the value is determined by Theorem 1. p. 2 For m, n ≥ 7,
s3(m, n) = LB,
except: s3(m, n) = LB + 1 when m, n ≡ 1 (mod 6) and m, n ≡ 3 (mod 6) (unless m = n = 2k − 1
for some integer k, where the value is determined by Theorem 1. In the case of toroidal grids, Flocchini, Lodi, Luccio, Pagli, and Santoro showed the following in
[13]:
Theorem 1.Where the paper says it
Page 7
Theorem 1.7 states that for m, n ≥ 5 and not in certain residue classes, t3(m, n) = mn + 1/3 Theorem 1. p. 1 While this problem sounds innocent, determining the minimum is NP-hard, even in the case of
2-neighbor percolation on graphs of bounded degree [7, 8, 11]. Determining the minimum size of
a percolating set has been studied for many classes of graphs, including trees [7, 11, 16], chordal
graphs [5, 7, 9], hexagonal grids [1], and others.Where the paper says it
Page 8
Theorem 2.1 states that s3(m, n) ≥ LB The proof uses the perimeter argument to derive a lower bound of S0 ≥ mn + m + n/3 + 2a/3 Corollary 2. p. 1 Our first main result is to fully determine s3(m, n) for all pairs m, n, where it was not previously
known. We will compare these to a version of a folklore general lower bound which depends on
the number of even dimensions; for completeness, we provide a proof in Section 2.Where the paper says it
Page 9
Corollary 2.7 gives a lower bound of mn + m + n/3 + 1 when m, n are both odd and certain conditions hold Theorem 2. p. 4 1 gives an answer of 4n+n+4+4
3 =
5n+8
3 =
⌊
5n+8
3
⌋. It remains to show a lower bound of ⌊
5n+5
3
⌋ + 2 for the remaining values of n.Where the paper says it
Page 10
Theorem 2.9 gives bounds for s3(6, n) based on the residue of n modulo 6 Theorem 2. p. 4 Furthermore, if n ≡ 2 (mod 3), Theorem 1. 1 gives an answer of 4n+n+4+4
3 =
5n+8
3 =
⌊
5n+8
3
⌋.Where the paper says it
Page 11
Theorem 2.12 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 0 (mod 6) and n = [n] mod 6
Page 12
Theorem 2.14 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 13
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 14
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 15
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 16
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 17
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 18
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 19
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 20
Theorem 2.15 provides an upper bound t3(m, n) ≤ mn + m + n/3 + 1 when m, n ≥ 7 and m ≡ 4 (mod 6) and n = [n] mod 6
Page 21
Theorem 2.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved system can determine precisely for rectangular grids Pm□Pn, what is s3(m, n), which is
the minimum number of initial infected cells required to percolate under k-neighbor bootstrap on G.
-
The system can calculate the minimum size of a 3-neighbor percolating set for toroidal grids Cm□Cn by determining the exact values in many divisibility cases, as stated:
determining the answer precisely in many divisibility cases.
-
The system can use Theorem 2.6 (Four Rectangle Trick) to find an upper bound for s3(m, n) by calculating
1 + s3(x - 1, y - 1) + s3(m - x, y - 1) + s3(x - 1, n - y) + s3(m − x, n − y)
for any given m and n. -
The system can establish the lower bound for rectangular grids by proving Theorem 2.1:
s3(m, n) ≥ LB,
where LB is defined piecewise based on the parity of m and n:mn + m + n / 3
or variants thereof. -
The system can provide an upper bound for toroidal grids t3(m, n) by using Theorem 1.7:
t3(m, n) = mn + 1 / 3
for most pairs of m and n where they are not excluded by the specified conditions on parity and modulo 6. -
The system can determine bounds for specific cases like s3(4, n) by applying Theorem 2.4:
s3(4, n) = floor(5n + 5 / 3) + 1 when n = 7 or n mod 3 = 2 and s3(4, n) = floor(5n + 5 / 3) + 2 otherwise.
-
The system can calculate t3(m, n) for toroidal grids under specific conditions using Theorem 1.8:
mn + 1 / 3 ≤ t3(m, n) ≤ mn + 1 / 3 + 1
when the dimensions fall into certain parity or modulo conditions. -
The system can utilize complex constructions from Theorems 2.5 and later to establish upper bounds for s3(6, n) on rectangular grids by using intricate infection patterns described in Figure 1: "For the first n − 3 columns, in columns 1, 5 (mod 6), infect the cells in the odd rows; in columns 2, 4 (mod 6), infect the even rows; in column 3 (mod 6), infect only the first cell; and in columns-2 (mod-6), infect only the last cell. Additionally infect (6,1)."
Abstract
In the 3-neighbor bootstrap percolation process, a vertex becomes (and remains) infected if at least three of its neighbors are infected. We say that an initial configuration of infected vertices percolates if eventually all vertices are infected. We exactly determine the size of the minimum percolating set for the 3-neighbor bootstrap percolation process on all remaining open cases for rectangular grid graphs P m P n. This extends earlier work of Dukes, Noel, and Romer.
Sources
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality