Line-of-sight percolation

Given ω ≥ 1, ℤω2 be the graph with vertex set ℤ2 in which two vertices are joined if they agree in one coordinate and differ by at most in the other. (Thus ℤZ (1)2 is precisely ℤ2.) Let pc(ω) be the critical probability for site percolation on ℤ(ω)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 for the n-by-n grid and in higher dimensions, the latter involving interesting connections to Gilbert\u27s 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. © 2008 Cambridge University Press