The strong thin tree conjecture

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

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,

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

edges between its parts. Theorem 2.3 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 (4.4) 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,

For the marked changing parts, (4.5) gives

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

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,

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

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

for all sufficiently large r. If M_s=0, the assertion is immediate. This proves (4.6) simultaneously for every threshold.□

Proof of Theorem 4.1. The response supplied by Lemma 4.2 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

The denominator is positive by the open cover. The map

is a continuous self-map of the compact convex set \mathcal K. Theorem C.1 gives X_p=\Phi_p(X_p). Pass to a subsequence along which X_p\to X\in\mathcal K.

Choose

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

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

by Lemma 2.1. All remaining matrices are positive semidefinite. Hence their convex combination satisfies

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

contradicting Lemma 2.4(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.2).□

Proof. Choose orthonormal coordinates on \mathbf1^\perp and write b_e for the incidence columns in these coordinates. Denote the given trees by T_1,\ldots,T_q. For a\in\mathbb R^{E(B)}, set

Every N(a) is positive definite: the columns of T_1 are a basis and all its weights are positive. Thus h is a smooth, everywhere finite function.

Let c_t>0 be the square of the determinant of the basis of columns indexed by T_t. Cauchy–Binet, followed by the arithmetic–geometric mean inequality, gives

Here the last exponent uses the fact that the T_t partition E(B). In particular,

For \gamma>0, the function h(a)+\gamma\|a\|^2 is continuous and coercive, hence has a minimizer a^\gamma\in\mathbb R^{E(B)}. Comparison with a=0 shows that, with K=h(0)-L\geq0,

The stationarity equation supplies the equality in the second formula. Thus one may choose a finite a=a^\gamma for which every coordinate of \nabla h(a) has absolute value at most \rho/q. This remains valid when K=0, since the displayed gradient bound is then zero.

The determinant derivative formula yields

Define z_e=\exp(a_e/2)N(a)^{-1/2}b_e. Their outer products sum exactly to the identity, and the gradient bound gives their asserted norm bound. The common map N(a)^{-1/2} is invertible and every \exp(a_e/2) is positive. These operations preserve all subset ranks, including the dependencies among parallel edges.□

Proof. Fix a partition \mathcal P=\{V_1,\ldots,V_d\} into nonempty parts. Let W be the span of the z_e indexed by all edges of B whose endpoints lie in one part. The corresponding incidence vectors lie in the direct sum of the zero-sum spaces on the parts. The representation therefore gives

Let P be the orthogonal projection onto W^\perp, so that \operatorname{tr}P\geq d-1. Taking the trace after multiplication by P preserves the stated positive-semidefinite inequality: indeed, \operatorname{tr}(PQ)\geq0 for positive-semidefinite P,Q. Writing E_A(\mathcal P) for the edges of A crossing the partition, we obtain

The within-part terms vanish by the choice of P. Every partition therefore has at least \lfloor cq/(1+\rho)\rfloor(d-1) crossing edges. Theorem 2.3 completes the proof; if the floor is zero, the conclusion is immediate.□

Proof. Independently for each e, let v_e\in\mathbb R^{2D} equal (w_e,0) or (0,w_e), each with probability 1/2. Then

To make the covariance exactly isotropic, diagonalize the positive-semidefinite matrix I_{2D}-M. For each positive eigenvalue \lambda with unit eigenvector f, put m_\lambda=\lceil\lambda/\epsilon\rceil and introduce m_\lambda deterministic vectors equal to \sqrt{\lambda/m_\lambda}\,f. There are finitely many such vectors; each has squared norm at most \epsilon, and their outer products sum to I_{2D}-M. Deterministic vectors have singleton support and are independent of all other vectors. Consequently Theorem A.1 applies to the enlarged family.

In its successful outcome, let A be the indices assigned to the first block, and set S_A=\sum_{e\in A}w_ew_e^{\mathsf T}. Subtracting the fixed padding matrix from the theorem’s conclusion gives

The first block gives the upper bound in (6.1); the second block gives its lower bound.□

Proof. Write n=|V(H)|. Choose the cutoff large enough for Theorem 4.1, and also require r\geq16^{16}, so u\leq1/16. The extraction theorem supplies a positive definite matrix X with

and q edge-disjoint spanning trees all of whose edges satisfy b_e^{\mathsf T}X^{-1}b_e\leq4r^{-1/2}. Let B be precisely the union of these trees. Apply Lemma 5.1 to B with \rho=u, and put

The covariance includes cross blocks:

They need not vanish. Nevertheless, for any vectors x,y in the two coordinate spaces,

because L_B\preceq L_H\preceq X. Hence 0\preceq\Sigma\preceq2I without any invertibility assumption on \Sigma.

Since q\geq(1-u)r-1\geq r/2, and r\geq4,

Thus every w_e has squared norm at most 4r^{-1/2}+(1+u)/q\leq\epsilon. Choose the subset A\subseteq E(B) supplied by Lemma 6.1. The two principal blocks of the same inequality (6.1) give

Congruence by X^{1/2} in the second inequality yields

Testing on \mathbf1_S proves (6.3) for H'=(V,A), simultaneously for all cuts.

For the packing assertion, write the errors in terms of u:

For example, dividing by u and using \sqrt6<3 bounds the left ratio by 6(16^{-3}+16^{-7})<1/2. In particular c=1/2-\tau>0, so the first inequality in (6.5) and Lemma 5.2 give at least \lfloor(1/2-\tau)q/(1+u)\rfloor trees. The rounding margin is explicit:

where ru=r^{15/16}\geq1. Consequently

Taking floors proves (6.2).

Finally, the floor in that formula and 1/r\leq u give

Using \tau\leq u/2 once more, we obtain

which proves (6.4).□

Proof of Theorem 1.1. Choose an absolute integer r_* at least the cutoff in Proposition 6.2. For every r\ge r_*, that proposition supplies a positive integer r' satisfying

These are exactly the estimates in (6.4).

First let H_0 be any graph on at least two vertices with r_0\ge1 packed spanning trees. As long as r_i\ge r_*, apply Proposition 6.2 to obtain a subgraph H_{i+1} with at least

packed spanning trees. Stop at the first j with r_j<r_*. This happens after finitely many steps because r_{i+1}\le r_i/2. Every r_i is positive.

If j\ge1, reading the halving inequality backwards gives

Consequently

Set

For every cut S, multiplication of the step inequalities and (6.4) gives

For j=0 the same inequality holds with an empty product. All these estimates concern the same sequence of subgraphs and hold for every cut simultaneously.

