Computer Science/Discrete Mathematics Seminar I

In their great 1960 paper "On the Evolution of Random Graphs" Paul Erdos and Alfred Renyi expresses a special interest in the behavior of the random graph G(n,p) when np was near one. Today we view it through the prism of Percolation Theory. Write c=np. For c smaller than one the process is subcritical and all components are small and simple. But for c bigger than one the process is supercritical and a complex giant component has emerged. We now understand the fine structure: the critical window is parametrized by setting np equal to one plus lambda times n to the power minus one third. The regimes when lambda approaches minus infinity and plus infinity represent the barely subcritical and barely supercritical phases respectively. We discuss the behaviors, the arguments and the many analogies to bond percolation in Mathematical Physics. And we explain the power minus one third.