3-Neighbor bootstrap percolation on two-dimensional grids

summary

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…

In short

The authors precisely determine the minimum size of an initial infected set required for 3-neighbor bootstrap percolation on rectangular grids and toroidal grids. They establish exact answers for many divisibility cases and provide tight upper and lower bounds, extending previous work in this area.

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 used across episodes

This episode discusses

The paper

3-Neighbor bootstrap percolation on two-dimensional grids · Read on arXiv

Department of Math. & Appl. Math., Virginia Commonwealth University · Department of Theoretical Computer Science, Czech Technical University in Prague

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.

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.

More episodes

← Home