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

l a m b d a > 0

, consider the length of the longest path whose average weight is at most

l a m b d a

. It was shown by Aldous (1998) that the length is of order

l o g n

for

l a m b d a < 1 / m a t h r m e

and of order

n

for

l a m b d a > 1 / m a t h r m e

. In this paper, we study the near-supercritical regime where

l a m b d a = m a t h r m e^{- 1} + e t a

with

e t a > 0

a small fixed number. We show that there exist two absolute constants

c^{*}, C^{*} > 0

such that with high probability the length is in between

n m a t h r m e^{- C^{*} / s q r t e t a}

and

n m a t h r m e^{- c^{*} / s q r t e t a}

. Our result corrects a non-rigorous prediction of Aldous (2005).

Recommendations

Cited In (4)

This page was built for publication: Percolation of averages in the stochastic mean field model: the near-supercritical regime