Line percolation. Issue 4 (8th January 2018)

• Record Type: Journal Article
• Authors: Balister, Paul; Bollobás, Béla; Lee, Jonathan; Narayanan, Bhargav
• Is Part Of: Random structures & algorithms. Volume 52:Issue 4(2018)
• Page Start: 597
• Page End: 616
• Publication Date: 2018-01-08
• Subjects: bootstrap percolation -- critical probability -- polynomial method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20755
• Languages: English
• ISSNs: 1042-9832

Abstract

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.