Abstract

Perhaps the best understood phase transition is that in the component structure of the uniform random graph process introduced by Erdˆs and RÈnyi around 1960. Since the model is so fundamental, it is very interesting to know which features of this phase transition are specific to the model, and which are `universal’, at least within some larger class of processes. Achlioptas process, a class of variants of the Erdˆs-RÈnyi process that are easy to define but difficult to analyze, have been extensively studied from this point of view. Here, settling a number of conjectures and open problems, we show that all `bounded-size’ Achlioptas processes share many key features of the Erdˆs-RÈnyi phase transition (in particular the asymptotic behaviour of the size of the largest component above and below the critical window). We do not expect this to hold for Achlioptas processes in general. This is joint work with Oliver Riordan.