Connectivity of random geometric graphs related to minimal spanning forests. (English) Zbl 1268.60066

A homogeneous Poisson point process is considered in two or more dimensions and its Euclidean minimal spanning forest is defined by connecting points with an edge unless there is a finite path between them with shorter steps through other points. The minimal spanning forest on a homogeneous Poisson point process is almost surely connected in the plane but is believed not to be in higher dimensions. This paper considers a sequence of graphs with the minimal spanning forest as their intersection, and for these graphs almost sure connectivity is proved to hold in all dimensions and for some point processes that are more general than the homogeneous Poisson point process.


60G55 Point processes (e.g., Poisson, Cox, Hawkes processes)
05C10 Planar graphs; geometric and topological aspects of graph theory
60D05 Geometric probability and stochastic geometry
05C80 Random graphs (graph-theoretic aspects)
82B43 Percolation
Full Text: DOI Euclid


[1] Aldous, D. J. (2009). Which connected spatial networks on random points have linear route-lengths? Preprint. Available at http://arxiv.org/abs/0911.5296v1.
[2] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Prob. 12 , 1454-1508. · Zbl 1131.60003
[3] Aldous, D. J. and Shun, J. (2010). Connected spatial networks over random points and a route-length statistic. Statist. Sci. 25 , 275-288. · Zbl 1329.60009
[4] Aldous, D. and Steele, J. M. (1992). Asymptotics for Euclidean minimal spanning trees on random points. Prob. Theory Relat. Fields 92 , 247-258. · Zbl 0767.60005
[5] Aldous, D. and Steele, J. M. (2004). The objective method: probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures (Encyclopedia Math. Sci. 110 ), ed. H. Kesten, Springer, Berlin. · Zbl 1037.60008
[6] Alexander, K. S. (1995). Percolation and minimal spanning forests in infinite graphs. Ann. Prob. 23 , 87-104. · Zbl 0827.60079
[7] Błaszczyszyn, B. and Yogeshwaran, D. (2014). On comparison of clustering properties of point processes. To appear in Adv. Appl. Prob. · Zbl 1295.60059
[8] Daley, D. J. and Last, G. (2005). Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. Appl. Prob. 37 , 604-628. · Zbl 1078.60038
[9] Gaiselmann, G. et al. (2013). Stochastic 3D modeling of La\(_{0.6}\)Sr\(_{0.4}\)CoO\(_{3-\delta}\) cathodes based on structural segmentation of FIB-SEM images. Computational Materials Sci. 67 , 48-62.
[10] Grimmett, G. (1999). Percolation , 2nd edn. Springer, Berlin. · Zbl 0926.60004
[11] Holroyd, A. E. and Peres, Y. (2003). Trees and matchings from point processes. Electron. Commun. Prob. 8 , 17-27. · Zbl 1060.60048
[12] Last, G. (2006). Stationary partitions and Palm probabilities. Adv. Appl. Prob. 38 , 602-620. · Zbl 1121.60008
[13] Lawler, G. F. (1980). A self-avoiding random walk. Duke Math. J. 47 , 655-693. · Zbl 0445.60058
[14] Liggett, T. M., Schonmann, R. H. and Stacey, A. M. (1997). Domination by product measures. Ann. Prob. 25 , 71-95. · Zbl 0882.60046
[15] Lyons, R., Peres, Y. and Schramm, O. (2006). Minimal spanning forests. Ann. Prob. 34 , 1665-1692. · Zbl 1142.60065
[16] Neuhäuser, D., Hirsch, C., Gloaguen, C. and Schmidt, V. (2012). On the distribution of typical shortest-path lengths in connected random geometric graphs. Queueing Systems 71 , 199-220. · Zbl 1275.60018
[17] Penrose, M. D. and Yukich, J. E. (2001). Central limit theorems for some graphs in computational geometry. Ann. Appl. Prob. 11 , 1005-1041. · Zbl 1044.60016
[18] Penrose, M. D. and Yukich, J. E. (2003). Weak laws of large numbers in geometric probability. Ann. Appl. Prob. 13 , 277-303. · Zbl 1029.60008
[19] Timár, Á. (2006). Ends in free minimal spanning forests. Ann. Prob. 34 , 865-869. · Zbl 1255.60173
[20] Toussaint, G. T. (1980). The relative neighbourhood graph of a finite planar set. Pattern Recognition 12 , 261-268. · Zbl 0437.05050
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.