Preprint · arXiv:2610.04420v1. Published on arXiv on 3 October 2026. The English text is reproduced unchanged from the original version on arXiv. Download the original PDF.

Seed thresholds and degree variance in heterogeneous bootstrap percolation with growing degrees

Aleksandr Rodionov Affiliation: Yandex, Saint Petersburg, Russia Affiliation: ORCID: 0009-0006-6710-923X Email: rexarrior@yandex.ru

Preprint — 29 September 2026

Abstract

We study bootstrap percolation with independent vertex thresholds taking values one and two, with threshold-one probability $(1-c/d)/d$ for fixed $c>0$ . The seed set is chosen uniformly among sets of a prescribed deterministic size, independently of the graph and thresholds. We prove threshold statements at fixed relative margins. For uniform simple graphs with prescribed nonnegative integer degrees of even sum and exact mean $d$ , assume $\max_{i}|d_{i}-d|\leq C\sqrt{d}$ and $c+1-v_{n}\geq\kappa>0$ , where $v_{n}=\operatorname{Var}(D)/d$ and $C,\kappa$ are fixed. When $d\to\infty$ and $d=o(n^{1/7})$ , the leading seed scale is $n(c+1-v_{n})^{2}/(2d^{4})$ , without requiring a limit of $v_{n}$ . At fixed relative margins below and above this scale, the final active set has size $O(n/d^{3})$ and $n-o(n)$ , respectively, with high probability. A separate result for $G(n,d/n)$ holds when $d\to\infty$ and $d^{5}/n\to 0$ , and gives scale $nc^{2}/(2d^{4})$ . Thus regular and independent-edge graphs have different coefficients at the same asymptotic mean degree. Local exploration estimates yield explicit inactive remainders and survive conditioning on simplicity in the prescribed model. We also quantify the precision obstruction to static inclusion transfer and compute deterministic response-barrier corrections, without identifying a shrinking random critical window.

1 Model and main results

On a finite simple graph on $[n]=\{1,\ldots,n\}$ , start from a seed set $A_{0}$ and repeatedly activate each inactive vertex having at least $R_{i}$ active neighbours. Activation is permanent; write $A_{\infty}$ for the final active set. Throughout, $n\to\infty$ and logarithms are natural. For a fixed $c>0$ , the thresholds are mutually independent and independent of the graph, with

\Pr(R_{i}=1)=\pi=\frac{1-c/d}{d},\qquad\Pr(R_{i}=2)=1-\pi.

(1)

The seed set is independent of the graph and all thresholds and is uniform among subsets of a prescribed deterministic integer size $a=a_{n}\in\{0,\ldots,n\}$ . Write $\alpha=a/n$ . All probability statements average over the graph, thresholds and seeds. With high probability means with probability tending to one along each sequence satisfying the stated hypotheses. A bound $X=O(f_{n})$ with high probability means that some fixed finite $B$ satisfies $\Pr(X\leq Bf_{n})\to 1$ .

1.1 Excess degree and the seed scale

For prescribed degrees let $D$ have the empirical degree distribution, let $d=\mathbb{E}D$ , and put $v_{n}=\operatorname{Var}(D)/d$ . We assume a fixed positive gap $c+1-v_{n}\geq\kappa>0$ . The excess-degree identity and its deficit are

\frac{\mathbb{E}[D(D-1)]}{d}=d-1+v_{n},\qquad b=\frac{c+1-v_{n}}{d}+\frac{c(v_{n}-1)}{d^{2}}.

Thus $b\asymp d^{-1}$ uniformly under the fixed parameter bounds. If additionally $v_{n}\to v$ , the leading coefficient specializes to $(c+1-v)^{2}/2$ . The main theorem does not require this convergence.

For regular degrees the remaining degree is $d-1$ : the edge used to reach the vertex is no longer available. For a Poisson degree law of mean $d$ , size bias followed by removal of the arrival edge leaves mean $d$ . This one-edge difference changes the deficit from $(c+1)/d+O(d^{-2})$ to $c/d$ . The next response coefficient is $K\sim d^{2}$ , producing the seed scale $b^{2}/(2K)$ and hence the two different leading coefficients. The theorems below justify this deterministic prediction.

For prescribed degrees we quantitatively refine the established exponential exploration at the shrinking bottleneck scale, with error probabilities sufficient for conditioning on simplicity. For independent edges we specialize the established independent-mark and maximal empirical-process arguments to the mixed response, obtaining the range $d^{5}/n\to 0$ . Both arguments give terminal bounds at fixed relative margins.

The resulting regular/independent-edge separation rigorously realizes the prediction of the established response equations. The slow-degree supercritical overlap with finite-time approximation is recorded in Appendix B. Higher-moment refinements concern deterministic barriers, rather than the centre of a random critical window.

1.2 Threshold statements

Define the residual bounds

\mathcal{R}_{\rm P}(n,d,C)=n\bigl[d\,2^{-d+C\sqrt{d}}+n^{-1/3}\bigr],\qquad\mathcal{R}_{\rm E}(n,d)=n\bigl[(1+d)e^{-d/2+d/n}+n^{-1/3}\bigr].

(2)

Theorem 1 (P: prescribed degrees).

Fix $c>0$ , $C\geq 0$ , $\kappa>0$ and $\gamma\in(0,1)$ . Let $d_{1},\ldots,d_{n}$ be nonnegative integers with even sum $nd$ , where $d=n^{-1}\sum_{i}d_{i}$ is the exact mean. Let $D$ have the empirical degree distribution, and assume

\max_{i}|d_{i}-d|\leq C\sqrt{d},\qquad v_{n}=\frac{\operatorname{Var}(D)}{d},\qquad c+1-v_{n}\geq\kappa,

(3)

d\longrightarrow\infty,\qquad d=o(n^{1/7}).

(4)

Set

b=1-\pi\frac{\mathbb{E}[D(D-1)]}{d},\qquad K=(1-2\pi)\frac{\mathbb{E}[D(D-1)(D-2)]}{d},\qquad A=\frac{b^{2}}{2K}.

(5)

For all sufficiently large $n$ , the degree sequence is graphical, $0<\pi<1$ , $b>0$ and $K>0$ . On the uniform simple graph with these degrees, under the threshold and seed conventions above, there exist finite constants $B_{-},B_{+}$ depending only on $c,C,\kappa,\gamma$ such that, for every sequence of prescribed deterministic seed sizes,

	$\displaystyle a\leq(1-\gamma)nA$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(\|A_{\infty}\|\leq B_{-}n/d^{3}\bigr)\longrightarrow 1,$		(6)
	$\displaystyle a\geq(1+\gamma)nA$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(n-\|A_{\infty}\|\leq B_{+}\mathcal{R}_{\rm P}(n,d,C)\bigr)\longrightarrow 1.$		(7)

Here and below an inequality on $a_{n}$ is required eventually. No convergence of $v_{n}$ is assumed.

Theorem 2 (E: independent edges).

Fix $c>0$ and $\gamma\in(0,1)$ , and let

d\longrightarrow\infty,\qquad\frac{d^{5}}{n}\longrightarrow 0.

(8)

Take $G\sim G(n,d/n)$ with the threshold and seed conventions above, and put $A_{\rm E}=c^{2}/(2d^{4})$ and $a_{\rm E}=nA_{\rm E}$ . There exist finite constants $B_{-}^{\rm E},B_{+}^{\rm E}$ depending only on $c,\gamma$ such that, for every sequence of prescribed deterministic seed sizes,

	$\displaystyle a\leq(1-\gamma)a_{\rm E}$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(\|A_{\infty}\|\leq B_{-}^{\rm E}n/d^{3}\bigr)\longrightarrow 1,$		(9)
	$\displaystyle a\geq(1+\gamma)a_{\rm E}$	$\displaystyle\ \Longrightarrow\quad\Pr\bigl(n-\|A_{\infty}\|\leq B_{+}^{\rm E}\mathcal{R}_{\rm E}(n,d)\bigr)\longrightarrow 1.$		(10)

This theorem treats the independent-edge model separately, without the prescribed-degree assumptions of Theorem 1. Here $d=np$ parametrizes the edge probability, and the exact expected degree is $(n-1)d/n$ .

Both residual bounds are $o(n)$ in their respective ranges, so the supercritical conclusions imply $|A_{\infty}|/n\to 1$ in probability. They do not assert full activation or a shrinking critical window. The seed-size quantifiers concern prescribed sizes and independent uniform seeds, not seeds selected after observing graph or thresholds.

Constants.

The model parameters $c,C,\kappa$ and relative margin $\gamma$ are fixed whenever applicable. Constants in the prescribed-degree probability bounds may depend only on $c,C,\kappa,\gamma$ ; those in the independent-edge bounds may depend only on $c,\gamma$ . Constants in the logarithmic corollary may additionally depend on its fixed $K_{0}$ . Unspecified constants may vary between estimates, while the model parameters remain fixed. The index from which an asymptotic estimate holds may depend on the chosen sequence and its convergence rates; it need not be uniform over those sequences. In the abstract deterministic barrier lemma, constants may also depend on its uniform comparison and derivative bounds and its fixed local interval. None of these statements permits $\gamma\to 0$ or $\kappa\to 0$ .

Lemma 3 (Empirical moments and transfer at fixed margins).

Under (3), with fixed $c,C,\kappa$ and $d\to\infty$ , let $q_{n}=c+1-v_{n}$ and $A_{0,n}=q_{n}^{2}/(2d^{4})$ . For $b,K,A$ in (5), uniformly over these empirical laws,

b=\frac{q_{n}}{d}+\frac{c(v_{n}-1)}{d^{2}},\qquad K=d^{2}\bigl(1+O(d^{-1})\bigr),\qquad A=\frac{q_{n}^{2}}{2d^{4}}\bigl(1+O(d^{-1})\bigr).

(11)

Thus (6) and (7) remain valid with $A_{0,n}$ in place of $A$ , for each fixed relative margin (with possibly changed constants). If in addition $v_{n}\to v$ , then $v<c+1$ and

nA\sim\frac{n(c+1-v)^{2}}{2d^{4}},

(12)

and that limiting expression may likewise replace $nA$ in the fixed-margin conclusions. The deterministic estimates in (11) do not require a relation between $n$ and $d$ ; the probability conclusions retain (4).

Corollary 4 (Regular separation).

Fix $c>0$ . Let $d=d_{n}$ be integer, $nd$ even, and assume $d\to\infty$ and $d=o(n^{1/7})$ . Compare the uniform simple $d$ -regular graph and $G(n,d/n)$ under the same threshold and seed conventions. Their leading seed scales are

t_{\rm R}=\frac{(c+1)^{2}n}{2d^{4}},\qquad t_{\rm E}=\frac{c^{2}n}{2d^{4}},\qquad\frac{t_{\rm R}}{t_{\rm E}}=\frac{(c+1)^{2}}{c^{2}}.

Precisely, for every fixed $\gamma\in(0,1)$ , seeds below $(1-\gamma)t_{\rm R}$ give $O(n/d^{3})$ final active vertices in the regular model, whereas seeds above $(1+\gamma)t_{\rm R}$ leave $O(\mathcal{R}_{\rm P}(n,d,0))$ inactive vertices, with high probability. The corresponding E statements hold with $t_{\rm E}$ and $\mathcal{R}_{\rm E}(n,d)$ . For every fixed $c^{2}/2<\lambda<(c+1)^{2}/2$ and deterministic integer $a\sim\lambda n/d^{4}$ ,

|A_{\infty}^{\rm R}|=O(n/d^{3}),\qquad n-|A_{\infty}^{\rm E}|=O(\mathcal{R}_{\rm E}(n,d))=o(n)\quad\hbox{with high probability}.

If also $d\geq K_{0}\log n$ eventually for fixed $K_{0}>2/3$ , the E residual in this separation is $O(n^{2/3})$ with high probability. The comparison uses the same asymptotic mean degree; the exact means are $d$ and $d-d/n$ , respectively.

The proofs of Lemma 3 and Corollary 4 are given in Section 2. That section also records a sufficient logarithmic condition for an $O(n^{2/3})$ inactive remainder and an example with two degree values.

1.3 Relation to earlier work

Section VI, equation (24) of the arXiv:1003.5583v2 (2010) version of Baxter et al. (2010) gives the distributional threshold equation used here. Set its damage parameter to one and its threshold probabilities at zero, one, and two to $\alpha,(1-\alpha)\pi,(1-\alpha)(1-\pi)$ . The coefficients in (5) are Taylor coefficients of this established equation. We use the equation and its formal expansion as existing tools; our contribution is the quantitative terminal control specified above.

For independent edges, Janson et al. (2012) use independent Bernoulli marks, and Ballen and Guha (2015) allow nonuniform thresholds. The latter’s exact binomial response gives our mixed drift. Their Theorem 1 assumes a fixed positive gap $\beta$ through $d\zeta_{1}\leq 1-\beta$ , writing $d$ for their expected-degree parameter $\eta\phi$ . In our regime $d\pi=1-c/d$ , this gap vanishes, so that theorem does not directly apply. We apply the distribution-free forward/reverse empirical-process proof in Lemmas 7.2–7.3 of arXiv:1012.3535v2 to the mixed activation-time CDF, localize the early horizon and use dyadic error budgets. This is a specialization of established arguments, rather than a new exploration or maximal inequality.

