================================================================================
L1 EMBEDDINGS OF GRAPHS OF BOUNDED TREEWIDTH
a complete self-contained proof, in plain ASCII
================================================================================
1. WHAT IS PROVED.
THEOREM. For every integer k >= 2 there is a constant C_k >= 1
with the following property. Let G = (V,E) be a finite connected
simple undirected graph that admits a tree decomposition whose bags
have at most k vertices. Give every edge e of G an arbitrary
positive length ell(e), and let d be the resulting shortest-path
metric. Then there is a map F from V into a real L1 space with
d(u,v) <= ||F(u) - F(v)||_1 <= C_k * d(u,v)
for all u,v in V.
C_k depends on k only: not on |V|, not on the decomposition tree T,
not on its depth, and not on the ratios of edge lengths. The target
space may be taken finite-dimensional (dimension 2^|V|). The bound
is existence only; C_k is not estimated.
Equivalently: the shortest-path metrics of graphs of treewidth at
most k-1 embed into L1 with uniformly bounded distortion. By the
excluded-planar-minor theorem, this also covers every graph family
that excludes one fixed planar graph as a minor.
2. WHAT CUTS HAVE TO DO WITH L1.
For S subset of V define delta_S(u,v) = |1_S(u) - 1_S(v)|; this is
1 exactly when the cut S separates u from v, and 0 otherwise.
Every nonnegative combination
D(u,v) = sum_{S subset V} w_S * delta_S(u,v), w_S >= 0,
is a cut pseudometric, and conversely every finite L1 metric has
this form (Part 0). So the theorem is exactly the following
demand on cut weights w_S >= 0:
(upper) D(u,v) <= U * ell(uv) for every EDGE uv,
(lower) D(u,v) >= c * d(u,v) for every pair u,v.
The upper bound for edges extends to all pairs along a shortest
path by the triangle inequality, so all the work is in the lower
bound. The same cut data governs the flow-cut gap: the worst
nonuniform sparsest-cut ratio on a fixed graph equals the worst L1
distortion of its weighted shortest-path metrics (Linial-London-
Rabinovich; Gupta-Newman-Rabinovich-Sinclair, Section 3). Hence
the theorem also gives a uniform flow-cut gap C_k for these graphs.
3. WHY THIS IS NOT A TREE-SAMPLING ARGUMENT.
Trees embed isometrically into L1, and bounded treewidth "looks like
a tree of small pieces", so one might hope to sample a dominating
tree and embed that. This fails already at treewidth 2: some
series-parallel shortest-path metrics need distortion Omega(log n)
against every random dominating tree (GNRS, Theorem 5.6). The
proof below never samples a tree. It keeps many cut measures alive
at once and transports local information across bags.
Only three outside results are used: the symmetric Markov-flow
bound of Chlamtac-Krauthgamer-Raghavendra (Part 2), the padded
partition theorem of Filtser-Friedrich-Issac-Kumar-Le-Mallek-Zeif
(Part 4), and the Robertson-Seymour excluded-planar-minor theorem
(for the corollary above; it is not used in the proof itself).
4. THE PLAN.
Three ingredients.
(1) MARKOV GLUING (Part 1). Put a finite cut measure mu_t on each
bag B_t, all of the same mass m, and require adjacent measures
to agree on the overlap of their bags. Such a CONSISTENT
family glues canonically to one measure on cuts of the whole
vertex set, built by conditional sampling down a rooted tree.
The glue depends only on the family, not on the root.
(2) TRANSPORT OF UNCERTAINTY (Part 2). Suppose one small cut
measure nu is a summand of the bag law at every bag along a
path of bags, and nu is genuinely "uncertain" at the far end z
given the labels on a testing bag P on that path. Then the
glued metric separates the two ends of the path by a definite
fraction of that uncertainty. The fraction depends on k only,
never on the length of the path.
(3) PARTICLES AND RESERVATIONS (Part 3). Realize each bag law as
the sum of sweeps of N real functions on V ("particles").
Replacing a pair (F_a, F_b) by (f+g, f-g), where f is their
average and g vanishes on the current bag P, leaves the cut
measure on P unchanged but gives the pair height |g(z)| far
away; a reservation freezes such a pair along a stretch of
bags. A quadratic invariant Q_r = r(N-r) keeps every particle
uniformly Lipschitz no matter how many such edits occur.
These ingredients yield two cut pseudometrics:
D_bag (Part 4): D_bag <= U_bag * d everywhere, and
D_bag >= a_bag * d on pairs sharing a bag.
D_anc (Part 5): D_anc <= U * d everywhere, plus an
anchor-driven separation for vertices that
are far apart in the decomposition tree.
(Part 6) If D_bag + D_anc were not uniformly comparable to d, a
compactness argument (a nonprincipal ultrafilter) would produce a
normalized counterexample. On it, a bounded cache of anchors
yields a YOUNGEST CROSSING RESERVATION; the launch noise carried by
that reservation then forces a strictly younger crossing
reservation, which is impossible. Hence
D_bag + D_anc >= lambda_k * d, lambda_k > 0,
with lambda_k depending on k only. (Part 7) Adding the two cut
measures and using "cut metric = finite-dimensional L1" proves the
theorem with C_k = (U_bag + U) / lambda_k.
5. NOTATION.
Plain ASCII. ^ and _ are superscript and subscript; == and != are
equality and inequality; <=, >= are order; sum_, prod_, int_ are
indexed sum, product, integral; in and notin are membership;
subset and subseteq are inclusion; forall, exists, s.t. are the
usual quantifiers; iff means "if and only if"; o(1) means "tends to
0"; O, Omega, Theta are the usual asymptotics.
Graph and metric. G = (V,E); ell(e) > 0 edge lengths; d(u,v) the
shortest-path distance; Delta = diam(V,d); d(x,A) = min_{a in A}
d(x,a) for nonempty A.
Tree decomposition. T is the tree, B_t the bag at node t, |B_t|<=k,
and T_v = {t : v in B_t} is a connected subtree for every v.
Cuts. Omega_S = {0,1}^S is the set of binary labelings of S;
delta_S(u,v) = |1_S(u) - 1_S(v)|; ||.||_1 is the L1 norm. For a
labeled cut measure nu on Omega_V, D_nu(u,v) = nu{omega : omega(u)
!= omega(v)}.
Bag measures. mu_t is a labeled cut measure on Omega_{B_t}; nu|R
is the trace of nu to R (the pushforward under omega -> omega|R);
nu^c is the complement measure omega -> 1 - omega; nu^sym =
(nu + nu^c)/2; m is the common total mass. E_nu(z|P) is the
uncertainty at z given P: for each labeling b of P, take the
smaller of the two masses of "z labelled 0" and "z labelled 1",
and sum over b.
Particles and constants. F_1,...,F_N are particles (real-valued
functions on V); sigma_F^M is the sweep of F (push Lebesgue measure
on [-M,M] through t -> 1_{F > t}); Q_r = r(N-r). A perturbation g
satisfies Lip(g) <= L and |g| <= B*Delta. U is a uniform upper
bound for every cut pseudometric built here; b_k = 1/C(2^k) and
C(2^k) come from Part 2; q, q_0, N, M, n_0 count particles and
cache slots in Parts 3-5. The final constants are U_bag, a_bag,
U, lambda_k, and C_k = (U_bag + U)/lambda_k. Every one of them
depends on k only.
Square brackets [like this] mark informal asides; skipping them
loses nothing.
================================================================================
PART 0. BACKGROUND: METRICS, L1, AND TREE DECOMPOSITIONS
================================================================================
--------------------------------------------------------------------------------
0.1 GRAPHS, EDGE LENGTHS, SHORTEST-PATH METRICS
--------------------------------------------------------------------------------
Let G = (V,E) be a finite, connected, simple, undirected graph. Give
each edge e a positive length ell(e) > 0, with no further restriction.
For u,v in V let d(u,v) be the smallest total length of a walk from u
to v. Since G is finite and connected and all lengths are positive,
this minimum exists; d is a metric, because walks concatenate and give
the triangle inequality, and distinct vertices are at positive
distance.
We use two derived quantities:
Delta = max_{u,v in V} d(u,v) (the diameter)
d(x,A) = min_{a in A} d(x,a) for nonempty A subset of V.
For fixed nonempty A the function x -> d(x,A) is 1-Lipschitz:
|d(x,A) - d(y,A)| <= d(x,y).
Indeed, take a nearest point a of A to x; then d(y,A) <= d(y,a) <=
d(y,x) + d(x,a) = d(x,y) + d(x,A). Thus d(y,A) - d(x,A) <= d(x,y),
and exchanging x,y gives the absolute value.
A function g : V -> R has LIPSCHITZ CONSTANT AT MOST L (written
Lip(g) <= L) if |g(x) - g(y)| <= L d(x,y) for all x,y in V. The
display above is the case L = 1 of this notation.
--------------------------------------------------------------------------------
0.2 CUTS, L1, AND SWEEPS
--------------------------------------------------------------------------------
A CUT of V is a subset S of V; it is the same thing as a binary
labeling 1_S : V -> {0,1} that is 1 on S and 0 off S. Its elementary
metric is
delta_S(u,v) = |1_S(u) - 1_S(v)|,
which is 1 exactly when S separates u from v, and 0 otherwise. A CUT
COMBINATION is a nonnegative weighted sum of cuts:
D(u,v) = sum_{i=1}^{m} w_i * delta_{S_i}(u,v), w_i >= 0. (0.1)
CLAIM 0.1 (Cut combinations are exactly L1 metrics on finite V).
(i) Given (0.1), define F : V -> R^m by
F(v) = ( sqrt(w_1) 1_{S_1}(v), ..., sqrt(w_m) 1_{S_m}(v) ).
Then ||F(u) - F(v)||_1 = sum_i w_i |1_{S_i}(u) - 1_{S_i}(v)|
= D(u,v). So every cut combination is an L1 distance table.
(ii) Conversely, let F : V -> R^M with ||F(u)-F(v)||_1 = D(u,v).
Writing coordinates F_1,...,F_M,
D(u,v) = sum_{j=1}^{M} |F_j(u) - F_j(v)|,
and each coordinate contributes a cut combination, by the
LAYER-CAKE identity. For real numbers a,b,
|a - b| = int_{-inf}^{inf} |1_{a > t} - 1_{b > t}| dt, (0.2)
because the two step functions disagree exactly for t between
the two values, an interval of length |a-b|. Since V is
finite, F_j takes finitely many values, so (0.2) collapses to
a finite sum: the function is a cut combination.
For us, the useful packaging of (0.2) is the SWEEP. Let F : V -> R
and let M > 0 with F(V) contained in [-M, M]. The SWEEP MEASURE of F
is the pushforward of Lebesgue measure on [-M,M] under the map
t -> 1_{F > t} in Omega_V = {0,1}^V. (0.3)
It is a finite measure on the set of cuts of V, with total mass 2M,
and by (0.2) its cut pseudometric is exactly
D_{sigma_F^M}(u,v) = |F(u) - F(v)|.
We will also use SYMMETRIZATION, which sends a measure nu on Omega_V to
nu^sym = (nu + nu^c) / 2, nu^c = image of nu under omega -> 1 - omega.
The cut pseudometric of nu^sym equals that of nu, because for every
pair u,v the two events "omega(u) != omega(v)" and its complement
under omega -> 1-omega are the same event.
Summing up: on a finite set V the following two objects carry the same
information.
(L1') a map F : V -> R^M with ||F(u) - F(v)||_1 = D(u,v);
(CUT') a finite labeled cut measure nu on Omega_V with
D(u,v) = nu{omega : omega(u) != omega(v)}.
We build (CUT') objects and read off (L1') when needed.
A PSEUDOMETRIC satisfies the metric axioms except that D(u,v) = 0 is
allowed for distinct u,v. That is harmless: it only says two vertices
are never separated by the cuts we built. Combined with a positive
lower bound lambda_k d (Part 6) it becomes a genuine metric.
--------------------------------------------------------------------------------
0.3 TREE DECOMPOSITIONS AND SEPARATORS
--------------------------------------------------------------------------------
A TREE DECOMPOSITION of G = (V,E) consists of a finite tree T, whose
vertices we call NODES to avoid confusion with V, and a BAG B_t
subset of V for each node t, subject to
(COVER) every v in V lies in some bag, and every edge uv in E
lies inside some bag;
(RUNS) for every v in V, the set {t : v in B_t} of nodes is a
connected subtree of T.
The WIDTH is (max_t |B_t|) - 1, and the TREEWIDTH of G is the minimum
width over all decompositions. Here k always denotes a bound on BAG
SIZE, so the treewidth is at most k-1.
Two normalizations are used without comment.
(S1) All bags may be assumed nonempty. If some bag is empty,
deleting its node splits T into components whose bag-unions are
pairwise joined by no edge: an edge must lie in a bag, hence in a
single component. As G is connected, at most one component
contains vertices of V; delete the rest, and repeat. Each
deletion keeps a valid tree decomposition.
(S2) Bags are indexed objects. Two nodes may carry the same
vertex set; they remain different bags, and we never identify
them.
LEMMA 0.1 (Separator facts). Let T be a tree decomposition of a
connected graph G = (V,E).
(a) If a bag B lies on the tree path from a bag A to a bag C, then
every path in G from a vertex of A to a vertex of C meets B.
(b) For adjacent bags A and C, the intersection A cap C separates
the union of the bags on one side of the tree edge from the
union on the other side. In particular A cap C is nonempty.
(c) Let A_0, A_1, ..., A_r be bags along a tree path, and let z be
a vertex of A_r. Then d(z, A_i) is nonincreasing in i. More
sharply, if a bag B lies between a bag A and a bag containing
z, there is v in B with
d(z,A) - d(v,A) = d(z,v). (0.4)
PROOF OF (a). Delete the node t_B of T carrying B. The tree splits
into components. By (RUNS), for every vertex x not in B the subtree
of nodes carrying x lies entirely in one component. If x,y not in B
are adjacent in G, some bag carries both, so their subtrees meet, and
x,y lie in the same component. Hence any path in G that avoids B
stays inside one component. If A and C were on opposite sides of
t_B, no path could join them without meeting B. By hypothesis (a)
t_B is interior to the path from A to C, so A and C are indeed on
opposite sides. []
PROOF OF (b). Let L, R be the unions of bags on the two sides of the
tree edge AC. A vertex v is in L cap R exactly when its subtree T_v
meets both sides, i.e. exactly when v is in A cap C. Suppose an edge
xy had one endpoint in L\R and the other in R\L. The edge lies in
some bag, which lies on one side; then both x and y lie on that side,
contradiction. So A cap C separates L from R. If A cap C were
empty, no path could join the nonempty sets B_A\C and B_C\A, against
connectedness of G. []
PROOF OF (c). Monotonicity: A_{i+1} lies between the bag of z and the
bag A_i, so by (a) every shortest path from z to A_i passes through
A_{i+1}; hence d(z, A_{i+1}) <= d(z, A_i).
For (0.4): take a shortest path P from z to A. It meets B, say at v in
B, because B lies between z's bag and A. The part of P from z to v
has length d(z,v): otherwise a shorter z-to-v path followed by the
(preserved) v-to-A part would give a shorter z-to-A path. Likewise
the part from v to A has length d(v,A). The lengths add, so
d(z,A) = d(z,v) + d(v,A). []
The case of (c) we use constantly: fix bags A above B in a rooted
decomposition, and p in B. Then for every bag A' on the tree path
from A down to B,
d(p, A') is nonincreasing as A' moves down toward B,
because A' lies between A and B, so (c) applies with z = p and A_r
the bag containing p. This is what makes all distance lists in
Part 5 sorted.
--------------------------------------------------------------------------------
0.4 WHAT PART 0 GIVES
--------------------------------------------------------------------------------
* cut combination = finite-dimensional L1 embedding = labeled cut
measure on Omega_V, all interchangeable (Claim 0.1);
* shortest-path d is a metric, d(x,A) is 1-Lipschitz;
* tree decompositions, bags, and the separator facts (a),(b),(c).
Everything later is built on these three items. We construct cut
measures; their L1 realizations come for free.
================================================================================
PART 1. BAG MEASURES ON A TREE DECOMPOSITION AND MARKOV GLUING
================================================================================
Throughout this part: G = (V,E) is finite, connected, with positive
edge lengths; d is its shortest-path metric; T is a tree decomposition
with |B_t| <= k and all bags nonempty (Part 0, (S1)).
We give each bag a cut measure, demand agreement on overlaps, and glue
the family into one cut measure of the whole vertex set.
--------------------------------------------------------------------------------
1.1 BAG MEASURES, TRACES, CONSISTENCY
--------------------------------------------------------------------------------
For a finite set S, Omega_S = {0,1}^S is the set of binary labelings.
A LABELED CUT MEASURE on S is a finite nonnegative measure nu on
Omega_S. Since Omega_S is finite, nu is just a nonnegative weight for
each labeling.
For R subseteq S, the TRACE nu|R is the pushforward of nu under the
restriction map omega -> omega|R:
(nu|R)(b) = nu{omega in Omega_S : omega|R = b}, b in Omega_R.
The COMPLEMENT MAP is omega -> 1 - omega, applied pointwise; nu^c is
its pushforward. nu is SYMMETRIC if nu = nu^c, and the SYMMETRIZATION
is nu^sym = (nu + nu^c)/2. The CUT PSEUDOMETRIC of nu is
D_nu(u,v) = nu{omega : omega(u) != omega(v)}, u,v in S.
Symmetrization leaves it unchanged, because complementing a labeling
does not change whether it separates u from v.
DEFINITION 1.1. A CONSISTENT FAMILY is a family mu = (mu_t) of labeled
cut measures, one on each bag B_t, such that
(CM1) all mu_t have one common total mass m > 0;
(CM2) for every tree edge st of T,
mu_s | (B_s cap B_t) = mu_t | (B_s cap B_t).
The common trace in (CM2) is written mu_{st}.
--------------------------------------------------------------------------------
1.2 MARKOV GLUING
--------------------------------------------------------------------------------
LEMMA 1.1 (Markov gluing). Every consistent family mu with bags of
size at most k (all bags nonempty) has a labeled cut measure rho_mu on
Omega_V, of total mass m, with
(rho_mu)|B_t = mu_t for every node t of T. (1.0)
Moreover:
(MG1) rho_mu does not depend on the node of T chosen as root;
(MG2) if every mu_t is symmetric, then rho_mu is symmetric;
(MG3) for a tree path B_{t_0}, ..., B_{t_r}, the assignments on the
consecutive intersections B_{t_i} cap B_{t_{i+1}} form a
Markov chain under rho_mu/m;
(MG4) the coordinates F_v(omega) = omega(v) satisfy
||F_u - F_v||_{L1(rho_mu)} = D_mu(u,v), where
D_mu(u,v) := rho_mu{omega : omega(u) != omega(v)}.
PROOF.
CONSTRUCTION. Root T at any node t_0. Sample the root labels
omega|B_{t_0} with law mu_{t_0}/m. Then walk down the tree. Suppose
node t has parent s and the labels on B_s are already fixed. Put
S := B_s cap B_t, keep the labels on S, and sample the labels on
B_t \ S from the conditional law mu_t(. | omega|S).
This is well defined, because the labels already fixed at B_t are
exactly those on S. Indeed, if a vertex v of B_t was fixed at an
earlier step, then v lies in some earlier bag; by (RUNS) the subtree
T_v contains the tree path from that bag to t, and that path passes
through s, so v in B_s. Thus v in S.
MARGINALS. We show by induction over the rooted tree that omega|B_t
has law mu_t/m. For the root this is the definition. For a non-root
t with parent s, the induction hypothesis gives omega|B_s ~ mu_s/m,
hence omega|S ~ mu_s|S/m, which by (CM2) is mu_t|S/m; sampling mu_t/m
conditioned on that trace returns mu_t/m. Multiplying by m gives
(1.0) for every node t.
CONSISTENCY OVER V. A vertex lying in several bags keeps one label:
each step freezes the labels it inherits and never changes them. By
(COVER) every vertex lies in some bag, so the construction labels all
of V; it is therefore a measure rho_mu on Omega_V of total mass m, and
(1.0) holds.
(MG1) ROOT INDEPENDENCE. Assume first that every edge trace mu_{st}
is positive. Multiplying the conditional densities along the rooted
tree gives, for every assignment omega,
rho_mu(omega) = mu_{t_0}(omega|B_{t_0})
* prod_{t != t_0} mu_t(omega|B_t)
/ mu_{s(t)}(omega|B_{s(t)} cap B_t),
where s(t) is the parent of t. The edges (s(t), t) with t != t_0 are
exactly the edges of T, so the denominator is prod_{st in E(T)}
mu_{st}(omega|B_s cap B_t), and
rho_mu(omega) = ( prod_{t} mu_t(omega|B_t) )
/ ( prod_{st in E(T)} mu_{st}(omega|B_s cap B_t) ). (GLUE)
The right side involves no root: it is a property of the family mu
alone. If some trace factor vanishes, then some numerator factor
vanishes too (it is the trace of that numerator on an edge set), so
with the convention "vanishing denominator forces vanishing numerator"
the identity still holds, and the already proved marginals identify
the measure. Hence rho_mu is root independent.
(MG2) SYMMETRY. If every mu_t is symmetric, then each factor of
(GLUE) is invariant under omega -> 1 - omega, hence so is rho_mu.
(MG3) MARKOV CHAIN ALONG A PATH. Root T at t_0. Then
B_{t_0}, ..., B_{t_r} is a downward path. The construction samples
the labels on B_{t_{i+1}} from mu_{t_{i+1}} conditioned on the labels
on B_{t_i} cap B_{t_{i+1}}, and by the argument above those are the
only labels from the past that it uses. Hence, writing
X_i = omega | (B_{t_i} cap B_{t_{i+1}}),
the conditional law of X_{i+1} given X_0, ..., X_i depends on X_i only,
which is the Markov property. The kernels are
P_i(b, .) = law of omega|(B_{t_i} cap B_{t_{i+1}})
under mu_{t_{i+1}}( . | omega|(B_{t_i} cap B_{t_{i+1}}) = b ).
(MG4) L1 REALIZATION. Since |omega(u) - omega(v)| is 1 exactly when
omega separates u from v, and rho_mu has total mass m,
||F_u - F_v||_{L1(rho_mu)} = int |omega(u) - omega(v)| d rho_mu
= D_mu(u,v).
This is precisely a cut representation of D_mu, as in Part 0. []
TERMINOLOGY. D_mu is the GLUED CUT PSEUDOMETRIC of the family mu. For
a single labeled cut measure nu the notation D_nu keeps its earlier
meaning, and the two agree when nu = rho_mu.
--------------------------------------------------------------------------------
1.3 TWO IMMEDIATE CONSEQUENCES
--------------------------------------------------------------------------------
CONSEQUENCE A (edges control all pairs). Suppose every edge e = uv
lies in some bag B_t and satisfies the bag bound
D_{mu_t}(u,v) <= U * ell(uv) for every edge uv. (1.1)
Then the glued pseudometric satisfies
D_mu(u,v) <= U * d(u,v) for all u,v in V. (1.2)
PROOF. By (1.0), D_mu(u,v) = D_{mu_t}(u,v) for the bag carrying the
edge, so D_mu(u,v) <= U ell(uv). Sum this over the edges of a
shortest u-to-v path and use the triangle inequality for D_mu. []
CONSEQUENCE B (averaging auxiliary randomness). Suppose the family mu
depends measurably on an auxiliary random variable X, and that for
almost every realization the mass is the fixed number m. Then
rho_* := E_X [ rho_{mu(X)} ]
is a labeled cut measure on Omega_V of total mass m, and
D_{rho_*}(u,v) = E_X [ D_{mu(X)}(u,v) ] for all u,v in V.
Consequently, if D_{mu(X)} >= c d almost surely then D_{rho_*} >= c d,
and if D_{mu(X)} <= U d almost surely then D_{rho_*} <= U d.
PROOF. Expectation of finite measures is linear, and "omega(u) !=
omega(v)" is a bounded 0-1 function of omega, so Fubini gives the
identity, together with the two one-sided conclusions. []
================================================================================
PART 2. UNCERTAINTY TRANSPORT: A RIGIDITY OF MARKOV GLUING
================================================================================
Markov gluing produces one global law on labelings of V. It does not
organize that law "path by path", so a small cut measure sitting in
every bag law along a path does not automatically separate the two ENDS
of the path. Proposition 2.2 supplies exactly that implication, at a
cost depending only on the bag size k. It is the only place where a
result from outside this file enters.
--------------------------------------------------------------------------------
2.1 THE EXTERNAL SYMMETRIC MARKOV FLOW BOUND
--------------------------------------------------------------------------------
A MARKOV CHAIN with state sets (LAYERS) L_0,...,L_N is a sequence of
random variables X_i in L_i. Its MARKOV FLOW GRAPH has vertex set
{(i,a) : a in L_i}; between consecutive layers there is an arc from
(i-1,a) to (i,b) of capacity Pr[X_{i-1} = a, X_i = b]. A FEASIBLE FLOW
from a source s in L_0 to a sink t in L_N is a nonnegative mass on arcs,
bounded by the capacities and conserved at every vertex except s and t;
its VALUE is the total mass leaving s.
The chain is SYMMETRIC if each layer carries a fixed-point-free
involution theta_i such that the joint law of (theta_0(X_0), ...,
theta_N(X_N)) equals that of (X_0,...,X_N). We will use theta_i(a) =
1 - a, the complement, which is fixed-point-free on a nonempty layer.
THEOREM 2.1 (symmetric Markov flow bound; Chlamtac, Krauthgamer,
Raghavendra 2010, Theorem 4.4). For every integer w >= 2 there is a
constant C(w) >= 1 with the following property. Let a symmetric Markov
chain have at most w states in each layer, first layer {s_0, s_1}, last
layer {t_0, t_1}, and let theta_0, theta_N swap s_0 with s_1 and t_0
with t_1. Then every feasible flow from s_0 to t_1 has value at most
C(w) * Pr[X_0 = s_0, X_N = t_1].
C(w) depends on w only, neither on N nor on the transition
probabilities.
Two bookkeeping remarks. First, the theorem is used below for laws of
arbitrary total mass m: divide all masses by m, apply the theorem,
multiply back, and the same inequality holds with masses in place of
probabilities. Second, states of zero mass may be deleted: their
incident capacities vanish, so no feasible flow and no endpoint mass
changes, and the involutions remove them in pairs.
Fix once and for all
b_k := 1 / C(2^k) > 0. (2.1)
Every layer below is the set of binary labelings of a set with at most k
vertices, hence has at most 2^k states, so b_k depends on k alone.
--------------------------------------------------------------------------------
2.2 UNCERTAINTY, AND ITS TRANSPORT
--------------------------------------------------------------------------------
DEFINITION 2.2. For a labeled cut measure nu on V, a set P subseteq V
and a vertex z, the UNCERTAINTY of nu at z given P is
E_nu(z|P) := sum_{b in Omega_P}
min{ nu(omega|P = b, omega(z) = 0),
nu(omega|P = b, omega(z) = 1) }. (2.2)
For each labeling b of P take the smaller of the two masses of the two
possible labels of z, and sum over b. So E_nu(z|P) is the mass of the
part of z's label that cannot be predicted from the labels on P.
Two properties follow immediately from the definition.
(UNC1) E_nu(z|P) >= 0, and E_nu is monotone and positively
homogeneous in nu.
(UNC2) E_{nu^sym}(z|P) >= E_nu(z|P). Symmetrizing averages the
pair of masses at b with the pair at 1-b; taking the smaller
of two numbers can only grow under such averaging.
PROPOSITION 2.2 (Transport of uncertainty). Let mu be a consistent
family of SYMMETRIC bag measures with bags of size at most k. Let
B_0, ..., B_r be bags along a tree path, with y in B_0 and z in B_r,
and let P = B_j for some 0 <= j <= r. Suppose a labeled cut measure
nu, not necessarily symmetric, satisfies
nu|B_i <= mu_{B_i} for every j <= i <= r. (2.3)
Then the Markov-glued pseudometric satisfies
D_mu(y,z) >= b_k * E_nu(z|P). (2.4)
PROOF. Fix a realization and write rho = rho_mu.
STEP 0 (the layers). Splice the bag P itself into the list of
consecutive intersections:
S_0 = {y}, S_1 = B_0 cap B_1, ..., S_j = B_j = P,
S_{j+1} = B_j cap B_{j+1}, ..., S_N = {z}.
Each S_i is nonempty: the two endpoint layers are single vertices, and
intersections of consecutive bags are nonempty by Lemma 0.1(b). Each
S_i lies inside some bag, and consecutive layers lie inside ONE bag:
(S_i, S_{i+1}) is contained in B_i, except for the endpoint pairs,
which lie in B_0 and in B_r.
The labels on S_0, ..., S_N form a Markov chain under rho/m. Indeed,
by (GLUE) the glued law is a product of bag factors over edge factors of
the tree, so conditioned on the labels of any one bag, the labelings on
the two sides of that bag are independent. Walking along the path, the
past therefore influences the next layer only through the current
layer. The capacity of an arc between two consecutive layers is the
rho-mass of the corresponding joint assignment, which is the mass the
trace of mu assigns on a bag containing both layers.
Since every S_i is nonempty, a -> 1-a is a fixed-point-free involution
of the labelings of S_i; by (MG2), rho is invariant under complementing
all layers at once. Hence we have a symmetric Markov flow graph with at
most w = 2^k states per layer.
STEP 1 (a transport measure on paths). We build a measure lambda on
labelings of the chain whose consecutive two-layer marginals are
dominated by the capacities.
Suffix first. On the layers S_j, S_{j+1}, ..., S_N, which are the
labelings of sets inside bags B_i with i >= j, take the projection of
nu. Each of these is dominated by the corresponding trace of rho, by
(2.3).
Prefix second. For a labeling b of P = S_j put
n_b := nu(omega|P = b), m_b := rho(omega|P = b),
so n_b <= m_b by (2.3) at i = j. If m_b > 0, extend b to the earlier
layers S_0, ..., S_{j-1} with the conditional law of rho/m given
omega|P = b. If m_b = 0, then n_b = 0 and there is nothing to attach.
STEP 2 (feasibility). Let F be an event on the layers S_0,...,S_{j-1}.
Since (rho/m)(F | omega|P=b) = rho(F, omega|P=b)/m_b,
lambda(F) = sum_{b: m_b > 0} n_b * rho(F, omega|P = b)/m_b
<= sum_{b: m_b > 0} rho(F, omega|P = b) = rho(F),
term by term, because n_b <= m_b. So the prefix is dominated by the
capacities. The suffix marginals of lambda are those of nu, dominated
by (2.3), and at the seam S_j both descriptions agree because the
prefix was conditioned on b.
STEP 3 (uncertainty is carried to the two ends). For i in {0,1} and
b in Omega_P put
a_i(b) := nu(omega|P = b, omega(z) = i),
q_b := rho(omega(y) = 0, omega|P = b) / m_b (m_b > 0),
and q_b := 0 when m_b = 0; then both a_i(b) vanish as well. By the
construction, at P-labeling b the prefix puts mass q_b on y = 0 and
mass 1 - q_b on y = 1, while the suffix puts mass a_i(b) on z = i, so
the joint mass of {y = 0, z = 1} equals q_b a_1(b), and similarly for
the other orientation. Hence
lambda{omega(y) != omega(z)}
= sum_b ( q_b a_1(b) + (1 - q_b) a_0(b) ).
For every real q the inequality q a_1 + (1-q) a_0 >= min{a_0, a_1}
holds, so
lambda{omega(y) != omega(z)}
>= sum_b min{a_0(b), a_1(b)} = E_nu(z|P). (2.4a)
STEP 4 (the flow bound). Restrict lambda to the paths with omega(y) = 0
and omega(z) = 1. The restriction is a feasible flow from (y,0) to
(z,1): its arc masses are bounded by the capacities of Step 2, and mass
is conserved at every intermediate labeling. Theorem 2.1, in masses
(Remark after the theorem), gives
lambda{y = 0, z = 1} <= C(2^k) * rho{omega(y)=0, omega(z)=1}.
Complementing all layers is an automorphism of the flow graph, by the
symmetry of Step 0. So the restriction to paths with y = 1 and z = 0,
complemented, is again a feasible flow from (y,0) to (z,1), and the
same bound holds for it:
lambda{y = 1, z = 0} <= C(2^k) * rho{omega(y)=1, omega(z)=0}.
Adding the two displays,
lambda{omega(y) != omega(z)}
<= C(2^k) * rho{omega(y) != omega(z)}
= C(2^k) * D_mu(y,z). (2.4b)
STEP 5 (conclusion). Combine (2.4a) with (2.4b) and use (2.1):
D_mu(y,z) >= b_k * E_nu(z|P). []
REMARKS. (i) No symmetry of nu is assumed: only mu must be symmetric,
to make the chain symmetric. Our transport submeasures are usually
sums of the two sweeps of a pair f+g, f-g, which is not symmetric on
its own. (ii) The loss b_k is independent of r, because every layer
has at most 2^k states. (iii) The proposition only asks nu to be a
submeasure of the bag laws on the bags from P onward; it says nothing
about the bags before P.
--------------------------------------------------------------------------------
2.3 TWO TESTS THAT PRODUCE UNCERTAINTY
--------------------------------------------------------------------------------
The transport inequality is only useful if we can manufacture a
submeasure nu with a definite uncertainty at the far end. Two tests do
this. The first uses one function with a height gap; the second uses a
pair of functions that agree on a set A but differ elsewhere.
SETUP. Fix a cutoff M > 0. For F : V -> [-M, M] the SWEEP
sigma_F^M is Lebesgue measure on [-M,M] pushed through t -> 1_{F > t};
it has total mass 2M and cut pseudometric |F(u) - F(v)| (Part 0). Its
SYMMETRIZATION is
sigma_F^{M,sym} = ( sigma_F^M + (sigma_F^M)^c ) / 2,
with the same cut pseudometric. We say F has SWEEP MARGIN t at a
vertex z if F(z) lies in [-M+t, M-t], that is, at distance at least t
from both ends of the swept interval.
LEMMA 2.3 (height-gap test). Let P subseteq V, z in V and t > 0, and
let F : V -> [-M, M] satisfy
(HG1) F has sweep margin t at z;
(HG2) |F(z) - F(s)| >= t for every s in P.
Then, with nu := sigma_F^{M,sym},
E_nu(z|P) >= t. (2.5)
PROOF. Put a := F(z) and let U = (a - t, a + t), an open interval of
length 2t, contained in [-M,M] by (HG1).
Labels on P do not move. By (HG2), no value F(s) with s in P lies in
U; so each F(s) is <= a - t or >= a + t. For a threshold u in U the
label 1_{F(s) > u} is therefore determined by which side of U the value
F(s) lies on, and that side does not depend on u. Hence the labeling
b(u) := ( s -> 1_{F(s) > u} ), u in U,
of P is one and the same labeling b for every u in U.
The label at z moves once. The label 1_{F(z) > u} = 1_{a > u} equals 1
for u < a and 0 for u > a. So on the lower part of U, of length t, the
sweep contributes mass t to the event "labeling b on P, label 1 at z",
and on the upper part of U, also of length t, mass t to "labeling b on
P, label 0 at z". Taking the smaller of those two masses for the
labeling b, and summing over all labelings of P, gives
E_{sigma_F^M}(z|P) >= t.
Apply (UNC2) to symmetrize and conclude (2.5). []
LEMMA 2.4 (launch-gap test). Let A subseteq V and let f, g : V -> R
satisfy g|A = 0 and f + g, f - g in [-M, M]. Put
nu := sigma_{f+g}^{M,sym} + sigma_{f-g}^{M,sym}.
Then for every z in V,
E_nu(z|A) >= 2 |g(z)|, (2.6)
and for all u,v in V,
D_nu(u,v) = |f(u)-f(v) + g(u)-g(v)| + |f(u)-f(v) - g(u)+g(v)|
>= 2 |g(u) - g(v)|. (2.7)
PROOF. Write h_+ = f+g and h_- = f-g. On A both equal f, because
g|A = 0. Fix z and assume first g(z) >= 0; the other sign is the same
with + and - exchanged. Then h_-(z) = f(z) - g(z) and h_+(z) =
f(z) + g(z), and
U := ( h_-(z), h_+(z) )
is an interval of length 2|g(z)|, contained in [-M,M] because both
h_+ and h_- take values in [-M,M].
For a threshold u in U, the two sweeps give opposite labels at z:
1_{h_+(z) > u} = 1 and 1_{h_-(z) > u} = 0. On A both functions equal
f, so both sweeps give the same labeling of A at the threshold u; call
it b(u). For a fixed labeling b of A put U_b = {u in U : b(u) = b}.
Reading the u-parameter as the swept mass,
mass of {labeling b on A, z = 1} >= |U_b| (from h_+),
mass of {labeling b on A, z = 0} >= |U_b| (from h_-),
and nu is the sum of the two symmetrized sweeps, so both bounds hold
for nu as well. Taking minima and summing over b,
E_nu(z|A) >= sum_b |U_b| = |U| = 2|g(z)|.
This proves (2.6). For (2.7), the sweep of a function F has cut
pseudometric |F(u)-F(v)|, so the cut pseudometric of the (unsymmetrized)
sum is
|h_+(u)-h_+(v)| + |h_-(u)-h_-(v)|
= |a + b| + |a - b| with a = f(u)-f(v), b = g(u)-g(v)
>= 2|b| = 2|g(u)-g(v)|,
using |a+b| + |a-b| >= 2|b|. Symmetrization does not change a cut
pseudometric, so the same holds for nu. []
--------------------------------------------------------------------------------
2.4 THE TWO TRANSPORT ESTIMATES USED LATER
--------------------------------------------------------------------------------
Both consequences below put a test from 2.3 into Proposition 2.2. Note
the hypothesis: domination by the bag laws is required only from the
testing bag onward, which is exactly (2.3).
CONSEQUENCE C1 (launch transport). Let A subseteq V, let f, g be real
functions on V with g|A = 0 and f+g, f-g in [-M,M], and put
nu := sigma_{f+g}^{M,sym} + sigma_{f-g}^{M,sym}.
Let B_y be a bag containing y, let B_z be a bag containing z, and
suppose A lies on the tree path from B_y to B_z. If nu is dominated by
the bag laws on every bag of that path from A onward, that is,
nu|B <= mu_B for every bag B on the path from A to B_z,
then
D_mu(y,z) >= 2 b_k |g(z)|. (2.8)
In particular, if |g(z)| >= d(z,A)/2, then D_mu(y,z) >= b_k d(z,A).
PROOF. Apply Proposition 2.2 with testing bag P := A, path from
B_y to B_z. By Lemma 2.4, E_nu(z|A) >= 2|g(z)|, so (2.4) gives the
claim. []
CONSEQUENCE C2 (averaged height transport). Let F : V -> [-M,M] have
sweep margin t at z, let P be a testing bag on the tree path from a bag
B_y containing y to a bag B_z containing z, and let X be auxiliary
randomness. Suppose that on an event of probability at least p:
(i) the trace of sigma_F^{M,sym} is dominated by the bag law on
every bag of the path from P to B_z;
(ii) |F(z) - F(s)| >= t for every s in P.
Then
E_X [ D_mu(y,z) ] >= b_k * p * t. (2.9)
PROOF. On the event of probability at least p, Lemma 2.3 gives
E >= t and Proposition 2.2 gives D_mu(y,z) >= b_k t, pointwise in X.
Off that event D_mu >= 0 still holds, so averaging gives the claim. []
TYPICAL USE. The auxiliary randomness X is fresh noise inserted into a
pair of particles at a launch. The domination (i) is what a
"reservation" in Part 3 provides: a frozen pair keeps contributing its
sweeps to every bag law along a stretch of bags. The gap (ii) is
produced by making one fresh uniform coefficient large enough.
================================================================================
PART 3. PARTICLES AND RESERVATIONS
================================================================================
Parts 1 and 2 take the bag laws mu_t as given. Everything from here on
CONSTRUCTS them. Two demands must be met: the laws must agree on
overlaps (so that Markov gluing applies), and they must carry specific
submeasures (so that uncertainty transport applies).
The device is to write each bag law as a sum of sweeps of real functions
on V, called particles. Because a particle is a GLOBAL function, the
trace of its sweep on any bag is automatically consistent between
neighbouring bags: it is the restriction of one fixed global measure.
Consistency is free. The work is to modify particles without breaking
that, and without letting their Lipschitz constants grow.
Throughout Part 3: (V,d) and the tree decomposition (T,{B_t}) are as
before, with bags of size at most k >= 2 and all bags nonempty; T is
rooted; Delta = diam(V,d); and |V| >= 2 (the case |V| = 1 is trivial and
disposed of in Part 7).
--------------------------------------------------------------------------------
3.1 PARTICLES, SWEEPS, AND THE LIST MEASURE
--------------------------------------------------------------------------------
A PARTICLE is a real function on V. We keep a LIST
F_1, F_2, ..., F_N
of N particles, all initially zero.
Fix positive constants L and B (later L = B = 3) and a CUTOFF M > 0.
Every perturbation we ever add will satisfy
Lip(g) <= L, sup_{v in V} |g(v)| <= B * Delta. (3.1)
The cutoff will be chosen as M = (B(N-1)+2) Delta in (3.11); Lemma 3.2
shows that every particle then always stays at distance at least 2 Delta
from either end of [-M,M]. So every sweep below is well defined, and no
circularity arises: N, L, B and then M are fixed FIRST, and only then do
we start sampling perturbations.
For a particle F the SWEEP sigma_F^M is Lebesgue measure on [-M,M]
pushed through t -> 1_{F > t} (Part 0, (0.3)); it has total mass 2M and
cut pseudometric |F(u)-F(v)|. We use only SYMMETRIZED sweeps.
The MEASURE CARRIED BY THE LIST on a set P subseteq V is the restriction
(mu_list)|P := ( sum_{i=1}^{N} (sigma_{F_i}^M)^sym ) |P. (3.2)
Every summand is symmetric, so mu_list is symmetric. As long as adjacent
bags are given by lists whose particles agree on the overlap (which
copying the list down a branch gives), the traces on the overlap agree.
So the whole bookkeeping reduces to two rules.
(PC1) CONSISTENCY. Every edit of the list must leave the measure
(3.2) on the CURRENT bag P unchanged.
(PC2) COPYING. When the tree branches, each child receives its own
copy of the list and may edit it independently, as long as each
copy obeys (PC1) on the branching bag.
An edit that satisfies (PC1) is what the next lemma provides. It needs
the two particles to be sorted the same way on P.
LEMMA 3.1 (affine trace update). Let P subseteq V and let particles
F_a, F_b admit a COMMON WEAK INCREASING ORDER on P: a listing
P = {p_1, ..., p_r} with
F_a(p_1) <= ... <= F_a(p_r) and F_b(p_1) <= ... <= F_b(p_r).
Put f = (F_a + F_b)/2 and let g : V -> R satisfy g|P = 0, with F_a, F_b,
f+g, f-g all taking values in [-M,M]. Then the traces on P agree:
( sigma_{F_a}^M + sigma_{F_b}^M ) | P
= ( sigma_{f+g}^M + sigma_{f-g}^M ) | P, (3.3)
and the same holds after symmetrization.
PROOF. Fix any real function F with F(p_1) <= ... <= F(p_r) and write
a_i = F(p_i), plus a_0 = -M and a_{r+1} = +M. At threshold t the
labeling of P is p_i -> 1_{a_i > t}. Since the a_i are nondecreasing,
the set of vertices labelled 1 is a FINAL SEGMENT of p_1,...,p_r. For
i in {0,1,...,r} let L_i be the labeling that is 1 exactly on
p_{r-i+1}, ..., p_r. It occurs for exactly the thresholds t with
a_{r-i} <= t < a_{r-i+1},
an interval of length a_{r-i+1} - a_{r-i}. Hence
sigma_F^M | P gives mass m_i(F) := a_{r-i+1} - a_{r-i} to L_i,
and mass 0 to every other labeling of P. (3.4)
The masses m_i(F) are nonnegative because the a_i are nondecreasing, and
they sum to a_{r+1} - a_0 = 2M. Two features are all we need: the
support of the trace consists of the labelings L_0, ..., L_r, which
depend on the ORDER only, and each m_i(F) is AFFINE in the height vector
(a_1, ..., a_r).
Apply this to F_a and to F_b, which share the same order, so that both
traces live on the same L_i. Since b_i := F_b(p_i) and f_i = (a_i+b_i)/2
satisfy m_i(F_a) + m_i(F_b) = 2 m_i(f) termwise,
sigma_{F_a}^M | P + sigma_{F_b}^M | P = 2 ( sigma_f^M | P ).
On the other hand g|P = 0, so (f+g)|P = f|P = (f-g)|P; the two sweeps on
the right of (3.3) therefore have the SAME trace on P, and that trace is
sigma_f^M | P. Adding gives 2 ( sigma_f^M | P ) again. This proves
(3.3). Symmetrization and restriction are linear, so (3.3) survives
symmetrization. For P empty, Omega_P has a single labeling and both
sides have mass 2M. []
Read (3.3) as follows: replacing the pair (F_a, F_b) by (f+g, f-g),
where f is the average and g vanishes on P, does not change the measure
on the current bag P. So we may add a useful perturbation g, provided
we keep a common weak increasing order on P, and the perturbation will
still be visible on LATER bags, where the pair is frozen and P is far
away. That is the whole mechanism.
DEFINITION. An UPDATE AT P replaces a pair of particles that share a
common weak increasing order on P by
(F_a, F_b) -> ( f + g, f - g ), f = (F_a+F_b)/2, g|P = 0, (3.5)
where g satisfies the bounds (3.1). By Lemma 3.1 this is allowed: it
preserves the measure on P.
Two questions remain. Can we always find two free particles with a
common weak increasing order on the current bag? Yes: a counting
argument, Section 3.3. And do the Lipschitz constants stay bounded
under arbitrarily many updates? Also yes, and this is the content of
Section 3.2.
--------------------------------------------------------------------------------
3.2 UNIFORM BOUNDS: THE INVARIANT Q_r
--------------------------------------------------------------------------------
The naive estimate Lip(f+g) <= Lip(f) + L suggests that T updates could
push Lipschitz constants up by T L, which is unbounded. The surprise is
that a numerical invariant caps them once and for all.
LEMMA 3.2 (uniform particle bounds). Starting from all-zero particles,
after ANY finite sequence of updates (3.5) with perturbations obeying
(3.1), every particle satisfies
Lip(F_i) <= L (N-1), (3.6)
|F_i(v)| <= B (N-1) Delta for every v in V. (3.7)
Both bounds are independent of the number of updates.
PROOF. Two steps: a numerical invariant for vectors, then its
application to particle differences and to particle values.
STEP 1 (the invariant). Let a = (a_1,...,a_N) start at zero and be
changed only by operations
a_a, a_b -> (a_a + a_b)/2 + e, (a_a + a_b)/2 - e, |e| <= 1, (3.8)
on two coordinates a != b. Then at every stage
a_1 + ... + a_N = 0, (3.9)
sum_{i in I} a_i <= |I| (N - |I|) for every I subseteq {1..N}. (3.10)
The sum condition (3.9) is immediate: (3.8) replaces a_a + a_b by
a_a + a_b.
For (3.10), write r = |I| and Q_r = r(N-r), so Q_0 = Q_N = 0. The claim
is proved by induction on the number of operations. Initially all a_i
vanish and (3.10) reads 0 <= Q_r. Suppose it holds and one operation on
coordinates a, b is performed, giving a'.
* If I contains both a and b, or neither, then sum_{i in I} a_i does
not change.
* If I contains exactly one of them, say a, put S = I \ {a}, so
|S| = r-1 and S excludes b. Then sum_{i in I} a'_i equals
sum_{h in S} a_h + (a_a + a_b)/2 + e, and
sum_{h in S} a_h + (a_a + a_b)/2
= (1/2) ( sum_{h in S} a_h + sum_{h in S+a+b} a_h ),
because the union S + {a,b} contributes a_a + a_b on top of S. The
induction hypothesis bounds the two sums by Q_{r-1} and Q_{r+1}, so
sum_{i in I} a'_i <= (1/2)( Q_{r-1} + Q_{r+1} ) + 1.
Now Q_{r-1} + Q_{r+1} = (r-1)(N-r+1) + (r+1)(N-r-1) = 2r(N-r) - 2
= 2Q_r - 2, hence the bound is Q_r - 1 + 1 = Q_r.
STEP 2 (differences). Fix distinct u,v in V and put
a_i := ( F_i(u) - F_i(v) ) / ( L d(u,v) ).
An update on particles a, b changes a_a, a_b by (3.8) with
e = ( g(u) - g(v) )/( L d(u,v) ), and |e| <= Lip(g)/L <= 1 by (3.1).
So (3.10) applies, with I = {i} and with the complement I = {i}^c:
using (3.9), the complement bound is -a_i <= N-1. Together,
|a_i| <= N - 1, that is |F_i(u) - F_i(v)| <= L (N-1) d(u,v).
This holds for all pairs, which is (3.6).
STEP 3 (values). Fix v in V and put a_i = F_i(v)/(B Delta). An update
changes a_a, a_b by (3.8) with e = g(v)/(B Delta), |e| <= 1. The same
argument gives |F_i(v)| <= B (N-1) Delta, which is (3.7). []
Remark. If the tree branches, each branch keeps its own copy of the
list; the invariant is applied to each copy separately, which is
harmless.
CONSEQUENCES. With L = B = 3 the bounds read Lip(F_i) <= 3(N-1) and
|F_i(v)| <= 3(N-1) Delta. Take
M := ( B(N-1) + 2 ) * Delta. (3.11)
Then every particle ever built satisfies |F_i(v)| <= B(N-1) Delta = M -
2 Delta. So each particle keeps a SWEEP MARGIN of at least 2 Delta: its
values are 2 Delta away from both ends of [-M,M]. This is exactly what
the height tests of Part 2 will need.
Moreover, at any bag, for all u,v in V,
D_{mu_t}(u,v) = sum_{i=1}^{N} |F_i(u) - F_i(v)|
<= N L (N-1) d(u,v). (3.12)
So U := N L (N-1) is an upper bound of the kind required by (1.2).
--------------------------------------------------------------------------------
3.3 RESERVATIONS
--------------------------------------------------------------------------------
A RESERVATION is a pair of particles (F_a, F_b) that no update may
touch while the reservation lasts. Releasing it frees them again; the
particles themselves are not changed.
WHY FREEZING HELPS. Suppose we update at a bag A, replacing a pair by
(f+g, f-g) with g|A = 0, and then reserve that pair. While the
reservation lasts the two functions do not change, so their sweeps are
two summands of the total trace at every bag the reservation crosses.
Hence the fixed submeasure
nu := (sigma_{f+g}^M)^sym + (sigma_{f-g}^M)^sym
satisfies nu|B <= mu_B on every bag B of the reservation. That is
hypothesis (2.3) of Proposition 2.2 with testing bag A, so the transport
estimates of Part 2 apply, and by (2.6) the pair separates a remote z
by 2|g(z)|. The two sweeps are not equal to each other: their heights
differ by 2g, and that difference is exactly what (2.7) converts into
separation.
BOOKKEEPING. At each node t, in each MEMORY COPY, let c_t be the number
of active reservations. Each reservation uses two particles, so
N - 2c_t particles are free at t.
An update needs TWO FREE PARTICLES WITH A COMMON WEAK INCREASING ORDER
on the current bag B_t. Fix once and for all a linear order on the
vertices of each bag (its vertex names, say). A particle F induces a
strict order on B_t by sorting the pairs (F(x), x) lexicographically.
So each particle picks one of at most k! orders; if N - 2c_t >= 2 k!,
two free particles pick the same order and both are nondecreasing in
it. Such a pair can be updated.
BRANCHING. At a branching node each child receives its own copy of the
particle list and of the reservation record; c_t counts the reservations
in one copy only.
ONE-NODE RESERVATIONS. A proposal that is made and immediately rejected
still occupies its two particles at the single node where it is made,
and is counted in c_t there.
--------------------------------------------------------------------------------
3.4 REALIZATION: THE ALL-PURPOSE SCHEDULE
--------------------------------------------------------------------------------
PROPOSITION 3.3 (realization by particles). Fix a finite schedule of
launches and releases that needs at most q simultaneous reserved pairs
in each memory copy, including any one-node reservation. Let
N := 2q + k! + 2, L = B = 3, M := (3(N-1) + 2) Delta.
Then the whole schedule can be carried out, and the resulting symmetric
bag measures
mu_t := ( sum_{i=1}^{N} (sigma_{F_i}^M)^sym ) | B_t , (3.13)
built from the current particle list at bag t, satisfy:
(i) every mu_t has total mass m = 2NM, and the laws of adjacent
bags have equal traces on their intersection;
(ii) every particle ever built has sweep margin at least 2 Delta;
(iii) the Markov-glued pseudometric satisfies D_mu(u,v) <= U d(u,v)
for all u,v in V, with U = 3N(N-1);
(iv) a reserved pair contributes a fixed submeasure nu which is
dominated by mu_t on every bag of its reservation segment,
endpoints included, even if the two particles are reused at
the release bag.
All four hold pointwise in any auxiliary randomness; for measurable
random choices, taking expectations gives an L1 pseudometric with the
same upper bound.
PROOF.
(a) A PAIR IS ALWAYS AVAILABLE. At every stage at most 2q particles are
reserved, so at least N - 2q = k! + 2 are free. By the pigeonhole of
Section 3.3, two free particles share a weak increasing order on the
current bag.
(b) THE PAIR IS CHOSEN BEFORE THE NOISE. Order all pairs of indices by
a fixed rule and take the first eligible one in the current memory copy.
This choice depends only on the state before the launch, not on the
fresh perturbation sampled at the launch.
(c) BOUNDS AND CUTOFF. Lemma 3.2 with L = B = 3 and the displayed M
gives Lip(F_i) <= 3(N-1) and |F_i(v)| <= 3(N-1) Delta = M - 2 Delta at
every stage, whatever the number of updates. The cutoff M was fixed
first and does not depend on the schedule.
(d) THE BAG LAW IS WELL DEFINED. Record mu_t by (3.13) from the list
current at t. An update at B_t changes the list but not the measure on
B_t (Lemma 3.1), and releasing a reservation changes nothing at all. So
mu_t is the same whether we record before or after the operations at t.
Updates at the empty interface are done before the root law is recorded.
(e) CONSISTENCY. For a child t' of t, copy the list and the whole
reservation record, perform any child-specific updates still at B_t, and
then move that copy to B_{t'}. Both mu_t and mu_{t'} are traces of the
SAME global measure carried by that copy, so they agree on B_t cap B_t'.
This holds on every edge of T, by induction along the tree.
(f) MASS. The sweep sigma_F^M has total mass 2M, and symmetrizing
(averaging with the complement image) keeps the total mass 2M. A sum of
N of them has mass 2NM = m, the same at every bag.
(g) GLUING AND THE UPPER BOUND. Consistency plus Lemma 1.1 gives the
glued pseudometric. For an edge uv, pick a bag B_t containing both
endpoints. On that bag the glued measure is mu_t, whose cut
pseudometric is sum_i |F_i(u) - F_i(v)| (symmetrization does not change
a cut pseudometric), and Lemma 3.2 bounds that by 3(N-1) d(u,v) per
particle, so D_mu(u,v) <= U d(u,v) on edges. Consequence A of Part 1
extends this to all pairs along shortest paths.
(h) RESERVATIONS DOMINATE. A reserved pair is frozen by definition, so
its two sweeps are summands of the current trace at every bag of the
reservation, giving nu|B <= mu_B there. At the launch bag this is read
just after the launching update, and at the release bag just before the
release; so it also holds for the recorded law at either end, even if
the particles are reused immediately. A reservation made at the empty
interface satisfies the same from the root onward.
(i) RANDOMNESS. Nothing above used more than the pointwise bounds, so
the statements hold for every realization; Consequence B of Part 1 turns
measurable choices into an L1 pseudometric by averaging. []
CONSTANTS. With L = B = 3 and N = 2q + k! + 2:
Lip(F_i) <= 3(N-1), |F_i(v)| <= 3(N-1) Delta,
M = (3N - 1) Delta, U = 3N(N-1), m = 2 N M.
They depend on q, and hence on k, only. Neither the number of updates in
the whole tree nor the total number of reservations appears anywhere:
only the MAXIMUM SIMULTANEOUS number per memory copy matters. Choosing
the schedules themselves is the business of Parts 4 and 5.
One point deserves emphasis. At any moment, EVERY active reservation
contributes a fixed submeasure to the current bag law, and that
submeasure has the same trace on every bag of the reservation segment.
Proposition 2.2 therefore applies to any sub-path of the segment. That
is what turns "particles" into "transport".
================================================================================
PART 4. THE COMMON-BAG METRIC D_bag
================================================================================
Goal of this part: construct one symmetric consistent family of bag
measures whose glued cut pseudometric D_bag satisfies
UPPER: D_bag(u,v) <= U_bag * d(u,v) (all u,v),
LOWER: D_bag(u,v) >= a_bag * d(u,v) (u,v in a common bag),
with U_bag < infinity and a_bag > 0 depending only on k. The
construction uses the same particle machinery as Part 3. The
per-copy reservation cap will be R = 2k(k-1). So the particle count
N, the cutoff M, and the upper bound U_bag will be exactly the "Part 3
realization" formulas with q = R.
Throughout this part, (V,d) is the shortest-path metric of a finite
connected graph with positive edge lengths and a tree decomposition
whose bags are nonempty, size at most k; d has diameter Delta; |V|>=2.
--------------------------------------------------------------------------------
4.1 ACTIVE SCALES AND THE PER-BAG COUNT
--------------------------------------------------------------------------------
For a bag B (as a vertex set), say a POWER OF TWO s = 2^j (j in Z)
is ACTIVE at B if some two DISTINCT vertices u,v in B satisfy
s/2 <= d(u,v) <= 4 s. (4.1)
A pair u,v at distance e activates exactly the powers of two s with
e/4 <= s <= 2e, an interval of ratio eight; it therefore contains at
most FOUR powers of two. A bag of size at most k has at most
binom(k,2) unordered pairs of distinct vertices, so
|{s : s active at B}| <= 4 binom(k,2) = 2 k(k-1). (4.2)
Write R := 2k(k-1). Every bag has at most R active scales, and we will
keep one reserved pair of particles per active scale.
Three remarks on the definition.
(i) The constant 4 is chosen generous on purpose. The lower bound
(4.4) picks, for a pair u,v with s <= d(u,v) < 2s, a bag A at which
s is INACTIVE, and derives a contradiction from two vertices a,b of
A with d(a,b) in [3s/4, 9s/4]. For that contradiction, s must be
ACTIVE at A as soon as such a,b exist, and that is precisely what
(4.1) with the constant 4 delivers: 3s/4 >= s/2 and 9s/4 <= 4s.
(ii) A scale is launched at a bag where it is INACTIVE and is relied
on at the child, where it is active. The reason is that a
perturbation vanishes on its interface: launching at the child
itself would produce a bump that is invisible inside the child's
bag. Launching at the parent A and then freezing gives a bump that
vanishes on A and is nonzero inside the child.
(iii) A RUN of a scale is a maximal set of consecutive bags, on a
root-to-leaf path, where the scale is active. Each run gets its own
reserved pair, launched just above the run, and the pair is released
just below it. The next subsection makes this precise.
--------------------------------------------------------------------------------
4.2 PADDED PARTITIONS (EXTERNAL INPUT)
--------------------------------------------------------------------------------
The whole D_bag construction (and, later, Part 5's local-noise step)
uses the following padded decomposition theorem for bounded-treewidth
graphs, proved by Filtser, Friedrich, Issac, Kumar, Le, Mallek, and
Zeif (TheoretiCS 2025, Theorem 1.2 and Definition 2.1). The
"diameter" in its statement is the ORIGINAL shortest-path distance
(sometimes called WEAK diameter); the parts need not be geodesically
convex.
THEOREM 4.1 (Padded partitions for bounded treewidth). There are
constants alpha in (0, 1/8] and pi in (0, 1] with the following
property, depending only on the bag-size bound k. For every graph
metric (V,d) as above and every radius r > 0, there is a random
partition P of V (parts are subsets C subseteq V with pairwise-disjoint
union V) such that:
(PP-diam) diam(C) <= r for every part C in support,
(PP-pad) Pr[ B_d(x, alpha r) is contained in the part
containing x ] >= pi for every x in V.
Here B_d(x, t) = {y in V : d(x,y) <= t}.
CHOICE OF alpha AND pi. The source theorem is stated for one fixed
treewidth t and carries a PADDING PARAMETER gamma in (0, 1]: it
guarantees that B_d(x, gamma r) lies inside x's own part with
probability at least exp(-beta_t gamma), for every gamma in
(0, delta_t], where beta_t, delta_t > 0 depend on t. We need constants
that work for every t at once, and we read the theorem at one value of
gamma only.
Let t_max = max{2, k-1} and put
alpha := min { 1/8, min_{2 <= t <= t_max} delta_t },
pi := min_{2 <= t <= t_max} exp( - beta_t * alpha ).
These are positive and depend only on k. So we take the constants
alpha and pi fixed for the rest of the file.
Special case: treewidth 1. The cited padded decomposition is stated
for treewidth t >= 2. Treewidth 1 (forests) can be reduced to
treewidth 2 by attaching a positive-length triangle at a single
vertex. This enlarges the graph by at most three vertices but keeps
all original distances. Every partition of the enlarged graph,
restricted to original vertices, preserves both (PP-diam) and
(PP-pad). So the theorem extends to t = 1 with the SAME alpha and pi
that were chosen for t >= 2; no extra minimum is needed.
Two conventions. First, d(z, V\C) is only ever written for C != V,
where V\C is a nonempty finite set and the minimum is attained. (The
case C = V never arises below.) Second, for C != V the function
z -> d(z, V\C) is 1-Lipschitz, being the distance to a fixed set.
We also use the following elementary Lipschitz-bump lemma.
LEMMA 4.2 (Disjoint nonnegative bumps). Let E_1, ..., E_m subseteq V
be pairwise DISJOINT. For each i, let psi_i : V -> [0, inf) be
nonnegative and 1-Lipschitz, with psi_i vanish off E_i. Let
u_1, ..., u_m in [0,1]. Then sum_i u_i psi_i is 1-Lipschitz.
Proof. Within one set E_i, the summand u_i psi_i is 1-Lipschitz
(scale of a 1-Lipschitz function). For z,w in different sets, the
sum at either z or w is nonnegative and bounded by d(z,w) (each bump
vanishes off its own set, so the "other side" sees zero). Their
absolute difference is at most d(z,w). Same estimate covers points
outside all sets. []
--------------------------------------------------------------------------------
4.3 THE CO-BAG EMBEDDING: STATEMENT
--------------------------------------------------------------------------------
PROPOSITION 4.3 (Co-bag embedding). For every rooted tree
decomposition of a finite connected graph as above, with bags of size
at most k and all bags nonempty, there is an L1 pseudometric D_bag on
V and constants U_bag < infinity and a_bag > 0, depending only on k,
such that for every u,v in V
D_bag(u,v) <= U_bag * d(u,v), (4.3)
and
D_bag(u,v) >= a_bag * d(u,v) whenever u,v share a bag. (4.4)
One may take
R = 4 binom(k,2),
N = 2 R + k! + 2,
U_bag = 3 N (N-1),
a_bag = (pi * alpha) / 64.
The rest of PART 4 is the construction and the proof.
--------------------------------------------------------------------------------
4.4 THE RESERVATION SCHEDULE
--------------------------------------------------------------------------------
We root T at any node. The schedule is defined node by node.
Root bag. At the root bag B_root, launch one reserved particle pair
for every scale s ACTIVE at B_root, using the EMPTY INTERFACE (no
vanishing constraint, so any two free particles may be used). Then
record the root trace.
A node t with parent s. Make a fresh copy of the parent's particle
list and full reservation record. This copy is dedicated to t.
Step 1 (drop): release all reservations whose scale is INACTIVE at
B_t. Such pairs are just freed; the particles remain in the list.
Step 2 (carry): the pairs whose scale is ACTIVE at BOTH B_s and B_t
are unchanged; they continue from s to t.
Step 3 (launch): for every scale s' ACTIVE at B_t but NOT active
at B_s, launch a new reserved pair whose interface is B_s. This
update is performed AT B_s in the child-specific memory, BEFORE
moving the memory to t. The new pair therefore has trace on B_s
that is compatible with the child law, and is available to be
active at B_t and onward.
Step 4 (record): record mu_t in the child's memory; then move to t.
Step 5 (branch): if a node has multiple children, each child gets
its own copy from Step 1 onward. The reservations held in one
copy are counted separately.
A nonroot node t whose (Step 1) left some scales active at B_t has
those scales' pairs carried passively; no fresh launch. A pair whose
scale is active at a maximal consecutive run of bags gets
LAUNCHED at the top of that run and RELEASED after the bottom.
RESERVATION-COUNT INVARIANT. In any memory copy at any moment the
number of reserved pairs is at most R. Indeed a copy holds, at any
moment, at most one pair per scale active at the bag it is about to
visit, and there are at most R such scales. Dropping precedes
launching, so the count never overshoots, and a one-node proposal is
itself one of those launches and needs no extra slot. The cap q = R of
Proposition 3.3 is therefore respected, and with q = R:
N = 2R + k! + 2, M = (B(N-1)+2) Delta, m = 2NM.
All particles are uniformly Lipschitz by Lemma 3.2 with L = 3.
--------------------------------------------------------------------------------
4.5 THE PERTURBATION g FOR A NEW SCALE
--------------------------------------------------------------------------------
At a launch of scale s at interface bag A (possibly A = empty):
r := s/16.
Sample a random partition P from Theorem 4.1 at scale r (so parts
have diameter at most r, and every point has probability >= pi of
having a ball of radius alpha r around it inside its own part).
For each part C in P, give an independent uniform coefficient
U_C in [0, 1], and set the bump
min{ d(z,A), d(z, V \ C), r } if z in C,
psi_C(z) = {
0 if z notin C.
(For a root launch with EMPTY interface A, omit the term d(z,A)
entirely; the other two terms remain.)
Define g := sum_{C in P} U_C * psi_C.
PROPERTIES OF g:
(G1) Vanishes on A. For z in A: if z is in some C, then
d(z,A) = 0, so psi_C(z) = 0. So g(z) = 0 for z in A.
(G2) Lipschitz. The bumps psi_C are supported on disjoint sets C,
and each psi_C is 1-Lipschitz (it is the minimum of 1-Lipschitz
functions d(z,A), d(z,V\C), and the constant r). So by Lemma 4.2
with all u_i bounded by 1, the sum g is 1-Lipschitz.
(G3) Bounds. The scale s is active at some bag, so that bag holds
distinct u,v with s/2 <= d(u,v) <= 4s. Then s <= 2 d(u,v) <= 2
Delta, hence r = s/16 <= Delta/8. Each bump lies in [0, r] by
construction, and the bumps are nonnegative, so 0 <= g <= r <=
Delta/8.
(G4) Amplitude at a padding point. Fix w with d(w, A) >= s/8
(when A is nonempty) and let C be the part of the random partition
containing w. On the padding event that B_d(w, alpha r) is inside
C (probability >= pi, independent of the coefficients), the bump
psi_C(w) satisfies
min{ d(w,A), d(w, V\C), r } >= min{ s/8, alpha r, r }
= alpha r.
(Since d(w,A) >= s/8 = 2r, and d(w,V\C) >= alpha r on the padding
event, and alpha r <= r.)
(G5) Truncation cap is well below d(w,w'). If w' is the "other"
endpoint at distance d(w,w') >= s > r = s/16, then w,w' lie in
different parts of any partition at scale r. So psi_C(w') = 0.
At each launch, replace two free particles with a common weak sorting
order on the interface by (f+g, f-g) as in Lemma 3.1, and reserve
them. The empty-interface launch has no sorting constraint. All
launches use fresh randomness (partition, coefficients); the particle
pair is chosen deterministically BEFORE the launch randomness is
sampled, by the first-eligible-pair rule of Prop 3.3.
The L = B = 3 choices. Lip(g) <= 1 and |g| <= Delta/8, so any choice
of L >= 1 and B >= 1/8 works. We use L = 3 and B = 3 to match Part 3,
giving U_bag = 3N(N-1) as in Prop 3.3 with L = 3.
--------------------------------------------------------------------------------
4.6 UPPER BOUND: D_bag <= U_bag * d
--------------------------------------------------------------------------------
Fix a bag B_t containing both endpoints of some graph edge uv. Its
trace mu_t on B_t equals the glued one, so by Lemma 3.1 and the
definition of the reserved particle list (as in the proof of Prop 3.3),
D_bag(u,v) = E_X [ D_{mu_t(X)}(u,v) ]
= E_X [ sum_i |F_i(u) - F_i(v)| ].
The inner sum satisfies, by the uniform particle bound of Lemma 3.2,
sum_i |F_i(u) - F_i(v)| <= N L(N-1) d(u,v). Compute:
N L(N-1) = 3 N (N-1) = U_bag,
since L = 3 and N = 2R + k! + 2.
So D_bag(u,v) <= U_bag d(u,v) for every edge uv. By the triangle
inequality along a shortest path (Part 1, Consequence A, applied to
D_bag as a path-summed metric from the edge bound), the same inequality
holds for all u,v in V. This proves (4.3).
--------------------------------------------------------------------------------
4.7 LOWER BOUND: D_bag >= a_bag * d(u,v) for pairs in a common bag
--------------------------------------------------------------------------------
Fix two distinct vertices u,v in a common bag B. The goal is to
exhibit a definite mass of separating cuts of D_bag.
STEP 1: A dyadic scale for the pair. Since d(u,v) > 0, there is a
unique integer j with 2^j <= d(u,v) < 2^{j+1}. Let s = 2^j. Then
s <= d(u,v) < 2s. (4.5)
In particular, s is active at B: s/2 <= s <= d(u,v) < 2s <= 4s.
STEP 2: The reserved pair carrying s. The pair reserved for scale s
at bag B is the unique pair launched at the beginning of the maximal
run of bags (along the current branch, from the root toward B) where s
was active. Trace back to the start of that run:
CASE 1 (root launch). The pair was launched at the root bag with
EMPTY interface. Pick w := u (either endpoint works; empty
interface imposes no constraint). Let w' := v.
CASE 2 (launched at a bag A where s was inactive). The bag A sits
STRICTLY ABOVE B on the tree path (A is a parent of some bag on
the run). At least one of u,v, say w, has d(w, A) >= s/8. For,
if both d(u,A) < s/8 and d(v,A) < s/8, then pick nearest points
a, b in A: by triangle inequality,
d(a,b) >= d(u,v) - d(u,a) - d(v,b)
> s - s/8 - s/8 = 3s/4,
d(a,b) <= d(u,a) + d(u,v) + d(v,b)
< s/8 + 2s + s/8 = 9s/4.
So 3s/4 < d(a,b) < 9s/4, hence s/2 <= d(a,b) <= 4s. Then a != b
(they are at positive distance), and a,b in A, so s would be active
at A. Contradiction. Hence choose w as the endpoint with
d(w,A) >= s/8, and w' := the other endpoint.
In both cases, the interface A satisfies d(w, A) >= s/8 when A is
nonempty; when A is empty, the term d(z,A) is dropped from the bump
and the amplitude estimate below is even simpler.
STEP 3: w and w' lie in different parts of the launch partition. The
launch partition was sampled at scale r = s/16. By (4.5),
d(w,w') = d(u,v) >= s > s/16 = r. So any part of the partition
contains at most one of w,w' (parts have diameter <= r). Let C be
the part containing w; then w' notin C.
STEP 4: Amplitude at w on the padding event. Let
EV := the event that the random partition at the launch puts
B_d(w, alpha r) inside C, where C is w's part.
By Theorem 4.1 (PP-pad), Pr(EV) >= pi. On EV, d(w, V\C) >= alpha r.
Combined with d(w,A) >= s/8 = 2r (Case 2) or d(z,A) omitted entirely
(Case 1), the bump psi_C at w satisfies
psi_C(w) = min{ d(w,A), d(w, V\C), r }
>= min{ 2r, alpha r, r } = alpha r.
(If Case 1, replace d(w,A) by "infinity" in the min; the bound
min{alpha r, r} = alpha r still holds.)
STEP 5: Conditional uniform coefficient. Condition on the launch's
random partition, on the choice of the reserved pair, and on all
coefficients U_{C} except the one for w's part. The pair choice is
made before the launch randomness is sampled (Section 4.5), so it is
independent of the partition and of the coefficients. Then
g(w) - g(w') equals
U_C * psi_C(w) + F,
where F collects the coefficients of the other parts. Since w' is not
in C, psi_C(w') = 0, so g(w') does not involve U_C at all, and F is
independent of U_C.
Let a := psi_C(w) >= alpha r (on EV) and let b := F. Since U_C is
uniform on [0,1] and independent of everything else,
E_{U_C} [ | a U_C + b | ] >= a / 4, (4.6)
where (4.6) is the elementary estimate
int_0^1 | a s + b | ds >= a / 4 (a > 0, b real).
Why a/4. The integrand is a |s - s_0| with s_0 = -b/a, and for every
real s_0
int_0^1 |s - s_0| ds >= 1/4,
with equality exactly when s_0 = 1/2. Indeed the integral is minimized
when s_0 is the midpoint of [0,1], and there it is the integral of the
tent |s - 1/2|, which equals 1/4. Multiply by a > 0 to get (4.6).
So, conditioned on the padding event EV (so a >= alpha r),
E[ |g(w) - g(w')| | EV, partition, other coefficients ] >= alpha r / 4.
Averaging over EV (probability >= pi):
E[ |g(w) - g(w')| ] >= pi * alpha r / 4 = pi * alpha * s / 64. (4.7)
STEP 6: Apply the paired perturbation to get a lower cut bound. At
the launch we replaced two particles with (f+g, f-g). Let
nu = (sigma_{f+g}^M)^{sym} + (sigma_{f-g}^M)^{sym}. By Lemma 2.4,
equation (2.7):
D_nu(u,v) = D_nu(w, w')
>= 2 |g(w) - g(w')|.
The two functions f+g and f-g are FROZEN from the launch bag A (or
the empty interface, at root) down to B, so nu | B <= mu_B by the
trace-domination property of Prop 3.3(iv).
Taking expectation over launch randomness and using (4.7),
D_bag(u,v) = E_X [ D_{mu_B(X)}(u,v) ]
>= E_X [ D_nu(u,v)(X) ] (mu_B dominates nu)
>= 2 * E_X [ |g(w)-g(w')|(X) ] ((2.7))
>= 2 * pi * alpha * s / 64
= pi * alpha * s / 32. (4.8)
STEP 7: Relate s to d(u,v). By (4.5), s > d(u,v)/2, so
D_bag(u,v) >= (pi * alpha / 32) * (d(u,v) / 2)
= (pi * alpha / 64) * d(u,v) = a_bag * d(u,v). (4.9)
For u = v, both sides are 0. This proves (4.4). []
The proof of Proposition 4.3 is complete.
Two remarks on what we have and what we do NOT yet have.
(i) D_bag controls pairs that share a bag. We have NO lower bound
for a pair u,v in bags that are far apart in T. That is where
Part 5 enters.
(ii) The construction above used NO SPECIFIC STRUCTURE of the
metric besides (a) bounded active scales per bag and (b) the
padded-partitions theorem. Both are consequences of treewidth at
most k-1; nothing else about the graph is used in this part.
================================================================================
================================================================================
PART 5. THE ANCHOR METRIC D_anc
================================================================================
D_bag gives a lower bound for pairs that share a bag (Part 4). Pairs
in distant bags get nothing from D_bag. The role of D_anc is to give a
"leash" between a chosen early bag and any descendant bag, so that
distant pairs get separated too.
The construction is again particle-based, but with a different
schedule. Along every descending path of T (from the root toward a
leaf), we keep a BOUNDED-SIZE CACHE of "anchors". Each anchor is a
reserved particle pair launched at some bag occurrence A (its LAUNCH
bag). The pair is FROZEN until the anchor is evicted. Each anchor is
equivalently attached to a specific vertex set B_A (its launch bag's
vertex set); distinct occurrences of the same set give DISTINCT
possible anchors (Part 0, S2).
At a bag B_t, we PROPOSE a new anchor launched at B_t. If the cache
is at capacity, we must EVICT one existing non-root anchor. A
DETERMINISTIC EVICTION RULE is what protects enough ancestors from
eviction; it uses only the metric and the decomposition, NOT the
randomness of the launch noise. Section 5.2 spells out the rule.
Throughout PART 5: (V,d) finite connected metric graph, tree
decomposition of bag size at most k, |V| >= 2, bags nonempty.
--------------------------------------------------------------------------------
5.1 ORDINARY LAUNCH NOISE: A LEMMA WITH TWO INDEPENDENT PIECES
--------------------------------------------------------------------------------
At an anchor launch at a bag A, we put a perturbation g_A into two
particles. The perturbation is DETERMINED by fresh randomness
independent of everything sampled so far, and given by
g_A = xi_A * h_A + v_A, (5.1)
where:
h_A(z) := d(z, A) is the distance-to-A function;
xi_A is uniform on [1, 2], independent of v_A;
v_A is a "local noise" function constructed as follows.
Fix a parameter 0 < eta < 1/4 (small; chosen later, in 5.6).
The function v_A = v_A^{eta, A} is built as follows. First divide the
POSITIVE values of h_A into DYADIC BANDS by a uniformly chosen SHIFT
lambda in [0, 1). Then sample a padded partition per band, and give a
uniform coefficient to each (part, band) bump. The detailed
construction and its key properties are the content of the following
lemma.
Every anchor launch at a bag occurrence A satisfies these properties.
For the root the empty-interface launch is the special case A = empty.
LEMMA 5.1 (Ordinary launch noise). Let A subseteq V be NONEMPTY, put
h(z) = d(z, A), and let 0 < eta < 1/4. One can sample a random
function
g = xi * h + v (5.1')
using randomness independent of all previously sampled data, such
that:
(form of v) v is constructed in two stages. First sample a
finite indexed family of NONNEGATIVE functions (phi_i)_{i in I} on V
(the "bumps"), then set
v = sum_{i in I} U_i * phi_i,
where the coefficients U_i are independent, uniform on [0, 1],
conditional on the bump family.
(coefficient xi) xi is uniform on [1, 2], independent of the
bumps and all coefficients.
(MEASURABLE) All random objects are measurable, and I is finite.
Properties:
(N1) v is 1-Lipschitz, satisfies 0 <= v <= eta h / 2, and vanishes
on A. Consequently (with h|A = 0) g|A = 0, and Lip(g) <= 3. And
h(z) <= g(z) <= (5/2) h(z) <= (5/2) Delta for every z in V.
(N2) Amplitude of a distinguished bump. Set c := alpha / 8 and
rho := pi / 2. For each fixed x with D_0 := h(x) > 0, there is an
event E_x (depending only on the bump family, not on coefficients)
of probability at least rho, and an index i(x) (a measurable
function of the bump family) such that the bump phi_{i(x)} satisfies
phi_{i(x)}(x) >= c * eta * D_0, (5.2)
phi_{i(x)}(z) = 0 if d(x, z) > 4 * eta * D_0. (5.3)
Write U_x := U_{i(x)}. Conditional on the bump family, U_x is
UNIFORM and INDEPENDENT of xi, of the other coefficients, and of all
previously sampled data. In particular,
v = v^{\setminus x} + U_x * phi_{i(x)}, (5.4)
where the coefficients defining v^{\setminus x} are independent of
U_x.
Different vertices may select the same bump and coefficient (we only
pick one bump per tested vertex). All constants (c, rho, etc.) are
uniform in eta, A, |V| and the ratio of edge lengths.
Proof.
Step A (Setup: bands and partitions). If h is identically 0 on V
(that is, A = V), set v := 0 and return. Otherwise let h_min > 0 be
the smallest positive value of h on V and h_max the largest. Sample
lambda uniformly on [0, 1), then define
I := { floor(log_2 h_min) - 1, ..., floor(log_2 h_max) },
m := floor(log_2 eta),
and for each integer j in I:
Band: W_j := { z in V : 2^{j+lambda} <= h(z) < 2^{j+1+lambda} }.
Scale: r_j := 2^{j+m}.
The bands W_j (j in I) partition {z : h(z) > 0}.
Independently of lambda, for each j in I sample a padded partition
P_j at scale r_j from Theorem 4.1. (So the partition scales are
FIXED powers of two, not random functions of lambda. Conditioning on
lambda leaves each partition with its original padding guarantee.)
Step B (Bumps). For each nonempty intersection E = W_j cap C,
C in P_j, define
min{ r_j/2, d(z, V\E) } if z in E,
phi_{j,C}(z) = {
0 if z notin E.
Each phi_{j,C} is nonnegative, supported on E, and 1-Lipschitz on
V. [The minimum of two 1-Lipschitz functions and a constant.]
The sets E are pairwise DISJOINT (they are intersections of bands
that partition {h > 0}, one with each part C of the partition at
that band). So by Lemma 4.2 with all u_i bounded by 1, the sum
v := sum_{j,C} U_{j,C} phi_{j,C} is 1-Lipschitz.
Step C (Bounds on v). For z in V:
If h(z) = 0 then z is in A, because d(z,A) is a minimum over the
vertices of A and distinct vertices are at positive distance. So
h = 0 at z, and each phi_{j,C}(z) = 0 as well, since the support
W_j is the set {h > 0}. Hence v(z) = 0.
If h(z) > 0, then z lies in exactly one band W_j, j = j(z). Its
part C = C(z) in P_j contains z. We have phi_{j,C}(z) >= 0 (and
<= r_j/2), and all other bumps phi_{j',C'} vanish at z (disjoint
support). So
0 <= v(z) <= r_j/2 <= eta 2^j / 2 <= eta h(z) / 2.
(Using r_j = 2^{j+m} <= 2^{j-1} eta, since m = floor(log_2 eta)
gives 2^m <= eta.)
Step D (Combination with xi h). Since g = xi h + v, with xi in [1,2]
and 0 <= v <= eta h / 2 <= h / 2 (as eta < 1), we have h <= g <= (5/2) h.
So g|A = 0 and Lip(g) <= Lip(xi h) + Lip(v) <= 2 * 1 + 1 = 3. Also
g <= (5/2) h <= (5/2) Delta. This is (N1).
Step E (Amplitude of a distinguished bump, per vertex). Fix x with
D_0 = h(x) > 0. Let j be the band index of x under the realized
lambda.
Consider the auxiliary event
E* := { log_2 D_0 - (j + lambda) is in [1/4, 3/4] }. (5.5)
Its probability is 1/2 (over lambda). On E*, D_0 is at a distance
greater than D_0 / 8 from BOTH numerical endpoints 2^{j+lambda} and
2^{j+1+lambda} of the band. Since h is 1-Lipschitz, the whole ball
B_d(x, D_0 / 8) lies inside W_j. And r_j <= eta D_0 (by 2^m <= eta
and 2^{j+lambda} <= D_0), so alpha r_j < D_0 / 8.
Conditioned on lambda, the probability that B_d(x, alpha r_j) lies
inside the same part C of P_j as x is at least pi, by (PP-pad).
Let PAD_x := the event that this padding holds for the part C = C(x)
of the realized band W_j.
On E* and PAD_x simultaneously:
phi_{j,C}(x) >= min{ r_j/2, d(x, V\C) }
>= min{ r_j/2, alpha r_j } (PAD_x)
= alpha r_j (using alpha <= 1/2 in fact <= 1/8)
>= alpha * (eta D_0 / 8) (2^m >= eta/2)
= c * eta * D_0, (5.6)
with c = alpha / 8.
Support radius of phi_{j,C}: any z with phi_{j,C}(z) > 0 lies in E
subseteq C, hence in the same part C as x. Parts have diameter <= r_j
<= eta D_0. So d(x, z) <= r_j <= eta D_0 <= 4 eta D_0. This gives
(5.3).
The joint event E* cap PAD_x has probability at least rho := (1/2) pi.
It depends only on lambda and the partition family P_j (not on
coefficients). So define E_x := E* cap PAD_x and let phi_x be the
associated bump phi_{j, C(x)}. On E_x, (5.2) and (5.3) hold. A
deterministic tie-breaker (fixed ordering of (j, C)) selects a unique
i(x) in case multiple bumps happen to satisfy both displayed bounds.
Step F (Uniformity and independence of U_x). The coefficients U_{j,C}
are sampled independently of the bump locations, with uniform law on
[0, 1] each. Conditional on all bumps, U_x = U_{i(x)} is uniform on
[0,1] and independent of xi and of all U_{i'} with i' != i(x). This
is exactly the statement (5.4). []
Two sanity checks. First, all randomness is finite: one padded
partition per band, and there are finitely many bands because V is
finite. Second, none of the constants c, rho, alpha, pi depends on
eta, on A, on |V|, or on the ratio of edge lengths. []
REMARK ON "AT LEAST rho" AND ON "DETERMINISTIC SELECTION". The event
E_x has probability at least rho depending only on (lambda, partition
family) for the FIXED vertex x selected by the metric. In Part 5, x
will be p in a bag B (nearest to the failing point), and B is chosen
deterministically from the metric and cache. So the choice of x does
not condition on xi_A or on the "distinguished" coefficient U_x.
This is what lets us argue afterwards that fresh uniform variables
U_x, xi_A are independent of the past.
--------------------------------------------------------------------------------
5.2 THE CACHE OF ANCHORS: A DETERMINISTIC EVICTION RULE
--------------------------------------------------------------------------------
Set
n_0 := 2 k^2 + 2. (5.7)
The CACHE at any node is a LIST of anchors ordered by LAUNCH TIME, from
OLDEST (first launched) to YOUNGEST (last launched). It is stored in
the same memory as the particle list and reservations.
At a node t:
If t is the root bag B_root: launch one anchor (using the EMPTY
interface), record it as the (only) entry. The root anchor is
PERMANENT: it is never evicted below.
If t is any other bag: PROPOSE a new anchor launched at B_t.
If the resulting list (old + proposed) has <= n_0 entries, retain
it (no eviction).
If it has n_0 + 1 entries, EVICT exactly one non-root entry by the
RULE below. The proposed anchor itself is an eligible eviction.
Branching: if t has several children, each child gets a COPY of the
current cache.
THE EVICTION RULE (deterministic from metric and decomposition).
Fix a parameter J > 0, chosen later. At the current bag B = B_t:
For every ORDERED PAIR of distinct vertices (p, q) in B, and every
THRESHOLD tau in the pair of thresholds
tau in { d(p,q) / 100, J * d(p,q) }, (5.8)
consider the sequence d(p, A_1), d(p, A_2), ..., d(p, A_m) where
A_1, ..., A_m are the anchors in the inclusive list at B (including
the proposal), in launch order (oldest first).
By Lemma 0.1(c), this sequence is NONINCREASING (each later anchor
occurs between its predecessor's node and B, so distances drop
monotonically).
PROTECT the entry IMMEDIATELY FOLLOWING (that is, the entry with
index k + 1) any DROP from d(p, A_k) > tau to d(p, A_{k+1}) <= tau.
If there is no such drop for this (p,q,tau), it protects no entry.
EVICT the OLDEST non-root entry that is NOT PROTECTED.
All tie-breaking (which pair (p,q), which threshold, which "oldest")
is deterministic from the metric and decomposition and the cache
state, all BEFORE any launch randomness is used.
Per-copy reservation count is bounded by n_0 + 1 = 2k^2 + 3.
--------------------------------------------------------------------------------
5.3 THE CACHE IS WELL DEFINED
--------------------------------------------------------------------------------
LEMMA 5.2 (Cache consistency). The displayed distance list is
nonincreasing. At a full insertion (n_0 + 1 entries) there is always
an eligible (i.e. non-protected) non-root entry to evict. The
resulting cache has at most n_0 entries. The number of simultaneous
reservations, counting the proposal AND the evicted anchor, is at most
n_0 + 1.
Proof.
(Nonincreasing distance list.) Let A_1, A_2 be two anchors with A_1
launched earlier than A_2, so A_2's launch node lies between A_1's
launch node and B on the tree path to B. By Lemma 0.1(c), the
sequence d(p, A_1_node), d(p, A_2_node) is nonincreasing along the
path, giving d(p, A_2) <= d(p, A_1).
(Eligible eviction exists.) Each fixed (p, q, tau) protects AT MOST
one entry: the list is nonincreasing, so it crosses the level tau at
most once, and only the entry right after that crossing is protected.
A bag with at most k vertices has at most k(k-1) ordered pairs (p,q),
and each pair carries two thresholds, so at most 2k(k-1) entries are
protected in total (fewer if a single entry is protected by several
triples). At a full insertion there are n_0 + 1 entries, of which
n_0 are non-root, and
2 k (k-1) < 2 k^2 + 2 = n_0 for every k >= 2,
so at least one non-root entry is unprotected. Hence an eviction is
always possible.
(Bounded reservation count.) At a full insertion there are n_0 + 1
entries: the old n_0, unchanged, plus the proposal. Each entry costs
one reserved particle pair, so the reservation count is n_0 + 1 at
that moment, and n_0 after the eviction. The maximum simultaneous
reservation count is therefore n_0 + 1, attained transiently at a full
insertion before the eviction. []
--------------------------------------------------------------------------------
5.4 REALIZATION OF THE ANCHOR CACHE
--------------------------------------------------------------------------------
Set
q_0 := n_0 + 1, (5.9)
N := 2 q_0 + k! + 2 = 2(2k^2 + 3) + k! + 2. (5.10)
The reservation cap q = q_0 fits the maximum simultaneous reservations
of Lemma 5.2. So Proposition 3.3 applies with q = q_0, and we get
consistent bag measures mu_t with mass m = 2 N M, upper bound
D_anc := the glued pseudometric associated with (mu_t) (5.11)
<= U * d(u,v) for all u,v in V,
U := 3 N (N-1). (5.12)
The particles satisfy uniform bound Lip(F_i) <= 3 (N-1), so the anchor
construction gives a pseudometric D_anc of upper Lipschitz constant
U = 3N(N-1) that depends only on N (hence on q_0 and k), NOT on J or
eta. [The parameters J, eta only enter the CACHE RULE and the NOISE,
not the metric's upper bound.]
Define the ANCHOR at a launch: it is the bag A at which the launch was
performed together with the two particles (F_1, F_2) that were
selected for the update.
--------------------------------------------------------------------------------
5.5 TWO TESTS ALONG A RESERVATION
--------------------------------------------------------------------------------
Fix a path of bags from a bag containing y (the "y-end") to a later bag
containing z (the "z-end"). Along this path:
Anchors are reserved; their pairs of particles stay unchanged; the
submeasure nu_A := (sigma_{F_1}^{M})^{sym} + (sigma_{F_2}^{M})^{sym}
associated with the launch is a common submeasure of every bag law
on the reservation segment.
Two tests use this. Both allow the later bag to be the eviction bag
of the anchor (as in Prop 3.3(iv)).
LEMMA 5.3 (Two tests along a reservation).
(LAUNCH TEST) If an anchor A lies on this bag path and its
reservation lasts from A through the later bag containing z, then
D_anc(y, z) >= b_k d(z, A). (5.13)
(HEIGHT TEST) Suppose a testing bag P lies on the bag path, and
some reserved particle F for A is unchanged from P through the
later bag containing z. If, with probability at least theta
(over the launch randomness only, NOT the past), F satisfies
|F(z) - F(s)| >= t for every s in P, (5.14)
where 0 < t <= Delta, then
D_anc(y, z) >= b_k * theta * t. (5.15)
The tested reservation and the vertices P are CHOSEN WITHOUT
CONSULTING the launch randomness.
Proof.
(LAUNCH TEST) At the anchor A, the launch perturbation is
g_A = xi_A h_A + v_A, which by (N1) is at least d(.,A) in absolute
value on V, vanishes on A, and is at most (5/2) d(., A). The pair
after launch is f_A + g_A and f_A - g_A where g_A | A = 0. The
reserved pair therefore yields a common submeasure nu_A that by
Lemma 2.4 has E_{nu_A}(z | A) >= 2|g_A(z)|. Since |g_A(z)| >= d(z,A) / 2
(by 1 <= xi_A and 0 <= v_A <= h_A/2, so g_A >= h_A/2), we have
E_{nu_A}(z|A) >= d(z,A). Apply Proposition 2.2 with P = A on the bag
path from the y-bag to z. Prop 2.2 gives D_anc(y, z) >= b_k * d(z, A) pointwise in
launch randomness; average over all launch randomness to obtain the
displayed bound.
(HEIGHT TEST) For each realization of the launch randomness, the
symmetrized sweep sigma_F^{M, sym} is a common submeasure of the bag
laws along the reservation from P through the later bag. On the
event (5.14), by Lemma 2.3 the uncertainty is at least t at z given
P. Proposition 2.2 gives D_anc(y,z) >= b_k * t on that event. Average
over the launch randomness, using that the event has probability at
least theta by hypothesis:
E[ D_anc(y, z) ] >= b_k * theta * t. []
The height test is used as follows. We use a FIXED particle
F = f_{A*} + xi_{A*} h_{A*} + v_{A*} of a chosen anchor A*. The
particle was frozen on the reservation, so F is identical along the
reservation. We pick the testing bag P and the two vertices freely
from the metric and cache, then apply Lemma 5.3 with F. The randomness
in (5.14) is the launch randomness at A* (xi and coefficients U_i),
which was chosen BEFORE P was viewed; so theta is "probability over
launch randomness only", independent of P and of the past.
Similarly, the LAUNCH test is used when the anchor A itself lies on
the bag path from the y-bag to z. Then D_anc(y,z) >= b_k d(z,A).
Both tests are POINTWISE in the launch randomness and the earlier
past. Averages over the launch randomness preserve the bound.
--------------------------------------------------------------------------------
5.6 PARAMETER CHOICES
--------------------------------------------------------------------------------
The preceding construction and both tests hold for every J > 0 and
0 < eta < 1/4. We now FIX a specific member of the family:
K > 2 + (2 U + 1) / b_k, (5.16)
J = 10 (K + 1),
H > 10^5 * J,
0 < eta < 1 / (10 H).
All parameters depend only on k, in particular not on the metric or the
tree decomposition. From this point onwards, D_anc denotes the
pseudometric coming from this choice of eta and J.
Four notes on why these are chosen this way:
(H BIG relative to J) H > 10^5 J is needed later so that "distances
above H" are far beyond "distances around 300 J". In the LOWER
comparison argument, a bare inequality like D_0 > H (D_0 is the
anchor distance at the failing point x) then dwarfs quantities of
order J or 300 J.
(J BIG relative to K) J = 10(K+1) is needed so that the threshold
J * L (with L in the obstruction lemma, which is at most 300 or at
most D_0, see Part 6) straddles between "short" (at most K delta)
and "long" (at least D_0 - 1) anchor distances from p.
(K BIG relative to b_k) K > 2 + (2U+1) / b_k guarantees, via the
launch test, that the immediate successor of A* has d(p, A') at most
K delta whenever delta d is "early"; see Part 6, Lemma 6.9. The
"+2" accounts for the ratio D(y,x)/delta approaching 0 slowly.
(eta SMALL relative to H) 0 < eta < 1/(10H) then makes the local
noise concentration radius 4 eta D_0 < 1/(10 * 1) (with D_0 <= H)
much less than 1, so the noise hits only an infinitesimal tube
around the endpoint x, leaving every testing-bag vertex FAR away.
================================================================================
================================================================================
PART 6. THE UNIFORM LOWER COMPARISON
================================================================================
This part proves: D_bag + D_anc is comparable to d from below, uniformly
in the size, edge lengths, and decomposition. The comparison failure
sequence, if there were one, would produce a "youngest reservation
crossing from bounded distance to vanishing distance". The launch
noise on that reservation, plus the eviction rule, forbids such a
reservation by selecting a younger one. We work it out explicitly.
Throughout PART 6, we fix (V,d) as usual, tree decomposition of bag
size at most k, D_bag from Part 4, D_anc from Part 5 (with the fixed
parameters of 5.6).
--------------------------------------------------------------------------------
6.1 FROM "FAILS UNIFORMLY" TO A NORMALIZED SEQUENCE
--------------------------------------------------------------------------------
Suppose, towards a contradiction, that the constructed sum
D_bag + D_anc has NO uniform positive lower comparison with d, i.e.
there is no constant c > 0 with D_bag(u,v) + D_anc(u,v) >= c d(u,v)
for all inputs and all pairs. Then there is a SEQUENCE of examples:
for each n in N, a graph+lengths+decomposition with distinct vertices
x_n, y_n, such that, writing r_n := d(x_n, y_n) for the metric of the
n-th example,
( D_bag(x_n, y_n) + D_anc(x_n, y_n) ) / r_n -> 0. (6.1)
We call (6.1) the FAILING COMPARISON SEQUENCE.
COMPACTNESS TOOL. We fix a NONPRINCIPAL ULTRAFILTER calligraphic U on
N (existence by Zorn's lemma). For any ASSERTION about the index n,
write
"eventually P_n" iff {n in N : P_n holds} in U.
Sequences (s_n) and (s'_n) are IDENTIFIED when they agree eventually.
Any REAL-valued sequence bounded by a fixed constant C converges
along U to a "standard" real in [-C, C]; sequences NOT converging are
treated as alternative branches (mutually exclusive eventual
alternatives). We use the following elementary toolkit.
LEMMA 6.1 (Ultrafilter toolkit). For all sequences below:
(a) Of finitely many alternatives whose union holds eventually, at
least one holds eventually. Finitely many eventual assertions
hold simultaneously eventually.
(b) A sequence in [0, 1] that is not infinitesimal (does not tend
to 0 along U) is eventually bounded below by a POSITIVE standard
real. A finite minimum of such sequences has the same property.
(c) Sequences of "times" ordered along finite linearly ordered bags
are linearly ordered modulo U. If delta_n in [0,1] is nonincreasing
along each path, a time sequence with noninfinitesimal delta
precedes every time sequence with infinitesimal delta.
(d) A sequence that has a positive standard lower bound and a
sequence that is infinitesimal have their sum non-infinitesimal.
Proofs are immediate from the finite-union and finite-intersection
properties of ultrafilters. []
We will freely say "a = o(b)" for positive sequences b_n when
|a_n|/b_n -> 0 along U (that is, a_n/b_n is infinitesimal). We use
"o(1)" for an infinitesimal sequence.
From here on, all vertices, bags, and metrics denote SEQUENCES in the
failing examples; equations and inequalities are "eventually" unless
stated otherwise, and metric expressions like d(x,S) are the per-index
values, ordered by U. The reader may replace "eventually" with
"for all large n" throughout on a first pass.
--------------------------------------------------------------------------------
6.2 THE LEAST COMMON ANCESTOR AND NORMALIZATION
--------------------------------------------------------------------------------
Choose a bag X_n containing x_n and a bag Y_n containing y_n. Let
S_n be the LEAST COMMON ANCESTOR of X_n and Y_n in the tree T_n (rooted
at whatever node Part 3-5 selected). Then S_n is at the bottommost
place where the bag paths to X_n and to Y_n diverge; both X_n and Y_n
have S_n as ancestor.
Lemma 0.1(a) gives: every x_n-y_n path meets S_n, so
d(x_n, S_n) <= r_n, d(y_n, S_n) <= r_n. (6.2)
The two ratios on the left divided by r_n CANNOT BOTH BE
INFINITESIMAL. For suppose both were o(r_n). Choose nearest
vertices s_x, s_y in S_n to x_n, y_n. Then
D_bag(s_x, s_y)
<= D_bag(s_x, x_n) + D_bag(x_n, y_n) + D_bag(y_n, s_y) (triangle in D_bag)
<= (U_bag d(x_n, S_n)) + o(r_n) + (U_bag d(y_n, S_n)) (upper bounds)
= U_bag * o(r_n) + o(r_n) + U_bag * o(r_n)
= o(r_n).
(We used (4.3) for the two end terms, valid because both x_n and
s_x are the two endpoints of the edge-like path x_n -> s_x, and
D_bag(x_n, s_x) <= U_bag d(x_n, s_x) = U_bag d(x_n, S_n). Same for
y_n, s_y. And D_bag(x_n, y_n) = o(r_n) by the FAILING COMPARISON
SEQUENCE: D_bag <= D_bag + D_anc = o(r_n).)
On the other hand, s_x and s_y are both in the bag S_n, so by the
co-bag lower bound (4.4):
D_bag(s_x, s_y) >= a_bag * d(s_x, s_y).
And by the triangle inequality in d:
d(s_x, s_y) >= d(x_n, y_n) - d(x_n, s_x) - d(y_n, s_y)
= r_n - d(x_n, S_n) - d(y_n, S_n)
= r_n (1 - o(1)).
So D_bag(s_x, s_y) >= a_bag r_n (1 - o(1)), contradicting
D_bag(s_x, s_y) = o(r_n), because a_bag > 0.
Therefore the two ratios are NOT both infinitesimal; at least one is
not infinitesimal.
INTERCHANGE if necessary. Swap the names of x_n and y_n so that
a_n := d(x_n, S_n) satisfies a_n / r_n >= eps_0 > 0
eventually. (6.3)
(Equivalently: after interchange, d(x_n, S_n) is not infinitesimal
relative to r_n. Use Lemma 6.1(b).)
NORMALIZE. Discard the irrelevant indices (which are "not in U", so
do not affect any eventual statement). Rescale the whole example by
1/a_n: metric d -> d / a_n, particle heights F_i -> F_i / a_n, cut
mass -> cut mass / a_n. All our constructions, bounds, and noise
properties survive the rescaling:
* d(u,v) = a_n * (rescaled) - so d(x_n, S_n) becomes 1;
* the inequalities (D_bag <= U_bag d) and (D_anc <= U d) scale
identically on both sides;
* the noise variables xi_A, U_C are unchanged by rescaling (they are
dimensionless); only the FUNCTIONS h_A, v_A, and the cutoff M
scale;
* the bump amplitude and support bounds hold for the RESCALED
metric without regenerating the partition samples.
Write D := D_anc in the rescaled units, and x, y, S for x_n, y_n, S_n
(now scaled so that d(x,S) = 1). We have:
d(x, S) = 1 (normalized), (6.4)
D(x, y) infinitesimal, (6.5)
D(., .) <= U d pointwise, (6.6)
d(x, y) = r_n / a_n in [1, inf) eventually.
The last expression r_n / a_n: since a_n <= r_n by (6.2), the
rescaled r_n/a_n is at least 1. We do not require an upper bound on
r_n/a_n.
D_bag is also rescaled. The failing comparison reads
D_bag(x, y) + D(x, y) = o(r_n / a_n),
and both terms on the left are nonnegative, so each is separately
o(r_n / a_n). In particular D(x, y), the anchor metric's value, is
infinitesimal; (6.5) records this. The same conclusion is NOT
guaranteed for D_bag: "o(r_n/a_n)" expresses relative vanishing, but
r_n/a_n can be unbounded as n varies, so "o(r_n/a_n)" could still be
a large absolute number, or O(1).
So we will NOT use D_bag(x, y) in the analysis below. The lower-bound
arguments in Parts 6.5-6.8 work entirely with D := D_anc, and only
ever invoke D(x, y) = o(1) (plus the pointwise upper bound D <= U d).
The "normalized failure" statement we will use is
D(x, y) infinitesimal (D_anc after normalization). (6.7)
--------------------------------------------------------------------------------
6.3 EARLY AND LATE BAGS
--------------------------------------------------------------------------------
Fix the descending path from S to X (both bags of T; S contains some
vertices, X contains x_n). For each bag B_t on this path, put
delta_t := d(x_n, B_t). (6.8)
Apply Lemma 0.1(c) with the role of "A" there played by the point
set {x_n}: the path runs from S to X, and x_n is in X, so the
distance-to-{x_n} function is monotone nonincreasing along the path.
Thus delta_t is NONINCREASING in the index t. Moreover delta at S = 1
(by (6.4)), and delta at X = 0 (by x_n in X).
Call a sequence (n -> selected bag B_n on the path) EARLY if
delta_{B_n} is not infinitesimal, and LATE if delta_{B_n} is
infinitesimal. An EARLY sequence has a POSITIVE STANDARD lower bound
for its delta (Lemma 6.1(b), applied to delta_{B_n}/1); we will write
this as delta_{B_n} >= epsilon > 0 (with epsilon possibly depending on
the sequence).
Note: we do NOT assume a "first late bag" or "last early bag" exists.
The classification is now on SEQUENCES of bags; early and late
sequences may interleave in index n, and the whole classification is
sequentially coherent only via U.
--------------------------------------------------------------------------------
6.4 CROSSING ANCHORS AND THE YOUNGEST ONE
--------------------------------------------------------------------------------
Along the descending path from S to X, consider ALL anchors A from the
CACHE of PART 5 whose reservation MEETS this path. Each anchor A has:
(launch bag) the node of T at which A was proposed;
(effective start) the first bag of the path at which A is
present, i.e. max(S, launch bag) in ancestry
order. If A launched strictly above S, its
effective start is S.
(terminal bag) the first bag of the path at which A is evicted,
or X if A survived to X.
Restrict each anchor's reservation to the path, truncating at X if not
evicted earlier. All launch and terminal bags are deterministic from
the metric and cache; in particular they do NOT depend on the launch
noise (only on the deterministic eviction rule of 5.2).
Define: an anchor sequence (n -> A_n) is CROSSING if
(effective start is early) AND (terminal bag is late).
Equivalently: launched by some early time and still present at some
late time.
Recall an anchor sequence is an EQUIVALENCE CLASS modulo equality on a
set in U. Its launch time and terminal time are the sequences of
launch/terminal bag times for that class.
LEMMA 6.2 (A youngest crossing anchor). There are at most n_0 + 1
DISTINCT crossing anchor sequences. The set of crossing anchor
sequences is nonempty and has a YOUNGEST member, A*.
Proof.
(Nonempty) The permanent root anchor is crossing (launched at S or
above S, present from S onward, never evicted, so present at every
late time too).
(At most n_0 + 1 distinct sequences) Given any finite collection of
crossing anchor sequences, take their LATEST effective start (along
each n). By Lemma 6.1(a), the latest is early (since finitely many
early alternatives). Then every anchor in the collection has started
by this time, and its LATE terminal time follows this early time (by
Lemma 6.1(c)). So all of them are simultaneously present at the same
time. The cache size at any moment is bounded by n_0 + 1 (Lemma 5.2).
Thus if there were n_0 + 2 distinct crossing sequences, the n_0 + 2
selected anchors would be simultaneously present, contradicting the
cache bound. So the class of crossing sequences has size at most
n_0 + 1.
(Youngest exists) The finite set of crossing anchor sequences is
partially ordered by launch time; any two are comparable (they are
sequences of launch times along the same root path); by Lemma 6.1(a),
one is (eventually) before or equal to the other; so the order is
linear. A finite set has a maximum. []
Fix this A* and define:
h_* := d(., A*) (distance-to-A*-function)
D_0 := h_*(x_n) (distance from x_n to A*'s bag)
Z := a LATE terminal bag of A* (an anchor-crossing bag
existence guaranteed by A* being crossing)
z := a vertex of Z nearest x_n.
Then:
d(x_n, z) is infinitesimal (Z late)
(6.5) and the upper bound D(.,.) <= U d give
D(y_n, z) <= D(y_n, x_n) + U d(x_n, z) (6.9)
infinitesimal + infinitesimal = infinitesimal.
We use the LAUNCH test (Lemma 5.3) with anchor A* and its birth
reservation; the point x_n plays a role only via testing bags on the
reservation. Specifically, we will prove lemmas showing that, for
every early testing bag B on A*'s reservation ending at Z, plus the
LATE proxy z, we get a CONTRADICTION with (6.9) - forcing constraints
on the geometry (D_0, d(p, A*), etc.).
--------------------------------------------------------------------------------
6.5 THE CROSSING ANCHOR IS OLD AND DISTANT
Recall D_0 = h_*(x_n) = d(x_n, A*).
LEMMA 6.3 (The crossing anchor is old and distant). The launch bag
of A* lies strictly ABOVE S on the tree, and D_0 > H eventually (in
normalized units). In particular, A* is present at every selected
early bag on the path from S down to X.
Proof.
Part 1 (Launch must be strictly above S). Suppose the launch bag L of
A* sat on the S-to-X path (at or below S). Two facts.
(a) L lies on the bag path from Y_n (the chosen y-bag) to the
terminal bag Z of A*. Since A* is CROSSING, its effective start
max(S, L) is early. If L is at or below S, then S precedes L on
the descending path, so effective start = L, hence L is an EARLY
bag. On the other hand, A* is present at Z, so Z is at or below L
(a reservation running from L to Z visits Z only after L; if L
were below Z the reservation would not include Z). So the segment
L-to-Z lies inside S-to-Z, which is inside the Y_n-to-Z bag path.
Hence (a).
(b) The LAUNCH test (5.13), with A = L, y = y_n, z = z, gives
D(y_n, z) >= b_k d(z, A*). (*)
By the triangle inequality in d,
d(z, A*) >= d(x_n, A*) - d(x_n, z) = D_0 - o(1).
Because L is an EARLY bag, d(x_n, L) has a positive standard lower
bound eps_0 > 0 (Lemma 6.1(b)). Since A* = L as bags, this is
D_0 = d(x_n, A*) >= eps_0. Therefore D(y_n, z) >= b_k (eps_0 -
o(1)) >= b_k eps_0 / 2 > 0.
But D(y_n, z) is infinitesimal by (6.9). Contradiction. So the
launch bag of A* is strictly ABOVE S. [Part 1 ends]
Part 2 (D_0 >= 1). From Part 1, A*'s launch bag lies above S on T.
Every path from x_n (in a bag below S) to any vertex of A*'s launch
bag must meet the bag S (Lemma 0.1(a)). Hence
D_0 = d(x_n, A*) >= d(x_n, S) = 1. (6.10)
The reservation of A* runs from above S, through S (since we just
showed D_0 > 0 and A* launched above S), and continues to a late
terminal bag (by the CROSSING property). So A* is present at every
selected early bag on the path from S down to X.
Part 3 (D_0 > H). We prove the contrapositive: assume D_0 <= H and
derive a contradiction with (6.9). Fix the "+" member of A*'s
reserved pair, which is the frozen particle
F := f_{A*} + xi_{A*} h_{A*} + v_{A*}. (6.11)
We use it in a HEIGHT test with testing bag P = S and terminal bag Z.
Step 3a (distinguished bump at x_n). By Lemma 5.1(N2), there is an
event EV (probability at least rho = pi/2, determined by A*'s bump
family alone) on which a DISTINGUISHED bump phi_x of A*'s local noise
satisfies
phi_x(x_n) >= c eta D_0 >= c eta, (6.12)
phi_x(y) = 0 if d(x_n, y) > 4 eta D_0. (6.13)
(c = alpha/8; the constant rho = pi/2.) Because 4 eta D_0 <= 4 eta
H < 1 (our choice eta < 1/(10 H)), and d(x_n, s) >= 1 > 0 for every
s in S (x_n notin S by d(x_n, S) = 1), phi_x(s) = 0 for every s in S.
Step 3b (uniform exclusion of the distinguished coefficient). On EV,
the frozen particle F = F_0 + U_x phi_x, where U_x in [0,1] is the
uniform coefficient of phi_x and F_0 collects f_{A*}, xi_{A*} h_{A*},
and all other bumps of A*'s noise (everything except U_x). Conditional
on EV and on everything except U_x, fix s in S. Since phi_x(s) = 0,
the value F(s) does not depend on U_x, and the inequality
|F(x_n) - F(s)| < t excludes at most
2 t / phi_x(x_n) <= 2 t / (c eta)
of the unit interval of U_x. A union bound over the at most k
vertices of S gives
Pr[ exists s in S : |F(x_n) - F(s)| < t | EV, rest ]
<= k * 2 t / (c eta). (6.14)
Choose the positive standard t in (0, 1/4] so that 2 k t / (c eta) <
1/2. Then the right side of (6.14) is < 1/2.
Step 3c (transfer to Z and height test). On the joint event (EV and
the good U_x, probability >= rho/2), we have
|F(x_n) - F(s)| >= t for every s in S.
Applying the Lipschitz bound on F (Lip(F) <= L_p = 3(N-1)) and the
fact that d(x_n, z) is infinitesimal (Z is late, z nearest x_n in Z),
|F(z) - F(x_n)| <= L_p d(x_n, z) = o(1).
Combining, for every s in S,
|F(z) - F(s)| >= |F(x_n) - F(s)| - |F(z) - F(x_n)|
>= t - o(1) >= t/2 (eventually).
The HEIGHT test (Lemma 5.3, (5.15)) applied with testing bag P = S,
terminal bag Z (where F is still frozen because A* persists through
Z), and probability at least rho/2, gives
D(y_n, Z) >= b_k * (rho/2) * (t/2) = positive standard. (6.15)
But by the definition D(y_n, Z) := min_{w in Z} D(y_n, w) and z in Z,
D(y_n, Z) <= D(y_n, z) = o(1),
where we used the late-proxy identity (6.9). Contradiction. Hence
D_0 > H eventually. This proves Lemma 6.3. []
--------------------------------------------------------------------------------
6.6 THE GEOMETRIC OBSTRUCTION AT EVERY EARLY SEQUENCE
Fix a SELECTED early sequence B = (B_n). Let p be a vertex of B
nearest x_n, and put delta := d(x_n, B), which is EARLY, so has a
positive standard lower bound eps > 0 (Lemma 6.1(b)).
LEMMA 6.4 (Geometric obstruction at every early sequence). If D_0 > H,
then there is a vertex q of B satisfying
delta / 4 <= d(p, q) <= 10 D_0 (6.11)
eventually.
Proof. Suppose (6.11) fails eventually. Then there is an ultrafilter
alternative (a finite disjunction, so we may assume one branch)
(FAIL-OBSTR) every s in B is either NEAR (d(p, s) < delta/4)
or FAR (d(p, s) > 10 D_0).
(The two alternatives do not overlap: delta/4 <= 1/4 while 10 D_0 > 10.)
Step 1 (a vertex v_0 of B on a shortest A*-to-x_n path, and v_0 is
NEAR). The launch of A* is strictly above S by Lemma 6.3, and
B lies on the S-to-X bag path. By Lemma 0.1(a), every path from a
vertex of A*'s launch bag to x_n (in a bag below B on this path) meets
B. By Lemma 0.1(c) with bags A*, ..., B, ..., X, there is a vertex
v_0 in B lying on a shortest A*-to-x_n path, with
D_0 - h_*(v_0) = d(x_n, v_0). (6.12)
(Separator (0.4).) By the triangle inequality and (6.12):
d(p, v_0) <= d(p, x_n) + d(x_n, v_0)
= delta + (D_0 - h_*(v_0))
<= delta + D_0
<= 1 + D_0
< 10 D_0 (6.13)
(the last because 1 < 9 D_0, true since D_0 >= 1). In particular
v_0 is NOT FAR, so by (FAIL-OBSTR) v_0 is NEAR; hence d(p, v_0) <
delta / 4.
Step 2 (a height gap for NEAR s). Let s in B be NEAR. By Step 1
d(p, v_0) < delta/4, and by NEAR d(p, s) < delta/4. Combining:
d(s, v_0) <= d(s, p) + d(p, v_0) < delta/2.
By (6.12) and the triangle inequality in d,
h_*(x_n) - h_*(s)
= (D_0 - h_*(v_0)) + (h_*(v_0) - h_*(s))
= d(x_n, v_0) + (h_*(v_0) - h_*(s))
>= d(x_n, v_0) - d(s, v_0). (6.14)
The first term satisfies d(x_n, v_0) >= d(x_n, p) - d(p, v_0)
>= delta - delta/4 = 3 delta/4. The second is < delta/2. Hence
h_*(x_n) - h_*(s) > 3 delta/4 - delta/2 = delta/4. (6.15)
Step 3 (FAR s is unaffected by the distinguished bump). Let s in B
be FAR, i.e. d(p, s) > 10 D_0. Then
d(x_n, s) >= d(p, s) - d(p, x_n) > 10 D_0 - delta >= 9 D_0.
Since 4 eta D_0 < 4 eta H < 1 < 9 D_0 (our eta < 1/(10 H)), the
distinguished bump phi_x of A*'s ordinary noise, whose support lies in
the ball of radius 4 eta D_0 around x_n (Lemma 5.1(N2)), vanishes at s.
Step 4 (Frozen particle and simultaneous gap at x_n). Consider the
frozen "+" particle F := f_{A*} + xi_{A*} h_{A*} + v_{A*} (the reservation
of A* keeps it unchanged from B through Z). On the favorable bump
event EV (probability rho = pi/2, Lemma 5.1(N2)), for each s in B:
(Near) Vary xi_{A*} in [1,2] with everything else fixed.
F(x_n) - F(s) = [past-dependent coefficient] + xi_{A*}(h_*(x_n) -
h_*(s)). By (6.15) the coefficient of xi_{A*} is > delta/4, so
the set of xi_{A*} giving |F(x_n) - F(s)| < t has measure <=
8 t / delta on [1,2].
(Far) Vary U_x in [0,1] with everything else fixed.
F(x_n) - F(s) = [past-dependent coefficient] + U_x(phi_x(x_n) -
phi_x(s)). By Step 3 phi_x(s) = 0 and by Step 3a of Lemma 6.3
phi_x(x_n) >= c eta D_0. So the set of U_x giving
|F(x_n) - F(s)| < t has measure <= 2 t / (c eta D_0) <= 2 t / (c eta H).
Union bound over the at most k vertices of B (only one of the two
"Xi" variables is used per s; at most k terms):
Pr[ exists s in B : |F(x_n) - F(s)| < t | EV, rest ]
<= k (8 t / delta + 2 t / (c eta D_0))
<= k (8 t / eps + 2 t / (c eta H)). (6.16)
Choose a positive standard t in (0, 1/4] so that the right side of
(6.16) is < 1/2. Such t exists because k, eps, c, eta, H are positive
standard and fixed. Thus, conditional on EV, the simultaneous gap
|F(x_n) - F(s)| >= t for every s in B has probability at least 1/2,
and the joint event (EV and the gap) has probability at least
theta_B := rho / 2 > 0.
Step 5 (transfer to the late proxy and apply the height test). Let Z
be the terminal (late) bag of A* and z in Z nearest x_n. Because Z is
late, d(x_n, z) = d(x_n, Z) is infinitesimal. The frozen particle F
is Lipschitz with Lip(F) <= 3(N-1) = L_p, so on the joint event
|F(z) - F(x_n)| <= L_p d(x_n, z) = o(1),
and hence, for every s in B,
|F(z) - F(s)| >= |F(x_n) - F(s)| - |F(z) - F(x_n)|
>= t - o(1) >= t/2 (eventually).
By the HEIGHT test (Lemma 5.3, (5.15)) with testing bag P := B, terminal
bag Z, and probability at least theta_B:
D(y_n, Z) >= b_k * theta_B * (t/2) = positive standard. (6.17)
On the other hand, z in Z so D(y_n, Z) <= D(y_n, z), and by (6.9)
D(y_n, z) is infinitesimal. So D(y_n, Z) is infinitesimal, contradicting
(6.17). Therefore (6.11) holds for some q in B. []
--------------------------------------------------------------------------------
6.7 PROTECTION OF THE IMMEDIATE SUCCESSOR
--------------------------------------------------------------------------------
Lemma 6.5 (Protection of the immediate successor). Let B be any
selected early sequence of bags on the path from S to X, and let p be
a vertex of B nearest x_n. Put delta := d(x_n, B). Let A' be the
IMMEDIATE SUCCESSOR of A* in the inclusive cache list at B (the anchor
one position younger than A* in launch order). Suppose A' was
launched at or after S (that is, its launch bag sits on the segment
from S to X, not strictly above S). Then at the eviction test at B,
A' is PROTECTED by the eviction rule of section 5.2, and cannot be
evicted there.
Proof.
Step 1 (bound d(p, A')). Two alternatives.
Alternative 1 (A' is the current PROPOSAL at B). Then its launch
bag is B itself; p lies in B; so d(p, A') = 0 <= K delta trivially.
Alternative 2 (A' launched earlier, in cache at B). Its launch
bag lies on the segment S -> ... -> B, which is contained in the
bag path from Y_n to B (the path Y_n -> S -> ... -> B). So the
LAUNCH test (5.13) applies, and gives
D(y_n, p) >= b_k d(p, A'). (6.23)
From the failing-comparison upper bound D(x_n,y_n) infinitesimal
(6.5) and D(.,.) <= U d:
D(y_n, p) <= D(y_n, x_n) + U d(x_n, p)
<= D(y_n, x_n) + U delta. (6.24)
(The first inequality is the triangle inequality for D, the second
substitutes d(x_n, p) = delta since p is nearest x_n in B.)
Matching (6.23) and (6.24):
d(p, A') <= [ D(y_n, x_n) + U delta ] / b_k
= (D(y_n,x_n)/b_k) + (U/b_k) delta. (6.25)
Because D(y_n, x_n) is infinitesimal (6.5) and delta is at least the
positive standard epsilon (Lemma 6.1(b) applied to the early
sequence B), the ratio
D(y_n, x_n) / delta -> 0 along U.
Also, from (5.16) K > 2 + (2 U + 1) / b_k, we compute:
b_k * K > b_k * (2 + (2 U + 1) / b_k) = 2 b_k + 2 U + 1 > U,
so b_k K - U =: C_0 > 0 (a positive standard constant,
depending on b_k and U = 3N(N-1), hence on k only).
Together:
d(p, A') / delta <= (D(y_n,x_n)/delta)/b_k + U / b_k
<= (small) / b_k + U/b_k
< K = C_0/b_k + U/b_k + (slack) eventually.
In other words, d(p, A') <= K delta eventually, for BOTH
alternatives (0 <= K delta in Alternative 1). This is the
bound we will use below.
Step 2 (bound d(p, A*)). By triangle:
d(p, A*) >= d(x_n, A*) - d(x_n, p) = D_0 - delta. (6.26)
Step 3 (choosing q from the obstruction lemma). By Lemma 6.4 there
is a q in B with delta/4 <= L := d(p,q) <= 10 D_0. Two cases.
Case I (L <= 300). Then
J * L >= J * (delta / 4)
= (10(K+1)/4) * delta
> K delta
>= d(p, A') (by Step 1).
Also,
J * L <= 300 J (since L <= 300)
= 300 * 10(K+1)
< H - 1 (since H > 10^5 J, in particular > 300 J + 1)
< D_0 - 1 (since D_0 > H)
<= d(p, A*) (by Step 2 and delta <= 1).
So in Case I, the threshold tau := J L satisfies
d(p, A*) > tau > d(p, A').
Case II (L > 300). Then
L / 100 > 3 > 2 >= d(p, A')
(the last inequality uses d(p, A') <= 1 + delta <= 2, by
Alternative 2 with bound d(x_n, A') <= 1 -- A' is on the path
from S down, so d(x_n, A') <= d(x_n, S) = 1; or Alternative 1 with
d(p,A') = 0).
Also,
L / 100 <= (10 D_0) / 100 = D_0 / 10 < D_0 - 1 <= d(p, A*)
(using D_0 > H >> 10).
So in Case II, the threshold tau := L / 100 satisfies
d(p, A*) > tau > d(p, A').
Step 4 (applying the eviction rule). In either case, we found a
threshold tau (one of the two thresholds of the rule (5.8), with
values d(p,q)/100 and J d(p,q)) satisfying
d(p, A*) > tau > d(p, A'). (6.27)
Now, the distance sequence d(p, A_1) >= d(p, A_2) >= ... is
nonincreasing in launch order (Lemma 5.2). And A' is the IMMEDIATE
SUCCESSOR of A*: i.e., A* = A_j and A' = A_{j+1} for some index j.
But (6.27) says: d(p, A_j) > tau > d(p, A_{j+1}). That is
precisely a "drop from >tau to <tau" happening AT THE JUMP FROM
INDEX j TO INDEX j+1. By the rule of section 5.2, the entry
immediately following the drop (that is, entry j+1 = A') is PROTECTED
by threshold tau.
Thus A' is not eligible for eviction at B. []
Notice that the choice of q was in B, so L = d(p,q) is a metric
quantity about B, not a launch-noise quantity. This is essential:
the eviction rule is deterministic from the metric and the cache state,
so it cannot be influenced by the noise. So "A' is protected at B"
is a deterministic statement (for a given realization of the whole
schedule up to B), and it holds in EVERY realization.
--------------------------------------------------------------------------------
6.8 A YOUNGER CROSSING ANCHOR EXISTS
--------------------------------------------------------------------------------
We now show that, under the normalized failing-comparison assumptions
of section 6.1-6.4, the existence of A* (as the YOUNGEST crossing
anchor) is self-contradictory.
Lemma 6.6 (A younger crossing anchor exists). Under the normalized
failing-comparison hypotheses (6.4)-(6.7), there is a CROSSING anchor
strictly YOUNGER than A*.
Proof.
Focus on the INSERTION TEST AT S (that is, the insertion performed
when we arrive at bag S). By Lemma 6.3, A* was launched strictly
above S. So at the insertion at S, the cache has some number of
entries; A* is present (present at S); the newly proposed anchor at S
is retained if there is space, and evicts some non-root anchor
otherwise (the rule of 5.2). Either way, A* is unchanged at S (it is
frozen permanently from some point above S onward; it persists at S).
Consider the finite set
LIST := { anchors in the cache at S :
launched strictly above S, and launched strictly
AFTER A* }.
By Lemma 6.2, LIST has size at most n_0 + 1 (bounded by cache size).
And it is a finite set of "anchor sequences" (equivalence classes
modulo U). Take them one at a time, in launch order.
For each anchor C in LIST:
(Effect start) Launch was strictly above S, so at S, C has been
present since S began; effective start of C's reservation (as
restricted to the path S -> X) is S. S is early (delta at S = 1).
(If C survives past X, contradiction) Suppose some C in LIST had
terminal bag strictly below or at some LATE time. Then C would be
crossing (effective start early, terminal late), and C is younger
than A* (launched strictly after A*). This contradicts "A* is the
youngest crossing anchor". So every C in LIST has terminal bag
that is EARLY.
(Terminal is an actual eviction time) The terminal bag of C
cannot be X itself. If it were, then C would still be present at
the LATE bag X, so C would be a crossing anchor younger than A*,
contradicting the choice of A*. Therefore the terminal bag of C
is an ACTUAL eviction bag; and by the previous paragraph it is an
EARLY bag.
Let B_0 := the LATEST of these early eviction times in LIST. If
LIST is nonempty, B_0 is early (Lemma 6.1(b): a finite max of early
times is early). If LIST is empty, set B_0 := S (which is early).
Case (A): LIST nonempty. At B_0, some C in LIST is evicted (at
least one; at most one per insertion). Therefore the insertion at
B_0 corresponds to replacing C by a proposed anchor at B_0. After
this insertion, A* is still present (A* has terminal time late). And
no entry whose launch is strictly above S and strictly after A*
remains in the cache: all other entries of LIST were evicted earlier
(contradicting "latest"); and no new such entry launches after B_0
(launches after B_0 are at B_0 itself or below, which is at or below
S; such launches count as "at or BELOW S", not "strictly above S").
Therefore, immediately AFTER the insertion at B_0, the entry
immediately following A* is a newly retained proposal from B_0. Let
A' denote this proposal.
Case (B): LIST empty. At the insertion at S, no entry is present in
the cache whose launch is strictly above S and strictly after A*.
Since A* itself IS present (it persists from above S down to a late
terminal bag), no entry lies between A* and the proposal at S in
launch order. Hence the proposal at S is the IMMEDIATE SUCCESSOR of
A* in the inclusive cache list at S.
Let this proposal be called A'. A' is RETAINED at S. Indeed, if
the cache had space, retention is automatic. If the insertion at
S filled the cache to capacity, then by Lemma 6.5 applied with
B := S (an early bag, delta at S = 1) and with the immediate
successor A' launched at S (so "at or after S"), the eviction rule
protects A' and A' cannot be evicted.
In BOTH cases: A' is the immediate successor of A* at some early time
B_0 (which is S in Case B, or a strictly positive-time fresh launch
in Case A). A' launched at or AFTER S (since B_0 is at or below S).
Now: A' has a terminal bag. If the terminal bag is LATE, then A' is
a younger crossing anchor, and we are done.
Otherwise, A' is evicted at some EARLY time B_1. We claim this is
impossible.
Claim: At B_1, A' is still the immediate successor of A*. Reason:
Between B_0 (when A' became the immediate successor of A*) and
B_1, the only cache operations are insertions/evictions at bags in
between. Any new insertion is a younger proposal (later launch
than A'), which inserts to the right of A' in the launch order.
Any eviction removes some entry; if it removes A*, then A* would
have been evicted, contradicting A*'s LATE terminal time (A* is
still in cache at B_1). If it removes some entry between A* and
A', that entry would have to exist between A* and A' at some
intermediate time, contradicting A' being the IMMEDIATE successor
immediately after B_0. So A' remains the immediate successor
throughout the interval [B_0, B_1]. In particular, at B_1, A' is
the immediate successor of A*.
Since B_1 is early and A' launched at or after S and is the
immediate successor of A* at B_1, Lemma 6.5 applies: at the
eviction test at B_1, A' is protected and cannot be evicted. This
contradicts "A' is evicted at B_1".
Therefore, A' terminal bag must be LATE, and we get a younger
crossing anchor. []
Remark. The proof selects only a BOUNDED list (size <= n_0 + 1), its
latest eviction time, and one successor's terminal time. It does not
use induction over an unbounded or limiting order of early times.
Everything is finite and "eventual" (in the sense of the nonprincipal
ultrafilter).
--------------------------------------------------------------------------------
6.9 THE UNIFORM LOWER COMPARISON
--------------------------------------------------------------------------------
Proposition 6.9 (Uniform lower comparison). For each fixed k >= 2
there is a constant lambda_k > 0 such that, for every admissible
weighted graph with a tree decomposition of bag size at most k, and
every pair of vertices u, v,
D_bag(u,v) + D_anc(u,v) >= lambda_k * d(u,v). (6.28)
Proof.
Suppose, towards a contradiction, that no such constant exists.
Choose pairs (x_i, y_i) and examples for i = 1, 2, 3, ... with
( D_bag(x_i,y_i) + D_anc(x_i,y_i) ) / d(x_i, y_i) < 1/i
and x_i != y_i in the i-th example.
This is a FAILING COMPARISON SEQUENCE (6.1) with r_n := d(x_n,y_n)
and ratio -> 0. Normalize along the nonprincipal ultrafilter as in
sections 6.1-6.4. Obtain x, y, S and a bag path S -> X, x_n -> normal
units with d(x,S) = 1. Let delta_the_path := d(x_n, B_t) along this
path, so delta at S is 1 and delta is nonincreasing along the path.
By Lemma 6.2 there is a YOUNGEST crossing anchor A*; by Lemma 6.3
A* is "old and distant" (launched strictly above S, and D_0 > H).
By Lemma 6.6 there is a YOUNGER crossing anchor. This contradicts
"youngest".
Hence no failing sequence exists. That is, the ratios
( D_bag(x,y) + D_anc(x,y) ) / d(x,y) are uniformly bounded below by
some positive constant over all admissible examples and all distinct
pairs x != y.
Define
lambda_k := the infimum of those ratios
over all admissible examples and all distinct pairs.
By the above, lambda_k > 0. It depends only on k (everything in the
construction is k-only). For pairs u = v, both sides of (6.28) are 0;
the inequality holds with equality. For one-vertex graphs, both
metrics are zero. []
================================================================================
PART 7. ASSEMBLING THE EMBEDDING AND PROVING THE MAIN THEOREM
================================================================================
We have now built:
* D_bag from Part 4: upper bound (4.3) with constant U_bag,
lower bound (4.4) with constant a_bag on
co-bag pairs;
* D_anc from Part 5 (with the fixed parameters of 5.6):
upper bound (5.12) with constant U.
* Proposition 6.9: lambda_k > 0 with D_bag + D_anc >= lambda_k d
for all pairs u,v.
Both U_bag = 3 N_bag (N_bag - 1) and U = 3 N_anc (N_anc - 1) are
FINITE, and both depend on k only. Both D_bag and D_anc are cut
pseudometrics (each is a positive linear combination of symmetric
sweeps, Markov-glued and averaged). So their sum is a cut
pseudometric too.
Let
D(u,v) := D_bag(u,v) + D_anc(u,v). (7.1)
Then, for all u,v in V:
UPPER: D(u,v) <= (U_bag + U) * d(u,v); (7.2)
LOWER: D(u,v) >= lambda_k * d(u,v). (7.3)
Both constants U_bag + U and lambda_k are finite and positive and
depend on k only. Set
C_k := (U_bag + U) / lambda_k. (7.4)
Then C_k >= 1, depends on k only, and for every u,v:
d(u,v) <= D(u,v) / lambda_k <= C_k d(u,v). (7.5)
Proof of Theorem (the main theorem of Part 0 / Section 0.1).
Cut representation. Both D_bag and D_anc are averages over
finite consistent bag families, and each finite bag family gives a
finite labeled cut measure rho_mu on Omega_V (Lemma 1.1). So
D_bag(u,v) = sum_{A subseteq V} w^bag_A * delta_A(u,v),
D_anc(u,v) = sum_{A subseteq V} w^anc_A * delta_A(u,v),
with weights w^bag_A >= 0 and w^anc_A >= 0 summing to finite totals
m_bag and m_anc. Adding,
D(u,v) = sum_{A subseteq V} w_A * delta_A(u,v),
with w_A := w^bag_A + w^anc_A >= 0. (7.6)
L1 realization. Define the map F : V -> R^{2^{|V|}} by
F(v) := ( sqrt(w_A / lambda_k) * 1_A(v) )_{A subseteq V}. (7.7)
Then, for every u,v in V,
||F(u) - F(v)||_1
= sum_A (w_A / lambda_k) * |1_A(u) - 1_A(v)|
= D(u,v) / lambda_k.
And D(u,v)/lambda_k is between d(u,v) and C_k d(u,v) (7.5).
So F is a map into a real L1 space (dimension 2^{|V|}, finite)
that realizes the embedding of Theorem 0.1 with distortion at most
C_k.
Constants. Every constant in F, D, and C_k is a function of k
alone:
- the bag-measure mass m_bag and m_anc: functions of N, M,
Delta, i.e. of k and the metric; the RESULT after normalization
by lambda_k is a metric whose bounds depend on k only;
- U_bag, U: functions of k only;
- lambda_k: a positive function of k only (Prop 6.9);
- C_k = (U_bag + U)/lambda_k.
Therefore C_k depends on k only. It does not depend on |V|, T, or
the edge lengths. This proves Theorem 0.1.
Edge cases:
* |V| = 1: the trivial map to a point, C_k = 1, works.
* u = v: both sides of (0.1) are 0.
* disconnected graph: not permitted (this is a graph metric of a
connected graph).
* nonempty bags in the tree decomposition: WLOG by Part 0 (S1).
[]
That completes the proof of the main theorem.
================================================================================
CONCLUDING REMARKS
================================================================================
We can summarize what the proof actually used. For each fixed
treewidth bound k-1:
* BAG MEASURES + MARKOV GLUING turn compatible local data into one
global measure of cuts (Part 1). The gluing is a canonical
construction (Lemma 1.1).
* The TRANSPORT INEQUALITY (Prop 2.2) is the bridge from a local
submeasure appearing everywhere to a global separation between the
two ENDPOINTS of the bag path. It uses the external CKR
symmetric Markov-flow bound once (Theorem 2.1).
* PARTICLES + RESERVATIONS (Part 3) let us carry cut measures along
bag paths without inflating the particles' Lipschitz constants:
the invariant Q_r = r(N-r) makes the bound uniform in the number
of updates. This is where "you can preserve infinitely many local
laws" comes from.
* Two cut pseudometrics (Parts 4, 5) are constructed: D_bag, using
active scales and padded partitions; D_anc, using an anchor cache.
The anchor cache is a bounded-memory schedule with a
deterministic eviction rule.
* A COMPACTNESS + ULTRAPILTER argument (Part 6) reduces "no uniform
lower bound" to a descending sequence that looks locally like
"youngest crossing anchor A*". The launch noise at A* forces,
on every early testing bag B, a vertex q at distance
delta/4 <= d(p,q) <= 10 D_0 from the nearest point p to x, which
PROTECTS the immediate successor of A* through the eviction rule.
A separate "younger crossing anchor exists" step then contradicts
A* being the youngest. So D_bag + D_anc separates every pair
(Prop 6.9).
* The L1 embedding then follows purely algebraically, because every
cut pseudometric is the L1 distance of an embedding into R^{2^{|V|}}
(Part 0).
The bound C_k is existence-only: we do not try to estimate it as an
explicit function of k. Obtaining explicit estimates would require
sharp constants in the CKR symmetric flow bound and in the padded
partitions, which we have not attempted.
The result is also a positive resolution of the bounded-treewidth
case of the Gupta-Newman-Rabinovich-Sinclair conjecture, which
predicted uniform L1 embeddings for every proper minor-closed graph
family. Bounded treewidth = excluding a fixed planar graph (by the
excluded-planar-minor theorem), so the present result gives a uniform
bound for one (large) family of proper minor-closed families, namely
those defined by excluding a single planar graph.
================================================================================
END OF PROOF
================================================================================