Hostname: page-component-74656f9884-skzmx Total loading time: 0 Render date: 2026-11-06T00:21:43.624Z Has data issue: false hasContentIssue false
  • English
  • Français

Line-of-Sight Percolation

Published online by Cambridge University Press:  01 March 2009

BÉLA BOLLOBÁS ,
SVANTE JANSON  and
OLIVER RIORDAN
BÉLA BOLLOBÁS
Affiliation:
Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA and Trinity College, Cambridge CB2 1TQ, UK (e-mail: B.Bollobas@dpmms.cam.ac.uk)
SVANTE JANSON
Affiliation:
Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden (e-mail: svante.janson@math.uu.se)
OLIVER RIORDAN
Affiliation:
Royal Society Research Fellow, Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK; Mathematical Institute, University of Oxford, 24–29 St Giles, Oxford OX1 3LB, UK (e-mail: riordan@maths.ox.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 pc(ω) be the critical probability for site percolation on $\Z^2_{(\omega)}$. Extending recent results of Frieze, Kleinberg, Ravi and Debany, we show that limω→∞ωpc(ω)=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.

References

[1]Aizenman, M., Kesten, H. and Newman, C. M. (1987) Uniqueness of the infinite cluster and related results in percolation. In Percolation Theory and Ergodic Theory of Infinite Particle Systems, Springer, pp. 13–20.Google Scholar
[2]Athreya, K. B. and Ney, P. E. (1972) Branching Processes, Springer, Berlin.CrossRefGoogle Scholar
[3]Balister, P., Bollobás, B. and Walters, M. (2004) Continuum percolation with steps in an annulus. Ann. Appl. Probab. 14 1869–1879.CrossRefGoogle Scholar
[4]Balister, P., Bollobás, B. and Walters, M. (2005) Continuum percolation with steps in the square or the disc. Random Struct. Alg. 26 392–403.CrossRefGoogle Scholar
[5]Bollobás, B., Janson, S. and Riordan, O. (2007) The phase transition in inhomogeneous random graphs. Random Struct. Alg. 31 3–122.Google Scholar
[6]Bollobás, B., Janson, S. and Riordan, O. (2007) Spread-out percolation in $\RR^d$. Random Struct. Alg. 31 239–246.CrossRefGoogle Scholar
[7]Bollobás, B. and Riordan, O. (2006) Percolation, Cambridge University Press.CrossRefGoogle Scholar
[8]Franceschetti, M., Booth, L., Cook, M., Meester, R. and Bruck, J. (2005) Continuum percolation with unreliable and spread-out connections. J. Statist. Phys. 118 721–734.CrossRefGoogle Scholar
[9]Frieze, A., Kleinberg, J., Ravi, R. and Debany, W. (2007) Line-of-sight networks. In Proc. 18th ACM–SIAM Symposium on Discrete Algorithms, pp. 968–977.Google Scholar
[10]Frieze, A., Kleinberg, J., Ravi, R. and Debany, W. Line-of-sight networks. Combin. Probab. Comput., to appear.Google Scholar
[11]Gilbert, E. N. (1961) Random plane networks. J. Soc. Indust. Appl. Math. 9 533–543.Google Scholar
[12]Glaz, J., Naus, J. and Wallenstein, S. (2001) Scan Statistics, Springer.Google Scholar
[13]Hall, P. (1985) On continuum percolation. Ann. Probab. 13 1250–1266.CrossRefGoogle Scholar
[14]Penrose, M. D. (1993) On the spread-out limit for bond and continuum percolation. Ann. Appl. Probab. 3 253–276.Google Scholar
[15]Stevens, W. L. (1939) Solution to a geometrical problem in probability. Ann. Eugenics 9 315–320.CrossRefGoogle Scholar