The continuation argument

The proof separates the part of the process governed by uniform subgraph counts from the final evolution of individual edges. Stop at a deterministic time when the edge density is approximately \(p=n^{-1/2+\epsilon}\), for a small fixed \(\epsilon>0\). The graph then has \[m=\frac{n^2p}{2}\quad\text{edges},\qquad D=np^2\] triangles through each edge to relative error \(o(1)\). Section 2 states the exact properties needed and verifies their application from the public removal estimates.

The continuation analysis uses backward priority exploration, whose hypergraph form appears in Spencer’s work (Spencer 1995, secs. 2–4). Grable formulated triangle packing as a uniform priority scan and used adaptive exposure decision trees in his concentration analysis (Grable 1997, sec. 1 and 4). The quantitative issue here is to follow a growing rescaled time interval and to approximate joint survival on the scale of its vanishing probability. A fixed-time local approximation alone does not give the precision required for a second moment.

Give the triangles of this graph fresh independent uniform priorities and scan them in increasing order, accepting a triangle when all its edges remain. This represents the continuation of uniform removal. An edge survives precisely when a recursive test returns true. A child test asks whether the other two edges of a candidate triangle survive before its priority. We test the two edges with one jointly ordered list of candidates, which is essential to the later visitation estimate. Section 3 proves this rule and constructs an auxiliary tree in which each occurrence of a candidate receives an independent priority.

In this independent model, the survival probabilities satisfy exact product equations. The scalar comparison is \[q(t)=(1+2Dt)^{-1/2},\qquad 0\le t\le1.\] This is Spencer’s scalar branching law after the time change \(c=Dt\) (Spencer 1995, sec. 3, equation (9)). Bal and Bennett obtained related matching estimates for fixed-degree random regular hypergraphs and regular hypergraphs of growing girth (Bal and Bennett 2023, Corollaries 3–4); here \(D\) grows with \(n\), and the terminal rescaled time is \(D\). To prove a uniform approximation by \(q\), one needs stability of a matrix acting on the graph’s edges. We obtain it from cycle counts in vertex links. Each normalized link matrix is close in Euclidean norm to its averaging projection; the sum of these projections has a directly controlled semigroup in the maximum norm. A finite perturbation expansion then gives the stability needed by the product equations (Section 4).

The final issue is the difference between independent occurrences and repeated triangle types in the finite graph. We compare the complete candidate lists exposed by one or two root queries. A repetition forces an extra graph edge in the union of at most two ancestral query paths (Section 5). Small rooted-template bounds control the number of such witnesses. Joint time ordering controls the probability that their calls are visited. Their combination gives an absolute error \(o(1/D)\) (Section 6). This precision matters because the two-root survival probability is itself of order \(1/D\).

The one- and two-root probabilities determine the first and second moments of \(F_n\). Their normalization is \[mq(1)=\frac{n^2p}{2\sqrt{1+2np^2}} \sim\frac{n^{3/2}}{2\sqrt2}.\] Uniformity over the good prefix graphs, together with a sufficiently small prefix failure probability, gives the unconditional conclusion in Section 7.

The continuation estimates developed here are the maximum-norm stability of the unfolding and the smaller than \(D^{-1}\) error for adaptive paired queries. Both the numerical constant and the moment conclusion use these estimates.

Conventions

All graphs are finite and simple. An embedding is injective and preserves edges; it need not preserve nonedges. Thus an embedding of a fixed labeled cycle counts its ordered vertex labels, without division by automorphisms. The notation \((1\pm a)b\) means a number in \([(1-a)b,(1+a)b]\). All unspecified constants below are independent of \(n\) and of the realized good prefix graph. They may depend on the fixed parameters introduced next. A statement holds with superpolynomially high probability if its failure probability is \(n^{-\omega(1)}\), meaning smaller than \(n^{-C}\) for every fixed \(C>0\) when \(n\) is sufficiently large.

Priorities and the finite test

