The Phase Transition in Random Graphs: A Simple Proof

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 ε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

Speaker Details

Benny Sudakov got his Ph.D from Tel Aviv University in 1999 under Noga Alon, had appointments in Princeton University and Institute for Advanced Studies and is currently professor of mathematics in UCLA. He is the recipient of an Alfred P. Sloan Foundation Fellowship, an NSF CAREER Award and was an invited speaker at 2010 International Congress of Mathematicians.

His main interests are Combinatorics and its applications in Computer Science.

Series:
Microsoft Research Talks
Date:
Speakers:
Benny Sudakov
Affiliation:
UCLA

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks