Line percolation. Issue 4 (8th January 2018) - Balister, Paul; Bollobás, Béla; Lee, Jonathan; Narayanan, Bhargav
Abstract: We study a new geometric bootstrap percolation model, line percolation, on the d ‐dimensional integer grid [ n ] d . In line percolation with infection parameter r, infection spreads from a subset A ⊂ [ n ] d of initially infected lattice points as follows: if there exists 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 density at which percolation (infection of the entire grid) becomes likely. In this paper, we determine p c ( n, r, 2 ) up to a multiplicative factor of 1 + o ( 1 ) and p c ( n, r, 3 ) up to a multiplicative constant as n → ∞ for every fixed r ∈ ℕ . We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter.