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

Abstract

The evolution of the largest component has been studied intensely in a variety of random graph processes, starting in 1960 with the Erdős-Rényi process (ER). It is well known that this process undergoes a phase transition at n/2 edges when, asymptotically almost surely, a linear-sized component appears. Moreover, this phase transition is continuous, i.e., in the limit the function f(c) denoting the fraction of vertices in the largest component in the process after cn edge insertions is continuous. A variation of ER are the so-called Achlioptas processes in which in every step a random pair of edges is drawn, and a fixed edge-selection rule selects one of them to be included in the graph while the other is put back. Recently, Achlioptas, DʼSouza and Spencer [Achlioptas, D., R. M. DʼSouza and J. Spencer, Explosive percolation in random networks, Science 323 (2009), pp. 1453–1455] gave strong numerical evidence that a variety of edge-selection rules exhibit a discontinuous phase transition. However, Riordan and Warnke [Riordan, O. and L. Warnke, Achlioptas process phase transitions are continuous, arXiv:1102.5306v1 (2011)] very recently showed that all Achlioptas processes have a continuous phase transition. In this work we prove discontinuous phase transitions for a class of ER-like processes in which in every step we connect two vertices, one chosen randomly from all vertices, and one chosen randomly from a restricted set of vertices.