UC Berkeley

In the mean field (or random link) model there are n points and inter-point distances are independent random variables. For 0 < ℓ < ∞ and in the n → ∞ limit, let δ(ℓ) = 1/n times the maximum number of steps in a path whose average step-length is ≤ ℓ. The function δ(ℓ) is analogous to the percolation function in percolation theory: there is a critical value ℓ* = e-1 at which δ(·) becomes non-zero, and (presumably) a scaling exponent β in the sense δ(ℓ) equivalent to sign (ℓ - ℓ*) β. Recently developed probabilistic methodology (in some sense a rephrasing of the cavity method developed in the 1980s by Mézard 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 β = 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. © 2005 The Royal Society.