Scaling window for mean-field percolation of averages

Abstract

For a complete graph of size $n$, assign each edge an i.i.d. exponential variable with mean $n$. For $λ>0$, consider the length of the longest path whose average weight is at most $λ$. It was shown by Aldous (1998) that the length is of order $\log n$ for $λ< 1/\mathrm{e}$ and of order $n$ for $λ> 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 $μ, ν$ such that for $λ$ within $1/\mathrm{e}$ of order $n^{-μ}$, the length for the longest path of average weight at most $λ$ has order $n^ν$. We answer this question by showing that the critical behavior is far richer: For $λ$ around $1/\mathrm{e}$ within a window of $α(\log n)^{-2}$ with a small absolute constant $α>0$, the longest path is of order $(\log n)^3$. Furthermore, for $λ\geq 1/\mathrm{e} + β(\log n)^{-2}$ with $β$ 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} + [α(\log n)^{-2}, β(\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.

17pages. Minor revision upon previous version. To appear in Annals of Probability