Extending Lipschitz functions via random metric partitions

James R. Lee^{∗} U.C. Berkeley

              jrl@cs.berkeley.edu

Assaf Naor Microsoft Research

                                      anaor@microsoft.com

1 Introduction

Many classical problems in geometry and analysis involve the gluing together of local information to produce a coherent global picture. Inevitably, the difficulty of such a procedure lies at the local boundary, where overlapping views of the same locality must somehow be merged. It is therefore desirable that the boundaries be “smooth,” allowing a graceful transition from one viewpoint to the next. For instance, one may point to Whitney’s use of partitions of unity in studying what is now known as the Whitney extension problem [36, 37].

In the present work, we consider what is perhaps the most basic Whitney-type extension problem, that of extending a Lipschitz function so that it remains Lipschitz. Often such a map is extended by first producing a cover of the new domain, extending the mapping locally, and then gluing together the individual pieces. Our main observation is that in many cases, if one chooses a random cover from the right distribution, the boundary can be made “smooth” on average, even when the local maps are individually quite coarse. This insight leads to the unification, generalization, and improvement of many known results, as well as to new results for many interesting spaces.

1.1 The Lipschitz extension problem

Let (Y, d_{Y}), (Z, d_{Z}) be metric spaces, and for every X ⊆ Y, denote by e(X, Y, Z) the infimum over all constants K such that every Lipschitz function f : X → Z can be extended to a function f̃: Y → Z satisfying ∥f̃∥_{Lip} ≤ K∥f∥_{Lip}. (If no such K exists, we set e(X, Y, Z) = ∞). We also define e(Y, Z) = sup{e(X, Y, Z) : X ⊆ Y } and for every integer n, e_{n}(Y, Z) = sup{e(X, Y, Z) : X ⊆ Y, |X| ≤ n}.

Estimating e(Y, Z) is a classical and fundamental problem that has attracted a lot of attention due to its intrinsic interest and applications to geometry and approximation theory. It is a classical fact that for every metric space Y, e(Y, ℓ_{∞}) = 1, and Kirszbraun’s famous extension theorem [19] states that whenever H_{1} and H_{2} are Hilbert spaces, e(H_{1}, H_{2}) = 1. We refer to the books [3, 35] for a detailed account of the case e(Y, Z) = 1.

Typically, proofs of the fact that e(Y, Z) = 1 involve showing that it is possible to extend an arbitrary Lipschitz function to an additional point while preserving the Lipschitz constant. Once this is achieved, the existence of the required extension follows from Zorn’s lemma. When e(Y, Z) > 1, this “one point at a time” argument cannot work, since the Lipschitz constant will deteriorate with each iteration. Hence, in proving “non-isometric” extension results, one must argue that it is possible to extend Lipschitz functions to arbitrarily many points at once, and it is therefore not surprising that such results are more recent.

∗Work partially supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship. The majority of this work was completed while the author was an intern at Microsoft Research, Redmond, WA.

The following theorem was proved by Marcus and Pisier in [27], via a probabilistic argument.

Theorem 1.1 (Marcus-Pisier [27]). For every 1 < p < 2 there exists a constant C(p) such that for every integer n,

e_{n}(L_{p}, L_{2}) ≤ C(p) (log n)^{1/p−1/2}.

The Marcus-Pisier theorem initiated the study of the parameter e_{n}(·, ·), and using a different probabilistic argument, Johnson and Lindenstrauss [17] subsequently proved the following theorem.

Theorem 1.2 (Johnson-Lindenstrauss [17]). For every metric space Y and every integer n,

e_{n}(Y, L_{2}) ≤ 2\sqrt{log n}.

In [17], it was also shown that Theorem 1.1 and Theorem 1.2 are almost optimal, in the

sense that, for every 1 ≤ p < 2, e_{n}(L_{p}, L_{2}) ≥ C(p) (\frac{log n}{log log n})^{1/p−1/2}.

In [18] Johnson, Lindenstrauss and Schechtman studied the case when the target space is an arbitrary Banach space, proving the following two theorems.

Theorem 1.3 (Johnson-Lindenstrauss-Schechtman [18]). There exists a universal constant C such that for every metric space Y, every Banach space Z and every integer n,

e_{n}(Y, Z) ≤ C log n.

Theorem 1.4 (Johnson-Lindenstrauss-Schechtman [18]). There exists a universal constant C such that for every d-dimensional normed space Y and every Banach space Z, e(Y, Z) ≤ Cd.

Additionally, Matoušek has shown in [28] that

Theorem 1.5 (Matoušek [28]). There exists a universal constant C such that for every metric tree T and every Banach space Z, e(T, Z) ≤ C.

In the important paper [1] (which introduced, among other things, the notion of Markov type), K. Ball has shown that for every 1 < p < 2, e(L_{2}, L_{p}) ≤ \frac{6}{\sqrt{p−1}}. More recently Tsar′kov [34] proved that for every 2 < p < ∞, e(L_{p}, L_{2}) ≤ C(p) < ∞ and the second named author proved in [30] that in the same range of p, e(L_{2}, L_{p}) = ∞. A quantitative version of the last result is discussed in the next section.

The extension problem when the target space Z isn’t linear (e.g. Hadamard manifolds) has also received a lot of attention. We deal with this problem in Section 1.3 below.

1.2 Absolute Lipschitz extendability

We return to these old problems with the new perspective made possible by recent advances in combinatorics and theoretical computer science. Often in theoretical computer science, one needs to analyze data with an inherent metric structure (e.g. graphs). A technique developed over the past decade to handle such problems can be referred to as the method of stochastic metric decomposition. The basic idea is that given a metric space X, one constructs a distribution over partitions of X with certain desirable properties. For example, one often requires that each set in the partition has small diameter and yet, in expectation, that every point is “far from the boundary” of the partition. Variants of this approach have appeared in numerous contexts; see for instance [26, 20, 2].

We offer a new approach to extension problems by showing that one can pass from a stochastic decomposition to a “well-behaved” partition of unity which, in turn, can be used to extend Lipschitz functions in such a way that we have control on the growth of the Lipschitz constant. This allows us to obtain simple proofs of many of the extension theorems stated above, and more importantly, to obtain new extension theorems which, in some cases, are significant generalizations of the above results.

Additionally, we observe a new phenomenon underlying some of the previous results which we refer to as absolute extendability—the notion that for some spaces X, Lipschitz functions f from X into any Banach space Z can be extended to any containing space Y ⊇ X, where the loss in the Lipschitz constant is independent of Y, Z, and f, and thus depends only on X. To this end, let us define, for a metric space X, the absolute extendability constant ae(X) by

ae(X) = sup{e(X, Y, Z) : Y ⊇ X, Z a Banach space}.

If ae(X) < ∞, we say that X is absolutely extendable. Additionally, for a family of metric spaces M, let us define ae(M) = sup_{X∈M} ae(X) to be a uniform bound on the extendability of metrics in M. As far as we are aware, the only previously known families of absolutely extendable metrics had such a property for a “trivial” reason; these are the cases when X is an absolute Lipschitz retract or when the family M consists of finite metrics of uniformly bounded cardinality (it is not to difficult to see that Theorem 1.3 is true when log n is replaced by n). We now turn to our results, some of which have been announced in [24].

Recall that the doubling constant (see, e.g. [15]) of a metric space X, denoted λ(X), is the infimum over all numbers λ such that every ball in X can be covered by λ balls of half the radius. When λ(X) < ∞, one says that X is doubling. Applying our approach to the stochastic decomposition of [14] yields the following result.

Theorem 1.6. There exists a universal constant C > 0 such that

ae(X) ≤ C log λ(X).

Since log λ(X) = O(log n) for any n-point metric space X, and log λ(X) = O(d) whenever X is a subset of some d-dimensional normed space, Theorem 1.6 unifies and generalizes Theorems 1.3 and 1.4. Moreover, it is interesting to note that, unlike Theorem 1.4, Theorem 1.6 only assumes a bound on the dimension of some normed space containing X, while Y is allowed to be arbitrary. The proof of Theorem 1.4 in [18] cannot be used to obtain such a result, since their proof uses nets in the complement of X. Techniques used in the proof of the above theorem also allow one to extend Lipschitz functions to neighborhoods of subsets of manifolds of negative curvature using an estimate of Bishop (see Corollary 3.13 in Section 3.2).

Our next theorem provides a significant generalization of Theorem 1.5. Let G = (V, E) be a countable graph with edge weights in [0, ∞]. Denote by Σ(G) the one-dimensional simplicial complex that arises from G by replacing every edge e of G by an interval whose length is equal to that of e. Note that Σ(G) has a natural Riemannian metric structure and that the shortest path metric on G occurs as a submetric. For a family of metric spaces M, define \overline{M} = \{(X, d) : X ⊆ Y for some (Y, d) ∈ M\}, i.e. the closure of M under taking submetrics.

We now define the set of metrics supported on G by

⟨G⟩ = \overline{⋃_{all weights} Σ(G)}

where the union is taken over all possible weights on edges of G. Finally, for a family of graphs F, let ⟨F⟩ = ⋃_{G∈F}⟨G⟩. Given such a family of graphs F, one can ask when there exists a constant K_{F} such that, ae(⟨F⟩) ≤ K_{F}. For instance, note that if F is the family of graphtheoretic trees, then ⟨F⟩ is precisely the class of metrics which are a submetric of a separable metric tree, and such a result would strengthen Theorem 1.5 in the separable case. We will see momentarily that such a result does follow and thus implies that a Lipschitz function on any subset of a separable metric tree can be extended to any superspace with a universally bounded loss in the Lipschitz constant, while Matoušek’s proof relies heavily on the fact that the superspace is a tree.

To state the next result, we need to recall the definition of a graph minor. Namely, consider the following two operations on a graph G = (V, E).

1. Removal of an edge e ∈ E, i.e. moving to the graph G′ = (V, E \ {e}).

2. Contraction of an edge {u, v} ∈ E, yielding the graph G′ = (V′, E′), where V′ = V \ {u, v} ∪ {v^{∗}} and {s, t} ∈ E′ precisely when either (i) {s, t} ∈ E for v^{∗} ∉ {s, t} or when (ii) s = v^{∗}, t ≠ v^{∗}, and either {u, t} ∈ E or {v, t} ∈ E.

When a graph G′ is obtainable from G by a finite sequence of such operations, G′ is called a minor of G. If a family of graphs F has the property that G′ ∈ F whenever G ∈ F and G′ is a minor of G, we say that F is minor-closed. Finally, we say that a graph G excludes K_{r} if it does not contain the complete graph on r vertices as a minor. Using the decomposition of [20], along with its stochastic formulation in [31] and a quantitative improvement due to [10] yields

Theorem 1.7. If a graph G excludes K_{r}, then ae(⟨G⟩) ≤ C r^{2} for some universal constant C.

In particular, it is not difficult to see that trees are precisely the class of graphs which exclude K_{3} as a minor. But the above result provides an even more significant extension to Theorem 1.5 by showing, for instance, that the family of planar metrics is absolutely extendable (it is well-known that every planar graph excludes K_{5} as a minor).

To see a striking consequence of this result, which is proved in Section 5 in conjunction with a deep theorem of Robertson and Seymour [32], let us restrict ourselves (for the moment) to families of finite graphs and ask the question, for such a family, when is it that ae(⟨F⟩) ≤ K_{F} and when do we have ae(⟨F⟩) = ∞? Clearly if ⟨F⟩ contains all finite metrics, then ae(⟨F⟩) = ∞ (see, for instance, the remark after the statement of Theorem 1.2, which shows that there is no uniform bound for finite subsets of L_{1}). It happens that this is the only case.

Corollary 1.8. For a family of finite graphs F, ae(⟨F⟩) < ∞ if and only if ⟨F⟩ does not contain all finite metrics.

The techniques used in proving Theorem 1.7 also yield the following result.

Corollary 1.9. If M is a two-dimensional Riemannian manifold of genus g, then for every subset X ⊆ M, we have ae(X) ≤ C · (g + 1) for some universal constant C.

We note here that since any n-point metric space is isometrically embeddable in a twodimensional Riemannian manifold of genus O(n^{3}), in Corollary 1.9, ae(M) must tend to infinity with the genus of M.

Using our approach, together with the stochastic decomposition of [6] and the improved analysis of [8, 9] (which we generalize to arbitrary measurable metric spaces in Theorem 3.17), it is possible to obtain an asymptotic improvement over Theorem 1.3.

Theorem 1.10. There exists a universal constant C such that for every n-point metric space X,

ae(X) ≤ C \frac{log n}{log log n}.

Our techniques, in conjunction with the decomposition of [7], also give a different kind of improvement to Theorem 1.4 (of a geometric flavor).

Theorem 1.11. For any Banach space Z, e(ℓ_{2}^{d}, Z) ≤ C\sqrt{d}.

