Draft:Explosive percolation

Explosive percolation is a class of percolation models for random graph evolution that exhibit unusually sharp phase transitions. The term was coined in 2009 by Dimitris Achlioptas, Raissa D'Souza, and Jon Spencer to describe processes that, unlike the classical Erdős–Rényi model, seemed to produce a discontinuous phase transition where a giant component emerges abruptly.

These models are characterized by introducing a "power of choice" mechanism into the graph's growth. Instead of adding a single, randomly chosen edge at each step, multiple potential edges are considered, and a selection rule is used to pick the "best" one, often with the goal of delaying the formation of large components.

While the canonical models of explosive percolation were later proven to have a continuous but extremely sharp phase transition, the field has provided deep insights into network formation, self-organizing criticality, and the nature of phase transitions.

The Achlioptas Process

The most famous example of a model for explosive percolation is the Achlioptas process. It is defined on a set of N isolated nodes as follows:

1. At each step, select m ≥ 2 potential edges uniformly at random from the set of all non-existent edges.
2. Apply a specific selection rule to choose exactly one of these m edges to add to the graph.

The goal of the selection rule is typically to suppress the growth of large components. For example, the product rule chooses the edge that connects two components whose size product is minimal. This biases the process towards merging smaller components and keeping the component size distribution narrow.

This selection mechanism was hypothesized to create a "powder keg" scenario: by delaying the inevitable merger of components, the system builds up a large number of medium-sized components that, upon reaching a critical point, would merge all at once, causing a discontinuous jump in the size of the largest component.

The Nature of the Phase Transition

The central question in the study of explosive percolation was whether the phase transition to a giant component was truly discontinuous. Initial numerical simulations for processes like the product-rule Achlioptas process strongly suggested a discontinuous jump.

Proof of Continuity

In 2011, Oliver Riordan and Lutz Warnke rigorously proved that for any Achlioptas process where the number of choices m is a fixed constant, the phase transition is in fact continuous. Their proof demonstrated that, contrary to the "powder keg" intuition, the second-largest component remains vanishingly small relative to the system size throughout the transition, which is a hallmark of a continuous transition.

Sharpness and Finite-Size Scaling

Although the transition is continuous in the thermodynamic limit, it is exceptionally sharp. The reason it appears discontinuous in simulations is due to unusual finite-size scaling behavior. The critical window, the period during which the giant component emerges, is much narrower than in the classical Erdős–Rényi model. For this reason, the transition is sometimes referred to as "weakly discontinuous."

Generalizations and Applications

Further research has shown that a truly discontinuous percolation transition is possible in modified models. For example, if the number of choices m is allowed to grow with the system size N (e.g., m = log N), a discontinuous transition can occur.

Explosive percolation models are studied in various contexts, including:

• Network robustness and cascading failures.
• Self-organizing systems.
• Designing networks with specific properties.

See Also

• Percolation theory
• Random graph
• Achlioptas process
• Phase transition
• Erdős–Rényi model
• Critical phenomena

References

Category:Percolation theory Category:Statistical mechanics Category:Random graphs Category:Phase transitions