For prescribed degrees, Amini (2010) requires a finite limiting mean and a bounded empirical second moment. Lelarge (2012) also treats independent random thresholds on prescribed-degree graphs, including uniform simple graphs. Condition 1 and Theorem 10 in the arXiv:1012.2062v4 (2011) version assume a fixed limiting degree law with finite mean and $\sum_{i}d_{i}^{2}=O(n)$ ; these assumptions exclude our growing-degree sequences. The $o_{p}(n)$ exploration approximation in its proof does not by itself resolve our bottleneck of order $n/d^{3}$ . Condition 1.1 in the arXiv:2103.00357v2 (2022) version of Amini et al. (2023) requires a limiting degree/threshold law and uniform exponential moments. These hypotheses fail in (3). We use the exponential half-edge exploration described by these authors. Our quantitative control includes local loss variance, stopped short-time predictable quadratic variation, the fixed-size seed mean and time interpolation. Garetto et al. (2016) already discuss degree heterogeneity and compare regular and two-level examples; their condition excluding one-edge activation and their homogeneous prescribed-degree calculation do not directly give our mixture.

Janson (2009) includes fixed-size initial sets and a critical-window result for fixed regular degree and common threshold. Prescribed seed size is therefore already covered in the literature. A different comparison concerns finite-time approximation: Rossi et al. (2019) develop quantitative finite-time coupling and concentration estimates for threshold dynamics (Sections 4.2–4.3.1 of the 2017 accepted manuscript). We prove below the excess-degree version needed here. Under our prescribed-degree assumptions and fixed supercritical seed margin, this adaptation yields an $O(n^{2/3})$ inactive remainder when $d\log d=o(\log n)$ ; see Appendix B. This uses the excess-degree offspring law, joint concentration of pairing and labels, and conditioning on simplicity. In the comparison established here, the subcritical terminal upper bound still requires control of activation after the certified finite horizon. The adaptation neither covers our full degree range nor proves the independent-edge counterpart.

For fixed degree $d$ and a common threshold $2\leq k\leq d-1$ , Balogh and Pittel (2007, Theorems 1–3) establish threshold and window estimates, including deterministic initial sets. Their equation (3) and equations (17)–(20) already express the threshold through the infimum of a deterministic response ratio. At the level of the deterministic response, replacing their binomial tail by the mixture of the tails for thresholds one and two gives our regular response; this substitution does not itself extend their probability theorems. Their passage from configurations to simple graphs uses a simplicity probability bounded away from zero for fixed $d$ ; it does not directly supply the uniform conditioning argument needed here.

Organization.

Section 2 proves the consequences stated above, gives further examples, and establishes the common deterministic barrier. Sections 3 and 4 connect it to the respective explorations and concentration bounds; the prescribed-degree proof then conditions on simplicity. Section 5 explains the precision obstruction to static inclusion transfer. Section 6 derives finite-degree and higher-moment corrections, and Section 7 records the remaining limits. The appendices supply the local concentration estimates and the slow-degree comparison with finite-time approximation.

2 Consequences and deterministic estimates

2.1 Empirical moments and consequences

Proof of Lemma 3.

Write $\mu_{3}=\mathbb{E}[(D-d)^{3}]$ . The deviation bound gives $0\leq v_{n}\leq C^{2}$ and $|\mu_{3}|\leq C\sqrt{d}\,\mathbb{E}[(D-d)^{2}]=O(d^{3/2})$ . The exact factorial-moment identities give the displayed formula for $b$ and

K=(1-2\pi)\left[d^{2}+(3v_{n}-3)d+2-3v_{n}+\frac{\mu_{3}}{d}\right].

Consequently $K/d^{2}=1+O(d^{-1})$ and, since $q_{n}\geq\kappa$ , $b=(q_{n}/d)(1+O(d^{-1}))$ . This proves (11). For any positive densities $T_{n},A_{n}$ with $T_{n}/A_{n}\to 1$ and fixed $\gamma\in(0,1)$ , eventually

(1-\gamma)T_{n}\leq(1-\gamma/2)A_{n},\qquad(1+\gamma)T_{n}\geq(1+\gamma/2)A_{n}.

Apply the appropriate theorem with margin $\gamma/2$ . If $v_{n}\to v$ , the fixed gap gives $c+1-v\geq\kappa$ , and the same argument proves the limiting specialization. ∎

Integer seed sizes.

In both (4) and (8), $n/d^{4}\to\infty$ . Thus rounding a size of order $n/d^{4}$ changes it by a relative $o(1)$ . More precisely, for any theorem centre $A_{\star}\asymp d^{-4}$ , $\lfloor(1-\gamma)nA_{\star}\rfloor$ satisfies its subcritical inequality and $\lceil(1+\gamma)nA_{\star}\rceil$ satisfies its supercritical inequality. The reference size $\lceil(1+\gamma/2)nA_{\star}\rceil$ is no larger than every permitted supercritical size for all sufficiently large $n$ . Uniform seeds of all prescribed sizes can be coupled as initial segments of one uniform permutation independent of graph and thresholds. Monotonicity of bootstrap closure then transfers a bound from a reference size to each permitted smaller or larger prescribed size.

Corollary 5 (A sufficient logarithmic condition).

In the supercritical conclusion of Theorem 1, suppose also $d\geq K_{0}\log n$ eventually for some fixed $K_{0}>1/(3\log 2)$ . Then $n-|A_{\infty}|=O(n^{2/3})$ with high probability. In the supercritical conclusion of Theorem 2, the same conclusion holds if $d\geq K_{0}\log n$ eventually for some fixed $K_{0}>2/3$ . These are sufficient conditions, not necessary conditions or optimal constants; the boundary equalities are not asserted.

Proof.

For P the function $f(x)=x\log 2-C\sqrt{x}\log 2-\log x$ is increasing for all sufficiently large $x$ . Hence

f(d)-\tfrac{1}{3}\log n\geq(K_{0}\log 2-\tfrac{1}{3})\log n-O(\sqrt{\log n})-O(\log\log n)\longrightarrow\infty.

It follows that $d2^{-d+C\sqrt{d}}=o(n^{-1/3})$ . For E, $g(x)=x/2-\log(1+x)$ is eventually increasing and $d/n=o(1)$ . Therefore

g(d)-\tfrac{1}{3}\log n-d/n\geq(K_{0}/2-\tfrac{1}{3})\log n-O(\log\log n)-o(1)\longrightarrow\infty,

so $(1+d)e^{-d/2+d/n}=o(n^{-1/3})$ . Insert these estimates into (2) and the corresponding supercritical theorem. ∎

Proof of Corollary 4.

For the regular model $C=v_{n}=0$ and

b_{\rm R}=\frac{c+1}{d}-\frac{c}{d^{2}},\qquad K_{\rm R}=(1-2\pi)(d-1)(d-2),\qquad nA_{\rm R}\sim t_{\rm R}.

Theorem 1 and Lemma 3 give the regular statements. The common range implies (8), since

\frac{d^{5}}{n}=\left(\frac{d}{n^{1/7}}\right)^{5}n^{-2/7}\longrightarrow 0.

Thus Theorem 2 applies as well. Put $L=c^{2}/2$ , $U=(c+1)^{2}/2$ and

\gamma_{*}=\frac{1}{4}\min\{1,\lambda/L-1,1-\lambda/U\}>0.

The ratios $a/t_{\rm E}\to\lambda/L$ and $a/(nA_{\rm R})\to\lambda/U$ place the seeds on opposite sides with margin $\gamma_{*}$ . The theorem bounds and a union bound give the joint conclusion. Independence between the two graphs is not needed: one may use any coupling of their laws, with common threshold labels and a uniform seed permutation independent of the graph pair. Rounding $\lambda n/d^{4}$ is harmless by $n/d^{4}\to\infty$ . The last assertion follows from Corollary 5. ∎

Corollary 6 (Two degree values).

Fix $c>0$ , $\kappa>0$ and $\gamma\in(0,1)$ . Let $n$ be even, $s\geq 0$ , and let $d-s,d+s$ be nonnegative integers with $nd$ even. Assign degree $d-s$ to half the vertices and $d+s$ to the other half. Assume $d\to\infty$ , $d=o(n^{1/7})$ , and

v_{n}=\frac{s^{2}}{d},\qquad q_{n}=c+1-v_{n}\geq\kappa.

Set $t_{2,n}=nq_{n}^{2}/(2d^{4})$ and $C_{2}=\sqrt{c+1}$ . The sequence is graphical eventually. For the uniform simple graph with these degrees and the stated independent threshold and seed model,

\begin{split}a\leq(1-\gamma)t_{2,n}&\ \Longrightarrow\quad|A_{\infty}|=O(n/d^{3})\quad\hbox{with high probability},\\ a\geq(1+\gamma)t_{2,n}&\ \Longrightarrow\quad n-|A_{\infty}|=O(\mathcal{R}_{\rm P}(n,d,C_{2}))\quad\hbox{with high probability}.\end{split}

If $d\geq K_{0}\log n$ eventually for fixed $K_{0}>1/(3\log 2)$ , the supercritical residual is $O(n^{2/3})$ with high probability. If additionally $v_{n}\to v<c+1$ , then $t_{2,n}$ may be replaced in these fixed-margin statements by $n(c+1-v)^{2}/(2d^{4})$ .

Proof.

The empirical mean is exactly $d$ , its variance is $s^{2}$ , and its third central moment is zero. The gap implies $s\leq\sqrt{c+1}\sqrt{d}$ , so the P deviation condition holds with fixed $C_{2}$ . In particular,

b=\frac{q_{n}}{d}+\frac{c(v_{n}-1)}{d^{2}},\qquad K=(1-2\pi)[d^{2}+(3v_{n}-3)d+2-3v_{n}].

Apply Theorem 1, Lemma 3, and Corollary 5. ∎

The conditions concern the two degrees themselves: $d,s$ may both be half-integers, and even $n$ alone does not ensure even $nd$ . For a concrete limiting-variance example, fix $0\leq v<c+1$ , take integer $d\to\infty$ and even $n$ in the stated range, and set $s=\lfloor\sqrt{vd}\rfloor$ . Then the degrees are nonnegative integers eventually, $nd$ is even, and

0\leq v-v_{n}\leq 2\sqrt{v/d},\qquad v_{n}\longrightarrow v.

A fixed positive gap follows, and the limiting specialization applies. For finite-degree corrections the actual $v_{n}=s^{2}/d$ must still be retained; this example supplies no $o(d^{-1})$ rate for $v_{n}-v$ . The case $s=0$ is regular. The agreement of a leading coefficient at the formal variance value $v=1$ does not make the independent-edge model a special case of the prescribed maximum-deviation hypothesis.

2.2 A common deterministic barrier

The two models share the same local mechanism: an unseeded response $F$ with $F^{\prime}(0)=1-b$ and $F^{\prime\prime}(0)=K$ produces a barrier of order $b^{2}/(2K)$ . The next lemma controls this barrier and the drift beyond it; the probabilistic arguments will then compare the exploration queues with that drift.

Lemma 7 (A small-deficit response barrier).

Let $d\to\infty$ and let $F:[0,1/2]\to[0,1)$ be nondecreasing, with $F(0)=0$ . Suppose that $F$ is $C^{3}$ on $[0,\varepsilon/d]$ for a fixed $\varepsilon>0$ , with one-sided endpoint derivatives, and that

F^{\prime}(0)=1-b,\quad F^{\prime\prime}(0)=K,\quad b_{*}/d\leq b\leq b^{*}/d,\quad K_{*}d^{2}\leq K\leq K^{*}d^{2},

F^{\prime\prime}\geq K/2,\quad|F^{\prime\prime\prime}|\leq C_{3}d^{3}\quad(0\leq z\leq\varepsilon/d).

Here $b_{*},b^{*},K_{*},K^{*},C_{3}$ are fixed positive constants. Assume $\sup_{\xi\leq z\leq 1/2}(1-F(z))=o(1)$ for each fixed $\xi\in(0,1/2)$ . Put $A=b^{2}/(2K)$ , $z_{0}=b/K$ and $h_{\alpha}(z)=\alpha+(1-\alpha)F(z)-z$ . Choose any fixed $L>8b^{*}/K_{*}$ . For every fixed $\eta\in(0,1)$ , if $\alpha_{\pm}=(1\pm\eta)A+o(A)$ , then, eventually, for a fixed $k_{\eta}>0$ ,

h_{\alpha_{+}}(z)\geq k_{\eta}\begin{cases}d^{-4},&0\leq z\leq L/d^{3},\\ d^{2}z^{2},&L/d^{3}\leq z\leq\varepsilon/d,\\ 1,&\varepsilon/d\leq z\leq 1/2,\end{cases}\qquad h_{\alpha_{-}}(z_{0})\leq-\eta A/2.

