Abstract

The classical random graph process starts with a fixed set of n vertices and no edges. Edges are then added one-by-one, uniformly at random. One of the most interesting features of this process, established by Erdős and Rényi more than 50 years ago, is the phase transition near n/2 edges, where a single `giant' component emerges from a sea of small components. This example serves as a starting point for understanding phase transitions in a wide variety of other contexts. Around 2000, Dimitris Achlioptas suggested an innocent-sounding variation of the model: at each stage two edges are selected at random, but only one is added, the choice depending on (typically) the sizes of the components it would connect. This may seem like a small change, but these processes do not have the key independence property that underlies our understanding of the classical process. One can ask many questions about Achlioptas processes; the most interesting concern the phase transition: does the critical value change from n/2? Is the nature of the transition the same or not? I will describe a number of results on these questions from joint work with Lutz Warnke.