Line-of-Sight Percolation

Source 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.