Update, October 2011.
This preprint by Jian Ding gives a detailed analysis of this question, showing that
it is powers of log(n) instead of powers of n that are relevant to the scaling window behavior.
This page is no longer relevant; refer to Ding's preprint to see what is now known
and what is still an open problem.
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.