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 .>0, consider the length of the longest path whose average weight is at most .. It was shown by Aldous [Combin. Probab. Comput. 7 (1998) 1.10] that the length is of order logn for .<1/e and of order n for .>1/e. Aldous [Open problems (2003) Preprint] posed the question on detailed behavior at and near criticality 1/e. In particular, Aldous asked whether there exist scaling exponents ., . such that for . within 1/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/e within a window of .(logn).2 with a small absolute constant .>0, the longest path is of order (logn)3. Furthermore, for ..1/e+.(logn).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/e+[.(logn).2,.(logn).2]. In addition, we demonstrate a smooth transition from subcritical to critical regime. Our results were not known before even in a heuristic sense.