Average-weight percolation on the complete graph

Abstract

Attach to each edge of the complete graph on $n$ vertices, i.i.d. exponential random variables with mean $n$. Aldous [1] proved that the longest path with average weight below $p$ undergoes a phase transition at $p=\frac{1}{e}$: it is $o(n)$ when $p<\frac{1}{e}$ and of order $n$ if $p>\frac{1}{e}$. Later, Ding [4] revealed a finer phase transition around $\frac{1}{e}$: there exist $c^{\prime }>c>0$ such that the length of the longest path is of order ${\ln }^{3}n$ if $p\le \frac{1}{e}+\frac{c}{{\ln }^{2}n}$ and is polynomial if $p\ge \frac{1}{e}+\frac{c^{\prime }}{{\ln }^{2}n}$. We identify the location of this phase transition and obtain sharp asymptotics of the length near criticality. The proof uses an exploration mechanism mimicking a branching random walk with selection introduced by Brunet and Derrida [3].