pith. sign in

arxiv: 1907.01940 · v1 · pith:7Q7DAWH5new · submitted 2019-07-03 · 🧮 math.CO

Smallest percolating sets in bootstrap percolation on grids

Micha{\l} Przykucki , Thomas Shelton This is my paper

Pith reviewed 2026-05-25 10:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords bootstrap percolationpercolating setsgridsminimal sizeextremal combinatoricsd-neighbourinfection process
0
0 comments X

The pith

The smallest percolating sets in d-neighbour bootstrap percolation on [n]^d have size exactly n^{d-1} for every d at least 1.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the minimal number of initially infected sites needed to eventually infect an entire d-dimensional grid [n]^d under the d-neighbour rule is n to the power d minus one. In this process a site becomes infected only after at least d of its grid neighbors are already infected, and the rule is applied iteratively until closure. The result holds uniformly for all dimensions d and supplies the exact extremal size that had been missing from the literature. The same minimal sets are shown to reach full infection in at most c_d n squared steps for a constant c_d that depends only on dimension.

Core claim

For all d ≥ 1, the size of the smallest percolating sets in d-neighbour bootstrap percolation on [n]^d is n^{d-1}. Additionally, such sets percolate in time at most c_d n^2, for some constant c_d >0 depending on d only.

What carries the argument

d-neighbour bootstrap percolation on the finite grid [n]^d, where a site becomes infected precisely when it has at least d infected neighbors.

If this is right

  • Minimal percolating sets of size exactly n^{d-1} exist in every dimension.
  • These minimal sets reach full infection in at most quadratic time in n.
  • The extremal size of a percolating set is determined solely by dimension and the neighbour threshold d.
  • The quadratic-time bound holds uniformly for all such minimal sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The exact size may serve as a benchmark for minimal seed sets in other monotone cellular automata on grids.
  • Analogous bounds could be sought when the neighbour threshold differs from the dimension.
  • The time bound suggests that closure of these minimal configurations can be computed efficiently for moderate n.

Load-bearing premise

Infection spreads exactly when a site has at least d infected neighbors in the grid.

What would settle it

A set of size smaller than n^{d-1} that eventually infects the whole [n]^d, or a minimal-size set whose closure time exceeds every linear multiple of n squared.

Figures

Figures reproduced from arXiv: 1907.01940 by Micha{\l} Przykucki, Thomas Shelton.