Since r_j\ge1, the final graph H_j is connected. Any spanning tree T of H_j satisfies

This includes r_0<r_*: there are then zero rounds, and any spanning tree works because C_{\mathrm{it}}r_*/r_0\ge1.

Finally take H_0=G. If k\ge2, summing the cut lower bounds over a partition into d\ge2 parts shows that

Theorem 2.3 supplies \lfloor k/2\rfloor packed trees. If k=1, connectedness supplies one tree. Thus in all cases we may choose

Substitution in (7.2) proves the theorem with the universal constant

□

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

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

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

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 A.2.□

Proof. The determinant in (A.4) is stable by Lemma A.3; 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 A.2.

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

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 (A.5).□

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

For h tending to zero with fixed sign \sigma\in\{-1,1\},

coefficientwise. Every polynomial on the left is real-rooted; hence so is its nonzero limit by Lemma A.2. 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

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 A.4, 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 A.5 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 A.3, 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 (A.3), 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

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 (A.6).

Finally, direct differentiation on t\geq0 gives

Together with R(t)\geq0, these are the asserted properties.□

Proof. The polynomial q is real stable by Lemma A.3. Applying the monotonicity in Lemma A.7 successively in each coordinate, for every vector s\geq0 we have

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

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

as required.□

Proof. Let

The first polynomial is real stable by Lemma A.3, since \sum_iA_i=I_d. Moreover,

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 (A.4).

Set

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,

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 A.8 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 (A.9), the mixed polynomial is positive for every real x\geq t+\delta. It is real-rooted by Lemma A.4; hence its largest root is at most

□

Proof of Theorem A.1. Put A_i=\mathbb E[v_iv_i^*]. These matrices are Hermitian positive semidefinite, and (A.1) says that \sum_iA_i=I_d and \operatorname{tr}A_i=\mathbb E\|v_i\|^2\leq\epsilon. Lemma A.9 bounds the largest root of their mixed polynomial by (1+\sqrt\epsilon)^2. Lemma A.6 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 (A.2).□

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.

Separation in finite dimension.. We use the following elementary geometric fact: if \mathcal U is a nonempty open convex subset of a Euclidean space and a\notin\mathcal U, there is a nonzero vector v such that \langle v,x-a\rangle\geq0 for every x\in\mathcal U. Here is a proof. Choose y\in\mathcal U and put a_j=a+(a-y)/j. None of the points a_j belongs to K=\overline{\mathcal U}. Otherwise a, being a strict convex combination of y\in\mathcal U and a_j\in K, would belong to \mathcal U: an open ball about y, convexly combined with points of \mathcal U approaching a_j, gives an open ball about a in \mathcal U. Choose a nearest point z_j\in K to a_j. Such a point exists by minimizing distance on a sufficiently large closed ball. Convexity and differentiation of squared distance along the segment from z_j to any x\in K give

Hence, for v_j=(z_j-a_j)/\|z_j-a_j\|_2, \langle v_j,x-a_j\rangle\geq\|z_j-a_j\|_2\geq0. A convergent subsequence of the unit vectors v_j has a unit limit v, which has the stated property since a_j\to a.

Strong duality for this program.. Put

Each f_t is convex on D\succ0. Indeed, completing the square gives

a supremum of affine functions of D. The functions g_S are affine. Choose

Then all cut constraints are strict at D_0. In particular 0\leq p_*<\infty.

Consider the open convex set of vectors (a,b,s) for which there are D\succ0 and r\in\mathbb R such that

The point (0,0,p_*) is outside this set, since membership would give a feasible D with every f_t(D)<p_*. The separation fact just proved therefore supplies nonzero coefficients (\lambda,y,\alpha) such that

throughout the set. Each coefficient is nonnegative, because any one coordinate of a point in the set can be increased arbitrarily. Moreover \alpha>0. To see this, choose r_0>\max_t f_t(D_0); there is then a point of the set with all the a_t and b_S negative. If \alpha=0, this would contradict the separation inequality and the nonzero, nonnegative vector (\lambda,y). Normalize \alpha=1 and take limits down to the displayed strict inequalities. For every D\succ0 and every r\in\mathbb R this gives

Since r is unrestricted, \sum_t\lambda_t=1.

For any nonnegative \lambda with this sum and any y\geq0, weak duality gives the reverse bound: at a feasible D, the weighted objective plus the weighted constraint residuals is at most \max_t f_t(D). Consequently, writing

we have proved

This argument neither assumes attainment of the primal infimum nor requires a uniform positive lower bound on the eigenvalues of its feasible matrices.

The matrix infimum, including singular matrices.. For any symmetric positive semidefinite A,Z, we claim that

First suppose A,Z\succ0, and set H=Z^{1/2}DZ^{1/2} and C=Z^{1/2}AZ^{1/2}. The difference between the left-hand objective and 2\operatorname{tr}(C^{1/2}) equals

It is zero when H=C^{1/2}, proving the identity in this case. For general A,Z\succeq0, replace them temporarily by A_\varepsilon=A+\varepsilon I and Z_\varepsilon=Z+\varepsilon I. The positive definite identity, applied at any fixed D, and then continuity of positive semidefinite square roots give the lower bound in (B.5) as \varepsilon\downarrow0. Conversely, the unperturbed objective is at most the perturbed objective at every D, so its infimum is at most the known perturbed infimum. Letting \varepsilon\downarrow0 gives the upper bound. Continuity here also follows directly from the spectral theorem: along a convergent sequence of positive semidefinite matrices their square roots are bounded, and every convergent subsequence of these square roots has the unique positive semidefinite square root of the limit as its limit. These perturbations prove an auxiliary matrix identity; they do not change the allowed dual multipliers.

For fixed \lambda,y, abbreviate the trace of the square root in (B.5) by N(\lambda,y). If y\ne0, then d(y)>0. Scaling y by s\geq0 changes the dual value to 2\sqrt{s}\,N(\lambda,y)-s\,d(y), whose supremum over s\geq0 is N(\lambda,y)^2/d(y). The case y=0 contributes zero. Thus (B.4) becomes

From weighted cuts to binary coordinates.. Let W=W(\lambda) be the diagonal E\times E matrix with entries

Then A(\lambda)=BW^2B^{\mathsf T}. If a matrix Y has rows \sqrt{y_S}\,\mathbf1_S^{\mathsf T}, then Y^{\mathsf T}Y=Z(y). The matrices Z(y)^{1/2}A(\lambda)Z(y)^{1/2} and WB^{\mathsf T}Z(y)BW have the same nonzero eigenvalues: they are the two products TT^{\mathsf T} and T^{\mathsf T}T with T=Z(y)^{1/2}BW. It follows that

