Scaling window for percolation of averages, in the mean-field setting

Recall the stochastic mean-field model of distance. That is, take n vertices, and for each pair (i,j) let the distance d(i,j) = d(j,i) be random with exponential (mean n) distribution, independently over the {n \choose 2} pairs. For any path \sigma = v_0,v_1,v_2,\ldots,v_l of any length l, write

A_\sigma := l^{-1} \sum_{i=1}^l d(v_{i-1},v_i)

for the average edge-length. Now for each c>0 define

M(n,c) := \max {l: \exists some path $\sigma$ of length $l$ with $A_\sigma \leq c$ } .

It is fairly easy to see that, as n \to \infty for c fixed

M(n,c) = o(\log n) if c < e^{-1}

M(n,c) = \Omega(n) if c > e^{-1} .

PROBLEM. Give more details of the behavior near c = e^{-1}. In particular, do there exist scaling exponents $\alpha, \beta$ such that

n^{-\alpha} M(n,e^{-1} +xn^{- \beta}) \to m(x) in probability

for some deterministic function m(x) satisfying

\lim_{x \to \infty} m(x) = \infty, \lim_{x \to -\infty} m(x) = 0 .

Discussion. The easy fact that the first-order critical value equals $e^{-1}$ is mentioned at the end of this 1998 paper. where the analogous first-order problem for trees is treated in detail. Our problem here asks for second-order behavior, or finite-size scaling in the language of statistical physics. We regard the model as a mean-field analog of first passage percolation. The corresponding questions for ordinary percolation in this mean-field setting are just a rephrasing of questions concerning emergence of the giant component in the Erdos - Renyi random graph process, where the corresponding critical value is 1 and the scaling exponents are \alpha = 2/3, \beta = 1/3.

Returning to our definition of M(n,c), it is natural to conjecture that a broader description of first-order behavior is given by

n^{-1} M(n,c) \to f(c) in probability

where the limit function has

f(c) = 0 iff c \leq e^{-1}

Using our reformulation of the cavity method we can give a non-rigorous derivation of this limit function whose inverse function is pictured here.

History. Posed explicitly in 2003 version of these open problems.