Line-of-sight percolation
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...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2007
|
| _version_ | 1797083724193464320 |
|---|---|
| author | Bollobas, B Janson, S Riordan, O |
| author_facet | Bollobas, B Janson, S Riordan, O |
| author_sort | Bollobas, B |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T01:45:28Z |
| format | Journal article |
| id | oxford-uuid:98454460-37a6-41ce-a92f-fd7af17f8b4d |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:45:28Z |
| publishDate | 2007 |
| record_format | dspace |
| spelling | oxford-uuid:98454460-37a6-41ce-a92f-fd7af17f8b4d2022-03-27T00:05:48ZLine-of-sight percolationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:98454460-37a6-41ce-a92f-fd7af17f8b4dEnglishSymplectic Elements at Oxford2007Bollobas, BJanson, SRiordan, OGiven $\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. |
| spellingShingle | Bollobas, B Janson, S Riordan, O Line-of-sight percolation |
| title | Line-of-sight percolation |
| title_full | Line-of-sight percolation |
| title_fullStr | Line-of-sight percolation |
| title_full_unstemmed | Line-of-sight percolation |
| title_short | Line-of-sight percolation |
| title_sort | line of sight percolation |
| work_keys_str_mv | AT bollobasb lineofsightpercolation AT jansons lineofsightpercolation AT riordano lineofsightpercolation |