where \|M\|_* denotes the sum of the singular values of M.

For fixed \lambda, the ratio in (B.6) is continuous in y\geq0, y\ne0. Approximate y by nonzero nonnegative rational vectors. For rational y, choose a positive integer q with every qy_S integral and form a binary matrix X by repeating the row \mathbf1_S^{\mathsf T} exactly qy_S times. Then X^{\mathsf T}X=qZ(y), and both the squared numerator and the denominator in the ratio acquire the same factor q. Conversely, any binary X gives integral cut multiplicities after its constant rows are discarded. Constant rows contribute zero to XB, so they have no effect on the ratio. Adding zero rows permits h\geq m. These observations prove the exact identity

The limiting argument takes a supremum over all finite dimensions; it asserts no exact finite binary representation for irrational cut weights.

Orthonormal edge vectors and the factor two.. For any h\times m matrix M with h\geq m, singular-value decomposition gives

Indeed, write M=P\Sigma V^{\mathsf T} with P^{\mathsf T}P=I_m, V orthogonal, and \Sigma diagonal nonnegative; zero singular values can be included by completing the columns of P. For any admissible U, each diagonal entry of V^{\mathsf T}UP is at most one, giving the upper bound \operatorname{tr}(UM)\leq\operatorname{tr}(\Sigma). The choice U=VP^{\mathsf T} attains it.

Write a_e=\langle u_e,Xb_e\rangle. Individual rows of U can be multiplied by -1 while preserving UU^{\mathsf T}=I_m. Consequently, when taking either the supremum in (B.2) or the supremum of the squared trace in (B.9), we may restrict to a_e\geq0 for all e: replacing a_e by |a_e| cannot decrease either expression. Equation (B.8) therefore says

with the other conditions on X,U,\lambda as above.

Every edge belongs to at most two parent boundaries O(t): if its endpoints have lowest common ancestor s, only the two children of s containing its respective endpoints can have that edge in their parent boundary. Restricting to marked nodes preserves this property. Hence, on putting

the elementary inequalities between the Euclidean norm and the sum of at most two nonnegative numbers give w_e\leq v_e\leq\sqrt2\,w_e. Because a_e\geq0,

For fixed X,U, let

Then \sum_e v_ea_e=\sum_t\sqrt{\lambda_t}\,c_t. Cauchy–Schwarz, with equality at \lambda_t=c_t^2/\sum_s c_s^2 when the denominator is nonzero, shows that

The identity is also valid when all c_t vanish. Taking suprema in (B.11) and using (B.10) proves p_*\leq Q_*\leq2p_*. Finally, if Q_*\leq K, the defining property of the finite infimum p_* supplies a feasible D\succ0 whose maximum marked average is less than p_*+\eta\leq K+\eta.□

Proof. The scalar Cauchy–Schwarz inequality gives

The last quantity is positive, so the assumption implies a\le1.

The matrix estimate. Let P_F:\R^E\to\R^F be coordinate restriction, and form the m-by-m matrix A whose column indexed by e\in F is P_FY_e. Set \tau=m\sqrt\Upsilon. The singular values \sigma_1\ge\cdots\ge\sigma_m\ge0 of A satisfy

Indeed, writing a singular value decomposition as A=\sum_i\sigma_i u_i v_i^{\mathsf T}, the trace is \sum_i\sigma_i\langle u_i,v_i\rangle, whose absolute value is at most \sum_i\sigma_i. The Frobenius norm identity follows from orthonormality, and its upper bound follows from (B.12) and the fact that coordinate restriction does not increase a vector’s norm.

We will also use the following rank approximation inequality: for 0\le k\le m and any matrix C of rank at most k,

For completeness, let Q be orthogonal projection onto the column space of C. Since (I-Q)C=0, orthogonal projection and the singular value decomposition give

The numbers w_i=\|Qu_i\|_2^2 lie in [0,1], and \sum_iw_i=\rank Q\le k. Because the \sigma_i^2 are nonincreasing, \sum_i\sigma_i^2w_i\le\sum_{i=1}^k\sigma_i^2: moving available weight from a later index to an earlier index never decreases this weighted sum, and its maximum therefore puts weight one on the first k indices. This proves (B.17), including k=0.

Selecting a singular-value tail. Define

We have 1\le p_0\le m. By (B.16),

The sum is zero when p_0=1, so this also covers arbitrarily small am. It follows that

Partition the integer interval [p_0,m] into the nonempty blocks

where

For the first index p=2^jp_0 of a block, its cardinality is at most p. Cauchy–Schwarz therefore gives

Summing this inequality and using (B.18), one of these first indices p satisfies

Selecting the balls at an explicit radius. Fix the positive number

Scan the endpoint images of edges in F, keeping a point precisely when its distance from every previously kept point is greater than 2\sqrt r. This finite procedure produces centers Y_{w_1},\ldots,Y_{w_b} for pairwise disjoint closed balls of squared radius r. Its maximality also ensures that each endpoint image Y_v lies within distance 2\sqrt r of one of the centers; choose such a center and call its vertex c(v).

If b\le p, define a matrix C by

Every column of C belongs to the span of P_F(Y_{w_j}-Y_{w_1}), 2\le j\le b, so \rank C\le b-1\le p-1. On the other hand,

This contradicts (B.17) with k=p-1, which bounds the same quantity below by T_p>0. Thus b\ge p+1\ge2. Combining (B.19) and (B.20) yields

The bound on L proves (B.13).

Conversion to the power bound. Put t=\log(1/a)\ge0. Since \log2\ge1/2, 5+\log_2(1/a)\le5+2t. The elementary maximum of t e^{-\varepsilon t/2} is 2/(e\varepsilon)\le1/\varepsilon, and 5\le5/(3\varepsilon) for 0<\varepsilon<1/3. Consequently,

Squaring and substituting in (B.13) gives

Finally C_1(\varepsilon)\ge16, so the count estimate in (B.15) follows as well.□

Proof. Fix the node, let m=|O(t)|, and let expectations be uniform on O(t). Writing \mu=\mathbb E a_e>0, badness says \mathbb E d_e\le\mu^2/\alpha. Discard edges for which a_e<\mu/4 or d_e>16\mu^2/\alpha^2. The first class contributes at most \mu/4 to \mathbb E a_e. For the second class, Markov’s inequality gives probability at most \alpha/16, and therefore Cauchy–Schwarz and a_e^2\le d_e give