It follows that for any normed space Y, we have e(Y, Z) ≤ C\sqrt{d} · dist(Y, ℓ_{2}^{d}), where dist is the Banach-Mazur distance. In particular, when Y is a d-dimensional normed space, John’s theorem [16] implies that e(Y, Z) ≤ C · d. When Y is closer to a Hilbert space, improved bounds are achieved.

Finally, in the case when Y is an L_{p} space and 1 < p ≤ 2, we obtain the following estimate for finite subsets.

Theorem 1.12. For every 1 < p ≤ 2 there exits a constant C(p) such that for every integer n and every Banach space Z,

e_{n}(L_{p}, Z) ≤ C(p) (log n)^{1/p}.

The case p = 2 in Theorem 1.12 may be viewed as a “dual” to Theorem 1.2.

It has been asked in [18] whether e_{n}(L_{2}, Z) is bounded for every Banach space Z. Since in [30] it was shown by the second named author that for 2 < p < ∞, e(L_{2}, L_{p}) = ∞, it follows that the answer to this question is negative (this fact was overlooked in [30]). Since e_{n}(L_{2}, L_{2}) = e_{n}(L_{2}, L_{∞}) = 1, it is of interest to give quantitative lower bounds on e_{n}(L_{2}, L_{p}) for 2 < p < ∞. We therefore analyze the proof in [30] and obtain the following lower bound.

Lemma 1.13. For every integer n and every 2 < p < ∞,

e_{n}(L_{2}, L_{p}) ≥ C (\frac{log n}{log log n})^{\frac{p−2}{p^{2}}} ,

where C is a universal constant.

1.3 Lipschitz functions which take values in a barycentric metric space

In recent years there has been considerable effort to obtain extension theorems for Lipschitz functions which take values in spaces which are not Banach spaces. A generalization of Kirszbraun’s extension theorem to metric spaces with certain curvature bounds was proved by Lang and Schroeder in [26]. The problem of estimating e(X, Y, Z) when Z is the hyperbolic space ℍ^{n} arose in the context of geometric group theory. This problem was posed by Gromov in [11] and has been subsequently studied by Lang, Pavlović and Schroeder in [23]. We refer to [5, 23, 26] and the references therein for a selection of related results.

Since our approach to the extension problem is based on a random construction and an averaging argument, it is most natural to present it in the context of Banach spaces (as in this case taking expectation has a concrete meaning). However, our methods generalize to a wider class of target spaces which encompasses, for example, the spaces considered by Lang, Pavlović and Schroeder in [23]. The basic idea is that instead of taking expectations, we need to require that every compactly supported measure on the target space Z has a barycenter, and that the map which assigns to each measure its barycenter is Lipschitz continuous. A similar notion was introduced by Gromov in [13] (see also [33]). It will be instructive to begin by presenting the definition of Gromov codiffusion spaces from [13, 33]. For a metric space Z let M_{Z} be the set of all regular Borel probability measures on X, topologized with the total variation norm ∥ · ∥_{T V}. A random walk, or a diffusion, on Z is a continuous map μ : Z → M_{Z}. A codiffusion on Z is a continuous map c : M → Z defined on a convex subset M ⊆ M_{Z} containing all the Dirac measures δ_{z} such that c(δ_{z}) = z for every z ∈ Z and such that c^{−1}(z) is convex for every z ∈ Z. The notion of a codiffusion is close to what we need, except that in the context of the Lipschitz extension problem it is natural to require that c is not only continuous, but also satisfies a certain Lipschitz condition, described in the following definition.

Definition 1.14 (Barycentric metric space). For a metric space Z let M_{Z}^{bounded} be the set of all regular Borel probability measures on Z with bounded support. We shall say that Z is barycentric if there exists a constant β > 0 and a map c : M_{Z}^{bounded} → Z such that c(δ_{z}) = z for every z ∈ Z and for every μ, ν ∈ M_{Z}^{bounded},

d_{Z}(c(μ), c(ν)) ≤ β · diam(supp(μ + ν)) · ∥μ − ν∥_{T V} .  (1)

The least constant β for which there exists such a mapping c is denoted β(Z). When β(Z) ≤ β we say that Z is β-barycentric.

If Z is a Banach space then β(Z) = 1. Indeed, for μ ∈ M_{Z}^{bounded} we define c(μ) to be the usual “center of mass” ∫_{Z} xdμ(x). Barycentric metric spaces need not, however, be linear. Examples of barycentric spaces are Hadamard spaces, i.e. complete geodesic metric spaces satisfying the CAT(0) comparison inequality of Alexandrov-Toponogov (see [23]). This class of spaces includes Hadamard manifolds, i.e. complete, simply connected Riemannian manifolds of nonpositive sectional curvature and is closed under taking products and gluing along closed convex subsets. If Z is a Hadamard space and μ ∈ M_{Z}^{bounded} then c(μ) is defined as the unique minimizer of the function z ↦ ∫_{Z} d(y, z)^{2}dμ(y). The existence and uniqueness of c(μ), as well as the fact that this map satisfies the barycentric condition (1) with β = 1 are proved in Section 4 of [23].

Most of the results presented above (namely Theorem 1.6, Theorem 1.7, Corollary 1.8, Corollary 1.9, Theorem 1.11 and Theorem 1.12) transfer to the case when the target space Z is allowed to be any complete barycentric metric space, the only difference being that when Z is β-barycentric, the estimates for the Lipschitz constant of the extended function are multiplied by β. Our proof of Theorem 1.10 does not seem to admit such a generalization—this issue is briefly discussed in Appendix 6. We present our results first for the case of linear Z, and in Appendix 6 we explain the simple modifications required to transfer them to arbitrary barycentric target spaces.

1.4 Some open problems

We end this introduction by recalling some related problems which remain open. In [1], K. Ball asked whether e(L_{2}, L_{1}) is finite or infinite. Similarly, it is not known whether for 2 < p < ∞ and 1 < q < 2, e(L_{p}, L_{q}) < ∞. The second problem will be answered affirmatively if Ball’s Markov type 2 problem [1] is resolved positively. Finally, it is not known whether, for every metric space X and every normed space Z, e_{n}(X, Z) = O (\sqrt{log n}). All known lower bounds fail to beat the “\sqrt{log n} barrier.”

The flexibility of our approach suggests that it could be applied to other extension problems. For example, the extendability of large scale Lipschitz maps (studied in [22]), Hölder maps (studied in [30]) and uniformly continuous maps (studied in [4]) are all of great interest. It is also interesting to study the applicability of the random method presented in this paper to the higher order Whitney extension problem.

Acknowledgements: We are grateful to Misha Gromov for his support and many helpful suggestions. Specifically, we thank him for suggesting that we look at codiffusion spaces. We also thank Yuval Peres for several useful discussions.

2 Gentle partitions of unity

Let (Y, d) be a metric space, X a subspace of Y and (Ω, F, μ) a measure space. Given K > 0 we shall say that a function Ψ : Ω × Y → [0, ∞) is a K-gentle partition of unity with respect to X if the following conditions hold true:

1. For every x ∈ Y \ \overline{X} the function ω ↦ Ψ(ω, x) is measurable and ∫_{Ω} Ψ(ω, x)dμ(ω) = 1.

2. For every ω ∈ Ω and x ∈ \overline{X}, Ψ(ω, x) = 0.

3. There exists a Borel measurable function γ : Ω → \overline{X} such that for every x, y ∈ Y,

∫_{Ω} d(γ(ω), x) · |Ψ(ω, x) − Ψ(ω, y)| dμ(ω) ≤ Kd(x, y).

If in condition (1) above, we require that the set {ω ∈ Ω : Ψ(ω, x) > 0} is finite, we shall say the partition of unity Ψ is locally finite.

Lemma 2.1. Let (Y, d) be a metric space and X a subspace of Y. Fix K ≥ 1 and assume that Y admits a K-gentle partition of unity Ψ : Ω × Y → [0, ∞) with respect to X. Let C be a closed convex set in some Banach space Z. If Ψ is locally finite or if X is separable, then every Lipschitz function f : X → C can be extended to a function f̃: Y → C such that ||f̃||_{Lip} ≤ 3K||f||_{Lip}. Furthermore, the extension depends linearly and continuously on f.

Proof. The completeness of C implies that f can be extended to the closure of X with the same Lipschitz constant, so we may assume without loss of generality that X is closed. Let γ : Ω → T be as in condition (2) above. If Ψ is locally finite, then all integrals appearing below reduce to finite sums, and we may ignore measurability issues. Thus we now assume that C is closed and X is separable.

In what follows we refer to [3] for the basic facts on Bochner integration which we use. Since X is separable we may assume that Z is separable. In this case, Pettis’ measurability lemma implies that for every y ∈ Y the function ω ↦ f(γ(ω))Ψ(ω, y) is Bochner measurable. Moreover, for every x ∈ X,

∫_{Ω} ∥f(γ(ω))∥Ψ(ω, y) dμ(ω) ≤ ∫_{Ω} (∥f(γ(ω)) − f(x)∥ + ∥f(x)∥)Ψ(ω, y) dμ(ω)
≤ ∥f∥_{Lip} · ∫_{Ω} d(γ(ω), x) · |Ψ(ω, x) − Ψ(ω, y)| dμ(ω) + ∥f(x)∥
≤ ∥f∥_{Lip} · Kd(x, y) + ∥f(x)∥ < ∞.

Since C is closed, it follows that the Bochner integral ∫_{Ω} d(γ(ω), x)Ψ(ω, y) dμ(ω) is a welldefined element of C. We can therefore define, for x ∈ Y,