(13)

The constants depend only on the displayed fixed bounds, $L$ and $\eta$ . Moreover $R=(z-F)/(1-F)$ has a unique global maximum on $[0,1/2]$ , attained in $(0,8b/K)$ , of value $A+o(A)$ .

Proof.

Uniformly on $[0,L/d^{3}]$ , for $\alpha=O(A)$ ,

h_{\alpha}(z)=\alpha-A+\frac{K}{2}(z-z_{0})^{2}+O(d^{3}z^{3}+\alpha F(z)).

(14)

Indeed Taylor expansion also gives $F(z)=O(d^{-3})$ there, so the two remainder terms are $O(d^{-6})$ and $O(d^{-7})$ , both $o(A)$ . This proves the early and negative margins. For $z\geq L/d^{3}\geq 8b/K$ and $z\leq\varepsilon/d$ ,

F(z)-z\geq-bz+Kz^{2}/4\geq Kz^{2}/8.

Thus $F(\varepsilon/d)\geq q_{0}$ eventually for some fixed $0<q_{0}\leq 1/4$ . On $[\varepsilon/d,q_{0}/2]$ monotonicity gives $F-z\geq q_{0}/2$ ; on $[q_{0}/2,1/2]$ the tail hypothesis gives $F-z\geq 1/4$ eventually. Since $h_{\alpha}=F-z+\alpha(1-F)\geq F-z$ for $\alpha\geq 0$ , this proves the remaining margins.

For $B=1-F$ , on $[0,8b/K]$ ,

R^{\prime}=g/B^{2},\quad g=B-(1-z)F^{\prime},\quad g^{\prime}=-(1-z)F^{\prime\prime}.

Here $g$ is strictly decreasing, $g(0)=b$ and $g(8b/K)=-7b+O(d^{-3})<0$ . There is a unique early maximum. The preceding middle and late argument, starting at $8b/K$ , gives $F-z>0$ everywhere outside that interval, so $R<0$ there. Inside it $R=bz-Kz^{2}/2+o(A)$ uniformly; its maximum is $A+o(A)>0$ . All perturbations $o(A)$ are absorbed by the fixed margin. ∎

Verification for the two responses.

For the prescribed empirical law define, with $y=1-z$ ,

B_{k}(z)=y^{k-1}+(1-\pi)(k-1)zy^{k-2},\qquad F_{\rm P}(z)=1-\frac{1}{d}\mathbb{E}[DB_{D}(z)].

For independent edges define

F_{\rm E}(z)=1-e^{-dz}[1+(1-\pi)dz].

The P verification uses only (3), fixed $c,C,\kappa$ and $d\to\infty$ . Lemma 3 gives its $b,K,A$ . Eventually $\delta=\min_{i}d_{i}\geq 7$ , $\Delta=\max_{i}d_{i}\asymp d$ . For $F_{k}=1-B_{k}$ and $1\leq j\leq 5$ ,

F_{k}^{(j)}(z)=(-1)^{j+1}(k-1)_{j}y^{k-2-j}\{[1-j(1-\pi)]y+(1-\pi)(k-1-j)z\}.

In particular $F_{k}^{\prime}\geq 0$ and

F_{k}^{\prime\prime}=(k-1)(k-2)y^{k-4}\{(1-2\pi)y-(1-\pi)(k-3)z\}.

For E, for $1\leq j\leq 5$ ,

F_{\rm E}^{(j)}(z)=(-1)^{j+1}d^{j}e^{-dz}[1-j(1-\pi)+(1-\pi)dz].

It has $b=c/d$ , $K=(1-2\pi)d^{2}$ and $A^{\rm quad}=b^{2}/(2K)=A_{\rm E}(1+O(d^{-1}))$ . Both responses are nondecreasing and strictly below one on $[0,1/2]$ . For a sufficiently small fixed $\varepsilon>0$ the formulas imply $F^{\prime\prime}\geq K/2$ and $|F^{(j)}|=O(d^{j})$ , $2\leq j\leq 5$ , on $[0,\varepsilon/d]$ . For P, $k/d=1+O(d^{-1/2})$ uniformly, so the ratio of each second derivative to its value at zero is at least $1/2$ for small $\varepsilon$ . For E its ratio is $e^{-dz}[1-(1-\pi)dz/(1-2\pi)]$ , with the same property. For each fixed $\xi>0$ the tail bounds are

1-F_{\rm P}(z)\leq(1+\Delta)(1-\xi)^{\delta-2},\qquad 1-F_{\rm E}(z)\leq(1+d)e^{-d\xi}\quad(\xi\leq z\leq 1/2).

Thus Lemma 7 applies to both responses without a relation between $n$ and $d$ . The same formulas give $F^{\prime}=O(1)$ on each fixed early interval $[0,L/d^{3}]$ .

3 Proof for prescribed degrees

Write $\delta=\min_{i}d_{i}$ , $\Delta=\max_{i}d_{i}$ , and take $n$ large enough that $\delta\geq 4$ and $0<\pi<1$ . All constants below depend only on the fixed parameters of Theorem 1. Put $M=\sum_{i}d_{i}=nd$ . We first work with a uniform pairing of the $M$ labelled half-edges, counting edges with multiplicity. We compare the active queue with its deterministic drift, use concentration to locate stopping or passage, and then bound the final number of active or inactive vertices. Finally, we condition on simplicity and check that the failure probabilities remain $o(1)$ .

Response and deterministic margins.

Use $F=F_{\rm P}$ from Section 2.2, $B=1-F$ , $M=nd$ and $h_{\alpha}=\alpha+(1-\alpha)F-z$ . Lemma 3 gives $b\asymp d^{-1}$ , $K\asymp d^{2}$ and $A\asymp d^{-4}$ ; the present degree range gives $nA\to\infty$ . Take

a_{-}=\lfloor(1-\gamma)nA\rfloor,\qquad a_{+}=\lceil(1+\gamma/2)nA\rceil,\qquad\alpha_{\pm}=a_{\pm}/n.

Their rounding errors are $o(A)$ . Choose $L$ as in Lemma 7 and apply it with margins $\gamma$ and $\gamma/2$ respectively. Put $\eta=\varepsilon$ , $u=-\log(1-z)$ and $D_{\alpha}(u)=M(1-z)h_{\alpha}(z)$ . Since $1/2\leq 1-z\leq 1$ , for a sufficiently small fixed $k>0$ ,

D_{\alpha_{+}}(u)\geq\begin{cases}kn/d^{3},&0\leq z\leq L/d^{3},\\ knd^{3}z^{2},&L/d^{3}\leq z\leq\eta/d,\\ knd,&\eta/d\leq z\leq 1/2,\end{cases}\qquad D_{\alpha_{-}}(u_{*})\leq-kn/d^{3},\quad u_{*}=-\log(1-b/K).

(15)

Exploration and stopping convention.

Give every original half-edge an independent rate-one exponential clock, independently of the seeds and thresholds. Reserve one active end, without inspecting its future clock, and pair it to the first ringing unreserved end. Record a mark at the partner vertex, activate that vertex if its threshold is reached, and reserve the next active end. Use only revealed information to choose a reserved end. Stop at time $\tau$ when no active end remains after a pairing. Complete all remaining pairs uniformly. By exponential memorylessness each exposed partner is uniform among the other remaining ends. Induction on the number of remaining ends therefore gives a uniform full pairing conditional on every seed and threshold assignment, so this pairing is independent of these assignments.

Every activation is justified by exposed edges from active vertices. At stopping all ends of active vertices have been explored; the remaining pairs join inactive vertices, each of which has received fewer than its threshold many marks from active vertices. The final set is therefore closed under the activation rule, and is exactly the bootstrap closure. In particular completion adds no activations.

Let $X_{i}(u)$ count original clocks at vertex $i$ expiring by $u$ , including latent clocks of removed ends, and set

H(u)=\sum_{i\notin A_{0}}(d_{i}-X_{i}(u))\mathbf{1}_{\{X_{i}(u)<R_{i}\}}.

Up to and including $\tau$ , this is the actual number of inactive ends: before activation no end at that vertex was manually removed, and after activation its original-clock count stays at least its threshold. The formula remains a latent process after $\tau$ , without implying any further real activation. Its unconditional mean is exactly

\bar{H}(u)=(1-\alpha)Me^{-u}B(1-e^{-u}),\qquad Me^{-2u}-\bar{H}(u)=D_{\alpha}(u).

(16)

Let $W$ count unreserved ends, initially $W(0)=M-1$ . Each pairing decreases $W$ by two, with a fictitious final reservation if no active end is available. Thus the bookkeeping value of $W$ at $\tau$ is one less than the actual remaining count, and

Q(u):=W(u)-H(u)\geq 0\quad(u<\tau),\qquad Q(\tau)=-1.

(17)

All queue comparisons below include this terminal convention.

Local passage estimate.

Put $U=\log 2$ . The following estimate compares the queue with the three drift scales in (15).

Lemma 8 (Local concentration of the active queue).

Under the hypotheses of Theorem 1, consider the configuration model exploration just defined with either reference size $a_{-}$ or $a_{+}$ . Let $k,L,\eta$ be as in (15). There are constants $C_{2},k_{2}>0$ , depending only on $c,C,\kappa,\gamma$ , such that, except on an event of probability at most

C_{2}(1+d^{2})(1+\log d)\exp(-k_{2}n/d^{5}),

(18)

the following bounds hold simultaneously for $0\leq u\leq U\wedge\tau$ , where $z=1-e^{-u}$ :

|Q(u)-D_{\alpha}(u)|<\frac{k}{2}\begin{cases}n/d^{3},&0\leq z\leq L/d^{3},\\ nd^{3}z^{2},&L/d^{3}<z\leq\eta/d,\\ nd,&\eta/d<z\leq 1/2.\end{cases}

For size $a_{-}$ , on the same event, if $u_{*}\leq\tau$ then $|Q(u_{*})-D_{\alpha_{-}}(u_{*})|<kn/(2d^{3})$ .

The proof in Appendix A uses separate vertex, seed and stopped-queue estimates at the three drift scales.

For $a_{-}$ , if $\tau\geq u_{*}$ the queue would be less than $-1$ at $u_{*}$ , contradicting (17). Thus $\tau<u_{*}$ . For $a_{+}$ , stopping at any $\tau\leq U$ would give $Q(\tau)>0$ , again a contradiction. Thus $\tau>U$ .

Counts at the two outcomes.

In the subcritical case every eventually active nonseed vertex satisfies $X_{i}(u_{*})\geq R_{i}$ . The indicators of these events over all vertices are independent under the unconditioned clock and threshold law, and their sum has mean at most

\mu_{*}\leq\sum_{i}\left[\pi d_{i}z_{*}+\binom{d_{i}}{2}z_{*}^{2}\right]\leq C_{3}n/d^{3},\qquad z_{*}=b/K.

Bernstein’s inequality for Bernoulli sums, with deviation $n/d^{3}$ , bounds the probability that this sum exceeds $(C_{3}+1)n/d^{3}$ by $\exp(-k_{3}n/d^{3})$ . Adding $a_{-}=O(n/d^{4})$ proves the required count on the intersection with the stopping event. Independence of these two events is not required.

For the supercritical case put $N_{U}=\sum_{i}\mathbf{1}_{\{X_{i}(U)<R_{i}\}}$ . These indicators are independent under the unconditioned clock and threshold law, with

\mu_{U}=\mathbb{E}N_{U}=\sum_{i}2^{-d_{i}}[1+(1-\pi)d_{i}]\leq n(1+\Delta)2^{-\delta}.

Hoeffding gives

\Pr(N_{U}>\mu_{U}+n^{2/3})\leq e^{-2n^{1/3}}.

(19)

Take $k_{4}=2$ in (20). On $\{\tau>U\}$ every ultimately inactive vertex has $X_{i}(U)<R_{i}$ , since no end of an inactive vertex was manually removed. Intersecting passage and this unconditional count event therefore gives

n-|A_{\infty}|\leq N_{U}\leq\mu_{U}+n^{2/3}\leq B_{+}n[d2^{-d+C\sqrt{d}}+n^{-1/3}].

Simplicity, graphicality and uniformity.

For $M_{r}=\sum_{i}(d_{i})_{r}$ and $\nu=M_{2}/M=d-1+v_{n}$ , Lemma 5.1 of McKay and Wormald (1991) gives, in the present regime,

\log s=-\nu/2-\nu^{2}/4+O(d^{3}/n),\qquad s=\Pr\{\text{the pairing is simple}\}\geq e^{-C_{0}d^{2}}.

Indeed its condition $\Delta=o(M^{1/3})$ follows from $\Delta^{3}/M=O(d^{2}/n)=o(1)$ . Its additional terms are $O(\Delta^{4}/M)$ and its remainder is $O(\Delta^{3}/M)$ , by $M_{r}\leq M\Delta^{r-1}$ ; this yields the displayed specialization. The positive probability also proves eventual graphicality. Every simple graph has exactly $\prod_{i}d_{i}!$ pairings, so the conditional graph is uniform simple. The full pairing is independent of thresholds and seeds, whose joint law is therefore preserved. The clocks need not stay independent after conditioning.

