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 [Combin. Probab. Comput. 7 (1998) 1-10] that the length is of order log n for lambda < 1/e and of order n for lambda > 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 mu, v such that for lambda within 1/e of order n(-mu), the length for the longest path of average weight at most. has order n(v). We answer this question by showing that the critical behavior is far richer: For lambda around 1/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 >= 1/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/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.