f̃(x) = \{ \begin{matrix}∫_{Ω} f(γ(ω))Ψ(ω, x) dμ(ω) & x ∈ Y \ X, \\ f(x) & x ∈ X. \end{matrix}  (2)

Clearly f̃ is an extension of f. To check the Lipschitz condition, take x ∈ Y and y ∈ Y \X. Fix z ∈ X such that d(x, z) ≤ 2 d(x, X), and observe that

f̃(y) − f̃(x) = ∫_{Ω} [f(γ(ω)) − f(z)] · [Ψ(ω, y) − Ψ(ω, x)] dμ(ω).

Indeed, this is obviously true if x, y ∈ Y \ X, while if x ∈ X then necessarily x = z, and the required identity follows from (2) and the fact that Ψ(ω, z) ≡ 0.

Now,

||f̃(x) − f̃(y)|| ≤ ∥f∥_{Lip} ∫_{Ω} d(γ(ω), z) · |Ψ(ω, x) − Ψ(ω, y)| dμ(ω)
≤ ∥f∥_{Lip} ∫_{Ω} [d(γ(ω), x) + d(x, z)] · |Ψ(ω, x) − Ψ(ω, y)| dμ(ω)
≤ 3 ∥f∥_{Lip} ∫_{Ω} d(γ(ω), x) · |Ψ(ω, x) − Ψ(ω, y)| dμ(ω) ≤ 3 K · ∥f∥_{Lip} d(x, y).

3 Stochastic metric decomposition

In this section, we introduce various notions of “well-behaved” random (pointed) partitions of a metric space and show that they exist in several important cases. Section 4 establishes that such decompositions imply the existence of gentle partitions of unity.

3.1 Well-behaved decompositions

In what follows, we use the convention that the distance from a point in a metric space to the empty set is ∞.

Definition 3.1 (Stochastic decomposition). Let (Y, d) be a metric space and X a subspace of Y. We shall say that (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) is a stochastic decomposition of Y with respect to X if I is some index set, (Ω, μ) is a probability space, for every ω ∈ Ω, {Γ^{i}(ω)}_{i∈I} is a partition of Y into Borel subsets and for every x ∈ Y the set {i ∈ I : ∃ ω ∈ Ω such that x ∈ Γ^{i}(ω)} is countable. We assume that for every i ∈ I, γ^{i} : Ω → X is a Borel measurable function such that for every ω ∈ Ω, d (γ^{i}(ω), Γ^{i}(ω)) < 2d (X, Γ^{i}(ω)). Finally, we require that for every x ∈ Y and i ∈ I the set {ω ∈ Ω : x ∈ Γ^{i}(ω)} is measurable.

If {{Γ^{i}(ω)}_{i∈I} : ω ∈ Ω} ranges over only a finite number of partitions of Y we shall say that the decomposition (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) is finitely supported.

Definition 3.2 (Bounded decomposition). Let (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) be a stochastic decomposition of Y with respect to X and Δ > 0. We say that it is Δ-bounded if for every ω ∈ Ω and i ∈ I, diam(Γ^{i}(ω)) ≤ Δ.

Definition 3.3 (Padded decomposition). Let (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) be a Δ-bounded stochastic decomposition of Y with respect to X and ε, δ > 0. We say that it is (ε, δ)-padded if for every x ∈ Y and i ∈ I the function ω ↦ d (x, Y \ Γ^{i}(ω)) is measurable and if d(x, X) ≤ εΔ then

μ (⋃_{i∈I} {ω : d (x, X \ Γ^{i}(ω)) ≥ εΔ}) ≥ δ.

Observe that the assumptions in Definition 3.1 imply that the above union is countable.

Remark 3.4. Note that when Y is countable, the requirement the function ω ↦ d (x, Y \ Γ^{i}(ω)) is measurable is redundant (i.e. it is enough to demand that {ω ∈ Ω : x ∈ Γ^{i}(ω)} is measurable). Indeed, for every ρ > 0,

{ω ∈ Ω : d (x, Y \ Γ^{i}(ω)) < ρ} = ⋃_{y∈B^{∘}(x,ρ)}{ω ∈ Ω : y ∉ Γ^{i}(ω)}.

This observation is useful since if we are interested in extending Lipschitz functions from a closed subset X of a separable space Y then it is enough to restrict our attention to the case when Y is countable. Indeed, let f : X → Z be a Banach space-valued Lipschitz function and S ⊆ X, T ⊆ Y be countable dense subsets in X and Y \ X, respectively. Clearly S is closed in S ∪ T and if we extend f|_{S} to a Lipschitz function defined on S ∪ T then we may pass to the closure and obtain the required extension without further loss in the Lipschitz constant.

Definition 3.5 (Thick decomposition). Let (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) be a Δ-bounded stochastic decomposition of Y with respect to X and ε, δ > 0. We say that it is (ε, δ)-thick if for every x ∈ Y and i ∈ I the function ω ↦ d (x, Y \ Γ^{i}(ω)) is measurable and if d(x, X) ≤ εΔ then

∫_{Ω} ∑_{i∈I} min {d (x, Y \ Γ^{i}(ω)) , Δ} dμ(ω) ≥ δΔ.

Observe that since {Γ^{i}(ω)}_{i=1}^{∞} is a partition of X, the above sum contains only one element.

Remark 3.6. Observe that if (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) is (ε, δ)-padded then it is also (ε, εδ)- thick.

Definition 3.7 (Separating decomposition). Let (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) be a Δ-bounded stochastic decomposition of Y with respect to X and ε, δ > 0. We say that it is (ε, δ)-separating if for every x, y ∈ Y such that d({x, y}, X) ≤ εΔ,

∫_{Ω} ∑_{i∈I} |1_{Γ^{i}(ω)}(x) − 1_{Γ^{i}(ω)}(y)| dμ(ω) ≤ \frac{2d(x, y)}{δΔ}.

The next lemma simply states that for a metric space (Y, d) and an arbitrary closed subspace X, an (ε, δ)-padded decomposition of X (with respect to itself) can be extended to a (roughly) (ε, δ)-padded decomposition of Y with respect to X. This will make it possible for us to place assumptions only on X, letting Y be arbitrary.

Lemma 3.8 (Partition extension). Let (Y, d) be a metric space and X a closed subspace of Y. If X admits a finitely supported (ε, δ)-padded Δ-bounded stochastic decomposition (with respect to itself), then Y admits a finitely supported (\frac{ε}{16+8ε}, δ)-padded (1+ \frac{ε}{2})Δ-bounded stochastic decomposition with respect to X.

Proof. Let (Ω, μ, {Γ^{i}(·), γ^{i}(·)}_{i∈I}) be a finitely supported (ε, δ)-padded Δ-bounded stochastic decomposition of X. For every point x ∈ Y, let t_{x} ∈ X be such that d(x, t_{x}) ≤ 2d(x, X). Now, for every ω ∈ Ω and i ∈ I, create a new set

Γ̂^{i}(ω) = Γ^{i}(ω) ⋃ \{x ∈ Y : d (t_{x}, X \ Γ^{i}(ω)) ≥ \frac{εΔ}{2} and d(x, t_{x}) ≤ \frac{εΔ}{4}\} .

Finally, for any point x ∈ Y \ ⋃_{i∈I} Γ̂^{i}(ω), place x in a singleton cluster {x}. This constitutes a finitely supported distribution over partitions of Y. The selection function corresponding to Γ̂^{i}(·) is simply chosen to be γ̂^{i} = γ^{i}, while the selection function corresponding to a singleton cluster {x} is an arbitrary point t ∈ X satisfying d(t, x) ≤ 2d(x, X) .

Let us now show that the above stochastic decomposition is (\frac{ε}{16}, δ)-padded and (1 + \frac{ε}{2})Δbounded. The (1 + \frac{ε}{2})Δ-bounded condition is easy; singleton clusters have diameter zero. For points x, y ∈ Γ̂^{i}(ω), i ∈ I, we have

d(x, y) ≤ d(x, t_{x}) + d(t_{x}, t_{y}) + d(y, t_{y}) ≤ \frac{εΔ}{4} + diam (Γ^{i}(ω)) + \frac{εΔ}{4} ≤ (1 + \frac{ε}{2}) Δ.

Fix some x ∈ Y with d(x, X) ≤ \frac{ε}{16+8ε} (1 + \frac{ε}{2}) Δ = \frac{εΔ}{16}. By the definition of padded decompositions, with probability at least δ, d (t_{x}, X \ Γ^{i}(ω)) ≥ εΔ for some i ∈ I. Our goal will be to show that in this case we have d (x, Y \ Γ̂^{i}(ω)) ≥ \frac{εΔ}{16}, which will complete the proof.

Assume to the contrary that there is some y ∈ Y \ Γ̂^{i}(ω) with d(x, y) ≤ \frac{εΔ}{16}. Observe that

d(t_{x}, t_{y}) ≤ d(t_{x}, x) + d(x, y) + d(y, t_{y}) ≤ 2d(x, X) + \frac{εΔ}{16} + 2 (d(x, X) + d(x, y)) < \frac{εΔ}{2}.

Hence,

d (t_{y}, X \ Γ^{i}(ω)) ≥ d (t_{x}, X \ Γ^{i}(ω)) − d(t_{x}, t_{y}) > \frac{εΔ}{2},

Since we also have that

d(y, t_{y}) ≤ 2d(y, X) ≤ 2d(x, X) + 2d(x, y) ≤ \frac{εΔ}{4},

we see that y ∈ Γ̂^{i}(ω), which contradicts the choice of y.

Remark 3.9. For later applications, we note that if X is \frac{εΔ}{32}-dense in Y and ε < 1, then the above proof shows that Y admits an (\frac{ε}{32}, δ)-padded 2Δ-bounded stochastic decomposition with respect to itself.

Remark 3.10. Lemma 3.8 holds true when Y is countable and the decomposition in not necessarily finitely supported (in which case the extended decomposition is not necessarily finitely supported either). The proof is the same, and all one has to observe is that in this case the resulting decomposition satisfies the required measurability assumptions.

3.2 Constructions

In this section, we construct stochastic decompositions for various classes of metric spaces. Most of the constructions come directly from the theoretical computer science literature, but since we are dealing here with infinite spaces, we must be somewhat delicate in placing these finite random processes into the appropriate probability spaces and dealing with the measurability issues that arise. Because of this, some of the constructions are restated in a form which is different than that in which they originally appeared.

Let (X, d) be a metric space and R > r > 0. Denote by C(X; R, r) the largest cardinality of a set N ⊆ X satisfying for every distinct x, y ∈ N, r ≤ d(x, y) ≤ R. The following result is essentially contained in [14], though we must deal with a technical issue due to our use of possibly infinite nets.

Lemma 3.11. For every Δ > 0, every metric space (X, d) admits an (ε, \frac{1}{2})-padded Δbounded finitely supported stochastic decomposition of X with respect to itself, where ε = \frac{1}{256 log[C(X;2Δ,Δ/4)]}.

Proof. For ease of notation, we construct a 4Δ-bounded decomposition. We may assume that C(X; 8Δ, Δ) is finite, since otherwise the result holds vacuously. Let N be a Δ-net of X. First, we need to introduce a distribution over partial orders ≺ on N such that for every ball B ⊂ X of radius 3Δ, ≺ is a uniformly random total order on B ∩ N (note that |B ∩ N| is finite). To this end, consider the infinite graph G = (N, E) where {x, y} ∈ E if and only if d(x, y) ≤ 3Δ. The degree of G is at most C(X; 6Δ, Δ) < ∞, and thus G admits a proper coloring using some finite number of color classes; call these classes 1, 2, …, M. Now let σ be a random permutation on {1, …, M} and let χ : N → {1, …, M} be a proper coloring. Finally, define x ≺ y if and only if σ(χ(x)) < σ(χ(y)). It is easy to see that for a ball B of radius 3Δ, every point in B ∩ N receives a unique color, and thus σ induces a uniformly random permutation on B. It follows that ≺ satisfies the desired properties.

Now choose a radius R ∈ [Δ, 2Δ] uniformly at random. For each y ∈ N, define a cluster

C_{y} = {x ∈ X : x ∈ B(y, R) and y ≺ z for all z ∈ N with x ∈ B(z, R)}.

Since N is a Δ-net and R ≥ Δ, P = {C_{y}}_{y∈N} constitutes a partition of X. Clearly all the clusters C_{y} have diameter at most 4Δ. Finally, we construct the required selectors as follows: for y ∈ N let γ^{y} be the minimal element of N in C_{y} (with respect to ≺).

Now fix a value t ∈ [0, Δ] and some x ∈ X. Let W = B(x, 2Δ + t) ∩ N, and note that m = |W | ≤ C(X; 6Δ, Δ). Arrange the points w_{1}, …, w_{m} ∈ W in order of increasing distance from x, and let I_{k} be the interval [d(x, w_{k}) − t, d(x, w_{k}) + t]. Let us say that B(x, t) is cut if for some cluster C_{w_{k}}, C_{w_{k}} ∩ B(x, t) ≠ ∅, but B(x, t) ⊈ C_{w_{k}}. Finally, write E_{k} for the event that w_{k} is the minimal element in W (according to ≺) for which C_{w_{k}} cuts B(x, t). Then,

Pr[B(x, t) is cut] ≤ ∑_{k=1}^{m} Pr[E_{k}]

= ∑_{k=1}^{m} Pr[R ∈ I_{k}] · Pr[E_{k} | R ∈ I_{k}]

≤ ∑_{k=1}^{m} \frac{2t}{Δ} · \frac{1}{k} ≤ \frac{2t}{Δ}(1 + log m) ≤ \frac{8t}{Δ} log [C(X; 6Δ, Δ)] .

Setting t = \frac{Δ}{64 log[C(X;6Δ,Δ)]} yields the required result. We remark that the stochastic decomposition can be made finitely supported by choosing R uniformly from a sufficiently fine mesh in [Δ, 2Δ].

Corollary 3.12 (Doubling metrics). Let (X, d) be a doubling metric space. Then for every Δ > 0, there exists a (\frac{1}{C log λ(X)}, \frac{1}{2})-padded Δ-bounded finitely supported stochastic decomposition of X with respect to itself, where C is a universal constant.

Proof. This is a direct consequence of Lemma 3.11, since it is evident that log [C(X; 2Δ, Δ/4)] = O (log λ(X)). Indeed, let N ⊆ X be a set such that, for every distinct x, y ∈ N, \frac{Δ}{4} ≤ d(x, y) ≤ 2Δ. Then clearly X is contained in a ball of radius 2Δ which can be covered by λ(X)^{4} balls of radius \frac{Δ}{8}. Since every such ball contains at most one point of N, we see that |N| ≤ λ(X)^{4}.

Corollary 3.13 (Negatively curved manifolds). Fix r > 0 and let M be an n-dimensional Riemannian manifold satisfying Ricci(g) ≥ −(n − 1)rg, where g is the Riemannian metric on M and Ricci(g) is the Ricci curvature of g. Then for any subset A ⊆ M and every Δ > 0, A admits an (ε, \frac{1}{2})-padded Δ-bounded finitely supported stochastic decomposition (with respect to itself), where ε = \frac{c}{n(1+\sqrt{rΔ})} and c is a universal constant.

Proof. Fix 0 < R_{1} < R_{2} and x ∈ M. The following inequality is a well known consequence of Bishop’s inequality (see Lemma 5.3, pg. 275 in [12]):

\begin{matrix}Vol & (B_{M}(x, R_{2})) \\ Vol & (B_{M}(x, R_{1})) \end{matrix} ≤ \frac{∫_{0}^{R_{2}} (e^{\sqrt{rt}} − e^{−\sqrt{rt}})^{n−1} dt}{∫_{0}^{R_{1}} (e^{\sqrt{rt}} − e^{−\sqrt{rt}})^{n−1} dt}.

By standard arguments it follows that:

log [C(A; 2Δ, Δ/4)] ≤ log [C(M; 2Δ, Δ/4)] ≤ O (1 + \sqrt{rΔ}) · n,

so that Lemma 3.11 implies the required result.

A strong decomposition for excluded-minor spaces follows from the (graph) decompositions of [20], and a similar notion was used in [31] to embed planar metrics into ℓ_{2}. We sketch the argument below.

Lemma 3.14 (Excluded minors). Let G be a graph which does not possess K_{r} as a minor, and suppose that X ∈ ⟨G⟩. Then for every Δ > 0, X admits a (\frac{c}{r^{2}} , \frac{1}{2})-padded Δ-bounded finitely supported stochastic decomposition with respect to itself.

Proof. Let G be a weighted graph without a K_{r} minor such that X ⊆ Σ(G). Fix some β ∈ (0, 1] and k ∈ ℕ. Consider the distribution μ on P which arises from the following random process. We decompose Σ(G) recursively. Let x_{0} be an arbitrary point of X. Choose now some u ∈ [0, βΔ) uniformly at random and consider, for each n ∈ ℕ ∪ {0}, the annuli

A_{n} = {x ∈ Σ(G) : (n − 1)βΔ + u ≤ d_{Σ(G)}(x, x_{0}) < nβΔ + u} .

In general, the sets A_{n} may be disconnected in the topology of Σ(G). Let C denote the set of (disjoint) connected components of the {A_{n}}, and apply the above random process again to each component in C. The process ends after k such steps, producing a partition P of Σ(G).

In [20], it is shown that for some fixed β = β(r) and k = r, the above process produces a partition P such that for every C ∈ P, diam(C) ≤ Δ. Improved quantitative bounds were obtained in [10], yielding β(r) = Ω (\frac{1}{r}).

For every partition P and x ∈ X let π_{P} (X) be the maximal r ≥ 0 for which there exists A ∈ P such that B_{Σ(G)}(x, r) ⊆ A. We claim that for any x ∈ Σ(G) and every t > 0,

Pr[π_{P} (x) ≥ t] ≥ (1 − \frac{2t}{βΔ})^{k}. To see this, simply note that the probability of B_{Σ(G)}(x, t) being separated into two different connected components at any step of the decomposition is at most \frac{2t}{βΔ}. Choosing t = Ω (\frac{Δ}{r^{2}} ) gives P r[π_{P} (x) ≥ t] ≥ \frac{1}{2}. This random partition can be modified to have finite support by choosing u uniformly from a sufficiently fine mesh in [0, βΔ), so that Σ(G), and hence also X, admits the required padded stochastic decomposition.

Corollary 3.15 (Surfaces of bounded genus). Let M be a two dimensional Riemannian manifold with genus g and X ⊆ M. Then for every Δ > 0, X admits a (\frac{c}{g+1}, \frac{1}{2})-padded Δ-bounded finitely supported stochastic decomposition with respect to itself.

Proof. Let N be an η-net in X. For every x, y ∈ N let ℓ_{x,y} be a minimal length geodesic joining x and y. Consider the set N′ ⊇ N obtained from adding all the points of intersection of the geodesics {ℓ_{x,y}}_{x,y∈N}. Consider the graph G = (N′, E), where {u, v} ∈ E if there is some x, y ∈ N such that u and v are connected by a sub-geodesic ℓ ⊆ ℓ_{x,y} for which ℓ ∩ N′ = {u, v}. By construction, the graph G is embedded in M (in the graph-theoretic sense). It follows (see [29]) that G excludes a K_{Ω(\sqrt{g+1})} minor. Furthermore, N is isometric to a subset of Σ(G) where the weight of an edge {u, v} is equal to the length of the sub-geodesic connecting u and v. Hence N is a K_{Ω(\sqrt{g+1})}-excluded metric, so that the required result follows from Lemma 3.14 and Remark 3.9 (for η small enough).

Optimal decompositions for finite subsets of ℓ_{2}^{d} were given in [7]. The following lemma is based on their techniques.

Lemma 3.16 (Finite dimensional Hilbert space.). For any closed subset X of ℓ_{2}^{d} and for every Δ > 0 there exists a stochastic decomposition of ℓ_{2}^{d} with respect to X which is (ε, δ)- separating and Δ-bounded for every ε > 0 and δ = \frac{1}{2\sqrt{d}}.

Proof. We construct a graph G = (ℤ^{d}, E) where for u, v ∈ ℤ^{d}, {u, v} is an edge if and only if d (u + [0, 1)^{d}, v + [0, 1)^{d}) ≤ 8Δ. As before, the degree of G is uniformly bounded, and thus it admits an M-coloring χ : ℤ^{d} → {1, 2, …, M} such that χ(u) ≠ χ(v) whenever d (u + [0, 1)^{d}, v + [0, 1)^{d}) ≤ 8Δ.

Denote by m_{d} the Lebesgue measure on [0, 1]^{d} and by ν the uniform probability measure on {1, …, M}. Consider the product space Ω = ∏_{i=1}^{∞} ([0, 1)^{d} × {1, …, M}) equipped with the natural product measure μ. Given ω = (x_{1}, c_{1}, x_{2}, c_{2}, …) ∈ Ω we construct recursively a sequence of disjoint subsets of ℝ^{d}, {Γ^{i,v}(ω) : i ∈ ℕ, v ∈ ℤ^{d}} as follows:

Γ^{k,v}(ω) = \{ \begin{matrix}B_{2} (v + x_{k}, \frac{Δ}{2}) \ (⋃_{j=1}^{k−1} ⋃_{u∈ℤ^{d}} Γ^{j,u}(ω)) & if χ(v) = c_{k} \\ ∅ & otherwise, \end{matrix}

where B_{2}(y, ρ) denotes the closed Euclidean ball of radius ρ centered at y. The sets {Γ^{i,v}(ω) : i ∈ ℕ, v ∈ ℤ^{d}} form a partition of [0, 1)^{d} with probability one. We claim that there exist measurable maps γ^{i,v} : Ω → X such that for every ω ∈ Ω, d (γ^{i,v}(ω), Γ^{i,v}(ω)) ≤ 2d (X, Γ^{i,v}(ω)).

Indeed, by a classical measurable selection theorem of Kuratowski and Ryll-Nardzewski [21] it is enough to check that for every open ball B ⊆ R^{d} the set

{ω ∈ Ω : B ∩ X ∩ {a ∈ ℝ^{d}; d (a, Γ^{i,v}(ω)) ≤ 2d (X, Γ^{i,v}(ω))} ≠ ∅}

is measurable, and this fact follows directly from the construction.

The above decomposition is trivially Δ-bounded. Now, fix x, y ∈ ℝ^{d}. Since the (ε, δ)- separating condition is trivial for d(x, y) > Δ, assume that d(x, y) ≤ Δ. We now bound the probability that x and y end up in different clusters. It follows from the construction that x and y are separated in the partition induced by ω = (x_{1}, c_{1}, x_{2}, c_{2}, …) precisely when there is an index j for which [x_{j} + χ^{−1}(c_{j})] ∩ [B_{2} (x, \frac{Δ}{2}) △ B_{2} (y, \frac{Δ}{2})] ≠ ∅ while [x_{i} + χ^{−1}(c_{i})] ∩ [B_{2} (x, \frac{Δ}{2}) ∩ B_{2} (y, \frac{Δ}{2})] = ∅ for every i < j. Notice that since d(x, y) ≤ Δ, no two cubes from \{v + [0, 1)^{d} : v ∈ ℤ^{d}\} which intersect B_{2} (x, \frac{Δ}{2}) ∪ B_{2} (y, \frac{Δ}{2}) have the same color. Denoting by K ⊆ ℝ^{n} the union of all the cubes which intersect B_{2} (x, \frac{Δ}{2}) ∪ B_{2} (y, \frac{Δ}{2}), it follows that for every Borel measurable A ⊆ K, μ ([x_{k} + χ^{−1}(c_{k})] ∩ A ≠ ∅) = \frac{Vol(A)}{Vol(K)}. Hence

∫_{Ω} ∑_{i∈I} |1_{Γ^{i}(ω)}(x)−1_{Γ^{i}(ω)}(y)| dμ(ω) = 2μ({x and y are not in the same Γ^{i}(ω)})

≤ 2 ∑_{j=1}^{n} \frac{Vol (B_{2} (x, \frac{Δ}{2}) △ B_{2} (y, \frac{Δ}{2}))}{Vol(K)} [1 − \frac{Vol (B_{2} (x, \frac{Δ}{2}) ∩ B_{2} (y, \frac{Δ}{2}))}{Vol(K)}]^{j−1}

= 2Vol (B_{2} (x, \frac{Δ}{2}) △ B_{2} (y, \frac{Δ}{2})) ; Vol (B_{2} (x, \frac{Δ}{2}) ∩ B_{2} (y, \frac{Δ}{2})) ≤ \frac{4\sqrt{d}}{Δ}∥x − y∥_{2},

by straightforward volume estimates.

Finally, we present a decomposition theorem for general metric spaces Y with respect to a compact, measurable submetric X. The analysis is based on ideas from [6] and [9] for finite metrics.

Theorem 3.17. Let (Y, d) be a metric space and X a compact subspace of Y. If σ is any non-degenerate Borel measure on X (i.e. one which assigns non-zero measure to every ball in X), then for every Δ > 0, there exists a Δ-bounded stochastic decomposition of Y with respect to X such that, for every x, y ∈ Y with d(\{x, y\}, X) < \frac{Δ}{16},

∫_{Ω} ∑_{i∈I} |1_{Γ^{i}(ω)}(x) − 1_{Γ^{i}(ω)}(y)| dμ(ω) ≤ \frac{2 d(x, y)}{Δ} [1 + log (\frac{σ(B_{X}(x, 5Δ))}{σ(B_{X}(x, Δ))})] .  (3)

Proof. Since X is compact, we may assume that σ is a probability measure on X. Let us then equip the product space Ω′ = ∏_{i=1}^{∞} X with the natural product measure μ′. Finally, let Ω = Ω′×[2Δ, 4Δ], equipped with the probability measure Pr = μ′×λ, where λ is the normalized Lebesgue measure on [2Δ, 4Δ]. Given ω = (x_{1}, x_{2}, x_{3}, …) ∈ Ω′ and some R ∈ [2Δ, 4Δ], we construct recursively a sequence of disjoint subsets of Y, {Γ^{i}(ω, R) : i ∈ ℕ} as follows,

Γ^{k}(ω, R) = B(x_{k}, R) \ ( ⋃_{j=1}^{k−1} Γ^{j}(ω)) .

Let S = \{y ∈ Y : d(x, y) < \frac{Δ}{2}\}, then with probability 1, for any R ∈ [2Δ, 4Δ], the sets \{Γ^{i}(ω, R) ∩ S\}_{i=1}^{∞} form a partition of S. To see this, let N be a \frac{Δ}{4}-net in X, and consider the balls B(x, \frac{Δ}{8}) for x ∈ N. Since σ is non-degenerate, it assigns any such ball positive measure, and hence with probability 1, we have x_{j} ∈ B(x, Δ/8) for some j ∈ ℕ. Now fix a point y ∈ Y such that d(y, X) < \frac{Δ}{2}, and let z ∈ X be such that d(y, z) < 2 d(y, X). Observe that z is within \frac{Δ}{4} of some point of N, and hence within \frac{3Δ}{8} of some x_{j} with probability 1. But now we see that d(y, x_{j}) ≤ d(y, z) + d(z, x_{j}) < Δ + \frac{3Δ}{8} < 2Δ, hence y ∈ B(x_{j}, R). It follows that the proposed sets are indeed a partition of S with probability 1.

We define the final partition by

{Γ^{i}(ω, R)}_{i=1}^{∞} ⋃ {{y} : y ∈ Y \ ⋃_{i∈ℕ}Γ^{i}(ω, R)} ,

and note that the required selectors exist due to an application of the Kuratowski, Ryll-Nardzewski Theorem as in the proof of Lemma 3.16.

Fix x ∈ Y such that d(x, X) < \frac{Δ}{2} and denote by ν the distribution of the random variable z ↦ d(z, x), i.e. for 0 ≤ α < β, ν([α, β)) = σ({z ∈ X : α ≤ d(z, x) < β}). Fix t ≤ Δ and for every R ∈ [2Δ, 4Δ] denote by D_{R} the set of all z ∈ X for which B(z, R)∩B(x, t) ∉ {∅, B(x, t)} (when this happens we say that B(x, t) is cut by B(z, R)). Finally, let

Ω_{i,R} = {ω ∈ Ω′ : ω_{i} ∈ D_{R}} \ ⋃_{j=1}^{i−1}{ω ∈ Ω′ : ω_{j} ∈ D_{R}}.

Observe that for ω = (ω_{1}, ω_{2}, …) ∈ Ω′, if ω ∈ Ω_{i,R} then the triangle inequality implies that R ∈ [d(x, ω_{i}) − t, d(x, ω_{i}) + t]. Moreover, if ω_{i} ∈ B(x, Δ) then B(x, t) ⊆ B(ω_{i}, R), since t ≤ Δ and R ≥ 2Δ, so that B(ω_{i}, R) can’t cut B(x, t). Additionally, B(ω_{i}, R) ∩ B(x, t) ≠ ∅ implies ω_{i} ∈ B(x, 5Δ), since R ≤ 4Δ. It follows that if ω ∈ Ω_{i,R}, then Δ < d(ω_{i}, x) ≤ 5Δ. Finally, if ω ∈ Ω_{i,R} then d(ω_{j}, x) > d(ω_{i}, x) for j < i, since otherwise B(ω_{i}, R) will not be the first ball to cut B(x, t). These observations imply that for every i = 1, 2, …, every R ∈ [2Δ, 4Δ] and every ρ > 0,

μ′(Ω_{i,R}|d(x, ω_{i}) = ρ) ≤ 1_{{R∈[ρ−t,ρ+t]}} · 1_{{Δ<ρ≤5Δ}}[1 − ν([0, ρ])]^{i−1}.

Hence,

Pr[B(x, t)is cut] = \frac{1}{2Δ} ∫_{2Δ}^{4Δ} (∑_{i=1}^{∞} μ′(Ω_{i,R})) dR

= \frac{1}{2Δ} ∫_{2Δ}^{4Δ} (∑_{i=1}^{∞} ∫_{0}^{∞} μ′(Ω_{i,R}|d(x, ω_{i}) = ρ)dν(ρ)) dR

≤ \frac{1}{2Δ} ∫_{2Δ}^{4Δ} (∑_{i=1}^{∞} ∫_{(Δ,5Δ]} 1_{\{R∈[ρ−t,ρ+t]\}} · [1 − ν([0, ρ])]^{i−1}dν(ρ)) dR

≤ \frac{t}{Δ} ∫_{(Δ,5Δ]} \frac{dν(ρ)}{ν([0, ρ])}
≤ \frac{t}{Δ} log (\frac{ν([0, 5Δ])}{ν([0, Δ])}) = \frac{t}{Δ} log (\frac{σ(B_{X}(x, 5Δ))}{σ(B_{X}(x, Δ))}) .  (4)

The last inequality above is a classical fact, which can be proved as follows: Approximate the integral by the sum ∑_{i=1}^{k} \frac{ν([0,ρ_{i}])−ν([0,ρ_{i−1}])}{ν([0,ρ_{i}])} for some Δ < ρ_{0} < ρ_{1} < … < ρ_{k} = 5Δ, and use

the estimate \frac{ν([0,ρ_{i}])−ν([0,ρ_{i−1}])}{ν([0,ρ_{i}])} ≤ ∫_{ν([0,ρ_{i−1}])}^{ν([0,ρ_{i}])} \frac{ds}{s}.

Observe that (3) holds trivially if d(x, y) ≥ Δ. Otherwise, choosing t = d(x, y) in (4) yields the required result.

4 Constructing gentle partitions

In this section we show that the various decompositions that were introduced in the previous section can be used to construct gentle partitions of unity.

Theorem 4.1 (Stochastic decompositions yield gentle partitions). There exists a universal constant C > 0 such that for every metric space (Y, d) and every subspace X ⊆ Y the following assertions hold true:

1. If for every n ∈ ℤ, Y admits an (ε, δ)-thick 2^{n}-bounded stochastic decomposition with respect to X, then Y also admits a \frac{C}{εδ} -gentle partition of unity with respect to X.

2. If for every n ∈ ℤ, Y admits an (ε, δ)-padded 2^{n}-bounded stochastic decomposition with respect to X, then Y also admits a \frac{C}{εδ} -gentle partition of unity with respect to X.

3. If for every n ∈ ℤ, Y admits an (ε, δ)-separating 2^{n}-bounded stochastic decomposition with respect to X, then Y also admits a C (\frac{1}{ε} + \frac{1}{δ})-gentle partition of unity with respect to X.

Proof. For every n ∈ ℤ let (Ω_{n}, μ_{n}, {Γ_{n}^{i}(·), γ_{n}^{i}(·)}_{i∈I}) be a 2^{n}-bounded stochastic decomposition of Y with respect to X. Let φ : ℝ → ℝ_{+} be any 2-Lipschitz map with supp(φ) ⊂ [\frac{1}{2}, 4] and φ ≡ 1 on [1, 2]. Define φ_{n}(x) = φ (\frac{d(x,X)}{ε2^{n−3}}) and let (Ω, μ) be the disjoint union of \{I × Ω_{n}\}_{n∈ℤ} (where the measure on I is the counting measure). In all the cases of the theorem the partition of unity which we construct will have the following form: For every n ∈ ℤ, ω ∈ Ω_{n}, i ∈ I and x ∈ Y denote:

Ψ(i, ω, x) = \frac{1}{S(x)} θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x),  (5)

where for every n ∈ ℤ and x ∈ Y the function ω ↦ θ_{ω}^{n}(x) ∈ [0, ∞) is μ_{n}-integrable and

S(x) = ∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) dμ_{n}(ω) = ∑_{n∈ℤ}φ_{n}(x) ∫_{Ω_{n}} θ_{ω}^{n}(x) dμ_{n}(ω).

