Controlled asymptotics, general phase structure, and dynamics of bootstrap percolation in the large-connectivity limit

Bootstrap percolation (BP) on a random regular graph of coordination $k+1$ with threshold $m$ exhibits, for $m>2$, a hybrid (mixed-order) transition: a discontinuous jump of the order parameter accompanied by diverging critical fluctuations. Parisi and Sellitto (EPL 109, 36001 (2015)) analyzed the simultaneous limit $m,k\to\infty$ with fixed ratio $\alpha=m/k$, deriving leading-order formulas from a de Moivre–Laplace Gaussian approximation of the binomial self-consistency equation, showing that the hybrid character survives with a jump amplitude decaying as $k^{-1/4}$, that the $k\to\infty$ limit is singular, and that threshold mixtures develop multiple percolating phases and higher-order bifurcation singularities. The framework, however, rests on uncontrolled asymptotics: no error bounds or systematic higher-order corrections at large finite $k$ exist, only the binary mixture case is classified, the singular limit is not uniformly controlled, and the announced dynamical extension (the dynamics of facilitated spin models whose statics is bootstrap percolation, and threshold dynamics closely related to BP) remains unsolved in the large-connectivity regime. This problem asks for a controlled asymptotic theory of large-connectivity BP delivering these missing elements.

Background

Bootstrap percolation (BP) is a threshold generalization of ordinary random percolation, introduced in the late 1970s for dilute magnets: each site of a graph is initially occupied independently with probability $p$, and particles with fewer than $m$ occupied neighbors are then iteratively removed until a stable configuration is reached — either an empty graph or a residual cluster in which every particle has at least $m$ occupied neighbors. On locally tree-like graphs — the Bethe lattice, realized as a random regular graph of coordination $z=k+1$ — the model is exactly solvable: the probability $B$ that a site is connected to the infinite cluster through a given neighbor satisfies a closed self-consistency equation whose right-hand side is a binomial tail sum, and the percolation threshold $p_c$ follows from its first nontrivial solution (Chalupa, Leath, and Reich, 1979). For $m>2$ the transition is hybrid, also called mixed-order: the order parameter jumps discontinuously at $p_c$ while fluctuations diverge as in a continuous transition. The mechanism — a sudden jump driven by fragile 'corona' clusters, in which every particle has exactly $m$ occupied neighbors, so that removing one particle triggers a cascade — is shared by k-core percolation on complex networks (the k-core being the maximal subgraph in which every vertex keeps at least $k$ neighbors; Baxter, Dorogovtsev, Goltsev, and Mendes, 2010), by jamming, and by kinetically constrained (facilitated) spin models of glassy dynamics, whose ergodicity breaking is the freezing of a BP backbone (Sellitto, Biroli, and Toninelli, 2005). The BP self-consistency equation is also formally identical to the equation of the nonergodicity parameter in mode-coupling theory (MCT), the mean-field theory of the glass transition.

Parisi and Sellitto (2015) introduced the large-connectivity limit, in which the threshold and the connectivity both diverge with fixed ratio $\alpha=m/k\in(0,1)$. Approximating the binomial distribution by a Gaussian (the de Moivre–Laplace theorem, the classical normal approximation of the binomial) converts the self-consistency equation into closed expressions involving the error function, from which they extracted, to leading order in $k$:

$B_c(\alpha,k)\simeq\alpha-\sqrt{\frac{\alpha(1-\alpha)}{k}\ln\frac{k\alpha}{2\pi(1-\alpha)}},\qquad p_c(\alpha,k)\simeq B_c(\alpha,k),$

the square-root approach $B-B_c\sim k^{-1/4}\sqrt{p-p_c}$, showing that the jump amplitude vanishes as $k^{-1/4}$ while the width of the hybrid window shrinks as $k^{-1/2}$; and the fact that the $k=\infty$ limit itself is singular — at strictly infinite connectivity the order parameter grows linearly with $p-p_c$ (exponent $\beta=1$) instead of with the finite-$k$ exponent $\beta=1/2$. When $\alpha$ is a random variable taking $n$ values $\alpha_1<\cdots<\alpha_n$ with fractions $q_i$ (an n-ary mixture), the same framework predicts multiple percolating phases of increasing compactness separated by additional hybrid transition lines, together with higher-order bifurcation singularities $A_\ell$ — in the language of catastrophe theory, points where the first $\ell-1$ derivatives of the governing function $F(B)$ vanish while the $\ell$-th does not, giving order-parameter scaling $(p-p_c)^{1/\ell}$ — including the $A_3$ cusp endpoints and $A_4$ swallowtail coincidences, which they locate explicitly for the binary ($n=2$) case. Prior work on heterogeneous k-core percolation had established the binary and ternary mixture structure at generic (order-one) connectivity (Cellai, Lawlor, Dawson, and Gleeson, 2011; Cellai and Gleeson, 2013).

