  For a complete graph of size $n$, assign each edge an i.i.d. exponential
variable with mean $n$. For $\lambda>0$, consider the length of the longest
path whose average weight is at most $\lambda$. It was shown by Aldous (1998)
that the length is of order $\log n$ for $\lambda < 1/\mathrm{e}$ and of order
$n$ for $\lambda > 1/\mathrm{e}$. Aldous (2003) posed the question on detailed
behavior at and near criticality $1/\mathrm{e}$. In particular, Aldous asked
whether there exist scaling exponents $\mu, \nu$ such that for $\lambda$ within
$1/\mathrm{e}$ of order $n^{-\mu}$, the length for the longest path of average
weight at most $\lambda$ has order $n^\nu$.
  We answer this question by showing that the critical behavior is far richer:
For $\lambda$ around $1/\mathrm{e}$ within a window of $\alpha(\log n)^{-2}$
with a small absolute constant $\alpha>0$, the longest path is of order $(\log
n)^3$. Furthermore, for $\lambda \geq 1/\mathrm{e} + \beta (\log n)^{-2}$ with
$\beta$ a large absolute constant, the longest path is at least of length a
polynomial in $n$. An interesting consequence of our result is the existence of
a second transition point in $1/\mathrm{e} + [\alpha (\log n)^{-2}, \beta (\log
n)^{-2}]$. In addition, we demonstrate a smooth transition from subcritical to
critical regime. Our results were not known before even in a heuristic sense.