Independent priorities give the standard random greedy packing representation; see Spencer (Spencer 1995, sec. 1), Grable (Grable 1997, sec. 1), and the triangle-removal accounts (Bohman et al. 2015, sec. 1.2) (Joos and Kühn 2025, sec. 14.1).

Assign independent uniform priorities \(U_T\in[0,1]\) to the triangles \(T\in\mathcal T\). Scan the triangles in increasing priority order, accepting a triangle precisely when all three of its edges remain, and deleting those edges on acceptance. We work on the probability-one event that all priorities are distinct. An edge is untouched before \(t\) if no accepted triangle with priority strictly below \(t\) contains it.

In applying the lemma after the good prefix, the priorities are fresh random variables on the triangles of the fixed graph \(G\). The original process has the same continuation law because its next-step rule depends only on its current graph.

A call consists of a focus (one or two edges), a threshold \(t\), and, for a two-edge focus, a parent triangle. The finite test has two forms:

• A root call has focus \(\{e\}\), threshold \(t\in[0,1]\), and no parent. Its candidates are all triangles containing \(e\).

• A non-root call has focus \(\{f,g\}\subset T\), parent triangle \(T\), and threshold \(t=U_T\). Its candidates are all triangles meeting the focus, except \(T\).

Distinct triangles meet in at most one graph edge. Consequently every candidate \(S\) contains exactly one focus edge, denoted \(e(S)\). Its child call has focus \(S\setminus\{e(S)\}\), parent \(S\), and threshold \(U_S\).

At a call the test performs the following steps.

1. Expose the priorities of all candidates, in a fixed deterministic order of triangle types. Each candidate occurs once in this list.

2. Sort the candidates by priority and consider those with \(U_S<t\) in that order. For a pair focus this is one joint ordering of the candidates at both focus edges.

3. Evaluate each considered candidate’s child. At the first child returning true, stop and return false. If no child returns true, return true.

Exposing a candidate does not require visiting its child: priorities above the threshold and candidates skipped after an earlier success are also exposed. All calls use the same finite family \((U_T)_{T\in\mathcal T}\). The test has no side effects; it does not delete edges or change any priority.

The parent omission is local to its call and is justified by the strict threshold. It does not erase that triangle from descendant lists. Also, the two finite survival events in a pair call need not be independent. We retain their joint chronological test, including its stopping rule, throughout the comparison argument.

Fresh randomness at each occurrence

Backward exploration and comparison with independent branching occur in Spencer’s analysis (Spencer 1995, secs. 2–4). We retain the paired query rule above and all candidate-list exposures for the finite comparison.

For a fixed root type, first construct the deterministic tree of all possible calls. Each node has one child for each candidate on its list, with the focus and parent specified above. The tree is countable and finitely branching. A triangle type may label many different child occurrences.

Assign an independent uniform variable to each child occurrence. This variable serves both as the candidate priority in its parent’s list and as the child’s threshold if the child is visited. Apply the same joint scanning and stopping rule on this tree. Different occurrences of a triangle type now have independent priorities; different root queries use disjoint trees with independent variables. We call this the independent unfolding.

We also allow a singleton root of type \(e\) with a specified triangle \(T\ni e\) omitted from its root list. The omission affects that list only. Descendant occurrences of \(T\) remain available whenever their own parent rule allows them. A two-edge root with focus \(\{f,g\}\subset T\), omitted parent \(T\), and prescribed threshold \(t\) is defined by the same independent construction.

The finiteness argument uses factorial decay along decreasing-priority paths, as in the local construction of graph adsorption processes by Penrose and Sudbury (Penrose and Sudbury 2005, Proposition 1 and its proof). We give the argument for the present occurrence trees.

We may consequently evaluate a child’s subtree hypothetically even when the chronological test never reaches that child. These hypothetical outputs characterize the root event: a call returns true if and only if no child with priority below its threshold would return true. For fixed priorities this indicator is nonincreasing in the root threshold, since each child’s threshold is its own occurrence priority.

