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

Source 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.