Proof. Congruence by \(X^{-1/2}\) reduces the first assertion to the fact that the only possible nonzero eigenvalue of \(aa^{\mathsf T}\) is \(\|a\|^2\), with \(a=X^{-1/2}b\). For the second, \(Y^{-1/2}XY^{-1/2}\succeq I\); diagonalization and inversion give \(X^{-1}\preceq Y^{-1}\). ◻

Proof. A vector is orthogonal to every incidence column precisely when its coordinates agree at the endpoints of each edge, equivalently when it is constant on every connected component. The orthogonal complement thus has dimension \(c\). A tree on \(n\) vertices has \(n-1\) edges, as follows by deleting leaves successively, so its spanning columns form a basis. ◻

Proof. The necessity follows by counting the crossings of each tree. For sufficiency, choose \(r\) disjoint forests whose total number \(m\) of edges is maximum. A state is such a choice. Starting from this state, allow a move that adds an unused edge to one forest and removes an edge of the resulting cycle.

In every reachable state, every unused edge closes a cycle with each forest: otherwise adding it would increase \(m\). Let \(U\) be the set of edges that are unused in at least one reachable state. If an unused edge is added to a forest, every edge of the resulting cycle lies in \(U\), since any one of its original edges can be made unused by the corresponding move. Such a move preserves the components of that forest restricted to its edges in \(U\). It also leaves the other forests unchanged.

Fix \(e\in U\). In a state where \(e\) is unused, its endpoints are connected by edges in \(U\) in each forest. The component invariance just proved carries this statement to the initial state. Consequently each component of \((V(H),U)\) is spanned by the \(U\)-edges of every forest. If there are \(d\) such components, this accounts for \(r(n-d)\) used edges, where \(n=|V(H)|\). Every edge between these components is used, since every unused edge belongs to \(U\). Their number is therefore at most \[m-r(n-d).\] If \(m<r(n-1)\), this is smaller than \(r(d-1)\), contrary to the partition hypothesis. Thus \(m=r(n-1)\); each of the \(r\) forests has \(n-1\) edges and is a spanning tree. ◻

Proof. For (i), enumerate the \(q\) trees on each of \(A\) and \(B\). In the \(i\)-th tree on \(B\), contract all vertices of \(A\cap B\) to a single vertex, discard loops, and choose a spanning tree of the resulting connected multigraph. Its selected edges, together with the \(i\)-th tree on \(A\), form a tree on \(A\cup B\). Every selected edge has an endpoint outside \(A\), so no such edge lies in any tree on \(A\). The selections in different colors remain disjoint. This proves (i).

Every singleton is packable, and finiteness gives maximal sets. Part (i) shows that two maximal sets cannot intersect unless equal. Every previously packable set remains packable when edges are added, which proves (ii).

For (iii), contract the parts and remove loops. If its crossing count were at least \(q(d-1)\), where \(d=|\mathcal P(F)|>1\), the quotient would have a set \(W\) of at least two vertices with \(|E(W)|\ge q(|W|-1)\). Choose such \(W\) inclusion-minimal. For each proper nonempty \(J\subset W\), \[|E(J)|\le q(|J|-1);\] this also holds for a singleton because loops were removed. For a partition \(W=J_1\sqcup\cdots\sqcup J_t\), with \(t\ge2\), subtraction gives at least \[q(|W|-1)-\sum_{\ell=1}^t q(|J_\ell|-1)=q(t-1)\] edges between its parts. Theorem 4 supplies \(q\) quotient trees on \(W\). Attach to each color a packed tree inside each of its quotient vertices. This gives \(q\) disjoint spanning trees on their union in \(F\), contradicting maximality of the parts. ◻

Proof. Temporarily suppress \(X\) from the notation. In each occupied bin \(2^a\le M_s<2^{a+1}\), \(a\ge0\), choose the finest partition that occurs in that bin. List the chosen partitions in order from fine to coarse as \(\mathcal P_0,\ldots,\mathcal P_{\ell-1}\), with crossing sets \(B_i\) and sizes \(M_i\). Append \(\mathcal P_\ell=\{V\}\), \(B_\ell=\varnothing\), \(M_\ell=0\).

The distinct parts of these partitions, together with all singletons, form a laminar family containing \(V\). Give each proper set its smallest proper containing set as parent. The children of every nonsingleton partition that set, so this is a hierarchy. Every induced graph at a node is \(q\)-edge-connected: this was proved for the partition parts, the root is \(r\)-tree-packable, and singleton conditions are vacuous. Take the response \(Y\) from (6) for this hierarchy.

Consider a transition \(\mathcal P_j\) to \(\mathcal P_{j+1}\). If a part \(A\in\mathcal P_j\) changes, the part of \(\mathcal P_{j+1}\) containing it is its immediate parent in the hierarchy. Indeed, earlier selected partitions are finer and later ones are coarser, so none supplies a distinct set strictly between these two. Adding singleton leaves creates no such set.