Additionally define γ(i, ω) = γ_{n}^{i}(ω).

Observe that supp(φ_{n}) ⊆ {x ∈ Y : d(x, X) ∈ [ε2^{n−4}, ε2^{n−1}]}, so the sum in the denominator of (5) contains at most 5 terms, and is therefore finite. Additionally, the definition of φ_{n} ensures that for every x ∈ \overline{X} and ω ∈ Ω, Ψ(ω, x) = 0.

The functions θ_{ω}^{n}(x) will be different in each particular case, but we begin by making some general comments. Our goal is to show that for every x, y ∈ Y,

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} d(γ(i, ω), x) · |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω) ≤ \frac{C}{εδ} · d(x, y).  (6)

In cases (1) and (2) above and

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} d(γ(i, ω), x) · |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω) ≤ C (\frac{1}{ε} + \frac{1}{δ}) · d(x, y).  (7)

in case (3).

Claim 4.2. Fix ω ∈ Ω_{n} and assume that Ψ(i, ω, x) ≠ Ψ(i, ω, y). Then

d(γ(i, ω), x) ≤ d(x, y) + \frac{18}{ε} · max\{d(x, X), d(y, X)\}.

Proof. Our assumption implies that either Ψ(i, ω, x) > 0 or Ψ(i, ω, y) > 0. In the first case, x ∈ Γ_{n}^{i}(ω) and

