The ACO Seminar (2011-2012)

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 show by Aldous (1998) that the critical value of $\lambda$ is $1/e$, below which the length is logarithmic and above which the length is linear. We show that at criticality the order of the length is $(\log n)^3$ where the scaling window (for $\lambda$) is of size $(\log n)^{-2}$. Furthermore, we establish a polynomial lower bound on the length when $(\lambda - 1/e) (\log n)^2$ exceeds a certain constant, which implies a second phase transition at criticality. Our results answer a question of Aldous (2003).