Divide the sum of all applicable bad-event probabilities by $s$ . For either reference outcome a common upper envelope is

e^{C_{0}d^{2}}\left[C_{2}(1+d^{2})(1+\log d)e^{-k_{2}n/d^{5}}+e^{-k_{3}n/d^{3}}+4e^{-k_{4}n^{1/3}}\right]=o(1).

(20)

This uses only

\frac{n/d^{5}}{d^{2}}=\frac{n}{d^{7}}\to\infty,\qquad\frac{n/d^{5}}{\log n}\geq\frac{n^{2/7}}{\log n}\to\infty,\qquad\frac{d^{2}}{n^{1/3}}\to 0,

where the middle inequality holds eventually. In particular it does not require $d^{2}\gg\log n$ . Every permitted subcritical size is at most $a_{-}$ , and every permitted supercritical size is at least $a_{+}$ eventually, since $nA\to\infty$ . The independent permutation coupling in paragraph 2.1 transfers the reference conclusions by monotonicity. The empty and full seed cases are immediate. This completes the proof.

4 Proof for independent edges

We specialize the independent-mark construction and the distribution-free empirical-process argument of Janson et al. (2012) to the threshold mixture.

Put $p=d/n$ and $N=n-a$ . All assertions below concern sufficiently large $n$ , so $0<p<1/2$ and $0<\pi<1$ .

Condition on a particular seed set of size $a$ . At each real step $i$ , choose one active, unused vertex $u_{i}$ by a deterministic rule based only on the revealed history and thresholds. Reveal its edges to all other unused vertices. These edges are fresh: neither endpoint was previously used. Conditional on the history and all thresholds, they are independent Bernoulli $(p)$ variables. For each nonseed vertex $v$ , set $I_{v}(i)$ equal to this edge indicator when $v$ is a target of the step; in every other cell (including $v=u_{i}$ ) insert a fresh independent Bernoulli $(p)$ variable. Thus each new column has product Bernoulli $(p)$ law independent of all preceding columns and thresholds. After real exploration stops, fill the remaining columns with fresh variables. Unexposed graph edges are completed independently. Deferred decisions therefore give exactly the required graph law, independent of the thresholds, and an iid mark array independent of the thresholds. The artificial cells are auxiliary variables, not additional graph edges.

For integer $0\leq t\leq n$ , define

M_{v}(t)=\sum_{i=1}^{t}I_{v}(i),\quad S(t)=\sum_{v\notin A_{0}}{\bf 1}_{\{M_{v}(t)\geq R_{v}\}},\quad L(t)=a+S(t)-t.

Before a nonseed vertex first becomes active it is unused, and all its marks are genuine edges from distinct used vertices. After activation its mark total stays above its threshold. Hence up to and including real stopping the active count is exactly $a+S(t)$ . Since $L(t+1)-L(t)\geq-1$ , exploration stops at

T=\min\{0\leq t\leq n:L(t)\leq 0\},\qquad L(T)=0,\qquad|A_{\infty}|=T.

(21)

The minimum exists because $L(n)\leq 0$ . At stopping every active vertex has been used, and every inactive vertex has fewer than $R_{v}$ neighbours in that active set. The set is closed, and every activation used in constructing it was a legal bootstrap activation, proving the last identity. When $a=0$ , $T=0$ directly. No activation after $T$ in the auxiliary array is declared a real activation.

Independence of rows gives, at each deterministic integer time,

S(t)\sim\operatorname{Bin}(N,q(t)),\quad q(t)=1-(1-p)^{t}-(1-\pi)tp(1-p)^{t-1}\ (t\geq 1),\quad q(0)=0.

(22)

Different times need not be independent. Write $F=F_{\rm E}$ from Section 2.2, $z=t/n$ and $h_{\alpha}=\alpha+(1-\alpha)F-z$ . Factorial moments give

q(t)\leq z+d^{2}z^{2}/2,\qquad|q(t)-F(z)|\leq d^{2}z/n.

(23)

For the second bound, couple Bernoulli $(p)$ and Poisson $(p)$ with mismatch probability $p(1-e^{-p})\leq p^{2}$ , take $t$ independent copies and the same independent threshold. For $\mu_{a}(t)=a+Nq(t)-t$ this gives

|\mu_{a}(t)-nh_{\alpha}(t/n)|\leq d^{2}z.

(24)

Lemma 9 (Maximal control of the mixed empirical process).

Let $Y_{1},\ldots,Y_{N}$ be independent identically distributed positive integer variables with CDF $q$ , where $q(0)=0$ , $0<q(t)<1$ for finite $t\geq 1$ , and $q(t)\uparrow 1$ . Let $N\leq n$ and $D_{t}=\sum_{v}\mathbf{1}_{\{Y_{v}\leq t\}}-Nq(t)$ . Then for $x>0$ and each integer $u\geq 0$ ,

\Pr(\sup_{t\leq u}|D_{t}|>x)\leq 16nq(u)/x^{2},\qquad\Pr(\sup_{t\geq 0}|D_{t}|>x)\leq 8n/x^{2}.

(25)

Proof.

Use the own indicator filtrations $\mathcal{F}_{t}=\sigma(\mathbf{1}_{\{Y_{v}\leq s\}}:s\leq t,v)$ and $\mathcal{G}_{t}=\sigma(\mathbf{1}_{\{Y_{v}\leq s\}}:s\geq t,v)$ . The processes $D_{t}/(1-q(t))$ and $D_{t}/q(t)$ are respectively forward and reverse martingales where their denominators are nonzero. For an indicator not yet one, the next hazard is $(q(t+1)-q(t))/(1-q(t))$ ; in reverse, conditional on an indicator being one at $t+1$ , its probability of being one at $t$ is $q(t)/q(t+1)$ . These identities prove the conditional expectations; independence permits summation. No thresholds are revealed in these filtrations. Doob’s $L^{2}$ inequality and $\operatorname{Var}(D_{u})=Nq(u)(1-q(u))$ give

\mathbb{E}\sup_{t\leq u}|D_{t}|^{2}\leq 4Nq(u)/(1-q(u))\leq 8nq(u)\quad(q(u)\leq 1/2),

and $\mathbb{E}\sup_{t\geq u}|D_{t}|^{2}\leq 4N(1-q(u))/q(u)$ if $q(u)\geq 1/2$ . For the reverse bound first use a finite reversed horizon, then let it tend to infinity. Let $t_{1}$ be the last integer with $q(t_{1})\leq 1/2$ . The left bound at $t_{1}$ and the right bound at $t_{1}+1$ are each at most $4N$ , even when $q$ jumps across $1/2$ . Thus the global second moment is at most $8n$ . If $q(u)>1/2$ , this is also at most $16nq(u)$ . Markov’s inequality proves both assertions; $u=0$ is deterministic. This is the empirical-process proof of Lemmas 7.2–7.3 of Janson et al. (2012), applied to the mixed CDF. ∎

Apply this lemma to $Y_{v}=\min\{t:M_{v}(t)\geq R_{v}\}$ . Extend the iid auxiliary coins independently beyond $n$ if necessary; these extra coins are not graph edges. The $Y_{v}$ are iid with the mixed CDF in (22), including its continuation. Take reference sizes

a_{-}=\lfloor(1-\gamma/2)nA_{\rm E}\rfloor,\qquad a_{+}=\lceil(1+\gamma/2)nA_{\rm E}\rceil.

Choose $L$ as in Lemma 7. Since $A^{\rm quad}/A_{\rm E}=1+O(d^{-1})$ and $1/n=o(d^{-4})$ , Lemma 7 applies with margin $\gamma/2$ and $o(A^{\rm quad})$ perturbations. Set $\eta=\varepsilon$ , $m=\lfloor n/2\rfloor$ and $t_{*}=\operatorname{round}(nb/K)$ . The three errors in (24), relative to the corresponding queue scales, are bounded by $Ld^{3}/n$ , $d^{3}/(Ln)$ and $d^{2}/(2n)$ , all $o(1)$ . Also $t_{*}=O(n/d^{3})$ is early; $F^{\prime}=O(1)$ there makes time rounding an $O(1)=o(n/d^{4})$ drift error. Consequently, for some fixed $k>0$ ,

\mu_{a_{+}}(t)\geq 2k\begin{cases}n/d^{4},&z\leq L/d^{3},\\ nd^{2}z^{2},&L/d^{3}<z\leq\eta/d,\\ n,&\eta/d<z\leq 1/2,\end{cases}\qquad\mu_{a_{-}}(t_{*})\leq-2kn/d^{4}.

(26)

The early horizon $u=\lfloor nL/d^{3}\rfloor$ has $q(u)=O(d^{-3})$ . With budget $kn/d^{4}$ , (25) gives failure $O(d^{5}/n)$ , also controlling the negative test. For middle intervals put $s_{j}=2^{j}L/d^{3}<\eta/d$ and $u_{j}=\lfloor n\min(2s_{j},\eta/d)\rfloor$ . For $s_{j}\leq t/n\leq\min(2s_{j},\eta/d)$ use budget $knd^{2}s_{j}^{2}$ . Since $q(u_{j})\leq C(s_{j}+d^{2}s_{j}^{2})$ , failure is at most

C\{(nd^{4}s_{j}^{3})^{-1}+(nd^{2}s_{j}^{2})^{-1}\}.

The sums of $2^{-3j}$ and $2^{-2j}$ are bounded, giving $O((d^{5}+d^{4})/n)$ . These intervals and the early horizon cover all integer times up to $\eta/d$ ; empty intervals may be skipped. The late global bound with budget $kn$ costs $O(1/n)$ . No independence of intervals or survival conditioning is used. Hence

\Pr\{\exists t\leq m:L_{+}(t)\leq 0\}\leq Cd^{5}/n=o(1),\qquad\Pr\{L_{-}(t_{*})\geq 0\}\leq Cd^{5}/n.

(27)

By (21), the negative auxiliary test forces $T\leq t_{*}$ , giving $|A_{\infty}|=O(n/d^{3})$ below the threshold. Above it, $T>m$ , so the count at $m$ is a real active count. Separately, unconditional binomial Hoeffding gives $\Pr(|S(m)-Nq(m)|>n^{2/3})\leq 2e^{-2n^{1/3}}$ . Intersect this event with passage, without conditioning the binomial law on survival. Since $p\leq 1/2$ , $mp\leq d/2$ and $mp\geq d/2-d/n$ ,

1-q(m)=(1-p)^{m}[1+(1-\pi)mp/(1-p)]\leq(1+d)e^{-d/2+d/n}.

Thus

n-|A_{\infty}|\leq n-a-S(m)\leq n(1+d)e^{-d/2+d/n}+n^{2/3},

with failure at most $Cd^{5}/n+2e^{-2n^{1/3}}$ . This residual is $o(n)$ for every permitted $d\to\infty$ . Since $nA_{\rm E}\to\infty$ , each allowed subcritical size is at most $a_{-}$ and each allowed supercritical size is at least $a_{+}$ eventually. Paragraph 2.1 transfers the conclusions. The estimates conditional on a seed set fixed in advance are uniform in its labels. They do not permit adaptive seed selection or assert a simultaneous guarantee over all sets. The cases $a=0,n$ are immediate. This proves Theorem 2.

5 Precision required of a static sandwich

For common thresholds and seeds, graph inclusion preserves active sets, by induction on activation rounds. To examine the precision needed for coefficient transfer, we first record a consequence of the fixed-parameter theorem.

Lemma 10 (A compact range of effective parameters).

Suppose $r\to\infty$ and $r^{5}/n\to 0$ , and fix $0<m_{0}\leq M_{0}<\infty$ and $\gamma\in(0,1)$ . Let $c_{n}^{\prime}\in[m_{0},M_{0}]$ be deterministic and take $G(n,r/n)$ with independent thresholds satisfying $\Pr(R_{i}=1)=(1-c_{n}^{\prime}/r)/r$ and independent uniform seeds of prescribed size $a$ . Put $T_{n}^{\prime}=n(c_{n}^{\prime})^{2}/(2r^{4})$ . Then

\begin{split}a\leq(1-\gamma)T_{n}^{\prime}&\ \Longrightarrow\quad|A_{\infty}|=O(n/r^{3})\quad\hbox{with high probability},\\ a\geq(1+\gamma)T_{n}^{\prime}&\ \Longrightarrow\quad n-|A_{\infty}|=O(\mathcal{R}_{\rm E}(n,r))\quad\hbox{with high probability}.\end{split}

The constants may depend on $m_{0},M_{0},\gamma$ only. The E conclusion of Corollary 5 also holds with $r$ in place of $d$ .

Proof.

Cover $[m_{0},M_{0}]$ by finitely many intervals $[u_{j},v_{j}]\subset(0,\infty)$ so short that

