A strong law for the longest edge of the minimal spanning tree. (English) Zbl 0944.60015

Penrose, Mathew D.

Ann. Probab. 27, No. 1, 246-260 (1999).

Let \(f\) be a continuous density on a connected compact support set \(\Omega\) in \(\operatorname{Re}^{d}\) \((d \geq 2)\) that has smooth boundary \(\partial \Omega\). Assume \(f_{0}=\) \(\min_{\Omega}f > 0\) and define \(f_{1}=\) \(\min_{\partial \Omega}f\). Let \(\underline{X}_{n}=\) \((X_1, \dots, X_n)\) be a random sample from \(f\) and define \(Y_n\) to be the smallest \(r\) such that the union of balls of diameter \(r\) centered at \(X_1, \ldots, X_n\) is connected. This \(Y_n\) also represents the maximum edge-length of a minimum spanning tree of the vertex set \(\underline{X}_n\). It is shown that, as \(n \to \infty\), \(n \theta Y_{n}^{d}/\log n \to\) \(\max\{f_{0}^{-1}, 2(1-d^{-1})f_{1}^{-1}\}\) a.s., where \(\theta\) is the volume of the unit ball. This result disproves a conjecture made by E. Tabakis [in: From data to knowledge: theoretical and practical aspects of classification, data analysis, and knowledge organization, 222-230 (1996; Zbl 0897.62063)] that the limit is free of \(f\).

Reviewer: H.N.Nagaraja (Columbus/Ohio)

MSC:

60D05	Geometric probability and stochastic geometry
60G70	Extreme value theory; extremal stochastic processes
60F15	Strong limit theorems

Keywords:

geometric probability; connectedness; extreme values

Citations:

Zbl 0897.62063

References:

[1]	APPEL, M. J. B. and RUSSO, R. P. 1996. The connectivity of a graph on uniform points in d 0, 1. Preprint, Univ. Iowa.
[2]	APPEL, M. J. B. and RUSSO, R. P. 1997. The minimum vertex degree of a graph on uniform d points in 0, 1. Adv. in Appl. Probab. 29 582 594. JSTOR: · Zbl 0899.05061 · doi:10.2307/1428077
[3]	DUGUNDJI, J. 1966. Topology. Allyn and Bacon, Boston. · Zbl 0144.21501
[4]	GRIMMETT, G. 1989. Percolation. Springer, New York. · Zbl 0691.60089
[5]	KLARNER, D. A. 1967. Cell growth problems. Canad. J. Math. 19 851 863. · Zbl 0178.00904
[6]	PENROSE, M. D. 1998. Extremes for the minimal spanning tree on normally distributed points. Adv. in Appl. Probab. 30 628 639. · Zbl 0919.60025 · doi:10.1239/aap/1035228120
[7]	PENROSE, M. D. 1997. The longest edge of the random minimal spanning tree. Ann. Appl. Probab. 7 340 361. · Zbl 0884.60042 · doi:10.1214/aoap/1034625335
[8]	PENROSE, M. D. 1997. On k-connectivity for a geometric random graph.
[9]	PENROSE, M. D. 1997. A strong law for the largest nearest-neighbour link between random points. J. London Math. Soc. · Zbl 0955.60009 · doi:10.1112/S0024610799008157
[10]	TABAKIS, E. 1996. On the longest edge of the minimal spanning tree. In From Data toKnowledge W. Gaul and D. Pfeifer, eds. 222 230. Springer, New York. · Zbl 0897.62063