Proof. First assign the n labeled vertices to their local-profile classes, giving n!/\prod_\tau n_\tau! choices. At a vertex of profile (i,\mathbf c), assign the d labeled half-edges their neighbor labels in \binom d{\mathbf c} ways. There are then H_{ij} half-edges of ordered type (i,j). For i<j, pairing the (i,j) half-edges bijectively with the (j,i) half-edges gives H_{ij}! choices; the H_{ii} diagonal half-edges admit (H_{ii}-1)!! pairings. Division by the total number (dn-1)!! of pairings proves the displayed count.

Every resulting pairing has the prescribed exact distance labels. Indeed, the allowed edge types make the label function 1-Lipschitz, while every positive label has a neighbor one level lower. Following a descending edge reaches label zero in exactly the displayed number of steps, and following any path from label zero cannot increase the label by more than one per edge. Thus the label equals graph distance to its zero set.

Use, uniformly for integers r\ge0,

\log(r!)=r\log r-r+O(\log(r+1))

and, for even r,

\log((r-1)!!)=\frac r2\log r-\frac r2+O(\log(r+1)).

There are O_d(h+1) profile classes and nonzero tridiagonal edge types. Substitution into the displayed exact count cancels every \log n, \log d, and linear term, leaving exactly n\Phi_{d,h}(\xi) with error O_d(h\log(n+1)). This proves the displayed bound. □

Proof. First let \xi be a rational feasible profile. Passing to arbitrarily large multiples of a common denominator, and multiplying once more if necessary to make every diagonal half-edge count even, realizes \xi as an integer type. Since N_{\mathbf n} counts only subsets of size \alpha n,

\mathbb E N_{\mathbf n}\le\binom n{\alpha n}.

The lower inequality in Theorem 11, followed by n\to\infty, gives

\Phi_{d,h}(\xi)\le H(\alpha).

The feasible set is a rational polytope, so rational feasible profiles are dense. The functional \Phi_{d,h} is continuous on it under the convention 0\log0=0. Hence the same inequality holds for every feasible profile. Taking the maximum at fixed selected density proves the corollary. □

Proof. First expose the central label. Its entropy is H(p_0,\ldots,p_h). Conditional on the central label i, choosing a local count vector and then assigning the d labeled half-edges contributes exactly the entropy of the induced law on words of length d over the allowed neighboring labels.

For i=0, only labels 0 and 1 are allowed and their coordinate marginals are \ell_0/p_0 and x_1/p_0. Subadditivity of entropy is sharp only for independent coordinates, giving the first term above.

Fix i\ge1. Mark the coordinates whose neighbor label is i-1. Their random subset is nonempty and has common coordinate marginal

a_i=\frac{q_{i,i-1}}{p_i}=\frac{x_i}{p_i}.

By definition, its entropy is at most s_d(a_i), with equality for the exponential tilt \Pr(A)\propto\lambda^{|A|}, \varnothing\ne A\subseteq[d], where \lambda satisfies the marginal characterization above; this also proves the dual formula for s_d. Given the lower-neighbor set, the remaining d-|A| coordinates must split between labels i and i+1. Conditional entropy is maximized by independent splitting with probabilities \ell_i/y_i and x_{i+1}/y_i. Its expectation is

d(1-a_i)H\!\left(\frac{\ell_i}{y_i},\frac{x_{i+1}}{y_i}\right).

The chain rule for entropy proves the displayed reduction; strict entropy concavity gives uniqueness in the positive interior. □

Proof. Insert Lemma 14 into the full profile functional \Phi_{d,h}. The edge term is

\frac d2\left(\sum_{i=0}^h\ell_i\log\ell_i+2\sum_{i=1}^hx_i\log x_i\right).

Expanding the two categorical entropies in Lemma 14, the x_i\log x_i terms cancel against the off-diagonal edge terms. The remaining p_i, y_i, and \ell_i terms collect to \mathcal F_{d,h}, including the root contribution (d-1)p_0\log p_0. Since every full feasible profile induces a feasible q and Lemma 14 constructs a maximizing profile for every feasible q, the variational values coincide. □

Proof. The envelope theorem applied to the dual formula for s_d gives

s_d'(a)=-d\log\lambda(a).

Expanding the marginal characterization at \lambda=0 gives

\lambda(a)=\frac{2d}{d-1}\left(a-\frac1d\right)+O_d\!\left(\left(a-\frac1d\right)^2\right).

At the other endpoint, \lambda(a)=(1-a)^{-1}(1+O_d(1-a)). Integrating s_d' from the known endpoint values s_d(1/d)=\log d and s_d(1)=0 gives the result. □

Proof. For each k\ge1, a strictly interior feasible profile exists. Choose 1/d<\chi<1/2, 0<r<\chi^{-1}-1, put p_i proportional to r^i, and set x_i=\chi p_i. Then

