Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model

Abstract

In the mean field (or random link) model there are $n$ points and inter-point distances are independent random variables. For $0<\ell <\infty$ and in the $n\to \infty$ limit, let $\delta (\ell )=1/n\times$ (maximum number of steps in a path whose average step-length is $\le \ell$). The function $\delta (\ell )$ is analogous to the percolation function in percolation theory: there is a critical value ${\ell }_{\ast }=e^{-1}$ at which $\delta (\cdot )$ becomes non-zero, and (presumably) a scaling exponent $\beta$ in the sense $\delta (\ell )\asymp (\ell -{\ell }_{\ast }{)}^{\beta }$. Recently developed probabilistic methodology (in some sense a rephrasing of the cavity method of Mezard-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 instead of paths gives scaling exponent $\beta =2$. The new exponents coincide with those found in a different context (comparing optimal and near-optimal solutions of mean-field TSP and MST) and reinforce the suggestion that these scaling exponents determine universality classes for optimization problems on random points.

19 pages

References in corpus (4)

• A survey of max-type recursive distributional equations
• Minimal spanning forests
• The cavity method at zero temperature
• Scaling and Universality in Continuous Length Combinatorial Optimization

Cited by in corpus (6)

• A survey of max-type recursive distributional equations
• Analytical calculation of neighborhood order probabilities for high dimensional Poissonic processes and mean field models
• An efficient algorithm to generate large random uncorrelated Euclidean distances: the random link model
• Replica Symmetry and Combinatorial Optimization
• Percolation of averages in the stochastic mean field model: the near-supercritical regime
• Percolating paths through random points :