Premium
Line percolation
Author(s) -
Balister Paul,
Bollobás Béla,
Lee Jonathan,
Narayanan Bhargav
Publication year - 2018
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20755
Subject(s) - multiplicative function , mathematics , lattice (music) , grid , percolation (cognitive psychology) , percolation threshold , combinatorics , lattice constant , integer lattice , percolation theory , statistical physics , physics , condensed matter physics , mathematical analysis , geometry , topology (electrical circuits) , electrical resistivity and conductivity , quantum mechanics , diffraction , neuroscience , acoustics , biology , half integer
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 ] dof 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 ] don 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 determinep c ( n , r , d ) , the density at which percolation (infection of the entire grid) becomes likely. In this paper, we determinep c ( n , r , 2 ) up to a multiplicative factor of 1 + o ( 1 ) andp 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.