\ell_0=p_0-x_1>0,\qquad \ell_i=p_i-x_i-x_{i+1}>0\ (1\le i<k),\qquad \ell_k=p_k-x_k>0.

Mix a proposed boundary maximizer with such an interior profile. If a_i=1/d, Lemma 16 contributes a strictly positive multiple of t\log(1/t). If \ell_i=0, the term -\tfrac d2\ell_i\log\ell_i contributes a strictly positive multiple of t\log(1/t). All terms that remain away from their endpoints change by only O(t).

The only apparent negative singularity occurs if a_k=1, equivalently y_k=\ell_k=0. In that case, with y_k(t)=\beta t+O(t^2) for some \beta>0,

p_k(t)s_d\!\left(1-\frac{y_k(t)}{p_k(t)}\right)+dy_k(t)\log y_k(t)=O(t)

by Lemma 16; the two logarithmic singularities cancel. The remaining diagonal-edge term contributes

-\frac d2y_k(t)\log y_k(t)=\frac d2\beta t\log\frac1t+O(t),

which is strictly positive. If several faces are active simultaneously, all leading t\log(1/t) coefficients are nonnegative and at least one is positive. Hence every proper relative boundary point admits an improving inward direction. □

Proof. By Lemma 17, a maximizer is strictly interior on its effective prefix. Choose a_*\in(\max\{1/d,1-2/d\},1). For small \tau>0, introduce a new level of mass p_{k+1}=\tau with

x_{k+1}=a_*\tau,\qquad y_{k+1}=\ell_{k+1}=(1-a_*)\tau.

Keep p_k fixed by reducing \ell_k by a_*\tau, and preserve total mass by reducing \ell_0 by \tau. All old variables remain feasible for sufficiently small \tau. When k=0, take instead

p_0=1-\tau,\qquad x_1=a_*\tau,\qquad \ell_0=1-(1+a_*)\tau.

The new level contributes

\left[1-\frac d2(1-a_*)\right]\tau\log\frac1\tau+O(\tau).

The coefficient is positive by the choice of a_*. All changes to previously positive coordinates are O(\tau). Thus the extension strictly increases the grand functional. □

Proof. Combine Lemma 17 and Lemma 18. □

Proof. For i\ge2, the derivative of \mathcal F with respect to x_i is the sum of the p_{i-1} and p_i contributions. Subtract the two diagonal equations above, use the dual-formula identities for s_d', and cancel the common constants. The result is

\frac d2\log\ell_{i-1}-d\log\left(\lambda_i\frac{y_i}{\sqrt{\ell_i}}\right)=0.

Thus \lambda_iy_i=\sqrt{\ell_{i-1}\ell_i}, which is the displayed identity. The root contribution at i=1 has the same algebra, with the activity term cancelling through the root diagonal equation. □

Proof. Put T_i=B_i+A_{i+1}, S_i=B_{i-1}+T_i. By Lemma 20, \lambda_i=B_{i-1}/T_i. Exponentiating the diagonal KKT equation and using the entropy dual-formula identities shows that one common constant \kappa>0 satisfies

\kappa=\frac{((1+\lambda_i)^d-1)y_i^d}{p_iB_i^d}=\frac{S_i^d-T_i^d}{p_i}

for every i\ge1. Hence p_i=(S_i^d-T_i^d)/\kappa. The descent marginal formula gives x_i=a_ip_i=B_{i-1}S_i^b/\kappa. Since x_i=B_{i-1}A_i, this is the stationary equation for A_i. Subtracting x_i from p_i gives y_i=T_i(S_i^b-T_i^b)/\kappa. Since y_i=B_iT_i, this is the stationary equation for B_i. At the root, the diagonal KKT equation gives \kappa=zp_0^b/B_0^d. Because p_0=B_0(B_0+A_1)=B_0S_0, this is the stationary equation for B_0.

Conversely, let positive messages satisfy the stationarity equations. Put \sigma=Z_e^{-1/2} and introduce normalized messages \widehat A_i=\sigma A_i, \widehat B_i=\sigma B_i, \widehat\kappa=\sigma^{b-1}\kappa. Then

\widehat\kappa\widehat A_i=\widehat S_i^b,\qquad \widehat\kappa\widehat B_i=\widehat S_i^b-(\widehat S_i-\widehat B_{i-1})^b,\qquad \widehat\kappa\widehat B_0=z\widehat S_0^b.

The reconstructed beliefs are simply \ell_i=\widehat B_i^2, x_i=\widehat B_{i-1}\widehat A_i. They have total mass one by the definition of Z_e. Writing \widehat T_i=\widehat B_i+\widehat A_{i+1}, \lambda_i=\widehat B_{i-1}/\widehat T_i, the message equations give the exact row identities

p_i=\frac{\widehat S_i^d-\widehat T_i^d}{\widehat\kappa},\qquad x_i=\frac{\widehat B_{i-1}\widehat S_i^b}{\widehat\kappa},\qquad y_i=\frac{\widehat T_i(\widehat S_i^b-\widehat T_i^b)}{\widehat\kappa}.

