Average-weight percolation on the complete graph

Vortrag von Prof. Dr. Yueyun Hu

Sprecher eingeladen von: Prof. Dr. Jean Bertoin

Datum: 04.03.26  Zeit: 17.15 - 18.45  Raum: Y27H12

This talk is based on a joint work with Elie Aidékon (Shanghai).
 
Attach to each edge of the complete graph on $n$ vertices, i.i.d. 
exponential random variables with mean $n$. Aldous (1998) proved 
that the longest path with average weight below $p$ undergoes a 
phase transition at $p=\frac{1}{e}$: it is  $o(n)$ when 
$p<\frac{1}{e}$ and of order $n$ if $p>\frac1e$. Later, 
Ding (2013) revealed a finer phase transition around $\frac{1}{e}$:   
there exist $c'>c>0$ such that the length of the longest path is of 
order $\ln^3 n$ if $ p \le \frac{1}{e}+\frac{c}{\ln^2 n}$ and is  
polynomial  if $p\ge  \frac{1}{e}+\frac{c'}{\ln^2 n}$.  
We identify the location of this phase transition and obtain 
sharp asymptotics of the length near criticality.  The proof 
uses an exploration mechanism mimicking a branching random 
walk with selection introduced by Brunet and Derrida (1999).