Growth rates of Euclidean minimal spanning trees with power weighted edges (Q1109408): Difference between revisions
From MaRDI portal
Created claim: Wikidata QID (P12): Q56454188, #quickstatements; #temporary_batch_1711439739529 |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1214/aop/1176991596 / rank | |||
Property / DOI | |||
Property / DOI: 10.1214/AOP/1176991596 / rank | |||
Normal rank |
Latest revision as of 15:30, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Growth rates of Euclidean minimal spanning trees with power weighted edges |
scientific article |
Statements
Growth rates of Euclidean minimal spanning trees with power weighted edges (English)
0 references
1988
0 references
For \(x_ i\in {\mathbb{R}}^ d\), \(1\leq i\leq n\), the family \({\mathcal G}\) of all connected graphs with vertex-set \(V=\{x_ 1,x_ 2,...,x_ n\}\) and edge-set \(E=\{(x_ i,x_ j):1\leq i<j\leq n\}\) is considered. The length of an edge \(e=(x_ i,x_ j)\in E\) is denoted by \(| e|\), where \(| e| =| x_ i-x_ j|\) equals the Euclidean distance from \(x_ i\) to \(x_ j\). Let \(\Psi\) : [0,\(\infty)\to [0,\infty)\) and \[ M(x_ 1,...,x_ n)=\min_{T\in {\mathcal G}} \sum_{e\in T}\Psi (| e|). \] The main result of this paper is the following limit theorem: Suppose that \(X_ i\), \(1\leq i<\infty\), are independent random variables with distribution \(\mu\) having compact support in \({\mathbb{R}}^ d\), \(d\geq 2\). If the monotone function \(\Psi\) satisfies \(\Psi (x)\sim x^{\alpha}\) as \(x\to 0\) for some \(0<\alpha <d\), then with probability 1 \[ \lim_{n\to \infty}n^{-(d-\alpha)/d} M(X_ 1,...,X_ n)=c(\alpha,d)\int_{{\mathbb{R}}^ d}f(x)^{(d-\alpha)/d} dx. \] Here f denotes the density of the absolutely continuous part of \(\mu\) and c(\(\alpha\),d) denotes a strictly positive constant which depends only on the power \(\alpha\) and the dimension d.
0 references
minimal spanning trees
0 references
connected graphs
0 references