Exact probability identities

Let \(q_e(t)\) be the probability that a full singleton root at \(e\) returns true at threshold \(t\) in the independent unfolding. Let \(q_{e,T}(t)\) be the same probability when \(T\ni e\) is omitted only from that singleton root list. For \(T=\{e,f,g\}\in\mathcal T\), define \[ I_{e,T}(t)=\int_0^t q_{f,T}(v)q_{g,T}(v)\,dv, \qquad 0\le t\le1. \tag{6}\] The integral is well defined by Lemma 6.

These identities describe the auxiliary independent model. They assert no factorization of survival probabilities in the finite priority system. We next estimate their solution uniformly over all edge and omitted-parent types; the finite evaluation above has already constructed this solution, so no recursive fixed-point assumption is needed.

The exact equation and its linearization

Use the increasing change of variables \[s=\tfrac12\log(1+2Dt),\qquad S=\tfrac12\log(1+2D),\qquad t(s)=\frac{e^{2s}-1}{2D}.\] Thus \(0\le s\le S\), \(q(t(s))=e^{-s}\), and \(S\le\log n\) for all sufficiently large \(n\). Since \(0\le I_{e,T}(t)\le t\), the product identities in Proposition 7 give \(q_e(t)>0\) for \(t<1\). On any interval on which all product factors remain positive, define the vector \(z(s)\in\mathbb R^{\mathcal E}\) by \[z_e(s)=\log\frac{q_e(t(s))}{q(t(s))}.\] In particular, \(z(0)=0\). Positivity at \(t=1\) will follow from the estimates below.

Let \(A\) be the real symmetric matrix indexed by \(\mathcal E\), with \(A_{ef}=1\) if \(e\ne f\) belong to a common triangle of \(G\), and \(A_{ef}=0\) otherwise. Each row indexed by \(e\) has sum \(2d_e\). Linearity of the triangle hypergraph ensures that each pair of distinct edges contributes at most once to \(A\).

Differentiating the products is legitimate by Proposition 7. For \(T=\{e,f,g\}\) we have \[I'_{e,T}(t)=q_{f,T}(t)q_{g,T}(t),\qquad q_{f,T}(t)=\frac{q_f(t)}{1-I_{f,T}(t)},\qquad \frac{dt}{ds}=\frac1{Dq(t)^2}.\] Here and below a prime on \(I\) denotes differentiation in \(t\), and a prime on \(z\) denotes differentiation in \(s\). Taking the logarithmic derivative of \(q_e\) consequently gives the exact identity \[ z'_e(s)=1-\frac1D \sum_{\substack{T\in\mathcal T\\T=\{e,f,g\}}} \frac{\exp(z_f(s)+z_g(s))} {(1-I_{e,T}(t))(1-I_{f,T}(t))(1-I_{g,T}(t))}, \qquad t=t(s). \tag{10}\] The factor indexed by \(e\) comes from differentiating its product; the other two factors come from the two omitted-parent probabilities.