Consequently a_i=x_i/p_i is exactly the tilted conditioned-binomial marginal with parameter \lambda_i, and \lambda_iy_i=\widehat B_{i-1}\widehat B_i=\sqrt{\ell_{i-1}\ell_i}. Substitution into the diagonal derivative gives, for every i\ge1, g_i=\log\widehat\kappa+(d-2)/2. The root equation gives the same value for g_0. Finally, the displayed edge identity and s_d'(a_i)=-d\log\lambda_i make the difference between the x_i derivative and g_{i-1}+g_i vanish exactly. Thus, with \mu=\log\widehat\kappa+(d-2)/2, one has \partial\mathcal F^{(z)}/\partial\ell_i=\mu and \partial\mathcal F^{(z)}/\partial x_i=2\mu. Positivity makes the point strict interior, and common message scaling cancels from the beliefs. □

Proof. The forward transfer identities imply \rho/u=v'e/w=R. The next lower-neighbor fraction also gives

e=\frac{\rho(1-\rho)^{1/b}}{u^{1/b}(u+\rho)}.

Substituting \rho=Ru and solving yields u=1/(R+M), which gives the displayed formulas for \rho,v. Uniqueness follows from the algebraic solution. Since e+w/v'\ge e+w=1, we have M\ge1, and therefore 0<\rho<v\le1. □