d (γ(i, ω), x) ≤ d (γ(i, ω), Γ_{n}^{i}(ω)) + diam(Γ_{n}^{i}(ω)) ≤ 2d (X, Γ_{n}^{i}(ω)) + 2^{n} ≤ 2d(x, X) + 2^{n}.

On the other hand, φ_{n}(x) > 0, so d(x, X) ≥ ε2^{n−4}, which implies the required estimate. In the second case, Ψ(i, ω, y) > 0, so that

d(γ(i, ω), x) ≤ d(γ(i, ω), y) + d(x, y) ≤ 2d(y, X) + diam(Γ_{n}^{i}(ω)) + d(x, y)
≤ 2d(y, X) + 2^{n} + d(x, y) ≤ \frac{18}{ε} · d(y, X) + d(x, y).

By Claim 4.2 we can estimate the left-hand side of (6) and (7) as follows:

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} d(γ(i, ω), x) · |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω)

≤ d(x, y) · ∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} [Ψ(i, ω, x) + Ψ(i, ω, y)] dμ_{n}(ω)

+\frac{18}{ε} · max\{d(x, X), d(y, X)\} ∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω)

= 2d(x, y) + \frac{18}{ε} · max\{d(x, X), d(y, X)\} ∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω)

It is therefore enough to show that:

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω) ≤ \frac{C′}{δ} · \frac{d(x, y)}{max\{d(x, X), d(y, X)\}},  (8)

when the decompositions are either (ε, δ)-padded or (ε, δ)-thick and

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω) ≤ C′ (1 + \frac{ε}{δ}) · \frac{d(x, y)}{max\{d(x, X), d(y, X)\}},  (9)

when the decompositions are (ε, δ)-separating. Here C′ is a universal constant.

We may assume that C′ > 4, in which case inequality (8) (resp. inequality (9)) holds trivially when d(x, y) ≥ d({x, y}, X). Indeed, in this case d(x, X) ≤ d(x, y) + d(y, X) ≤ 2d(x, y) and analogously d(y, X) ≤ 2d(x, y). Hence the right-hand side of (8) (resp. (9)) is greater than 2 while the left-hand side of (8) (resp. (9)) is at most 2 since by construction ∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} Ψ(i, ω, z)dμ_{n}(ω) = 1 for every z ∈ Y.

Our goal is therefore to prove (8) (resp. (9)) under the assumption d(x, y) < d({x, y}, X). We may also assume without loss of generality that d(x, X) ≥ d(y, X). Now,

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω)

= ∑_{n∈ℤ}∫_{Ω_{n}} ∑_{i∈I} |\frac{θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x)S(y) − θ_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)S(x)}{S(x)S(y)}| dμ_{n}(ω)

≤ ∑_{n∈ℤ}∫_{Ω_{n}} ∑_{i∈I} \frac{|θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − θ_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)|}{S(x)} dμ_{n}(ω) +

(∑_{n∈ℤ}∫_{Ω_{n}} θ_{ω}^{n}(y)φ_{n}(y) dμ_{n}(ω)) \frac{|S(x) − S(y)|}{S(x)S(y)}

≤ ∑_{n∈ℤ}∫_{Ω_{n}} ∑_{i∈I} \frac{|θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − θ_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)|}{S(x)} dμ_{n}(ω) +

∑_{n∈ℤ}∫_{Ω_{n}} θ_{ω}^{n}(y)φ_{n}(y) dμ_{n}(ω) ∑_{k∈ℤ}∫_{Ω_{k}} ∑_{i∈I} \frac{|θ_{τ}^{n}(x)φ_{k}(x)1_{Γ_{k}^{i}(τ)}(x) − θ_{τ}^{n}(y)φ_{k}(y)1_{Γ_{k}^{i}(τ)}(y)|}{S(x)S(y)} dμ_{k}(τ)

= \frac{2}{S(x)} ∑_{n∈ℤ}∫_{Ω_{n}} ∑_{i∈I} |θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − θ_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}(ω).  (10)

We now deal with each of the particular cases in the statement of the theorem:

Case 1. The stochastic decomposition (Ω_{n}, μ_{n}, {Γ_{n}^{i}(·), γ_{n}^{i}(·)}_{i∈I}) is (ε, δ)-thick and 2^{n}-bounded for all n ∈ ℤ. In this case we take θ_{ω}^{n}(x) = π_{ω}^{n}(x), where for every ω ∈ Ω_{n} and x ∈ Y,

π_{ω}^{n}(x) = ∑_{i∈I} min {d (x, Y \ Γ_{n}^{i}(ω)) , 2^{n}} .  (11)

Observe that since {Γ_{n}^{i}(ω)}_{i∈I} is a partition of Y, the above sum consists of only one element. Let n_{0} be an integer such that \frac{d(x,X)}{ε2^{n_{0}−3}} ∈ [1, 2]. Then

S(x) ≥ ∑_{n: d(x,X)≤ε2^{n}} φ_{n}(x) ∫_{Ω_{n}} π_{ω}^{n}(x) dμ_{n}(ω)

≥ ∑_{n: d(x,X)≤ε2^{n}} δ2^{n}φ_{n}(x) ≥ δ2^{n_{0}}φ (\frac{d(x, X)}{ε2^{n_{0}−1}}) ≥ δ2^{n_{0}} ≥ \frac{δ}{ε} d(x, X).  (12)

We now estimate the numerator in (10). Fix n ∈ ℤ and ω ∈ Ω_{n}. Assume first of all that x, y ∈ Γ_{n}^{j}(ω) for some j ∈ I. Hence

∑_{i∈I} |π_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − π_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| = |π_{ω}^{n}(x)φ (\frac{d(x, X)}{ε2^{n−3}}) − π_{ω}^{n}(y)φ (\frac{d(y, X)}{ε2^{n−3}})|

≤ φ (\frac{d(x, X)}{ε2^{n−3}}) |π_{ω}^{n}(x) − π_{ω}^{n}(y)| + π_{ω}^{n}(y) |φ (\frac{d(x, X)}{ε2^{n−3}}) − φ (\frac{d(y, X)}{ε2^{n−3}})|
≤ d(x, y) + π_{ω}^{n}(y)\frac{16d(x, y)}{ε2^{n}} ≤ d(x, y) + 2^{n} · \frac{16d(x, y)}{ε2^{n}} ≤ \frac{17}{ε} d(x, y).  (13)

If, on the other hand, there are distinct i, j ∈ I such that x ∈ Γ_{n}^{i}(ω) and y ∈ Γ_{n}^{j}(ω) then clearly π_{ω}^{n}(x), π_{ω}^{n}(y) ≤ d(x, y), so:

∑_{ℓ∈I} |π_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{ℓ}(ω)}(x) − π_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{ℓ}(ω)}(y)| = π_{ω}^{n}(x)φ (\frac{d(x, X)}{ε2^{n−1}}) + π_{ω}^{n}(y)φ (\frac{d(y, X)}{ε2^{n−1}})
≤ π_{ω}^{n}(x) + π_{ω}^{n}(y) ≤ 2 d(x, y).  (14)