An edge of \(B_j\setminus B_{j+1}\) has endpoints in two changing parts of \(\mathcal P_j\) with the same parent. It belongs to the \(O(A)\) set of each of those parts; see Figure 1. The total full boundary size of all changing parts is at most \(2M_j\), since they belong to the single partition \(\mathcal P_j\). For the unmarked changing parts, \[\sum_A |O(A)|\le \frac1q\sum_A|P(A)|\le\frac{2M_j}{q}.\] For the marked changing parts, (7) gives \[\bigl|\{e\in O(A):R_Y(e)>r^{-1/2}\}\bigr| \le r^{-1/4}|O(A)|.\] Their total bad-edge count is therefore at most \(2M_jr^{-1/4}\). These counts may cover an edge more than once, which only enlarges the upper bound. Consequently at most \[2(r^{-1/4}+1/q)M_j\] of the disappearing edges are bad.

There is only one representative per occupied dyadic bin, so its bin exponents strictly decrease. For every \(i<\ell\), \[ \sum_{j=i}^{\ell-1}M_j<4M_i. \tag{9}\] For example, if \(2^a\le M_i<2^{a+1}\), the successive terms are bounded by \(2^{a+1},2^a,2^{a-1},\ldots\). Every edge of \(B_i\) disappears at exactly one later transition. Its bad-edge count is thus at most \[8(r^{-1/4}+1/q)M_i.\] For an arbitrary \(s\) with \(M_s>0\), the chosen representative in its bin is finer, so \(B_s\subseteq B_i\) and \(M_i<2M_s\). The bad-edge count in \(B_s\) is at most \[16(r^{-1/4}+1/q)M_s\le40r^{-1/4}M_s\] for all sufficiently large \(r\). If \(M_s=0\), the assertion is immediate. This proves (8) simultaneously for every threshold. ◻

Proof of Theorem 8. The response supplied by Lemma 9 need not vary continuously with \(X\). We interpolate only finitely many responses at a time.

For each positive integer \(p\), cover \(\mathcal K\) by finitely many relative open balls of radius \(1/p\), with centers \(C_{p,1},\ldots,C_{p,N_p}\in\mathcal K\). At each center choose a response \(Y_{p,j}\). Define continuous weights \[\phi_{p,j}(Z)= \frac{\max\{0,p^{-1}-\|Z-C_{p,j}\|\}} {\sum_{h=1}^{N_p}\max\{0,p^{-1}-\|Z-C_{p,h}\|\}} \qquad(Z\in\mathcal K).\] The denominator is positive by the open cover. The map \[\Phi_p(Z)=\sum_{j=1}^{N_p}\phi_{p,j}(Z)Y_{p,j}\] is a continuous self-map of the compact convex set \(\mathcal K\). Theorem 46 gives \(X_p=\Phi_p(X_p)\). Pass to a subsequence along which \(X_p\to X\in\mathcal K\).

Choose \[3r^{-1/2}<s<4r^{-1/2}\] distinct from every \(R_X(e)\), \(e\in E(H)\). This is possible because the graph is finite. If \(\phi_{p,j}(X_p)>0\), then \[\|C_{p,j}-X\|<p^{-1}+\|X_p-X\|\longrightarrow0\] uniformly over these centers. The resistance of each edge is continuous on \(\mathcal K\). Since all resistances at \(X\) avoid \(s\), for all sufficiently large \(p\) every contributing center has exactly the same threshold graph, packing partition, and crossing set as \(X\).

Write \(B=B_s(X)\), \(M=|B|\), and \(\delta=C_0r^{-1/4}\). If \(M=0\), connectedness of \(H\) implies that its partition is \(\{V\}\), and the conclusion already follows. Otherwise, for large \(p\), each contributing \(Y_{p,j}\) has at most \(\delta M\) bad edges in this same set \(B\). Summing their bad indicators with weights \(\phi_{p,j}(X_p)\) shows that at most \(2\delta M\) edges receive bad weight greater than one half.

For every other edge \(e\in B\), at least half the total weight is on matrices satisfying \[Y_{p,j}\succeq r^{1/2}b_eb_e^{\mathsf T},\] by Lemma 2. All remaining matrices are positive semidefinite. Hence their convex combination satisfies \[X_p\succeq\tfrac12r^{1/2}b_eb_e^{\mathsf T}, \qquad R_{X_p}(e)\le2r^{-1/2}.\] Thus at least \(N=\lceil(1-2\delta)M\rceil\) edges satisfy this closed inequality. The condition that at least \(N\) edges of the finite set \(B\) obey it is closed: it is a finite union, over \(N\)-element subsets of \(B\), of finite intersections of closed conditions. The same count therefore holds at the limit \(X\). Since \(2r^{-1/2}<s\), these edges belong to \(F_s(X)\).

