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

preprint2015arXivOpen access

Abstract

For a complete graph of size nn, assign each edge an i.i.d.\ exponential variable with mean nn. For λ>0λ>0, consider the length of the longest path whose average weight is at most λλ. It was shown by Aldous (1998) that the length is of order log⁡n\log n for λ<1/eλ< 1/\mathrm{e} and of order nn for λ>1/eλ> 1/\mathrm{e}. In this paper, we study the near-supercritical regime where λ=e−1+ηλ= \mathrm{e}^{-1} +η with η>0η>0 a small fixed number. We show that there exist two absolute constants c∗,C∗>0c^*, C^*>0 such that with high probability the length is in between ne−C∗/ηn \mathrm{e}^{-C^*/\sqrtη} and ne−c∗/ηn \mathrm{e}^{-c^*/\sqrtη}. Our result corrects a non-rigorous prediction of Aldous (2005).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.