Non-equilibrium coagulation processes and subcritical percolation on evolving networks
Authors
Sayan Banerjee
Shankar Bhamidi
Remco van der Hofstad
Rounak Ray
Abstract
We investigate percolation on growing networks where the evolution of connected components resembles a non-equilibrium version of the multiplicative coalescent. The supercritical $π> π_c$ regime for a host of such models was conjectured in statistical physics, and then rigorously proven in mathematics, to exhibit behavior similar to the BKT infinite-order phase transition as $π\searrow π_c$. It has further been conjectured that the entire regime $π<π_c$ for such growing networks are ''critical'' with power-law cluster size distributions having a non-universal exponent for all values of $π\in (0, π_c)$.
In this paper, we study percolation on the uniform attachment model, as a concrete template in order to develop general tools based on stochastic approximation, local convergence, branching random walks and tree-graph inequalities to prove the above conjectured phenomena. For each $π\in (0,π_c)$, we show there exists an explicit $α(π) \in (0,\tfrac{1}{2}) $ such that the maximal component size, as well as the size of the component containing any fixed vertex, all re-scaled by $n^{α(π)}$, converge almost surely to strictly positive random variables as the network size $n \to \infty$. These dynamics lead to novel phenomena, compared to classical 'static' models, including long-range dependence and fixation of the identity of the maximal component, within finite time, among a finite number of 'early' components. Moreover, in contrast with most static network models, we show that the susceptibility, that is, the expected size of the component of a uniformly chosen vertex, remains bounded as the network grows and $π$ approaches $π_c$ from below. The general tools developed in this paper will be used in follow-up work to understand percolation for general growing network evolution models.
