Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Monday, May 07, 2012, 12:15 pm
Duration: 45 minutes
Location: OAT S15/S16/S17
Speaker: Benny Sudakov (University of California, Los Angeles)
The classical result of Erdős and Renyi shows that the random graph G(n,p) experiences sharp phase transition around p=1/n -- for any ε>0 and p=(1-ε)/n, all connected components of G(n,p) are typically of size O(\log n), while for p=(1+ε)/n, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime p=(1+ε)/n, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games.
Joint work with M. Krivelelvich.
Automatic MiSe System Software Version 1.4803M | admin login