Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T11:18:05.907Z 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: [email protected]) (http://www.stat.berkeley.edu/users/aldous)
Get access Rights & Permissions [Opens in a new window]

Abstract

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)