Abstract: Contrary to initial beliefs, random graph evolution under an edge competition process with fixed choice (an Achlioptas process) seems to lead to a continuous transition in the thermodynamic limit. Here we show that a simpler model, which examines a single edge at a time, can lead to a strongly discontinuous transition and we derive the underlying mechanism. Starting from a collection of $n$ isolated nodes, potential edges chosen uniformly at random from the complete graph are examined one at a time while a cap, $k$, on the maximum allowed component size is enforced. Edges whose addition would exceed size $k$ can be simply rejected provided the accepted fraction of edges never becomes smaller than a decreasing function, $g(k) = 1/2 + (2k)^{-\beta}$. If the rate of decay is sufficiently small ($\beta < 1$), troublesome edges can always be rejected, and the growth in the largest component is dominated by an overtaking mechanism leading to a strongly discontinuous transition. If $\beta > 1$, once the largest component reaches size $n^{1/\beta}$, troublesome edges must often be accepted, leading to direct growth dominated by stochastic fluctuations and a “weakly” discontinuous transition.
Introduction
Percolation theory provides the theoretical underpinning for analyzing properties of networks, including epidemic thresholds and system resilience. Traditionally, the emergence of a "giant component" in random graphs is a continuous process. However, the discovery of "explosive percolation" in 2009 suggested that these transitions could be discontinuous. Subsequent research revealed that many such models actually revert to continuous transitions in the thermodynamic limit ($n \to \infty$). This paper addresses the challenge of identifying a simple model that remains truly discontinuous for infinite networks and derives the physical mechanism—growth by overtaking—that drives this behavior.
Methods
The researchers analyzed a modified version of the Bohman, Frieze, Wormald (BFW) algorithm. Starting with $n$ isolated nodes, potential edges are sampled one by one. A cap $k$ is maintained on the maximum allowed component size. An edge that would create a component larger than $k$ can be rejected, but only if the fraction of accepted edges remains above a threshold function: $g(k) = 1/2 + (2k)^{-\beta}$. The parameter $\beta$ controls how quickly the requirement to accept edges relaxes as $k$ grows. The study utilized numerical simulations with system sizes up to $n = 10^8$ nodes and analytical derivations to track the evolution of the largest components ($C_1, C_2, C_3$).
The Overtaking Mechanism
The fundamental insight of this work is the distinction between "direct growth" and "growth by overtaking." In standard percolation, the giant component grows by absorbing smaller clusters. In the BFW model with small $\beta$, the rejection rule prevents the largest component from growing too large directly. Instead, multiple medium-sized components grow in parallel. Eventually, two of these components merge and suddenly "overtake" the previous leader. This overtaking event creates the abrupt, discontinuous jump in the size of the giant component.
Scaling and the Thermodynamic Limit
A critical test for true discontinuity is whether the size of the jump in connectivity vanishes as the system size $n$ increases. The authors found that $\beta$ acts as a tuning knob for this behavior:
- Strongly Discontinuous ($\beta < 1$): The rejection rule is strong enough to consistently prevent direct growth. For $\beta = 0.5$, the largest jump in the giant component ($\Delta C_{max}$) remains constant regardless of $n$, proving the transition is fundamentally discontinuous.
- Weakly Discontinuous ($\beta > 1$): The rule is weak; once components reach size $n^{1/\beta}$, the algorithm is forced to accept edges that lead to direct growth. For $\beta = 2.0$, the jump size shrinks following a power law ($\Delta C_{max} \approx 0.285n^{-0.0068}$), indicating it would eventually vanish in an infinite system.
Conclusion
By identifying the "growth by overtaking" mechanism, this research provides a clear physical basis for strongly discontinuous transitions in network evolution. The model demonstrates that simple size constraints and minimum density requirements can lead to abrupt phase transitions that persist even in the thermodynamic limit. Future work may apply this framework to real-world competitive systems, such as industrial growth or ecological niche evolution, to identify similar abrupt transitions.
Summary updated