Combinatorics Seminar

When: Sunday, May 27, 10am Where: Schreiber 309 Speaker: Joel Spencer, Courant Institute Title: The Erdos-Renyi Phase Transition

Abstract:

In their great 1960 paper "On the Evolution of Random Graphs" Paul Erdos and Alfred Renyi expressed a special interest in the behavior of the random graph G(n,p) when p was near n^{-1}. Today we view it through the prism of Percolation Theory. If p=cn^{-1} and c < 1 the process is subcritical and all components are small and simple. But for c > 1 the process is supercritical and a complex giant component has emerged. We now understand the fine structure: the critical window is parametrized p=n^{-1}+lambda n^{-4/3}, with lambda tending to negative infinity and lambda tending to positive infinity representing the barely subcritical and barely supercritical phases. We discuss the behaviors, the arguments and the many analogies to bond percolation in Mathematical Physics. Our approach, in this semi-expository talk, is to compare the generation of the component C(v) containing a given vertex v in G(n,cn^{-1}) with a Poisson branching model with parameter c.