Scaling window for mean-field percolation of averages

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{/}\mathrm{e}$ and of order $n$ for $\lambda >1\mathrm{/}\mathrm{e}$. Aldous (2003) posed the question on detailed behavior at and near criticality $1\mathrm{/}\mathrm{e}$. In particular, Aldous asked whether there exist scaling exponents $\mu ,\nu$ such that for $\lambda$ within $1\mathrm{/}\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{/}\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$\mathrm{.}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.