Suppose \(\mathcal P_s(X)\) has \(d>1\) parts. The original \(r\) packed trees in \(H\) give \(M\ge r(d-1)\). Choose the absolute threshold on \(r\) so that \(2C_0r^{-1/4}<u\). Then \[|E_{F_s(X)}(\mathcal P_s(X))| \ge(1-2C_0r^{-1/4})M >q(d-1),\] contradicting Lemma 5(iii). The partition is therefore \(\{V\}\), so \(F_s(X)\) is \(q\)-tree-packable. Every one of its edges has resistance at most \(s<4r^{-1/2}\), and \(X\in\mathcal K\) gives (4). ◻

Proof. For the first assertion choose \(a\in\mathbb H\) with \(f(a)\ne0\). Pass to a subsequence on which the degree is constant, and enumerate its roots \(\lambda_{\nu,1},\ldots,\lambda_{\nu,e}\) with multiplicity. By compactness of the complex plane together with the point at infinity, a further subsequence makes every root converge, allowing infinite limits. Every finite limit lies outside \(\mathbb H\). In the factorization \[\frac{f_\nu(z)}{f_\nu(a)} =\prod_{k=1}^e\frac{z-\lambda_{\nu,k}}{a-\lambda_{\nu,k}},\] a root tending to infinity contributes a factor tending to \(1\), and a root tending to a finite \(\lambda_k\) contributes \((z-\lambda_k)/(a-\lambda_k)\). The limiting identity factors \(f(z)/f(a)\) with all its roots outside \(\mathbb H\). For real-rooted \(f_\nu\), the same proof uses the extended real line; all finite limiting roots are then real.

For the last assertion, a bounded set of monic coefficient vectors has bounded roots. Indeed a root of \(z^d+\sum_{k<d}a_kz^k\) has absolute value at most \(1+\max_k|a_k|\), as is seen by summing a geometric series when the opposite strict inequality holds. Any convergent subsequence of ordered root tuples factors the limiting polynomial. Its limiting tuple must therefore be the unique ordered root tuple of that polynomial. This proves continuity. ◻

Proof. For the first assertion, when all variables are in \(\mathbb H\), the imaginary part of the matrix is \[(\operatorname{Im}x)I+\sum_i(\operatorname{Im}z_i)A_i\succ0.\] Such a matrix is nonsingular: a nonzero kernel vector would have a strictly positive imaginary part in its quadratic form, a contradiction. The same argument applies to the second determinant because \(\sum_iA_i\succ0\). For real arguments the matrices are Hermitian and their determinants are real; consequently the polynomial coefficients are real.

For the second assertion, fix all arguments of \(p\) in \(\mathbb H\), and regard \(p\) as a polynomial in argument \(i\) alone. This slice is nonzero, and its roots \(\alpha_k\) have nonpositive imaginary parts. If it is nonconstant, factorization gives \[ \frac{\partial_i p}{p} =\sum_k\frac1{z_i-\alpha_k}, \qquad \operatorname{Im}\frac{\partial_i p}{p}<0. \tag{20}\] If the slice is constant, the quotient is zero. In either case it cannot equal \(1\), so \((1-\partial_i)p\) is nonzero at this point. The operation preserves real coefficients.

For the last assertion, replace each fixed real constant \(a\) by \(a+\mathrm i\eta\), \(\eta>0\). The resulting univariate polynomials have no zeros in \(\mathbb H\) and converge coefficientwise to the stated nonzero real polynomial. Apply Lemma 16. ◻

Proof. The determinant in (21) is stable by Lemma 17; applying all the operators preserves stability. Specializing all \(z_i\) to zero leaves a nonzero real-rooted polynomial. To see directly both that it is nonzero and that it is monic of degree \(d\), the coefficient of \(x^d\) in the determinant is \(1\), independent of the \(z_i\), and every term involving at least one \(z_i\) has smaller \(x\)-degree. The operations leave that leading coefficient unchanged. The specialization can be performed all at once by substituting \(z_i=\mathrm i\eta\) and using Lemma 16.

For the identity, let \(M\) be any square matrix, let \(v\) be a random vector, and put \(A=\mathbb E[vv^*]\). The rank-one determinant identity and the derivative formula for the determinant give \[\begin{align*} \mathbb E\det(M-vv^*) &=\det M-\operatorname{tr}(\operatorname{adj}(M)A)\\ &=\left.(1-\partial_z)\det(M+zA)\right|_{z=0}. \end{align*}\] Here \(\operatorname{adj}(M)\) is the adjugate. These identities hold also for singular \(M\): they are polynomial identities in its entries, or follow directly by multilinearity of the determinant in its columns. Apply this formula conditionally to \(v_m\), then \(v_{m-1}\), and so forth. Independence keeps each covariance \(A_i\) unchanged under conditioning. Finite sums, differentiation, and the specializations commute, giving (22). ◻

