Line Percolation

Balister, Paul; Bollobás, Béla; Lee, Jonathan D.; Narayanan, Bhargav P.
We study a geometric bootstrap percolation model, line percolation, on the d-dimensional grid [n]\^{}d. In line percolation with infection parameter r, infection spreads from a subset A of initially infected lattice points as follows: if there is an axis parallel line L with r or more infected lattice points on it, then every lattice point of [n]\^{}d on L gets infected and we repeat this until the infection can no longer spread. The elements of the set A are usually chosen independently, with some density p, and the main question is to determine p\_c(n,r,d), the critical density at which percolation (infection of the entire grid) becomes likely. In this paper, we determine p\_c(n,r,2) up to a factor of 1+o(1) and p\_c(n,r,3) up to multiplicative constants as n tends to infinity for every fixed natural number r. We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter.
Research areas:
Type of Publication:
Hits: 5714

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information