Line-of-sight percolation
| dc.creator | Bollobas, Bela | |
| dc.creator | Janson, Svante | |
| dc.creator | Riordan, Oliver | |
| dc.date | 2007-02-02 | |
| dc.date | 2008-04-07 | |
| dc.date.accessioned | 2026-07-07T13:12:46Z | |
| dc.date.available | 2026-07-07T13:12:46Z | |
| dc.description | Given $ω\ge 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 $p_c(ω)$ be the critical probability for site percolation in $Z^2_{(ω)}$. Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that $\lim_{ω\to\infty} ω\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 random walk. | |
| dc.description | Revised and expanded (section 2.3 added). To appear in Combinatorics, Probability and Computing. 27 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/math/0702061 | |
| dc.identifier | http://arxiv.org/abs/math/0702061 | |
| dc.identifier | Combinatorics, Probability and Computing 18 (2009), 83--106. | |
| dc.identifier | doi:10.1017/S0963548308009310 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/229676 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 60K35; 05C80 | |
| dc.title | Line-of-sight percolation | |
| dc.type | text |