Percolation of averages in the stochastic mean field model: the near-supercritical regime

Abstract

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 (1998) that the length is of order $\log n$ for $\lambda <1/\mathrm{e}$ and of order $n$ for $\lambda >1/\mathrm{e}$. In this paper, we study the near-supercritical regime where $\lambda ={\mathrm{e}}^{-1}+\eta$ with $\eta >0$ a small fixed number. We show that there exist two absolute constants $c^{\ast },C^{\ast }>0$ such that with high probability the length is in between $n{\mathrm{e}}^{-C^{\ast }/\sqrt{\eta }}$ and $n{\mathrm{e}}^{-c^{\ast }/\sqrt{\eta }}$. Our result corrects a non-rigorous prediction of Aldous (2005).

21 pages, 3 figures

References in corpus (5)

• Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model
• The min mean-weight cycle in a random network
• Percolation of averages in the stochastic mean field model: the near-supercritical regime
• Scaling window for mean-field percolation of averages
• Supercritical minimum mean-weight cycles

Cited by in corpus (2)

• The planted matching problem: Sharp threshold and infinite-order phase transition
• Percolation of averages in the stochastic mean field model: the near-supercritical regime