Proof. First consider two members \(p,q\) and \(r_t=(1-t)p+tq\), \(0\leq t\leq1\). Fix a real \(x\) that is not a root of either \(p\) or \(q\), and let \(N(t)\) count the roots of \(r_t\) strictly below \(x\), with multiplicity. By ordered-root continuity, \(N\) is locally constant wherever \(r_t(x)\ne0\). The affine function \(r_t(x)\) vanishes at most once. If it vanishes at \(t_0\in(0,1)\), then \(b=q(x)-p(x)\ne0\).

We claim that \(x\) is a simple root of \(r_{t_0}\). Otherwise let its multiplicity be \(\ell\geq2\) and write \[r_{t_0}(x+w)=aw^\ell+O(w^{\ell+1}),\qquad a\ne0.\] For \(h\) tending to zero with fixed sign \(\sigma\in\{-1,1\}\), \[|h|^{-1}r_{t_0+h}\bigl(x+|h|^{1/\ell}z\bigr) \longrightarrow az^\ell+\sigma b\] coefficientwise. Every polynomial on the left is real-rooted; hence so is its nonzero limit by Lemma 16. For \(\ell=2\), choose the sign so that \(\sigma b/a>0\), obtaining two nonreal roots. For \(\ell\geq3\), the equation \(z^\ell=-\sigma b/a\ne0\) has nonreal roots for either sign. This contradiction proves the claim.

Thus \(N\) can change by at most one, at that single simple crossing. It follows that \(|N(0)-N(1)|\leq1\). If \(\lambda_k(p)>\lambda_{k+1}(q)\) for some \(k<d\), one can choose \(x\) strictly between these roots and avoiding all endpoint roots. Then \(N(0)\leq k-1\) and \(N(1)\geq k+1\), a contradiction. Applying this reasoning to every pair gives \[\lambda_k(p_i)\leq\lambda_{k+1}(p_j) \quad\hbox{for all }i,j\hbox{ and }k<d.\] Therefore \(c_k=\max_i\lambda_k(p_i)\) is a common interlacing. This proof includes repeated roots because all interlacing inequalities are weak.

For the last assertion discard zero-weight polynomials and denote the weighted average by \(P\), with largest root \(\rho\). If \(d=1\), \(\rho\) is the weighted average of the individual roots, which proves the assertion. Otherwise put \(c=c_{d-1}\). Every \(p_i(c)\leq0\), since its first \(d-1\) roots are at most \(c\) and its last root is at least \(c\). Thus \(P(c)\leq0\), and, since \(P\) is monic, \(\rho\geq c\). For each \(x>\rho\), \(P(x)>0\), so at least one \(p_i(x)>0\). Its first \(d-1\) roots are below \(x\); positivity therefore implies \(\lambda_d(p_i)<x\). Taking the minimum over the finite collection and letting \(x\downarrow\rho\) proves \(\min_i\lambda_d(p_i)\leq\rho\). ◻

Proof. Delete zero-probability support points. For a fixed choice of the first \(k\) vectors, consider the expected characteristic polynomial over the remaining vectors. It is monic of degree \(d\) and real-rooted by Lemma 18, treating the first \(k\) vectors as deterministic. Its children are the conditional polynomials formed by fixing one further vector to each of its possible values.

Every convex combination of these children is again real-rooted: it is the expected characteristic polynomial for the same family, with the next vector assigned the probabilities of that convex combination. Lemma 19 therefore lets us choose a positive-probability child whose largest root does not increase. Repeating for \(k=0,\ldots,m-1\) yields a complete outcome. The probability of that outcome is a product of finitely many positive support probabilities, so is positive. At the leaf, the polynomial is the characteristic polynomial of \(\sum_i v_iv_i^*\) and its largest root is the largest eigenvalue. ◻

Proof. Set \(h(t)=p(z+te_j)\) and \(a(t)=\partial_i p(z+te_j)\). The polynomial \(h\) is real-rooted by Lemma 17, and is nonzero since \(h(0)>0\). It is positive on \([0,\infty)\), so every root is strictly negative. Thus the real rational function \(R=a/h\) has only negative real poles, after cancelling common factors.

We next show that \(\operatorname{Im}R(t)\leq0\) for \(t\in\mathbb H\). In (20), use the point with argument \(z_j+t\) in coordinate \(j\) and argument \(z_k+\mathrm i\eta\) in every other coordinate. All coordinates have positive imaginary parts, and the logarithmic derivative in direction \(i\) has nonpositive imaginary part. Let \(\eta\downarrow0\). Since \(h(t)\ne0\) for \(t\in\mathbb H\), the quotient converges to \(R(t)\) and proves the desired inequality.