The remaining edges contribute at least m\mu/2 to the boundary sum. On those edges both a_e^2 and d_e lie in [\mu^2/16,16\mu^2/\alpha^2]. Divide this interval into half-open dyadic intervals, with an extra last interval if needed. There are at most J choices for each quantity and at most J^2 pairs of choices. Some pair contains edges whose a_e sum is at least m\mu/(2J^2). Its edges are 2-homogeneous, and squaring this last estimate gives the asserted dominance.□

Proof. Set m_t=|O(t)|, m'_t=|O'(t)|, N=\sum_{t\in T}m_t, N'=|F|, and c_2=\max_{e\in F}d_e. The sets O'(t) are nonempty. Homogeneity, dominance, and badness imply, for each t,

Cancel m'_t and sum. Since \sum_t m'_t\le2N', we obtain

Also N\ge N' and c_1\le c_2, since a_e^2\le d_e. Consequently

Let Y_v=UX_v. The row-e coordinate of Y_u-Y_v is a_e. Moreover \|Y_u-Y_v\|_2^2\le d_e, so

Lemma B.3 yields b disjoint Euclidean balls with squared radius r and centers at endpoint images Y_v, with

Their center distances squared are at least 4r. Contraction and the binary-coordinate identity therefore give \|X_u-X_v\|_1\ge4r for distinct selected centers. Thus the corresponding Q-balls of radius r are disjoint. Shrink their common radius to \delta so that

Call this family of b small balls \mathcal A. There are at most 2N' distinct endpoint centers. It follows that

As \epsilon<1/2, condition (B.21) implies s^{1-\epsilon}\le s^\epsilon\le1/(2C); hence

Finally, homogeneity and the multiplicity bound show

Let V'(t) consist of the endpoints of O'(t) that lie in V(t), and let V'=\bigcup_tV'(t). Define D=\max\{\delta,2c_2\}. Choose a maximal disjoint collection \mathcal B of radius-D balls centered at X_u for u\in V'. Every such center is within 2D of a chosen center: otherwise its ball could be added. Each center of a small ball is an endpoint of an edge of F, so it is within c_2 of a point of V', and hence within 3D of a chosen center.

If |\mathcal B|<w/(12\beta D), assign every small ball to its closest chosen center, breaking ties consistently. The balls assigned to one center have center diameter at most 6D. Keep a resulting bag precisely when it contains at least 6\beta D/\delta balls. The discarded bags contain fewer than |\mathcal B|6\beta D/\delta<b/2 balls. Each retained bag is \beta-compact of type (\delta,6D); the numerical threshold is larger than 2 because D\ge\delta and \beta>1. Their balls are still mutually disjoint and their mass is at least w/2, which implies (B.22).

In the other case, |\mathcal B|\ge w/(12\beta D), assign each ball of \mathcal B to one node t for which its center belongs to V'(t). Keep the bag assigned to t when

Discarding the other bags loses fewer than |\mathcal B|/2 balls. For each retained ball its center is in V(t) and some edge of O'(t) has length at most c_2<D. Furthermore

If D=\delta, the right side is b/(24\beta N), at least s/(24\beta C) by the bound on b. If D=2c_2, it is at least s^{1+\epsilon}/(48\beta C) by (B.23) and (B.24). In either case (B.21) makes it at least s^{1+2\epsilon}. These bags are therefore assigned as asserted. Their mass is at least D|\mathcal B|/2\ge w/(24\beta); (B.26) gives (B.22).

In both cases (B.23) gives c_2\le c_1/s and therefore D\le2c_1/s. Together with (B.25), this places all radii, and the compact diameter 6D, in [sc_1,12c_1/s].□

Proof. Lemma B.5 gives 2-homogeneous subsets O'(t) with \gamma=1/(4J^4)=32/C_2(\alpha). Define

All are positive. For m=|O(t)| and m'=|O'(t)|, the same pointwise argument used above, now with 2-homogeneity, gives

Consequently

Partition the nodes according to the two integers n=\lfloor\log_2 A_t\rfloor and m=\lfloor\log_2 B_t\rfloor. For each fixed n, (B.29) allows at most L values of m. Retain the value m(n) maximizing the sum of the s_t over that group, and call the resulting node set T_n. Summing over n yields

The last inequality uses \gamma\ge1/C_2(\alpha).

The union of the O'(t) over T_n is 4-homogeneous: its a_e^2 lie in [2^n,2^{n+2}) and its d_e in [2^{m(n)},2^{m(n)+2}). Apply Lemma B.6 to every nonempty T_n. Let \mathcal F_n be the resulting family. Its radius is at least s2^n and at most 24\,2^n/s; the latter upper bound also holds for its compact diameter parameter. Its mass is at least s^\epsilon\sum_{t\in T_n}s_t/(192\beta C_1(\epsilon)).

Partition these families by their integer n modulo H and by whether they are compact or assigned. One of the 2H resulting classes has at least 1/(2H) of their total mass. Order that class by decreasing n. If n' follows n, then n'\le n-H, and the definition of H implies

This verifies the geometric condition, including the stronger diameter condition for compact families. Assigned nodes are distinct across the sequence because the original T_n are disjoint and each construction uses only a subset of its own T_n. Finally combine its 1/(2H) mass share with (B.30) and the mass guarantee for each \mathcal F_n. This is exactly (B.28).□

Proof. For H\in\mathcal Z, clamp the radial distance to its radial interval:

For every a_H<t<b_H, the set S_{H,t}=\{v:\|X_v-x_H\|_1<t\} is nonempty and proper, by (B.32). Its edge boundary therefore has at least k edges, with multiplicity. Integrating this finite step function gives

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

This also handles a segment lying along a shell boundary: its clamped radial function is constant there. Summing (B.34) over H and then applying the last bound to each edge proves (B.33).□

Proof of Proposition B.8. 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

The invariant and the order of processing.. We construct a finite collection \mathcal Z, initially empty, and process the families in the order 1,\ldots,q. During phase i, call an original ball inserted from \mathcal F_i fresh. Every other live object is called old, including any shell produced by splitting an old object during this phase. A fresh ball is kept intact until the phase ends. Write [s]_+=\max\{s,0\}. Assign capacities

where w(H) denotes width. All capacities are nonnegative and at most the object’s width. At every step we maintain:

1. (i)

   the live objects are pairwise disjoint;