Figure 1
Figure 1. Figure 1: Example showing the spread of infection in [6] [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The infection witness tree of v = (4, 2, 2), IW((4, 2, 2)), when n = 5 and d = 3. Here, the format of the vertex labels is u/tu. The round vertices have labels in the initially infected set A. Observe that, as vertices are included in A based only on the sum of their coordinates and not on the order of their values, any two vertices whose coordinates are a permutation of each other become infected simultan… view at source ↗
Figure 3
Figure 3. Figure 3: Schematic depiction of the level of consecutive vertices on a directed [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
read the original abstract

In this paper we fill in a fundamental gap in the extremal bootstrap percolation literature, by providing the first proof of the fact that for all $d \geq 1$, the size of the smallest percolating sets in $d$-neighbour bootstrap percolation on $[n]^d$, the $d$-dimensional grid of size $n$, is $n^{d-1}$. Additionally, we prove that such sets percolate in time at most $c_d n^2$, for some constant $c_d >0 $ depending on $d$ only.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for all d ≥ 1 the minimal size of a d-neighbour percolating set in the finite grid [n]^d is exactly n^{d-1}. It additionally shows that every such minimal set percolates in at most c_d n^2 steps, where c_d depends only on d.

Significance. If the argument holds, the result supplies the exact extremal function that had been missing from the bootstrap-percolation literature, closing a basic gap between the known upper bound (a coordinate hyperplane) and the conjectured matching lower bound. The quantitative time bound is a useful strengthening that is not implied by the size result alone.

minor comments (2)
  1. [Abstract] The abstract states that the sets 'percolate in time at most c_d n^2' but does not indicate whether the constant c_d is effective or merely existential; a short remark on this point would be helpful.
  2. [§1] The notation [n]^d is used without an explicit sentence defining the vertex set and the neighbour relation; adding one sentence in §1 would remove any ambiguity for readers outside the immediate area.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity

full rationale

This is a pure mathematical proof paper. The central claim (minimal percolating set size equals n^{d-1}) is established by a constructive upper bound (a coordinate hyperplane) and a non-trivial inductive lower bound, both derived directly from the standard d-neighbor bootstrap percolation definition on [n]^d. No parameters are fitted, no predictions are renamed fits, and no load-bearing step reduces to a self-citation or self-definition. The derivation is self-contained against the external benchmark of the process definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard combinatorial definition of d-neighbour bootstrap percolation; no free parameters, new entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • domain assumption d-neighbour bootstrap percolation on the grid [n]^d
    The result is stated for this specific process; the definition is presupposed.

pith-pipeline@v0.9.0 · 5612 in / 993 out tokens · 27518 ms · 2026-05-25T10:07:17.304857+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages · 1 internal anchor

  1. [1]

    Aizenman and J

    M. Aizenman and J. Lebowitz. Metastability effects in bootstrap percolation. Journal of Physics A , 21:3801–3813, 1988

    work page 1988

  2. [2]

    Balister, B

    P. Balister, B. Bollob´ as, R. Johnson, and M. Walters. Random majority percolation. Random Structures and Algorithms , 36:315–340, 2010

    work page 2010

  3. [3]

    Balogh, B

    J. Balogh, B. Bollob´ as, H. Duminil-Copin, and R. Morris. The sharp thresh- old for bootstrap percolation in all dimensions. Transactions of the American Mathematical Society, 364:2667–2701, 2012

    work page 2012

  4. [4]

    Balogh, B

    J. Balogh, B. Bollob´ as, and R. Morris. Bootstrap percolation in high dimen- sions. Combinatorics, Probability and Computing , 37:643–692, 2010

    work page 2010

  5. [5]

    Balogh and G

    J. Balogh and G. Pete. Random disease on the square grid. Random Struc- tures and Algorithms, 13:409–422, 1998

    work page 1998

  6. [6]

    Benevides and M

    F.S. Benevides and M. Przykucki. On slowly percolating sets of minimal size in bootstrap percolation. The Electronic Journal of Combinatorics , 20:1–20, 2013. 10

    work page 2013

  7. [7]

    Benevides and M

    F.S. Benevides and M. Przykucki. Maximum percolation time in two- dimensional bootstrap percolation. SIAM Journal on Discrete Mathematics , 29:224–251, 2015

    work page 2015

  8. [8]

    Chalupa, P.L

    J. Chalupa, P.L. Leath, and G.R. Reich. Bootstrap percolation on a Bethe lattice. Journal of Physics C , 12:L31–L35, 1979

    work page 1979

  9. [9]

    Coja-Oghlan, U

    A. Coja-Oghlan, U. Feige, M. Krivelevich, and D. Reichman. Contagious sets in expanders. In Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ‘15, pages 1953–1987, 2015

    work page 1953

  10. [10]

    Feige, M

    U. Feige, M. Krivelevich, and D. Reichman. Contagious sets in random graphs. The Annals of Applied Probability , 27:2675–2697, 2017

    work page 2017

  11. [11]

    A.E. Holroyd. Sharp metastability threshold for two-dimensional bootstrap percolation. Probability Theory and Related Fields , 125:195–224, 2003

    work page 2003

  12. [12]

    Deterministic bootstrap percolation in high dimensional grids

    H. Huang and C. Lee. Deterministic bootstrap percolation in high dimen- sional grids. Available at https://arxiv.org/abs/1308.6791

    work page internal anchor Pith review Pith/arXiv arXiv

  13. [13]

    R. Morris. Minimal percolating sets in bootstrap percolation. The Electronic Journal of Combinatorics , 16:1–20, 2009

    work page 2009

  14. [14]

    Morrison and J.A

    N. Morrison and J.A. Noel. Extremal bounds for bootstrap percolation inthe- hypercube. Journal of Combinatorial Theory, Series A , 156:61–84, 2018

    work page 2018

  15. [15]

    G. Pete. Personal communication

    work page

  16. [16]

    G. Pete. Disease processes and bootstrap percolation. Master’s thesis, Bolyai Institute, J´ ozsef Attila University, Szeged, 1997. 11

    work page 1997