Plugging the estimates (12), (13), (14) into (10) we obtain

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω) ≤ \frac{2ε}{δ d(x, X)} ∑_{n: \{x,y\}∩supp(φ_{n})≠∅} ∫_{Ω_{n}} \frac{17}{ε} d(x, y)dμ_{n}

≤ \frac{340 d(x, y)}{δ d(x, X)},  (15)

where we have used the fact that for every z ∈ Y, |{n : z ∈ supp(φ_{n})}| ≤ 5.

Case 2. The stochastic decomposition (Ω_{n}, μ_{n}, {Γ_{n}^{i}(·), γ_{n}^{i}(·)}_{i∈I}) is (ε, δ)-padded and 2^{n}- bounded for all n ∈ ℤ. In this case let g : [0, ∞) → [0, ∞) be given by:

g(x) = \{ \begin{matrix}1 & x ≥ 2 \\ x − 1 & 1 ≤ x ≤ 2 \\ 0 & 0 ≤ x ≤ 1, \end{matrix}

and define θ_{ω}^{n}(x) = g (\frac{π_{ω}^{n}(x)}{ε2^{n−1}} ), where π_{ω}^{n}(x) is as in (11). Let n_{0} be as in the proof of (12). Then:

S(x) ≥ ∑_{n: d(x,X)≤ε2^{n}} φ_{n}(x) ∫_{\{ω∈Ω_{n}: π_{ω}^{n}(x)≥ε2^{n}\}} g (\frac{π_{ω}^{n}(x)}{ε2^{n−1}}) (x) dμ_{n}(ω)

≥ φ (\frac{d(x, X)}{ε2^{n_{0}−3}}) μ_{n_{0}} (⋃_{i∈I} \{ω ∈ Ω_{n_{0}} : d (x, X \ Γ_{n}^{i}(ω)) ≥ ε2^{n_{0}}\}) ≥ δ.  (16)

Fix n ∈ ℤ and ω ∈ Ω_{n}. Assume φ_{n}(x) · φ_{n}(y) > 0. In this case {d(x, X), d(y, X)} ∩ [ε2^{n−4}, ε2^{n−1}] ≠ ∅, so that in particular d(y, X) ≤ ε2^{n−1}. We are assuming that d(x, y) < d(y, X), so d(x, X) ≤ d(x, y) + d(y, X) ≤ 2d(y, X) ≤ ε2^{n}. If x, y ∈ Γ_{n}^{j}(ω) for some j ∈ I then since g is Lipschitz with constant 1 and bounded by 1, the same reasoning as in (13) gives:

∑_{i∈I} |θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − θ_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| ≤ \frac{6d(x, y)}{ε2^{n}} ≤ \frac{6d(x, y)}{d(x, X)}.  (17)

On the other hand, if there distinct i, j ∈ I such that x ∈ Γ_{n}^{i}(ω) and y ∈ Γ_{n}^{j}(ω) then using the fact that π_{ω}^{n}(x), π_{ω}^{n}(y) ≤ d(x, y) we get :

∑_{ℓ∈I} |π_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{ℓ}(ω)}(x) − π_{ω}^{n}(y)φ_{n}(y)1_{Γ_{n}^{ℓ}(ω)}(y)| ≤ g (\frac{π_{ω}^{n}(x)}{ε2^{n−1}}) + g (\frac{π_{ω}^{n}(y)}{ε2^{n−1}} )

≤ \frac{π_{ω}^{n}(x)}{ε2^{n−1}} + \frac{π_{ω}^{n}(y)}{ε2^{n−1}} ≤ \frac{4d(x, y)}{d(x, X)}, (18)

and we conclude as in (15).

Case 3. The stochastic decomposition (Ω_{n}, μ_{n}, {Γ_{n}^{i}(·), γ_{n}^{i}(·)}_{i∈I}) is (ε, δ)-separating 2^{n}-bounded for all n ∈ ℤ. This case is simpler: we take θ_{ω}^{n}(x) ≡ 1. Arguing as in (12) we get that S(x) ≥ 1. Fix n ∈ ℤ and ω ∈ Ω_{n} and assume as before that φ_{n}(x) · φ_{n}(y) > 0. Observe that

∑_{i∈I} |φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| ≤ |φ_{n}(x) − φ_{n}(y)|

+\frac{φ_{n}(x) + φ_{n}(y)}{2} ∑_{i∈I} |1_{Γ_{n}^{i}(ω)}(x) − 1_{Γ_{n}^{i}(ω)}(y)|

≤ \frac{8d(x, y)}{ε2^{n}} + ∑_{i∈I} |1_{Γ_{n}^{i}(ω)}(x) − 1_{Γ_{n}^{i}(ω)}(y)|

≤ \frac{8d(x, y)}{d(x, X)} + ∑_{i∈I} |1_{Γ_{n}^{i}(ω)}(x) − 1_{Γ_{n}^{i}(ω)}(y)| . (19)

Plugging this estimate into (10) we get

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x)−Ψ(i, ω, y)| dμ_{n}(ω) ≤ \frac{8d(x, y)}{d(x, X)} · |\{n : \{x, y\} ∩ supp(φ_{n}) ≠ ∅\}|

+ ∑_{n: {x,y}∩supp(φ_{n})≠∅} ∫_{Ω_{n}} ∑_{i∈I} |1_{Γ_{n}^{i}(ω)}(x) − 1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}

≤ \frac{80 d(x, y)}{d(x, X)} + ∑_{n: \{x,y\}∩supp(φ_{n})≠∅} \frac{2d(x, y)}{δ2^{n}}

≤ \frac{80 d(x, y)}{d(x, X)} + \frac{20εd(x, y)}{δd(x, X)},

where we have used the (ε, δ)-separating condition and the fact that in the above sum, d(x, X) ≤ ε2^{n}.

We proceed to construct gentle partitions of unity when X is finite. The proof is analogous to the proof of Theorem 4.1, but there are several subtle differences, so we deal with this important case separately. The analysis uses ideas from [8, 9], namely that a certain sum of logarithms collapses in the analysis of the decomposition of Lemma 3.17. This allows the smoothing function φ to have larger support, which will be the key to achieving an improved result.

Theorem 4.3. There exists a universal constant C > 0 such that for all m ∈ ℕ, any metric space (Y, d) and any m-point subset X ⊆ Y, Y admits a C \frac{log m}{log log m}-gentle partition of unity with respect to X.

Proof. Let M > 2 be an integer which will be determined later. Let φ : ℝ → ℝ_{+} be a 5-Lipschitz map with supp(φ) ⊆ [\frac{1}{5}, 5^{M+1}] and φ ≡ 1 on [1, 5^{M}]. By Theorem 3.17, with σ the counting measure on X, for every n ∈ ℤ there exists a stochastic decomposition of Y with respect to X, (Ω_{n}, μ_{n}, {Γ_{n}^{i}(·), γ_{n}^{i}(·)}_{i∈I}), which is 5^{n}-bounded and for every x, y ∈ Y satisfying d({x, y}, X) ≤ 5^{n−2},

∫_{Ω_{n}} ∑_{i∈I} |1_{Γ_{n}^{i}(ω)}(x) − 1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}(ω) ≤ \frac{2d(x, y)}{5^{n}} [1 + log (\frac{|B_{X}(x, 5^{n+1})|}{|B_{X}(x, 5^{n})|})] .  (20)

Define φ_{n}(x) = φ (\frac{d(x,X)}{5^{n−M−4}} ), and let (Ω, μ), Ψ(i, ω, x), γ(i, ω), S(x) be as in the proof of Theorem 4.1, with θ_{ω}^{n}(x) ≡ 1. Our goal is to show that for every x, y ∈ Y,

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} d(γ(i, ω), x) · |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ(ω) ≤ O (\frac{log m}{log log m}) · d(x, y).

In what follows we fix x, y ∈ Y and we may assume without loss of generality that d(x, X) ≥ d(y, X). As in the proof of Claim 4.2, if |Ψ(i, ω, x) − Ψ(i, ω, y)| > 0 then d(γ(i, ω), x) ≤ 5^{n} + d(x, y). It is therefore enough to show that

∑_{n∈ℤ}5^{n} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ(ω) ≤ O (\frac{log m}{log log m}) · d(x, y).

Since φ_{n}(x) = 1 for at least M − 1 values of n, S(x) = ∑_{n∈ℤ} φ_{n}(x) ≥ M − 1 ≥ \frac{M}{2} . Hence, arguing as in (10) we get that

∑_{n∈ℤ}5^{n} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ(ω)

≤ \frac{2}{M} ∑_{n∈ℤ}5^{n} ∫_{Ω_{n}} ∑_{i∈I} |φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}(ω) +

\frac{4}{M^{2}} (∑_{n∈ℤ}5^{n}φ_{n}(y)) |S(x) − S(y)|.  (21)

Let j be the maximal integer for which φ_{j}(y) > 0. Then 5^{j} ≤ 5^{M+5}d(y, X) and

∑_{n∈ℤ}5^{n}φ_{n}(y) ≤ ∑_{n≤j} 5^{n} ≤ 5^{j+1} ≤ 5^{M+6}d(y, X).

Analogously, ∑_{n∈ℤ} 5^{n}φ_{n}(x) ≤ 5^{M+6}d(x, X). Since in |S(x) − S(y)| there are at most 4M non-zero summands, each of which is bounded by 2, we get the following estimate:

∑_{n∈ℤ}5^{n} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ(ω) ≤ \frac{4}{M} ∑_{n: \{x,y\}∩supp(φ_{n})≠∅} 5^{n} + \frac{5^{M+9}d(y, X)}{M}

≤ \frac{5^{M+7}}{M} [d(x, X) + d(y, X)] + \frac{5^{M+9}d(y, X)}{M}
≤ \frac{5^{M+10}}{2M} [d(y, X) + d(x, y)].

Corollary 4.4. If d(y, X) ≤ d(x, y) then:

∑_{n∈ℤ}5^{n} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ(ω) ≤ \frac{5^{M+10}}{M} d(x, y).

We now deal with the case d(x, X) ≥ d(y, X) > d(x, y). The reasoning above shows that the estimate (21) can be written as

∑_{n∈ℤ}5^{n} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ(ω)

≤ \frac{2}{M} ∑_{n∈ℤ}5^{n} ∫_{Ω_{n}} ∑_{i∈I} |φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}(ω) +
\frac{5^{M+7}}{M^{2}} · d(x, X) · |S(x) − S(y)|.  (22)

For the sake of simplicity, denote

E_{x,y} = {n ∈ ℤ : φ_{n}(x) = φ_{n}(y) = 1} and F_{x,y} = {n ∈ ℤ : φ_{n}(x) + φ_{n}(y) > 0} \ E_{x,y}. By the definition of φ_{n}, if n ∈ F_{x,y} then 5^{n} must be in

[5^{3}d(x, X), 5^{M+5}d(x, X)] ∪ [5^{3}d(y, X), 5^{M+5}d(y, X)]

but not in

[5^{4}d(x, X), 5^{M+4}d(x, X)] ∩ [5^{4}d(y, X), 5^{M+4}d(y, X)].

Since d(y, X) ≤ d(x, X) ≤ d(y, X) + d(x, y) ≤ 2d(y, Y), it follows that n can take at most 10 values. We have shown that |F_{x,y}| ≤ 10. Hence, using the fact that φ is 5-Lipschitz,

|S(x) − S(y)| ≤ ∑_{n∈F_{x,y}} |φ_{n}(x) − φ_{n}(y)| ≤ 10\frac{d(x, y)}{5^{n−M−5}} ≤ 5^{M+7} · \frac{d(x, y)}{d(x, X)}.  (23)

Fix n ∈ ℤ and ω ∈ Ω_{n} and argue as in (19) to get that

∑_{i∈I} |φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| ≤ \frac{d(x, y)}{5^{n−M−5}} · 1_{F_{x,y}}(n) + ∑_{i∈I} |1_{Γ_{n}^{i}(ω)}(x) − 1_{Γ_{n}^{i}(ω)}(y)| .

Since for n ∈ E_{x,y} ∪ F_{x,y}, d(x, X) ≤ 5^{n−2}, we may use (20) to get that

∫_{Ω_{n}} ∑_{i∈I} |φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}(ω)

≤ \frac{d(x, y)}{5^{n−M−5}} · 1_{F_{x,y}}(n) + \frac{2d(x, y)}{5^{n}} [1 + log (\frac{|B_{X}(x, 5^{n+1})|}{|B_{X}(x, 5^{n})|})]  (24)

Let j, J be the minimal and maximal integers i, respectively, for which φ_{i}(x) + φ_{i}(y) > 0. Observe that in this case J − j ≤ 4M and 5^{j−3} ≥ \frac{d(x,X)}{2}. Hence

∑_{n∈ℤ}5^{n} ∫_{Ω_{n}} ∑_{i∈I} |φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) − φ_{n}(y)1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}(ω)

