Line-of-sight percolation

Journal article

Given $\omega\ge 1$, let $Z^2_{(\omega)}$ be the graph with vertex set $Z^2$ in which two vertices are joined if they agree in one coordinate and differ by at most $\omega$ in the other. (Thus $Z^2_{(1)}$ is precisely $Z^2$.) Let $p_c(\omega)$ be the critical probability for site percolation in $Z^2_{(\omega)}$. Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that $\lim_{\omega\to\infty} \omega\pc(\omega)=\log(3/2)$. We also prove analogues of this result on the $n$-by-$n$ grid and in higher dimensions, the latter involving interesting connections to Gilbert's continuum percolation model. To prove our results, we explore the component of the origin in a certain non-standard way, and show that this exploration is well approximated by a certain branching random walk.

Authors: Bollobas, B; Janson, S; Riordan, O

• Publication status: Published
• Journal: Combinatorics, Probability and Computing 18 (2009), 83--106.
• Volume: 18
• Issue: 1-2
• Pages: 83-106
• Publication date: 2007-02-02
• DOI: 10.1017/S0963548308009310
• EISSN: 1469-2163
• ISSN: 0963-5483
• Language: English
• Keywords: math.PR; 60K35; 05C80; math.CO