2. (ii)

   their centers are embedded vertices, and every live object has the two witnesses in (B.32);

3. (iii)
   P_i(\mathcal Z)\ge \frac14\sum_{D\text{ already processed}}|D|\delta(D), \tag{B.37}

   where \delta(D) is the radius of the balls of D.

These assertions hold initially. We verify them for each operation and for each change of phase.

Processing a bag with an interior ball.. For an unprocessed ball B_Q(z,\delta_i) and a live object H with center x and numerical radii a,b, say that the ball is interior to H if

An interior ball is contained in H, by the triangle inequality. It is nonempty, so disjointness of \mathcal Z makes its containing object unique. Moreover, this object cannot be fresh: an unprocessed ball and a fresh ball belong to the same family, whose balls are disjoint.

While some unprocessed bag has an interior ball, choose such a bag D=\{B_Q(z_j,\delta_i):1\le j\le n\}. Let H be the old object containing an interior ball of D, and set

The function z\mapsto\|z-x\|_1 is 1-Lipschitz. The diameter bound on the centers, applied first to the interior center and then to the extremal pair, gives

Thus every ball of D lies in H. Replace H by the two old shells

discarding any zero-width shell, and insert all n balls of D as fresh balls. Mark D processed.

Here are the geometric invariant checks. The shells in (B.40) are subsets of H and are disjoint from each other. For y\in B_Q(z_j,\delta_i), strictness of the ordinary ball gives

It therefore lies in neither shell. The inserted balls are mutually disjoint by the family assumption; all replacements are subsets of H, so they also avoid every other live object. For H_-, an old inner witness remains an inner witness, and a center achieving L is an outer witness. For H_+, a center achieving R is an inner witness, and an old outer witness remains an outer witness. Every inserted ordinary ball has its own center as inner witness and the center of another ball of D as outer witness; their distance is at least 2\delta_i. All centers of new objects are either x or a z_j, hence are embedded vertices. This proves (i) and (ii), and also proves that fresh objects have not been altered.

For the potential calculation, write w=b-a and t=[w-6\Delta_i]_+, the old capacity being replaced. The new ordinary balls have total capacity n(\delta_i-6\Delta_{i+1})\ge n\delta_i/2. If t=0, they alone pay the new requirement n\delta_i/4, and no previous capacity is lost. If t>0, then t=w-6\Delta_i. The widths of the two shells sum to w-(R-L)-2\delta_i, including zero-width shells formally, so

The first bound uses [s]_+\ge s, also when a shell is discarded. The second uses R-L\le\Delta_i and 2\delta_i\le\Delta_i. The last uses n\delta_i\ge \beta\Delta_i and \beta\ge36\ge32. Unchanged objects keep their capacities. Thus (iii) also survives, with the new bag included on its right-hand side. Each such operation processes one new bag, so the loop ends after finitely many steps.

Inserting the remaining bags and changing scale.. At the end of the loop, let \mathcal R_i be the unprocessed bags. None of their balls satisfies (B.38) for any live object. Set s_i=2\delta_i+\Delta_i. Retain every fresh ball. For each old object with numerical radii a,b, replace it by

and otherwise discard it. Insert every ball of every bag in \mathcal R_i, and mark those bags processed. We now regard all surviving objects as old objects at the beginning of phase i+1. After phase q, this is just a final accounting state with \Delta_{q+1}=0 and capacity equal to width.

Shrinking preserves pairwise disjointness among old objects and preserves their witnesses: increasing the inner radius and decreasing the outer radius only weakens the witness conditions. A remaining ball B_Q(z,\delta_i) is disjoint from each retained fresh ball, because both belong to \mathcal F_i. For an old object, failure of (B.38) says that at least one of

holds. In the first case every point of B_Q(z,\delta_i) has radial distance less than a+s_i; in the second every such point has radial distance greater than b-s_i. In either case this ball avoids H^{\mathrm{sh}}. All newly inserted balls are mutually disjoint by the family assumption, and their witnesses are again their own centers and another center in the same bag. This verifies (i) and (ii) after the transition, including the center condition.

It remains to verify (iii) across the change in its definition of capacity. A retained fresh ball has capacity \delta_i-6\Delta_{i+1} both before and after the transition. For a surviving old object, the new capacity is [ w-2s_i-6\Delta_{i+1}]_+. By (B.35),

Thus its new capacity is at least [w-6\Delta_i]_+, its old capacity. If an old object is discarded, then w\le2s_i\le4\Delta_i, so its old capacity was zero. Finally, every ball inserted from \mathcal R_i contributes \delta_i-6\Delta_{i+1}\ge\delta_i/2 in the new state. These capacities pay at least |D|\delta_i/4 for each newly processed bag D. No previous capacity decreases, so (B.37) holds at the start of the next phase.

After phase q, every bag in the chosen initial sequence has been processed and the capacity of each live object equals its width. The final collection \mathcal Z_{\mathrm{fin}} is disjoint and has both witnesses for every object. The potential invariant and Lemma B.9 give

For a countable sequence, its nonnegative sum is the supremum of these finite initial sums. Taking that supremum proves (B.31).□

Proof. Give each edge an arbitrary orientation and maintain an integral antisymmetric flow whose value on an oriented edge is in \{-1,0,1\}. Start with zero flow. A directed traversal of an edge is available when its signed flow in that direction is less than 1. As long as the current flow value is less than q, augment by one along an available directed u–v path if one exists. The edge bounds and flow conservation at all other vertices remain valid, and the value increases by one. If no such path exists, let S be the vertices reachable from u by available traversals. Then v\notin S, and every edge leaving S has signed outward flow 1. Summing flow conservation over S says that the current flow value equals the number of those edges, at least q, a contradiction. Thus the procedure reaches value q after q augmentations. An integral flow of positive value contains a directed positive-flow u–v path: otherwise the vertices reachable on positive-flow edges would have no positive outward flow, contradicting their positive net flow. Extract such a path and subtract one on its edges. Repeating extracts q paths. Each used edge had flow 1 in its traversal direction and then has flow zero, so the extracted paths are edge-disjoint. Parallel edges are separate edges throughout the argument.□

Proof. The set being counted is empty for i\le\ell. For each i>\ell, assign to every counted ball one endpoint of an edge in P(s) that lies in that ball. Pairwise disjointness of the center-inclusive balls in \mathcal B_i makes this assignment injective on endpoint vertices. There are at most 2|P(s)| such vertices, even when edges are parallel or several vertices have the same image. Thus the left-hand side is at most

