Line-of-Sight Percolation

Abstract

Given ω ≥ 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 ω in the other. (Thus $\Z^2_{(1)}$ is precisely $\Z^2$ .) Let p_c(ω) be the critical probability for site percolation on $\Z^2_{(\omega)}$ . Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that lim_ω→∞ωp_c(ω)=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'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.