Line percolation

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\subset [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\to \infty$ for every fixed $r\in \mathbb{N}$. We also determine the size of the minimal percolating sets in all dimensions and for all values of the infection parameter.

27 pages, Random Structures and Algorithms