**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.