Proof. Delete the node corresponding to \(B\) from \(T\). The occurrence subtree of each vertex outside \(B\) lies in one resulting component. Two adjacent graph vertices outside \(B\) lie in the same component, since some bag contains them both. A graph path avoiding \(B\) therefore stays in one component. This proves the first assertion; if \(B\) is an endpoint bag, that assertion is immediate.

For a tree edge with endpoint bags \(A,C\), a graph vertex occurs on both sides precisely when it belongs to \(A\cap C\), by connectedness of its occurrence subtree. An edge joining the two sides away from this intersection would have no bag containing both endpoints. This proves the second assertion. If \(A\cap C\) were empty, the nonempty bags \(A\) and \(C\) would lie in different nonempty components of \(G\).

For the third assertion, a shortest path from \(A_i\) to \(x\) meets \(A_{i+1}\) by the first assertion, so \(d(x,A_{i+1})\leq d(x,A_i)\). Finally, choose a shortest path from \(A\) to \(x\) and let \(v\) be any of its vertices in \(B\). Its initial segment has length \(d(v,A)\): a shorter path from \(A\) to \(v\) would shorten the chosen path to \(x\). The remaining segment has length \(d(x,v)\), giving (3). ◻

Proof. Root \(T\) and sample the root assignment with law \(\mu_t/m\). At a child bag \(B_s\) with parent bag \(B_t\), keep the labels on \(S=B_t\cap B_s\) and sample the remaining labels according to the conditional law of \(\mu_s\) given that assignment on \(S\). Previously assigned vertices in \(B_s\) are exactly those in \(S\): any earlier occurrence of such a vertex is connected to \(s\) through \(t\). Consequently the sampling defines an assignment on all of \(V\). An induction over the rooted tree, using consistency on \(S\), proves that each bag has marginal \(\mu_s/m\). Multiply the resulting probability measure by \(m\) to obtain \(\rho_\mu\).

For every full assignment \(\omega\) for which all separator factors are positive, its mass is \[ \rho_\mu(\omega) =\frac{\displaystyle\prod_{t\in V(T)}\mu_t(\omega|_{B_t})} {\displaystyle\prod_{ts\in E(T)} \mu_{B_t\cap B_s}(\omega|_{B_t\cap B_s})}. \tag{5}\] If a separator assignment has zero mass, the full assignment has zero mass as well, by the already established marginals. Formula (5) is independent of the root and invariant under complement when the bag measures are symmetric.

Rooting at the first bag of a path and integrating out branches shows that each next intersection is sampled using only the previous intersection assignment. This also permits an endpoint vertex as the first or last layer, by conditioning the endpoint bag law on that vertex or restricting it to that vertex, respectively. Finally, on the finite measure space \((\Omega_V,\rho_\mu)\), the functions \(F_v(\omega)=\omega(v)\) satisfy \(\|F_u-F_v\|_1=D_\mu(u,v)\). ◻

Proof. We will attach a prefix sampled from the glued law to a suffix sampled from \(\nu\). It is enough to dominate each consecutive joint marginal; no domination of \(\nu\) by the full glued measure is asserted. The full assignment on \(P\) is inserted as a layer so that the attachment uses exactly the information in the uncertainty functional.

Write \(\rho=\rho_\mu\) and let \(m\) be its mass. If \(z\in P\), each assignment on \(P\) determines the label at \(z\), so \(E_\nu(z\mid P)=0\) and the assertion is immediate. Otherwise, use the vertex sets \[\{y\},\ B_0\cap B_1,\ldots,B_{r-1}\cap B_r,\ \{z\},\] as indices for layers: the states in the layer indexed by a set \(R\) are the assignments in \(\Omega_R\). Insert one additional layer consisting of the full assignment on \(P\). This layer goes between the incoming and outgoing intersections at \(P\); when \(P=B_0\), it goes immediately after the \(y\) layer. The vertex sets indexing consecutive layers are contained in a single bag.

