The random minimal spanning tree in high dimensions

• 成果类型: Article
• 署名作者: Penrose, MD
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• 发表日期: 1996
• 页码: 1903-1925
• 关键词: percolation; probability

摘要

For the minimal spanning tree on n independent uniform points in the d-dimensional unit cube, the proportionate number of points of degree k is known to converge to a limit alpha(k,d) as n --> infinity. We show that alpha(k,d) converges to a limit alpha(k) as d --> infinity for each k. The limit alpha(k) arose in earlier work by Aldous, as the asymptotic proportionate number of vertices of degree k in the minimum-weight spanning tree on k vertices, when the edge weights are taken to be independent, identically distributed random variables. We give a graphical alternative to Aldous's characterization of the alpha(k).