Mathematics – Probability
Scientific paper
2007-02-02
Combinatorics, Probability and Computing 18 (2009), 83--106.
Mathematics
Probability
Revised and expanded (section 2.3 added). To appear in Combinatorics, Probability and Computing. 27 pages, 4 figures
Scientific paper
10.1017/S0963548308009310
Given $\omega\ge 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 $\omega$ in the other. (Thus $Z^2_{(1)}$ is precisely $Z^2$.) Let $p_c(\omega)$ be the critical probability for site percolation in $Z^2_{(\omega)}$. Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that $\lim_{\omega\to\infty} \omega\pc(\omega)=\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.
Bollobas Bela
Janson Svante
Riordan Oliver
No associations
LandOfFree
Line-of-sight percolation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Line-of-sight percolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Line-of-sight percolation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-676127