≤ ∑_{n∈F_{x,y}} 5^{n} · \frac{d(x, y)}{5^{n−M−5}} + ∑_{n∈E_{x,y}∪F_{x,y}} 5^{n} ∫_{Ω_{n}} ∑_{i∈I} |1_{Γ_{n}^{i}(ω)}(x) − 1_{Γ_{n}^{i}(ω)}(y)| dμ_{n}
≤ 10 · 5^{M+5}d(x, y) + ∑_{n=j}^{J} 2d(x, y) [1 + log (\frac{|B_{X}(x, 5^{n+1})|}{|B_{X}(x, 5^{n})|})]
≤ 5^{M+7}d(x, y) + 2d(x, y) [4M + log (\frac{|B_{X}(x, 5^{J+1})|}{|B_{X}(x, 5^{j})|})]
≤ (5^{M+7} + 8M + 2 log m) · d(x, y),  (25)

Plugging (23) and (25) into (22) we arrive at the following corollary:

Corollary 4.5. If d(x, y) < d(y, X) then

∑_{n∈ℤ}5^{n} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ(ω) ≤ O (\frac{5^{2M}}{M^{2}} + \frac{log m}{M}) · d(x, y).

Using Corollary 4.4 and Corollary 4.5 with M ≈ log log m yields the required result.

5 Extension theorems

The following theorem is a direct consequence of the results of Section 2, Section 3 and Section 4.

Theorem 5.1. There exists a universal constant C > 0 such that

1. For every metric space X, ae(X) ≤ C log λ(X).

2. For every r > 0 and any K_{r}-excluded metric space X, ae(X) ≤ C · r^{2}.

3. Let M be a two dimensional Riemannian manifold with genus g and X ⊆ M. Then ae(X) ≤ C · (g + 1).

4. If X is an n-point metric space then ae(X) ≤ C \frac{log n}{log log n}.

5. For every integer d and every Banach space Z, e(ℓ_{2}^{d}, Z) ≤ C\sqrt{d}.

We also have the following extension result for neighborhoods of subsets of negatively curved manifolds.

Proposition 5.2. Fix r > 0 and let M be an n-dimensional Riemannian manifold satisfying Ricci(g) ≥ −(n−1)rg, where g is the Riemannian metric on M. Then for any subset X ⊆ M, any metric space Y ⊇ X such that X is Δ-dense in Y, and any Banach space Z, e(X, Y, Z) ≤ C · n (1 + \sqrt{rΔ}). Here C is a universal constant.

Proof. Observe that in this case in the proof of 4.1 we only require the existence of 2^{n}- padded decomposition with 2^{n} ≤ Δ. Hence the required result follows from an application of Corollary 3.13 and Lemma 3.8.

Let us recall that for a family of finite graphs F, we claim that ae(⟨F⟩) ≤ K_{F} if and only if ⟨F⟩ does not contain all finite metrics. We now give the simple proof which is based on a deep result of Robertson and Seymour [32].

Proof of Corollary 1.8. For a family of graphs F, let mc(F) denote its closure under taking minors, i.e. the maximal minor-closed family containing F. Robertson and Seymour proved that if mc(F) is non-trivial, i.e. does not contain all finite graphs, then there is some finite list of graphs H_{1}, ⋯, H_{k} such that G ∈ mc(F) if and only if G does not contain any H_{i} as a minor.

Observe that contraction/deletion of an edge corresponds to weighting by 0/∞, respectively. It follows that ⟨F⟩ = ⟨mc(F)⟩, thus if ⟨F⟩ does not contain all finite metrics, then certainly mc(F) does not contain all finite graphs, hence if X ∈ ⟨F⟩, it must be supported on some graph G which excludes a K_{r} minor with r = max_{i} |H_{i}|, and in this case part (2) of Theorem 5.1 applies.

We are now in position to prove Theorem 1.12 which was stated in the introduction.

Proof of Theorem 1.12. We begin with the case p = 2. Let X be an n-point subset of L_{2}, Z a Banach space and f : X → Z a Lipschitz function. Let H be the linear span of X and let Q be the orthogonal projection from L_{2} onto H. By the proof of the Johnson-Lindenstrauss dimension reduction lemma [17] there is a probability space (Ω, P) such that for every ω ∈ Ω there is a rank d linear operator T_{ω} : H → H such that for every x ∈ H, P (|∥T_{ω}(x)∥_{2} − ∥x∥_{2}| ≥ \frac{1}{2}) ≤ 2e^{−cd}, where c is a universal constant. We can therefore find for d ≈ \frac{4}{c} log n a subset A ⊂ Ω with P (A) ≥ \frac{1}{2} such that for every x, y ∈ X and ω ∈ A, ∥T_{ω}(x) − T_{ω}(y)∥_{2} ≥ \frac{1}{2}∥x − y∥_{2}. The function g_{ω} = f ∘ (T_{ω}|_{T_{ω}(X)})^{−1} is Lipschitz on T_{ω}(X) with constant 2∥f∥_{Lip}. By Theorem 5.1, there is a function g̃_{ω} : T_{ω}(H) → Z such that g̃_{ω}|_{T_{ω}(X)} = g_{ω} and ∥g̃_{ω}∥_{Lip} ≤ \frac{4C}{\sqrt{c}} \sqrt{log n} · ∥f∥_{Lip}. Define f̃: L_{2} → Z by:

f̃(x) = \frac{1}{P (A)} ∫_{A} g̃_{ω}(T_{ω}Qx)dP (ω).

Clearly f̃ is an extension of f and since P (A) ≥ \frac{1}{2}, for every x, y ∈ L_{p},

∥f̃(x) − f̃(y)∥_{Z} ≤ \frac{1}{P (A)} ∫_{A} ∥g̃_{ω}(T_{ω}Qx) − g̃_{ω}(T_{ω}Qy)∥_{Z} dP (ω)
≤ O (\sqrt{log n}) ∥f∥_{Lip} · ∫_{Ω} ∥T_{ω}(Qx − Qy)∥_{2} dP (ω)
= O (\sqrt{log n}) ∥f∥_{Lip} · ∥x − y∥_{2},

where we have used the fact that the concentration inequality for ∥T_{ω}z∥_{2}, z ∈ H, implies that ∫_{Ω} ∥T_{ω}z∥dP (ω) = O(∥z∥_{2}).

We pass to general 1 < p ≤ 2 via a method due to Marcus and Pisier [27]. In [27] they show that for every 0 < p ≤ 2 there is a probability space (Ω′, P′) such that for every ω ∈ Ω′ there is a linear operator S_{ω} : L_{p} → L_{2} such that for every x ∈ L_{p} \ {0} the random variable X = \frac{∥S_{ω}(x)∥_{2}}{∥x∥_{p}} satisfies for every a ∈ ℝ, 𝔼e^{−aX^{2}} = e^{−a^{p/2}}. Let T be an n-point subset of L_{p}, Z a Banach space and f : T → Z a Lipschitz function. A standard application of Markov’s inequality shows that there is constant c_{p} and a subset A′ ⊂ Ω with P′(A′) ≥ \frac{1}{2} such that for every x, y ∈ X and ω ∈ A′,

∥x − y∥_{p} ≤ c_{p}(log n)^{\frac{1}{p} − \frac{1}{2}} ∥S_{ω}(x) − S_{ω}(y)∥_{2}.

For every ω ∈ A′ the function g_{ω} = f ∘ (S_{ω}|_{S_{ω}(X)})^{−1} is O ((log n)^{\frac{1}{p} − \frac{1}{2}} ) ∥f∥_{Lip} Lipschitz. By the above reasoning for the case p = 2, g_{ω} can be extended to a function g̃_{ω} defined on all of L_{2} which is Lipschitz with constant O ((log n)^{1/p}) ∥f∥_{Lip}. Define f̃: L_{p} → L_{2} by:

f̃(x) = \frac{1}{P′(A′)} ∫_{A′} g̃_{ω}(S_{ω}(x)) dP′(ω).

Clearly f̃ is an extension of f and since P′(A′) ≥ \frac{1}{2}, for every x, y ∈ L_{p},

∥f̃(x) − f̃(y)∥_{Z} ≤ \frac{1}{P′(A′)} ∫_{A′} ∥g̃_{ω}(S_{ω}(x)) − g̃_{ω}(S_{ω}(y))∥_{Z} dP′(ω)
≤ O ((log n)^{1/p}) ∥f∥_{Lip} · ∫_{Ω} ∥S_{ω}(x − y)∥_{2} dP′(ω)
= O ((log n)^{1/p}) ∥f∥_{Lip} · ∥x − y∥_{p} · 𝔼X,

and we conclude since for p > 1, 𝔼X = C_{p} < ∞.

Remark 5.3. As stated in the introduction, it was asked in [17] and [18] whether for every Banach space X, sup_{n} e_{n}(L_{2}, X) < ∞. This is false since in [30] it was shown that for 2 < p < ∞, e(L_{2}, L_{p}) = ∞. We end by reproducing the argument from [30] (which is based on ideas from [25]) in such a way that we get quantitative lower bounds on e_{n}(L_{2}, ℓ_{p}), 2 < p < ∞. Since we are essentially repeating the proof from [30], our argument will be somewhat sketchy.

We claim that, for every integer n and every 2 < p < ∞,

e_{n}(L_{2}, L_{p}) ≥ Ω [(\frac{log n}{log log n})^{\frac{p−2}{p^{2}}} ] .

Proof (sketch). Fix an integer m and set ε = \frac{1}{n^{1/2−1/p}}. Let N be an ε net in the unit ball of ℓ_{2}^{2m}, denoted B. By standard (crude) volume estimates |N| ≤ m^{2m}. Consider the Mazur map f : ℓ_{2}^{2m} → ℓ_{p}^{2m} given by f(x)_{i} = |x_{i}|^{2/p}sign(x_{i}). From the numerical inequality |a^{2/p}sign(a) − b^{2/p}sign(b)| ≤ 2^{1−2/p}|a−b|^{2/p} it follows that for every x, y ∈ ℓ_{2}^{2m}, ∥f(x)−f(y)∥_{p} ≤ 2∥x−y∥_{2}^{2/p}. Since the elements of N are ε separated, the restriction of f to N is Lipschitz with constant 2/ε^{1−2/p} = 2m^{(1−2/p)(1/2−1/p)}. Assume that it is possible to extend f|_{N} to a function g : ℓ_{2}^{2m} → ℓ_{p}^{2m} which is K Lipschitz. Since N is ε-dense in B, for every x ∈ B, ∥f(x)−g(x)∥_{p} ≤ Kε+2ε^{2/p}. As in [30], by averaging g over all permutations and sign changes we arrive at a function h satisfying h(a1_{A}) = b1_{A} for all scalars a and A ⊂ {1, …, 2m}, where b depends only on the a and the cardinality of A. Additionally, h is K Lipschitz, and since f is invariant under permutations and changes of sign of the coordinates, for every x ∈ B, ∥h(x) − f(x)∥_{p} ≤ Kε + 2ε^{2/p}. Setting x_{k} = \frac{1}{\sqrt{2m}}1_{\{k,...,k+m−1\}} it follows that ∥h(x_{m+1}) − h(x_{1})∥_{p}^{p} = ∑_{k=1}^{m} ∥h(x_{k+1}) − h(x_{k})∥_{p}^{p}, and since h is K-Lipschitz we get the estimate ∥h(x_{m+1}) − h(x_{1})∥_{p} ≤ \frac{K}{m^{1/2−1/p}} = Kε. On the other hand,

2Kε + 2ε^{2/p} ≥ ∥h(x_{m+1}) − f(x_{m+1})∥_{p} + ∥h(x_{1}) − f(x_{1})∥_{p}
≥ ∥f(x_{m+1}) − f(x_{1})∥_{p} − ∥h(x_{n+1}) − h(x_{1})∥_{p} ≥ 1 − Kε.

This implies that the ratio between K and the Lipschitz constant of f is at least K/(2ε^{2/p−1}) = Ω(ε^{−2/p}) = Ω {[(log n)/(log log n)]^{(2−p)/p^{2}}}, where n = m^{2m} ≥ |N|.

6 Appendix: Passing to arbitrary barycentric target spaces

In order to deal with barycentric metric spaces it is convenient to introduce the following variant of the notion of a gentle partition of unity. Let (Y, d) be a metric space, X a subspace of Y and (Ω, F, μ) a measure space. Given K, L > 0 we shall say that a function Ψ : Ω × Y → [0, ∞) is a (K, L)-gentle partition of unity with respect to X if the following conditions hold true:

1. For every x ∈ Y \ X the function ω ↦ Ψ(ω, x) is measurable and ∫_{Ω} Ψ(ω, x)dμ(ω) = 1.

2. There exists a Borel measurable function γ : Ω → \overline{X} such that for every x, y ∈ Y,

diam({x, y} ∪ {γ(ω) : Ψ(ω, x) + Ψ(ω, y) > 0}) ≤ K · [d(x, y) + max{d(x, X), d(y, X)}], 3. For every x, y ∈ Y, x ≠ y,

∫_{Ω} |Ψ(ω, x) − Ψ(ω, y)| dμ(ω) ≤ L · \frac{d(x, y)}{d(x, y) + max\{d(x, X), d(y, X)\}}.