(1-\gamma)v_{j}^{2}\leq(1-\gamma/2)u_{j}^{2},\qquad(1+\gamma)u_{j}^{2}\geq(1+\gamma/2)v_{j}^{2}.

Such a cover exists because both required upper bounds on $v_{j}/u_{j}$ are strictly larger than one. At fixed $r$ , increasing the parameter $c$ decreases the probability of threshold one. Couple thresholds using common independent uniform labels. For fixed graph and seeds, the final active set is then decreasing in $c$ . If $c_{n}^{\prime}\in[u_{j},v_{j}]$ , the subcritical comparison is with the easier model $c=u_{j}$ , and the supercritical comparison with the harder model $c=v_{j}$ . The displayed inequalities supply margin $\gamma/2$ . Apply Theorem 2 to the finitely many fixed endpoints and take the maximum of their constants and a union bound over their errors. If an interval is selected only on a subsequence, extend its tested seed sizes outside that subsequence by zero for the subcritical application and by $n$ for the supercritical application. The fixed-parameter theorem then applies on a full sequence. Finally apply the explicit residual bound to obtain the logarithmic assertion. ∎

Fix $c>0$ and let $d$ satisfy (8). For each $n$ , keep the threshold probability $\pi=(1-c/d)/d$ unchanged while replacing the edge-probability parameter $d$ by $r=(1+\delta_{n})d>0$ . Write $\beta=c/d$ . Assume, for some fixed $0<m\leq M<\infty$ ,

\frac{m}{d}\leq b_{n}^{\prime}:=1-\pi r=\beta-\delta_{n}(1-\beta)\leq\frac{M}{d}.

(28)

Then $\delta_{n}=O(1/d)$ , $r/d\to 1$ , and $c_{n}^{\prime}=rb_{n}^{\prime}$ stays in a fixed compact subinterval of $(0,\infty)$ . Moreover $\pi=(1-c_{n}^{\prime}/r)/r$ . Lemma 10 therefore gives the leading seed scale $T_{n}^{\prime}=n(b_{n}^{\prime})^{2}/(2r^{2})$ , with both fixed-margin outcomes and their stated residual bounds. Relative to the baseline scale, the exact ratio of these leading expressions is

\frac{T_{n}^{\prime}}{nc^{2}/(2d^{4})}=\frac{[1-\delta_{n}(1-\beta)/\beta]^{2}}{(1+\delta_{n})^{2}}=\left(1-\frac{\delta_{n}}{\beta(1+\delta_{n})}\right)^{2}.

(29)

The expression before squaring is positive under (28). Consequently this ratio tends to one if and only if $\delta_{n}=o(\beta)=o(1/d)$ . For example, $\delta_{n}=t/d$ with fixed $t<c$ gives the limiting ratio $(c-t)^{2}/c^{2}$ . A nonpositive or vanishing normalized deficit is outside (28); squaring does not extend the theorem there. Suppose every displacement in the band $|\delta|\leq\varepsilon_{n}$ satisfies (28) with the same fixed constants $m,M$ . The leading coefficient is then preserved to relative error $o(1)$ uniformly over the band if and only if $\varepsilon_{n}=o(1/d)$ . Necessity follows already from the endpoint $\delta=-\varepsilon_{n}$ , and sufficiency follows from (29). This is a statement about a full band, not about a possibly much smaller actual displacement within an upper bound.

Proposition 11 (Static inclusion at coefficient precision).

Let $d=d_{n}$ be integer with $nd$ even, $d\to\infty$ and $d=o(n^{1/7})$ , and let $0\leq\varepsilon_{n}=o(1/d)$ . For every coupling on the same labelled vertex set of

G^{-}\sim G(n,(1-\varepsilon_{n})d/n),\qquad G_{\rm R}\sim G_{n,d},

where $G_{n,d}$ is the uniform simple $d$ -regular graph,

\Pr(G^{-}\subseteq G_{\rm R})\leq\tfrac{1}{2}+o(1).

The error term can be chosen independently of the coupling. In particular, inclusion cannot hold with probability tending to one.

Proof.

At any fixed vertex let $Y$ be its degree in $G^{-}$ . Set $p=(1-\varepsilon_{n})d/n$ and $N=n-1$ . Then

Y\sim\operatorname{Bin}(N,p),\quad\mu=Np=(1-\varepsilon_{n})d(1-1/n),\quad\sigma^{2}=Np(1-p)\sim d\longrightarrow\infty,

d-\mu=\varepsilon_{n}d+(1-\varepsilon_{n})d/n=o(1).

For completeness, write $Y-\mu=\sum_{j=1}^{N}Z_{j}$ with independent centred Bernoulli summands. For fixed real $t$ ,

\mathbb{E}e^{itZ_{j}/\sigma}=1-\frac{t^{2}\mathbb{E}Z_{j}^{2}}{2\sigma^{2}}+\rho_{j},\qquad\sum_{j}|\rho_{j}|\leq\frac{|t|^{3}}{6\sigma^{3}}\sum_{j}\mathbb{E}|Z_{j}|^{3}\leq\frac{|t|^{3}}{6\sigma}\longrightarrow 0.

The maximum modulus of the terms added to one tends to zero, and the sum of their moduli is bounded. Taking logarithms of their product therefore yields $-t^{2}/2+o(1)$ . Thus $(Y-\mu)/\sigma$ converges in law to a standard normal variable. Since $(d-\mu)/\sigma\to 0$ , $\Pr(Y\leq d)\to 1/2$ . Inclusion in a $d$ -regular graph requires $Y\leq d$ , whatever the coupling. Its probability is therefore bounded by this same marginal probability, proving the assertion. ∎

Together with (29), this obstructs direct transfer of the leading coefficient by a static two-sided inclusion sandwich of relative width $o(1/d)$ in the common degree range. It does not rule out coarser sandwiches or other comparison arguments.

6 Deterministic finite-degree corrections

We now refine the quadratic approximation $A=b^{2}/(2K)$ using the deterministic response functions. The assumptions are stated locally: these calculations do not require the degree ranges used in the probability theorems.

\alpha_{\rm det}=\max_{0\leq z\leq 1/2}R(z),\qquad R(z)=\frac{z-F(z)}{1-F(z)}.

(30)

Indeed $h_{\alpha}(z)=(1-F(z))(\alpha-R(z))$ , and $1-F(z)>0$ on this interval. This barrier refines the deterministic quadratic approximation; it is not an identification of the finite- $n$ random critical-window centre.

6.1 Exact regular barrier

For regular degrees, let $d\geq 4$ and $0\leq\pi<1/(d-1)$ , and put $b=1-\pi(d-1)\in(0,1]$ . The deterministic barrier is explicit:

\widehat{z}_{\rm reg}=\frac{b}{(d-2)(d-3+b)},\qquad\alpha_{\rm det}^{\rm reg}=1-\frac{(1+b/(d-3))^{d-3}}{(1+b/(d-2))^{d-2}}.

Indeed $R_{d}=1-J_{d}^{-1}$ , where $J_{d}=(1-z)^{d-3}[1+(d-3+b)z]$ , and $J_{d}^{\prime}=(1-z)^{d-4}[b-(d-2)(d-3+b)z]$ . The optimiser satisfies $0<\widehat{z}_{\rm reg}\leq 1/(d-2)^{2}\leq 1/4$ , so it belongs to the interval in (30). At $\pi=0$ this reduces to the threshold-two response formula of Balogh and Pittel (2007); here it is used only as a deterministic identity. For the choice $\pi=(1-c/d)/d$ , put $m=d-3$ . The logarithm of $J_{d}(\widehat{z}_{\rm reg})$ is

\ell=(m+1)\log(1+b/(m+1))-m\log(1+b/m)=\frac{b^{2}}{2m(m+1)}+O(d^{-6}).

The linear terms cancel; the cubic difference is $\frac{b^{3}}{3}[(m+1)^{-2}-m^{-2}]=O(d^{-6})$ , and each fourth-order remainder is $O(d^{-7})$ . Since $\alpha_{\rm det}^{\rm reg}=1-e^{-\ell}=\ell+O(d^{-8})$ , $b=(c+1)/d-c/d^{2}$ and $[m(m+1)]^{-1}=d^{-2}(1+5/d+O(d^{-2}))$ give

\alpha_{\rm det}^{\rm reg}=\frac{(c+1)^{2}}{2d^{4}}+\frac{(c+1)(3c+5)}{2d^{5}}+O(d^{-6}).

6.2 General degree sequence

Proposition 12 (Finite-degree expansion).

Fix $c>0$ , $C\geq 0$ and $\kappa>0$ . Let $D$ have the empirical law of nonnegative integers $d_{1},\ldots,d_{n}$ , with exact mean $d\to\infty$ , and assume

\max_{i}|d_{i}-d|\leq C\sqrt{d},\qquad v_{n}=\operatorname{Var}(D)/d,\qquad\rho=c+1-v_{n}\geq\kappa.

Set $\pi=d^{-1}-cd^{-2}$ and $(x)_{j}=x(x-1)\cdots(x-j+1)$ . For sufficiently large $d$ define

\begin{split}B(z)&=\frac{1}{d}\mathbb{E}\!\left[D\left\{(1-z)^{D-1}+(1-\pi)(D-1)z(1-z)^{D-2}\right\}\right],\qquad F=1-B,\\ R(z)&=\frac{z-F(z)}{1-F(z)},\qquad\alpha_{\rm det}=\max_{0\leq z\leq 1/2}R(z),\\ b&=1-\pi\frac{\mathbb{E}[(D)_{2}]}{d},\qquad K=(1-2\pi)\frac{\mathbb{E}[(D)_{3}]}{d},\qquad A=\frac{b^{2}}{2K},\\ L_{3}&=-(2-3\pi)\frac{\mathbb{E}[(D)_{4}]}{d},\qquad L_{4}=(3-4\pi)\frac{\mathbb{E}[(D)_{5}]}{d}.\end{split}

The maximum is attained uniquely, at

\widehat{z}=\frac{b}{K}-\frac{L_{3}b^{2}}{2K^{3}}+\frac{b^{2}}{2K^{2}}+O(d^{-7}),

(31)

and

\begin{split}\alpha_{\rm det}={}&A-\frac{L_{3}b^{3}}{6K^{3}}+\frac{Ab}{K}-A^{2}\\ &+\frac{L_{3}^{2}b^{4}}{8K^{5}}-\frac{L_{4}b^{4}}{24K^{4}}+O(d^{-9}).\end{split}

(32)

All coefficients here are exact empirical moments. The remainders are uniform for fixed $c,C,\kappa$ ; no limit of $v_{n}$ and no relation between $n$ and $d$ are required. This is a deterministic response statement, not a graphicality assertion or a random critical-window theorem.

Proof.

The deterministic P response verification in Section 2.2 uses exactly the assumptions of this proposition. It gives $F^{\prime}(0)=1-b$ , $F^{\prime\prime}(0)=K$ , $F^{\prime\prime\prime}(0)=L_{3}$ , $F^{\prime\prime\prime\prime}(0)=L_{4}$ and $|F^{(j)}|=O(d^{j})$ for $2\leq j\leq 5$ on the early interval. Lemma 7 gives the unique global maximiser in $(0,8b/K)$ , with $b\asymp d^{-1}$ , $K\asymp d^{2}$ and $A\asymp d^{-4}$ . No probability degree range is used.

Put $z_{0}=b/K$ and $N=z-F$ . On $[0,8b/K]$ ,

N(z)=bz-Kz^{2}/2-L_{3}z^{3}/6-L_{4}z^{4}/24+O(d^{5}z^{5}),\qquad R^{\prime\prime}(z)=-K(1+O(d^{-2})).

Here $z_{0}=O(d^{-3})$ , $L_{3}=O(d^{3})$ and $L_{4}=O(d^{4})$ . At $z_{0}$ the numerator of $R^{\prime}$ is

N^{\prime}(z_{0})B(z_{0})+N(z_{0})F^{\prime}(z_{0})=-L_{3}z_{0}^{2}/2+A+O(d^{-5}).

The mean value theorem first gives $\widehat{z}-z_{0}=O(d^{-5})$ ; the same identity and curvature then give (31). Writing $\delta_{3}=-L_{3}z_{0}^{2}/(2K)$ , we have $\widehat{z}-z_{0}=\delta_{3}+O(d^{-6})$ . Completing the square yields

N(\widehat{z})=A-L_{3}z_{0}^{3}/6-L_{4}z_{0}^{4}/24+L_{3}^{2}z_{0}^{4}/(8K)+O(d^{-10}).

Indeed the neglected terms are bounded by constant multiples of $d^{5}z_{0}^{5}$ , $Kd^{-12}$ , $|L_{3}|z_{0}\delta_{3}^{2}$ and $|L_{4}|z_{0}^{3}|\delta_{3}|$ , each $O(d^{-10})$ . Finally $F(\widehat{z})=z_{0}-A+O(d^{-5})$ , whence

