Phase transitions in supercritical explosive percolation

Abstract

Percolation describes the sudden emergence of large-scale connectivity as edges are added to a lattice or random network. In the Bohman-Frieze-Wormald model (BFW) of percolation, edges sampled from a random graph are considered individually and either added to the graph or rejected provided that the fraction of accepted edges is never smaller than a decreasing function with asymptotic value of alpha, a constant. The BFW process has been studied as a model system for investigating the underlying mechanisms leading to discontinuous phase transitions in percolation. Here we focus on the regime alpha is an element of [0.6,0.95] where it is known that only one giant component, denoted C-1, initially appears at the discontinuous phase transition. We show that at some point in the supercritical regime C-1 stops growing and eventually a second giant component, denoted C-2, emerges in a continuous percolation transition. The delay between the emergence of C-1 and C-2 and their asymptotic sizes both depend on the value of a and we establish by several techniques that there exists a bifurcation point alpha(c) = 0.763 +/- 0.002. For a. [0.6, ac), C-1 stops growing the instant it emerges and the delay between the emergence of C-1 and C-2 decreases with increasing alpha. For alpha is an element of (alpha(c), 0.95], in contrast, C-1 continues growing into the supercritical regime and the delay between the emergence of C-1 and C-2 increases with increasing alpha. As we show, alpha(c) marks the minimal delay possible between the emergence of C-1 and C-2 (i.e., the smallest edge density for which C-2 can exist). We also establish many features of the continuous percolation of C-2 including scaling exponents and relations.