Under \(\rho/m\) these layers form a Markov chain. Indeed, the additional layer samples the rest of \(P\) conditional on its incoming assignment, and its outgoing intersection is then a restriction of the full \(P\) assignment. Summing over the additional coordinates gives exactly the original intersection transition. Every layer has at most \(2^k\) states. All indexing vertex sets are nonempty by Lemma 2, so complementation acts on their assignment spaces without fixed points. Symmetry of the bag laws preserves the chain law. The mass-\(m\) capacity on each consecutive pair is the corresponding projection of a bag measure.

We construct a measure \(\lambda\) on paths in these layers. Take the suffix measure, beginning with the full \(P\) layer, to be the projection of \(\nu\). For its assignment \(b\) on \(P\), attach an independent prefix with the conditional probability law under \(\rho/m\) given that same full assignment. Put \[m_b=\rho(\omega|_P=b),\qquad n_b=\nu(\omega|_P=b).\] The assumed domination at \(P\) gives \(0\leq n_b\leq m_b\). For any prefix event \(F\), \[\lambda(F) =\sum_{b:m_b>0}n_b\Pr_\rho[F\mid\omega|_P=b] \leq\sum_{b:m_b>0}m_b\Pr_\rho[F\mid\omega|_P=b] =\rho(F).\] Here and below conditional probabilities under \(\rho\) mean those under \(\rho/m\). Assignments with \(m_b=0\) have \(n_b=0\) and require no conditional law. Thus every prefix edge respects its original capacity. On the suffix, the law is the corresponding projection of \(\nu\); because the vertex sets indexing consecutive layers lie within a single suffix bag, its edges also respect the capacities. The attachment is consistent on all overlapping vertex labels: a vertex occurring on both sides of \(P\) must occur in \(P\), by the connectedness of its occurrence subtree.

For \(i\in\{0,1\}\) and \(b\in\Omega_P\), set \[a_i(b)=\nu(\omega|_P=b,\omega(z)=i), \qquad q_b=\Pr_\rho[\omega(y)=0\mid\omega|_P=b].\] For \(m_b=0\), set \(q_b=0\); both \(a_i(b)\) then vanish. The construction gives \[\begin{align*} \lambda(\omega(y)\ne\omega(z)) &=\sum_b\bigl(q_ba_1(b)+(1-q_b)a_0(b)\bigr)\\ &\geq\sum_b\min\{a_0(b),a_1(b)\} =E_\nu(z\mid P). \end{align*}\] Restrict \(\lambda\) first to paths with endpoint labels \((0,1)\), and then to paths with endpoint labels \((1,0)\). Each restriction defines a feasible flow: its arc masses satisfy conservation at intermediate states and are dominated by the original arc capacities. Apply Theorem 4 to the first flow and to the complemented second flow, normalizing all masses by \(m\). After multiplying back by \(m\) and adding, we obtain \[\lambda(\omega(y)\ne\omega(z)) \leq C(2^k)\rho(\omega(y)\ne\omega(z)) =C(2^k)D_\mu(y,z).\] Together with the preceding lower bound and (7), this proves the Proposition. ◻

Proof. No value \(F(s)\) with \(s\in P\) lies in the open interval \((F(z)-t,F(z)+t)\). The assignment on \(P\) is therefore constant throughout this threshold interval. Its two halves each have length \(t\), and the label at \(z\) is opposite on the two halves. For that fixed assignment on \(P\), the unsymmetrized sweep gives mass at least \(t\) to each label at \(z\). Thus \(E_{\sigma_F^M}(z\mid P)\geq t\), and (9) proves the result. ◻

Proof. The two height functions agree on \(A\). For each threshold strictly between \(f(z)-g(z)\) and \(f(z)+g(z)\), their assignments on \(A\) consequently agree and their labels at \(z\) are opposite. For each \(b\in\Omega_A\), let \(I_b\) be the set of thresholds in this interval giving assignment \(b\) on \(A\). In the sum of the two unsymmetrized sweeps, each of the two possible labels at \(z\), together with assignment \(b\) on \(A\), has mass at least the Lebesgue measure of \(I_b\). Summing over \(b\) gives uncertainty at least the length of the whole interval, namely \(2|g(z)|\). The sum of the symmetric sweeps is the symmetrization of their sum, so (9) proves (12). Formula (11) proves the equality in (13); the final inequality follows from \(|a+b|+|a-b|\geq2|b|\). ◻

