Growth rates of Euclidean minimal spanning trees with power weighted edges (Q1109408): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Added link to MaRDI item.
links / mardi / namelinks / mardi / name
 

Revision as of 02:06, 31 January 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
    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
    0 references
    minimal spanning trees
    0 references
    connected graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references