Combinatorics Seminar
When: Sunday, April 29, 10am
Where: Schreiber 309
Speaker: Michael Krivelevich, Tel Aviv University
Title: The phase transition in random graphs - a simple
proof
Abstract:
The classical result of Erdos and Renyi shows that the random graph G(n,p)
experiences sharp phase transition around p=1/n - for any \epsilon>0 and
p=(1-\epsilon)/n, all connected components of G(n,p) are typically of size
O(log n), while for p=(1+\epsilon)/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+\epsilon)/n, the random graph G(n,p) contains typically a
path of linear length. Time permitting, we also discuss applications of
our technique to other random graph models and to positional games.
Joint work with Benny Sudakov (UCLA).