Proof. For a bag \(B\), let \(\mathcal A_B\) be the set of scales \(s=2^j\) for which some distinct \(u,v\in B\) satisfy \[s/2\leq d(u,v)\leq4s.\] Call these scales active at \(B\). A fixed positive distance can belong to \([s/2,4s]\) for at most four powers of two \(s\): equivalently, \(s\in[d(u,v)/4,2d(u,v)]\), an interval with endpoint ratio eight. Consequently \(|\mathcal A_B|\leq R\).

The activity interval \([s/2,4s]\) is wider than the interval \([s,2s]\) used to choose a scale for a tested pair. This slack has a geometric purpose: if a pair at distance between \(s\) and \(2s\) occurs later in a consecutive run of bags where \(s\) is active, at least one endpoint must lie away from the inactive launch bag. A padded bump can then have positive amplitude at that endpoint while vanishing at the other. Retaining its pair carries that separation to the bag containing the tested vertices.

We use the particle construction of Proposition 10, reserving one pair of particles for each active scale. Initially all \(N\) particles vanish. At the root, launch a pair for each active scale using an empty interface, and then measure the root trace. For a child of a bag \(A\), make a separate copy of the parent’s list. First drop the reservations of all scales that are inactive at this child; retain those active at both bags. Then launch the child’s newly active scales, with every update performed at \(A\), before moving to the child. This order keeps at most \(R\) pairs reserved at any time. It also leaves more than \(k!\) particles free whenever an update is required, by the choice of \(N\). Different children use their own copies. A retained pair is unchanged along every consecutive run of bags where its scale is active.

Here is the perturbation used for a new scale \(s\). Put \(r=s/16\), and sample a partition \(\mathcal P\) at scale \(r\) from Theorem 11. For \(C\in\mathcal P\) give an independent uniform coefficient \(U_C\in[0,1]\) to the bump \[\psi_C(z)= \begin{cases} \min\{d(z,A),d(z,V\setminus C),r\},&z\in C,\\ 0,&z\notin C. \end{cases} \qquad g(z)=\sum_{C\in\mathcal P}U_C\psi_C(z).\] For a root launch with empty interface, omit the term \(d(z,A)\). All these choices are fresh. Lemma 12 shows that \(g\) is \(1\)-Lipschitz. It vanishes on the launch bag when that bag is nonempty. Since the scale is active at some bag, \(s\leq2\Delta\), and hence \(0\leq g\leq r\leq\Delta/8\).

At each launch use two free particles with a common weak sorting order on the interface, replace them by \(f+g\) and \(f-g\) as in Lemma 8, and reserve them. An empty interface imposes no sorting constraint. All updates have \(\operatorname{Lip}(g)\leq3\) and \(|g|\leq3\Delta\). Proposition 10 therefore gives consistent bag measures and a Markov-glued cut metric with upper bound \(3N(N-1)d\). Average over all the preparatory randomness to obtain \(D_{\mathrm{bag}}\); it is still an \(L_1\) pseudometric with that upper bound. Dropping a reservation does not delete a particle, and all updates at a parent preserve its full trace, so this procedure also covers branching and the ending of active runs.

It remains to prove the lower bound. Fix distinct \(u,v\) in a common bag \(B\), and choose a dyadic scale \(s\) with \(s\leq d(u,v)<2s\). This scale is active at \(B\). Trace its reserved pair backwards to the start of its active run. Either this was a root launch with empty interface, or it was launched at a preceding bag \(A\) where \(s\) was inactive.

In the latter case at least one of \(u,v\), say \(w\), has \(d(w,A)\geq s/8\). Indeed, if both distances were less than \(s/8\), nearest points \(a,b\in A\) would satisfy \[\tfrac34s<d(a,b)<\tfrac94s,\] by the triangle inequality and \(s\leq d(u,v)<2s\). In particular \(a\ne b\) and \(s\) would be active at \(A\), a contradiction. For an empty-interface launch take either endpoint as \(w\).