The following lemma is a variant of Lemma 2.1

Lemma 6.1. Let (Y, d_{Y}) be a metric space and X a subspace of Y. Fix K, L > 0 and assume that Y admits a (K, L)-gentle partition of unity Ψ : Ω × Y → [0, ∞) with respect to X. Let (Z, d_{Z}) be a complete barycentric metric space and β > β(Z). Then every Lipschitz function f : X → Z can be extended to a function f̃: Y → Z such that ∥f̃∥_{Lip} ≤ β max{KL, 2K + 2}.

Proof. As in the proof of Lemma 2.1, we may assume that X is closed. Let c : M_{Z}^{bounded} → Z be a mapping satisfying the conditions of Definition 1.14 and let γ : Ω → X be as in condition 2 above.

For every x ∈ Y \ X define ν_{x} ∈ M_{Z}^{bounded} by

ν_{x}(A) = ∫_{γ^{−1}(f^{−1}(A))} Ψ(ω, x)dμ(ω).

In other words, ν_{x} is the pullback of the probability measure Ψ(·, x)dμ under the mapping f ∘ γ. For x ∈ X we define ν_{x} = δ_{f(x)}. Finally, for x ∈ Y set f̃(x) = c(ν_{x}). Clearly f̃ is an extension of f.

If x, y ∈ Y then by (1),

d_{Z}(f̃(x), f̃(y)) ≤ β · diam(supp(ν_{x} + ν_{y})) · ∥ν_{x} − ν_{y}∥_{T V} .

Now, if x, y ∈ Y \ X then

diam(supp(ν_{x} + ν_{y})) ≤ ∥f∥_{Lip} · diam({γ(ω) : Ψ(ω, x) + Ψ(ω, y) > 0})
≤ ∥f∥_{Lip} · K · [d(x, y) + max{d(x, X), d(y, X)}].

and

∥ν_{x} − ν_{y}∥_{T V} ≤ ∫_{Ω} |Ψ(ω, x) − Ψ(ω, y)|dμ(y) ≤ L · \frac{d(x, y)}{d(x, y) + max\{d(x, X), d(y, X)\}}.

This implies that for x, y ∈ Y \ X,

d_{Z}(f̃(x), f̃(y)) ≤ βKL · ∥f∥_{Lip}.

It remains to deal with the case x ∈ X and y ∈ Y \X. In this case set Γ = {γ(ω) : Ψ(ω, y) > 0}. Condition 2 (applied with x = y) implies that diam({y} ∪ Γ) ≤ Kd(y, X). In particular, d(x, Γ) ≤ d(x, y) + d(y, Γ) ≤ d(x, y) + Kd(y, X) ≤ (K + 1)d(x, y). It follows that

diam(supp(ν_{x} + ν_{y})) ≤ ∥f∥_{Lip} · diam({x, y} ∪ Γ) ≤ ∥f∥_{Lip}(K + 1)d(x, y).

On the other hand, ∥ν_{x} − ν_{y}∥_{T V} ≤ 2, and the required result follows.

The following theorem is a simple variant of Theorem 4.1, adapted to the case of (K, L) gentle partitions of unity.

Theorem 6.2. For every ε, δ ∈ (0, 1), every metric space (Y, d) and every subspace X ⊆ Y the following assertions hold true:

1. If for every n ∈ ℤ, Y admits an (ε, δ)-thick 2^{n}-bounded stochastic decomposition with respect to X, then Y also admits a (\frac{36}{ε}, \frac{680}{δ})-gentle partition of unity with respect to X.

2. If for every n ∈ ℤ, Y admits an (ε, δ)-padded 2^{n}-bounded stochastic decomposition with respect to X, then Y also admits a (\frac{36}{ε}, \frac{680}{δ})-gentle partition of unity with respect to X.

3. If for every n ∈ ℤ, Y admits an (ε, δ)-separating 2^{n}-bounded stochastic decomposition with respect to X, then Y also admits a (\frac{36}{ε}, 160 (1 + \frac{ε}{δ}))-gentle partition of unity with respect to X.

Proof. Since the proof is a straightforward modification of the proof of Theorem 4.1, we will only sketch the necessary changes. As before, for every n ∈ ℤ let (Ω_{n}, μ_{n}, {Γ_{n}^{i}(·), γ_{n}^{i}(·)}_{i∈I}) be a 2^{n}-bounded stochastic decomposition of Y with respect to X. Let φ : ℝ → ℝ_{+} be any 2-Lipschitz map with supp(φ) ⊂ [\frac{1}{2}, 4] and φ ≡ 1 on [1, 2]. Define φ_{n}(x) = φ (\frac{d(x,X)}{ε2^{n−3}}) and let (Ω, μ) be the disjoint union of {I × Ω_{n}}_{n∈ℤ} (where the measure on I is the counting measure). The partition of unity which we construct has the following form: For every n ∈ ℤ, ω ∈ Ω_{n}, i ∈ I and x ∈ Y denote:

Ψ(i, ω, x) = \frac{1}{S(x)} θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x),  (26)

where for every n ∈ ℤ and x ∈ Y the function ω ↦ θ_{ω}^{n}(x) ∈ [0, ∞) is μ_{n}-integrable and

S(x) = ∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} θ_{ω}^{n}(x)φ_{n}(x)1_{Γ_{n}^{i}(ω)}(x) dμ_{n}(ω) = ∑_{n∈ℤ}φ_{n}(x) ∫_{Ω_{n}} θ_{ω}^{n}(x) dμ_{n}(ω).

Additionally define γ(i, ω) = γ_{n}^{i}(ω). Fix n ∈ ℤ, ω ∈ Ω_{n}, i ∈ I and assume that x ∈ Y is such that Ψ(i, ω, x) > 0. Then x ∈ Γ_{n}^{i}(ω) and d(x, X) ∈ [ε2^{n−4}, ε2^{n−1}]. Since d(γ_{n}^{i}(ω), Γ_{n}^{i}(ω)) < 2d(X, Γ_{n}^{i}(ω)) ≤ 2d(x, X) there is x′ ∈ Γ_{n}^{i}(ω) for which d(γ_{n}^{i}(ω), x′) < 2d(x, X). Hence,

d(γ_{n}^{i}(ω), x) ≤ 2d(x, X) + diam(Γ_{n}^{i}(ω)) ≤ 2d(x, X) + 2^{n} ≤ (2 + \frac{16}{ε}) d(x, X) ≤ \frac{18}{ε}d(x, X).

Similarly, if m ∈ ℤ, ω′ ∈ Ω_{m}, j ∈ I are such that Ψ(j, ω′, y) > 0 for some y ∈ Y then

d(γ_{m}^{j}(ω′), y) ≤ \frac{18}{ε}d(y, X).

It follows that

d(γ_{n}^{i}(ω), γ_{m}^{j}(ω′)) ≤ d(x, y) + \frac{18}{ε}d(x, X) + \frac{18}{ε}d(y, X) ≤ \frac{36}{ε} (d(x, y) + max\{d(x, X), d(y, X)\}) .

Hence,

diam (\{x, y\} ∪ \{γ(i, ω) : Ψ(i, ω, x) + Ψ(i, ω, y) > 0\}) ≤ \frac{36}{ε} (d(x, y) + max\{d(x, X), d(y, X)\}) .

It is therefore enough to show that:

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω) ≤ \frac{680}{δ} · \frac{d(x, y)}{d(x, y) + max\{d(x, X), d(y, X)\}},

when the decompositions are either (ε, δ)-padded or (ε, δ)-thick and

∑_{n∈ℤ} ∑_{i∈I} ∫_{Ω_{n}} |Ψ(i, ω, x) − Ψ(i, ω, y)| dμ_{n}(ω) ≤ 160 (1 + \frac{ε}{δ}) · \frac{d(x, y)}{d(x, y) + max\{d(x, X), d(y, X)\}},

when the decompositions are (ε, δ)-separating. From here on the proof is exactly as in the proof of Theorem 4.1.

Lemma 6.1, Theorem 6.2 and the results of Section 3.2 imply the extension results stated in the introduction, in the case when the target space Z is a complete barycentric metric space. The above argument does not yield a similar generalization of Theorem 1.10, since the construction of Theorem 4.3 does not imply a satisfactory bound as in condition 2 in the definition of a (K, L) gentle partition of unity. An inspection of the proof of Lemma 2.1 shows that we have only used the following property of the Banach space Z: There exists a map c : M_{Z}^{bounded} → Z such that c(δ_{z}) = z for every z ∈ Z and for every μ, ν ∈ M_{Z}^{bounded} and p ∈ Z,

d_{Z}(c(μ), c(ν)) ≤ C ∫_{Z} d(p, z)d|μ − ν|(z),  (27)

where C is a constant (depending on Z). This inequality holds true in Banach spaces due to the identity

∫_{Z} zdμ(z) − ∫_{Z} zdν(z) = ∫_{Z}(z − p)d(μ − ν)(z).

All the results presented in this paper extend to target spaces satisfying (27) (using K-gentle partitions of unity), and it would be of interest to find a wider class of spaces with this property.

References

[1] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2:137–172, 1992.

[2] Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium Foundations of Computer Science, 1998.

[3] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[4] Y. Brudnyi and P. Shvartsman. Stability of the Lipschitz extension property under metric transforms. Geom. Funct. Anal., 12(1):73–79, 2002.

[5] S. Buyalo and V. Schroeder. Extension of Lipschitz maps into 3-manifolds. Asian J. Math., 5(4):685–704, 2001.

[6] G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, 2001.

[7] M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. A. Plotkin. Approximating a finite metric by a small number of tree metrics. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998.

[8] J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar. An improved approximation algorithm for the 0-extension problem. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, 2003.

[9] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In 35th Annual ACM Symposium on Theory of Computing. ACM, 2003.

[10] J. Fakcharoenphol and K. Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In 7th International Workshop on Randomization and Approximation Techniques in Computer Science. Springer-Verlag, 2003.

[11] M. Gromov. Asymptotic invariants of infinite groups. In Geometric group theory, Vol. 2 (Sussex, 1991), volume 182 of London Math. Soc. Lecture Note Ser., pages 1–295. Cambridge Univ. Press, Cambridge, 1993.

[12] M. Gromov. Metric structures for Riemannian and non-Riemannian spaces. Birkhäuser, Boston, 1999.

[13] M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13:73–146, 2003.

[14] A. Gutpa, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and lowdistortion embeddings. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 2003.

[15] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[16] F. John. Extremum problems with inequlities as subsidiary conditions. Courant Anniversary Volume. Interscience, New York, pages 187–204–245, 1948.

[17] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

[18] W. B. Johnson, J. Lindenstrauss, and G. Schechtman. Extensions of Lipschitz maps into Banach spaces. Israel J. Math., 54(2):129–138, 1986.

[19] M. D. Kirszbraun. Über die zusammenziehenden und Lipschitzchen Transformationen. Fund. Math., (22):77–108, 1934.

[20] P. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In 25th Annual ACM Symposium on Theory of Computing, pages 682–690, May 1993.

[21] K. Kuratowski and C. Ryll-Nardzewski. A general theorem on selectors. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astron. Phys., 13:397–403, 1965.

[22] U. Lang. Extendability of large-scale Lipschitz maps. Trans. Amer. Math. Soc., 351(10):3975–3988, 1999.

[23] U. Lang, B. Pavlović, and V. Schroeder. Extensions of Lipschitz maps into Hadamard spaces. Geom. Funct. Anal., 10(6):1527–1553, 2000.

[24] J. R. Lee and A. Naor. Absolute Lipschitz extendability. C. R. Acad. Sci. Paris, to appear, 2003.

[25] J. Lindenstrauss. On nonlinear projections in Banach spaces. Michigan Math. J., 11:263– 287, 1964.

[26] N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441– 454, 1993.

[27] M. B. Marcus and G. Pisier. Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes. Acta Math., 152(3-4):245–301, 1984.

[28] J. Matoušek. Extension of Lipschitz mappings on metric trees. Comment. Math. Univ. Carolin., 31(1):99–104, 1990.

[29] B. Mohar and C. Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 2001.

[30] A. Naor. A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between L_{p} spaces. Mathematika, 48:253–271, 2001.

[31] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300–306. ACM, 1999.

[32] N. Robertson and P. D. Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Combin. Theory Ser. B, 48(2):255–288, 1990.

[33] L. Silberman. Addendum to ”Random walk in random groups” by M. Gromov. Geom. Funct. Anal., 13:147–177, 2003.

[34] I. G. Tsar′kov. Extension of Hilbert-valued Lipschitz mappings. Vestnik Moskov. Univ. Ser. I Mat. Mekh., (6):9–16, 72, 1999.

[35] J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, New York, 1975. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.

[36] H. Whitney. Analytic extension of differentiable functions defined in closed sets. Trans. Amer. Math. Soc., 36:63–89, 1934.

[37] H. Whitney. Differentiable functions defined in closed sets I. Trans. Amer. Math. Soc., 36:369–387, 1934.