Abstract:
More than fifty years ago, Paul Erdős and Alfred Rényi discovered that the random graph $G(n,p)$ underwent a phase transition (in modern language) near $p = 1/n$. For p a bit smaller (e.g., $0.99/n$) all of the components were very small and had simple structures. But for p a bit bigger (e.g., $1.01/n$) a “giant component” had emerged with a complex behavior. We now understand how to slow down this process so as to see the incipient giant component (the dominant component) at an early stage and to define a Critical Window through which the process moves from subcriticality to supercriticality.
