Achlioptas process phase transitions are continuous

Abstract

It is widely believed that certain simple modifications of the random graph process lead to discontinuous phase transitions. In particular, starting with the empty graph on $n$ vertices, suppose that at each step two pairs of vertices are chosen uniformly at random, but only one pair is joined, namely, one minimizing the product of the sizes of the components to be joined. Making explicit an earlier belief of Achlioptas and others, in 2009, Achlioptas, D'Souza and Spencer [Science 323 (2009) 1453-1455] conjectured that there exists a $\delta >0$ (in fact, $\delta \ge 1/2$) such that with high probability the order of the largest component "jumps" from $o(n)$ to at least $\delta n$ in $o(n)$ steps of the process, a phenomenon known as "explosive percolation." We give a simple proof that this is not the case. Our result applies to all "Achlioptas processes," and more generally to any process where a fixed number of independent random vertices are chosen at each step, and (at least) one edge between these vertices is added to the current graph, according to any (online) rule. We also prove the existence and continuity of the limit of the rescaled size of the giant component in a class of such processes, settling a number of conjectures. Intriguing questions remain, however, especially for the product rule described above.

Published in at http://dx.doi.org/10.1214/11-AAP798 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Self-organized adaptation of a simple neural circuit enables complex robot behaviour
• Impact of Single Links in Competitive Percolation -- How complex networks grow under competition

Cited by in corpus (32)

• Recent advances in percolation theory and its applications
• Explosive transitions in complex networks' structure and dynamics: percolation and synchronization
• Explosive Percolation: Novel critical and supercritical phenomena
• Avoiding a Spanning Cluster in Percolation Models
• Dynamical Systems on Networks: A Tutorial
• Crackling Noise in Fractional Percolation -- Randomly distributed discontinuous jumps in explosive percolation
• Minimal contagious sets in random regular graphs
• Preferential attachment with choice
• The evolution of subcritical Achlioptas processes
• Choice-Driven Phase Transition in Complex Networks
• The Bohman-Frieze Process Near Criticality
• Percolation model with an additional source of disorder
• Given enough choice, simple local rules percolate discontinuously
• Inverting the Achlioptas rule for explosive percolation
• Bounded-size rules: The barely subcritical regime
• The phase transition in bounded-size Achlioptas processes
• The augmented multiplicative coalescent and critical dynamic random graph models
• Percolation under Noise: Detecting Explosive Percolation Using the Second Largest Component
• Preferential attachment without vertex growth: emergence of the giant component
• On the largest component in the subcritical regime of the Bohman-Frieze process
• Convergence of Achlioptas processes via differential equations with unique solutions
• The Power of Two Choices for Random Walks
• Space-filling Percolation
• Bohman-Frieze processes at criticality and emergence of the giant component
• Critical Percolation on Random Networks with Prescribed Degrees
• Choices and intervals
• Sesqui-type branching processes
• From flip processes to dynamical systems on graphons
• A geometric Achlioptas process
• Prominent examples of flip processes
• Kinetics of Aggregation with Choice
• Shifting the Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints