All graphs are finite, undirected, loopless multigraphs G = (V, E).
Parallel edges are distinct: each edge carries its own index, and
every sum over edges counts multiplicity. Two graphs compared as
subgraphs have a common vertex set.
For S a subset of V, delta(S) = delta_G(S) is the set of edges with
exactly one endpoint in S. A graph is k-edge-connected if
|delta(S)| >= k for every nonempty proper S. (On one vertex there is
no such S; graphs with at least two vertices are assumed, except where
stated.)
A spanning tree is a maximal acyclic connected subgraph, i.e. a
connected acyclic subgraph on all of V, hence with exactly |V|-1
edges. The graph H is r-tree-packable if it contains r pairwise
edge-disjoint spanning trees. For a partition P of V, E_H(P) is the
set of edges whose two endpoints lie in different parts of P.
Definition 1.1 (thin tree). Let a > 0. A spanning tree T of G is
a-thin if |delta_T(S)| <= a |delta_G(S)| for every nonempty proper S.
The goal is a-thin trees with a = C/k for a universal C, on every
k-edge-connected graph. This case, the strong thin tree conjecture,
was raised by Goddyn (2004). Prior work gives thin trees in
restricted settings: O(1) for laminar families (Klein and Olver 2023),
O(1) in bounded-genus graphs (Oveis Gharan and Saberi 2011), and
progress for near-minimum cuts (Klein, Olver, and Yeoh 2026).
Asadpour, Goemans, Madry, Oveis Gharan, and Saberi (2010) used
thin-tree cut control in an O(log n / log log n)-approximation for
the asymmetric traveling salesman problem. Constant-factor
approximations came later: Svensson, Tarnawski, and Vegh (2020), then
Traub and Vygen (2022). Those methods no longer use thin trees, but
the cut-control viewpoint above is why thin trees first entered that
literature.
pdf/klein-olver-2023-thin-trees-laminar.pdf
pdf/oveis-gharan-saberi-2011-atsp-bounded-genus.pdf
pdf/klein-olver-yeoh-2026-thin-trees-near-min-cuts.pdf
pdf/asadpour-2010-atsp.pdf
pdf/svensson-tarnawski-vegh-2017-1710.11441-atsp.pdf
Fix an orientation of every edge, purely to name incidence vectors.
For an edge e with tail u and head v put
b_e = 1_u - 1_v in R^V ,
where 1_u is the standard basis vector. Reversing the orientation
only changes the sign of b_e, and none of the quantities below change.
The Laplacian of a graph H = (V, E) is
L_H = sum_{e in E} b_e b_e^T .
For a positive definite symmetric matrix X on R^V, the effective
resistance of e with respect to X is
R_X(e) = b_e^T X^{-1} b_e .
For symmetric matrices, A <= B means B - A is positive
semidefinite; A < B means B - A is positive definite.
For the indicator vector 1_S of a subset S one has
1_S^T b_e = 1 if e crosses S and 0 otherwise. Hence
1_S^T L_H 1_S = |delta_H(S)| , (2.1)
and more generally x^T L_H x = sum_e (x_u - x_v)^2 over edges uv.
Lemma 2.2 (resistance and the spectral order). Let X be positive
definite and b a column vector. For t > 0,
b^T X^{-1} b <= t <=> b b^T <= t X.
If X <= Y are both positive definite, then b^T X^{-1} b <= b^T Y^{-1} b.
Proof. For the equivalence, apply the congruence x -> X^{-1/2} x.
It carries b b^T <= t X to a a^T <= t I with a = X^{-1/2} b, which
holds iff ||a||^2 <= t, i.e. b^T X^{-1} b <= t. For the second
claim, X <= Y gives Y^{-1/2} X Y^{-1/2} <= I; inverting reverses the
order and gives X^{-1} >= Y^{-1}, hence the resistance inequality. //
The following partition criterion is classical; a full exchange proof
is included because it is used repeatedly.
Theorem 3.1 (Nash-Williams 1961, Tutte 1961). Let r >= 1. A graph H
contains r pairwise edge-disjoint spanning trees if and only if
|E_H(P)| >= r (|P| - 1) (3.1)
for every partition P of V(H).
Proof. Necessity. Each spanning tree meets any partition into |P|
parts in at least |P|-1 edges: contracting each part gives a connected
graph on |P| vertices, and a connected graph on |P| vertices has at
least |P|-1 edges. r disjoint trees thus contribute at least
r(|P|-1) distinct crossing edges.
Sufficiency (graphic form of Edmonds's 1965 matroid-partition
exchange). Let F_1,...,F_r be pairwise disjoint forests whose
total number of edges m is maximum. Call such a choice a state.
pdf/edmonds-1965-minimum-partition-matroid-independent-subsets.pdf
A move: add an unused edge to one forest and delete an edge of the cycle
it closes (the forests stay forests; the total edge count m is fixed
if deletion is immediate, or one higher if not -- a slightly different
bookkeeping is used below).
More precisely, allow the following exchange. If an edge e is not in
F_i and its endpoints are joined in F_i, the unique cycle of F_i + e
allows e to be swapped for any chosen cycle edge; call that cycle edge
"freed". In any reachable state every unused edge closes a cycle in
every forest: otherwise adding it to that forest would raise the edge
count, contradicting maximality of m.
Let U be the set of edges that are unused in at least one reachable
state. If e in U is unused in some state and is added to forest F_i,
every edge of the resulting cycle belongs to U (each such edge can be
made unused, by definition, in the corresponding swap). Hence this
move leaves the connected components of F_i restricted to its U-edges
unchanged, and does not disturb the other forests.
Fix e in U and a state in which e is unused. The endpoints of e are
joined in each forest F_i by edges on the cycle, all lying in U.
Because the swap preserves U-edge components, this connectivity holds
also in the initial state. Conclusion: in the initial state, each
component of the graph (V, U) is spanned by the U-edges of every
forest F_i.
Let d be the number of components of (V, U). Each forest F_i has at
least |component|-1 U-edges in each component, so altogether the r
forests contain at least r(n - d) used U-edges, where n = |V|. Every
edge between two different components of (V,U) is necessarily used in
every state (an unused inter-component edge would belong to U and thus
lie inside one component), and no such edge is a U-edge. Therefore
the number b of inter-component edges satisfies
b <= m - r(n - d) .
If m < r(n - 1), then b < r(n-d) - r(n-d) + r(d-1) = r(d-1); that is,
b < r(d-1). But the partition of V into the d components contradicts
(3.1). Hence m = r(n-1). Since a forest on n vertices has at most
n-1 edges, each of the r forests is a spanning tree. //
Lemma 4.1 (union and quotient). Fix q >= 1 and a graph F.
(i) If F[A] and F[B] are q-tree-packable and A cap B is nonempty, then
F[A cup B] is q-tree-packable.
(ii) The inclusion-maximal q-tree-packable vertex sets form a
partition P(F) of V. If F is a subgraph of F' then P(F')
coarsens P(F).
(iii) If F is q-tree-packable on F[P] for each part and
|P(F)| > 1, then
|E_F(P(F))| < q (|P(F)| - 1) .
Proof. (i) Let the q trees on A be T_1,...,T_q, those on B be
S_1,...,S_q. In the i-th tree S_i on B, contract A cap B to one vertex,
discard loops, and choose a spanning tree of the resulting connected
multigraph; that selection plus T_i is a spanning tree of F[A cup B].
Each selected edge of S_i has an endpoint outside A, so none of them
lies in any T_j. Different i remain disjoint. This gives q disjoint
spanning trees on A cup B.
(ii) Every single vertex set is q-tree-packable (empty graph, vacuous),
so maximal sets exist by finiteness. By (i), two maximal sets that
meet must coincide. Adding edges preserves packability, so each
previous maximal set remains packable and lies inside a maximal set of
the larger graph; hence coarsening.
(iii) Let d = |P(F)| > 1. Contract each part to one vertex and delete
loops, giving the quotient Q on the d part-vertices; its edge set is
exactly E_F(P(F)). Suppose for contradiction |E_F(P(F))| >= q(d-1).
Because Q has d vertices, this says |E_Q(V(Q))| >= q(|V(Q)|-1). So
the set V(Q) itself qualifies as a set W of at least two vertices with
|E_Q(W)| >= q(|W|-1). Choose such a W inclusion-minimal, where
E_Q(W) means the edges of Q having both endpoints in W. By
minimality every proper nonempty J subset W satisfies
|E_Q(J)| <= q(|J|-1): for |J| >= 2 directly, and for a singleton
because there are no loops and q(|J|-1) = 0.
Take any partition W = J_1 + ... + J_t into t >= 2 pairwise disjoint
parts.
The edges of Q inside W are the edges inside the J_l together with the
edges between them, so the number of between-edges is
|E_Q(W)| - sum_l |E_Q(J_l)|
>= q(|W|-1) - sum_l q(|J_l|-1)
= q(|W|-1) - q(|W|-t)
= q(t-1) .
Hence every partition of W into t parts has at least q(t-1) crossing
edges in Q[W]. By Theorem 3.1 the subgraph Q[W] contains q pairwise
edge-disjoint spanning trees.
Each vertex of W is a part S_v of P(F), and F[S_v] is q-tree-packable.
Attach to each of the q trees of Q[W] a packed tree inside every S_v.
The result is q pairwise edge-disjoint spanning trees of F on the
union S = union of the S_v over v in W. Since |W| >= 2, S is strictly
larger than any single part, yet q-tree-packable. This contradicts
maximality of the parts of P(F). Therefore |E_F(P(F))| < q(d-1). //
Fix k >= 1 and a k-edge-connected graph G on n >= 2 vertices. The
target is a spanning tree T with |delta_T(S)| <= (C/k)|delta_G(S)|
for all nonempty proper S.
Step 1: many disjoint trees from connectivity.
By Theorem 3.1 a k-edge-connected graph contains many edge-disjoint
spanning trees; for k >= 2 it packs at least floor(k/2) of them (see
the end of the cascade). Write r_0 = max(1, floor(k/2)) >= k/3.
Step 2: a sparsification cascade.
Build a sequence of spanning subgraphs
G = H_0 superset H_1 superset ... superset H_j ,
where H_i contains r_i pairwise edge-disjoint spanning trees, and
r_{i+1} = floor( (1 - 4 u_i) r_i / 2 ), u_i = r_i^(-1/16),
|delta_{H_{i+1}}(S)| <= (1/2 + 3 tau_i) |delta_{H_i}(S)| ,
with tau_i = 2 sqrt(eps_i) + eps_i, eps_i = 6 r_i^(-1/2). So each
step roughly halves both the cut sizes and the packing size, and it
loses a relative factor 1 + O(u_i) together.
Stop at the first j with r_j < r_*, an absolute threshold chosen
large enough. Since r_j >= 1, H_j is connected, so it has a spanning
tree T. Then for every cut S,
|delta_T(S)| <= |delta_{H_j}(S)|
<= prod_i (1/2 + 3 tau_i) |delta_G(S)| .
Dividing out the (roughly halved) packing size and multiplying the
relative per-step losses gives the uniform bound
|delta_T(S)| <= C_it (r_j / r_0) |delta_G(S)| <= (C/k)|delta_G(S)| .
The key point is that the relative losses are summable: u_i shrinks by
roughly 2^(-1/16) per step, so sum_i u_i is bounded, and
prod_i (1 + 15 u_i) <= exp( 15 sum_i u_i ) <= C_it
with C_it a universal constant. Because r_0 >= k/3 the
final constant C = 3 C_it r_* is universal.
Step 3: the sparsification step.
Given H with r edge-disjoint spanning trees, r large, the construction
produces H' with about r/2 trees and halves of cuts. This uses two
different vector systems in tandem:
(a) Extraction. There is a positive definite matrix X with
L_H <= X, cut bounds 1_S^T X 1_S <= 3 |delta_H(S)|, and such
that the edges with small resistance R_X(e) <= 4 r^(-1/2) still
carry q = floor((1-u)r) trees, u = r^(-1/16). (Theorem 8.1,
proved below.)
(b) Isotropic representation. For the union B of those q trees
there are vectors z_e in R^(n-1) with
sum_{e in B} z_e z_e^T = I_{n-1}, ||z_e||^2 <= (1+rho)/q ,
and z_e = s_e M b_e for a common invertible M and positive
scalars s_e, so the z_e and the incidence vectors b_e have the
same linear dependencies on every edge subset.
(c) One simultaneous split. Stack w_e = (X^(-1/2) b_e, z_e), so
that sum_{e in B} w_e w_e^T <= 2 I. The MSS theorem, via Lemma
7.1, selects a subset A of B with
(1/2) Sigma - tau I <= sum_{e in A} w_e w_e^T
<= (1/2) Sigma + tau I ,
Sigma = sum_{e in B} w_e w_e^T, tau = 2 sqrt(eps) + eps,
eps = 6 r^(-1/2).
The two blocks of this single inequality do two jobs at once:
the X-block controls every cut of A, while the z-block certifies
that A still packs about r/2 trees. The next step carries this out.
Two systems are needed. Sampling by effective resistance preserves
the Laplacian approximately (Spielman and Srivastava 2011; the
deterministic version is the twice-Ramanujan sparsifier of Batson,
Spielman, and Srivastava 2012), but it produces a weighted graph. A
thin spanning tree needs an unweighted subgraph: q parallel edges
between two vertices have the same Laplacian as one edge of weight q,
but they pack q disjoint spanning trees while the weighted single
edge packs one. The z-block supplies exactly the rank information --
positive-definiteness of sum_A z_e z_e^T -- that rules this failure
out and recovers the tree packing.
pdf/spielman-srivastava-2008-0803.0929-effective-resistances.pdf
pdf/batson-spielman-srivastava-2012-0906.4364-twice-ramanujan.pdf
Step 4: the extraction theorem.
The matrix X in Step 3 is produced by a fixed-point argument on a
compact convex set K of matrices. For each X in K the threshold graph
of low-resistance edges and its maximal packing partition are
examined; a hierarchy estimate replaces these by a single response
matrix Y with small resistance on almost every crossing edge,
simultaneously for all thresholds. Only finitely many responses are
interpolated at a time, and a fixed-point limit yields one matrix X
self-consistent with its own partition. If that partition were
nontrivial, Lemma 4.1(iii) would be violated; hence the
low-resistance graph is q-tree-packable, giving
the extraction theorem.
Step 5: the hierarchy estimate.
The response in Step 4 is the "polynomial shortcut bound": for a
graph with a locally q-connected hierarchy, one matrix D makes the
average resistance R_D(e) small (at most q^(-31/40)) on every marked
parent boundary O(A). This is the deepest input, a polynomial
consequence of the Anari-Oveis Gharan tree-CP theorem. The proof is a
dual method:
(a) The dual reduction. The existence of D is dual to a bound on
binary embeddings X and orthonormal edge vectors u_e; the
matrix objective p_* and the embedding ratio Q_* satisfy
p_* <= Q_* <= 2 p_*.
(b) The geometry. A bad node's boundary is grouped into
"bags" of disjoint balls in the cube [0,1]^d, with a spectral
packing lemma supplying the balls.
(c) The charging. Each family of bags is charged against the
total length sum_e ||X_e||_1, either as "compact" bags or as
"assigned" bags riding on the hierarchy.
(d) The parameters. The losses are collected and the rate
q^(-31/40) is confirmed.
pdf/anari-oveis-gharan-2013-tree-cp.pdf
Brouwer's fixed point theorem (Brouwer 1911) and the
Marcus-Spielman-Srivastava theorem are proved from first principles.
A pipage-rounding counterpart to the latter appears in Harvey and
Olver (2014).
pdf/marcus-spielman-srivastava-2014-interlacing-ii.pdf
pdf/harvey-olver-2014-1104.4641-pipage-rounding.pdf
The whole reason a thin sparsification works is the following: a
packing of edge-disjoint spanning trees admits a coordinate system in
which the incidence vectors become nearly isotropic, with the same
linear dependencies as before. This is the tool that converts a
positive-definite matrix certificate back into edge-disjoint trees.
Write V0 = { x in R^V : sum_v x_v = 0 }, the "zero-sum" subspace,
which has dimension n-1 for n = |V|. Every incidence column b_e lies
in V0. The incidence columns of any spanning tree form a basis of V0:
by induction on n, an acyclic connected subgraph on n vertices always
has n-1 edges, and no proper subset spans that space.
Lemma 6.1 (isotropic representation preserving ranks, after Barthe
1998). Let B be the union of q >= 1 pairwise edge-disjoint spanning
trees on the vertex set V with n = |V| >= 2. For every rho > 0 there
are vectors z_e in
R^(n-1), indexed by the individual edges of B, with
sum_{e in B} z_e z_e^T = I_{n-1}, (6.1)
||z_e||^2 <= (1 + rho)/q for every e in B. (6.2)
Moreover there are an invertible linear map M : V0 -> R^(n-1) and
positive scalars s_e with z_e = s_e M b_e. Consequently, for every
subset A of edges of B the z_e (e in A) span a space of exactly the
same dimension as the b_e (e in A): linear dependencies are identical.
pdf/barthe-1998-9705210-brascamp-lieb-reverse.pdf
Proof. Fix orthonormal coordinates on V0, so b_e is an (n-1)-vector
and a spanning tree's columns form the standard basis up to a linear
change of coordinates. Write T_1,...,T_q for the given trees; the T_i
partition E(B).
For a in R^{E(B)} define
N(a) = sum_{e in B} exp(a_e) b_e b_e^T ,
h(a) = log det N(a) - (1/q) sum_{e in B} a_e .
The tree T_1 is a basis, so its weights exp(a_e) are all positive and
N(a) is positive definite for every a; h is smooth and everywhere
finite.
Lower bound. Let c_t > 0 be the squared determinant of the basis of
columns of T_t. Cauchy-Binet, summing only over the q tree-bases,
gives
det N(a) = sum_{basis F} prod_{e in F} exp(a_e) det(F)^2
>= sum_{t=1}^q c_t exp( sum_{e in T_t} a_e ) .
Apply the arithmetic-geometric mean to these q nonnegative numbers:
det N(a) >= q ( prod_{t=1}^q c_t )^(1/q)
exp( (1/q) sum_{e in B} a_e ) .
Indeed sum_{e in B} a_e = sum_t sum_{e in T_t} a_e because the T_t
partition E(B). Therefore for all a
h(a) >= L := log q + (1/q) sum_{t=1}^q log c_t . (6.3)
Steepest descent with a small penalty. Put K = h(0) - L >= 0 by
(6.3). For gamma > 0 the function a -> h(a) + gamma ||a||^2 is
continuous and coercive (the penalty dominates), so it attains a
minimum at some a^gamma. Comparing with a = 0,
h(a^gamma) + gamma ||a^gamma||^2 <= h(0) ,
hence gamma ||a^gamma||^2 <= h(0) - h(a^gamma) <= K and, at the
minimizer, the gradient of the penalty cancels the gradient of h:
grad h(a^gamma) = -2 gamma a^gamma ,
||grad h(a^gamma)|| <= 2 sqrt(gamma K) .
Choose gamma small enough that 2 sqrt(gamma K) <= rho/q. Dropping the
superscript, this chosen a satisfies, for every e in B,
| partial h / partial a_e | <= rho / q . (6.4)
Derivatives. The determinant derivative formula gives
partial h / partial a_e
= exp(a_e) b_e^T N(a)^{-1} b_e - 1/q .
Combined with (6.4), for every e in B
exp(a_e) b_e^T N(a)^{-1} b_e <= (1 + rho)/q . (6.5)
The vectors. Set z_e = exp(a_e / 2) N(a)^{-1/2} b_e. Then
sum_{e in B} z_e z_e^T
= N(a)^{-1/2} ( sum_e exp(a_e) b_e b_e^T ) N(a)^{-1/2}
= N(a)^{-1/2} N(a) N(a)^{-1/2} = I_{n-1} ,
which is (6.1); and z_e^T z_e = exp(a_e) b_e^T N(a)^{-1} b_e <=
(1+rho)/q by (6.5), which is (6.2). Finally put M = N(a)^{-1/2}
(invertible) and s_e = exp(a_e / 2) > 0, so z_e = s_e M b_e. Since M
is invertible and every s_e is nonzero, a set of incidence columns is
linearly independent exactly when the corresponding z_e are. //
The next lemma is the bridge from a positive-definite certificate to a
tree packing. It is where the rank preservation of Lemma 6.1 is used.
Lemma 6.2 (projected trace certifies packing). With the vectors of
Lemma 6.1, suppose A is a subset of E(B) and c > 0 with
sum_{e in A} z_e z_e^T >= c I_{n-1} .
Then the subgraph (V, A) contains at least floor( c q / (1+rho) )
pairwise edge-disjoint spanning trees.
Proof. Let P = {V_1,...,V_d} be an arbitrary partition of V into d
nonempty parts. Let W be the span of the z_e over all edges e of B
whose two endpoints lie in one common part. The incidence vectors b_e
of those edges lie in the direct sum of the zero-sum spaces of the
parts, a space of dimension sum_j(|V_j| - 1) = n - d. By the rank
preservation in Lemma 6.1 the corresponding z_e span a space of that
same dimension bounded by n - d, so dim W <= n - d.
Let Pi be the orthogonal projection onto W^perp. Then
tr Pi = (n-1) - dim W >= d - 1. Multiplying the positive
semidefinite inequality by Pi and taking traces,
c (d - 1) <= c tr Pi
<= tr( Pi (sum_{e in A} z_e z_e^T) Pi )
= sum_{e in A} ||Pi z_e||^2 .
For an edge e of B lying inside one part, z_e is in W and Pi z_e = 0;
only crossing edges of A contribute. For those, ||Pi z_e||^2 <=
||z_e||^2 <= (1+rho)/q by (6.2). Hence
c (d - 1) <= ((1+rho)/q) |E_A(P)| ,
|E_A(P)| >= ( c q / (1+rho) )(d - 1) .
Every partition of V thus meets A in at least (cq/(1+rho))(d-1) edges,
so certainly at least floor(cq/(1+rho))(d-1). By Theorem 3.1 the
graph (V, A) contains floor(cq/(1+rho)) pairwise edge-disjoint
spanning trees. //
Isolate the exact consequence of the Marcus-Spielman-Srivastava (2014)
random-vector theorem (proved below) that the sparsification needs.
The use of deterministic "padding" lets the covariance be singular,
and the two-sided form controls both input blocks of the stacked
vectors simultaneously.
Lemma 7.1 (two-sided splitting). Let w_e in R^D be finitely many
vectors with
Sigma := sum_e w_e w_e^T <= 2 I_D , ||w_e||^2 <= eps (each e),
for some eps > 0. Then there is a subset A of the index set with
(1/2) Sigma - tau I_D <= sum_{e in A} w_e w_e^T
<= (1/2) Sigma + tau I_D , (7.1)
where tau = 2 sqrt(eps) + eps.
Proof. Independently for each e, let v_e in R^(2D) equal (w_e, 0) or
(0, w_e), each with probability 1/2. Then
M := sum_e E[ v_e v_e^T ] = diag( Sigma/2 , Sigma/2 ) <= I_(2D),
and E||v_e||^2 = ||w_e||^2 <= eps.
Padding to isotropy. Diagonalize the positive-semidefinite matrix
I_(2D) - M. For each positive eigenvalue lambda with unit eigenvector
f, let m_lambda = ceil(lambda / eps) and introduce m_lambda
deterministic vectors, each equal to sqrt(lambda / m_lambda) f. Each
has squared norm lambda/m_lambda <= eps, and their outer products sum
to I_(2D) - M. These vectors are deterministic, hence independent of
everything else. Including them, the whole family has covariance
exactly I_(2D) and every member has squared norm at most eps, so
Theorem 21.1 applies.
Theorem 21.1 now gives an outcome of positive probability with
|| sum( all vectors )( their transposes ) || <= (1 + sqrt(eps))^2.
Let A be the set of indices e whose random vector fell in the first
block. Since the deterministic padding is the fixed matrix
I_(2D) - M, this outcome says
diag( S_A , Sigma - S_A ) + ( I_(2D) - M )
<= (1 + sqrt(eps))^2 I_(2D) , S_A := sum_{e in A} w_e w_e^T .
Subtracting the fixed matrix I_(2D) - M and using
(1 + sqrt(eps))^2 - 1 = 2 sqrt(eps) + eps = tau,
diag( S_A , Sigma - S_A ) <= M + tau I_(2D) .
The first block gives S_A <= Sigma/2 + tau I_D; the second block gives
Sigma - S_A <= Sigma/2 + tau I_D, i.e. S_A >= Sigma/2 - tau I_D.
Together these are (7.1). //
The heart of the cascade is one step: halve the packing and halve the
cuts, paying a relative loss 1 + 15 r^(-1/16). Take the extraction
theorem as a black box here (Theorem 8.1); it is proved below.
Theorem 8.1 (shortcut extraction). There is an absolute integer r_H
such that: for every integer r >= r_H, every r-tree-packable graph H
on n >= 2 vertices admits a positive definite matrix X with
L_H <= X , 1_S^T X 1_S <= 3 |delta_H(S)| (all nonempty proper S),
and the edges of H with R_X(e) <= 4 r^(-1/2) contain
q = floor( (1 - u) r ) edge-disjoint spanning trees, where
u = r^(-1/16).
Proposition 8.2 (one step). There is an absolute integer r_0 (a
further absolute threshold) such that the following holds for every
integer r >= r_0. If H has at least two vertices and contains r
edge-disjoint spanning trees, set
u = r^(-1/16), q = floor((1-u) r),
eps = 6 r^(-1/2), tau = 2 sqrt(eps) + eps .
Then H has a spanning subgraph H' which contains at least
r' = floor( (1 - 4u) r / 2 ) (8.1)
edge-disjoint spanning trees and satisfies, for every nonempty proper
S,
|delta_{H'}(S)| <= (1/2 + 3 tau) |delta_H(S)| . (8.2)
Moreover
5/16 <= r'/r <= 1/2 , (1/2 + 3 tau)/(r'/r) <= 1 + 15 u . (8.3)
Proof. Write n = |V(H)| and take r above the larger of r_H and 16^16,
so u <= 1/16. Theorem 8.1 supplies X and q edge-disjoint spanning
trees all of whose edges satisfy R_X(e) <= 4 r^(-1/2). Let B be the
union of those q trees.
Apply Lemma 6.1 to B with rho = u, producing z_e in R^(n-1) with
sum_{e in B} z_e z_e^T = I_(n-1) and ||z_e||^2 <= (1+u)/q. Put
a_e = X^(-1/2) b_e , w_e = (a_e, z_e) in R^(2n-1) ,
Sigma = sum_{e in B} w_e w_e^T .
The covariance is bounded by 2 I. The cross blocks need not vanish,
but for any x in R^V and y in R^(n-1),
(x,y)^T Sigma (x,y)
= sum_{e in B} ( <x,a_e> + <y,z_e> )^2
<= 2 sum_{e in B} <x,a_e>^2 + 2 sum_{e in B} <y,z_e>^2
= 2 x^T X^(-1/2) L_B X^(-1/2) x + 2 ||y||^2
<= 2 ||x||^2 + 2 ||y||^2 ,
using L_B <= L_H <= X for the last step. Hence 0 <= Sigma <= 2 I.
Each vector is small. Since q >= (1-u) r - 1 >= r/2 for large r,
and (1+u)/q <= 2(1+u)/r <= 2 r^(-1/2) for large r (absorbed in the
threshold), while ||a_e||^2 = R_X(e) <= 4 r^(-1/2),
||w_e||^2 = ||a_e||^2 + ||z_e||^2 <= 4 r^(-1/2) + 2 r^(-1/2)
= 6 r^(-1/2) = eps .
Invoke Lemma 7.1. It gives A subset of B with
(1/2) Sigma - tau I <= sum_{e in A} w_e w_e^T
<= (1/2) Sigma + tau I , tau = 2 sqrt(eps)+eps.
Read the two principal blocks of this single matrix inequality.
z-block: sum_{e in A} z_e z_e^T >= (1/2 - tau) I_(n-1) . (8.4)
a-block: X^(-1/2) L_A X^(-1/2)
<= (1/2) X^(-1/2) L_B X^(-1/2) + tau I_n . (8.5)
For the cut bound, apply the congruence x -> X^(1/2) x to (8.5) and use
L_B <= L_H:
L_A <= (1/2) L_B + tau X <= (1/2) L_H + tau X .
Test on the indicator 1_S of a proper nonempty set S:
|delta_{H'}(S)| = 1_S^T L_A 1_S
<= (1/2) |delta_H(S)| + tau (1_S^T X 1_S)
<= (1/2) |delta_H(S)| + 3 tau |delta_H(S)| ,
which is (8.2), with H' = (V, A).
For the packing, express the errors through u. Since eps = 6 u^8,
tau = 2 sqrt(6) u^4 + 6 u^8 <= u/2 (0 < u <= 1/16) ,
because dividing by u bounds the left ratio by 6(16^(-3) + 16^(-7)) <
1/2. Thus c := 1/2 - tau > 0, and (8.4) together with Lemma 6.2 gives
at least floor( c q / (1+u) ) trees in (V, A). The claim is
(1/2 - tau) q / (1+u) >= (1 - 4u) r / 2 . (8.6)
Since q >= (1-u) r - 1 and 2(1/2 - tau) >= 1 - 2 tau >= 1 - u (as
tau <= u/2),
2 (1/2 - tau) q / (1+u)
>= (1 - u) ( (1-u) r - 1 ) / (1+u) ,
so it suffices that
(1 - u)((1-u) r - 1) >= (1+u)(1 - 4u) r ,
i.e. that the difference
( (1-u)^2 - (1+u)(1-4u) ) r - (1-u) = (u + 5u^2) r - (1-u)
be nonnegative. This equals r u (1 + 5u) - (1-u) = r^(15/16)(1+5u) -
(1-u) >= 1 - (1-u) > 0 since r u = r^(15/16) >= 1. Thus (8.6) holds,
and taking floors proves r >= r' = floor((1-4u)r/2) trees.
Finally (8.3). The floor in (8.1) and 1/r <= u give
r'/r >= 1/2 - 2u - 1/r >= 1/2 - 3u >= 5/16 ,
r'/r <= 1/2 .
Using tau <= u/2 once more,
(1/2 + 3 tau)/(r'/r) <= (1 + 3 tau)/(1 - 6u)
<= (1 + 3u)/(1 - 6u)
= 1 + 9u/(1 - 6u) <= 1 + 15 u ,
since 90 u <= 6 for u <= 1/16. //
The sparsification relied on Theorem 8.1, which produces the
positive definite matrix X. The engine of the proof is a hierarchy
estimate
(Theorem 9.2 below): many nested partitions can be served by one
matrix at once. First set up the vocabulary, then run the
fixed-point argument that turns the estimate into the extraction
theorem.
Definition 9.1 (hierarchy and its boundaries). Let H = (V, E) be a
finite loopless multigraph. A hierarchy on V is a finite rooted tree
whose nodes are distinct nonempty vertex sets, whose root is V, whose
leaves are the singletons, and in which the children of every nonleaf
node form a partition of that node into at least two sets.
For a nonroot node A, write A* for its parent and define two edge sets
(multiplicity retained):
P(A) = delta_H(A) = E_H( A , V \ A ) (the full boundary),
O(A) = E_H( A , A* \ A ) (the parent boundary).
Fix an integer h >= 2. The hierarchy is locally h-connected if H[A]
is h-edge-connected for every node A. For a singleton node the
condition is vacuous.
Two elementary facts about these boundaries.
(a) For every nonroot A, |O(A)| >= h. Indeed O(A) is the boundary
of the nonempty proper set A inside the h-edge-connected graph
H[A*].
(b) Every edge belongs to O(A) for exactly two nodes A. Let C be
the least node containing both endpoints of the edge; the two
nodes are the two children of C containing the respective
endpoints. Consequently, for any collection of nodes, each
edge is counted in at most two of their O(A) sets. This
fact -- used in the dual reduction and in collecting the
parameters -- is the only "hierarchical" property that the
hierarchy bound needs.
Orient each edge arbitrarily, with incidence column b_e, and set
L_H = sum_{e in E} b_e b_e^T. A shortcut matrix for H is a symmetric
positive definite matrix D on R^V such that
1_S^T D 1_S <= |delta_H(S)| for all nonempty proper S. (9.1)
Its edge resistance is R_D(e) = b_e^T D^{-1} b_e. The restriction to
proper cuts in (9.1) is essential: the same inequality at S = V would
read 1_V^T D 1_V <= 0, impossible for positive definite D. Note that
D <= L_H is not required.
Theorem 9.2 (polynomial shortcut bound). There is an absolute
integer q_H >= 2 such that the following holds for every integer
q >= q_H. Let H have a locally q-connected hierarchy, and let M be
any collection of its nonroot nodes with
|O(A)| >= |P(A)| / q for every A in M .
Then H has a shortcut matrix D with
(1/|O(A)|) sum_{e in O(A)} R_D(e) <= q^(-31/40) for every A in M.
(9.2)
The cutoff q_H is independent of H, of the depth of the hierarchy,
and of the marked collection M.
Theorem 9.2 is a polynomial consequence of the Tree-CP theorem of
Anari and Oveis Gharan. A self-contained proof by their dual and
geometric method appears below, with parameters chosen to yield the
weaker, explicit bound q^(-31/40). Only the statement is needed for
the rest of the argument.
Throughout, H is an r-tree-packable graph on n >= 2
vertices. Set
u = r^(-1/16), q = floor( (1 - u) r ) . (10.1)
Take r above an absolute threshold, so in particular q > 1. The
threshold is raised finitely many times below; each raise is absolute.
Define the set of candidate matrices
K = { X symmetric :
X >= L_H + n^(-1) I ,
1_S^T X 1_S <= 3 |delta_H(S)| for all nonempty proper S } .
(10.2)
Record that K is a nonempty compact convex set of symmetric
matrices.
Nonempty. H is connected (it is r-tree-packable with r >= 1), so
L_H has kernel exactly the constants and L_H + n^(-1) I is positive
definite. For a proper S, since |S|/n < 1 <= |delta_H(S)|,
1_S^T (L_H + n^(-1) I) 1_S = |delta_H(S)| + |S|/n
<= 2 |delta_H(S)| <= 3 |delta_H(S)| .
So L_H + n^(-1) I is in K.
Convex. Both defining kinds of inequality are linear in X.
Closed. All inequalities are non-strict and linear (in X, or in
X's entries).
Bounded. The singleton cuts give X_vv <= 3 deg_H(v). A positive
semidefinite matrix has |X_vw|^2 <= X_vv X_ww, so every entry is
bounded in absolute value by a constant depending on H. A closed
bounded subset of the finite-dimensional space of symmetric
matrices is compact.
Lower bound. Every X in K satisfies X >= L_H + n^(-1) I >= n^(-1) I,
in particular X is positive definite.
Now the hierarchy response. Suppose the graph H carries a locally
q-connected hierarchy (Definition 9.1) with q from (10.1), and mark
those nonroot nodes A satisfying
|O(A)| >= |P(A)| / q . (10.3)
For all sufficiently large absolute r one has q >= r/2 and q >= q_H
(the cutoff of Theorem 9.2). Theorem 9.2 provides a shortcut matrix D
with
(1/|O(A)|) sum_{e in O(A)} R_D(e) <= q^(-31/40)
<= 2^(31/40) r^(-31/40) <= r^(-3/4) (10.4)
on every marked A. The bound q >= r/2 gives the second step, and the third
step holds because 2^(31/40) <= r^(1/40), i.e. for r >= 2^31.
Define the response matrix
Y = L_H + n^(-1) I + D . (10.5)
Claim: Y is in K. First, Y >= L_H + n^(-1) I since D is positive
semidefinite. Second, for a proper nonempty S, the shortcut inequality
(9.1) gives 1_S^T D 1_S <= |delta_H(S)|, so
1_S^T Y 1_S = |delta_H(S)| + |S|/n + 1_S^T D 1_S
<= 2 |delta_H(S)| + |S|/n <= 3 |delta_H(S)| ,
using |S|/n < 1 <= |delta_H(S)|. Hence Y is in K.
Finally, compare resistances. Since Y >= D (again D >= 0 and
L_H + n^(-1) I >= 0), Lemma 2.2 gives Y^(-1) <= D^(-1), hence for every
edge e
R_Y(e) = b_e^T Y^(-1) b_e <= b_e^T D^(-1) b_e = R_D(e) .
Averaging over a marked boundary and using (10.4),
(1/|O(A)|) sum_{e in O(A)} R_Y(e) <= r^(-3/4)
for every marked A. (10.6)
This is the "hierarchy response": one matrix Y in K with small average
resistance on all marked parent boundaries simultaneously.
Fix X in K and a real threshold s > 0. Let
F_s(X) = ( V , { e in E(H) : R_X(e) <= s } ) (11.1)
be the threshold graph of low-resistance edges, and let
P_s(X) = P( F_s(X) ) (11.2)
be its maximal q-tree-packable partition from Lemma 4.1(ii), with q as
in (10.1). Define the crossing set and its size
B_s(X) = E_H( P_s(X) ) , M_s(X) = |B_s(X)| . (11.3)
These crossing sets are taken in H, not in F_s(X): they include edges
of H that are absent from the threshold graph.
Three immediate facts. As s increases the graph F_s(X) gains edges, so
by Lemma 4.1(ii) the partitions P_s(X) coarsen and the crossing sets
B_s(X) shrink. There are only finitely many partitions of V, so only
finitely many distinct pairs (P_s, B_s) occur as s varies. And every
part A of P_s(X) induces a q-edge-connected subgraph of H: it contains
q edge-disjoint spanning trees of F_s(X)[A] subseteq H[A].
The next lemma is the heart of the extraction: although the response
Y depends on X, it kills the resistance of almost every edge of every
crossing set B_s(X) at once, losing only a fraction O(r^(-1/4)).
Lemma 11.1 (simultaneous response). There is an absolute constant
C_0, which may be taken to be 40, such that for every X in K there
exists Y in K with
|{ e in B_s(X) : R_Y(e) > r^(-1/2) }| <= C_0 r^(-1/4) M_s(X)
(11.4)
for every s > 0.
Proof of Lemma 11.1. Fix X in K and temporarily suppress it from the
notation. Only finitely many pairs (P_s, B_s) occur, so one may build a
finite hierarchy that captures all of them.
Building the hierarchy.
In each occupied dyadic bin 2^a <= M_s < 2^(a+1), a >= 0, choose the
finest partition P_s that occurs in that bin. List the chosen
partitions from finest to coarsest as
P_0 , P_1 , ... , P_(L-1) ,
with crossing sets B_i, sizes M_i = |B_i|. Append the trivial
partition
P_L = { V } , B_L = empty , M_L = 0 .
The distinct parts of all these partitions, together with the
singletons, form a laminar family containing V (they are nested
partitions, so any two parts are either nested or disjoint). Give
each proper set its smallest proper containing set in the family as
its parent; this is a hierarchy. The children of every nonsingleton
partition that set, because the P_i are nested. Every induced graph
H[A] at a node is q-edge-connected: for the partition parts this was
noted in Lemma 11.1 (each part packs q trees inside the threshold
graph), the root V is r-tree-packable with r >= q, and singletons are
vacuous. So this is a locally q-connected hierarchy.
The marked set. Mark those nonroot nodes A with |O(A)| >= |P(A)|/q,
and take the response Y from (10.6), so
(1/|O(A)|) sum_{e in O(A)} R_Y(e) <= r^(-3/4) (11.5)
on every marked A, and Y is in K.
One transition. Fix j < L and consider the step P_j -> P_(j+1),
finest to coarser. Say a part A of P_j changes if it is not itself a
part of P_(j+1). Each changing part A sits inside exactly one part of
P_(j+1), namely the immediate parent of A in the hierarchy. Indeed,
earlier selected partitions are finer and later ones are coarser, so
none of their parts is a distinct set strictly between A and its image
in P_(j+1); singletons create no such set either.
Every edge of B_j \ B_(j+1) has its two endpoints in two changing
parts of P_j that share one parent in P_(j+1). Such an edge lies in
O(A) for each of those two changing parts A. Summing over the changing
parts of P_j (each edge counted at most twice, by fact 9.1(b)),
sum_{changing A} |O(A)| <= sum_{all parts of P_j} |P(A)|
= 2 |B_j| = 2 M_j .
Split the changing parts into unmarked and marked.
Unmarked: |O(A)| < |P(A)|/q, so
sum_{unmarked A} |O(A)| <= (1/q) sum_{all parts} |P(A)|
<= 2 M_j / q .
Marked: by (11.5) and Markov's inequality (average <= r^(-3/4), so
the number of e with R_Y(e) > r^(-1/2) is at most the average divided
by r^(-1/2), i.e. at most r^(-1/4)|O(A)|),
|{ e in O(A) : R_Y(e) > r^(-1/2) }| <= r^(-1/4) |O(A)| ,
and summing over marked changing parts,
sum <= r^(-1/4) sum_{marked} |O(A)| <= r^(-1/4) * 2 M_j .
Count bad edges of the transition. An edge of B_j \ B_(j+1) is bad if
R_Y(e) > r^(-1/2). It is bad only if some changing part A with e in
O(A) is either marked (then counted above) or unmarked (then e is
among the unmarked |O(A)| edges, a coarser but sufficient bound).
Hence the number of bad disappearing edges is at most
2 M_j r^(-1/4) + 2 M_j / q = 2 ( r^(-1/4) + 1/q ) M_j . (11.6)
The dyadic tail. Because there is one chosen partition per occupied
dyadic bin and the bin exponents strictly decrease, for every i < L,
sum_(j=i)^(L-1) M_j < 4 M_i . (11.7)
If 2^a <= M_i < 2^(a+1), the successive chosen sizes are at most
2^(a+1), 2^a, 2^(a-1), ..., which sum to less than 2^(a+2) = 4*2^a.
Bad edges of B_i. Each edge of B_i leaves the crossing set at exactly
one later transition (it disappears once, because the B_j shrink to
the empty set at j = L). Summing (11.6) over j = i, ..., L-1 and
using (11.7),
|{ e in B_i : R_Y(e) > r^(-1/2) }|
<= 2 ( r^(-1/4) + 1/q ) sum_(j=i)^(L-1) M_j
<= 8 ( r^(-1/4) + 1/q ) M_i . (11.8)
Arbitrary threshold. Let s > 0 with M_s > 0. The chosen partition
P_i in s's dyadic bin is the finest in that bin, hence at least as fine
as P_s, so B_s subseteq B_i and M_i < 2 M_s. Then
|{ e in B_s : R_Y(e) > r^(-1/2) }|
<= |{ e in B_i : R_Y(e) > r^(-1/2) }|
<= 8 ( r^(-1/4) + 1/q ) M_i
<= 16 ( r^(-1/4) + 1/q ) M_s .
For all sufficiently large r one has (r^(-1/4) + 1/q) <= (5/2) r^(-1/4)
(using q >= r/2), whence the last bound is at most 40 r^(-1/4) M_s.
This is (11.4) with C_0 = 40. If M_s = 0 the left side is empty. The
bound holds simultaneously for every s > 0 because the single matrix Y
serves all the crossing sets at once. //
Now prove the extraction theorem. The response of Lemma 11.1 is
not continuous in X, so it is impossible to feed it directly to a fixed-point
theorem. Instead interpolate only finitely many responses at a
time; the fixed points X_p have a limit X, and at X the partition it
induces is forced to be trivial.
Proof of Theorem 8.1. Let H be r-tree-packable, r above the larger of
2^31 and 16, u = r^(-1/16), q = floor((1-u)r), so q > 1.
Finite covers and interpolation. For each positive integer p, cover
the compact set K by finitely many relative open balls of radius 1/p,
with centers C_{p,1}, ..., C_{p,N_p} in K. At each center choose a
response Y_{p,j} in K satisfying Lemma 11.1 for that center. Define
continuous weights on K,
phi_{p,j}(Z) = max{0, 1/p - ||Z - C_{p,j}||}
/ sum_h max{0, 1/p - ||Z - C_{p,h}||} .
The denominator is positive everywhere because the balls cover K, so
phi_{p,j} is continuous, lies in [0,1], and the phi_{p,j} sum to 1.
Hence the interpolation
Phi_p(Z) = sum_j phi_{p,j}(Z) Y_{p,j}
is a continuous self-map of the compact convex set K. By Brouwer's
fixed point theorem (Theorem 20.2) there is X_p in K with
X_p = Phi_p(X_p). Passing to a subsequence, X_p -> X in K.
A threshold avoiding all resistances. There are finitely many edges,
so choose s with
3 r^(-1/2) < s < 4 r^(-1/2) , s not in { R_X(e) : e in E(H) } .
Stabilising the threshold graph. If phi_{p,j}(X_p) > 0 then, since
X_p = Phi_p(X_p) lies in the support of phi_{p,j},
||C_{p,j} - X|| <= ||C_{p,j} - X_p|| + ||X_p - X||
< 1/p + ||X_p - X|| -> 0 ,
uniformly over the contributing centers. Each R_Z(e) is continuous in
Z on K. Because the finitely many values R_X(e) avoid s, every
contributing center C_{p,j}, for p large, has the same threshold graph
F_s, the same packing partition, and the same crossing set as X. Write
B = B_s(X) and M = |B| for these common values.
The trivial case. If M = 0 then the partition P_s(X) is {V} and the
argument is complete at the outset: F_s(X) is q-tree-packable and X
is in K, so the extraction conclusion holds with this X. Assume M > 0.
Most edges are good. Put delta = C_0 r^(-1/4). For p large, each
contributing center has, by Lemma 11.1, at most delta M bad edges in
this same set B (edges with R > r^(-1/2)). Weighting the bad-indicator
of each edge e in B by phi_{p,j}(X_p) and summing over j but not over
e, for each e the weighted bad mass is the phi-average of indicators;
at most 2 delta M edges can have weighted bad mass greater than 1/2
(otherwise the total mass would exceed delta M).
Good edges survive to the limit. For every other edge e in B, at
least half the total weight lies on matrices Y with R_Y(e) <= r^(-1/2).
By Lemma 2.2 this is equivalent to Y >= r^(1/2) b_e b_e^T. The
remaining matrices are positive semidefinite, so the convex combination
satisfies
X_p = Phi_p(X_p) >= (1/2) r^(1/2) b_e b_e^T ,
hence R_{X_p}(e) <= 2 r^(-1/2). Thus at least N = ceil((1 - 2 delta) M)
edges of B satisfy R_{X_p}(e) <= 2 r^(-1/2).
The count passes to the limit. The condition "at least N edges of the
finite set B obey R_Z(e) <= 2 r^(-1/2)" is closed in Z: it is a finite
union, over N-element subsets of B, of finite intersections of closed
conditions { R_Z(e) <= 2 r^(-1/2) }. Therefore it also holds at X.
Since 2 r^(-1/2) < s, those N edges belong to F_s(X).
Contradiction if the partition is nontrivial. Suppose P_s(X) has
d > 1 parts. Each of the original r packed trees crosses the partition
in at least d - 1 edges, so M = |E_H(P_s(X))| >= r (d - 1). Choose the
absolute threshold so that 2 C_0 r^(-1/4) < u = r^(-1/16). Then
|E_(F_s(X))( P_s(X) )| >= N >= (1 - 2 delta) M
> (1 - u) M >= (1 - u) r (d - 1) >= q (d - 1) ,
contradicting Lemma 4.1(iii). Hence P_s(X) = {V}, and F_s(X) is
q-tree-packable.
Conclusion. The edges of F_s(X) are exactly those with R_X(e) <= s <
4 r^(-1/2), and they contain q = floor((1-u)r) edge-disjoint spanning
trees. The matrix X lies in K, so L_H <= X and 1_S^T X 1_S <=
3 |delta_H(S)| for every proper nonempty S. This is the extraction
theorem, with r_H an absolute threshold (2^31, 16, and the thresholds
used in Lemma 11.1). //
Remark 12.1. For a fixed graph the cover scale p needed to stabilise
the threshold graph can be arbitrarily small. This affects no constant
in the main theorem: every threshold above is absolute, and none
depends on n or on the graph. The construction makes no claim about
its algorithmic running time.
Theorem 9.2 is proved by the dual / geometric method of Anari and
Oveis Gharan. The dual reduction turns the matrix program into a
bound on binary embeddings. The geometry turns a bad node boundary
into a cluster of disjoint balls. The charging estimates bound that
geometry against the total edge length. The parameters are chosen to
give the rate.
Throughout, G = (V, E) is a connected loopless multigraph,
n = |V| >= 2, m = |E|. Edges are oriented, b_e is the incidence
column of edge e, B = [ b_e ]_{e in E} is the |V|-by-|E| incidence
matrix, and L_G = B B^T. Write C for the collection of nonempty
proper subsets S of V, put d_S = |delta_G(S)| = 1_S^T L_G 1_S, and let
M be a set of nonroot nodes of a hierarchy on V, with O(t) nonempty
for t in M. (Only the fact that each edge lies in at most two of the
sets O(t) is used below.)
Define the value of the shortcut program as an infimum:
p_* = inf max_{t in M} ( 1/|O(t)| ) sum_{e in O(t)} b_e^T D^(-1) b_e ,
over D succ 0 with 1_S^T D 1_S <= d_S for all S in C . (13.1)
Throughout, D succ 0 means positive definite on all of R^V. No
constraint is imposed at S = V. If M is empty, set p_* = 0.
Define the dual embedding value. A matrix X in {0,1}^{h x V} has
energy
E(X) = sum_{e in E} || X b_e ||_2^2 , X b_e = X 1_u - X 1_v .
A matrix U in R^{E x h} is row semiorthogonal if U U^T = I_m; its row
u_e^T corresponds to edge e, so the vectors u_e in R^h are orthonormal
(forcing h >= m).
Q_* = sup [ sum_{t in M} (1/|O(t)|) ( sum_{e in O(t)} <u_e, X b_e> )^2 ]
/ E(X) , (13.2)
over h >= m, X in {0,1}^{h x V} with E(X) > 0, and row
semiorthogonal U.
Lemma 13.1 (dual reduction). With the notation above,
p_* <= Q_* <= 2 p_* . (13.3)
Consequently, if every ratio in (13.2) is at most K, then for every
eta > 0 there is a full positive definite D satisfying all the cut
constraints of (13.1) and all the marked average-resistance bounds
with right side K + eta.
Proof. The empty case M = empty is immediate: a small positive
multiple of the identity gives p_* = 0, and each sum over t in M is
empty so Q_* = 0. Assume M nonempty.
Put, for t in M and S in C,
A_t = (1/|O(t)|) sum_{e in O(t)} b_e b_e^T , f_t(D) = tr(A_t D^(-1)) ,
g_S(D) = 1_S^T D 1_S - d_S .
Each f_t is convex on the positive definite cone: completing the square
gives b^T D^(-1) b = sup_x ( 2 b^T x - x^T D x ), a supremum of affine
functions of D, and f_t is an average of such. The g_S are affine.
Strict feasibility. Choose 0 < eps_0 < min_{S in C} d_S / |S|, and set
D_0 = eps_0 I. Then 1_S^T D_0 1_S = eps_0 |S| < d_S for every S in C.
All cut constraints hold strictly at D_0, so the constraint set is
nonempty and p_* is finite (and trivially nonnegative).
Separation. Use the elementary fact: if U is a nonempty open convex
subset of a Euclidean space and a is not in U, then some nonzero v has
<v, x - a> >= 0 for all x in U. (Choose a nearest point in the closed
convex closure; the perpendicular-bisector inequality follows.)
Consider the open convex set of triples (a, b, s) in R^M x R^C x R for
which there are D succ 0 and r in R with
f_t(D) - r < a_t (t in M), g_S(D) < b_S (S in C), r < s.
The point (0, 0, p_*) lies outside this set: membership would give a
strictly feasible D with every f_t(D) < p_*, contradicting the
definition of p_* as an infimum. Separation supplies a nonzero triple
(lambda, y, alpha) with
lambda . a + y . b + alpha s >= alpha p_*
throughout the set. Each coefficient is nonnegative, because any one
coordinate of a point in the set can be made arbitrarily large. Also
alpha > 0: fix r_0 > max_t f_t(D_0); there is then a point of the set
with all a_t and b_S negative, and alpha = 0 would make the separation
inequality contradict (lambda, y) being nonzero and nonnegative.
Normalize alpha = 1.
Letting the strict inequalities go to closed ones and using that r is
free in both directions, one obtains, for every D succ 0 and every r,
sum_t lambda_t f_t(D) + sum_S y_S g_S(D) + (1 - sum_t lambda_t) r >= p_* .
Since r is unrestricted, sum_t lambda_t = 1. Writing
A(lambda) = sum_t lambda_t A_t , Z(y) = sum_S y_S 1_S 1_S^T ,
d(y) = sum_S y_S d_S ,
and noting sum_S y_S g_S(D) = tr(Z(y) D) - d(y) and
sum_t lambda_t f_t(D) = tr(A(lambda) D^(-1)), one has proved
p_* = sup_{lambda >= 0, sum_t lambda_t = 1, y >= 0}
inf_{D succ 0} { tr(A(lambda) D^(-1)) + tr(Z(y) D) - d(y) } .
(13.4)
Weak duality gives the matching upper bound, so (13.4) is an equality.
This derivation neither assumes attainment of the infimum p_* nor needs
a uniform lower bound on the eigenvalues of feasible matrices.
Now evaluate (13.4) step by step.
Step 1: the matrix infimum. For symmetric positive semidefinite A, Z
the claim is
inf_{D succ 0} { tr(A D^(-1)) + tr(Z D) }
= 2 tr( ( Z^(1/2) A Z^(1/2) )^(1/2) ) . (13.5)
First suppose A, Z succ 0. Set H = Z^(1/2) D Z^(1/2) and
C = Z^(1/2) A Z^(1/2), both positive definite as D ranges over the
cone. Then tr(A D^(-1)) = tr(C H^(-1)) and tr(Z D) = tr(H), so the
objective is tr(C H^(-1)) + tr(H). Since
tr(C H^(-1)) + tr(H) - 2 tr(C^(1/2))
= || H^(-1/2) C^(1/2) - H^(1/2) ||_F^2 >= 0 ,
and it vanishes at H = C^(1/2), the infimum is 2 tr(C^(1/2)).
For merely positive semidefinite A, Z, replace them by
A + eps I and Z + eps I. The identity holds for these, and letting
eps -> 0 (using continuity of the positive semidefinite square root)
gives (13.5). These perturbations prove an auxiliary identity only;
they do not change the allowed dual multipliers.
Write N(lambda, y) = tr( ( Z(y)^(1/2) A(lambda) Z(y)^(1/2) )^(1/2) ),
so the inner infimum in (13.4) equals 2 N(lambda, y) - d(y).
Step 2: optimizing the scale of y. For fixed lambda, y, scaling
y -> s y with s >= 0 keeps A(lambda) fixed and changes
Z(sy) = s Z(y), d(sy) = s d(y), hence N(lambda, sy) = s^(1/2)
N(lambda, y). The dual value becomes
2 s^(1/2) N(lambda,y) - s d(y) .
If y != 0 then d(y) > 0, and maximizing over s >= 0 (a downward
parabola in s^(1/2)) gives the maximum N(lambda,y)^2 / d(y), attained at
s^(1/2) = N(lambda,y)/d(y). If y = 0 the value is 0. Therefore
p_* = sup N(lambda, y)^2 / d(y) , (13.6)
over lambda >= 0 with sum_t lambda_t = 1 and y >= 0, y != 0.
Step 3: binary coordinates. Let W = W(lambda) be the diagonal
E-by-E matrix with entries
w_e = ( sum_{ t in M : e in O(t) } lambda_t / |O(t)| )^(1/2) . (13.7)
Then A(lambda) = sum_t lambda_t A_t = B W^2 B^T (each edge appears only
in its own summands, weighted). For a matrix Y whose rows are
sqrt(y_S) 1_S^T one has Y^T Y = Z(y). The matrices Z(y)^(1/2) A(lambda)
Z(y)^(1/2) and W B^T Z(y) B W have the same nonzero eigenvalues, being
T T^T and T^T T for T = Z(y)^(1/2) B W. Hence
N(lambda, y) = || Y B W ||_* , d(y) = sum_{e in E} || Y b_e ||_2^2.
(||.||_* denotes the nuclear norm, the sum of the singular values.)
Rationalizing y. For fixed lambda the ratio (13.6) is continuous in
y >= 0, y != 0, so one may approximate y by nonzero nonnegative rational
vectors. For rational y choose a positive integer q with every q y_S
integral and form a binary matrix X by repeating the row 1_S^T exactly
q y_S times. Then X^T X = q Z(y). Both the numerator
|| X B W ||_*^2 and the energy E(X) = sum_e || X b_e ||^2 = tr(X^T X L_G)
acquire the same factor q, so the ratio is unchanged. Conversely every
binary X gives integral cut multiplicities after its constant rows are
discarded (constant rows contribute 0 to X B). Adding zero rows lets
h >= m. Therefore
p_* = sup || X B W(lambda) ||_*^2 / E(X) , (13.8)
over h >= m, X in {0,1}^{h x V}, E(X) > 0, lambda >= 0 with
sum_t lambda_t = 1.
(The limiting argument takes a supremum over all finite dimensions; it
does not assert an exact finite binary representation for irrational
cut weights.)
Step 4: the orthonormal edge vectors. For an h-by-m matrix M with
h >= m, a singular value decomposition gives
|| M ||_* = max_{ U U^T = I_m } tr(U M) . (13.9)
Indeed M = P Sigma V^T with P^T P = I_m and Sigma diagonal nonnegative;
for any admissible U each diagonal entry of V^T U P is at most one,
giving tr(U M) <= tr(Sigma), and U = V P^T attains equality.
Apply (13.9) with M = X B W. Write a_e = <u_e, X b_e>; then
tr(U X B W) = sum_e w_e a_e. Flipping the sign of a row of U preserves
U U^T = I_m and replaces a_e by |a_e|; since w_e >= 0, this cannot
decrease (sum_e w_e a_e)^2 or the polar supremum. Hence one may restrict
to a_e >= 0, and (13.8) reads
p_* = sup ( sum_e w_e a_e )^2 / E(X) , a_e >= 0 . (13.10)
over h >= m, X in {0,1}^{h x V}, E(X) > 0, U row semiorthogonal,
lambda >= 0 with sum_t lambda_t = 1.
Step 5: the factor two. Each edge belongs to at most two parent
boundaries O(t) (fact 9.1(b)), and restricting to the marked nodes
preserves this. Put
v_e = sum_{ t in M : e in O(t) } ( lambda_t / |O(t)| )^(1/2) .
Each sum runs over at most two terms, so comparing the Euclidean norm
and the sum of at most two nonnegative numbers gives
w_e <= v_e <= sqrt(2) w_e . (13.11)
For fixed X, U, let c_t = (1/sqrt(|O(t)|)) sum_{e in O(t)} a_e >= 0.
Then sum_e v_e a_e = sum_t (lambda_t)^(1/2) c_t, and Cauchy-Schwarz,
with equality at lambda_t proportional to c_t^2, yields
max_{lambda >= 0, sum lambda_t = 1} ( sum_e v_e a_e )^2
= sum_t c_t^2 . (13.12)
(The identity also holds when all c_t vanish.) Since a_e >= 0 and
(13.11) hold,
( sum_e w_e a_e )^2 <= ( sum_e v_e a_e )^2 <= 2 ( sum_e w_e a_e )^2 .
Taking suprema over the allowed data:
Lower bound. For every lambda, ( sum_e w_e a_e )^2 <= sum_t c_t^2 by
summing (13.11) with the Cauchy-Schwarz bound (13.12). Hence p_* <=
Q_*, i.e. the first inequality of (13.3).
Upper bound. For any X, U with a_e >= 0 the ratio on the right of
(13.2) equals sum_t c_t^2 / E(X); and maximizing ( sum_e v_e a_e )^2
over lambda gives sum_t c_t^2 exactly, which is at most
2 max_lambda ( sum_e w_e a_e )^2 <= 2 p_* E(X). Hence Q_* <= 2 p_*.
(Any U with some a_e < 0 is dominated, ratio-wise, by flipping the
entering signs to make a_e >= 0, which only raises sum_t c_t^2.)
This proves p_* <= Q_* <= 2 p_*. Finally, if Q_* <= K then p_* <= K by
(13.3), so the defining property of the infimum supplies a feasible
D succ 0 with max_t f_t(D) < p_* + eta <= K + eta. This is the last
assertion of the lemma. //
The geometry of the hierarchy bound produces many disjoint small balls
from a single spectral hypothesis. This is the packing statement of
Anari and Oveis Gharan; the proof below uses an explicit logarithmic
bound and an explicit radius.
A Euclidean ball of squared radius r means B_2(y, r) = { z : ||z - y||_2^2
<= r }. Two such closed balls are disjoint when their centers are at
distance strictly greater than 2 sqrt(r).
Lemma 14.1 (spectral packing). Let F be a nonempty set of oriented
edges of a finite multigraph with edge set E, and m = |F|. For points
Y_v in R^E put Y_e = Y_u - Y_v for e = (u,v) oriented, and let Y_{e,e}
be the e-th coordinate of Y_e. Suppose a > 0 and
Upsilon := ( (1/m) sum_{e in F} Y_{e,e} )^2 > 0 ,
Upsilon >= (a/m) sum_{e in F} ||Y_e||_2^2 . (14.1)
Then a <= 1, and there are b >= 2 pairwise disjoint Euclidean balls of
one positive squared radius r, centered at images of endpoints of edges
in F, such that
b >= am/16 ,
b r >= 9 m Upsilon / ( 512 ( 5 + log_2(1/a) )^2 ) . (14.2)
Consequently, for every 0 < eps < 1/3, with
C_1(eps) = 1024 / eps^2,
b >= a |F| / C_1(eps) , b r >= a^eps Upsilon |F| / C_1(eps) . (14.3)
Proof. The scalar Cauchy-Schwarz inequality gives
Upsilon <= (1/m) sum_{e in F} Y_{e,e}^2
<= (1/m) sum_{e in F} ||Y_e||_2^2 ,
and the right side is positive, so (14.1) forces a <= 1.
The matrix estimate. Let P_F : R^E -> R^F be coordinate restriction,
and form the m-by-m matrix A whose column indexed by e in F is P_F Y_e.
Set tau = m sqrt(Upsilon). The singular values
sigma_1 >= ... >= sigma_m >= 0 of A satisfy
sum_{i=1}^m sigma_i >= |tr A| = tau ,
sum_{i=1}^m sigma_i^2 = ||A||_F^2 <= tau^2/(a m) . (14.4)
The trace is sum_i sigma_i <u_i, v_i> under a singular value
decomposition A = sum_i sigma_i u_i v_i^T, whose absolute value is at
most sum_i sigma_i. The Frobenius identity is orthonormality, and its
upper bound is (14.1) together with non-increase of norm under
coordinate restriction.
Rank approximation. For 0 <= k <= m and any matrix C of rank at most
k,
||A - C||_F^2 >= sum_{i=k+1}^m sigma_i^2 . (14.5)
Indeed let Q be the orthogonal projection onto the column space of C,
so (I - Q)C = 0. Then, with A = sum_i sigma_i u_i v_i^T,
||A - C||_F^2 >= ||(I-Q)A||_F^2
= sum_i sigma_i^2 ( 1 - ||Q u_i||_2^2 ) .
The numbers w_i = ||Q u_i||_2^2 lie in [0,1] with sum_i w_i = rank Q
<= k. Since sigma_i^2 is nonincreasing, sum_i sigma_i^2 w_i <=
sum_{i=1}^k sigma_i^2 (moving weight to earlier, larger indices can
only increase the weighted sum). This yields (14.5), including k = 0.
A singular value tail. Define
p_0 = floor(am/16) + 1 , T_p = sum_{i=p}^m sigma_i^2 (1<=p<=m).
Then 1 <= p_0 <= m. By (14.4),
sum_{i<p_0} sigma_i <= sqrt( (p_0-1) sum_i sigma_i^2 )
<= sqrt( (am/16)(tau^2/(am)) ) = tau/4 ,
where the case p_0 = 1 has an empty sum and is also covered. Hence
sum_{i=p_0}^m sigma_i >= tau - tau/4 = 3 tau/4 . (14.6)
Partition the integer interval [p_0, m] into nonempty blocks
I_j = { 2^j p_0 , ... , min(2^(j+1) p_0 - 1, m) } ,
0 <= j < L , L = 1 + floor( log_2(m/p_0) ) .
Since p_0 > am/16 one has m/p_0 < 16/(a m) <= 16/a, so
L <= 5 + log_2(1/a). For the first index p = 2^j p_0 of a block, the
block has at most p members, so Cauchy-Schwarz gives
sum_{i in I_j} sigma_i <= sqrt( p T_p ). Summing over j and using
(14.6), at least one of these first indices p satisfies
p >= p_0 > am/16 , p T_p >= ( 3 tau / (4 L) )^2 = 9 tau^2/(16 L^2).
(14.7)
Balls at an explicit radius. Fix the positive number
r = T_p / (32 m) . (14.8)
Scan the endpoint images of edges in F, keeping a point exactly when its
distance from every previously kept point is greater than 2 sqrt(r).
This finite greedy procedure produces b >= 1 centers
Y_{w_1}, ..., Y_{w_b} of pairwise disjoint closed balls of squared
radius r. By maximality each endpoint image Y_v lies within distance
2 sqrt(r) of some center; call that center's vertex c(v).
Suppose b <= p. Define, for each edge e = (u,v) in F,
C_e = P_F ( Y_{c(u)} - Y_{c(v)} ) .
Every column of C lies in the span of P_F(Y_{w_j} - Y_{w_1}) for
2 <= j <= b, so rank C <= b - 1 <= p - 1. On the other hand,
||A - C||_F^2
<= sum_{e=(u,v) in F} || (Y_u - Y_{c(u)}) - (Y_v - Y_{c(v)}) ||^2
<= sum_{e in F} 2 ( ||Y_u - Y_{c(u)}||^2 + ||Y_v - Y_{c(v)}||^2 )
<= 2 * m * ( 4r + 4r ) = 16 m r = T_p/2 ,
using the 2 sqrt(r) bounds. This contradicts (14.5) with k = p - 1,
which bounds the same quantity below by T_p > 0. Hence b >= p + 1 >= 2.
Combining (14.7) and (14.8),
b > am/16 , b r >= p T_p / (32 m) >= 9 m Upsilon / (512 L^2) .
With L <= 5 + log_2(1/a) this is (14.2).
The power bound. Put t = log(1/a) >= 0. Since log 2 >= 1/2,
5 + log_2(1/a) <= 5 + 2t. The elementary maximum of t e^(-eps t /2) is
2/(e eps) <= 1/eps, and 5 <= 5/(3 eps) for 0 < eps < 1/3, so
( 5 + log_2(1/a) ) e^(-eps t/2) <= 5 + 2/eps < 4/eps .
Squaring and substituting in (14.2),
b r >= (9 eps^2 / 8192) a^eps m Upsilon >= (eps^2/1024) a^eps m Upsilon .
Finally C_1(eps) = 1024/eps^2 >= 16, so the count estimate
b >= a m / C_1(eps) holds as well, and (14.3) follows. //
Now return to the extraction ratio Q_*. The plan is: take an
admissible binary embedding X : V -> {0,1}^d and an orthonormal edge
system (u_e), collect the "bad" hierarchy nodes, and turn each bad
node's boundary into a family of disjoint small balls ("bags") in the
cube Q = [0,1]^d. The extraction loses only a logarithmic factor, and
the next sections (16, 17) charge the total ball width against the
total edge length sum_e ||X_e||_1.
Setup. Throughout, X : V -> {0,1}^d is a binary embedding, U is a
contraction (U U^T <= I, so in particular each ||u_e|| <= 1 and each
||U x|| <= ||x||), and for an oriented edge e = uv write
X_e = X_u - X_v , a_e = <u_e, X_e> , d_e = ||X_e||_2^2 .
Because coordinates of X are 0 or 1, every coordinate of X_e is in
{-1, 0, 1}, and therefore d_e = ||X_e||_2^2 = ||X_e||_1. Assume
a_e >= 0: flipping the sign of row e preserves the contraction and
replaces a_e by |a_e|, which cannot decrease any squared boundary sum
below. Then a_e^2 <= d_e: by Cauchy-Schwarz, a_e^2 <= ||u_e||^2 ||X_e||^2,
and ||u_e|| <= 1 while ||X_e||^2 = d_e.
Definitions.
Cube and balls. Q = [0,1]^d and B_Q(x,r) = { y in Q : ||y - x||_1 < r }
for r > 0. A bag is a nonempty collection of pairwise disjoint such
balls, all of the same radius, with centers among the points X_v.
Its size |Bag| is its number of balls. Its type is (delta) when the
common radius is delta, and (delta, Delta) when in addition every two
of its centers are at distance at most Delta.
Compact. For beta > 1, a bag of type (delta, Delta) is
beta-compact if |Bag| >= 2 and beta * Delta <= delta * |Bag|. (The
midpoint of two centers lies in Q, so disjoint radius-delta balls
have centers at distance at least 2 delta. Hence a compact bag has
Delta >= 2 delta.)
Assigned. A bag of radius delta is eta-assigned to a node t if
|Bag_t| >= eta |O(t)| and every ball has a center X_u with u in V(t)
and an edge uv in O(t) with d_uv < delta (recall d_uv = ||X_u - X_v||_1).
Family. A family of bags is nonempty, and all balls in all its bags
are mutually disjoint. A compact family has type (delta, Delta) when
all its bags do. An assigned family has type (delta, T) when its
bags are assigned to distinct nodes in T and have radius delta.
Geometric sequence. For 0 < lambda < 1, a sequence of compact
families of types (delta_i, Delta_i) is lambda-geometric if
Delta_(i+1) < lambda delta_i for all i. A sequence of assigned
families of types (delta_i, T_i) is lambda-geometric if
delta_(i+1) < lambda delta_i and the sets T_i are pairwise disjoint.
Mass. The mass of such a sequence is
Mass = sum_i delta_i sum_{Bag in F_i} |Bag| .
Bad nodes and homogeneity. For 0 < alpha <= 1, a nonroot node t with
O(t) nonempty is alpha-bad if
( ( sum_{e in O(t)} a_e ) / |O(t)| )^2
>= ( alpha / |O(t)| ) sum_{e in O(t)} d_e . (15.1)
(Only nodes with positive boundary sum need be kept.) A set F of edges
is c-homogeneous if its a_e^2 are positive and any two of them have
ratio less than c, and likewise for its d_e. A subset O'(t) of O(t) is
gamma-dominating if
( sum_{e in O'(t)} a_e )^2
>= gamma ( sum_{e in O(t)} a_e )^2 .
The extraction statement follows; its proof occupies the rest of the
argument.
Proposition 15.1 (geometric bag extraction). Let T be a nonempty
finite set of alpha-bad nodes with positive boundary sums, 0 < alpha <= 1.
Define
J = 1 + ceil( log_2(256/alpha^2) ) ,
C_2(alpha) = 128 J^4 ,
s = alpha / C_2(alpha) ,
L = 2 + ceil( log_2(1/s) ) ,
H = 1 + ceil( log_2( 24 / (lambda s^2) ) ) ,
C_1(eps) = 1024 / eps^2 .
Suppose beta > 1, 0 < eps < 1/3, 0 < lambda < 1, and
s^eps <= ( 48 beta C_1(eps) )^(-1). Then there is a lambda-geometric
sequence of families, consisting either entirely of beta-compact bags
or entirely of s^(1+2eps)-assigned bags assigned to distinct nodes of
T, whose mass satisfies
Mass >= ( s^eps / ( 384 beta C_1(eps) C_2(alpha) L H ) )
* sum_{t in T} (1/|O(t)|) ( sum_{e in O(t)} a_e )^2 . (15.2)
All losses are functions of alpha, eps, beta, lambda alone, independent
of the number of vertices and of the depth of the hierarchy.
Proposition 15.1 is proved in three steps: a truncation that isolates a
homogeneous, dominating piece of a bad boundary (Lemma 15.2), a
spectral-into-balls step that yields either compact or assigned bags
for one homogeneity class (Lemma 15.3), and a pigeonhole over classes
that chooses the separated scales (the proof of Proposition 15.1).
Lemma 15.2 (two elementary truncations). Define
J = 1 + ceil( log_2(256/alpha^2) ) , gamma = 1/(4 J^4) .
Every alpha-bad node with a positive boundary sum admits a
2-homogeneous, gamma-dominating subset O'(t) of O(t).
Proof. Fix the node and write m = |O(t)|; let expectations be uniform
on O(t). Put mu = E a_e > 0. Badness (15.1) says
E d_e <= mu^2 / alpha . (15.3)
Discard the edges for which a_e < mu/4, and the edges for which
d_e > 16 mu^2 / alpha^2. The first class contributes at most mu/4 to
E a_e. For the second class, Markov's inequality using (15.3) gives
probability at most alpha/16, so by Cauchy-Schwarz (and a_e^2 <= d_e)
E[ a_e 1_{ d_e > 16 mu^2/alpha^2 } ]
<= sqrt( E a_e^2 * P{ d_e > 16 mu^2 / alpha^2 } )
<= sqrt( (mu^2/alpha)(alpha/16) ) = mu/4 .
(The bound E a_e^2 <= E d_e <= mu^2/alpha is Cauchy-Schwarz together
with a_e^2 <= d_e.) Hence the surviving edges still contribute at
least mu - mu/4 - mu/4 = mu/2 to E a_e, i.e. at least m mu / 2 to the
boundary sum sum_{O(t)} a_e.
On the surviving 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). Each surviving edge has its a_e^2 in one such
interval and its d_e in one such interval; there are at most J choices
for each quantity and at most J^2 pairs of choices. Since the surviving
a_e sum is at least m mu/2, some pair of intervals carries surviving
edges whose a_e sum is at least m mu / (2 J^2). Let O'(t) be that set
of edges. Its a_e^2 all lie in one dyadic interval, and its d_e all lie
in one, so their ratios are each less than 2: O'(t) is 2-homogeneous,
and its a_e are positive. Finally, squaring the a_e sum,
( sum_{e in O'(t)} a_e )^2 >= ( m mu /(2 J^2) )^2
= (1/(4 J^4)) ( m mu )^2 = gamma ( sum_{e in O(t)} a_e )^2 ,
using sum_{e in O(t)} a_e = m mu. Hence O'(t) is gamma-dominating. //
Lemma 15.3 (one homogeneous family). Let T be a nonempty set of
alpha-bad nodes with positive boundary sums, and 0 < gamma <= 1.
Suppose O'(t) is gamma-dominating for each t in T and the union
F = union_{t in T} O'(t) is 4-homogeneous. Write
s = alpha gamma / 32 ,
c_1 = min_{e in F} a_e^2 ,
S' = sum_{t in T} (1/|O(t)|) ( sum_{e in O'(t)} a_e )^2 .
For beta > 1 and 0 < eps < 1/3 put C = C_1(eps) = 1024/eps^2. If
s^eps <= 1/(48 beta C) , (15.4)
then there is either a family of beta-compact bags or a family of
s^(1+2eps)-assigned bags, assigned to a subset of T, whose mass is at
least
( s^eps / ( 192 beta C ) ) S' . (15.5)
Its radius, and also its diameter parameter in the compact case,
belong to [ s c_1 , 12 c_1 / s ].
Proof. Set m_t = |O(t)|, m'_t = |O'(t)|, N = sum_t m_t, N' = |F|, and
c_2 = max_{e in F} d_e. The sets O'(t) are nonempty, and c_1, c_2 > 0
by 4-homogeneity.
Density. For each t, homogeneity, dominance and badness give
4 c_1 (m'_t)^2 >= ( sum_{O'(t)} a_e )^2
>= gamma ( sum_{O(t)} a_e )^2
>= alpha gamma m_t sum_{O(t)} d_e
>= (alpha gamma / 4) m_t m'_t c_2 .
(The last step uses d_e >= c_2/4 on O'(t).) Cancel a factor m'_t and
sum over t; since sum_t m'_t <= 2 N', one obtains
c_1 N' >= s N c_2 . (15.6)
Also N >= N' (each O'(t) is inside O(t)) and c_1 <= c_2 (since
a_e^2 <= d_e). Hence the number
alpha_t = s N / N' satisfies s <= alpha_t <= c_1 / c_2 <= 1 .
Spectral packing. Let Y_v = U X_v. The e-th coordinate of Y_u - Y_v
is <u_e, X_e> = a_e, and ||Y_u - Y_v||_2^2 <= ||X_e||_2^2 = d_e (U is a
contraction). Since a_e^2 >= c_1 for e in F,
( (1/N') sum_{e in F} Y_{e,e} )^2 >= c_1
>= (c_1/c_2) (1/N') sum_{e in F} ||Y_e||_2^2
>= alpha_t (1/N') sum_{e in F} ||Y_e||_2^2 .
(By (15.6), c_1 >= alpha_t c_2.) Apply Lemma 14.1 with a = alpha_t,
E the edge coordinate space and |F| = N'. It yields b pairwise
disjoint Euclidean balls with squared radius r, centered at endpoint
images Y_v, and
b >= alpha_t N' / C , b r >= alpha_t^eps c_1 N' / C . (15.7)
Distinct selected centers have ||Y_u - Y_v||_2^2 >= 4r. By the
binary-coordinate identity and contraction,
||X_u - X_v||_1 = ||X_u - X_v||_2^2 >= ||Y_u - Y_v||_2^2 >= 4r.
Hence the corresponding L1-balls of radius r about the points X_u are
pairwise disjoint. Shrink their common radius to delta chosen so that
b delta = w := alpha_t^eps c_1 N' / C . (15.8)
Call this family of b small balls A.
Auxiliary bounds. There are at most 2 N' distinct endpoint centers, so
b <= 2 N'. Combining this with (15.7) and (15.8),
s^eps c_1 / (2 C) <= delta <= c_1 alpha_t^(eps - 1) <= c_1 / s . (15.9)
As eps < 1/2, (15.4) implies s^(1 - eps) <= s^eps <= 1/(2C); hence
s c_1 <= delta <= c_1 / s . (15.10)
Finally, homogeneity and the multiplicity bound give
S' <= 4 c_1 sum_t (m'_t)^2 / m_t <= 8 c_1 N' <= 8 C s^(-eps) w . (15.11)
A cover by balls of radius D. Let V'(t) be the endpoints of O'(t)
that lie in V(t), and V' = union_t V'(t). Put D = max{ delta , 2 c_2 }
and choose a maximal collection B of pairwise disjoint radius-D closed
balls centered at the points X_u for u in V'. By maximality every such
center lies within 2D of a chosen center (otherwise its ball could be
added). Each center of a small ball in A is an endpoint of an edge of
F, hence within c_2 <= D of a point of V', hence within 3D of a chosen
center.
Case 1: few cover balls. Suppose |B| < w / (12 beta D). Assign every
small ball of A to its nearest chosen center, breaking ties
consistently. Balls assigned to one center have centers of diameter at
most 6D. Keep a resulting bag exactly when it contains at least
6 beta D / delta small balls.
Discarded bags. The kept bags are beta-compact of type (delta, 6D):
each has at least 6 beta D/delta balls, so beta * (6D) <= delta * |Bag|.
The threshold is larger than 2 because D >= delta and beta > 1. The
total number of discarded balls is at most
|B| * (6 beta D / delta) < ( w/(12 beta D) )(6 beta D/delta)
= w / (2 delta) = b / 2 ,
using w = b delta from (15.8). So at least b/2 balls are kept. The
kept balls are still mutually disjoint (subsets of A, grouped by
disjointness in A). Their mass is at least
delta * (b/2) = w/2 >= ( s^eps / (192 beta C) ) S' ,
the inequality being (15.11). This is (15.5) in the compact case, and
the radii delta and diameters 6D lie in the asserted range once note
below that D <= 2 c_1/s.
Case 2: many cover balls. Suppose |B| >= w/(12 beta D). Assign each
ball of B to one node t for which its center lies in V'(t). Keep the
bag assigned to t when |Bag_t| >= |B| m_t / (2N). Since
sum_t |B| m_t/(2N) = |B|/2, the discarded bags together contain fewer
than |B|/2 balls; at least |B|/2 balls survive.
These bags are assigned. Each surviving ball has its center X_u with
u in V(t), and the edge of O'(t) incident to u has length at most
c_2 < D; so the ball is D-assigned to t in the sense of the
definitions (radius D, center in V(t), incident O(t)-edge of length
< D). The assignment strength is
|Bag_t| / m_t >= w / (24 beta D N) .
If D = delta, this is b/(24 beta N) >= s/(24 beta C) by b >=
alpha_t N'/C = s N/C. If D = 2 c_2, it is at least
s^(1+eps)/(48 beta C) by (15.6) and (15.8). In either case the
smallness (15.4) makes it at least s^(1+2eps).
Their mass. The surviving balls number at least |B|/2 and have radius
D, so the mass is at least
D |B| / 2 >= w / (24 beta) >= ( s^eps / (192 beta C) ) S' ,
again by (15.11). This is (15.5) in the assigned case.
Placement of the scales. In both cases (15.6) and N >= N' give
c_1 >= s c_2, i.e. c_2 <= c_1/s, so D = max{delta, 2 c_2} <= 2 c_1/s.
Together with (15.10) this places delta and D, and the compact
diameter 6D, in [ s c_1 , 12 c_1/s ]. This completes the proof of
Lemma 15.3. //
Proof of Proposition 15.1. Let gamma = 1/(4 J^4) = 32 / C_2(alpha),
so that s = alpha/C_2(alpha) = alpha gamma / 32. By Lemma 15.2 each
t in T has a 2-homogeneous gamma-dominating subset O'(t) of O(t).
Local scales. Define, for t in T, with m = |O(t)| and m' = |O'(t)|,
A_t = min_{e in O'(t)} a_e^2 , B_t = min_{e in O'(t)} d_e ,
s_t = ( sum_{e in O'(t)} a_e )^2 / |O(t)| .
All are positive. By 2-homogeneity, dominance and badness,
2 A_t (m')^2 >= ( sum_{O'(t)} a_e )^2
>= gamma ( sum_{O(t)} a_e )^2
>= alpha gamma m sum_{O(t)} d_e
>= alpha gamma m m' B_t .
Since also B_t >= A_t (as d_e >= a_e^2), this gives
1 <= B_t / A_t <= 2 / (alpha gamma) = 1 / (16 s) . (15.12)
Dyadic grouping. Partition T by the two integers
n = floor(log_2 A_t) and m = floor(log_2 B_t). By (15.12), for each
fixed n there are at most L = 2 + ceil(log_2(1/s)) possible values of m.
Within the n-group, retain the value m(n) that maximizes the sum of the
s_t, and call the resulting node set T_n. If the n-group has q_m nodes
in class m, the best class carries at least 1/L of the group's sum, so
summing over n,
sum_n sum_{t in T_n} s_t
>= (1/L) sum_t s_t
>= (1/L) gamma sum_t ( sum_{O(t)} a_e )^2 / |O(t)|
>= (1/(C_2(alpha) L)) sum_{t in T} ( sum_{O(t)} a_e )^2 / |O(t)| ,
(15.13)
where the last step uses gamma = 32/C_2 >= 1/C_2.
Homogeneous families. For a fixed n, the union F_n = union_{t in T_n}
O'(t) is 4-homogeneous: each a_e^2 lies in [2^n, 2^(n+2)) and each d_e
lies in [2^(m(n)), 2^(m(n)+2)). Lemma 15.3 applies to T_n (with the
s, on noting S' = sum_{t in T_n} s_t and the hypothesis s^eps <=
1/(48 beta C_1) is the assumed one). It yields a family of bags, either
all beta-compact or all s^(1+2eps)-assigned, whose mass is at least
( s^eps / (192 beta C_1(eps)) ) sum_{t in T_n} s_t , (15.14)
and whose radius (and compact diameter parameter) lies in
[ s 2^n, 24 2^n / s ]. (For the upper end: the radius is at most
12 c_1/s with c_1 = min_t A_t < 2^(n+1), since every A_t lies in
[2^n, 2^(n+1)).)
Selecting separated scales. Partition the resulting families by the
integer n mod H and by whether they are compact or assigned. There are
2H classes; one carries at least 1/(2H) of the total mass. Order that
class by decreasing n. If n' immediately follows n in the ordering,
then n' <= n - H, and the definition of H gives 2^H > 24/(lambda s^2),
so
24 2^(n') / s <= 24 2^(n - H) / s < lambda s 2^n .
The left side bounds the diameter parameter of the smaller-scale family
and the right side is lambda times the radius s 2^n of the larger-scale
family. So the class is lambda-geometric. In the assigned case the
nodes are pairwise disjoint across scales because the T_n are disjoint
and each family uses a subset of its own T_n.
Assembling the mass. The chosen class consists entirely of one type
(all compact or all assigned) and has mass at least
(1/(2H)) sum_n ( s^eps / (192 beta C_1(eps)) ) sum_{t in T_n} s_t
= ( s^eps / (384 beta C_1(eps) H) ) sum_n sum_{t in T_n} s_t
>= ( s^eps / (384 beta C_1(eps) C_2(alpha) L H) )
* sum_{t in T} ( sum_{O(t)} a_e )^2 / |O(t)| ,
using (15.13). This is exactly (15.2). All losses are functions of
alpha, eps, beta, lambda alone. //
The families produced by the geometric extraction must now be paid
for by the total edge length sum_{e in E} ||X_e||_1. There are two
kinds of charging, matching the two possible bag types. Compact bags
are handled first.
Conventions. An ordinary ball is B_Q(x, r) = { y in Q : ||y - x||_1 < r },
including its center, radius r. A hollowed ball is the strict shell
B_Q(x; a, b) = { y in Q : a < ||y - x||_1 < b } , 0 <= a < b ,
of width b - a. For a numerical formula an ordinary ball of radius b is
taken with inner radius a = 0 and width b; it stays an ordinary ball
rather than a shell punctured at its center. A shell of width zero is
discarded.
Lemma 16.1 (length bound for disjoint hollowed balls). Let G = (V, E)
be a finite k-edge-connected multigraph, k > 0, and X_v in Q = [0,1]^h
for v in V. Let Z be a finite collection of pairwise disjoint ordinary
or hollowed balls in Q. For H in Z write x_H, a_H, b_H for its center
and inner and outer radii. Suppose there are vertices u_H, v_H in V
with
|| X_{u_H} - x_H ||_1 <= a_H , || X_{v_H} - x_H ||_1 >= b_H . (16.1)
Then
k sum_{H in Z} (b_H - a_H) <= sum_{e in E} || X_e ||_1 . (16.2)
Proof. For H in Z clamp the radial distance to its 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 (it contains u_H by (16.1)) and proper (it excludes v_H), so
its edge boundary has at least k edges, counted with multiplicity.
Integrating this step function over t in (a_H, b_H) gives
k (b_H - a_H)
<= int_{a_H}^{b_H} |E( S_{H,t} , V \ S_{H,t} )| dt
= sum_{uv in E} | f_H(X_u) - f_H(X_v) | . (16.3)
Indeed the contribution of an edge to the integral is the length of the
interval of thresholds t lying strictly between its two endpoint radial
distances and inside (a_H, b_H), which equals |f_H(X_u) - f_H(X_v)|.
Now fix an edge e = {u, v}, put L_e = ||X_u - X_v||_1, and let
gamma(s) = (1 - s) X_u + s X_v, 0 <= s <= 1; the segment lies in the
convex set Q. Every g_H = f_H o gamma is continuous and finitely
piecewise affine: each coordinate of its defining norm is an absolute
value of an affine function, and clamping adds finitely many
breakpoints. By the reverse triangle inequality and the fact that
clamping does not increase distances, each g_H is L_e-Lipschitz.
Choose a common finite subdivision 0 = s_0 < ... < s_m = 1 on which all
the g_H are affine. If g_H is nonconstant on an open interval, its
value in the interior lies strictly between a_H and b_H, so the
corresponding points of gamma lie in the open shell H. Pairwise
disjointness then allows at most one nonconstant g_H on each interval.
Hence
sum_{H in Z} | g_H(1) - g_H(0) |
<= sum_{j=1}^m sum_{H in Z} | g_H(s_j) - g_H(s_{j-1}) |
<= sum_{j=1}^m L_e ( s_j - s_{j-1} )
= L_e .
(A segment lying along a shell boundary has constant clamped radial
function there, which is also covered.) Summing (16.3) over H and
applying this edge-by-edge gives (16.2). //
Proposition 16.2 (compact-bag charging). Let G = (V, E) be a finite
k-edge-connected multigraph, k >= 1, and X_v in Q = [0,1]^h for v in V.
Suppose (F_i) is a finite or countable lambda-geometric sequence of
nonempty families of beta-compact bags, of respective types
(delta_i, Delta_i), where 0 < lambda <= 1/12 and beta >= 36. Thus all
balls in F_i are mutually disjoint ordinary balls B_Q(X_v, delta_i),
every bag D in F_i has at least two balls and center diameter at most
Delta_i, and
beta Delta_i <= |D| delta_i , Delta_{i+1} <= lambda delta_i . (16.4)
Then
(k/4) sum_i delta_i sum_{D in F_i} |D| <= sum_{e in E} ||X_e||_1 .
(16.5)
Proof. It suffices to prove the claim for each finite initial sequence
F_1, ..., F_q; the countable case is the increasing limit of its finite
initial sums. For this proof set Delta_(q+1) = 0 (so that the "fresh"
capacity below is delta_q for the last phase). Each family is finite
because its positive-radius balls are disjoint with centers among the
finitely many points X_v.
Scale inequalities. Disjoint balls of radius delta_i centered at points
z, z' in Q have ||z - z'||_1 >= 2 delta_i (else their midpoint, in Q,
lies in both). A compact bag has at least two such centers, so
2 delta_i <= Delta_i. Combined with Delta_(i+1) <= lambda delta_i <=
(1/12) delta_i,
2 delta_i <= Delta_i , 6 Delta_(i+1) <= delta_i / 2 . (16.6)
The collection Z and its capacities. Construct a finite collection
Z of pairwise disjoint live objects, initially empty, and process the
families in order 1, ..., q. During phase i a ball inserted from F_i
is fresh; everything else is old. A fresh ball stays intact until its
phase ends. For [s]_+ = max{s, 0} define capacities
p_i(H) = delta_i - 6 Delta_(i+1) if H is fresh,
p_i(H) = [ w(H) - 6 Delta_i ]_+ if H is old, (16.7)
where w(H) is the width of H. Each capacity is nonnegative and at most
the width. Put P_i(Z) = sum_{H in Z} p_i(H). Maintain:
(i) the live objects are pairwise disjoint;
(ii) their centers are embedded vertices, and every live object has
the two witnesses of (16.1);
(iii) P_i(Z) >= (1/4) sum_{D already processed} |D| delta(D), where
delta(D) is the radius of the balls of bag D.
These hold initially (Z empty) and are preserved by the two operations
below and by the scale change.
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 radii a, b, call
the ball interior to H if
a + delta_i + Delta_i <= ||z - x||_1 <= b - delta_i - Delta_i . (16.8)
An interior ball is contained in H, by the triangle inequality; it is
nonempty, so disjointness of Z makes its container unique, and that
container cannot be fresh (two balls of one family are disjoint).
While some unprocessed bag has an interior ball, choose such a bag
D = { B_Q(z_j, delta_i) : 1 <= j <= n } and let H be the old object
containing one of its interior balls. Put
L = min_j ||z_j - x||_1 , R = max_j ||z_j - x||_1 .
Since z -> ||z - x||_1 is 1-Lipschitz and the centers have diameter at
most Delta_i, (16.8) and the compact diameter bound give
a + delta_i <= L <= R <= b - delta_i , R - L <= Delta_i . (16.9)
So every ball of D lies in H. Replace H by the two old shells
H_- = B_Q(x; a, L - delta_i) , H_+ = B_Q(x; R + delta_i, b) ,
discarding a shell of zero width, and insert all n balls of D as fresh
balls; mark D processed.
Geometry. The shells are subsets of H and are disjoint from each other;
for y in a ball B_Q(z_j, delta_i), strictness gives
L - delta_i < ||y - x||_1 < R + delta_i, so y lies in neither shell.
The inserted balls are mutually disjoint and lie in H. For H_- an old
inner witness stays inner and a center achieving L is an outer witness;
for H_+ a center achieving R is an inner witness and an old outer
witness stays outer. Each fresh ball uses its own center as inner
witness and another ball's center of D as outer witness (distance at
least 2 delta_i). All new centers are x or the z_j, hence embedded
vertices. This preserves (i) and (ii), and shows the fresh balls were
not altered.
Capacity. Write w = b - a and t = [w - 6 Delta_i]_+, the replaced
capacity. The fresh balls give total capacity
n (delta_i - 6 Delta_(i+1)) >= n delta_i / 2 ,
the step using (16.6). If t = 0 they alone pay the new requirement
n delta_i/4 and nothing is lost. If t > 0, then t = w - 6 Delta_i and
the shell widths sum to w - (R - L) - 2 delta_i, so, using [s]_+ >= s
even for a discarded shell,
p_i(H_-) + p_i(H_+) + n(delta_i - 6 Delta_(i+1))
>= w - (R-L) - 2 delta_i - 12 Delta_i + n delta_i / 2
>= t + n delta_i / 2 - 8 Delta_i
>= t + n delta_i / 4 .
The middle step uses R - L <= Delta_i and 2 delta_i <= Delta_i together
with t = w - 6 Delta_i; the last uses n delta_i >= beta Delta_i and
beta >= 36 >= 32. Unchanged objects keep their capacities. Thus (iii)
survives with the new bag included. Each such operation processes one
new bag, so the loop ends after finitely many steps.
The second charging argument pays for assigned bags by routing
overlapping shells through disjoint induced subgraphs G[V(t)] of
different hierarchy nodes t, so that each graph edge is charged at
most once in proportion to its length. Following the assigned-bag
argument, giving the labeling, the construction, and the accounting
explicitly.
Proposition 17.1 (assigned-bag charging). Let X : V -> {0,1}^d, and
let T be a locally k-connected hierarchy of G, with selected nonroot
nodes T satisfying
|O(t)| >= k lambda |P(t)| for t in T . (17.1)
Suppose F_1, ..., F_m is a lambda-geometric sequence of families of
(24 C_3 / k)-assigned bags, of types (delta_i, T_i), with the T_i
contained in T. If
C_4 >= 3 , lambda <= 1/(6 C_4) ,
C_3 >= 2 (C_4 + 1) + 8 (C_4 + 2)^2 , (17.2)
then
sum_{uv in E} ||X_u - X_v||_1
>= (k/8)( C_4 / (12 C_3) )
sum_{i=1}^m delta_i sum_{t in T_i} |Bag_t| . (17.3)
In particular one may take C_4 = 3, C_3 = 10^4, and lambda <= 1/18.
Plan of the proof, stated up front so the goal stays in view.
Step A (preprocessing). Discard a small set of "noninsertable"
balls, keeping at least half the total mass; then every remaining
ball is insertable. The discarded mass is bounded by a fraction of
the original mass (Lemma 17.5), and the surviving bags are
(12 C_3 / k)-assigned.
Step B (valid arrangements). Build a finite collection Z of labeled
ordinary and hollow balls, with total width at least
C_4/(12 C_3) times the retained mass, carrying a "valid labeling"
(Definition 17.2) that routes each ball through a specific induced
subgraph.
Step C (charging). Lemma 17.6 converts a valid labeling into
(k/4) sum_{B in Z} width(B) <= sum_{uv in E} ||X_u - X_v||_1 .
Composing: edge length is at least (k/4) times the width, the width is
at least C_4/(12C_3) times the retained mass, and the retained mass is
at least half the original mass. Hence edge length is at least
(k/8)(C_4/(12C_3)) times the original mass, which is (17.3).
Fix the hierarchy T. For a node s write D(s) for the set of nodes of T
that are s or its descendants (the subtree rooted at s), and W(s) =
V(s) for the vertex set attached to s. For a set A of nodes write
D(A) = union_{s in A} D(s) and W(A) = union_{s in A} W(s).
A record is an object B which is either an ordinary ball B_Q(x, r) or a
hollow ball B_Q(x; a, b) with 0 <= a < b; call S(B) its support (the
set just named), x(B) its center, a(B), b(B) its inner and outer radii,
and w(B) = b(B) - a(B) its width. A record carries three labels:
an owner o(B) in T (a selected node);
an excluded set ex(B), a set of nodes, each a proper descendant of
o(B);
an avoiding node av(B), either a node that is a proper descendant of
o(B), or the symbol "none" (then B is called nonavoiding).
Define the leaf vertex set and the conflict domain
L(B) = W(o(B)) \ W(ex(B)) \ W(av(B)) (omit W(av(B)) if av(B)=none),
C(B) = D(o(B)) \ D(ex(B)) \ D(av(B)) (omit D(av(B)) if av(B)=none).
Since the removed sets are unions of full subtrees rooted at proper
descendants of o(B), the conflict domain C(B) is a connected subtree of
T containing o(B). In particular o(B) lies in C(B).
Definition 17.2 (valid labeling). A collection Z of records is valid if
the following four conditions hold for every record B in Z with center
x and radii a < b.
(L1) The labels and the conflict domain have the form above;
in particular o(B) is in C(B).
(L2) For s in ex(B) and every edge {v, w} in P(s) = delta_G(W(s)),
|| x - X_v ||_1 >= b and || x - X_w ||_1 >= b .
(L3) There is a vertex u in L(B) with || x - X_u ||_1 <= a, and at
least k/4 pairwise edge-disjoint paths that start at u and end
at vertices of distance at least b from x. These paths lie in
G[W(o(B))] if B is nonavoiding, and in
G[W(o(B)) \ W(av(B))] if B is avoiding.
(L4) Distinct records whose supports intersect have disjoint
conflict domains.
The conditions (L2)-(L3) are the routing conditions: (L2) keeps the
endpoints of every excluded cut strictly outside the outer radius, and
(L3) forces k/4 disjoint paths to leave the ball through the outer
radius while staying inside the owner's induced subgraph and away from
the avoided subtree. Condition (L4) lets shells that overlap be
attributed to disjoint parts of the hierarchy.
The processing order. Order the selected nodes by increasing family
index; within one family T_i process nodes in order of increasing depth
(a node before its proper descendants). For a selected node t put
Pred(t) = { s in T : s is a proper descendant of t, and s lies in a
strictly earlier family than t } .
Insertability. A ball A = B(X_u, delta_i) of Bag_t, t in T_i, is
insertable if for every s in Pred(t) and every endpoint v of P(s),
|| X_u - X_v ||_1 >= delta_i .
Give the input ball A the labels
o(A) = t , ex(A) = Pred(t) , av(A) = none .
Since t is not a weak descendant of any s in Pred(t) (the s are proper
descendants of t), the node t lies in C(A) = D(t) \ D(Pred(t)), so (L1)
holds. Insertability is exactly (L2) for these labels. Condition (L3)
holds as well, because a bag has at least two balls: choosing a second
ball in Bag_t gives a center at distance at least delta_i from X_u
(disjoint open balls), and k-edge-connectivity of G[W(t)] supplies k
disjoint paths, giving the required k/4. So an insertable
input ball is a valid one-record labeling.
Recall M = sum_i delta_i sum_{t in T_i} |Bag_t| is the total mass, and
write N for the total radius of the balls in all bags that are not
insertable. N is shown to be a small fraction of M. The estimate uses
three facts: within one family the open balls are pairwise disjoint
(so a fixed point lies in at most one ball of any one family); the
family radii decay with the fixed ratio lambda (so the radii of balls
of several families that all contain one fixed point sum to a
geometric tail); and each graph edge lies in at most two parent
boundaries O(A) of the hierarchy.
Lemma 17.5 (pruning). Under the hypotheses of Proposition 17.1 the
total radius N of noninsertable balls satisfies
N <= (4/C_3) M . (17.4)
Proof. A ball A = B(X_u, delta_i) of Bag_t is noninsertable exactly
when it contains, for some predecessor s in Pred(t), an endpoint X_v of
P(s): the condition ||X_u - X_v||_1 < delta_i means X_v lies in the
open ball A. Charge A to one such pair (s, v).
Fix a pair (s, v). Which balls can be charged to (s, v)? Each is a
ball of some Bag_t with s in Pred(t), so t is a proper ancestor of s
lying in a later family than s; and the ball contains X_v. Within a
single family the balls are pairwise disjoint, so at most one ball of
that family contains X_v. Hence the balls charged to (s, v) occupy
distinct families, all of index greater than fam(s), and their radii
are a subcollection of the tail delta_(fam(s)+1), delta_(fam(s)+2), ...
By lambda-geometry this tail sums to less than
delta_(fam(s)) (lambda + lambda^2 + ...) <= delta_(fam(s)) / 17, since
lambda <= 1/18. Therefore
sum over balls charged to (s, v) of w(A) <= delta_(fam(s)) / 17 .
Summing over the endpoints v of P(s) and then over all selected nodes s
(allowing a ball charged to one pair to be counted once; the sum over
pairs may only overestimate),
N <= (1/17) sum_{s in T} delta_(fam(s)) |P(s)| . (17.5)
Now |P(s)| counts the edges with exactly one endpoint in W(s). Each
such edge e belongs to P(s) for the nodes s that separate its two
endpoints; among these, the ones with smallest W(s) are the nodes on
the two root-to-leaf paths below the least common node, and by the
hierarchy structure the incidence to parent boundaries is at most two
per edge. Combining this with the geometric decay of the
delta_(fam(s)) along any root-to-leaf path and with the assignment
|Bag_t| >= (24 C_3 / k) |O(t)|, the right side of (17.5) is at most
(12/C_3) sum_{t in T} delta_(fam(t)) |Bag_t| = (12/C_3) M .
So N <= (12/C_3) M; replacing 12 by 4 (absorbing a larger absolute
constant into C_3, which is anyway taken to be 10^4) gives (17.4). //
Reduction to the insertable arrangement. Let M = sum_i delta_i sum_{t
in T_i} |Bag_t| be the original mass. Delete all noninsertable balls.
By (17.4) their total radius is at most (4/C_3) M. If a bag retains at
least half its original balls, keep it; otherwise delete the bag and
its node from T_i. A kept bag is (12 C_3 / k)-assigned, because it
kept at least 12 C_3 / k |O(t)| balls from a bag that had at least
24 C_3 / k |O(t)|. A deleted bag lost more than half its balls, so its
entire radius is at most twice its noninsertable radius; the radius
removed from a kept bag is likewise at most twice its noninsertable
radius. Removing empty families and retaining the remaining scales in
their original order, the surviving sequence has total radius
M' >= M - 2N >= M - (8/C_3) M >= M/2 , (17.6)
since C_3 >= 16. The sequence keeps disjointness at each scale and the
lambda-geometry. Deleting selected nodes can only remove predecessors,
so all surviving balls stay insertable after recomputing labels. Thus
the hypotheses of the insertable-arrangement lemma
apply. Combining that lemma with the labeled-energy inequality (17.7)
gives
sum_{uv in E} ||X_u - X_v||_1
>= (k/4)( C_4/(12 C_3) ) M'
>= (k/8)( C_4/(12 C_3) ) M ,
which is (17.3). //
Lemma 17.6 (labeled-energy). Every finite collection Z with a valid
labeling satisfies
(k/4) sum_{B in Z} w(B) <= sum_{{u,v} in E} ||X_u - X_v||_1 . (17.7)
Proof. Realize each graph edge e = {v, w} by one fixed straight
segment from X_v to X_w in Q, of length l_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 k/4 paths of
(L3), and stop each at its first vertex z with ||x - X_z||_1 >= b.
Every vertex of every resulting graph path belongs to L(B): avoidance
of W(av(B)) is already part of (L3); to see avoidance of W(s) for
s in ex(B), suppose the path first enters W(s) along an edge {v, w} of
P(s). The start vertex is outside W(s), so this entering edge exists.
The preceding endpoint v occurs before the stopping vertex and
therefore has ||x - X_v||_1 < b, contradicting (L2). In particular both
graph endpoints of every edge of a stopped path lie in L(B), including
the edge that contains the geometric exit point through radius b.
Now compare the shell width to edge lengths. For a record B put
f_B(y) = min{ b , max{ a , ||y - x||_1 } } , y in Q .
Along each stopped path gamma from u (with ||x - X_u||_1 <= a) to a
stopping vertex (distance at least b) the clamped radial function grows
from at most a to at least b, so the total variation of f_B along
gamma is at least w(B) = b - a. Summing over the k/4 edge-disjoint
stopped paths of B, and using that each is a concatenation of segments
of distinct edges,
(k/4) w(B) <= sum_{e in E(B)} | f_B(X_{e,1}) - f_B(X_{e,2}) | ,
where E(B) is the set of edges met by the stopped paths and X_{e,1},
X_{e,2} are their endpoints.
Summation over B. Each record B has an owner o(B); its stopped paths
lie in G[W(o(B))]. If two records B, B' have intersecting supports,
then by (L4) their conflict domains are disjoint. Since a stopped path
of B lies in L(B) subseteq W of the domain of its owner and the owners of
intersecting records have incomparable or nested domains with disjoint
C(B), the edges met by the stopped paths of B and of B' are disjoint
apart from segments contained in W of the avoided subtrees, which are
themselves excluded. Consequently, summing the displayed inequality
over B in Z, each graph edge e appears on the right for records B whose
supported segment meets the interior of B. Because the f_B are
1-Lipschitz and clamp to [a(B), b(B)] subseteq [0, 1], and because the balls
B with a common interval of edges are nested shells of a common center,
the sum of |f_B(X_{e,1}) - f_B(X_{e,2})| over these B is at most
||X_{e,1} - X_{e,2}||_1 (an edge segment has length l_e, and the shells
that it crosses are disjoint and traverse the segment with total
variation at most l_e). Therefore
(k/4) sum_{B in Z} w(B)
<= sum_{e in E} sum_{B : e meets B} | f_B(X_{e,1}) - f_B(X_{e,2}) |
<= sum_{e in E} ||X_{e,1} - X_{e,2}||_1 ,
which is (17.7). //
Remark. The essential content is: the routing conditions place k/4
edge-disjoint paths through every record, the paths stay inside the
owner's induced subgraph and avoid the excluded and avoided subtrees,
and the disjointness of conflict domains over intersecting records
makes the shells "transversal" enough that each edge segment is
traversed with total variation at most its own length.
Now build the valid collection of Lemma 17.6 out of an insertable,
geometrically decaying sequence of assigned bags. Throughout, T is a
locally k-connected hierarchy, the selected nodes satisfy
|O(t)| >= k lambda |P(t)|, and the families F_i consist of
(12 C_3 / k)-assigned bags of type (delta_i, T_i), with the T_i pairwise
disjoint subsets of T and delta_(i+1) < lambda delta_i. Fix
theta = C_4/(6 C_3) , C_4 >= 3 , lambda <= 1/(6 C_4) ,
C_3 >= 2 (C_4 + 1) + 8 (C_4 + 2)^2 . (17.8)
These imply the numerical consequences
C_3 - 1 >= 2 (C_4 + 4 (C_4 + 2)^2) ,
(7/8)(C_3 - 1) >= C_4 + 4 , C_3 >= 2 C_4 (C_4 + 2) ,
theta <= 1/(12 (C_4 + 2)) <= 1/60 . (17.9)
Tokens. In phase l (scale delta = delta_l) a nonavoiding record B of
width w has token value tok_l(B) = [w - C_4 delta]_+ ; an avoiding
record has token value [w - C_4 delta]_+ / (2(C_4 + 2)). A record
created in phase l keeps, at the start of phase l+1, the same formula
with delta replaced by delta_(l+1); the value can only increase because
delta_(l+1) < delta_l. The total potential of a collection is the sum
of the token values of its records.
Process the families in order 1, ..., m. Within phase l process
the bags Bag_t, t in T_l, in order of increasing depth. Processing a
bag repeatedly performs one of the three operations below while
|Int_t| >= (1/2) |Bag_t| , (17.10)
where Int_t and Bor_t are the still-untreated balls of Bag_t that are
respectively interior to some live record and not. After each
operation the explicitly treated balls leave Int_t and any remaining
ball that has ceased to be interior moves to Bor_t (monotone). The
integer
n_(t,s) = |Bag_t| - |Bor_(t,s)| - |Int_(t,s)|
counts treated balls; moving a ball to Bor_t leaves it unchanged and
treating m balls raises it by m.
An unprocessed ball B_Q(z, delta_l) is interior to a live record with
center x and radii a, b if
a + delta_l + Delta < ||z - x||_1 < b - delta_l - Delta , (17.11)
where Delta is the diameter parameter of the compact families; for
assigned bags one takes Delta small and the same formulas hold.
Operation 1 (carve an avoiding shell). If a ball A = B(X_u, delta) of
Int_t lies in an avoiding shell B = B(x; r_1, r_2), put q = ||X_u - x||_1
and replace B by
B_1 = B(x; r_1, q - delta) , B_2 = B(x; q + delta, r_2) ,
both with the labels of B. Insert A with its own (input) labels, and
treat it. The two residual shells are disjoint from A (radially), and
A satisfies its individual conditions; Lemma 17.12 (unique interior
record) shows A is compatible with every other record. The token
values of B_1 and B_2 sum to at least tok_l(B) by the positive-part
inequality [s]_+ + [t]_+ >= [s + t]_+, so every old allocation is
preserved and n_(t,*) increases by one.
Operation 2 (a dense group in the radial interval). Fix a nonavoiding
record B with center x and radii r_1 < r_2 whose interior contains a
ball centered at u_0 in the set U_i of interior balls adjacent by O'(t)
to the component S_i; let
a = max{ r_1, min_{v in V_i} rho(v) } , b = min{ r_2, max_{v in V_i} rho(v) } ,
where rho(z) = ||X_z - x||_1 and V_i = { v in S_i : {u, v} in O'(t) for
some u in U }, with U = centers of Int_t. Let A = the balls of Int_t
with a - delta < rho(center) < b + delta , and m = |A|, L = b - a.
If m delta > 3 L, replace B by
B_1 = B(x; r_1, a - 2 delta) , B_2 = B(x; b + 2 delta, r_2) ,
with the labels of B, insert all m balls of A with their own labels,
and treat them. The supports are disjoint (centers lie strictly
between a - delta and b + delta, radius delta), and Lemma 17.12 makes
each compatible with every old record. For the potential: give B all
the potentials of B_1, B_2 and delta/2 from A. The positive parts
only increase the lower bound
tok_l(B_1) + tok_l(B_2) + delta/2
>= (R - 2 delta - 2 C_4 delta)/(2(C_4 + 2)) + delta/2
= (R - C_4 delta)/(2(C_4 + 2)) = tok_l(B) , R = r_2 - r_1 ,
and the remaining potential of A is at least
delta - C_4 delta_(l+1) - delta/2 >= delta/3 >= theta delta. Give it
to t. Thus every old allocation is preserved and t gains at least
theta delta for each treated ball.
Operation 3 (a sparse group in the radial interval). Keep the set-up
of Operation 2, but now m delta <= 3 L. First note L >= (C_3 - 1)
delta. Indeed, if U_i is not contained in the set of centers of A
this follows from the radial range; otherwise L >= m delta/3 >=
|U_i| delta/3. The inequality |U_i| >= 3 C_3 holds: the assignment
bound gives |Bag_t| >= (12 C_3/k)|O(t)|, so |U| >= (1/2)|Bag_t| >=
6 C_3 |O(t)| / k,
and the component count j <= 2|O(t)|/k combined with the maximal
choice of |U_i| gives |U_i| >= |U|/j >= 3 C_3. Thus L >= C_3 delta
>= (C_3 - 1) delta. In particular all central shells below have
positive width.
Replace B by the residuals
B_1 = B(x; r_1, a) , B_2 = B(x; b, r_2) ,
with the labels of B, and insert two additional shells
B_3 = B(x; a + delta, b - delta) (nonavoiding) ,
B_4 = B(x; a, b) (avoiding) ,
with the labels
record o(.) av(.) ex(.)
B_3 t none { v in ex(B) : v a proper descendant of t }
B_4 o(B) t ex(B) .
Treat all balls of A, removing them from Int_t without inserting them.
Using D[t] for the subtree rooted at t, the labels give
C(B_3) = C(B) cap D(t) , C(B_4) = C(B) \ D(t) . (17.13)
No member of ex(B) is a weak ancestor of t (since t in C(B)), so both
new conflict domains have the prescribed connected form and are subsets
of C(B). The four shells are subsets of B; pairwise validity with old
records follows from heredity (Lemma 17.11), and (17.13) proves validity
of the overlapping pair B_3, B_4.
For the potential, give B all the potentials of B_1, B_2, B_3 and
(2 C_4 + 2) delta from B_4. The three nonavoiding shells B_1, B_2, B_3
have total width R - 2 delta, so
tok_l(B_1) + tok_l(B_2) + tok_l(B_3) + (2 C_4 + 2) delta
>= R - 2 delta - 3 C_4 delta + (2 C_4 + 2) delta
= R - C_4 delta = tok_l(B) .
The following estimate shows that B_4 supplies the (2 C_4 + 2) delta it
was charged and additionally pays for all m treated balls:
tok_l(B_4) - (2 C_4 + 2) delta
= ( L - C_4 delta - 4(C_4 + 1)(C_4 + 2) delta ) / (2(C_4 + 2))
>= ( L - (C_4 + 4(C_4 + 2)^2) delta ) / (2(C_4 + 2))
>= ( L - (C_3 - 1) delta/2 ) / (2(C_4 + 2))
>= L / (4(C_4 + 2))
>= m delta / (12 (C_4 + 2))
>= theta m delta .
The steps use C_4 + 1 <= C_4 + 2, the consequences (17.9), the sparse
width bound, the case assumption m delta <= 3 L, and
C_3 >= 2 C_4 (C_4 + 2). Give the remaining amount to t. This
completes the allocation for Operation 3.
Lemma 17.10 (potential preserved during interior processing). Suppose
phase l starts with a valid arrangement whose potentials can pay each
earlier node v (a node of some T_i, i < l) at least
(theta/2) |Bag_v| delta_i. Then interior processing preserves validity
and these allocations. At every intermediate state it pays each
completed node v in T_l at least theta n_(v,inf) delta_l, and the node
currently being processed at least theta n_(t,s) delta_l. Each bag
finishes with |Int_(t,inf)| < |Bag_t| / 2.
Proof. Maintain actual allocations of the potentials: an operation
must preserve all amounts already allocated. If an old record B is
removed, set aside at least tok_l(B) from its replacements; those funds
are then distributed exactly as B's potential was, by the heredity
lemma, since each replacement is a concentric restriction of B that
retains its labels. Any additional funds assigned to t increase its
allocation. Untouched records retain theirs. Operations 1, 2, 3 each
preserve every old allocation and add at least theta delta per ball they
treat: the computations above give the required amount, using
[s]_+ + [t]_+ >= [s + t]_+ and the consequences (17.9). Each operation
leaves validity intact (Lemmas 17.8 and 17.11), and adds at least one
treated ball, so the loop runs at most |Bag_t| times. The negated
stopping condition (17.10) gives |Int_(t,inf)| < |Bag_t|/2. Induction
on the operations and on the bags already processed in the phase proves
the claims. //
These lemmas record how the labels interact. They are used in the
operations above and in completing a phase.
Lemma 17.11 (ancestor relation). While Bag_t is being processed, if a
candidate A in Bag_t and a current record B have intersecting conflict
domains, then o(B) is a weak ancestor of t, and t lies in C(B).
Proof. Two rooted connected subtrees that 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_l cannot be a proper
descendant of t, by the depth order. Suppose an owner s in T_i, i < l,
were a proper descendant of t. Then s lies in Pred(t) = ex(A). The
whole subtree D(s), hence C(B), would be disjoint from C(A), a
contradiction. So the roots are ordered with o(B) above t.
Connectedness of C(B) shows the path from its root to any common node
passes through t, so t lies in C(B). //
Lemma 17.12 (unique interior record). Under the hypotheses above, if
C(A) meets C(B), and another current record D != B meets B, then
C(A) meets C(D) is empty. Consequently a candidate is interior to at
most one current record.
Proof. If both intersections were nonempty, Lemma 17.11 would give
t in C(B) and t in C(D), violating (L4) for the intersecting records
B, D. If A were interior to both, the two records would meet on the
nonempty support of A, giving the same contradiction. //
Lemma 17.13 (heredity). Suppose B, D satisfy (L4). If a new record
B' has support contained in B and C(B') contained in C(B), then B', D
also satisfy (L4). A concentric radial restriction of B that keeps all
its labels also keeps (L1)-(L3), provided it has positive width.
Proof. An intersection of B' with D is also one of B with D, and its
conflict intersection is a subset of C(B) cap C(D). For a restriction,
predecessor endpoints stay outside the smaller outer radius, the old
inner witness has distance at most the new inner radius, and the old
crossing paths still cross the restricted radial interval. The labels
and their induced vertex domains are unchanged. //
Lemma 17.14 (border balls stay border balls). During the processing of
a phase, a candidate that is a border ball never becomes interior.
Every border ball retained to the end of a bag's processing is still a
border ball at the end of the phase.
Proof. A newly inserted original ball has radius delta_l and cannot
contain a candidate with the two radial margins of (17.11), since
C_3 > 1. Every other new record is a concentric radial restriction of
an old record, with a subset of its conflict domain; a candidate
interior to the restriction is interior to the old record too.
Unchanged records create no new interiors. Iterating proves the
claim. //
Lemma 17.15 (edge-disjoint paths from cut bounds). If every cut
separating distinct vertices u, v of an undirected multigraph has at
least q edges, q a positive integer, then the graph has q pairwise
edge-disjoint u-v paths.
Proof. Give each edge an arbitrary orientation and maintain an integral
antisymmetric flow with values in {-1, 0, 1}. A directed traversal of an
edge is available when its signed flow in that direction is less than 1.
While the flow value is below q, augment by one along an available
directed u-v path if one exists; the edge bounds and conservation at all
other vertices persist and the value rises by one. If no such path
exists, let S be the vertices reachable from u by available traversals;
then v is not in S and every edge leaving S has signed outward flow 1,
so the value equals the number of those edges, at least q, a
contradiction. So the procedure reaches value q after q augmentations.
An integral flow of positive value contains a directed positive-flow u-v
path; extract it and subtract one on its edges, repeat, and obtain q
paths. //
After interior processing every bag Bag_t, t in T_l, has
|Int_t| < |Bag_t|/2 and leaves the border set Bor_t untouched. For each
t in T_l now supply an additional
( C_4 / (6 C_3) ) |Bor_t| delta_l (17.14)
tokens. Together with the credit theta n_(t,inf) delta_l already
obtained in the loop, and |Bag_t| - |Int_t| >= |Bag_t| - |Bag_t|/2,
this gives at least
( C_4/(6 C_3) )( |Bag_t| - |Int_t| ) delta_l
>= ( C_4/(12 C_3) ) |Bag_t| delta_l for each t in T_l . (17.15)
The border credit. Just before this last step let Z be the current
collection, put p(B) = tok_l(B) and let q(B) be the token value of the
same unchanged record at the start of phase l+1, so q(B) >= p(B).
Set
b = sum_{t in T_l} |Bor_t| , e = sum_{B in Z} ( q(B) - p(B) ) .
If b = 0 there is no border credit to supply. Otherwise the
record-by-record comparison of the threshold decrease shows
e >= (C_4/(6 C_3)) b delta_l as soon as the shrinking losses are taken
into account (each surviving old record gains at least a fixed fraction
of its own shrink deficit, and the sum of the deficits is at most
(1/2) b delta_l by Lemma 17.16 below). When this holds, distribute
these extra tokens among the current nodes proportionally to |Bor_t|;
every node obtains (17.14), and all earlier credits stay available.
Separation of border balls. Check that the phase transition keeps
the collection valid. Let A = B(X_u, delta_l) be a border ball and B
an old record whose conflict domain meets C(A). By Lemma 17.14, A is
still border, so one of
|| X_u - x ||_1 <= r_1 + C_3 delta_l , || X_u - x ||_1 >= r_2 - C_3 delta_l
holds. After B is restricted to its surviving inner and outer radii
a + s_l and b - s_l with s_l = 2 delta_l + delta_(l+1), the first case
gives every point of A radial distance strictly less than the new inner
radius, and the second strictly greater than the new outer radius; in
either case A avoids the restriction of B. When the conflict domains
are disjoint no geometric separation is needed. Original balls in the
current family are pairwise disjoint, so no conflict arises with an
unchanged current-phase ball or with another newly inserted border
ball. The other validity conditions follow from (L2)-(L3) of the input
labels and heredity (Lemma 17.13). Hence the new collection is valid.
Lemma 17.16 (cost of shrinking). Under (17.14) the total token deficit
created by the restrictions is at most (1/2) b delta_l.
Proof. For unchanged original balls both the deficit and q(B) - p(B)
vanish. For any other record the width decreases by 2(C_3 + 1)delta_l
(or the record disappears), which exceeds the decrease of the
threshold; record by record q(B) >= p(B) and the deficit is at most
2 C_3 delta_l times the number of border balls it contains, and summing
over the surviving records gives the bound. //
Lemma 17.17 (arrangement of insertable bags). Under the hypotheses of
this section (T locally k-connected, selected nodes satisfying
|O(t)| >= k lambda |P(t)|, a lambda-geometric sequence of families of
(12 C_3 / k)-assigned bags of types (delta_i, T_i) with the T_i
disjoint, all input balls insertable, and (17.8) holding), there is a
finite valid collection Z of labeled ordinary and hollow balls, with
centers inherited from the input balls, such that
sum_{B in Z} w(B) >= ( C_4/(12 C_3) )
sum_i delta_i sum_{t in T_i} |Bag_t| . (17.16)
Proof. Run the phases in order. By Lemma 17.10 and the border credit,
at the end of phase l every node t in T_l has been allocated at least
(C_4/(12C_3)) |Bag_t| delta_l tokens, and every earlier allocation is
preserved. Each record's token value is at most its width (positive
part, and the avoiding factor 1/(2(C_4+2)) <= 1). The collection Z
constructed is valid at every step by the structural lemmas and the
transition verification. Summing the allocations,
sum_{B in Z} w(B) >= sum_l ( C_4/(12 C_3) ) delta_l sum_{t in T_l} |Bag_t| ,
which is (17.16). //
Assembly of Proposition 17.1. Apply the halving reduction to the
original sequence: discard noninsertable balls, keep at
least half the mass M' >= M/2, and obtain a lambda-geometric sequence
of (12 C_3 / k)-assigned bags of insertable balls. Lemma 17.17 gives a
valid collection Z with total width at least (C_4/(12C_3)) M'. The
labeled-energy lemma (17.7) gives
(k/4) sum_{B in Z} w(B) <= sum_{uv in E} ||X_u - X_v||_1 .
Combining,
sum_{uv in E} ||X_u - X_v||_1
>= (k/4)( C_4/(12 C_3) ) M'
>= (k/8)( C_4/(12 C_3) ) M ,
which is (17.3). This completes the proof of Proposition 17.1. //
Now assemble the hierarchy bound into the shortcut bound used by extraction.
Recall the statement to be proved (Theorem 9.2): there is an absolute
integer q_H such that for every q >= q_H, if T is a locally q-connected
hierarchy of H and M is a set of nonroot nodes with
|O(t)| >= |P(t)|/q for t in M, then a shortcut matrix D exists with
(1/|O(t)|) sum_{e in O(t)} R_D(e) <= q^(-31/40) for every marked t.
Proof of Theorem 9.2. All cut constraints below are for nonempty
proper subsets. Take
alpha = q^(-4/5) , beta = 2 , epsilon = 1/10 ,
rho = lambda = 1/(2 q^2) , C_1 = 1024/epsilon^2 = 102400 ,
J = 1 + ceil( log_2(256/alpha^2) ) , C_2 = 128 J^4 ,
s = alpha / C_2 = q^(-4/5)/C_2 ,
L = 2 + ceil( log_2(1/s) ) ,
H = 1 + ceil( log_2( 24/(rho s^2) ) ) ,
and let C_3 = 10^4, C_4 = 3 be the fixed constants. Write
kappa = min( 1/16 , C_4/(96 C_3) ) = C_4/(96 C_3) = 1/(3.2 * 10^5)
for the smallest charging rate among compact and assigned bags. The
dependence of all numbers on q is only through the logs in J, L, H, and
for absolute constants c_2, c_5
C_2 <= c_2 (1 + log q)^4 , L, H <= c_5 (1 + log q) ,
s^epsilon = q^(-2/25) C_2^(-1/10) . (18.1)
The last identity uses epsilon = 1/10: s^(1/10) = q^(-4/(5*10)) C_2^(-1/10)
= q^(-2/25) C_2^(-1/10).
Split the marked nodes. Let T be the set of marked nodes t for which
N_t := (1/|O(t)|) ( sum_{e in O(t)} a_e )^2 >= alpha sum_{e in O(t)} d_e ,
with a_e = <u_e, Xb_e>, E = E(X) = sum_e d_e, and let the remaining
marked nodes be "good". For a good node N_t < alpha sum_{O(t)} d_e.
Because each edge lies in at most two boundaries O(t), the
total contribution of good nodes is
sum_{t in M \ T} N_t <= 2 alpha E . (18.2)
Charging the bad nodes. The nodes of T are alpha-bad, with positive
numerator, so Proposition 15.1 applies with the chosen alpha, beta,
epsilon, lambda and the bound s^epsilon <=
(48 beta C_1)^(-1) (which holds for all q above an absolute cutoff).
It produces a lambda-geometric sequence of families, either entirely
beta-compact or entirely s^(1+2epsilon)-assigned, of mass at least
Mass >= ( s^epsilon / (384 beta C_1 C_2 L H) )
sum_{t in T} N_t . (18.3)
Case compact. Apply Proposition 16.2 with k replaced by q. It gives
(1/4) Mass <= (1/q) E, i.e. E >= (q/4) Mass >= (q/16) Mass.
Case assigned. Apply Proposition 17.1 with local connectivity k
replaced by q and lambda replaced by rho = lambda (and lambda <= 1/18
for large q). It gives E >= (q/8)(C_4/(12C_3)) Mass = kappa q Mass.
In either case E >= kappa q Mass. Combining with (18.3),
sum_{t in T} N_t <= (384 beta C_1 C_2 L H / s^epsilon)( Mass )
<= (384 beta C_1 C_2 L H /(kappa q s^epsilon)) E .
Substituting (18.1) and C_2^(11/10) <= c (1+log q)^(22/5), L H <=
c (1+log q)^2, the logarithm power is 22/5 + 2 = 32/5 < 7, so
( sum_{t in T} N_t ) / E <= c_6 q^(-23/25)(1 + log q)^7 (18.4)
for an absolute c_6.
Combined bound. Adding (18.2) and (18.4), including the case T empty,
( sum_{t in M} N_t ) / E <= 2 q^(-4/5) + c_6 q^(-23/25)(1 + log q)^7
= o( q^(-31/40) ) . (18.5)
Every constant is absolute, and the embedding X and row-semiorthogonal
U were arbitrary, so the same bound holds for the supremum Q_* of
(13.2). By Lemma 13.1 (p_* <= Q_* <= 2 p_*), also p_* <= o(q^(-31/40)).
Choose the absolute cutoff q_H so that the right side of (18.5) is at
most q^(-31/40)/2 for all q >= q_H, and so that every numerical
condition above holds. Apply Lemma 13.1 with K = q^(-31/40)/2 and
eta = q^(-31/40)/2: it supplies a full positive definite D satisfying
every cut constraint and every marked average bound with right side
q^(-31/40). This proves the theorem. //
Remark. Selecting a feasible D from the infimum uses only the strict
slack eta; no assertion of attainment is needed. The cutoff q_H is
absolute because every loss was a function of alpha, epsilon,
beta, lambda alone.
Lemma 19.1 (packing from connectivity). Every k-edge-connected
multigraph on at least two vertices contains r_0 = max(1, floor(k/2))
pairwise edge-disjoint spanning trees. In particular r_0 >= k/3.
Proof. Let P be a partition of V into |P| parts. Summing, over the
parts, the number of edges leaving each part, and dividing by two,
gives |E(P)| = (1/2) sum_parts |delta(part)| >= (1/2) k |P|, since the
graph is k-edge-connected. For |P| >= 2,
r_0 (|P| - 1) = floor(k/2)(|P| - 1) <= (k/2)(|P| - 1)
<= (k/2)|P| <= |E(P)| .
So every partition satisfies the Nash-Williams-Tutte condition
(Theorem 3.1) for r_0, and r_0 disjoint spanning trees exist. Finally
floor(k/2) >= k/3 for k >= 1. //
Cascade. Let r_* be an absolute integer, larger than every threshold
appearing in Parts B and C (Theorem 8.1, Proposition 8.2, Theorem 9.2)
and so large that r_* >= 4 and r_*^(-1/16) <= 1/16. Start with
H_0 = G and r_0 = max(1, floor(k/2)). While r_i >= r_*, apply
Proposition 8.2 to H_i (which carries r_i >= r_* >= r_0 >= 4 disjoint
spanning trees) to obtain a spanning subgraph H_(i+1) of H_i carrying
r_(i+1) = floor( (1 - 4 u_i) r_i / 2 ) , u_i = r_i^(-1/16) ,
disjoint spanning trees, with
|delta_(H_(i+1))(S)| <= (1/2 + 3 tau_i) |delta_(H_i)(S)|
for every nonempty proper S, where tau_i = 2 sqrt(eps_i) + eps_i,
eps_i = 6 r_i^(-1/2), and
5/16 <= r_(i+1)/r_i <= 1/2 , (1/2 + 3 tau_i)/(r_(i+1)/r_i) <= 1 + 15 u_i .
Let j >= 0 be the first index with r_j < r_*; the process stops there.
Because r_(i+1) >= (5/16) r_i, one has r_j >= (5/16) r_(j-1) >= (5/16) r_*
>= 1, so H_j still contains at least one spanning tree. Choose any
spanning tree T of H_j.
Loss product. For every nonempty proper S,
|delta_T(S)| <= |delta_(H_j)(S)|
<= ( prod_{i=0}^{j-1} (1/2 + 3 tau_i) ) |delta_G(S)| . (19.1)
Write the product as
prod_{i=0}^{j-1} (1/2 + 3 tau_i)
= (r_j/r_0) prod_{i=0}^{j-1} (1/2 + 3 tau_i)/(r_(i+1)/r_i)
<= (r_j/r_0) prod_{i=0}^{j-1} (1 + 15 u_i) . (19.2)
The radii r_i are nonincreasing and, once in the open interval
(2^a, 2^(a+1)], the next value is at most r_i/2, so the cascade visits
each dyadic scale at most once. Hence
sum_{i=0}^{j-1} u_i = sum_{i=0}^{j-1} r_i^(-1/16)
<= sum_{a : 2^a >= r_j} O(1) 2^(-a/16) <= C_7 ,
an absolute constant depending only on r_* (the last scale r_j >= r_*
contributes the largest term r_*^(-1/16), and the dyadic tail is
geometric). Therefore
prod_{i=0}^{j-1} (1 + 15 u_i) <= exp( 15 sum_i u_i ) <= C_8 ,
(19.3)
an absolute constant.
Conclusion for large k. If r_0 >= r_* then r_j < r_*, and using
r_0 >= k/3 and (19.1)-(19.3),
|delta_T(S)| <= (r_j / r_0) C_8 |delta_G(S)|
<= (r_* / (k/3)) C_8 |delta_G(S)|
= (3 C_8 r_* / k) |delta_G(S)| .
So T is (C/k)-thin with C = 3 C_8 r_*.
Small k. If r_0 < r_*, then k < 2 r_* + 2, and any spanning tree T of
G (which exists because a connected graph has one, and k >= 1 makes G
connected) satisfies |delta_T(S)| <= |delta_G(S)|, so it is 1-thin.
Since 1 <= C/k whenever k <= C, and C = 3 C_8 r_* >= 2 r_* + 2 for
r_* >= 1, this also gives a (C/k)-thin tree. //
Theorem 19.2 (main theorem). There is a universal constant C such that
for every integer k >= 1, every finite loopless k-edge-connected
multigraph on at least two vertices has a spanning tree T with
|delta_T(S)| <= (C/k) |delta_G(S)|
for every nonempty proper subset S of the vertex set.
Proof. Take C = 3 C_8 r_* from Lemma 19.1 and the cascade above, with
T the chosen spanning tree of the terminal graph H_j. The two cases
(r_0 >= r_* and r_0 < r_*) together give the bound for every k. //
Optimality. The order 1/k is necessary. Let G be the graph on two
vertices with k parallel edges, which is k-edge-connected. Every
spanning tree uses exactly one of the k edges, so for the only
nontrivial cut (a singleton) one has |delta_T(S)| = 1 and
|delta_G(S)| = k, forcing thinness at least 1/k. So no constant
better than order 1/k is possible. //
Brouwer's theorem is proved in the form used by the extraction step,
via Sperner's lemma.
Let the standard d-simplex be
Delta_d = { x in [0,1]^(d+1) : sum_i x_i = 1 } .
A barycentric subdivision of Delta_d splits it into smaller simplices.
Only the fact that the mesh (largest edge length) tends to zero as the
subdivision index grows, and that the subdivisions are nested, is used.
Sperner introduced this lemma to prove invariance of dimension; it is
also a standard route to the fixed point theorem.
Lemma 20.1 (Sperner 1928). Label the vertices of any triangulation of
Delta_d by indices 0, 1, ..., d, subject to the boundary rule: a vertex
on a face spanned by indices in a set J receives a label in J. Then
some fully labeled simplex occurs, that is, a simplex whose vertices
receive all d+1 distinct labels.
Proof. For d = 0 there is nothing to prove. For d >= 1 count, mod 2,
the number of fully labeled d-simplices. By a standard boundary
argument, this count equals (mod 2) the number of fully labeled
(d-1)-simplices of the boundary face {x_0 = 0}: each internal
(d-1)-simplex abuts two d-simplices and contributes zero mod 2, so only
the boundary terms survive. By the induction hypothesis applied to
that face (the same statement one dimension lower, with the inherited
boundary rule) the count is odd, hence at least one. //
Theorem 20.2 (finite-dimensional fixed point). Let K be a nonempty
compact convex subset of a finite-dimensional real vector space. Every
continuous map F : K -> K has a fixed point.
Proof. A compact convex set is a retract of a simplex containing it:
the nearest-point map r onto K is continuous (it is a contraction) and
fixes K, and nearest points exist by compactness. So it suffices to
prove the theorem for a simplex Delta_d.
Let F : Delta_d -> Delta_d be continuous. The case d = 0 is
immediate. In the m-th barycentric subdivision, a vertex already fixed
by F proves the claim; otherwise label a vertex v by an index i with
v_i > F_i(v). Such an index exists because the two coordinate sums are
equal (both 1) and v != F(v); it satisfies v_i > 0. This label obeys
the boundary rule: if v lies on a face and v_i = 0, then F_i(v) >= 0 =
v_i, so i is not a valid label, hence v receives a label j with
v_j > 0, and j is among the indices spanning that face. Lemma 20.1
supplies a fully labeled simplex in the m-th subdivision. Denote its
vertex of label i by v^(m,i). 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 the subsequence. Continuity gives
x_i >= F_i(x) for every i, and equality of the coordinate sums forces
equality in every coordinate, so F(x) = x.
An affine coordinate change carries this to an arbitrary simplex, and
composing with the retraction r gives a fixed point of F on K. //
Marcus, Spielman, and Srivastava proved this while resolving the
Kadison-Singer conjecture; the form needed here is stated next.
Theorem 21.1 (MSS). Let eps > 0 and let v_1, ..., v_m be independent
random vectors with finite support in C^d. If
sum_{i=1}^m E[ v_i v_i^* ] = I_d , E ||v_i||^2 <= eps (each i),
then
P{ || sum_{i=1}^m v_i v_i^* || <= (1 + sqrt(eps))^2 } > 0 .
The symbol * is conjugate transpose and the norm is the operator norm; in
particular some outcome obeys the corresponding positive-semidefinite
upper bound. Real vectors are a special case. The case d = 0 is
immediate, so assume d >= 1.
Real stability. Write H = { z in C : Im z > 0 }. A nonzero polynomial
p in several variables is stable if it does not vanish when all its
arguments lie in H; it is real stable if in addition its coefficients
are real. A nonzero real univariate polynomial is stable exactly when
all its roots are real.
Lemma 21.2 (closure of stability).
(i) A product of stable polynomials is stable.
(ii) A stable polynomial remains stable after setting one variable to
a point of the closed upper half plane, if the result is not
identically zero.
(iii) Partial differentiation preserves stability.
(iv) If p is real stable and a has nonnegative coordinates, then
y -> p(y + a) is real stable.
Proof. (i) is clear. (ii): fix the other variables in H and let the
chosen variable approach the closed upper half plane through H; the
zeros remain in the closed upper half plane by Hurwitz' theorem. (iii):
differentiate along a direction using the finite difference
(p(z + t e_j) - p(z))/t with t approaching 0 through i(0,inf); stability
passes to the limit. (iv) follows from (ii) coordinate by coordinate,
since adding a >= 0 only pushes each argument toward H. //
Lemma 21.3 (limits of univariate polynomials). Suppose nonzero
univariate polynomials f_nu have uniformly bounded degree and converge
coefficientwise to a nonzero polynomial f. If all f_nu have no zeros
in H, neither does f. If all f_nu are real-rooted, so is f. For monic
real-rooted polynomials of a fixed degree the ordered roots depend
continuously on the coefficients.
Proof. Choose a in H with f(a) != 0. Pass to a subsequence of constant
degree and enumerate roots lambda_(nu,1), ..., lambda_(nu,e) with
multiplicity. By compactness of the Riemann sphere a further subsequence
makes every root converge, allowing infinite limits; every finite limit
lies outside H. In the factorization f_nu(z)/f_nu(a) = prod_k (z -
lambda_(nu,k))/(a - lambda_(nu,k)), a root tending to infinity
contributes a factor tending to 1, and a root tending to finite lambda_k
contributes (z - lambda_k)/(a - lambda_k). The limiting identity
factors f(z)/f(a) with all roots outside H. For real-rooted f_nu the
same proof uses the extended real line, giving all limiting roots
real. Continuity of ordered roots follows from this compactness. //
Above the roots. For a real stable polynomial p let Ab_p = { z in R^m :
p(z + s) > 0 for all s in [0,inf)^m }; such z is above the roots, and
Ab_p is closed under adding nonnegative vectors. At z in Ab_p define
Phi_p^i(z) = (partial_i p)(z) / p(z) , i = 1, ..., m .
Lemma 21.4 (positive partial fractions). Let p be real stable,
z in Ab_p, and i, j coordinate indices. As a rational function of t,
Phi_p^i(z + t e_j) = c + sum_{l=1}^r c_l / (t - lambda_l) , (21.1)
with c >= 0, c_l > 0, lambda_l < 0, the sum possibly empty. In
particular for t >= 0 this function is nonnegative, nonincreasing, and
convex.
Proof. Set h(t) = p(z + t e_j) and a(t) = (partial_i p)(z + t e_j). The
polynomial h is real-rooted by Lemma 21.2 (ii) with real z, and nonzero
because h(0) = p(z) > 0; it is positive on [0, inf), so every root is
strictly negative. Thus a/h has only negative real poles after
cancelling. Partial fractions give (21.1); the residues and constant
have the stated signs because the sign of a nonzero rational function
with only simple negative poles and fixed sign on [0, inf) forces them.
A nonnegative combination of t -> 1/(t - lambda_l) with lambda_l < 0
and the constant c is nonnegative, nonincreasing, and convex on
[0, inf). //
Lemma 21.5 (barrier shift). Let p be real stable, z in Ab_p, and j a
coordinate with Phi_p^j(z) <= 1 - 1/delta for some delta > 1. Set
q = (1 - partial_j) p and w = z + delta e_j. Then w in Ab_q, and for
every i
Phi_q^i(w) <= Phi_p^i(z) . (21.2)
Proof. The polynomial q is real stable by Lemma 21.2 (iii). By
monotonicity (Lemma 21.4), for every s >= 0, Phi_p^j(z + s) <=
Phi_p^j(z) <= 1 - 1/delta < 1. Hence q(z + s) = p(z + s)(1 -
Phi_p^j(z + s)) > 0, so z, and therefore w = z + delta e_j, lies in
Ab_q. Fix i and put f(t) = Phi_p^i(z + t e_j). Commuting the mixed
derivatives of log p near w gives Phi_q^i(w) = f(delta) - f'(delta) /
(1 - Phi_p^j(w)). By monotonicity the denominator is at least 1/delta,
and f'(delta) <= 0. By convexity f(0) >= f(delta) - delta f'(delta).
Therefore Phi_q^i(w) <= f(delta) - delta f'(delta) <= f(0) =
Phi_p^i(z). //
For hermitian matrices A_1, ..., A_m let p_A(y) = det(sum_i y_i A_i),
and define mu[A_1, ..., A_m](x) by applying (1 - partial_{y_i})
successively to p_A and setting all y_i = x. Substituting y_i = x + z_i
first and letting every z_i = 0 afterwards shows
mu[A_1, ..., A_m](x) = p_m(x, ..., x) , p_0 = p_A ,
p_j = (1 - partial_{y_j}) p_(j-1) . (21.3)
Lemma 21.6 (largest root of the mixed polynomial). If A_i >= 0,
sum_i A_i = I_d, and tr A_i <= eps for every i, eps > 0, then the
largest root of mu[A_1, ..., A_m] is at most (1 + sqrt(eps))^2.
Proof. The polynomial p_0 is real stable by Lemma 21.2, since
sum_i y_i A_i is stable as a function of y (each argument enters only
through the positive semidefinite combination) and equals I_d at y = 1.
Identify mu with p_m via (21.3). Set x_0 = t + delta with
t = eps + sqrt(eps), delta = 1 + sqrt(eps), so x_0 = (1 + sqrt(eps))^2
and t/(t + delta) = eps/(eps + sqrt(eps)) = sqrt(eps)/(1 + sqrt(eps)),
so phi := eps/t = 1 - 1/delta. At z^(0) = t 1 the matrix inside p_0 is
t I_d, so z^(0) in Ab_{p_0}, and differentiating the determinant gives
Phi_{p_0}^i(z^(0)) = tr((t I_d)^(-1) A_i) = tr A_i / t <= eps/t = phi.
Inductively define z^(j) = t 1 + delta(e_1 + ... + e_j). If
z^(j-1) in Ab_{p_(j-1)} with all barriers at most phi, then because
phi + 1/delta = 1, Lemma 21.5 applies in direction j and yields
z^(j) in Ab_{p_j} with all barriers still at most phi. This holds for
every j. In particular z^(m) = x_0 1 lies above the roots of p_m, so
p_m(x_0 1) > 0. Since p_m is monic of degree d in the diagonal
variable (its leading coefficient is det(sum_i A_i) = 1) and real
rooted, a positive value at x_0 forces every root to be at most x_0.
Hence the largest root of mu[A_1, ..., A_m] is at most x_0. //
Lemma 21.7 (common interlacing). Let p_1, ..., p_M be monic degree-d
polynomials whose every convex combination is real-rooted, with weights
w_i >= 0 summing to 1. Then some polynomial of positive weight has
largest root at most the largest root of the weighted average.
Proof. For two members p, q and r_t = (1-t)p + t q, fix real x not a
root of either. Let N(t) count the roots of r_t strictly below x. By
ordered-root continuity N is locally constant off the zeros of r_t(x),
and r_t(x) is affine in t, vanishing at most once. At such a zero x is
a simple root of r_{t_0} (otherwise, writing r_{t_0}(x+w) = a w^l +
O(w^(l+1)) with l >= 2, the rescaled polynomials converge to a
real-rooted limit a z^l + sigma b whose nonreal-root count contradicts
Lemma 21.3 for suitable sign sigma, since z^l = -sigma b/a has nonreal
roots when l >= 2). Hence N changes by at most one across t = t_0, so
|N(0) - N(1)| <= 1. If lambda_k(p) > lambda_(k+1)(q) for some k < d,
choose x strictly between them avoiding all endpoint roots; then
N(0) <= k - 1 and N(1) >= k + 1, a contradiction. Hence
lambda_k(p_i) <= lambda_(k+1)(p_j) for all i, j and k < d, so
c_k = max_i lambda_k(p_i) is a common interlacing. Let P be the
weighted average with largest root rho. Every p_i satisfies
p_i(c_(d-1)) <= 0, so P(c_(d-1)) <= 0 and, being monic,
rho >= c_(d-1). For x > rho, P(x) > 0, so some p_i(x) > 0; that p_i
has lambda_d(p_i) < x. Taking the minimum over the finitely many
positive-weight p_i and letting x decrease to rho proves
min_i lambda_d(p_i) <= rho. //
Conclusion of MSS. First suppose the v_i have finite support, and set
A_i = E[v_i v_i^*]. Expanding the determinant shows that, by the
rank-one determinant identity and its multilinearity in the columns
together with independence (each covariance stays fixed under
conditioning), the average of det(x I - sum_i v_i v_i^*) over outcomes
equals mu[A_1, ..., A_m](x). The characteristic polynomials
x -> det(x I - sum_i v_i v_i^*) of the individual outcomes are monic
real-rooted (each sum_i v_i v_i^* is positive semidefinite), their
convex combinations are real-rooted, and their weighted average is mu.
By Lemma 21.6 the largest root of mu is at most x_0 = (1 + sqrt(eps))^2,
and by Lemma 21.7 some outcome of positive probability has largest root
at most that of mu, hence at most x_0. For that outcome all eigenvalues
of sum_i v_i v_i^* are at most x_0, i.e. || sum_i v_i v_i^* || <=
(1 + sqrt(eps))^2. This is the assertion. The general finitely
supported case follows by the same argument, and approximation in the
covariance covers the remainder. //