Also \(R(t)\geq0\) for real \(t\geq0\). Indeed \(g(s)=p(z+te_j+se_i)\) is a nonzero real-rooted polynomial, positive for \(s\geq0\). Factoring it with its negative real roots \(\beta_k\) gives \[R(t)=\frac{g'(0)}{g(0)}=\sum_k\frac1{-\beta_k}\geq0;\] the empty sum covers a constant \(g\).

It remains to classify this rational function, which can be done directly. At a pole \(\lambda\) of order \(b\geq1\), let its highest principal part be \(a_0(t-\lambda)^{-b}\), with \(a_0\ne0\) real. At \(t=\lambda+r\exp(\mathrm i\theta)\), as \(r\downarrow0\), the leading imaginary part is \(-a_0r^{-b}\sin(b\theta)\). For \(b\geq2\) this has both signs for \(0<\theta<\pi\), contradicting \(\operatorname{Im}R\leq0\). Hence every pole is simple, and the same inequality for \(b=1\) forces its residue to be positive.

Subtract these simple principal parts. The remainder is a real polynomial. If its degree were at least two, its leading term along large rays \(t=r\exp(\mathrm i\theta)\) would again have imaginary parts of both signs; the subtracted fractions are \(O(1/r)\) and cannot affect this conclusion. Thus the remainder has degree at most one, and a linear remainder must have nonpositive slope. The inequality \(R(t)\geq0\) for all real \(t\geq0\) rules out a negative slope and forces its constant term to be nonnegative. This proves (23).

Finally, direct differentiation on \(t\geq0\) gives \[R'(t)=-\sum_\ell\frac{c_\ell}{(t-\lambda_\ell)^2}\leq0, \qquad R''(t)=2\sum_\ell\frac{c_\ell}{(t-\lambda_\ell)^3}\geq0.\] Together with \(R(t)\geq0\), these are the asserted properties. ◻

Proof. The polynomial \(q\) is real stable by Lemma 17. Applying the monotonicity in Lemma 21 successively in each coordinate, for every vector \(s\geq0\) we have \[\Phi_p^j(z+s)\leq\Phi_p^j(z)\leq1-1/\delta<1.\] It follows that \(q(z+s)=p(z+s)(1-\Phi_p^j(z+s))>0\). Thus \(z\), and therefore also \(w\), belongs to \(\operatorname{Ab}_q\).

Fix \(i\) and put \(f(t)=\Phi_p^i(z+te_j)\). Commuting the mixed derivatives of \(\log p\) in a neighborhood of \(w\) gives \[\Phi_q^i(w) =f(\delta)-\frac{f'(\delta)}{1-\Phi_p^j(w)}.\] By monotonicity, the denominator is at least \(1/\delta\), and \(f'(\delta)\leq0\). By convexity, \(f(0)\geq f(\delta)-\delta f'(\delta)\); this also follows by integrating the nondecreasing derivative on \([0,\delta]\). Therefore \[\Phi_q^i(w) \leq f(\delta)-\delta f'(\delta) \leq f(0)=\Phi_p^i(z),\] as required. ◻

Proof. Let \[p_0(y)=\det\left(\sum_{i=1}^m y_iA_i\right), \qquad p_j=(1-\partial_{y_j})p_{j-1}\quad(1\leq j\leq m).\] The first polynomial is real stable by Lemma 17, since \(\sum_iA_i=I_d\). Moreover, \[ \mu[A_1,\ldots,A_m](x)=p_m(x,\ldots,x). \tag{26}\] To check this identity, substitute \(y_i=x+z_i\) before applying the operators. Then \(\sum_i y_iA_i=xI_d+\sum_i z_iA_i\), \(\partial_{y_i}\) acts as \(\partial_{z_i}\), and setting every \(z_i=0\) is exactly (21).

Set \[t=\epsilon+\sqrt\epsilon, \qquad \delta=1+\sqrt\epsilon, \qquad \varphi=\frac\epsilon t=1-\frac1\delta.\] At \(z^{(0)}=t\mathbf1\), the matrix in \(p_0\) is \(tI_d\). Adding nonnegative coordinates adds a positive-semidefinite matrix, so \(z^{(0)}\in\operatorname{Ab}_{p_0}\). Differentiating the determinant gives, for every \(i\), \[\Phi_{p_0}^i(z^{(0)}) =\operatorname{tr}((tI_d)^{-1}A_i) \leq\frac\epsilon t=\varphi.\] Inductively define \(z^{(j)}=t\mathbf1+\delta(e_1+\cdots+e_j)\). Suppose \(z^{(j-1)}\in\operatorname{Ab}_{p_{j-1}}\) and all its barriers are at most \(\varphi\). Because \(\varphi+1/\delta=1\), Lemma 22 applies in direction \(j\) and yields \(z^{(j)}\in\operatorname{Ab}_{p_j}\), with all its barriers still at most \(\varphi\). This proves the induction for every \(j\).

At the end, \(z^{(m)}=(t+\delta)\mathbf1\) is above the roots of \(p_m\). By (26), the mixed polynomial is positive for every real \(x\geq t+\delta\). It is real-rooted by Lemma 18; hence its largest root is at most \[t+\delta=\epsilon+2\sqrt\epsilon+1 =(1+\sqrt\epsilon)^2.\] ◻

Proof of Theorem 15. Put \(A_i=\mathbb E[v_iv_i^*]\). These matrices are Hermitian positive semidefinite, and (18) says that \(\sum_iA_i=I_d\) and \(\operatorname{tr}A_i=\mathbb E\|v_i\|^2\leq\epsilon\). Lemma 23 bounds the largest root of their mixed polynomial by \((1+\sqrt\epsilon)^2\). Lemma 20 then supplies an outcome of positive probability whose largest eigenvalue obeys the same bound. The matrix \(\sum_i v_iv_i^*\) is positive semidefinite, so this largest eigenvalue is its operator norm. This proves (19). ◻

Proof. The assertion for an empty marked set follows by taking a sufficiently small positive multiple of the identity, so assume \(\mathcal M\ne\varnothing\). We give the finite-dimensional duality argument as well as the matrix and embedding steps.

Proof. For \(H\in\mathcal Z\), clamp the radial distance to its radial interval: \[f_H(y)=\min\{b_H,\max\{a_H,\|y-x_H\|_1\}\}.\] For every \(a_H<t<b_H\), the set \(S_{H,t}=\{v:\|X_v-x_H\|_1<t\}\) is nonempty and proper, by (58). Its edge boundary therefore has at least \(k\) edges, with multiplicity. Integrating this finite step function gives \[ k(b_H-a_H) \le \int_{a_H}^{b_H}|E(S_{H,t},V\setminus S_{H,t})|\,dt =\sum_{\{u,v\}\in E}|f_H(X_u)-f_H(X_v)|. \tag{60}\] Indeed, the contribution of an edge to the integral is exactly the length of the interval of thresholds lying between its two endpoint distances, intersected with \((a_H,b_H)\).

Fix an edge \(e=\{u,v\}\), put \(L_e=\|X_u-X_v\|_1\), and let \(\gamma(s)=(1-s)X_u+sX_v\), \(0\le s\le1\). The segment lies in the convex set \(Q\). Every \(g_H=f_H\circ\gamma\) is a continuous, finitely piecewise affine function: each coordinate in its defining norm is an absolute value of an affine function, and clamping adds only finitely many breakpoints. The reverse triangle inequality and the fact that clamping does not increase distances show that \(g_H\) is \(L_e\)-Lipschitz.

Take a common finite subdivision \(0=s_0<\cdots<s_m=1\) on which all the \(g_H\) are affine. If \(g_H\) is nonconstant on one of these intervals, its value in the interval’s interior lies strictly between \(a_H\) and \(b_H\). The corresponding points of \(\gamma\) belong to \(H\). Pairwise disjointness permits at most one such nonconstant function on each interval. Hence \[\begin{align*} \sum_{H\in\mathcal Z}|g_H(1)-g_H(0)| &\le \sum_{j=1}^m\sum_{H\in\mathcal Z} |g_H(s_j)-g_H(s_{j-1})|\\ &\le \sum_{j=1}^m L_e(s_j-s_{j-1})=L_e. \end{align*}\] This also handles a segment lying along a shell boundary: its clamped radial function is constant there. Summing (60) over \(H\) and then applying the last bound to each edge proves (59). ◻

Proof of Proposition 31. It suffices to prove the claim for each finite initial sequence \(\mathcal F_1,\ldots,\mathcal F_q\). For this proof only, set \(\Delta_{q+1}=0\). Each family is finite because its positive-radius balls are disjoint and their centers are drawn from the finite set \(\{X_v:v\in V\}\).

We first record the scale inequalities. Two disjoint balls of radius \(\delta_i\), with centers \(z,z'\in Q\), satisfy \(\|z-z'\|_1\ge2\delta_i\): otherwise their midpoint, which belongs to \(Q\), would lie in both balls. A compact bag contains two such balls. Consequently \[ 2\delta_i\le\Delta_i, \qquad 6\Delta_{i+1}\le\frac{\delta_i}{2}, \qquad |D|\delta_i\ge \beta\Delta_i \quad(D\in\mathcal F_i). \tag{61}\]

Proof of Theorem 7. All cut constraints in this proof are for nonempty proper subsets of the vertex set. If the marked set \(\mathcal M\) is empty, a sufficiently small positive multiple of the identity is a shortcut, so suppose it is nonempty. Write \(q\) for the connectivity parameter of the theorem. We may require \(q\) to exceed an absolute cutoff, which will be increased finitely many times below.

Fix an arbitrary binary embedding \(X:V\to\{0,1\}^d\) and an arbitrary row semiorthogonal matrix \(U\in\mathbb R^{E\times d}\) as in Lemma 24, and suppose that \[\mathcal E=\sum_{e\in E}\|Xb_e\|_2^2>0.\] The map \(U\) is a contraction. By changing its row signs, we may assume \[a_e=\langle u_e,Xb_e\rangle\ge0 \qquad(e\in E).\] This can only increase the numerator to be bounded. Put \(d_e=\|Xb_e\|_2^2=\|Xb_e\|_1\) and, for \(t\in\mathcal M\), set \[N_t=\frac{1}{|O(t)|}\left(\sum_{e\in O(t)}a_e\right)^2.\] Choose \[ \alpha=q^{-4/5},\qquad \epsilon=\frac1{10},\qquad \beta=36,\qquad \rho=\frac1{2q^2},\qquad C_4=3,\qquad C_3=10^4. \tag{91}\]

Let \(T\subseteq\mathcal M\) consist of the \(\alpha\)-bad nodes with positive numerator, in the sense of Definition 27. Each node outside \(T\) either has zero numerator or satisfies \(N_t<\alpha\sum_{e\in O(t)}d_e\). Since each edge lies in at most two parent boundaries, \[ \sum_{t\in\mathcal M\setminus T}N_t\le2\alpha\mathcal E. \tag{92}\] If \(T\) is empty, this already bounds the entire numerator. Otherwise we apply Proposition 30 to \(T\), with its geometric ratio \(\lambda\) set equal to \(\rho\) and its small parameter \(s\) given by \[ \begin{aligned} J&=1+\left\lceil\log_2(256/\alpha^2)\right\rceil, &C_2&=128J^4, &s&=\alpha/C_2,\\ L&=2+\lceil\log_2(1/s)\rceil, &H&=1+\lceil\log_2(24/(\rho s^2))\rceil, &C_1&=1024\epsilon^{-2}. \end{aligned} \tag{93}\] These quantities depend on \(q\) alone. In particular, for absolute constants \(c_2,c_5\) and all sufficiently large \(q\), \[ C_2\le c_2(1+\log q)^4, \qquad L,H\le c_5(1+\log q). \tag{94}\] For example, the first inequality follows immediately from \(\log_2(256/\alpha^2)=8+(8/5)\log_2q\); the other two follow by taking logarithms of \(s=q^{-4/5}/C_2\) and \(\rho=1/(2q^2)\).

The smallness condition in Proposition 30 holds eventually because \(s^\epsilon\le q^{-2/25}\to0\), whereas \(48\beta C_1\) is an absolute constant. The assignment strength it provides also satisfies \[ s^{1+2\epsilon}=\frac{q^{-24/25}}{C_2^{6/5}} \ge\frac{24C_3}{q} \tag{95}\] for all sufficiently large absolute \(q\). Indeed, after multiplication by \(q\), its left side is \(q^{1/25}/C_2^{6/5}\), which tends to infinity by (94).

The proposition therefore yields a \(\rho\)-geometric sequence, either of \(36\)-compact families or of families that are at least \((24C_3/q)\)-assigned. Let its mass be \(\mathsf M\). Its guarantee is \[ \mathsf M\ge \frac{s^\epsilon}{384\beta C_1C_2LH}\sum_{t\in T}N_t. \tag{96}\] In the assigned case, a stronger assignment implies the required weaker assignment because the cardinality condition is a lower bound. The selected nodes are a subset of the original marked nodes, so \[|O(t)|\ge\frac1q|P(t)|\ge q\rho|P(t)|.\] Thus the hierarchy satisfies the hypothesis of Proposition 33 with \(k=q\) and \(\lambda=\rho\). The constants in (91) obey its numerical restrictions, and \(\rho\le1/18\) for all sufficiently large \(q\). In the compact case, Proposition 31 applies, since \(\rho\le1/12\). Both cases give the uniform lower bound \[ \mathcal E\ge\kappa q\mathsf M, \qquad \kappa=\frac{C_4}{96C_3}=\frac1{320000}. \tag{97}\] The energy is the same in the dual and charging estimates, since each coordinate of \(Xb_e\) is \(0\), \(1\), or \(-1\).

Combining (96) and (97) proves \[ \frac{\sum_{t\in T}N_t}{\mathcal E} \le\frac{384\beta C_1C_2LH}{\kappa q s^\epsilon} \le c_6 q^{-23/25}(1+\log q)^7 \tag{98}\] for an absolute \(c_6\). To check the final exponent, substitute \(s^\epsilon=q^{-2/25}C_2^{-1/10}\) and use (94); the logarithmic power before rounding up is \(4(11/10)+2=32/5<7\).

Equations (92) and (98), including the case \(T\) is empty, yield the uniform bound \[ \frac{\sum_{t\in\mathcal M}N_t}{\mathcal E} \le2q^{-4/5}+c_6q^{-23/25}(1+\log q)^7 =o(q^{-31/40}). \tag{99}\] Every constant in this estimate is absolute, and the embedding and semiorthogonal matrix were arbitrary. Hence the same upper bound holds for the supremum \(Q_*\) of Lemma 24. Increase the absolute integer cutoff \(q_H\) so that the right side of (99) is at most \(q^{-31/40}/2\) for \(q\ge q_H\), as well as so that all previous numerical conditions hold. Applying that lemma with \(K=q^{-31/40}/2\) and \(\eta=q^{-31/40}/2\) supplies a feasible full positive definite \(D\) whose every marked average is less than \(q^{-31/40}\). This proves the theorem. In particular, selecting a feasible matrix from the infimum uses only strict slack; no assertion of attainment is needed. ◻

Proof. For \(d\ge1\), we use the following elementary incidence fact. A small \((d-1)\)-face belongs to two small \(d\)-simplices if it is not contained in the boundary, and to one if it is. To see this, choose a point in its relative interior. Any simplex containing that point contains the entire face, by the common-face intersection property. Finiteness allows a sufficiently small ball in the affine hull of \(\Delta_d\), centered at the point, to avoid all other simplices. Shrinking the ball further, each incident \(d\)-simplex occupies exactly one half of this ball, on one side of the face’s affine hyperplane: the point lies on none of its other facets. Disjoint interiors permit at most one simplex on either side, and the covering property supplies all sides belonging to \(\Delta_d\). A boundary \((d-1)\)-face lies in exactly one original facet, so precisely one side belongs to \(\Delta_d\). Indeed, a coordinate vanishing at a relative interior point vanishes on the whole face, and two distinct original facets intersect in dimension at most \(d-2\).

Induct on \(d\). For \(d=0\), there is one vertex, labeled zero. For \(d\ge1\), call a small \((d-1)\)-face special if its labels are exactly \(0,\ldots,d-1\). Count incidences between small \(d\)-simplices and their special faces. A simplex with all \(d+1\) labels contributes one incidence. A simplex containing \(0,\ldots,d-1\) but not \(d\) has exactly one repeated label and contributes two, by deleting either vertex with that label. Every other simplex contributes zero. Modulo two, the incidence count is therefore the number asserted to be odd.

By the incidence fact, the same count modulo two is the number of special faces on the boundary. Such a face cannot lie in \(x_i=0\) for \(i<d\), since then none of its vertices could receive label \(i\). Hence these are exactly the fully labeled top-dimensional simplices in the induced triangulation of \(x_d=0\). The labels there satisfy the same rule in dimension \(d-1\), and induction makes their number odd. ◻

Proof of Theorem 46. First let \(F:\Delta_d\to\Delta_d\) be continuous. The case \(d=0\) is immediate. In each of the successive barycentric subdivisions, a vertex fixed by \(F\) already proves the claim. Otherwise label each vertex \(v\) by an index \(i\) for which \(v_i>F_i(v)\). Such an index exists because the two coordinate sums are equal and \(v\ne F(v)\); it satisfies \(v_i>0\). Lemma 47 supplies a fully labeled simplex in each subdivision. Denote its vertex labeled \(i\) by \(v^{(m,i)}\), where \(m\) is the subdivision index. By compactness, a subsequence of \(v^{(m,0)}\) converges to some \(x\in\Delta_d\). The mesh tends to zero, so all \(v^{(m,i)}\) converge to the same \(x\) along that subsequence. Continuity gives \(x_i\ge F_i(x)\) for every \(i\). Equality of the coordinate sums forces equality in every coordinate, proving \(F(x)=x\). Affine coordinates give the same result for every simplex.

Now equip the affine hull of \(K\) with Euclidean coordinates. For any point \(x\) in this hull, compactness gives a nearest point \(P(x)\in K\). It is unique: if distinct \(p,q\in K\) both minimized the squared distance, convexity and \[\left\|x-\frac{p+q}{2}\right\|^2 =\frac{\|x-p\|^2+\|x-q\|^2}{2} -\frac{\|p-q\|^2}{4}\] would contradict minimality. If \(p=P(x)\) and \(z\in K\), comparison with \(p+t(z-p)\), followed by division by \(t>0\) and the limit \(t\downarrow0\), yields \(\langle x-p,z-p\rangle\le0\). Apply this with \(p=P(x),z=P(y)=q\), and with \(q=P(y),z=p\). Adding the inequalities gives \[\|p-q\|^2\le\langle x-y,p-q\rangle \le\|x-y\|\,\|p-q\|.\] Thus \(\|P(x)-P(y)\|\le\|x-y\|\), so \(P\) is continuous, and \(P(x)=x\) for \(x\in K\).

If the affine hull has dimension zero, \(K\) is a singleton. Otherwise identify it with \(\mathbb R^d\), \(d\ge1\), and choose \(M>0\) so that \(K\subseteq[-M,M]^d\). The simplex \[S=\{x\in\mathbb R^d:x_j\ge-M\ (1\le j\le d),\quad \sum_{j=1}^d x_j\le dM\}\] contains that cube: its vertices are \(a=(-M,\ldots,-M)\) and \(a+2dM e_j\), \(1\le j\le d\). The continuous map \(F\circ P:S\to K\subseteq S\) has a fixed point \(x\) by the simplex case. Its image lies in \(K\), so \(x\in K\), \(P(x)=x\), and \(F(x)=x\), as required. ◻