R(\widehat{z})=N(\widehat{z})(1+F(\widehat{z})+O(F(\widehat{z})^{2}))=N(\widehat{z})+Az_{0}-A^{2}+O(d^{-9}).

The denominator thus leaves an $O(d^{-9})$ remainder, although the numerator remainder above is $O(d^{-10})$ . This proves the claim. ∎

The expansion separates three levels of degree information. The leading term depends on $v_{n}$ through the excess-degree deficit. The third central moment can first contribute at absolute order $d^{-11/2}$ . After matching the first three moments, a fourth-moment difference of order $d^{2}$ can still change the deterministic barrier at order $d^{-8}$ . We now give the coefficients and an explicit example.

6.3 Variance, skewness, and two degree values

Let $\mu_{j}=\mathbb{E}[(D-d)^{j}]$ , $\rho=c+1-v_{n}$ , $r=c(v_{n}-1)$ , $k_{1}=3v_{n}-5$ and $k_{2}=8-9v_{n}+2c$ . The exact identities

b=\rho/d+r/d^{2},\qquad K=\left(1-\frac{2}{d}+\frac{2c}{d^{2}}\right)\left[d^{2}+(3v_{n}-3)d+2-3v_{n}+\frac{\mu_{3}}{d}\right]

and $\mu_{3}=O(d^{3/2})$ give, by expanding (32),

\begin{split}\alpha_{\rm det}=\frac{\rho^{2}}{2d^{4}}\bigg[1&+\frac{2r/\rho-k_{1}}{d}-\frac{\mu_{3}}{d^{3}}\\ &+\frac{r^{2}/\rho^{2}+k_{1}^{2}-k_{2}-2rk_{1}/\rho+2\rho/3}{d^{2}}+O(d^{-5/2})\bigg].\end{split}

(33)

The term $2\rho/3$ comes from the cubic response; the denominator correction $Ab/K$ has absolute order $d^{-7}$ and does not enter the displayed relative $d^{-2}$ coefficient. If $\mu_{3}=0$ , the remainder inside brackets improves to $O(d^{-3})$ . For equal empirical masses at $d-s$ and $d+s$ , require even $n$ and nonnegative integer values $d-s,d+s$ ; then $v_{n}=s^{2}/d$ and $\mu_{3}=0$ exactly. Graph applications also require even total degree $nd$ and the assumptions of the prescribed-degree probability theorem. The absolute remainder in (33) is $O(d^{-13/2})$ , or $O(d^{-7})$ when $\mu_{3}=0$ ; it is not the $O(d^{-9})$ remainder of the exact-coefficient formula. These expansions use actual empirical moments, with $c+1-v_{n}\geq\kappa>0$ . A variance limit is optional and cannot replace $v_{n}$ in the correction terms without a rate. For example, for integer $d$ and fixed $0\leq v<c+1$ , $s=\lfloor\sqrt{vd}\rfloor$ gives $v_{n}=v+O(d^{-1/2})$ ; this error can exceed the first relative $d^{-1}$ correction.

6.4 A distinction beyond variance

The third central moment can affect the barrier at order $d^{-11/2}$ through $K$ , as (33) shows. Even matching that moment leaves a further distinction. Indeed, expansion of the fourth factorial moment gives

\frac{\mathbb{E}[(D)_{4}]}{d}=d^{3}+(6v_{n}-6)d^{2}+(11-18v_{n})d+(11v_{n}-6)+(4-6/d)\mu_{3}+\frac{\mu_{4}}{d}.

For two degree laws with the same $d,v_{n},\mu_{3}$ and a common deviation bound, $b,K$ agree exactly. Their $L_{3}$ difference is $-(2-3\pi)(\mu_{4,2}-\mu_{4,1})/d=O(d)$ , whereas their $L_{4}$ difference is $O(d^{2})$ : this follows by expanding $(D)_{5}$ and using $\mu_{4}=O(d^{2})$ , $\mu_{5}=O(d^{5/2})$ . Consequently the differences of the $L_{3}^{2}$ and $L_{4}$ terms in (32) are $O(d^{-10})$ , and

\alpha_{{\rm det},2}-\alpha_{{\rm det},1}=\frac{(2-3\pi)b^{3}}{6dK^{3}}(\mu_{4,2}-\mu_{4,1})+O(d^{-9}).

(34)

For a concrete example take an integer $s\to\infty$ and put $d=s^{2}$ . The law with mass $1/2$ at each of $d-s,d+s$ , and the law with mass $3/4$ at $d$ and $1/8$ at each of $d-2s,d+2s$ , both have $v_{n}=1$ and $\mu_{3}=0$ . Their fourth central moments differ by $3d^{2}$ , so

\alpha_{{\rm det},2}-\alpha_{{\rm det},1}=c^{3}d^{-8}+O(d^{-9}).

Both are empirical degree laws when $n$ is divisible by eight, and admissible sequences can be chosen in (3). This distinguishes deterministic barriers at equal mean and variance; it does not resolve random threshold differences at this scale.

6.5 Independent-edge response

Fix $c>0$ and set $\pi=d^{-1}-cd^{-2}$ . The Poisson response and its deterministic barrier are

Q(x)=1-e^{-x}[1+(1-\pi)x],\qquad P(z)=\frac{z-Q(dz)}{1-Q(dz)},\qquad\alpha_{{\rm E},{\rm Pois}}=\max_{0\leq z\leq 1/2}P(z).

For $d\to\infty$ , the Taylor calculation in Proposition 12, applied directly to $F_{\rm E}(z)=Q(dz)$ , uses the exact coefficients

b_{\rm E}=c/d,\quad K_{\rm E}=(1-2\pi)d^{2},\quad L_{3,\rm E}=-(2-3\pi)d^{3},\quad L_{4,\rm E}=(3-4\pi)d^{4}.

It gives (32) with these coefficients and $A_{\rm E}^{\rm quad}=b_{\rm E}^{2}/(2K_{\rm E})$ , and in particular

\alpha_{{\rm E},{\rm Pois}}=\frac{c^{2}}{2d^{4}}\left[1+\frac{2}{d}+\frac{4-4c/3}{d^{2}}\right]+O(d^{-7}).

(35)

The derivative and localization bounds needed for this calculation are verified in the proof below; no bounded-support degree assumption is imposed on the Poisson response.

Proposition 13 (Integer-time binomial barrier).

Let $n$ be an integer, $d\to\infty$ and $n/d^{3}\to\infty$ . Put $p=d/n$ and, for integers $0\leq t\leq\lfloor n/2\rfloor$ , define

q(t)=1-(1-p)^{t}\left[1+\frac{(1-\pi)tp}{1-p}\right],\qquad\beta_{n}=\max_{0\leq t\leq\lfloor n/2\rfloor}\frac{t/n-q(t)}{1-q(t)}.

The maximum is over integers, and $q(0)=0$ . Then

|\beta_{n}-\alpha_{{\rm E},{\rm Pois}}|=O\left(\frac{1}{nd}+\frac{d^{2}}{n^{2}}\right),

(36)

and

\beta_{n}=\frac{c^{2}}{2d^{4}}\left[1+\frac{2}{d}+\frac{4-4c/3}{d^{2}}\right]+O\left(d^{-7}+\frac{1}{nd}+\frac{d^{2}}{n^{2}}\right).

(37)

The constants in (36) and (37) depend only on $c$ . Under $d^{5}/n\to 0$ the last remainder is $o(d^{-6})$ . An $O(d^{-7})$ remainder is obtained if additionally $d^{6}=O(n)$ . The full exact-coefficient expression (32), with the Poisson coefficients above, transfers to $\beta_{n}$ with remainder $O(d^{-9})$ if $d^{8}=O(n)$ . Constants in these simplified remainders may also depend on the bounds for $d^{6}/n$ or $d^{8}/n$ , respectively.

Proof.

All assertions are for sufficiently large $d$ , so $0<\pi<1$ and $p<1/2$ . For $x=tp$ , $r=t[-\log(1-p)-p]$ and $A_{x}=1+(1-\pi)x$ ,

1-q(t)=e^{-x-r}\left[A_{x}+\frac{(1-\pi)xp}{1-p}\right],\qquad 0\leq r\leq\frac{xp}{2(1-p)}.

Using $1-e^{-r}\leq r$ and boundedness of $e^{-x}(1+x)$ on $x\geq 0$ gives, with $z=t/n$ ,

|q(t)-Q(x)|\leq e^{-x}\left[A_{x}r+\frac{(1-\pi)xp}{1-p}\right]\leq C_{1}xp=C_{1}d^{2}z/n.

(38)

By the response verification and Lemma 7, the Poisson barrier has a unique maximiser $z_{P}\in(0,8b_{\rm E}/K_{\rm E})$ . For a fixed $L>8b^{*}/K_{*}$ , its response satisfies $F_{\rm E}-z\geq kd^{2}z^{2}$ on $[L/d^{3},\varepsilon/d]$ and $F_{\rm E}-z\geq k$ on $[\varepsilon/d,1/2]$ . These are bounds for the numerator, before any denominator comparison. The response-error ratios in (38) are at most $C/(nz)\leq Cd^{3}/(Ln)=o(1)$ in the middle interval and $O(d^{2}/n)=o(1)$ in the late interval, using only $n/d^{3}\to\infty$ . Thus $q(t)>t/n$ at every grid point outside $[0,L/d^{3}]$ ; their binomial barrier values are negative since $1-q(t)>0$ .

On $[0,L/d^{3}]$ , $|F_{\rm E}^{(j)}|=O(d^{j})$ for $2\leq j\leq 5$ , $F_{\rm E}^{\prime}=O(1)$ , and $P^{\prime\prime}=-K_{\rm E}(1+O(d^{-2}))$ . The Taylor calculation already proved therefore gives $z_{P}\asymp d^{-3}$ , $\alpha_{{\rm E},{\rm Pois}}\asymp d^{-4}$ and the full exact-coefficient expansion. Expanding

A_{\rm E}^{\rm quad}=\frac{c^{2}}{2d^{4}}\left[1+\frac{2}{d}+\frac{4-2c}{d^{2}}+O(d^{-3})\right]

and adding $-L_{3,\rm E}b_{\rm E}^{3}/(6K_{\rm E}^{3})=c^{3}/(3d^{6})+O(d^{-7})$ proves (35); the other terms start at order $d^{-7}$ .

Only on the localized interval do we compare denominators. There $F_{\rm E}=O(d^{-3})$ and, by (38), $q=O(d^{-3})$ at grid points, so both denominators are $1-O(d^{-3})$ . The exact identity

\frac{z-q(t)}{1-q(t)}-P(z)=-\frac{(1-z)(q(t)-F_{\rm E}(z))}{(1-q(t))(1-F_{\rm E}(z))}

then bounds the difference by $C_{3}/(nd)$ . Choose an integer $t_{P}$ nearest to $nz_{P}$ . Since $n/d^{3}\to\infty$ , its grid point is interior to the early interval and to $[0,\lfloor n/2\rfloor/n]$ . Stationarity $P^{\prime}(z_{P})=0$ and $|P^{\prime\prime}|=O(d^{2})$ give

P(t_{P}/n)=\alpha_{{\rm E},{\rm Pois}}+O(d^{2}/n^{2}).

Both $1/(nd)$ and $d^{2}/n^{2}$ are $o(d^{-4})$ . Thus this grid point has positive binomial barrier value; the binomial maximum is early. Comparison at this point gives the lower bound in (36), and comparison at a binomial maximiser gives its upper bound. No uniqueness of the integer maximiser is required.

Combining with (35) proves (37). Under $d^{5}/n\to 0$ , $d^{8}/n^{2}=(d^{5}/n)^{2}/d^{2}\to 0$ , proving the $o(d^{-6})$ assertion. If $d^{6}=O(n)$ , then $(nd)^{-1}=O(d^{-7})$ and $d^{2}/n^{2}=O(d^{-10})$ . If $d^{8}=O(n)$ , these errors are respectively $O(d^{-9})$ and $O(d^{-14})$ , which proves the full-expansion assertion. ∎

The integer-time error $O(d^{2}/n^{2})$ is distinct from rounding the number of seeds. For an integer seed size $a$ and $\alpha=a/n$ , the exact mean drift is

\frac{a+(n-a)q(t)-t}{n}=(1-q(t))\left(\alpha-\frac{t/n-q(t)}{1-q(t)}\right).

Consequently the smallest integer $a$ making all these mean drifts nonnegative is $\lceil n\beta_{n}\rceil$ ; for strictly positive mean drifts it is $\lfloor n\beta_{n}\rfloor+1$ . Their density errors are respectively less than $1/n$ and at most $1/n$ . This additional seed-rounding error is not part of (36) or (37). All these barriers concern exact deterministic means on the stated time interval. They do not locate the random critical-window centre or justify shrinking relative margins in the probability theorems.

7 Scope

The results concern independent uniform seeds of prescribed size, fixed positive model parameters and fixed relative margins. They establish almost complete activation, not full activation, and do not identify optimal seeds or a shrinking critical window. The prescribed assumptions impose bounded degree deviations and a fixed positive excess-degree gap; they do not cover arbitrary heavy-tailed degrees or thresholds correlated with the graph.