Let \(w'\) be the other endpoint. In the partition sampled at this launch, \(w,w'\) lie in different parts, since \(d(w,w')\geq s>r\). With probability at least \(\pi\), the part \(C\) containing \(w\) contains \(B_d(w,\alpha r)\). On this event its bump amplitude \(a=\psi_C(w)\) is at least \(\alpha r\): the distance-to-\(A\) cap, when present, is at least \(s/8=2r\), and the other caps are also at least \(\alpha r\). Conditional on the partition and every coefficient other than \(U_C\), the value \(g(w')\) is fixed and \(g(w)=aU_C\). For every real \(b\) and \(a>0\), \[\int_0^1|at-b|\,dt\geq a/4.\] Consequently \[\mathbb E\,|g(u)-g(v)|\geq\frac{\pi\alpha r}{4} =\frac{\pi\alpha s}{64}.\]

The reserved particles still supply their two sweep measures in the trace on \(B\). By Equation (13), their separation of \(u,v\) is at least \(2|g(u)-g(v)|\), irrespective of the launch average \(f\). The glued metric has the prescribed trace on \(B\), and all other cut measures are nonnegative. Therefore \[D_{\mathrm{bag}}(u,v) \geq\frac{\pi\alpha s}{32} \geq\frac{\pi\alpha}{64}\,d(u,v).\] For \(u=v\) the required inequalities are immediate. This proves the proposition. ◻

Proof. We divide the positive values of \(h\) into randomly shifted dyadic bands and put nonnegative bumps in partition parts within each band. Conditional on their locations, we give the bumps independent coefficients. Disjoint supports keep their sum Lipschitz. A vertex well inside its band and its partition part then has one coefficient whose amplitude is a fixed fraction of \(\eta h(x)\).

If \(h\) vanishes everywhere, take \(v=0\) and sample \(\xi\) as stated. Otherwise let \(h_{\min}\) and \(h_{\max}\) be the smallest positive and the largest values of \(h\). Sample \(\lambda\) uniformly on \([0,1)\), and put \[I=\{\lfloor\log_2h_{\min}\rfloor-1,\ldots, \lfloor\log_2h_{\max}\rfloor\}, \qquad m=\lfloor\log_2\eta\rfloor.\] For \(j\in I\), define the random band and the fixed scale \[W_j=\{z:2^{j+\lambda}\leq h(z)<2^{j+1+\lambda}\}, \qquad r_j=2^{j+m}.\] The bands partition \(\{h>0\}\). Independently of \(\lambda\), sample a partition \(\mathcal P_j\) at scale \(r_j\) from Theorem 11, for each \(j\in I\). Thus the partition scales are fixed powers of two, not random functions of \(\lambda\). Consequently, conditioning on the band offset leaves each sampled partition with its original padding guarantee.

For each nonempty \(E=W_j\cap C\), \(C\in\mathcal P_j\), set \[\varphi_{j,C}(z)= \begin{cases} \min\{r_j/2,d(z,V\setminus E)\},&z\in E,\\ 0,&z\notin E. \end{cases}\] Conditional on these locations, give the bumps independent uniform coefficients \(U_{j,C}\in[0,1]\), and define \[v(z)=\sum_{j,C}U_{j,C}\varphi_{j,C}(z).\] This is a finite measurable construction: there are finitely many bands and partitions of the finite set \(V\), and band memberships are measurable functions of \(\lambda\). If desired, the coefficients can be sampled in advance for every possible pair \((j,C)\) with \(C\subseteq V\).

The nonempty sets \(E\) are disjoint, and each bump is nonnegative and \(1\)-Lipschitz on all of \(V\). Lemma 12 therefore shows that \(v\) is \(1\)-Lipschitz, including at points where \(h=0\). For \(z\in W_j\), \[0\leq v(z)\leq r_j/2 \leq\eta 2^j/2\leq\eta h(z)/2.\] Sampling \(\xi\) independently gives the first assertion.

