2012/01/31 by Krivelevich, Michael, Sudakov, Benny
#05C80 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1201.6529
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.