For prescribed degrees the local concentration exponent $n/d^{5}$ must dominate the $O(d^{2})$ simplicity cost and the logarithm of the grid factor; $d=o(n^{1/7})$ also controls the separate late estimate. For independent edges the maximal empirical-process estimate and dyadic budgets give passage failure $O(d^{5}/n)$ , so $d^{5}/n\to 0$ suffices. These are sufficient ranges, not optimal endpoints.

The explicit residuals tend to zero as fractions of $n$ for every allowed sequence with $d\to\infty$ .

Corollary 5 gives sufficient logarithmic conditions for an $O(n^{2/3})$ inactive remainder. They are not necessity claims: Appendix B also gives this remainder in the prescribed slow-degree regime $d\log d=o(\log n)$ . That adaptation does not establish the independent-edge counterpart or complete the subcritical terminal comparison with Rossi et al.

The finite-degree results are deterministic response statements. For the integer-time binomial barrier the three-term expansion has absolute remainder $O(d^{-7}+(nd)^{-1}+d^{2}/n^{2})$ , which is $o(d^{-6})$ throughout the independent-edge theorem’s range. Rounding the number of seeds adds a separate density error $O(1/n)$ . Neither error is a stochastic window estimate.

If $c+1-v_{n}$ approaches zero, the exact identity in (11) shows that the order and sign of $b$ require a separate analysis. No boundary-gap conclusion is asserted here. An empty seed set remains empty because all thresholds are positive.

Appendix A Local concentration for the prescribed exploration

We prove Lemma 8, retaining the fixed-size seed law. For independent centred variables of absolute value at most $B$ and total variance at most $V$ , we use the two-sided bound $2\exp[-x^{2}/(2(V+Bx/3))]$ . For a martingale starting at zero, the same bound applies to its running absolute maximum if its jumps are bounded by $B$ and its predictable quadratic variation is at most $V$ . These follow from $e^{t}-1-t\leq t^{2}/[2(1-|t|/3)]$ for $|t|<3$ , the associated exponential (super)martingale, and the choice $\lambda=x/(V+Bx/3)$ ; applying both signs gives the factor two. The martingale bound is applied only to stopped processes with a deterministic quadratic-variation bound.

One-vertex loss and the seed mean.

At fixed $u$ , put $z=1-e^{-u}$ and let $X\sim\operatorname{Bin}(k,z)$ be independent of $R$ . For $Y=(k-X)\mathbf{1}_{\{X<R\}}$ , write

L=k-Y=k\mathbf{1}_{\{X\geq R\}}+\mathbf{1}_{\{R=2,X=1\}}.

The two events are disjoint: activation loses all $k$ ends, and a threshold-two vertex with one mark loses one. Hence

\operatorname{Var}Y\leq\mathbb{E}L^{2}=k^{2}[\pi\Pr(X\geq 1)+(1-\pi)\Pr(X\geq 2)]+(1-\pi)\Pr(X=1)\leq\pi k^{3}z+kz+k^{4}z^{2}/2,

using $\Pr(X\geq 1),\Pr(X=1)\leq kz$ and $\Pr(X\geq 2)\leq k^{2}z^{2}/2$ . Conditionally on a fixed seed set, different vertex summands are independent and lie in $[0,\Delta]$ . Thus

\operatorname{Var}(H(u)\mid A_{0})\leq V(z):=\min\{3n[(\pi\Delta^{3}+\Delta)z+\Delta^{4}z^{2}/2],\ n\Delta^{2}\}.

(39)

Let $g_{i}(u)=\mathbb{E}Y_{i}(u)\in[0,\Delta]$ and $m_{A_{0}}(u)=\sum_{i\notin A_{0}}g_{i}(u)$ . Reveal the $a$ seed labels in random order without replacement. For $a<n$ the Doob increment of the sampled sum at draw $j$ is

\frac{n-a}{n-j}\bigl(g_{I_{j}}(u)-\bar{g}_{j-1}(u)\bigr),\qquad 1\leq j\leq a,

where $\bar{g}_{j-1}$ averages the labels not yet drawn. This follows by writing the expected remaining sample as $a-j$ times its remaining population mean. Its absolute value is at most $\Delta$ , so the bounded-increment exponential estimate gives

\Pr\{|m_{A_{0}}(u)-\bar{H}(u)|>e\}\leq 2e^{-e^{2}/(2a\Delta^{2})}.

(40)

For $a=0,n$ the discrepancy is zero. The same estimate includes the variation in seed degrees at $u=0$ . For the reference sizes, $a\Delta^{2}=O(n/d^{2})$ .

Stopped queue martingale.

Use the exploration filtration, which does not reveal future clocks of manually removed ends. If $J$ counts pairings through $\tau$ , its compensator is $\int_{0}^{u\wedge\tau}W(s-)\,ds$ : before stopping there are $W$ unreserved rate-one clocks. The fictitious terminal reservation makes every jump of $W$ exactly $-2$ , also at $\tau$ . Consequently

Z(u)=e^{2(u\wedge\tau)}W(u\wedge\tau)-(M-1)=-2\int_{0}^{u\wedge\tau}e^{2s}(dJ(s)-W(s-)\,ds)

is a martingale. For each deterministic $r\leq U$ ,

|\Delta Z|\leq 2e^{2r},\qquad\langle Z\rangle_{r}=4\int_{0}^{r\wedge\tau}e^{4s}W(s-)\,ds\leq 4e^{4r}Mr.

The value $W(\tau)$ may be $-1$ if the pairing is exhausted, but the intensity uses the nonnegative preterminal value $W(s-)$ . The martingale inequality therefore gives

\Pr\left\{\sup_{u\leq r\wedge\tau}|W(u)-Me^{-2u}|>e+1\right\}\leq p_{W}(e,r):=2\exp\left[-\frac{e^{2}}{2(4e^{4r}Mr+2e^{2r}e/3)}\right].

(41)

The extra one accounts for $W(0)=M-1$ .

Time interpolation.

For any deterministic interval $I=[l,r]\subset[0,U]$ and $e\geq 1$ , use a grid containing both endpoints with mesh at most $e/(4n\Delta^{2})$ . Its size is at most $N_{I}=\lceil 4(r-l)n\Delta^{2}/e\rceil+1$ (one point for a degenerate interval). At a grid point, conditional Bernstein and (40) give $|H-\bar{H}|\leq 2e$ , except with probability at most

2\exp\left[-\frac{e^{2}}{2(V(1-e^{-r})+\Delta e/3)}\right]+2\exp[-e^{2}/(2a\Delta^{2})].

Each $Y_{i}(u)$ is nonincreasing. Its clock-event rate is at most $d_{i}$ and each loss at most $d_{i}$ , whence $|g_{i}^{\prime}(u)|\leq d_{i}^{2}$ . Thus both $H$ and $\bar{H}$ are nonincreasing and $|\bar{H}^{\prime}|\leq n\Delta^{2}$ . Bracketing an intermediate value of $H$ by its two adjacent grid values, and varying the mean by at most $e/4$ , gives $|H-\bar{H}|\leq 9e/4$ on all of $I$ , including jumps. Combining with (41) yields

|Q-D_{\alpha}|\leq 4e+1\quad\hbox{on }I\cap[0,\tau],

(42)

except on an event of probability at most

p_{W}(e,r)+N_{I}\left\{2\exp\left[-\frac{e^{2}}{2(V(1-e^{-r})+\Delta e/3)}\right]+2\exp[-e^{2}/(2a\Delta^{2})]\right\}.

This is a union bound, with no independence between intervals, between $W$ and $H$ , or between the estimates and survival.

Three scales and the total passage probability.

Partition the $z$ interval into $[0,L/d^{3}]$ , dyadic intervals $[s,\min(2s,\eta/d)]$ starting at $s=L/d^{3}$ , and $[\eta/d,1/2]$ . Map them to $u=-\log(1-z)$ and choose budgets respectively

e_{0}=\rho n/d^{3},\qquad e_{s}=\rho nd^{3}s^{2},\qquad e_{\rm p}=\rho nd.

Fix $\rho>0$ sufficiently small relative to (15). The minimum budget tends to infinity, so $4e+1$ is smaller than half the appropriate margin, including the negative test at $u_{*}$ . On the early interval, (39) is $O(n/d)$ , $a\Delta^{2}=O(n/d^{2})$ and $Mr=O(n/d^{2})$ . The three exponents (vertex Bernstein, seed, queue) are therefore bounded below by constant multiples of $n/d^{5},n/d^{4},n/d^{4}$ .

On a middle interval $r=O(s)$ and $z_{r}\leq 2s$ . The corresponding exponents have the lower bounds

k\frac{nd^{4}s^{3}}{1+d^{2}s},\qquad knd^{8}s^{4},\qquad k\frac{nd^{5}s^{3}}{1+d^{2}s},

respectively. Here $V(z_{r})+\Delta e_{s}\leq Cn(d^{2}s+d^{4}s^{2})$ and $Mr+e_{s}\leq Cnds(1+d^{2}s)$ . Since $s^{3}/(1+d^{2}s)$ is increasing and $s\geq L/d^{3}$ , these bounds are at least constant multiples of $n/d^{5},n/d^{4},n/d^{4}$ . On the last interval use $V\leq n\Delta^{2}$ : all three exponents are at least $kn$ . This last budget is for passage only.

The early grid has $O(1+d^{2})$ points; a middle grid has $O(1+1/(ds))=O(1+d^{2})$ points; the late grid has $O(1+d)$ points. There are $O(1+\log d)$ intervals, because the ratio of the middle endpoints has order $d^{2}$ . Summing (42)’s failure bounds proves (18). This completes the local estimate without a global error of order $n^{2/3}d$ at the bottleneck.

Appendix B The slow-degree overlap with finite-time approximation

We record the adaptation used in the literature comparison, without introducing a separate threshold theorem. Fix $c>0$ , $C\geq 0$ , $\kappa>0$ and $\gamma\in(0,1)$ . The prescribed nonnegative integer degrees have even sum $nd$ , exact mean $d$ , and satisfy

|d_{i}-d|\leq C\sqrt{d},\qquad v_{n}=\frac{1}{nd}\sum_{i}(d_{i}-d)^{2},\qquad c+1-v_{n}\geq\kappa,\qquad d\to\infty,\quad d\log d=o(\log n).

Let $p_{k}=n^{-1}|\{i:d_{i}=k\}|$ , $\delta=\min_{i}d_{i}$ and $\Delta=\max_{i}d_{i}$ . Independently of the graph, thresholds are independent with probabilities $\pi=(1-c/d)/d$ and $1-\pi$ for one and two, and the seed is a uniform subset of deterministic size $a$ . With expectation taken under $p_{k}$ , set

b=1-\pi\frac{\mathbb{E}[D(D-1)]}{d},\qquad K=(1-2\pi)\frac{\mathbb{E}[D(D-1)(D-2)]}{d},\qquad A=\frac{b^{2}}{2K}.

Then $b\asymp d^{-1}$ , $K\asymp d^{2}$ , and $A\asymp d^{-4}$ , uniformly for the fixed parameters above. We show that $a\geq(1+\gamma)nA$ implies $n-|A_{\infty}|=O(n^{2/3})$ with probability tending to one on the uniform simple graph. The probability includes the graph, thresholds and seed. Since $nA\to\infty$ , it suffices by paragraph 2.1 to use $a_{0}=\lceil(1+\gamma/2)nA\rceil$ and $\alpha=a_{0}/n$ .

On undirected trees the nonroot recursion excludes the parent edge, as in Lemma 4 of the accepted manuscript of Rossi et al. (2019).

The printed Theorem 2 refers to recursion (7), whose formulas (13)–(14) use $k$ rather than $k-1$ trials. We therefore prove the finite-time estimate needed for the excess-degree recursion directly, following the coupling and concentration strategy of Section 4.2 of Rossi et al. (2019).

Lemma 14 (Finite-time approximation for an undirected pairing).

Fix degrees $d_{i}\geq 0$ with even sum $M=nd>0$ and maximum $\Delta\geq 2$ , and fix integer thresholds $r_{i}$ and labels $s_{i}$ , where $s_{i}\in\{0,1\}$ , $r_{i}=0$ if $s_{i}=1$ , and $r_{i}\geq 1$ otherwise. Let $u_{k,r,s}=n^{-1}|\{i:(d_{i},r_{i},s_{i})=(k,r,s)\}|$ . On a uniform pairing of the labelled half-edges, run synchronous progressive activation with these initial states and thresholds, counting edges with multiplicity, and let $Z_{t}=|A_{t}|/n$ . Set $B_{m,r}(x)=\Pr\{\operatorname{Bin}(m,x)\geq r\}$ , with $B_{m,0}=1$ and $B_{m,r}=0$ for $r>m$ , and define

