# Maximum percolation time in two-dimensional bootstrap percolation

F. Benevides, M. Przykucki

*SIAM Journal on Discrete Mathematics* 29, 224 (2015)

#percolation#discretemath#graphtheory

What is the maximum percolation time in a two-dimensional grid?

We consider a classic model known as bootstrap percolation on the n × 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 2 already infected neighbours. 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 We consider a classic model known as bootstrap percolation on the n × 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 2 already infected neighbours. 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 13n^2/18 +O(n).

#### A phase transition creates the geometry of the continuum from discrete space

R. Farr, T. Fink

Sub. to *Physical Review E*

#### The statistical physics of real-world networks

G. Cimini, T. Squartini, F. Saracco, D. Garlaschelli, A. Gabrielli, G. Caldarelli

*Nature Reviews Physics*

#### On defining the Hamiltonian beyond quantum theory

D. Branford, O. Dahlsten, A. Garner

*Foundations of Physics*

#### Reconstructing grain-shape statistics from electron back-scatter diffraction microscopy

R. Farr, Z. Vukmanovic, M. Holness, E. Griffiths

*Physical Review Materials*

#### Tackling information asymmetry in networks: a new entropy-based ranking index

P. Barucca, G. Caldarelli, T. Squartini

*Journal of Statistical Physics*

#### Eigenvalues of subgraphs of the cube

B. Bollobás, J. Lee, S. Letzter

*European Journal of Combinatorics*

#### Maximum one-shot dissipated work from Rényi divergences

N. Halpern, A. Garner, O. Dahlsten, V. Vedral

*Physical Review E *

123 / 123 papers