Maximum percolation time in two-dimensional bootstrap percolation

F. Benevides, M. Przykucki

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

Abstract

We consider a classic model known as bootstrap percolation on the n x n square grid. To each vertex of the grid we assign an initial state, infected or healthy, and then in consecutive rounds we infect every healthy vertex that has at least two already infected neighbors. We say that percolation occurs if the whole grid is eventually infected. In this paper, contributing to a recent series of extremal results in this field, we prove that the maximum time a bootstrap percolation process can take to eventually infect the entire vertex set of the grid is 13n2 /18 + O (n).
Original languageEnglish
Pages (from-to)224-251
Number of pages28
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number1
DOIs
Publication statusPublished - Jan 2015

Keywords

  • bootstrap percolation
  • cellular automaton
  • maximum time

Fingerprint

Dive into the research topics of 'Maximum percolation time in two-dimensional bootstrap percolation'. Together they form a unique fingerprint.

Cite this