Fix \(x\) with \(D_0=h(x)>0\), and let \(j\) be its band index. The event \[\log_2D_0-(j+\lambda)\in[1/4,3/4] \tag{*}\] has probability \(1/2\). On this event, the value \(D_0\) is at distance greater than \(D_0/8\) from both numerical endpoints of its band. Since \(h\) is \(1\)-Lipschitz, the ball \(B_d(x,D_0/8)\) is contained in \(W_j\). Also \(r_j\leq\eta D_0\), so \(\alpha r_j<D_0/8\). Conditional on \(\lambda\), the probability that \(B_d(x,\alpha r_j)\) lies in its part \(C\in\mathcal P_j\) is at least \(\pi\). On this padding event together with \((*)\), \[\varphi_{j,C}(x)\geq\alpha r_j.\] Because \(2^m>\eta/2\) and \(D_0<2^{j+2}\), we have \(r_j>\eta D_0/8\). Thus the last display is at least \(c\eta D_0\) with \(c=\alpha/8\). The joint event has probability at least \(\rho=\pi/2\) and depends only on the locations. Finally, any point in the support of this bump is in the same partition part as \(x\), and hence is at distance at most \(r_j\leq\eta D_0\) from \(x\). This implies the stated support bound. Let \(E_x\) be the event that the sampled family contains a bump with the two displayed bounds in the second assertion, and select the first such bump in a fixed ordering. This event and the selected index \(i(x)\) are determined by the family. The band and padding event above implies \(E_x\), so \(\Pr(E_x)\geq\rho\). The independent coefficients are sampled after the family, which gives the stated conditional law of \(U_x=U_{i(x)}\). Finally, \(\xi\) is sampled independently of both the family and all coefficients. ◻

Proof. If \(A_i\) precedes \(A_j\), then \(A_j\) lies between \(A_i\) and \(B\) on the ancestry path. Lemma 2, applied to paths from \(p\in B\) to \(A_i\), gives \(d(p,A_j)\leq d(p,A_i)\). Thus a threshold protects at most one entry. There are at most \(2k(k-1)\) protected entries in total. At a full insertion there are \(n_0\) non-root candidates, and \(n_0>2k(k-1)\), so at least one is eligible. The size assertions follow from performing exactly one eviction at such an insertion. ◻

Proof. For each realization of the launch randomness, a reserved pair supplies a common submeasure throughout its reservation, including its endpoints. Since \(g_A\) vanishes on \(A\) and \(|g_A(z)|\geq h_A(z)/2\), Lemma 7 gives uncertainty at least \(d(z,A)\). Proposition 5 gives the first assertion after averaging. For the second assertion, use the single particle’s symmetrized sweep. The sweeping margin permits Lemma 6 to give uncertainty at least \(t\) on the stated event. Apply Proposition 5 and average again. These transport estimates hold pointwise in the prepared laws. To establish the probability of a height gap in Section 6, we will instead condition on the launch history and selected fresh variables, leaving the later bag laws unconditioned. ◻

Proof. The first assertion is the finite-union and finite-intersection property of an ultrafilter. If the second assertion failed, the sets on which the sequence is smaller than each positive constant would all belong to \(\mathcal U\), which is exactly infinitesimality. Take a finite minimum of the resulting positive lower bounds to obtain its last claim. For two time sequences, the alternatives \(s<t\), \(s=t\), and \(s>t\) partition the indices, proving the ordering assertion. If a time with noninfinitesimal \(\delta\) were at or after one with infinitesimal \(\delta\), monotonicity would bound its \(\delta\) by an infinitesimal sequence, a contradiction. ◻

Proof. The permanent root is crossing. Given any finite collection of crossing anchor sequences, take their latest effective start. It is early by Lemma 18. Every anchor in the collection has started, and each of their late terminal times follows this early time. Thus they are simultaneously present in the inclusive cache list. If \(n_0+2\) distinct crossing sequences existed, select that many; their pairwise distinctness also holds simultaneously eventually. This would contradict the bound \(n_0+1\) of Lemma 15. This bound concerns the set of equivalence classes of all crossing sequences, not just a list chosen in advance. The finite nonempty set of crossing anchors is ordered by launch time, so it has a youngest member. ◻

Proof. If \(A_*\) launches at or below \(S\), that launch is an early time on the path from \(S\) to \(X\). It also lies on the bag path from the chosen bag containing \(y\) to \(Z\). Equation (19) gives \[D(y,z)\geq b_kd(z,A_*) \geq b_k\bigl(d(x,A_*)-d(x,z)\bigr).\] The first distance in parentheses has a positive standard lower bound, contradicting (26). Hence the launch is strictly above \(S\). The separator inequality now gives \(D_0\geq d(x,S)=1\). Its reservation starts before \(S\) and has a late terminal time, proving the last assertion by Lemma 18.