All of these results are leading-order and formal. The paper itself is explicit about what is missing: the Gaussian-based approximations are validated only graphically (they 'work pretty well' for $k$ of a few hundred), with no error bounds, higher-order corrections, or sharp validity range in $(k,\alpha)$ — the boundary regimes $\alpha\to0$ and $\alpha\to1$, where the natural scaling variable $k\alpha/(1-\alpha)$ is no longer large, being excluded; only $n=2$ is worked out, the general-$n$ picture being an explicit speculation; the singular, non-commuting nature of the $k\to\infty$ limit is exhibited but not uniformly controlled; and the extension of the framework to dynamics is announced as work in progress. These acknowledged gaps define the problem below.

Problem Statement

Develop a controlled asymptotic theory of bootstrap percolation on random regular graphs in the large-connectivity regime ($m,k\to\infty$ with $\alpha=m/k\in(0,1)$ fixed), replacing the formal Gaussian asymptotics of Parisi and Sellitto (2015) with provable or systematically correctable statements about the exact binomial self-consistency equation for the order parameter $B$. Within this single framework, the theory must deliver all four of the following linked results, which the source paper's own analysis identifies as missing:

(a) Error control at large finite $k$: the precise range of validity in $(k,\alpha)$ of the leading-order formulas for $B_c(\alpha,k)$ and $p_c(\alpha,k)$, systematic higher-order corrections in powers of $1/k$, and explicit error bounds uniform in the relevant variables — including the boundary regimes where $\alpha$ approaches 0 or 1 and the scaling variable $k\alpha/(1-\alpha)$ is no longer large.

(b) Complete phase structure for general $n$-ary threshold mixtures: a classification, for arbitrary $n$ and composition fractions $\{\alpha_i,q_i\}$, of the number and topology of percolating phases, the loci of the hybrid transition lines, the loci and endpoints of the $A_\ell$ bifurcation singularities and their coincidence conditions (such as the $A_4$ swallowtail), and the fate of this structure when some $\alpha_i$ lie near 0 or 1 — going beyond the binary case of the source and the ternary k-core case of Cellai and Gleeson.

(c) Uniform control of the singular $k\to\infty$ limit: a rigorous description of how the finite-$k$ hybrid regime (exponent $\beta=1/2$, jump amplitude decaying as $k^{-1/4}$, window width shrinking as $k^{-1/2}$) crosses over to the linear $\beta=1$ regime at $k=\infty$ — that is, of the non-commutation of the critical regime with the connectivity limit.

(d) The dynamical extension: an analytic treatment, in the same large-connectivity framework, of the dynamics of facilitated spin models whose statics is bootstrap percolation, and of threshold dynamics closely related to bootstrap percolation.

Components (a)–(c) concern the static self-consistency equation and its solution structure; (d) extends the same framework to time-dependent problems, as the source announces. The common objective is that the large-connectivity BP framework rest on controlled rather than purely formal asymptotics across its statics and its announced dynamical extension.

References

