Line-of-sight percolation

Abstract

Given $\omega \ge 1$, let $Z_{(\omega )}^2$ 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_{(1)}^2$ is precisely $Z^2$.) Let $p_c(\omega )$ be the critical probability for site percolation in $Z_{(\omega )}^2$. Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that $\lim_{ω\to\infty} ω\pc(ω)=\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.

Revised and expanded (section 2.3 added). To appear in Combinatorics, Probability and Computing. 27 pages, 4 figures

References in corpus (1)

• Continuum percolation with steps in an annulus