f_{u}(x)=\sum_{k\geq 1,r,s}\frac{ku_{k,r,s}}{d}B_{k-1,r}(x),\qquad g_{u}(x)=\sum_{k,r,s}u_{k,r,s}B_{k,r}(x),

x_{0}=\sum_{k,r}\frac{ku_{k,r,1}}{d},\qquad y_{0}=\sum_{k,r}u_{k,r,1},\qquad x_{j+1}=f_{u}(x_{j}),\quad y_{j+1}=g_{u}(x_{j}).

For an integer $t\geq 1$ , put

Q_{t}=\sum_{j=1}^{t}\Delta^{j},\qquad b_{t}=\frac{\Delta Q_{t}(Q_{t}+1)}{2M}.

If $M\geq 2Q_{t}+2$ , then $|\mathbb{E}Z_{t}-y_{t}|\leq b_{t}$ . For every $h>0$ , without this size restriction,

\Pr\{|Z_{t}-\mathbb{E}Z_{t}|>h\}\leq 2\exp\left(-\frac{nh^{2}}{128d\Delta^{2t}}\right).

Consequently, if also $b_{t}\leq\varepsilon/2$ , then

\Pr\{|Z_{t}-y_{t}|>\varepsilon\}\leq 2\exp\left(-\frac{n\varepsilon^{2}}{512d\Delta^{2t}}\right).

All these bounds are uniform over the fixed labels. If instead the labels $(r_{i},s_{i})$ are iid, independently of the pairing, with law $\lambda_{r,s}$ , the expectation bound holds with $u_{k,r,s}=p_{k}\lambda_{r,s}$ , where $p_{k}=n^{-1}|\{i:d_{i}=k\}|$ . The concentration denominator becomes $(128d+8)\Delta^{2t}$ , and the combined denominator becomes $(512d+32)\Delta^{2t}$ . Here probability averages over pairing and labels.

Proof.

Choose a uniform root vertex. Its type has law $u$ . For each nonroot vertex of an independent comparison tree, choose a uniform half-edge from all $M$ half-edges, with replacement, and use the type of its incident vertex. These independent types have law $ku_{k,r,s}/d$ . The root has $k$ children and every nonroot vertex of degree $k$ has $k-1$ children.

On a tree, removing the parent edge does not change a child’s contribution to the first activation of its parent: until that activation the parent has been inactive at all earlier times. Induction on time, applying this observation to each child subtree, therefore identifies the root state with the outward-oriented tree calculation. With seeds encoded by threshold zero, the states in this calculation are nondecreasing in time. Independent subtrees then give exactly the recursions above, and the root activation probability at time $t$ is $y_{t}$ .

Explore the pairing breadth first from the same root, exposing edges only from vertices at distance less than $t$ . At most $Q_{t}$ partners are needed. After $h$ successful tree discoveries at most $h+1$ vertices have been seen. Draw the next comparison half-edge $U$ uniformly from all $M$ half-edges. If it is an eligible partner for the current half-edge, use it in the pairing; otherwise choose a uniform eligible partner independently. This rule gives a uniform partner: every eligible half-edge has probability $1/|E|$ , where $E$ is the eligible set. All ineligible half-edges belong to already seen vertices. Thus, until the first failure, if $U$ belongs to an unseen vertex, both constructions agree and discover a new vertex. Declare failure whenever $U$ belongs to a seen vertex. Its conditional probability is at most $(h+1)\Delta/M$ . The size assumption ensures that partners remain available during this exploration. A union bound gives failure probability at most

\sum_{h=0}^{Q_{t}-1}\frac{(h+1)\Delta}{M}=b_{t}.

Unexposed edges incident only to depth- $t$ vertices cannot affect the root state by time $t$ . Complete the remaining pairing uniformly. The coupled root states agree outside the failure event, proving the expectation bound.

For concentration, generate a uniform pairing by a uniform permutation of the $M$ half-edges and pair consecutive positions. A transposition changes at most two pairs and involves at most four endpoint vertices. A state at time $t$ can change only within distance $t-1$ of those endpoints in at least one of the two graphs. Each such ball has at most $\sum_{j=0}^{t-1}\Delta^{j}\leq\Delta^{t}$ vertices. Hence the activation count changes by at most $8\Delta^{t}$ under any transposition. This estimate also covers loops and repeated edges.

Expose the permutation one position at a time. Conditional completions for two possible next values are in bijection by transposing those values in the remaining positions. Their expected activation counts therefore differ by at most $8\Delta^{t}$ . Each increment of the Doob martingale for $|A_{t}|$ is bounded in absolute value by $8\Delta^{t}$ . Azuma’s inequality, with at most $M$ increments, yields

\Pr\{\big||A_{t}|-\mathbb{E}|A_{t}|\big|>nh\}\leq 2\exp\left(-\frac{n^{2}h^{2}}{2M(8\Delta^{t})^{2}}\right),

which is the stated concentration estimate. Taking $h=\varepsilon/2$ and using the expectation bound proves the last assertion. For iid labels, the same breadth-first coupling assigns each newly discovered vertex’s fresh independent label to its tree occurrence; at the first repeated vertex, assign that occurrence a fresh independent label and fill the rest of the comparison tree independently. Discovery order does not use labels, so this gives mean type law $p_{k}\lambda_{r,s}$ and the same bias $b_{t}$ .

For concentration expose the pairing permutation and then the independent labels. Changing one label affects only its radius- $t$ ball, of size at most $\sum_{j=0}^{t}\Delta^{j}\leq 2\Delta^{t}$ . The additional $n$ martingale increments are therefore bounded by $2\Delta^{t}$ . The squared increment budget is $(64M+4n)\Delta^{2t}$ ; Azuma gives denominator $(128d+8)\Delta^{2t}$ . Taking $h=\varepsilon/2$ gives the combined bound. ∎

Initially use iid Bernoulli $(\alpha)$ seeds, independently of the thresholds and pairing. The mean tree maps are

f_{\alpha}(x)=\alpha+(1-\alpha)F_{\rm P}(x),

g_{\alpha}(x)=1-(1-\alpha)\sum_{k}p_{k}\big[(1-x)^{k}+(1-\pi)kx(1-x)^{k-1}\big].

Set $x_{0}=y_{0}=\alpha$ , $x_{t+1}=f_{\alpha}(x_{t})$ and $y_{t+1}=g_{\alpha}(x_{t})$ .

Lemma 7 applies to the mean P response and $\alpha=(1+\gamma/2)A+o(A)$ . The increments $f_{\alpha}(x)-x$ are at least $kd^{-4}$ up to $L/d^{3}$ , $kd^{2}x^{2}$ up to $\varepsilon/d$ , and $k$ up to $1/2$ . The first interval takes $O(d)$ steps. Crossing each dyadic $[s,2s]$ takes at most $1+C/(d^{2}s)$ steps. Their sum is $O(d)$ , since $s$ starts at $L/d^{3}$ and $\sum_{j}2^{-j}<\infty$ . The remaining interval takes $O(1)$ steps. Thus a fixed $L_{0}$ gives $x_{T_{0}}\geq 1/2$ for $T_{0}=\lceil L_{0}d\rceil$ .

For $q_{t}=1-x_{t}\leq 1/2$ , the displayed responses imply, eventually,

q_{t+1}\leq(1+\Delta)q_{t}^{\delta-2}\leq q_{t}^{\delta/2},\qquad 1-g_{\alpha}(x_{t})\leq(1+\Delta)q_{t}^{\delta-1}\leq q_{t}^{\delta/2}.

The second inequalities use $\log(1+\Delta)=o(\delta)$ , and remain valid at $q_{t}=0$ . Choose

r=\max\left\{0,\left\lceil\frac{\log((\log n)/(3\log 2))}{\log(\delta/2)}\right\rceil\right\},\qquad T=T_{0}+r+1.

Then $1-y_{T}\leq n^{-1/3}$ and $T\log(\Delta+1)=O(d\log d+\log\log n)=o(\log n)$ .

Apply the iid-label part of Lemma 14 at $t=T$ with $\varepsilon=n^{-1/3}$ . Since $Q_{T}\leq 2\Delta^{T}=n^{o(1)}$ , eventually $nd\geq 2Q_{T}+2$ and $b_{T}=n^{-1+o(1)}\leq\varepsilon/2$ . The failure probability is at most

2\exp\left[-\frac{n^{1/3}}{(512d+32)\Delta^{2T}}\right].

Condition now on exactly $a_{0}$ seeds and on simplicity. The seed count $a_{0}$ is a mode of $\operatorname{Bin}(n,a_{0}/n)$ , with probability at least $1/(n+1)$ ; its conditioning gives uniform seeds of size $a_{0}$ . Pairing and labels are independent, so the threshold law remains iid and independent of these seeds and the uniform simple graph. The McKay–Wormald estimate from Section 3 applies in the slow range and gives $s_{n}\geq e^{-C_{0}d^{2}}>0$ , also proving graphicality. The resulting total failure is at most

2(n+1)\exp\left[C_{0}d^{2}-\frac{n^{1/3}}{(512d+32)\Delta^{2T}}\right]=o(1),

because $d=n^{o(1)}$ , $\Delta^{2T}=n^{o(1)}$ , and the negative exponent dominates both $d^{2}$ and $\log(n+1)$ . On the good event $n-|A_{T}|\leq 2n^{2/3}\leq 3n^{2/3}$ . Permanent activation gives $A_{T}\subseteq A_{\infty}$ , proving the remainder. This argument establishes no subcritical terminal upper bound and does not apply unchanged to the independent-edge model.

Author disclosure

The author is employed by Yandex. This research was conducted independently in the author’s personal time and received no dedicated funding from Yandex. Some computational work used Yandex equipment and computing infrastructure. The views expressed are solely those of the author and do not necessarily represent those of Yandex. The author declares no other competing interests.

AI assistance

OpenAI’s GPT-6 Astra agents were used as research assistants for literature analysis, mathematical calculations and proof arguments, and manuscript preparation. OpenResearch was used to organize research tasks, experiments, and artifacts. These tools do not replace independent human peer review. The author is responsible for all mathematical results and the final manuscript.

References

Amini (2010) H. Amini. Bootstrap percolation and diffusion in random graphs with given vertex degrees. Electronic Journal of Combinatorics, 17(1), R25, 2010. doi:10.37236/297.
Amini et al. (2023) H. Amini, E. Bayraktar, and S. Chakraborty. A central limit theorem for diffusion in sparse random graphs. Journal of Statistical Physics, 190(3), article 57, 2023. doi:10.1007/s10955-023-03068-9. The condition numbering cited here is from arXiv:2103.00357v2 (2022).
Ballen and Guha (2015) P. Ballen and S. Guha. Behavioral intervention and non-uniform bootstrap percolation. 2015. arXiv:1512.00834v1 (2015).
Balogh and Pittel (2007) J. Balogh and B. G. Pittel. Bootstrap percolation on the random regular graph. Random Structures & Algorithms, 30(1–2):257–286, 2007. doi:10.1002/rsa.20158.
Baxter et al. (2010) G. J. Baxter, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes. Bootstrap percolation on complex networks. Physical Review E, 82(1), 011103, 2010. doi:10.1103/PhysRevE.82.011103. The section and equation numbering cited here is from arXiv:1003.5583v2 (2010).
Garetto et al. (2016) M. Garetto, E. Leonardi, and G. L. Torrisi. Generalized threshold-based epidemics in random graphs: the power of extreme values. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science, ACM, pp. 37–50, 2016. doi:10.1145/2896377.2901455. The version consulted is arXiv:1603.04643v1.
Janson (2009) S. Janson. On percolation in random graphs with given vertex degrees. Electronic Journal of Probability, 14:87–118, 2009. doi:10.1214/EJP.v14-603.
Janson et al. (2012) S. Janson, T. Łuczak, T. Turova, and T. Vallier. Bootstrap percolation on the random graph $G_{n,p}$ . Annals of Applied Probability, 22(5):1989–2047, 2012. doi:10.1214/11-AAP822. The maximal estimates adapted here are Lemmas 7.2–7.3, pp. 22–24, of arXiv:1012.3535v2.
Lelarge (2012) M. Lelarge. Diffusion and cascading behavior in random networks. Games and Economic Behavior, 75(2):752–775, 2012. doi:10.1016/j.geb.2012.03.009. The condition and theorem numbering cited here refers to arXiv:1012.2062v4 (2011).
McKay and Wormald (1991) B. D. McKay and N. C. Wormald. Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2})$ . Combinatorica, 11(4):369–382, 1991. doi:10.1007/BF01275671. Published article PDF hosted by B. D. McKay.
Rossi et al. (2019) W. S. Rossi, G. Como, and F. Fagnani. Threshold models of cascades in large-scale networks. IEEE Transactions on Network Science and Engineering, 6(2):158–172, 2019. doi:10.1109/TNSE.2017.2777941. The coupling and concentration strategy adapted here is in Sections 4.2–4.3.1, pp. 7–10, of the 2017 accepted manuscript. The excess-degree estimate used here is proved separately in this article. See the University of Twente repository version.