1. J. Chalupa, P. L. Leath, and G. R. Reich, 'Bootstrap percolation on a Bethe lattice', J. Phys. C: Solid State Phys. 12, L31 (1979). DOI: 10.1088/0022-3719/12/1/008, https://doi.org/10.1088/0022-3719/12/1/008
2. G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, 'Bootstrap percolation on complex networks', Phys. Rev. E 82, 011103 (2010). DOI: 10.1103/PhysRevE.82.011103, https://doi.org/10.1103/PhysRevE.82.011103
3. M. Sellitto, G. Biroli, and C. Toninelli, 'Facilitated spin models on Bethe lattice: bootstrap percolation, mode-coupling transition and glassy dynamics', EPL 69, 496 (2005). DOI: 10.1209/epl/i2004-10372-5, https://doi.org/10.1209/epl/i2004-10372-5
4. Giorgio Parisi and Mauro Sellitto, 'The large-connectivity limit of bootstrap percolation', EPL 109, 36001 (2015). DOI: 10.1209/0295-5075/109/36001, https://doi.org/10.1209/0295-5075/109/36001; preprint arXiv:1411.1726, https://arxiv.org/abs/1411.1726
5. Davide Cellai, Aonghus Lawlor, Kenneth A. Dawson, and James P. Gleeson, 'Tricritical point in heterogeneous k-core percolation', Phys. Rev. Lett. 107, 175703 (2011). DOI: 10.1103/PhysRevLett.107.175703, https://doi.org/10.1103/PhysRevLett.107.175703
6. Davide Cellai and James P. Gleeson, 'Singularities in ternary mixtures of k-core percolation', in Complex Networks IV, Studies in Computational Intelligence (Springer, 2013), pp. 165-172. DOI: 10.1007/978-3-642-36844-8_16, https://doi.org/10.1007/978-3-642-36844-8_16; preprint arXiv:1301.4556, https://arxiv.org/abs/1301.4556
7. Mauro Sellitto, 'Crossover from beta to alpha relaxation in cooperative facilitation dynamics', Phys. Rev. Lett. 115, 225701 (2015). DOI: 10.1103/PhysRevLett.115.225701, https://doi.org/10.1103/PhysRevLett.115.225701; preprint arXiv:1508.02644, https://arxiv.org/abs/1508.02644
8. Nimrod Segall, Eial Teomy, and Yair Shokef, 'Jamming versus caging in three dimensional jamming percolation', J. Stat. Mech. (2016) 054051. DOI: 10.1088/1742-5468/2016/05/054051, https://doi.org/10.1088/1742-5468/2016/05/054051
9. Tommaso Rizzo, 'Fate of the hybrid transition of bootstrap percolation in physical dimension', Phys. Rev. Lett. 122, 108301 (2019). DOI: 10.1103/PhysRevLett.122.108301, https://doi.org/10.1103/PhysRevLett.122.108301; preprint arXiv:1807.08066, https://arxiv.org/abs/1807.08066
10. Mauro Sellitto, 'Selective bootstrap percolation', J. Stat. Mech. (2019) 113203. DOI: 10.1088/1742-5468/ab47fa, https://doi.org/10.1088/1742-5468/ab47fa; preprint arXiv:1911.01674, https://arxiv.org/abs/1911.01674
11. Wen-Jun Jiang, Run-Ran Liu, Tian-Long Fan, Shuang-Shuang Liu, and Lin-Yuan Lü, 'Overview of precaution and recovery strategies for cascading failures in multilayer networks', Acta Physica Sinica 69, 20192000 (2020). DOI: 10.7498/aps.69.20192000, https://doi.org/10.7498/aps.69.20192000
12. Koray Önder, Matthias Sperl, and W. Till Kranz, 'Asymptotically exact solution of the Fredrickson-Andersen model', arXiv:1902.06537 (2019), https://arxiv.org/abs/1902.06537
13. Gianmarco Perrupato and Tommaso Rizzo, 'Thermodynamics of the Fredrickson-Andersen model on the Bethe lattice', Phys. Rev. E 110, 044312 (2024); preprint arXiv:2312.01430, https://arxiv.org/abs/2312.01430
14. Gianmarco Perrupato and Tommaso Rizzo, 'Theory of kinetically-constrained-models dynamics', SciPost Phys. 18, 020 (2025). DOI: 10.21468/SciPostPhys.18.1.020, https://doi.org/10.21468/SciPostPhys.18.1.020; preprint arXiv:2212.05132, https://arxiv.org/abs/2212.05132
15. Damiano De Gaspari, 'Fredrickson Andersen model and noisy majority vote process on nonamenable graphs', arXiv:2508.06935 (2025), https://arxiv.org/abs/2508.06935
16. Jung-Ho Kim and K.-I. Goh, 'K-selective percolation: a simple model leading to a rich repertoire of phase transitions', Chaos 32, 023115 (2022). DOI: 10.1063/5.0081253, https://doi.org/10.1063/5.0081253; preprint arXiv:2109.15069, https://arxiv.org/abs/2109.15069