Maximum percolation time in two-dimensional bootstrap percolation

F. Benevides, M. Przykucki

SIAM Journal on Discrete Mathematics 29, 224 (2015)

#percolation#discretemath#graphtheory

Download the PDF

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

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).

LQ placeholder

Degree-correlations in a bursting dynamic network model

F. Vanni, P. Barucca

Journal of Economic Interaction and Coordination

LQ placeholder

Scale of non-locality for a system of n particles

S. Talaganis, I. Teimouri

Sub. to Physical Review D

LQ placeholder

Changes to Gate Closure and its impact on wholesale electricity prices: The case of the UK

A. Facchini, A. Rubino, G. Caldarelli, G. Liddo

Energy Policy

LQ placeholder

How much can we influence the rate of innovation?

T. Fink, M. Reeves

Science Advances

LQ placeholder

The statistical physics of real-world networks

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

Nature Reviews Physics

LQ placeholder

PopRank: Ranking pages’ impact and users’ engagement on Facebook

A. Zaccaria, M. Vicario, W. Quattrociocchi, A. Scala, L. Pietronero

PLoS ONE

128 / 128 papers