Hostname: page-component-7b9c58cd5d-dlb68 Total loading time: 0 Render date: 2025-03-15T12:16:08.511Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Critical Value for ‘Percolation’ of Minimum-Weight Trees in the Mean-Field Distance Model

Published online by Cambridge University Press:  01 March 1998

DAVID ALDOUS
DAVID ALDOUS
Affiliation:
Department of Statistics, University of California, Berkeley, CA 94720, USA (e-mail: aldous@stat.berkeley.edu) (http://www.stat.berkeley.edu/users/aldous)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M(c, n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M(c, n) makes the transition from o(n) to Ω(n) around some critical value c(0), which can be specified in terms of a fixed point of a mapping on probability distributions.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 7 , Issue 1 , March 1998 , pp. 1 - 10
Copyright
1998 Cambridge University Press