For vectors, \(\lVert\cdot\rVert_\infty\) denotes the maximum norm and \(\lVert\cdot\rVert_2\) the Euclidean norm. For matrices we use the corresponding induced operator norms. Fix \[ 0<a<\min\{c,2\epsilon\},\qquad \delta_n=n^{-a}. \tag{11}\] Suppose, provisionally, that on an interval starting at zero, \[ \lVert z(s)\rVert_\infty\le\delta_n, \qquad I_{e,T}(t(s))\le\tfrac12 \quad(e\in T\in\mathcal T). \tag{12}\] The omitted-parent identity then implies \(q_{e,T}(t)\le2e^{\delta_n}q(t)\). Integrating yields, on the same interval, \[ I_{e,T}(t) \le4e^{2\delta_n}\int_0^t\frac{dv}{1+2Dv} =\frac{2e^{2\delta_n}}D\log(1+2Dt) =O\!\left(\frac{\log n}{D}\right). \tag{13}\] In particular, all three denominator factors in (10) are \(1+O(\log n/D)\). Expanding the exponential and reciprocal factors gives, uniformly for each summand, \[\frac{e^{z_f+z_g}} {(1-I_{e,T})(1-I_{f,T})(1-I_{g,T})} =1+z_f+z_g+ O\!\left(\delta_n^2+\frac{\log n}{D}\right).\] The sum of the linear terms is exactly \((Az)_e\). Since \(d_e/D=1+O(n^{-c})\), we obtain the conditional estimate \[ \left\lVert z'(s)+(A/D)z(s)\right\rVert_\infty \le C\left(n^{-2a}+n^{-c}+\frac{\log n}{D}\right). \tag{14}\] The constant \(C\) is independent of the graph and the provisional interval. The general bound \(\lVert e^{-sA/D}\rVert_\infty\le e^{s\lVert A/D\rVert_\infty}\) gives a loss of order \(D\) at \(s=S\), too large to guarantee control of the prefix error \(n^{-c}\). We will instead prove a polylogarithmic bound, sufficient to turn (14) into a strict improvement of (12).

From link spectra to a uniform semigroup bound

The passage from even closed-walk counts to spectral control follows the sparse quasirandom trace method; compare Chung and Graham (Chung and Graham 2002, Theorem 1 and Facts 7–8). We prove the quantitative form required by the link hypotheses and then transfer it to the maximum norm on the full edge space.

Closing the probability estimate

The semigroup bound now controls the cumulative error in (14). This is the only use of the spectral calculation in the probability argument.

One consequence records the precision needed for the later exploration of selected paths. Set \(J_n=\max_{e\in T\in\mathcal T,\,0\le t\le1}I_{e,T}(t)\). At a paired call with focus \(\{f,g\}\subset T\) and omitted parent \(T\), the product of all no-success factors is \(q_{f,T}(t)q_{g,T}(t)\). Deleting at most two factors from this product increases it by at most \((1-J_n)^{-2}\). Hence, uniformly in the call and threshold, for large \(n\) the resulting product is at most \[ \frac{q_{f,T}(t)q_{g,T}(t)}{(1-J_n)^2} \le 2q(t)^2=\frac2{1+2Dt}. \tag{22}\] This remains a statement about the independent unfolding. We next compare its queries with the finite priority process.

The graph of visited calls

We now work entirely in the independent experiment. Its visited calls form a finite rooted forest almost surely. Construct a graph \(\Gamma\) and a label map \(\lambda:V(\Gamma)\to V(G)\) from this forest. Each root contributes two new formal vertices \(x,y\), the edge \(xy\), and labels given by its sampled ordered endpoints. Distinct roots have disjoint formal vertices even if their labels coincide. If a visited child is attached through a formal focus edge \(xy\) of its parent, introduce a new formal vertex \(z\), label it by the third vertex of the child’s triangle type, and add the edges \(xz,yz\). These two new edges are the child’s focus. If \(xy\) is ordered, order them as \((x,z),(y,z)\), so subsequent choices of focus edge have fixed names.

The birth call of a formal vertex or edge is the call that introduced it. Order the construction with all roots first and every parent before its children. The following properties hold in any such order:

1. Every formal edge has adjacent labels in \(G\), and the three vertices in any one gluing have distinct labels.

2. Every formal edge is focused at exactly one call, its birth call. An attachment edge is not in the child’s focus.

3. No step adds an edge between two vertices already present.

4. The only triangles of \(\Gamma\) are the triangles introduced by the gluings.

For the last property, consider the latest vertex of a formal triangle. The initial disjoint root edges contain no triangle. A non-root vertex has exactly two older neighbours, namely the endpoints of its attachment edge, so the triangle must be its gluing triangle.

Figure 1 shows the distinction between a visited call and an exposed candidate. The formal graph records the former, but an extra adjacency between its labels can account for repetitions among the latter.

For a formal vertex \(a\), its ancestral call path is the path from a root to the birth call of \(a\), including both ends. Given two formal vertices \(a,b\), let \(\Gamma_{a,b}\) be the graph constructed from the union of their ancestral call paths, using the root edges and gluings on those paths. All its calls are visited. We call \((a,b)\) an extra-edge witness if \(a,b\) are distinct and nonadjacent in \(\Gamma\), their labels are adjacent in \(G\), and \(\lambda\) is injective on \(V(\Gamma_{a,b})\).

The root experiment still samples with replacement; we have only charged its overlaps to the error bound. The remaining task is to bound the probability of a visited, injectively labelled pair of call paths whose two marked vertices have an extra edge. This uses both the template estimates for \(G\) and the independent-test probabilities.

Patterns and their embeddings

The paths in this section are paths in the call forest, not paths in the formal graph \(\Gamma\). Consider the union of the ancestral paths to the birth calls of two marked formal vertices \(a,b\). When the paths belong to the same rooted tree, let \(h\) be their common trunk length and let \(\ell_1,\ell_2\) be the two lengths after the trunk. Length counts non-root calls. When the paths belong to distinct trees, set \(h=0\) and let \(\ell_1,\ell_2\) be their individual lengths. In both cases put \[\ell=h+\ell_1+\ell_2, \qquad r=\text{the number of roots used}\in\{1,2\}.\] Zero lengths are allowed. A mark born at a root specifies one of its two formal endpoints.

A pattern records these rooted paths, their marks, and the choice of focus edge at each child step. The named focus edges from Section 5 give at most two choices at a step. The choices of roots, the order of the two marked paths, and any marked root endpoints contribute only an absolute constant. Consequently, for each triple \((h,\ell_1,\ell_2)\) there are at most \[ C\,2^\ell \tag{24}\] patterns, for an absolute constant \(C\). At a fork the two children each choose a focus edge; their third vertices will be determined by an embedding. Thus there is no further length-dependent multiplicity. Patterns that cannot occur under the query rule may be discarded.

The formal graph \(J\) of a pattern starts with \(r\) disjoint root edges and adds two edges and one vertex at each non-root call. In particular, \[v(J)=2r+\ell,\qquad e(J)=r+2\ell.\] We consider only patterns whose marks \(a,b\) are distinct and nonadjacent in \(J\), and write \(J^+=J+ab\). An embedding below is an injective map of the formal vertices into \(V(G)\) that maps every edge of \(J^+\) to an edge of \(G\) and respects the named endpoints of each root.

The embedding bound supplies a factor \(D^{-B}\) even when the paths are arbitrarily long. It remains to sum over their lengths. Counting paths alone would lose this factor, since a call can have order \(D\) children. The next estimate uses the failures required to reach a prescribed child, together with the decreasing order of priorities.

The probability of visiting prescribed paths

Fix a pattern and an embedding of \(J^+\) before exposing any priorities. The probability that its \(r\) used roots have the prescribed ordered labels is \((2m)^{-r}\). Conditional on this root event, each step of the pattern specifies one candidate occurrence in a fixed potential call tree: its focus edge and third vertex determine its triangle. If these specifications cannot define distinct required children under the query rule, their visitation probability is zero and they can be discarded. Otherwise, write \(u_y\) for the priority of the selected child occurrence corresponding to each of the \(\ell\) non-root calls \(y\). These are distinct independent uniform coordinates of the unfolding.

Set \[ b(t)=q(t)^2=\frac{1}{1+2Dt},\qquad C_D=1+2D,\qquad \mu=\int_0^1b(t)\,dt=\frac{\log(1+2D)}{2D}. \tag{29}\]

Summing all witnesses

We have thus compared the finite continuation with independent root queries at an error smaller than their two-root success probability. The first and second terminal moments can now be read directly from these root-query probabilities.