×

zbMATH — the first resource for mathematics

The RSW theorem for continuum percolation and the CLT for Euclidean minimal spanning trees. (English) Zbl 0855.60009
Summary: We prove a central limit theorem for the length of the minimal spanning tree of the set of sites of a Poisson process of intensity \(\lambda\) in \([0,1]^2\) as \(\lambda \to \infty\). As observed previously by Ramey, the main difficulty is the dependency between the contributions to this length from different regions of \([0,1]^2\); a percolation-theoretic result on circuits surrounding a fixed site can be used to control this dependency. We prove such a result via a continuum percolation version of the Russo-Seymour-Welsh theorem for occupied crossings of a rectangle. This RSW theorem also yields a variety of results for two-dimensional fixed-radius continuum percolation already well known for lattice models, including a finite-box criterion for percolation and absence of percolation at the critical point.

MSC:
60D05 Geometric probability and stochastic geometry
60K35 Interacting random processes; statistical mechanics type models; percolation theory
90C27 Combinatorial optimization
60F05 Central limit and other weak theorems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ALDOUS, D. and STEELE, J. M. 1992. Asy mptotics for Euclidean minimal spanning trees on random points. Probab. Theory Related Fields 92 247 258. · Zbl 0767.60005 · doi:10.1007/BF01194923
[2] ALEXANDER, K. S. 1994. Rates of convergence of means for distance-minimizing subadditive Euclidean functionals. Ann. Appl. Probab. 4 902 922. · Zbl 0809.60016 · doi:10.1214/aoap/1177004976
[3] ALEXANDER, K. S. 1995. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 87 104. · Zbl 0827.60079 · doi:10.1214/aop/1176988378
[4] AVRAM, F. and BERTSIMAS, D. 1993. On central limit theorems in geometrical probability. Ann. Appl. Probab. 4 1033 1046. · Zbl 0784.60015 · doi:10.1214/aoap/1177005271
[5] BARBOUR, A. D., HOLST, L. and JANSON, S. 1992. Poisson Approximation. Clarendon, Oxford. · Zbl 0765.60015 · doi:10.1214/aop/1176989531
[6] BEARDWOOD, J., HALTON, J. H. and HAMMERSLEY, J. M. 1959. The shortest path through many points. Proc. Cambridge Philos. Soc. 55 299 327. · Zbl 0118.35601 · doi:10.1017/S0305004100034095
[7] CHAy ES, J. T. and CHAy ES, L. 1986. Percolation and random media. In Critical PhenomZ. ena, Random Sy stems and Gauge Theories K. Osterwalder and R. Stora, eds. 1001 1142. Elsevier, Amsterdam. · Zbl 0661.60120
[8] CHUNG, K. L. 1974. A Course in Probability Theory. Academic Press, New York. · Zbl 0345.60003
[9] EFRON, B. and STEIN, C. 1981. The jackknife estimate of variance. Ann. Statist. 9 586 596. · Zbl 0481.62035 · doi:10.1214/aos/1176345462
[10] FEW, L. 1955. The shortest path and shortest road through n points. Mathematika 2 141 144. · Zbl 0067.12604 · doi:10.1112/S0025579300000784
[11] GRIMMETT, G. R. 1989. Percolation. Springer, New York. · Zbl 0691.60089
[12] HARRIS, T. E. 1960. A lower bound for the critical probability in a certain percolation process. Proc. Cambridge Philos. Soc. 56 13 20. · Zbl 0122.36403 · doi:10.1017/S0305004100034241
[13] HIGUCHI, Y. 1993. Coexistence of infinite -clusters. II. Ising percolation in two dimensions. Probab. Theory Related Fields 97 1 33. · Zbl 0794.60102 · doi:10.1007/BF01199310
[14] JAILLET, P. 1992. Rates of convergence for quasi-additive smooth Euclidean functionals and application to combinatorial optimization problems. Math. Oper. Res. 17 964 980. JSTOR: · Zbl 0770.90052 · doi:10.1287/moor.17.4.964 · links.jstor.org
[15] KESTEN, H. 1982. Percolation Theory for Mathematicians. Birkhauser, Boston. \" · Zbl 0522.60097
[16] KESTEN, H. and LEE, S. 1996. The central limit theorem for weighted minimal spanning trees on random points. Ann. Appl. Probab. 6 495 527. · Zbl 0862.60008 · doi:10.1214/aoap/1034968141
[17] MEESTER, R. and ROY, R. 1996. Continuum Percolation. Cambridge Univ. Press. · Zbl 0866.60088 · doi:10.1002/(SICI)1098-2418(199610)9:3<295::AID-RSA3>3.0.CO;2-S
[18] PREPARATA, F. P. and SHAMOS, M. I. 1985. Computational Geometry: An Introduction. Springer, New York. · Zbl 0575.68059
[19] PRIM, R. C. 1957. Shortest connection networks and some generalizations. Bell Sy stem. Tech. J. 36 1389 1401.
[20] RAMEY, D. B. 1982. A non-parametric test of bimodality with applications to cluster analysis. Ph.D. dissertation, Dept. Statistics, Yale Univ.
[21] REDMOND, C. and YUKICH, J. 1994. Limit theorems and rates of convergence for Euclidean functionals. Ann. Appl. Probab. 4 1057 1073. · Zbl 0812.60033 · doi:10.1214/aoap/1177004902
[22] RHEE, W. T. 1994. Boundary effects in the traveling salesperson problem. Oper. Res. Lett. 16 19 25. · Zbl 0814.90126 · doi:10.1016/0167-6377(94)90017-5
[23] RHEE, W. T. and TALAGRAND, M. 1989. A sharp deviation inequality for the stochastic traveling salesman problem. Ann. Probab. 17 1 8. · Zbl 0682.68058 · doi:10.1214/aop/1176991490
[24] ROY, R. 1990. The Russo Sey mour Welsh theorem and the equality of critical densities and the “dual” critical densities for continuum percolation on 2. Ann. Probab. 18 1563 1575. · Zbl 0719.60119 · doi:10.1214/aop/1176990632
[25] RUSSO, L. 1978. A note on percolation. Z. Wahrsch. Verw. Gebiete 43 39 48. · Zbl 0363.60120 · doi:10.1007/BF00535274
[26] RUSSO, L. 1981. On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete 56 229 237. · Zbl 0457.60084 · doi:10.1007/BF00535742
[27] SEy MOUR, P. D. and WELSH, D. J. A. 1978. Percolation probabilities on the square lattice. Z. In Advances in Graph Theory B. Bollobas, ed. 227 245. North-Holland, Amsterdam. · Zbl 0405.60015 · doi:10.1016/S0167-5060(08)70509-0
[28] STEELE, J. M. 1981. Subadditive Euclidean functionals and nonlinear growth in geometric probability. Ann. Probab. 9 365 376. · Zbl 0461.60029 · doi:10.1214/aop/1176994411
[29] STEELE, J. M. 1981. Complete convergence of short paths and Karp’s algorithm for the TSP. Math. Oper. Res. 6 374 378. JSTOR: · Zbl 0496.90078 · doi:10.1287/moor.6.3.374 · links.jstor.org
[30] STEELE, J. M. 1988. Growth rates of Euclidean minimal spanning trees with power weighted edges. Ann. Probab. 16 1767 1787. · Zbl 0655.60023 · doi:10.1214/aop/1176991596
[31] ZUEV, S. A. and SIDORENKO, A. F. 1985. Continuous models of percolation theory. I, II. Theoret. and Math. Phy s. 62 72 86, 253 265.
[32] LOS ANGELES, CALIFORNIA 90089-1113 E-MAIL: alexandr@math.usc.edu
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.