The last inequality is precisely the assigned-bag cardinality bound.□

Proof. Realize each graph edge e=\{v,w\} by one fixed straight segment from X_v to X_w in Q, of length \ell_e=\|X_v-X_w\|_1. Different parallel edges are distinct resources even if their segments coincide geometrically. Concatenating these segments realizes a graph path as a continuous curve.

Fix a record B with center x and radii a<b. Take the paths in (L3), and stop each at its first vertex z satisfying \|x-X_z\|_1\ge b. Every vertex in each resulting graph path belongs to L(B). Avoidance of V(t_d(B)) already follows from (L3). To check avoidance of V(s) for s\in t_P(B), suppose the path first enters V(s) along \{v,w\}\in P(s). The start vertex is outside V(s), so this entering edge exists. Its preceding endpoint v occurs before the stopping vertex and therefore has \|x-X_v\|_1<b. This contradicts (L2). In particular, both graph endpoints of every edge of the stopped path are in L(B), including the edge containing its geometric exit point.

On each of the resulting continuous curves, keep the portion between the last point at radius a preceding its first point at radius b and that first point at radius b. Those points exist by continuity. The retained curve, apart from its endpoints, is in the open shell a<\|x-y\|_1<b. The function y\mapsto\|x-y\|_1 is 1-Lipschitz, so its length is at least b-a. This also applies to an ordinary ball by taking a=0; removing its center changes no charged length. Charge each retained portion to its underlying graph edge. The paths for one record are edge-disjoint, so this record charges no portion of a graph edge twice.

