Line-of-sight percolation

Given ω ≥ 1, let Z 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 ω in the other. (Thus Z 2 (1) is precisely Z 2.) Let pc(ω) be the critical probability for site percolation in Z 2 (ω). Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that limω→ ∞ ω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 process. 1 Introduction an