2025/12/29 by Élie Aïdékon, Yue Hu, Aïdékon, Elie +1
Mathematics · Physics and Astronomy · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · doi:10.48550/arxiv.2512.23266
openalex publication_date 2025/12/29 · openalex created_date 2025/12/31 · openalex updated_date 2026/07/28
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=(1)/(e): it is o(n) when p<(1)/(e) and of order n if p>\frac1e. Later, Ding [4] revealed a finer phase transition around (1)/(e): there exist c'>c>0 such that the length of the longest path is of order ln3 n if p ≤ (1)/(e)+(c)/(ln2 n) and is polynomial if p≥ (1)/(e)+(c')/(ln2 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].