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

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

2005-01-19

arxiv.org/abs/cond-mat/0501473v1

Physics

Condensed Matter

Statistical Mechanics

19 pages

Scientific paper

10.1098/rspa.2004.1388

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 $\leq \ell$). The function $\delta(\ell)$ is analogous to the percolation function in percolation theory: there is a critical value $\ell_* = e^{-1}$ at which $\delta(\cdot)$ becomes non-zero, and (presumably) a scaling exponent $\beta$ in the sense $\delta(\ell) \asymp (\ell - \ell_*)^\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.

Affiliated with

Also associated with

No associations

Rating

Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-641093