Mathematical Sciences Research Institute

Home » Scaling window for mean-field percolation of averages


Scaling window for mean-field percolation of averages March 07, 2012 (10:00 AM PST - 11:00 AM PST)
Location: MSRI: Simons Auditorium
Speaker(s) Jian Ding
Description No Description
No Video Uploaded

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).

No Notes/Supplements Uploaded No Video Files Uploaded