Suppose \(D_0\leq H\) on a set in \(\mathcal U\). Use the ordinary noise event at \(x\) from Lemma 14, of probability at least \(\rho\). On this event, a fresh uniform coefficient has amplitude at least \(c\eta D_0\geq c\eta\) at \(x\). Its support is within distance \(4\eta D_0\leq4\eta H<1\) of \(x\), and so misses every vertex of \(S\).

Consider the frozen particle \(F=f_{A_*}+\xi_{A_*}h_*+v_{A_*}\). Conditional on the past, sampled bump family, \(\xi_{A_*}\), and all other coefficients, each inequality \(|F(x)-F(s)|<t\) for \(s\in S\) excludes at most \(2t/(c\eta)\) of the unit interval of this coefficient. Choose a positive standard \(t<1/4\) such that \(2kt/(c\eta)<1/2\). The union bound gives a simultaneous gap at least \(t\) from all of \(S\) with probability at least \(\rho/2\). The late-proxy test at \(S\) gives a contradiction. The ultrafilter alternative therefore is \(D_0>H\). ◻

Proof. Otherwise, by the ultrafilter alternative, eventually every vertex \(s\in B\) is either near, with \(d(p,s)<\delta/4\), or far, with \(d(p,s)>10D_0\). A shortest path from \(A_*\) to \(x\) meets \(B\) at a vertex \(v_0\), by Lemmas 2 and 20. As \(v_0\) lies on such a shortest path, \[h_*(v_0)+d(v_0,x)=D_0.\] Moreover, \[d(p,v_0)\leq\delta+d(x,v_0)\leq1+D_0\leq2D_0<10D_0.\] Thus \(v_0\) must be near. For every near vertex \(s\), we have \(d(v_0,s)<\delta/2\), whence \[ h_*(x)-h_*(s) \geq d(x,v_0)-d(v_0,s)>\frac{\delta}{2}. \tag{28}\] For every far vertex \(s\), on the other hand, \[ d(x,s)\geq d(p,s)-\delta>10D_0-\delta\geq9D_0>4\eta D_0. \tag{29}\]

Again use the favorable bump event at \(x\), of probability at least \(\rho\), and the particle \(F=f_{A_*}+\xi_{A_*}h_*+v_{A_*}\). Condition on the past and the sampled bump family. For a far vertex \(s\), the distinguished coefficient at \(x\) does not affect \(s\), by (29). Fixing \(\xi_{A_*}\) and all other noise coefficients gives \[\Pr\bigl(|F(x)-F(s)|<t\bigr) \leq\frac{2t}{c\eta D_0}.\] For a near vertex \(s\), instead fix all noise coefficients and use the independent uniform variable \(\xi_{A_*}\in[1,2]\). Equation (28) gives \[\Pr\bigl(|F(x)-F(s)|<t\bigr)\leq\frac{4t}{\delta}.\] Each estimate remains true after averaging over the variables fixed only for that estimate. In particular the different bad events need not be independent. The selected anchor, bag, and vertices depend only on the metric and cache. Thus this selection has not conditioned either the distinguished bump coefficient or \(\xi_{A_*}\).

Since \(B\) is early, \(\delta\geq\varepsilon>0\) eventually for some standard \(\varepsilon\). Since \(D_0>H\), we can choose a positive standard \(t<1/4\) with \[k\left(\frac{4t}{\varepsilon} +\frac{2t}{c\eta H}\right)<\frac12.\] The union bound gives a height gap at least \(t\) from all of \(B\) with probability at least \(\rho/2\). The reservation of \(A_*\) contains \(B\) and \(Z\), and \(B\) lies on the bag path from \(y\) to \(Z\). The late-proxy test is therefore a contradiction. This proves (27). Notice that the argument also permits \(D_0\) to be unbounded. ◻

