Achlioptas process phase transitions are continuous (Q453240): Difference between revisions

In the well-known Erdős-Rényi graph sequence, the initial graph \(G(0)\) is the empty graph on \(n\) vertices, and \(G(m)\) is obtained from \(G(m-1)\) by inserting an edge at a randomly selected empty vertex-pair site for \(m=1,2,\dots\). The proportion of vertices in the largest connected component converges in probability to zero if and only if \(m/n\) converges to a value not larger than \(1/2\). This phase transition at the critical value \(1/2\) can be changed by modifying the rule for edge selections. It has been conjectured that a certain ``product rule'' exhibits so called ``explosive percolation''. This conjecture is here disproved by investigating a general edge selection rule which specifies how at least one edge is inserted among the vertex-pair sites in a random fixed-size sample of vertices. It is shown that this rule leads to continuous phase transitions. Convergence of the proportion of vertices in any largest component and convergence of the proportions of vertices in components of different orders are investigated.