Proof. The quantity R=v'e/w is strictly increasing in both \rho' and v'. Put N=e+w/v', M=N^b. As v' increases, N strictly decreases. Since w'(\rho')<0 and e'=-w', one has

\frac{\partial N}{\partial\rho'}=w'(\rho')\left(\frac1{v'}-1\right)\le0.

Thus M is nonincreasing in both inputs. The function \rho=R/(R+M) increases with R and decreases with M. Likewise v=(1+R)/(R+M) increases with R when M\ge1 and decreases with M. The asserted monotonicity follows, and strictness of \rho propagates under iteration. □

Proof. Direct differentiation gives

\frac{\partial}{\partial v}\log z=\frac{b+1+vm}{v(1+vm)}>0,\qquad \frac{\partial}{\partial m}\log z=\frac1m+\frac{b(1-v)}{(1+m)(1+vm)}>0.

The quantity m is strictly increasing in \rho_1, so Proposition 23 completes the proof. □

Proof. For terminal (\rho',v')=(s,s) with s\downarrow0, one reverse step has R=O(s^2) and M=\Theta(s^{-b}), so the predecessor tends to (0,0). The reverse map is continuous at every interior state and has the displayed boundary limit; induction over the fixed number h-1 of reverse steps therefore sends every earlier state to (0,0). The root equation then gives z\to0.

As s\uparrow1, one has w\to0, R\to\infty, and M\to1, so one reverse step tends to (1,1). The same finite-step induction sends every earlier state to (1,1). Hence m\to\infty, v_1\to1, and the root equation gives z\to\infty. Continuity of the reverse map and of the root equation also makes s\mapsto z_h(s) continuous. □

Proof. Every positive solution has one terminal parameter s=\rho_h\in(0,1) and is uniquely reconstructed by Proposition 22. Lemma 24 and Lemma 25 show that s\mapsto z_h(s) is a strictly increasing bijection from (0,1) to (0,\infty). □

Proof. A maximizer exists by compactness. Theorem 19 places every maximizer in the strict interior, so every maximizer satisfies the interior stationarity equations. Theorem 26 gives only one such point. □

Proof. Write \theta=\log z and \phi_{d,h}(\theta)=\max_{(x,\ell)\in\mathcal P_{d,h}}\{\mathcal F_{d,h}(x,\ell)+\theta p_0\}.

By Theorem 27, the maximizer is unique for every \theta. Danskin’s theorem ^[16] therefore gives \phi_{d,h}'(\theta)=\alpha(\theta), the density of that maximizer. The derivative of a differentiable convex function is continuous here (equivalently, one may use continuity of the unique optimizer). It is also strictly increasing. Indeed, if \theta_1<\theta_2 had the same maximizing density, the two optimality inequalities would force each optimizer to maximize at both activities. Grand-canonical uniqueness would make the profiles equal, but the root equation assigns one activity to an interior stationary profile, a contradiction. To identify the endpoint limits, let \theta_k\to-\infty and pass, by compactness, to a convergent subsequence of optimizers. Comparing with a feasible profile of density 1/B_h shows that any limit must minimize p_0 over the polytope, hence has density 1/B_h. Similarly, along \theta_k\to\infty, comparison with the all-selected profile forces every subsequential limit to have density 1. Therefore

\alpha(\theta)\to\frac1{B_h}\ (\theta\to-\infty),\qquad \alpha(\theta)\to1\ (\theta\to\infty).

Hence every interior density is attained.

Fix \alpha and choose \theta with \alpha(\theta)=\alpha. For every profile P of density \alpha, \mathcal F(P)+\theta\alpha\le \mathcal F(P_\theta)+\theta\alpha, so P_\theta is the microcanonical maximizer. Uniqueness follows from grand-canonical uniqueness. □

Proof. This is the standard differentiable Legendre correspondence produced by the unique maximizers in Theorem 27 and Theorem 28. Strict monotonicity of \alpha(\theta) gives strict concavity. □

Proof. For 1\le i\le h, put V_i=S_i^d-(S_i-B_{i-1})^d. Using the stationary equations for A_i,B_i,

V_i=\kappa\left(B_{i-1}A_i+B_i^2+B_iA_{i+1}\right).

The root contribution is zS_0^d=\kappa(B_0^2+B_0A_1). After summation, every square B_i^2 appears once and every cross term B_iA_{i+1} appears twice: once from each adjacent vertex contribution, with the root supplying the first copy of B_0A_1. This is exactly \kappa Z_e. □

Proof. Proposition 30 gives \phi=\log\kappa-c_0\log Z_e. Since c_0(D+1)=b, this is \phi=E_{\mathrm{root}}-c_0N_e. Now use \Psi=\phi-\alpha\log z and expand H(\alpha)=-\alpha\log\alpha-(1-\alpha)\log(1-\alpha). □

Proof. Put \delta=q'. Since v'=1-\delta,

R=(1-\delta)\frac{1-w}w,\qquad M=\left(1-w+\frac w{1-\delta}\right)^b=\left(1+\frac{w\delta}{1-\delta}\right)^b.

For \delta\le1/2, the binomial expansion with a uniform remainder gives M=1+bw\delta+O_d(\delta^2). Furthermore,

w(R+M)=(1-\delta)(1-w)+wM=1+O_d(\delta).

Now 1-\rho=u+q=M/(R+M), q=(M-1)/(R+M). Substitution gives the displayed expansions. □

Proof. Here w=(1-V\delta)^{1/b}, e=1-w=(V\delta/b)(1+O_d(\delta)), so R=V(e/w)=(V^2\delta/b)(1+O_d(\delta)). Also

e+\frac wV=\frac1V(w+Ve)=\frac1V(1-e(1-V)),

whence M=V^{-b}(1+O_d(V\delta)). Since R/M=O_d(V^{b+2}\delta), the reverse-map formula for u yields the displayed expansion for \log u; moreover \rho/u=R, which gives the displayed expansion for \rho/v.

For the transverse-ratio estimate, use \rho=uR and compute \widetilde a_i/\widetilde a_{i+1}=bRu^{1-D}(u')^D/\rho'. The preceding expansions give bR/\rho'=V(1+O_d(\delta)) and u^{1-D}(u')^D=V^{-1}(1+O_d(\delta)), because (b-1)D=b+1. Their product is 1+O_d(\delta). □

Proof. Let E_i=\log\bigl((1-\rho_i)/\bar u_i\bigr). Lemma 33 gives E_i=\tfrac1bE_{i+1}+O(q_{i+1}), and

\log\frac{q_i}{\bar q_i}=\log\frac{q_{i+1}}{\bar q_{i+1}}+\frac2bE_{i+1}+O(q_{i+1}).

Both errors vanish at i=h.

Write r=h-i. The logarithm of the formal transverse sequence is

f(r)=r\log b-Dt+\frac{2t}{b-1}b^{-r}.

The function f is convex, so its maximum on 0\le r\le H occurs at an endpoint. At r=0, f(0)=-t, while the definition of H gives f(H)\le-\tfrac14Dt+O_d(1). Since D/4<1, it follows that \max_{m\le i\le h}\bar q_i=O_d(e^{-Dt/4}).

A first-failure bootstrap now gives

\max_i|E_i|=O(e^{-Dt/4}),\qquad \max_i\left|\log\frac{q_i}{\bar q_i}\right|=O(h e^{-Dt/4}).

For large h these estimates prevent the first failure, proving the displayed shadow estimates and the stated formula for q_m. Furthermore, 1-e^{-t/b^H}=t b^{-H}\left(1+O(t b^{-H})\right), which gives the formula for \rho_m. Finally,

\log\frac{\rho_m}{q_m}=\log t-2H\log b+Dt+o(h)=-\frac12Dt+o(h).

Because H=3Dt/(4\log b)+O(1) and L=h\log b+O(1), the three quantitative estimates follow. □

Proof. Set \delta_i=\rho_i/v_i. Proposition 35 gives \delta_m=O(\rho_m), and Lemma 34 implies geometric backward contraction. Hence

\sum_{i=2}^m\delta_i=O(\rho_m).

Iteration of the transverse-ratio contraction gives \widetilde a=\rho_m/(b^m u_m^D)\,(1+O(\rho_m)). Since u_m=1-q_m-\rho_m, this proves the displayed formula for \widetilde a.

The stable-step estimate also gives \log v_i=b\log v_{i+1}+O(\rho_{i+1}). After iteration,

-\log v_1=b^{m-1}[-\log v_m]+O\left(\sum_{j=2}^m b^{j-2}\rho_j\right)=b^{m-1}[-\log v_m]+O(b^{m-1}\rho_m).

Since v_m=1-q_m, -\log v_m=q_m(1+O(q_m)). Backward contraction gives \delta_1=O(b^{-(m-1)}\rho_m), and therefore

0\le\log\frac{v_1}{u_1}=\log\left(1+\frac{\rho_1}{u_1}\right)=O(b^{-(m-1)}\rho_m).

This is absorbed by the preceding error. Dividing by the main term b^{m-1}q_m proves the displayed formula for x.

Likewise, the stable-side expansion for \log u and the contraction of \delta_i give \log u_i=b^{-(i-1)}\log u_1+O(\rho_m) uniformly for 1\le i<m. Summing the message ratios gives the displayed formula for \log A_m.

At the root, B_0=v_1\bigl(1-(1-\rho_1)^{1/b}\bigr)/(1-\rho_1)^{1/b}=\widetilde a\,u_1^{D+1}(1+O(\rho_m)). Since D+1=2b/(b-1), the displayed formulas for x and \log A_m give

\log\frac{B_0}{\widetilde a A_m^2}=-\frac{2b}{b-1}\frac{x}{b^{m-1}}+O(m\rho_m)=O(q_m+m\rho_m),

which proves the last assertion. □

Proof. The formula for \rho_m, the stable shadow’s formula for \widetilde a, and the quantitative overlap scales of Proposition 35 give

\widetilde a=\frac{t}{b^h}\left(1+B_h^{-c_t/4+o(1)}\right)=a_h(t)\left(1+B_h^{-c_t/4+o(1)}\right).

Since a_h(t)B_h=Dt(1+o(1))=B_h^{o(1)}, this also proves the last displayed identity.

Combining the formula for q_m with the stable shadow’s formula for x yields

\frac{x}{b^{h-1}}=\exp\left\{-Dt+\frac{2t}{b-1}b^{-H}\right\}\left(1+B_h^{-c_t/4+o(1)}\right).

On the other hand, by the definitions of B_h and a_h(t),

(1-a_h(t))^{B_h}=\exp\left\{-Dt+\frac{2t}{b-1}b^{-h}\right\}.

The exponent difference is O(tb^{-H})=B_h^{-3c_t/4+o(1)}, which is smaller than the displayed error. This proves the second identity. □

Proof. For i\ge m, B_i^2+2B_iA_{i+1}=(B_i+A_{i+1})^2-A_{i+1}^2. Since B_i+A_{i+1}=A_i(1-q_i), summation gives the exact tail identity

\sum_{i=m}^h(B_i^2+2B_iA_{i+1})=A_m^2(1-q_m)^2-\sum_{i=m+1}^hA_i^2q_i(2-q_i).

Proposition 35 bounds the relative tail error by O(hq_m).

For the left part, Proposition 36 and the stable invariant give, uniformly for i<m, \rho_i=\widetilde a\,b^iu_i^D(1+O(\rho_m)), while A_i^2u_i^{D+1}/A_m^2=1+O(q_m+m\rho_m). Therefore

\frac1{A_m^2}\sum_{i=1}^{m-1}2B_iA_{i+1}=O\!\left(\widetilde a\sum_{i=1}^{m-1}b^i\right)=O(\widetilde a b^m)=O(\rho_m).

The square terms are smaller by a factor \rho_i/u_i, and the root term is O(\widetilde a A_m^2). This proves the displayed formula for Z_e.

The exact root belief is \alpha=B_0(B_0+A_1)/Z_e. Use A_1=1, the stable shadow’s formula for B_0, the displayed formula for Z_e, and B_0=o(1) to obtain

\alpha=\widetilde a\left(1+O(hq_m+\rho_m)\right).

Now apply Theorem 37 and the quantitative overlap scales. Polynomial factors in h are B_h^{o(1)}, which proves the last two displayed identities. □

Proof. First work in a terminal window and put c_t=Dt/\log B_h. We spell out the quantitative root reconstruction because its additive error is later compared with a vanishing coupon term. Proposition 36 and the exact root formulas give

B_0=\widetilde a\,u_1^{D+1}\left(1+O(q_m+m\rho_m)\right),\qquad \kappa=u_1^b\left(1+O(\rho_m)\right).

Since z=B_0\kappa/(1+B_0)^b, x=-\log u_1, and B_0=B_h^{-1+o(1)}, it follows that

-\log z=\log\frac1{\widetilde a}+Kx+O(q_m+m\rho_m+B_0)=\log\frac1{\widetilde a}+Kx+B_h^{-c_t/4+o(1)},\qquad K=b+D+1=bD.

The arithmetic identity Kb^{h-1}=Db^h=B_h+2/(b-1) and Theorem 37 yield

Kx=B_h(1-a_h(t))^{B_h}\left(1+B_h^{-c_t/4+o(1)}\right).

Lemma 38 gives \log(\alpha/\widetilde a)=B_h^{-c_t/4+o(1)} and B_h|\alpha-a_h(t)|=B_h^{-c_t/4+o(1)}. The latter estimate changes the coupon term relatively by 1+B_h^{-c_t/4+o(1)}. Hence

-\log z-\log\frac1\alpha=B_h(1-\alpha)^{B_h}\left(1+B_h^{-c_t/4+o(1)}\right)+B_h^{-c_t/4+o(1)}.

It remains to identify the terminal range corresponding to the displayed density interval. By Lemma 38, uniformly in every terminal window, \alpha B_h=Dt\left(1+B_h^{-c_t/4+o(1)}\right). Since \log B_h=h\log b+O(1), choose constants \delta_-,\delta_+>0 such that \underline\tau=(c_--\delta_-)\log b/D>0 and \overline\tau=(c_++\delta_+)\log b/D<4\log b/(3D). Uniformly on this broader terminal window, \alpha B_h=Dt(1+o(1)). At t=\underline\tau h the resulting density is below c_-\log B_h/B_h, while at t=\overline\tau h it is above c_+\log B_h/B_h. The terminal parameter increases the activity by Lemma 24, and activity increases the selected density by Theorem 28; hence every density in the displayed interval is exposed by a terminal parameter in the broader window. Uniformly there, c_t=c+o(1), and the terminal-window estimate becomes the additive quantitative identity above.

Finally, B_h(1-\alpha)^{B_h}=B_h^{1-c+o(1)}. The additive error is therefore relatively B_h^{3c/4-1+o(1)}, while the multiplicative orbit error is B_h^{-c/4+o(1)}. Taking the worst exponent over [c_-,c_+] proves the boxed activity law and the value of \delta; the lower-bound inequality follows immediately. □

Proof. Since B_0+A_1=1 and B_i+A_{i+1}=A_i for i\ge1,

B_0^2+2B_0A_1=1-A_1^2,\qquad B_i^2+2B_iA_{i+1}=A_i^2-A_{i+1}^2.

Summing gives total directed-edge mass one, and p_0=B_0(B_0+A_1)=\alpha.

For i<h, put S_i=B_{i-1}+B_i+A_{i+1}. The messages satisfy

\kappa A_i=S_i^b,\qquad \kappa B_i=S_i^b-A_i^b,\qquad \kappa=1/r.

It follows that \kappa p_i=S_i^d-A_i^d, \kappa x_i=B_{i-1}S_i^b, which is exactly the conditioned-binomial row identity with tilt B_{i-1}/A_i. A positive tilt gives expected nonempty-subset size strictly larger than one, hence lower-neighbor marginal strictly larger than 1/d. The terminal formulas follow directly from B_h=A_h and B_{h-1}=A_{h-1}-A_h.

It remains to verify the explicit threshold. Since B_h<Db^h,

\alpha b^{h-1}>\frac{C}{Db}=\frac{d-2}{d(d-1)}C.

Under the displayed threshold and |s|\le M, this is at least \log(d/(d-1)). Therefore

\varepsilon_h=(1-\alpha)^{b^{h-1}}\le e^{-\alpha b^{h-1}}\le\frac{d-1}{d},

as required. □

Proof. First replace the terminal entropy s_d(a_h) by the unconstrained coordinate entropy dH(a_h)=dH(\varepsilon_h). For every nonterminal layer, and for the relaxed terminal layer, the dual entropy identity and the message row identities reduce the layer contribution to

p_i\log\kappa-d x_i\log B_{i-1}+d x_{i+1}\log B_i,\qquad x_{h+1}=0.

The sum over i=1,\ldots,h telescopes to (1-\alpha)\log\kappa-dx_1\log B_0. The root contribution is (d-1)\alpha\log\alpha-\tfrac d2\alpha^2\log(\alpha^2). Using \kappa=1/r, x_1=\alpha r, and B_0=\alpha, the relaxed total is exactly H(\alpha). Restoring the nonempty terminal condition subtracts the displayed capped-free entropy loss.

Since A_h=rA_{h-1}^b,

p_h\varepsilon_h^d=A_{h-1}A_h\left(\frac{A_h}{A_{h-1}}\right)^d=rA_h^d=r^{1+dT_{h-1}}=r^B,

which proves the coupon identity.

For the asymptotic expansion, let \eta be the coordinate-exclusion probability before conditioning on a nonempty subset. Then

\varepsilon=\frac{\eta-\eta^d}{1-\eta^d},\qquad 1-\varepsilon=\frac{1-\eta}{1-\eta^d},\qquad \eta-\varepsilon=(1-\varepsilon)\eta^d,

so \eta=\varepsilon+O(\varepsilon^d). Substituting the first two identities into the entropy of the conditioned product measure gives

\Delta_d(\varepsilon)=-\log(1-\eta^d)-d\,\mathrm{KL}\!\left(\operatorname{Ber}(\varepsilon)\Vert\operatorname{Ber}(\eta)\right).

The Bernoulli chi-square bound makes the KL term O_d(\varepsilon^{2d-1}), while -\log(1-\eta^d)=\varepsilon^d(1+O_d(\varepsilon^{d-1})). □

Proof of Theorem 2. The upper type anchor gives \Psi_{d,h}(\alpha)\le H(\alpha), while Lemma 40 supplies a feasible compact profile for every sufficiently large h, uniformly in the displayed window. Hence Lemma 41 implies

0\le \mathcal D_h(\alpha)\le Q_h(\alpha)\left(1+O_d(\varepsilon_h^{d-1})\right).

There, \varepsilon_h=(1-\alpha)^{b^{h-1}}=B^{-\frac{d-2}{d(d-1)}+o(1)}, which proves the upper bound in the theorem’s two-sided estimate.

For the lower bound, define \mathcal A_h(a):=-\log z(a)-\log(1/a). The envelope identity of Corollary 29 gives

-\mathcal D_h'(a)=-\log(1-a)+\mathcal A_h(a).

Put

C_0=L-2\log L+s,\quad \alpha_0=C_0/B,\qquad C_1=\frac87L,\quad \alpha_1=C_1/B.

For all large h, the interval lies in the fixed density window with c_-=3/4 and c_+=8/7. Theorem 39 applies uniformly there with relative error B^{-1/7+o(1)}. Since -\log(1-a)\ge0 and \mathcal D_h(\alpha_1)\ge0,

\mathcal D_h(\alpha_0)\ge \left(1-B^{-1/7+o(1)}\right)B\int_{\alpha_0}^{\alpha_1}(1-a)^B\,da =\left(1-B^{-1/7+o(1)}\right)\frac{B}{B+1}\left[(1-\alpha_0)^{B+1}-(1-\alpha_1)^{B+1}\right].

Finally, (1-\alpha_1)^B/(1-\alpha_0)^B=B^{-1/7}L^{-2}e^{s+o(1)}, and \alpha_0=O(L/B). This proves the lower bound in the two-sided estimate and hence the bounded-window identity. □

Proof of Corollary 3. Uniformly for bounded s,

H\!\left(\frac{L-2\log L+s}{B}\right)=\frac{L^2}{B}(1+o(1)),

whereas

\left(1-\frac{L-2\log L+s}{B}\right)^B=e^{-s}\frac{L^2}{B}(1+o(1)).

Apply Theorem 2. □

Proof of Corollary 4. For every fixed \epsilon>0, Corollary 3 gives opposite signs at s=-\epsilon and s=\epsilon for all large h; because strict concavity makes the superlevel set \{\alpha:\Psi_{d,h}(\alpha)\ge0\} an interval, its lower endpoint satisfies C_h^{\mathrm{ann}}=L-2\log L+o(1).

Let F_B(C):=H(C/B)-(1-C/B)^B. Theorem 2 gives

\Psi_{d,h}(C/B)=F_B(C)+O\!\left((1-C/B)^B B^{-1/7+o(1)}\right)

uniformly in a fixed neighborhood of the scalar root. There, F_B'(C)=(1+o(1))(1-C/B)^B, uniformly and with positive sign. A two-sided mean-value comparison therefore proves C_h^{\mathrm{ann}}=\widehat C_{B_h}+O(B_h^{-1/7+o(1)}).

It remains to invert the scalar equation. For C=L+O(\ell), the scalar coupon root equation is equivalent to

C+\log C+\log(L-\log C+1)=L+O(L^2/B).

The equation first gives C=L-2\ell+O(\ell/L); substituting this estimate successively into the two logarithms determines the coefficients through order L^{-3}. If P_3 denotes the degree-3 polynomial in the corollary’s expansion, direct expansion gives

P_3+\log P_3+\log(L-\log P_3+1)-L=O(\ell^4/L^4),

while the derivative of the left side of the scalar log-equation is 1+O(1/L). Thus the mean-value theorem yields \widehat C_B-P_3=O(\ell^4/L^4+L^2/B)=O(\ell^4/L^4), which supplies the claimed bootstrap remainder. Finally, B^{-1/7+o(1)} is smaller than every fixed inverse power of L, so the graph-scalar comparison transfers the expansion to C_h^{\mathrm{ann}}. Repeating the same formal substitution and mean-value estimate yields the expansion to any prescribed fixed inverse power of L. □

Proof of Theorem 6. Put B=B_h and L=\log B. For a value C in the theorem’s hypothesis, set

\alpha_-=\frac CB,\qquad C^\sharp=\frac{L+C}2,\qquad \alpha_+=\frac{C^\sharp}B.

For large h, the interval [\alpha_-,\alpha_+] lies in a fixed density window \eta L/(2B)\le a\le L/B, so Theorem 39 applies uniformly. Exact globality and the envelope identity of Corollary 29 give

\Psi(\alpha_-)=\Psi(\alpha_+)+\int_{\alpha_-}^{\alpha_+}\log z(a)\,da.

Corollary 12 and Theorem 39’s displayed inequality imply

\Psi(\alpha_-)\le H(\alpha_+)-\int_{\alpha_-}^{\alpha_+}\log\frac1a\,da-\frac12\int_{\alpha_-}^{\alpha_+}B(1-a)^Bda \le H(\alpha_-)-\frac1{2}\frac{B}{B+1}\left[(1-\alpha_-)^{B+1}-(1-\alpha_+)^{B+1}\right].

The second inequality uses H'(a)=\log(1/a)+\log(1-a).

Write W(C):=L-2\log L-C. By hypothesis W(C)\ge W_h\to\infty. Uniformly over the theorem’s interval,

H(\alpha_-)=O\!\left(\frac{L^2}B\right)=o(e^{-C}),

because e^{-C}=e^{W(C)}L^2/B. Also C=O(L) gives (1-\alpha_-)^{B+1}=e^{-C}(1+o(1)). Finally, C^\sharp-C=(L-C)/2\ge \log L+W_h/2, so

(1-\alpha_+)^{B+1}=e^{-C^\sharp}(1+o(1))=o(e^{-C}).

All estimates are uniform, proving the theorem. □

Proof of Corollary 8. For C=cL with c\in[c_-,c_+], one has L-2\log L-C=(1-c)L-2\log L\to\infty uniformly. Theorem 6 gives e^{-C}=B^{-c}. □

Proof of Theorem 5. Put C_h^*=L_h-2\log L_h-\omega, T_n=nC_h^*/B_h. If T_n\le1, then the real-valued lower bound follows from \gamma_h(G)\ge1. Otherwise set m_n=\lceil T_n\rceil-1, C_n=m_nB_h/n. The theorem’s growth condition implies B_h/n=o(1). Indeed, h=\Theta_d(L_h). If B_h\ge n along a subsequence and x=B_h/n\ge1, then

\frac{nL_h^2/B_h}{h\log n}=\Theta_d\!\left(\frac{L_h}{x\log n}\right)=\Theta_d\!\left(\frac{1+\log x/\log n}{x}\right)=O_d(1),

contradicting the growth condition. Hence B_h<n eventually, so L_h\le\log n; the same displayed ratio tends to infinity only if n/B_h\to\infty. Therefore C_n=C_h^*+o(1), C_n\le C_h^*.

The scaling-function convergence is uniform on compact s-intervals; hence

\Psi_{d,h}(C_n/B_h)=-\left(e^\omega-1+o(1)\right)\frac{L_h^2}{B_h}.

The uniform type estimate in Remark 13 now gives

\log \mathbb E Z_{n,d,h}(m_n)\le -\left(e^\omega-1+o(1)\right)\frac{nL_h^2}{B_h}+O_d(h\log n)\longrightarrow-\infty.

Thus the pairing model has no dominating set of size exactly m_n with high probability. Any smaller dominating set can be padded to size m_n, so \gamma_h(G)\ge m_n+1=\lceil T_n\rceil\ge T_n. Conditioning on simplicity transfers the conclusion to the uniformly random simple d-regular graph, and the domination inequality following Definition 1 gives the final assertion. □

Proof of Theorem 9. Set T_n=nC_h^*/B_h. For large n, C_h^*>0. If T_n\le1, the real-valued lower bound follows from \gamma_h(G)\ge1. Otherwise put m_n=\lceil T_n\rceil-1, C_n=m_nB_h/n. Then m_n<T_n and m_n/T_n\ge1/2. Choose \eta>0 such that C_h^*\ge2\eta L_h eventually. Then, for large h, \eta L_h\le C_n\le C_h^*.

Apply Theorem 6 with this \eta and the same W_h. Since e^{-C_n}\ge e^{-C_h^*}=e^{W_h}L_h^2/B_h and \tfrac12-o(1)\ge\tfrac13 for sufficiently large h,

\log \mathbb E Z_{n,d,h}(m_n)\le -\frac13\frac{ne^{W_h}L_h^2}{B_h}+O_d(h\log n),

which tends to -\infty by the growth hypothesis. Markov’s inequality shows that the configuration model has no dominating set of size exactly m_n with high probability. Any smaller dominating set could be padded to size m_n, so \gamma_h(G)\ge m_n+1=\lceil T_n\rceil\ge T_n. Conditioning on simplicity transfers the conclusion to the uniformly random simple d-regular graph. □

Proof of Corollary 10. Choose W_h=\varepsilon L_h-2\log L_h. Then W_h\to\infty, C_h^*=(1-\varepsilon)L_h, C_h^*/L_h=1-\varepsilon>0, and e^{W_h}L_h^2/B_h=B_h^{-(1-\varepsilon)}. Thus Theorem 9 applies directly. □