Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Scaling window for mean-field percolation of averages

Algebra & Discrete Mathematics

Speaker: Jian Ding, Stanford University and MSRI
Location: 1147 MSB
Start time: Thu, Mar 15 2012, 3:10PM

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