Scaling window for mean-field percolation of averages (Q2434921)

This paper is a study of what may be called mean-field percolation on a complete graph. Consider a complete graph on \(n\) vertices and assume that each edge is equipped with a random weight that is exponentially distributed with mean \(n\) (with these random variables forming an independent family). Consider the length \(L\) of the longest path among those of average total weight at most \(\lambda\). It has been shown by D. Aldous, that \(\lambda = 1/e\) is a critical quantity around which the behaviour of this parameter changes abruptly. If \(\lambda < 1/e\), then this quantity is of order \(\log n\), whereas if \(\lambda > 1/e\), then it becomes linear in \(n\). The present paper is a study of the critical behaviour where \(\lambda\) is close to \(1/e\). The first result states that there is a critical window of length \(\Theta (\log^{-2} n)\) around \(1/e\) where with high probability \(L\) is of order \(\log^3 n\). Beyond the upper end of this critical window \(L\) grows polynomially fast in \(n\) (bounded by \(n^{1/4}\) from below and being \(O(n(\lambda - e^{-1}))\)). A more precise result is obtained for the lower end of the window. Below this, \(L\) scales like \((e^{-1} -\lambda)^{-1} \log n\).