The time of bootstrap percolation for dense initial sets

In r-neighbour bootstrap percolation on the vertex set of a graph G, vertices are initially infected independently with some probability p. At each time step, the infected set expands by infecting all uninfected vertices that have at least r infected neighbours. We study the distribution of the time...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-10
Main Authors: Bollobás, Béla, Holmgren, Cecilia, Smith, Paul, Uzzell, Andrew J
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Percolation
Toruses
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In r-neighbour bootstrap percolation on the vertex set of a graph G, vertices are initially infected independently with some probability p. At each time step, the infected set expands by infecting all uninfected vertices that have at least r infected neighbours. We study the distribution of the time t at which all vertices become infected. Given t = t(n) = o(log n/log log n), we prove a sharp threshold result for the probability that percolation occurs by time t in d-neighbour bootstrap percolation on the d-dimensional discrete torus T_n^d. Moreover, we show that for certain ranges of p = p(n), the time at which percolation occurs is concentrated either on a single value or on two consecutive values. We also prove corresponding results for the modified d-neighbour rule.
ISSN:2331-8422