Explosive Percolation in Erdős–Rényi-Like Random Graph Processes

Source abstract

The study of the phase transition of random graph processes, and recently in particular Achlioptas processes, has attracted much attention. Achlioptas, D'Souza and Spencer ( Science , 2009) gave strong numerical evidence that a variety of edge-selection rules in Achlioptas processes exhibit a discontinuous phase transition. However, Riordan and Warnke ( Science , 2011) recently showed that all these processes have a continuous phase transition. In this work we prove discontinuous phase transitions for three random graph processes: all three start with the empty graph on n vertices and, depending on the process, we connect in every step (i) one vertex chosen randomly from all vertices and one chosen randomly from a restricted set of vertices, (ii) two components chosen randomly from the set of all components, or (iii) a randomly chosen vertex and a randomly chosen component.