Now fix a graph edge e=\{v,w\}. If two distinct records charge portions of e, the preceding paragraph gives v,w\in L(B)\cap L(B'), so their conflict domains meet. Condition (L4) forces their geometric balls to be disjoint. Hence their charged open portions of the fixed segment of e are disjoint. Summing over all records charges e at most \ell_e. This reasoning uses edge portions, not the whole length of every edge on a witness path. It also handles zero-length edges, which contribute no charge. Each record receives at least (k/4)(b-a), and summing the edge budgets proves the claim.□

Reduction of Proposition B.10 to Lemma B.15. Let M=\sum_i\delta_i\sum_{t\in T_i}|\operatorname{Bag}_t| be the original total radius. A ball can be noninsertable by several predecessors; summing Lemma B.13 over all selected nodes therefore bounds the total radius N of noninsertable balls from above, without needing a unique predecessor charge:

Here the original 24C_3/k assignment implies the weaker assignment needed in that lemma, and the displayed condition on C_3 implies C_3\ge16.

Delete all noninsertable balls. If a bag retains at least half its original balls, keep the remaining bag; otherwise delete the bag and its node from the corresponding T_i. A kept bag is 12C_3/k-assigned. In a deleted bag more than half the original balls were noninsertable, so its entire radius is at most twice its noninsertable radius. The same upper bound holds for the radius removed from a kept bag. The resulting sequence consequently has total radius

Discard empty families, retaining the remaining scales in their original order. The sequence retains disjointness at each scale and the geometric scale condition. Deleting selected nodes can only remove predecessors, so all surviving balls are still insertable after recomputing their labels. The hypotheses of Lemma B.15 therefore hold. Combining that lemma with Lemma B.14 gives

as required.□

Proof. The definition gives (L1), and insertability says exactly that every endpoint in (L2) has distance at least \delta_i from X_u. We have already proved that u\in L(B). Every selected node is nonroot, so |O(t)|\ge k by the cut bound in its parent’s induced graph. Moreover, |\operatorname{Bag}_t|\ge12C_3|O(t)|/k\ge12C_3>1. Choose another ball in the bag, with center vertex w\in V(t). Disjointness of the two open balls gives X_w\notin B, so \|X_u-X_w\|_1\ge\delta_i. Since G[V(t)] is k-edge-connected, Lemma B.11 supplies k pairwise edge-disjoint u–w paths in this induced graph. These witness (L3), with inner radius zero, and in fact give the stronger count k in place of k/4.□

Proof. Two rooted connected subtrees which intersect have comparable roots. Every current owner belongs either to an earlier family or to a bag already reached in this phase. An owner in T_\ell cannot be a proper descendant of t, by the depth order. Suppose an owner s\in T_i, i<\ell, were a proper descendant of t. Then s\in\operatorname{Pred}(t)=t_P(A). The whole subtree of s, and hence C(B), would be disjoint from C(A). This is a contradiction. The roots are therefore ordered with t(B) above t. Connectedness of C(B) shows that the path from its root to any common node passes through t, proving t\in C(B).□

Proof. If both conflict intersections were nonempty, Lemma B.17 would give t\in C(B)\cap C(D). This violates condition (L4) for the intersecting records B,D. If A were interior to both, the two records would intersect on the nonempty support of A, giving the same contradiction.□

Proof. An intersection of B' with D is also an intersection of B with D, and its conflict intersection is a subset of C(B)\cap C(D). For a concentric restriction, predecessor endpoints remain outside the smaller outer radius. The old inner witness still has distance at most the new inner radius, and the old crossing paths also cross the restricted radial interval. The labels and their induced vertex domains are unchanged.□

Proof. Consider any single operation before the final phase transition. A newly inserted original ball has radius \delta_\ell and cannot contain a candidate with the two radial margins in (B.48), since C_3>1. Every other new record is a concentric radial restriction of an old record, with a subset of its conflict domain. If a candidate satisfies (B.48) for that new record, it therefore satisfies it for the old record as well. Unchanged records create no new interiors. Iterating this observation proves the claim.□

Proof. We maintain actual allocations of the potentials, so that an operation must preserve all amounts already allocated. If an old record B is removed, it suffices to set aside at least \operatorname{tok}_\ell(B) from its replacements: those funds can then be distributed exactly as the old potential was. Any additional funds assigned to t increase its allocation. Untouched records retain their allocations.

Shrinking a record about its existing center and retaining its labels preserves all its individual validity conditions. Indeed, its old inner witness remains inside the new inner radius, its old crossing paths still cross the smaller radial interval, and all excluded boundary endpoints remain beyond the new outer radius. Pairwise validity is inherited by Lemma B.19. These observations apply to every residual shell below. Original current-family balls are never carved: their width is \delta, whereas a record containing an interior ball must have width greater than 2C_3\delta.

Operation 1: carving an avoiding shell.. If some A=B(X_u,\delta)\in\operatorname{Int}_t lies in an avoiding shell B=B(x,r_1\Vert r_2), put q=\|X_u-x\|_1 and replace B by

both with the labels of B. Insert the original ball A, with its original labels, and treat it. The two residual shells are disjoint from A. The original ball satisfies its individual validity conditions, and Lemma B.18 shows that its labels are compatible with every other existing record. This proves validity of the new arrangement.

Write R=r_2-r_1. Since R>2C_3\delta, the old potential is (R-C_4\delta)/(2(C_4+2)). Give B all the potentials of B_1,B_2 and \delta/2 from A. Positive parts can only increase the following lower bound:

The remaining potential of A is at least

Give it to t. Thus treating this one ball preserves every old allocation and increases the allocation to t by the required amount.

The common setup for operations 2 and 3.. Suppose no ball of \operatorname{Int}_t is interior to an avoiding shell. Write t^* for the parent of t. If enough interior centers lie near a short radial interval, inserting their balls will pay for the width removed from the old record. When the interval is long compared with their total radius, we instead create two overlapping central shells with crossing paths in G[V(t)] and G[V(t^*)\setminus V(t)], respectively. Local connectivity supplies the first set of paths; the decomposition below supplies the second. Define

Partition V(H) into sets S_1,\ldots,S_j whose induced graphs are k/4-edge-connected, by repeatedly splitting a part along a cut of size less than k/4 until no such cut remains. Singleton parts are allowed. There are j-1 splits, and each edge between final parts is counted at precisely the split that first separates its endpoints. Consequently

and the sum is zero when j=1. Each S_i is a nonempty proper subset of V(t^*), so the k-edge-connectivity of G[V(t^*)] gives

In particular,

This proves the decomposition estimate directly, including when H is disconnected and without assuming that k/4 is an integer.

Let U be the centers, identified with vertices, of the balls still in \operatorname{Int}_t, and set

The definition of an assigned bag ensures \bigcup_iU_i=U. By the loop condition and the 12C_3/k assignment bound,

Choose i with |U_i| maximal. Even if the sets U_i overlap, their union bound and (B.53) imply

Choose a nonavoiding record B with center x and numerical radii r_1<r_2, containing in its interior a ball with center u_0\in U_i. Such a record exists because every ball still under consideration is interior and operation 1 is unavailable. Write \rho(z)=\|X_z-x\|_1 and put

The neighbor of u_0 in V_i has radius strictly between r_1+(C_3-1)\delta and r_2-(C_3-1)\delta. In particular a\leq b. Define

The set \mathcal A is nonempty, since it contains the ball centered at u_0.

Every ball A\in\mathcal A is in the interior of B. To check this carefully, the radial inequalities defining \mathcal A imply that A meets the support of B: its center is less than \delta in radial distance from [r_1,r_2]. This assertion also holds for supports restricted to the cube. To decrease radius, move towards the binary center x; to increase it, move towards the opposite cube vertex. Along either segment, the change of radius equals the distance moved. Since B is nonempty, one can therefore reach a point of B within distance strictly less than \delta. All balls of \operatorname{Bag}_t have the same labels, so C(A) intersects C(B). Also A is interior to some existing record B'. If B'\ne B, then B meets B' at a point of A, since the interior margin implies A\subseteq B'. Lemma B.18 contradicts C(A)\cap C(B)\ne\varnothing. Therefore B'=B, as claimed.

We need one more radial estimate:

If every v\in V_i had r_1<\rho(v)<r_2, then all their radii would lie in [a,b]. Each u\in U_i has a neighbor v\in V_i with |\rho(u)-\rho(v)|<\delta, so it would lie in U_{\mathcal A}. Hence the premise of (B.56) supplies some v\in V_i with \rho(v)\geq r_2 or \rho(v)\leq r_1. Let w\in V_i be a neighbor of the chosen interior center u_0. If \rho(v)\geq r_2, then b=r_2, while

If \rho(v)\leq r_1, then a=r_1, while

These prove both cases of (B.56).

Operation 2: a dense group in the radial interval.. Suppose m\delta>3L. Replace B by

with its labels, and insert all m original balls of \mathcal A, with their original labels. Treat these m balls. Their supports are disjoint from B_1,B_2 because their centers have radii strictly between a-\delta and b+\delta. They are pairwise disjoint as members of the same family. We proved that each lies in the interior of B, so Lemma B.18 makes each compatible with every old record other than B. Their individual conditions follow from insertability. Residual shells inherit validity, proving that the whole replacement is valid.

The number treated is large. If U_i\subseteq U_{\mathcal A}, then (B.54) gives m\geq3C_3. Otherwise, (B.56) and m\delta>3L give

Allocate to B all the potential of B_1,B_2 and three quarters of the potential of each newly inserted ball. Writing R=r_2-r_1, the old potential is R-C_4\delta; it is positive because B contains an interior ball. Even if a residual shell is empty, its potential is at least its formal width minus C_4\delta. Therefore

The successive estimates use (B.51), L<m\delta/3, (B.57), and (B.49). Each inserted ball retains at least (1/4)(5/6)\delta=5\delta/24\geq\theta\delta to give to t. Thus this operation supplies at least \theta m\delta new credit.

Operation 3: a sparse group in the radial interval.. Suppose m\delta\leq3L. We first record that

If U_i\not\subseteq U_{\mathcal A} this follows from (B.56); otherwise L\geq m\delta/3\geq|U_i|\delta/3\geq C_3\delta. In particular, all the central shells defined next have positive width.

Replace B by the two residual shells

with its labels. Insert two additional shells

The shell B_3 is nonavoiding and B_4 is avoiding. Give them labels

Treat all the balls of \mathcal A, removing them from \operatorname{Int}_t without inserting them.

We verify every new labeling condition. Lemma B.17 implies that t(B) is a weak ancestor of t and that t\in C(B). In fact t(B)\ne t. An original ball with owner t cannot meet an unprocessed ball of the same family, since that family is disjoint. A synthetic shell with owner t could only have been created by an earlier occurrence of this operation while processing this very bag: the sets T_i are disjoint, and new nonavoiding owners are assigned only to the node being processed. At that earlier occurrence every remaining interior ball meeting the new central shell was in its expanded radial interval and was treated. Subsequent changes only restrict that shell, and Lemma B.20 prohibits the return of a border ball to the interior set. Hence neither that shell nor any of its residual pieces can now contain an unprocessed interior ball. This proves t(B)\ne t. Thus t is a proper descendant of t(B), as required for B_4 to be avoiding.

Using \mathcal T[t] for the subtree rooted at t, the labels give

Indeed, no member of t_P(B) is a weak ancestor of t, since t\in C(B); every remaining excluded subtree either lies below t or is disjoint from its subtree. Both new conflict domains have the prescribed connected form and are subsets of C(B). All four shells are subsets of B. The pairwise validity with old records follows from Lemma B.19; the residual shells are disjoint from the central shells, and (B.60) proves validity of the overlapping pair B_3,B_4. Finally, both new excluded-node sets are subsets of t_P(B) and both new outer radii are at most r_2. Thus the excluded-boundary-endpoint condition is preserved.

It remains to prove the crossing-path condition, which does not follow merely from shrinking the geometric support when labels change. Choose vertices v_1,v_2\in V_i minimizing and maximizing \rho, and choose their respective neighbors u_1,u_2\in U_i along edges of O'(t). Clipping in (B.55) gives

By (B.58), a+\delta<b\leq r_2. Hence \rho(u_1)<r_2 and \rho(v_1)<r_2; these strict inequalities will exclude membership in the forbidden subtrees.

For B_3, the k-edge-connectivity of G[V(t)] and Lemma B.11 supply k edge-disjoint u_1–u_2 paths. The radial inequalities show that each crosses B_3. To see that the initial vertex is in C(B_3), fix z\in t_P(B_3). If u_1\in V(z), the edge \{u_1,v_1\}\in O'(t) would belong to P(z) because z is below t and v_1\notin V(t). This contradicts the endpoint condition of B, since z\in t_P(B) but \rho(u_1)<r_2. Thus u_1 avoids every excluded subtree and lies in C(B_3). These paths and this initial vertex prove the required crossing condition for B_3.

For B_4, every cut separating v_1 from v_2 in G[S_i] has at least \lceil k/4\rceil edges. Lemma B.11 therefore supplies at least k/4 edge-disjoint v_1–v_2 paths. Since t(B) is a proper ancestor of t, V(t^*)\subseteq V(t(B)). The paths therefore lie in V(t(B))\setminus V(t) and cross B_4. Fix z\in t_P(B_4). The edge \{u_1,v_1\} cannot belong to P(z) because \rho(v_1)<r_2. If v_1\in V(z), it follows that u_1\in V(z) also. A hierarchy set containing both u_1\in V(t) and v_1\notin V(t) must be a proper ancestor of t, by laminarity. This would make z a weak ancestor of t, contrary to t\in C(B). Hence v_1 lies in none of the excluded subtrees; also v_1\notin V(t), so v_1\in C(B_4). This verifies the crossing condition for B_4 and completes the proof of validity.

For later use, every still-unprocessed interior ball is disjoint from B_3 and B_4: its center is outside the expanded interval (a-\delta,b+\delta). Such a ball can remain interior to B_1 or B_2, which is harmless. This establishes the property of new central shells used above to prove that t(B) is a proper ancestor.

We now distribute the new potentials. The shell B_3, although created in the current phase, is not an original current-family ball; it uses the second line of (B.50). Give B all the potential of B_1,B_2,B_3 and (2C_4+2)\delta from B_4. The sum of the three formal nonavoiding widths is R-2\delta, where R=r_2-r_1. Consequently

The following estimate proves both that B_4 has the amount just promised and that it can additionally pay for all m treated balls:

The first equality is valid because (B.58) makes L-C_4\delta positive. The other steps use C_4+1\leq C_4+2, (B.49), (B.58), the case assumption m\delta\leq3L, and C_3\geq2C_4(C_4+2), respectively. Give the remaining amount to t. This completes the allocation for operation 3.

Each operation treats at least one interior ball, preserves all old allocations, and gives t at least \theta\delta for each ball it treats. Border transfers change neither this count nor any allocation. Induction on the number of operations proves the stated bound for t, and induction on the bags already processed in the phase proves the bounds for the other current-phase nodes. The loop terminates after at most |\operatorname{Bag}_t| operations; its negated stopping condition gives the asserted strict half-bag bound. This proves the lemma. The first phase starts with an empty arrangement and no old allocations; the transfer of these allocations between phases is verified in the next subsection.□

Proof. For unchanged original balls both the deficit and q(B)-p(B) are zero. For any other record the decrease of width is 2(C_3+1)\delta_\ell, unless the record disappears entirely. This exceeds the decrease of the threshold, so the deficit is nonnegative. We prove, record by record,

If p(B)=0, its deficit is zero and the inequality is immediate. Otherwise, first take a nonavoiding record of width w. Since w>C_4\delta_\ell and \delta_{\ell+1}\le\delta_\ell/3,

Using the positive-part formula, whether or not the restriction survives,

where the last step uses C_4\ge3. These two bounds imply (B.64). For avoiding records both sides of these estimates have the common factor 1/(2(C_4+2)), giving exactly the same conclusion. Summing (B.64) and then using (B.63) gives \mathsf D\le(3C_3/C_4)e\le b\delta_\ell/2.□

Proof of Theorem 3.2. 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 B.1, and suppose that

The map U is a contraction. By changing its row signs, we may assume

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

Choose

Let T\subseteq\mathcal M consist of the \alpha-bad nodes with positive numerator, in the sense of Definition B.4. 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,

If T is empty, this already bounds the entire numerator. Otherwise we apply Proposition B.7 to T, with its geometric ratio \lambda set equal to \rho and its small parameter s given by

These quantities depend on q alone. In particular, for absolute constants c_2,c_5 and all sufficiently large q,

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 B.7 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

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 (B.68).

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

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

Thus the hierarchy satisfies the hypothesis of Proposition B.10 with k=q and \lambda=\rho. The constants in (B.65) obey its numerical restrictions, and \rho\le1/18 for all sufficiently large q. In the compact case, Proposition B.8 applies, since \rho\le1/12. Both cases give the uniform lower bound

The energy is the same in the dual and charging estimates, since each coordinate of Xb_e is 0, 1, or -1.

Combining (B.70) and (B.71) proves

for an absolute c_6. To check the final exponent, substitute s^\epsilon=q^{-2/25}C_2^{-1/10} and use (B.68); the logarithmic power before rounding up is 4(11/10)+2=32/5<7.

Equations (B.66) and (B.72), including the case T is empty, yield the uniform bound

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 B.1. Increase the absolute integer cutoff q_H so that the right side of (B.73) 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 C.1. 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 C.2 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

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

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 \R^d, d\ge1, and choose M>0 so that K\subseteq[-M,M]^d. The simplex

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.□