Proof. Let \(p\in B\) be nearest to \(x\), and put \(\delta=d(x,B)\). If \(A'\) is the current proposal, \(d(p,A')=0\). Otherwise its reservation lasts from its launch through \(B\), and its launch lies on the bag path from \(y\) to \(B\). Equation (19) yields \[b_kd(p,A')\leq D(y,p)\leq D(y,x)+U\delta.\] Because \(\delta\) is early, \(D(y,x)/\delta\) is infinitesimal. The choice of \(K\) in (21) consequently gives, eventually, \[ d(p,A')\leq K\delta. \tag{30}\] This inequality also holds for a proposal. Monotonicity of distances along the path gives \(d(x,A')\leq d(x,S)=1\), so in all cases \[ d(p,A')\leq\delta+1\leq2, \qquad d(p,A_*)\geq D_0-\delta\geq D_0-1. \tag{31}\]

Choose \(q\) from Lemma 21 and write \(L=d(p,q)\). There are two alternatives. If \(L\leq300\), then \[JL\geq\frac{J\delta}{4}>K\delta\geq d(p,A'), \qquad JL\leq300J<H-1<D_0-1\leq d(p,A_*).\] If \(L>300\), then \[\frac{L}{100}>3>2\geq d(p,A'), \qquad \frac{L}{100}\leq\frac{D_0}{10} <D_0-1\leq d(p,A_*).\] In either case one of the thresholds in (16) lies strictly below \(d(p,A_*)\) and at or above \(d(p,A')\). Since the distance list is nonincreasing and \(A'\) immediately follows \(A_*\), it is precisely the entry protected by this drop. ◻

Proof. Inspect the inclusive cache list at the insertion test at \(S\). By Lemma 20, \(A_*\) was launched strictly above \(S\), so this is indeed a non-root insertion. Consider the younger entries whose launches were strictly above \(S\). Their number is bounded by \(n_0+1\); by a finite ultrafilter alternative, enumerate them as a fixed finite list of anchor sequences. These are all the anchors younger than \(A_*\) and launched above \(S\) that can be present at any later test: an evicted reservation never returns, and every later launch is at or below \(S\).

Each has effective start \(S\), which is early. If any had a late terminal bag, it would be a crossing anchor younger than \(A_*\). By the choice of \(A_*\), every one must instead have an early terminal bag. Such a bag is its actual eviction bag, since the endpoint \(X\) is late.

If this finite list is nonempty, take the latest of these eviction times, say \(B_0\). It is early. At this test an old younger anchor is actually evicted, so the new proposal is retained: exactly one entry is evicted at an insertion. The anchor \(A_*\) remains present, because its terminal time is late. Immediately after this eviction no younger anchor launched above \(S\) remains, and the retained proposal ensures that at least one younger entry exists. Therefore \(A_*\) has an immediate successor \(A'\) whose launch is at or after \(S\).

If the finite list is empty, the proposal at \(S\) is itself the immediate successor of \(A_*\). It is retained automatically when there is space; at a full insertion Lemma 22 prohibits its eviction. Thus in this case too there is an immediate successor \(A'\) launched at or after \(S\), present just after an early test \(B_0=S\).

Fix this successor \(A'\). Its launch is no later than the early time \(B_0\), so its effective start is early. If its terminal bag is late, it is the required younger crossing anchor. Otherwise its terminal bag is an early eviction time \(B_1\). The anchor \(A_*\) is still present at \(B_1\). While both anchors remain, \(A'\) remains the immediate successor: there was no entry between them at \(B_0\), and all subsequent insertions are younger than \(A'\). Hence Lemma 22 prohibits eviction of \(A'\) at \(B_1\), a contradiction.

This argument selected only a bounded list of anchors, its last eviction, and one successor’s terminal time. It does not use induction over an unbounded or limiting order of early times. ◻

Proof of Proposition 17. If no such constant existed, choosing ratios smaller than \(1/i\) would give (23). The normalization above and Lemmas 19–23 would then produce a crossing anchor younger than the youngest crossing anchor. This contradiction rules out a sequence of ratios tending to zero. Their infimum over all nontrivial admissible examples and all distinct pairs is therefore positive. Choose \(\lambda_k\) no larger than that infimum. Equal pairs and the one-vertex graph satisfy (22) automatically. ◻