Mar 1, 3:30pm, Wean 8220

Jian Ding, Stanford

Scaling window for mean-field percolation of averages

Jian Ding, Stanford

Scaling window for mean-field percolation of averages

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 show by Aldous (1998) that the critical value of $\lambda$ is
$1/e$, below which the length is logarithmic and above which the length
is linear. We show that at criticality the order of the length is
$(\log n)^3$ where the scaling window (for $\lambda$) is of size $(\log
n)^{-2}$. Furthermore, we establish a polynomial lower bound on the
length when $(\lambda - 1/e) (\log n)^2$ exceeds a certain constant,
which implies a second phase transition at criticality. Our results
answer a question of Aldous (2003).