Percolation-like scaling exponents for minimal paths and trees in the stochastic mean field model

In the mean field (or random link) model there are n points and inter-point distances are independent random variables. For 0 < l < infinity and in the n --> infinity limit, let delta(l) = 1/n times the maximum number of steps in a path whose average step-length is less than or equal to l. The function delta(l) is analogous to the percolation function in percolation theory: there is a critical value l(*) = e(-1) at which delta((.)) becomes non-zero, and (presumably) a scaling exponent beta in the sense delta(l) asymptotic to (l - l(*))(beta). Recently developed probabilistic methodology (in some sense a rephrasing of the cavity method developed in the 1980s by Mezard and Parisi) provides a simple, albeit non-rigorous, way of writing down such functions in terms of solutions of fixed-point equations for probability distributions. Solving numerically gives convincing evidence that beta = 3. A parallel study with trees and connected edge-sets in place of paths gives scaling exponent 2, while the analogue for classical percolation has scaling exponent 1. The new exponents coincide with those recently found in a different context (comparing optimal and near-optimal solutions of the mean-field travelling salesman problem (TSP) and the minimum spanning tree (MST) problem), and reinforce the suggestion that scaling exponents determine universality classes for optimization problems on random points.