ON LIPSCHITZ EXTENSION FROM FINITE SUBSETS

ASSAF NAOR AND YUVAL RABANI

Abstract. We prove that for every n ∈ ℕ there exists a metric space (X, d_{X}), an n-point subset S ⊆ X, a Banach space (Z, ∥ · ∥_{Z}) and a 1-Lipschitz function f : S → Z such that the Lipschitz constant of every function F : X → Z that extends f is at least a constant multiple of \sqrt{log n}. This improves a bound of Johnson and Lindenstrauss [JL84]. We also obtain the following quantitative counterpart to a classical extension theorem of Minty [Min70]. For every α ∈ (1/2, 1] and n ∈ ℕ there exists a metric space (X, d_{X}), an n-point subset S ⊆ X and a function f : S → ℓ_{2} that is α-Hölder with constant 1, yet the α-Hölder constant of any F : X → ℓ_{2} that extends f satisfies

∥F ∥_{Lip(α)} ≳ (log n)^{\frac{2α−1}{4α}} + ( \frac{log n}{log log n} )^{α^{2}− \frac{1}{2}} .

We formulate a conjecture whose positive solution would strengthen Ball’s nonlinear Maurey extension theorem [Bal92], serving as a far-reaching nonlinear version of a theorem of König, Retherford and Tomczak-Jaegermann [KRTJ80]. We explain how this conjecture would imply as special cases answers to longstanding open questions of Johnson and Lindenstrauss [JL84] and Kalton [Kal04].

1. Introduction

Given two metric spaces (X, d_{X}) and (Z, d_{Z}), the Lipschitz constant of a mapping f : X → Z will be denoted below by ∥f∥_{Lip}. For every subset S ⊆ X, let e(X, S, Z) denote the infimum over those K ∈ (0, ∞] with the property that for every f : S → Z there exists F : X → Z with ∥F ∥_{Lip} ⩽ K∥f∥_{Lip} and whose restriction to S satisfies F |_{S} = f. In its most general form, the Lipschitz extension problem asks for estimates on the quantity e(X, S, Z).

It is of great interest to obtain geometric conditions on the metric spaces (X, d_{X}) and (Z, d_{Z}) ensuring that e(X, S, Z) < ∞ for every S ⊆ X. Formally, define e(X, Z) to be the supremum of e(X, S, Y) over all S ⊆ X. When e(X, Z) = ∞, it is natural to refine the Lipschitz extension problem by taking n ∈ ℕ and defining e_{n}(X, Z) to be the supremum of e(X, S, Z) over all S ⊆ X of cardinality at most n, and asking for the asymptotic behavior of e_{n}(X, Z) as n → ∞. Another natural quantitative refinement of the parameter e(X, Z) is to fix ε ∈ (0, 1] and define e_{ε}(X, Z) to be the supremum of e(X, S, Z) over all S ⊆ X that are ε-discrete in the sense that d_{X}(x, y) ⩾ ε·diam(S) for every distinct x, y ∈ S, and asking for the asymptotic behavior of e_{ε}(X, Z) as ε → 0.

Denote the supremum of e_{n}(X, Z) over all metric spaces (X, d_{X}) and all Banach spaces (Z, ∥·∥_{Z}) by 𝔞𝔢(n). Here “𝔞𝔢” stands for “absolute extendability,” where we are following the notation and terminology that was introduced in [LN04]. Thus, if 𝔞𝔢(n) < K then for every n-point metric space (M, d_{M}), every Banach-space valued 1-Lipschitz function defined on M can be extended to any metric space that (isometrically) contains (M, d_{M}) so that the Lipschitz constant of the extended function is at most K. One can similarly define for ε > 0 the quantity 𝔞𝔢(ε) by considering the supremum of e_{ε}(X, Z) over all metric spaces (X, d_{X}) and all Banach spaces (Z, ∥ · ∥_{Z}).

A. N. was supported in part by the NSF, the BSF, the Packard Foundation and the Simons Foundation.

Y. R. was supported in part by the ISF, the BSF, and by the Israeli Center of Excellence on Algorithms.

The finiteness of 𝔞𝔢(n) and 𝔞𝔢(ε) for every n ∈ ℕ and ε ∈ (0, 1] is well-known. Johnson, Lindenstrauss and Schechtman proved in [JLS86] that 𝔞𝔢(n) ≲ log n, where here, and in what follows, the notation A ≲ B (respectively A ≳ B) stands for A ⩽ CB (respectively A ⩾ CB) for some universal constant C ∈ (0, ∞). We shall also use the notation A ≍ B when A ≲ B and A ≳ B. The above upper bound of [JLS86] on 𝔞𝔢(n) was more recently improved [LN04, LN05] to 𝔞𝔢(n) ≲ (log n)/ log log n, which is the best-known upper bound on 𝔞𝔢(n) to date. Determining the asymptotic behavior of 𝔞𝔢(n) as n → ∞ remains a major open problem. The previously best-known lower bound on 𝔞𝔢(n) is 𝔞𝔢(n) ≳ \sqrt{(log n)/ log log n}, obtained over thirty years ago by Johnson and Lindenstrauss [JL84] (see also [MM10] for a variant of the construction of Johnson and Lindenstrauss that also yields the same lower bound). Here we obtain the following improvement.

Theorem 1. For every n ∈ ℕ we have 𝔞𝔢(n) ≳ \sqrt{log n}.

Thus, the best-known bounds for 𝔞𝔢(n) are now

\sqrt{log n} ≲ 𝔞𝔢(n) ≲ \frac{log n}{log log n}.  (1)

It would be very interesting to improve any of the bounds in (1), the ultimate goal being to determine the rate at which 𝔞𝔢(n) tends to ∞ as n → ∞.

In [JL84] it was shown that 𝔞𝔢(ε) ≲ 1/ε, and a different and very simple proof of this fact was given in [JLS86]. In [MN13a] it was proved that 𝔞𝔢(ε) ≳ 1/ε, via a quantitative refinement of a beautiful argument of Kalton [Kal12]. Thus 𝔞𝔢(ε) ≍ 1/ε. The example that leads to Theorem 1 also yields a new proof that 𝔞𝔢(ε) ≳ 1/ε which some may find to be somewhat simpler than the proof in [MN13a]; see Remark 14 below. We note, however, that the example of [MN13a] has important properties (see the discussion in Section 1.6 of [MN13a]) that Theorem 1 does not imply.

The value of Theorem 1 does not stem only from the fact that it yields an asymptotic improvement over the best known bound, but rather because this improvement relies on a conceptually different approach than that of [JL84]. In fact, as emphasized explicitly in [JL84], the difficulty to improve the lower bound on 𝔞𝔢(n) to a constant multiple of \sqrt{log n} is not purely technical, and the approach of [JL84] inherently cannot yield a lower bound that is better than o(\sqrt{log n}).

To explain the above assertions, we need to briefly sketch the argument of [JL84]. Fix k ∈ ℕ, L > 0 and ε ∈ (0, 1/2). Suppose that (X, ∥ · ∥_{X}) is a Banach space and Y ⊆ X is a k-dimensional linear subspace of X. Let 𝒩_{ε} be an ε-net in the unit sphere of Y and denote S_{ε} = 𝒩_{ε} ∪ {0}. Taking f : S_{ε} → S_{ε} ⊆ Y to be the identity mapping, it is proved in [JL84] that if F : X → Y is an L-Lipschitz extension of f and ε is sufficiently small then there exists a linear projection P : X → Y with ∥P ∥ ≲ L. Hence, if for some Λ > 0 one knows that ∥P ∥ ⩾ Λ for every linear projection P : X → Y then one concludes that L ≳ Λ. Suppose that Λ ≳ \sqrt{k}; since the classical Kadec′–Snobar theorem [KS71] (see also [Woj91, §III.B]) asserts that we always have Λ ⩽ \sqrt{k}, this lower bound on Λ is the best one could hope for. By standard bounds on the size of ε-nets (e.g. [MS86]), if we set n = |S_{ε}| then log n ≍ k log(1/ε), so we have L ≳ \sqrt{(log n)/ log(1/ε)}. For this strategy to yield a lower bound that is a constant multiple of \sqrt{log n}, one needs to take ε to be a universal constant, but in this case we would have L ≲ 𝔞𝔢(2ε) ≲ 1/ε = O(1). So, in order to get a lower bound on L that tends to ∞ with n one must have ε = o(1) as k → ∞ (indeed, in [JL84] the choice of ε is log(1/ε) ≍ log k ≍ log log n). This explains why one cannot prove Theorem 1 via the above strategy of reduction to the nonexistence of linear projections of small norm. Note also that due to the Kadec′–Snobar theorem [KS71], this “linearization” approach cannot yield a lower bound on 𝔞𝔢(n) that tends to ∞ at a rate that is faster than a constant multiple of \sqrt{log n}.

Here we overcome the above obstacle by abandoning entirely the desire to reduce the problem to the nonexistence of linear projections of small norm. We consider a family of metric spaces that arise from (a modification of) expander graphs, and our poorly extendable functions take values in their associated Wasserstein 1 spaces. The proof relies on direct geometric considerations, in particular the use of Banach space-valued Poincaré inequalities (see Lemma 8 below), rather than a reduction to linear mappings. Our approach is inspired by a certain algorithmic clustering problem for graphs, specifically by leveraging the difference between two relaxations of the corresponding combinatorial optimization problem. This motivation is explained in Section 2 below, though the proof of Theorem 1 (in Section 3) is direct and does not rely on any algorithmic background.

1.1. Hilbert space-valued Hölder functions. Suppose that (X, d_{X}) and (Z, d_{Z}) are metric spaces and α ∈ (0, 1]. We shall denote below the α-Hölder constant of a mapping f : X → Z by ∥f∥_{Lip(α)}. Thus ∥f∥_{Lip(α)} is the infimum over those L ∈ (0, ∞] for which every x, y ∈ X satisfy d_{Z}(f(x), f(y)) ⩽ Ld_{X}(x, y)^{α}. Equivalently, ∥f∥_{Lip(α)} is the Lipschitz constant of f when it is viewed as a mapping between from the metric space (X, d_{X}^{α}) to the metric space (Z, d_{Z}). Denote

e^{α}(X, Z) =^{def} e((X, d_{X}^{α}), (Z, d_{Z}))  and  ∀ n ∈ ℕ,  e_{n}^{α}(X, Z) =^{def} e_{n}((X, d_{X}^{α}), (Z, d_{Z})).

Thus, e^{α}(X, Z) is the infimum over those K ∈ [1, ∞] such that for every S ⊆ X and every f : S → Z there exists F : X → Z with F |_{S} = f and ∥F ∥_{Lip(α)} ⩽ K∥f∥_{Lip(α)}, and analogously for e_{n}^{α}(X, Z).

A classical theorem of Minty [Min70] asserts that if H is a Hilbert space then e^{α}(X, H) = 1 for every metric space (X, d_{X}) and α ∈ (0, 1/2] (equivalently, e_{n}^{α}(ℓ_{∞}, ℓ_{2}) = 1 for all n ∈ ℕ). Minty’s theorem fails when α ∈ (1/2, 1] (see [HW71]), but understanding what happens when α ∈ (1/2, 1] remains a mystery. Specifically, Kalton conjectured in [Kal04] that for every α ∈ [1/2, 1] and every m ∈ ℕ we have

e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ≲ m^{α− \frac{1}{2}} .  (2)

This conjecture appears as Problem 11.3 in [Kal04]^{1}. See the discussion immediately following Problem 11.3 in [Kal04] for an interesting geometric application that (2) would imply. The estimate (2) holds true when α = 1/2 due to Minty’s theorem, and also when α = 1 by the fact that ℓ_{2}^{m} is \sqrt{m}-isomorphic to ℓ_{∞}^{m}, combined with an application of the nonlinear Hahn–Banach theorem (see e.g. [BL00, Lemma 1.1]). Thus (2) is a natural conjectural interpolation between Minty’s theorem and the nonlinear Hahn-Banach theorem.

Kalton’s conjecture (2) remains an interesting open problem, and in Section 1.2 we formulate a conjecture whose validity would imply the validity of (2). In the reverse direction, to the best of our knowledge its isn’t known whether (2) would be sharp. We therefore ask the following question.

Question 2. Is it true that e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ≳ m^{α− \frac{1}{2}} for every α ∈ (1/2, 1)?

We also ask the following variant of Question 2 for the parameter e_{n}^{α}(ℓ_{∞}, ℓ_{2}).

Question 3. Is it true that e_{n}^{α}(ℓ_{∞}, ℓ_{2}) ≳ (log n)^{α− \frac{1}{2}} for every α ∈ (1/2, 1)?

By mimicking an argument of [JL84] one sees that a positive answer to Question 3 would imply a positive answer to Question 2. Indeed, for every metric space (X, d_{X}) and α ∈ (0, 1] we have

e_{2^{7m}}^{α}(X, ℓ_{2}) ⩽ 3e^{α}(ℓ_{∞}, ℓ_{2}^{m}).  (3)

(The choice of constants in (3) is somewhat arbitrary; see below.) Since (3) is not stated explicitly in [JL84], we shall now briefly explain how it is proved. Fix S ⊆ X with |S| ⩽ 2^{7m} and f : S → ℓ_{2}. Since f(S) is a subset of a Hilbert space of cardinality at most 2^{7m}, by the Johnson–Lindenstrauss dimensionality reduction lemma [JL84] there exists a mapping g : f(S) → ℓ_{2}^{m} such that

∀ a, b ∈ f(S),  ∥a − b∥_{2} ⩽ ∥g(a) − g(b)∥_{2} ⩽ 3∥a − b∥_{2}.  (4)

1We note in passing that there is a misprint in [Kal04, Problem 11.3]: in the two displayed equations that appear there the exponent α erroneously appears in the left hand side of the inequality rather than in its right hand side.

The specific parameters in the Johnson–Lindenstrauss lemma that we take here are valid due to the bounds in [Ach03, Theorem 1.1]. By the Kirszbraun extension theorem [Kir34],

∃ g̃^{−1} : ℓ_{2}^{m} → ℓ_{2} such that g̃^{−1}|_{g∘f(S)} = g^{−1} and ∥g̃^{−1}∥_{Lip} ⩽ ∥g^{−1}∥_{Lip} ⩽ 1,  (5)

where the last step of (5) uses the left hand inequality in (4). Also, by the definition of e^{α}(ℓ_{∞}, ℓ_{2}^{m}),

∃ { \atop g ∘ f} : X → ℓ_{2}^{m} such that { \atop g ∘ f}|_{S} = g ∘ f and ∥{ \atop g ∘ f}∥_{Lip(α)} ⩽ e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ∥g ∘ f∥_{Lip(α)} . (6)

Thus, the following diagram commutes.

\xymatrix{X \ar[rr]^{{ \atop g∘f}} \ar[r]^{g̃^{−1}∘{ \atop g∘f}} & ℓ_{2} & ℓ_{2}^{m} \ar[l]_{g̃^{−1}} \\ S \ar@{^{(}->}[u]^{⊆} \ar[r]^{f} & f(S) \ar@{^{(}->}[u]^{⊆} \ar[r]^{g} & g ∘ f(S) \ar[l]^{g^{−1}} \ar@{^{(}->}[u]^{⊆}}

The mapping g̃^{−1} ∘ { \atop g ∘ f} : X → ℓ_{2} therefore extends f and satisfies

∥g̃^{−1} ∘ { \atop g ∘ f}∥_{Lip(α)} ⩽ ∥g̃^{−1}∥_{Lip} · ∥{ \atop g ∘ f}∥_{Lip(α)} ⩽^{(5)∧(6)} e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ∥g ∘ f∥_{Lip(α)}

⩽ e^{α}(ℓ_{∞}, ℓ_{2}^{m})∥g∥_{Lip}∥f∥_{Lip(α)} ⩽ 3e^{α}(ℓ_{∞}, ℓ_{2}^{m})∥f∥_{Lip(α)}, (7)

where the last step of (7) uses the right hand inequality in (4). Clearly (7) implies (3).

The link between Question 2 and Theorem 1 is twofold. Firstly, Question 2 presents another situation in which the linearization strategy of [JL84] for proving extension lower bounds seems to be insufficient, because bounded linear maps are Lipschitz rather than α-Hölder for α ∈ (0, 1). Nevertheless, in Section 4.2 we do show how to use a linearization procedure in the spirit of [JL84] to bound e^{α}(ℓ_{∞}, ℓ_{2}^{m}) from below. However, our approach requires a substantial modification of the argument of [JL84] and at present we do not see how it could yield a nontrivial result for the entire range α ∈ (1/2, 1] (the argument of Section 4.2 yields nontrivial bounds only when α ⩾ 1/\sqrt{2}). The second link between Question 2 and Theorem 1 is that the bounds that we obtain in Theorem 4 below are based on a modification of a construction of [JLS86] which is part of a general family of constructions that were used in related contexts also in [Lan99, CKR05], and to which the example that underlies Theorem 1 belongs as well. We elaborate further on this in Remark 19 below.

Here we obtain the best known lower bounds in the context of Question 2 and Question 3.

Theorem 4. For every α ∈ (1/2, 1] and every m, n ∈ ℕ we have

e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ≳ m^{\frac{2α−1}{4α}} + m^{α^{2}− \frac{1}{2}}  and  e_{n}^{α}(ℓ_{∞}, ℓ_{2}) ≳ (log n)^{\frac{2α−1}{4α}} + (\frac{log n}{log log n})^{α^{2}− \frac{1}{2}} . (8)

Importantly, the lower bounds in (8) tend to ∞ with n for every α ∈ (1/2, 1]. A positive answer to Question 2 (respectively, Question 3) for α = \frac{1}{2} +ε would yield the lower bound e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ≳ m^{ε} (respectively, e_{n}^{α}(ℓ_{∞}, ℓ_{2}) ≳ (log n)^{ε}), while Theorem 4 implies that

e^{\frac{1}{2} +ε}(ℓ_{∞}, ℓ_{2}^{m}) ≳ m^{ε−2ε^{2}}  and  e_{n}^{\frac{1}{2} +ε}(ℓ_{∞}, ℓ_{2}) ≳ (log n)^{ε−2ε^{2}},

i.e., the exponents of Theorem 4 match what Kalton’s conjecture predicts up to lower order terms as α → 1/2^{+}. The exponent α^{2} − 1/2 in the second summands in (8) becomes positive only when α ⩾ 1/\sqrt{2}, and it becomes greater than the exponent of the first summands in (8), namely (2α − 1)/(4α), only when α ∈ (α_{0}, 1], where α_{0} = 0.837... is the largest root of the polynomial 4x^{3} − 4x + 1. As α tends to 1 the exponent α^{2} − 1/2 tends to 1/2, so the bounds in (8) yield an alternative possible interpolation between Minty’s theorem and the nonlinear Hahn–Banach theorem. We do not believe that this interpolation is sharp and it seems more likely that Kalton’s conjecture, and correspondingly Question 2 and Question 3, have positive answers. It may very well be the case that the example that we analyse in Section 4.2 is itself an example that yields a positive answer to Question 2, but at present we do not know how to prove this.

1.2. A conjectural strengthening of Ball’s extension theorem. A longstanding open problem posed by Johnson and Lindenstrauss in [JL84, Problem 1] asks whether or not for every p ∈ (1, 2) and every m ∈ ℕ we have

e(ℓ_{p}, ℓ_{2}^{m}) ≲_{p} m^{\frac{1}{p} − \frac{1}{2}} .  (9)

Here, and in what follows, the notation A ≲_{p} B stands for A ⩽ C(p)B, where C(p) ∈ (0, ∞) is allowed to depend only on p. The notations A ≳_{p} B and A ≍_{p} B are defined analogously.

Johnson and Lindenstrauss were motivated to ask whether (9) holds true by a Lipschitz extension theorem of Marcus and Pisier [MP84], which states that for every p ∈ (1, 2) and n ∈ ℕ we have

e_{n}(ℓ_{p}, ℓ_{2}) ≲_{p} (log n)^{\frac{1}{p} − \frac{1}{2}} .  (10)

Specifically, the validity of (9) would yield a new proof of the Marcus–Pisier theorem (10) through an application of the Johnson–Lindenstrauss dimensionality reduction lemma (we recalled how such arguments are carried out in the proof of (3) above). Thus, the validity of (9) would yield an illuminating new perspective on the work of Marcus and Pisier [MP84], who proved that (10) holds true via an entirely different argument.

Our goal in this section is to formulate a conjecture that implies both Kalton’s conjecture on the validity of (2) and the Johnson–Lindenstrauss conjecture on the validity of (9), in addition to a wealth of yet unknown Lipschitz extension results. In order to do so, we need to quickly recall Ball’s work [Bal92] (itself addressing another open question that was posed by Johnson and Lindenstrauss in [JL84]) on the nonlinear version of Maurey’s extension theorem [Mau74].

For p, q ∈ [1, ∞], the Rademacher type p constant and Rademacher cotype q constant of a Banach space (X, ∥ · ∥_{X}), denoted T_{p}(X) and C_{q}(X), respectively, are defined to be the infima of those T, C ∈ [1, ∞] such that for every n ∈ ℕ and every x_{1}, …, x_{n} ∈ X we have

\frac{1}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{j=1}^{n} ε_{j}x_{j}∥_{X}^{p} ⩽ T^{p} ∑_{j=1}^{n} ∥x_{j}∥_{X}^{p}  and  ∑_{j=1}^{n} ∥x_{j}∥_{X}^{q} ⩽ \frac{C^{q}}{2^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{j=1}^{n} ε_{j}x_{j}∥_{X}^{q}.

Maurey’s extension theorem [Mau74] asserts that if (X, ∥·∥_{X}) and (Z, ∥·∥_{Z}) are Banach spaces and E ⊆ X is a linear subspace then for every linear operator U : E → Z there exists a linear operator V : X → Z that extends U and satisfies the operator norm bound ∥V ∥_{X→Z} ≲ T_{2}(X)C_{2}(Z)∥U∥_{E→Z}.

In [Bal92], Ball discovered a powerful nonlinear version of the Maurey extension theorem. In order to do so, he introduced notions of type and cotype for metric spaces that have since proven to be useful in several contexts beyond their original use for the Lipschitz extension problem. For p ∈ (0, ∞), the Markov type p constant of a metric space (X, d_{X}), denoted M_{p}(X), is defined to be the infimum over those M ∈ [1, ∞] such that for every n, t ∈ ℕ, every n × n symmetric stochastic matrix A = (a_{ij}), and every x_{1}, …, x_{n} ∈ X we have

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(x_{i}, x_{j})^{p} ⩽ tM^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}.

For q ∈ (0, ∞), the metric Markov cotype q constant of a metric space (X, d_{X}), denoted N_{p}(X), is defined to be the infimum over those N ∈ (0, ∞] such that for every n, t ∈ ℕ, every n×n symmetric stochastic matrix A = (a_{ij}), and every x_{1}, …, x_{n} ∈ X, there exist y_{1}, …, y_{n} ∈ X such that

∑_{i=1}^{n} d_{X}(x_{i}, y_{i})^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(y_{i}, y_{j})^{p} ⩽ N^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} \frac{1}{t} ∑_{s=1}^{t}(A^{s})_{ij}d_{X}(x_{i}, x_{j})^{p}.

Ball’s extension theorem [Bal92] asserts that for every metric space (X, d_{X}) and every Banach space (Z, ∥ · ∥_{Z}) we have

e(X, Z^{∗∗}) ≲ M_{2}(X)N_{2}(Z).

This formulation is not the strongest known version of Ball’s theorem, but it suffices for our purposes; see [MN13a] for a more complete discussion.

Remark 5. In the setting of Ball’s extension theorem one actually needs to know the Markov type of the complement of the subset from which one wishes to extend rather than the Markov type of the entire ambient space. Namely, we actually have

e(X, S, Z^{∗∗}) ≲ M_{2}(X ∖ S)N_{2}(Z).

This assertion holds true also for the more general version of Ball’s extension theorem that was obtained in [MN13a]. The above stronger statement follows effortlessly from an inspection of the proofs in [Bal92, MN13a], though it has never been stated in the literature; we believe that it is worthwhile to record it here for potential future applications.

A beautiful strengthening of Maurey’s extension theorem for finite-dimensional targets was discovered by König, Retherford and Tomczak-Jaegermann [KRTJ80], who proved that for every p ∈ [1, 2], q ∈ [2, ∞) and m ∈ ℕ, if (X, ∥ · ∥_{X}) and (Z, ∥ · ∥_{Z}) are Banach spaces with dim(Z) = m and E ⊆ X is a linear subspace, then for every linear operator U : E → Z there exists a linear operator V : X → Z that extends U and satisfies

∥V ∥_{X→Z} ≲_{p,q} T_{p}(X)C_{q}(Z)m^{\frac{1}{p} − \frac{1}{q}} ∥U∥_{E→Z}.  (11)

See also the expository article of Pisier [Pis79] for an elegant proof of (11). Important earlier special cases of the above result (other than Maurey’s extension theorem itself) can be found (via different proofs) in the works of Lewis [Lew78] and Figiel and Tomczak-Jaegermann [FTJ79].

In light of (11), we ask the following question.

Question 6. Suppose that 1 ⩽ p ⩽ q < ∞ and that (X, d_{X}) is a metric space with Markov type p, i.e., M_{p}(X) < ∞. Suppose also that m ∈ ℕ and that (Z, ∥ · ∥_{Z}) is an m-dimensional normed space. Is it true that there exists a constant K = K(M_{p}(X), N_{q}(Z), p, q) ∈ (0, ∞), which may depend only on the parameters M_{p}(X), N_{q}(Z), p, q, such that

e(X, Z) ⩽ Km^{\frac{1}{p} − \frac{1}{q}} ?

Since, by a straightforward application of the triangle inequality, every metric space (X, d_{X}) has Markov type 1 with M_{1}(X) = 1, for every α ∈ (0, 1] the Markov type 1/α constant of (X, d_{X}^{α}) equals 1. Also, by [Bal13, MN13a], for every q ∈ (1, ∞) we have N_{max\{q,2\}}(ℓ_{q}) ≲ \sqrt{q/(q − 1)}. Hence, a positive answer to Question 6 would imply that for every k ∈ ℕ we have

\frac{1}{max\{q, 2\}} ⩽ α ⩽ 1 ⟹ e^{α}(ℓ_{∞}, ℓ_{q}^{m}) ≲_{q} m^{α− \frac{1}{max\{q,2\}}} .  (12)

The case q = 2 of (12) is the same as (2), i.e., Kalton’s conjecture is a special case of Question 6. By [Bal92, NPSS06], for every p ∈ [1, ∞) we have M_{min\{p,2\}}(ℓ_{p}) ≲ \sqrt{p}. This implies formally (directly from the definition of Markov type) that for α ∈ (0, 1] the Markov type min{p, 2}/α constant of the metric space (ℓ_{p}, ∥x − y∥_{p}^{α}) is at most a constant multiple of p^{α/2}. Hence, a positive answer to Question 6 would also imply that for every p, q ∈ (1, ∞) and every k ∈ ℕ we have

\frac{min\{p, 2\}}{max\{q, 2\}} ⩽ α ⩽ 1 ⟹ e^{α}(ℓ_{p}, ℓ_{q}^{m}) ≲_{p,q} m^{\frac{α}{min\{p,2\}} − \frac{1}{max\{q,2\}}} .  (13)

The case p ∈ (1, 2), q = 2 and α = 1 of (13) is the same as (9), i.e., the above conjecture of Johnson and Lindenstrauss is a special case of Question 6. The validity of (13) would complement the fact that e^{α}(ℓ_{p}, ℓ_{q}) < ∞ for every α ∈ (0, min{p, 2}/ max{q, 2}], as shown in [Nao01, NPSS06].

At present we see several obstacles to adapting the proofs in [Bal92, MN13a] so as to incorporate the finite dimensionality of the target in order to answer Question 6. We therefore leave Question 6 as an intriguing direction for future research, itself part of the Ribe program (see [Bal13, Nao12]).

1.3. Lipschitz extension between ℓ_{p} spaces. Theorem 1 yields the best known lower bound on 𝔞𝔢(n) as n → ∞, but there are several cases of special interest where the best known lower bound on e_{n}(X, Z) is o(\sqrt{log n}). Here we recall the best known bounds when X = ℓ_{p} and Y = ℓ_{q} for p, q ∈ [1, ∞], as a survey of very basic questions on Lipschitz extension that remain open.

The case of Hilbert space-valued functions was famously studied by Johnson and Lindenstrauss in [JL84], answering a question posed by Marcus and Pisier in [MP84]. The bounds on e_{n}(ℓ_{∞}, ℓ_{2}) that were obtained in [JL84] are as follows, and they remain the best known bounds to date.

\sqrt{log n} ; \sqrt{log log n} ≲ e_{n}(ℓ_{∞}, ℓ_{2}) ≲ \sqrt{log n}.  (14)

In the special case of Hilbert space-valued functions defined on finite subsets of ℓ_{p} for p ∈ (1, 2), the best known bounds are

(\frac{log n}{log log n})^{\frac{1}{p} − \frac{1}{2}} ≲ e_{n}(ℓ_{p}, ℓ_{2}) ≲_{p} (log n)^{\frac{1}{p} − \frac{1}{2}} .  (15)

The right hand inequality in (15) is due to [MP84] and the left hand inequality in (15) is due to [JL84], where it is shown to hold for every p ∈ [1, 2].

As shown by Makarychev and Makarychev in [MM10], the parameters e_{n}(ℓ_{∞}, ℓ_{1}) and e_{n}(ℓ_{1}, ℓ_{1}) have a special algorithmic significance. The best known bounds for these quantities are

\sqrt{log n} ; \sqrt{log log n} ≲ e_{n}(ℓ_{∞}, ℓ_{1}) ≲ \frac{log n}{log log n},  (16)

and

\frac{\sqrt{log n}}{log log n} ≲ e_{n}(ℓ_{1}, ℓ_{1}) ≲ \frac{log n}{log log n}.  (17)

The right hand inequalities in (16) and (17) are a special case of the general upper bound of [LN05]. The left hand inequalities in (16) and (17) appear in [MM10], with the left hand inequality of (17) being based on the work of Figiel, Johnson and Schechtman [FJS88] (an asymptotically weaker lower bound in (17) follows from earlier work of Bourgain [Bou81]).

By Ball’s extension theorem [Bal92], combined with the fact [NPSS06] that ℓ_{p} has Markov type 2 when p ∈ [2, ∞), if 1 < q ⩽ 2 ⩽ p < ∞ then e(ℓ_{p}, ℓ_{q}) ⩽ C(p, q) for some C(p, q) ∈ (0, ∞). Here the asymptotic dependence of C(p, q) as p → ∞ or q → 1 remains unknown. In particular, a famous and longstanding open question of Ball [Bal92] asks whether e(ℓ_{2}, ℓ_{1}) is finite or infinite. The best known bounds on e_{n}(ℓ_{p}, ℓ_{q}) for the remaining values of p, q ∈ [1, ∞] are as follows.

p, q ∈ [1, 2] and q ≠ 1 ⟹ (\frac{log n}{log log n})^{\frac{1}{p} − \frac{1}{2}} ≲_{q} e_{n}(ℓ_{p}, ℓ_{q}) ≲_{p} (log n)^{\frac{1}{p}} ,  (18)

1 ⩽ p ⩽ 2 ⟹ \frac{(log n)^{\frac{1}{p} − \frac{1}{2}}}{(log log n)^{\frac{1}{p}}} ≲ e_{n}(ℓ_{p}, ℓ_{1}) ≲_{p} (log n)^{\frac{1}{p}} .  (19)

p, q ∈ (2, ∞) ⟹ (\frac{log n}{log log n})^{\frac{q−2}{q^{2}}} ≲ e_{n}(ℓ_{p}, ℓ_{q}) ≲ \frac{log n}{log log n},  (20)

1 ⩽ p ⩽ 2 ⩽ q < ∞ ⟹ (\frac{log n}{log log n})^{max\{ \frac{1}{p} − \frac{1}{2} , \frac{q−p}{q^{2}} \}} ≲_{q} e_{n}(ℓ_{p}, ℓ_{q}) ≲_{p} (log n)^{\frac{1}{p}} .  (21)

The right hand inequalities in (18), (19), (21) are due to [LN05]. More generally, it was shown in [LN05] that for p ∈ (1, 2] we have e_{n}(ℓ_{p}, Z) ≲_{p} (log n)^{1/p} for every Banach space Z. It would be interesting to determine the best exponent of log n in this context of general Banach space targets, as well as when the target Z is allowed to range over some special classes of Banach spaces (e.g., for Banach spaces of cotype 2 it is known [MN13a] that this exponent cannot be smaller than 1/4).

No upper bound on e_{n}(ℓ_{p}, ℓ_{q}) that is asymptotically smaller than the general upper bound [LN05] of O((log n)/ log log n) is known when p, q ∈ (2, ∞), and similarly for e_{n}(ℓ_{1}, ℓ_{q}) for q ∈ (2, ∞).

Let (Z, ∥ · ∥_{Z}) be a Banach space that has Rademacher type p for some p > 1. By a theorem of Figiel and Tomczak-Jaegermann [FTJ79] there exists K(Z) ∈ (0, ∞) such that for every n ∈ ℕ one can find an n-dimensional subspace Z_{n} of Z that is 2-isomorphic to ℓ_{2}^{n} and there exists a projection from Z onto Z_{n} of norm at most K(Z). This implies that for any metric space X we have e_{n}(X, Z) ≳_{Z} e_{n}(X, ℓ_{2}). In particular, e_{n}(Z, ℓ_{q}) ≳_{q} e_{n}(X, ℓ_{2}) for every q > 1. This implies the validity of the left hand inequality in (18), as a consequence of the left hand inequality of (15). However, this reasoning does not apply when the target space is ℓ_{1}, i.e., in order to prove the left hand inequality in (19). For this purpose, one argues by adapting the proof of the left hand inequality in (17) that appears in [MM10] (the key tool being [FJS88]); the adaptation of this argument is simple and we omit it (the result itself, however, is far from trivial).

If (X, ∥ · ∥_{X}) is an infinite dimensional Banach space then, by Dvoretzky’s theorem [Dvo61], X contains a 2-isomorphic copy of ℓ_{2}^{n} for every n ∈ ℕ. Consequently, e_{n}(X, Z) ≳ e_{n}(ℓ_{2}, Z) for every metric space Z. In particular, the left hand inequality in (20) follows from the special case p = 2 of the left hand inequality in (21). The latter inequality consists of two lower bounds, one with the exponent 1/p − 1/2 and the other with the exponent (q − p)/q^{2}. Since, as explained in the previous paragraph, e_{n}(ℓ_{p}, ℓ_{q}) ≳_{q} e_{n}(ℓ_{p}, ℓ_{2}), the lower bound with exponent 1/p − 1/2 follows from the left hand inequality in (15). The lower bound with exponent (q − p)/q^{2} is due to [Nao01], with the explicit asymptotic dependence being computed when p = 2 in [LN05, Lemma 1.13], and when p ∈ (1, 2) the corresponding bound follows mutatis mutandis by the same argument.

It is worthwhile to point out here an interesting feature of the left hand inequality in (21). Suppose that p ∈ [1, 2]. For every n-dimensional subspace Y of ℓ_{p} there exists a projection from ℓ_{p} onto Y of norm at most c_{p}n^{1/p−1/2}. This assertion follows from the work of Lewis [Lew78], and it is also a consequence (11). Thus, for every Banach space Z, every linear operator U : Y → Z can be extended to a linear operator V : ℓ_{p} → Z with ∥V ∥_{ℓ_{p}→Z} ≲_{p} n^{1/p−1/2}∥U∥_{Y →Z}. Consequently, the linearization method of Johnson and Lindenstrauss [JL84] cannot yield a lower bound on e_{n}(ℓ_{p}, Z) that is at least a constant multiple of (log n)^{1/p−1/2}. However, (q − p)/q^{2} > 1/p − 1/2 if and only if

\frac{3}{2} < p ⩽ 2  and  2 + \frac{(1 − \sqrt{2p − 3})^{2}}{1 + \sqrt{2p − 3}} < q < 2 + \frac{(1 − \sqrt{2p − 3})^{3}}{2(2 − p)} .  (22)

So, if p, q satisfy (22) then the left hand inequality in (21) shows that

lim_{n→∞} \frac{e_{n}(ℓ_{p}, ℓ_{q})}{(log n)^{\frac{1}{p} − \frac{1}{2}}} = ∞,  (23)

i.e., we have a lower bound on e_{n}(ℓ_{p}, ℓ_{q}) that is asymptotically larger than any bound that can be deduced by reducing the problem to the extension problem for linear operators. We conjecture that the restrictions in (22) are not needed here, i.e., (23) holds true whenever 1 ⩽ p ⩽ 2 < q < ∞. It even seems to be unknown whether for every p ∈ [1, 2] there exists a Banach space Z for which

lim_{n→∞} \frac{e_{n}(ℓ_{p}, Z)}{(log n)^{\frac{1}{p} − \frac{1}{2}}} = ∞.  (24)

The best-known result towards (24) seems to follow from [MN13a], where it is shown that there exists a Banach space Z for which e_{n}(ℓ_{2}, Z) ≳ \sqrt[4]{(log n)/ log log n}. Hence, by Dvoretzky’s theorem [Dvo61], for every infinite dimensional Banach space X we have e_{n}(X, Z) ≳ \sqrt[4]{(log n)/ log log n}, implying that (24) holds true if p ∈ [1, 2] satisfies 1/p − 1/2 < 1/4, i.e., for every p ∈ (4/3, 2].

2. Algorithmic clustering

An algorithmic optimization problem called 0-Extension, which we describe below, served as inspiration for our proof of Theorem 1. In this section we shall survey this background so as to clarify the context and explain the “twist” over the existing approaches to 0-Extension that we introduce in order to prove Theorem 1. We stress, however, that our present work does not have new algorithmic implications, and the sole purpose of this section is to explain how this context motivated our approach to Theorem 1. Those who are interested only in the proof of Theorem 1 can skip this section on first reading: the proof itself appears in Section 3 below and is entirely self-contained, with none of the algorithmic background that we describe here being used.

In what follows, the vertices of a combinatorial graph G are denoted V_{G} and its edges are denoted E_{G}. The 0-Extension problem is a clustering framework for finite graphs that was introduced by Karzanov [Kar98]. The input of the 0-Extension problem is a graph G with edge weights w : E_{G} → [0, ∞), and a subset T ⊆ V_{G} equipped with a metric d_{T} : T × T → [0, ∞). The subset T is called in the literature the set of terminals. The output of the 0-Extension problem is a partition of V_{G} into |T | subsets {C_{x} ⊆ V_{G}}_{x∈T} with the requirement that x ∈ C_{x} for every x ∈ T. The cost of this partition is defined as follows. Every edge {u, v} ∈ E_{G} with |{u, v} ∩ C_{x}| = |{u, v} ∩ C_{y}| = 1 for some distinct x, y ∈ T contributes its weight w(u, v) times d_{T} (x, y) to the total cost, and all other edges (i.e., edges that are entirely within one cluster C_{x} for some x ∈ T) do not contribute to the total cost. The goal is to find efficiently (in polynomial time) such a partition with minimum cost, or with cost that is guaranteed to be close to the minimum possible cost. Formally, define

COST_{(G,w,d_{T})} (\{C_{x}\}_{x∈T}) =^{def} ∑_{\begin{matrix}x,y∈T \\ x≠y \end{matrix}} ∑_{\begin{matrix}\{u,v\}∈E_{G} \\ |\{u,v\}∩C_{x}|=|\{u,v\}∩C_{y}|=1 \end{matrix}} w(u, v)d_{T} (x, y),

and

OPT(G, w, d_{T}) =^{def} min_{{C_{x}}_{x∈T} partition of V_{G} ∀ x∈T, x∈C_{x}} COST_{(G,w,d_{T})} ({C_{x}}_{x∈T}) .  (25)

The goal is to find efficiently a partition {C_{x}}_{x∈T} of V_{G} with x ∈ C_{x} for every x ∈ T such that

\frac{COST_{(G,w,d_{T})} (\{C_{x}\}_{x∈T})}{OPT(G, w, d_{T})}

is guaranteed to be at most a (hopefully small) value α ∈ [1, ∞).

Obtaining α = 1 here would imply that P = NP, since in the special when w(u, v) = 1 and d_{T} (x, y) = 1 for every {u, v} ∈ E_{G} and every distinct x, y ∈ T, the quantity COST_{(G,w,d_{T})} ({C_{x}}_{x∈T}) is nothing more than the total number of edges that are incident to distinct elements of the partition {C_{x}}_{x∈T}. Computing the minimum cost in this special case is the MULTIWAY CUT problem, and it was shown in [DJP^{+}94] that if P ≠ NP then there exists α_{0} > 1 such that no polynomialtime algorithm outputs a partition whose cost is guaranteed to be less than α_{0} times the minimum possible cost. For the 0-Extension problem in its full generality, it was shown in [KKMR09] that for every ε ∈ (0, 1) there exists C(ε) ∈ (0, ∞) such that the existence of a polynomial-time algorithm for 0-Extension whose approximation factor on instances of size n is α ⩽ (log n)^{1/4−ε} would imply that any problem in NP of size n could be solved in time exp((log n)^{C(ε)}).

Due to the above evidence for the nonexistence of a constant-factor approximation algorithm for 0-Extension, the literature has focused on the design of approximation algorithms with potentially unbounded approximation factor, based on two competing continuous relaxations of the discrete optimization problem. The first is the metric relaxation, which was formulated in [Kar98] and studied extensively in [CKR05]. Given an instance of 0-Extension, i.e., an n-vertex graph G, a metric d_{T} : T × T → [0, ∞) on a subset T ⊆ V_{G}, and edge weights w : E_{G} → [0, ∞), define

MET(G, w, d_{T}) =^{def} min_{d:V_{G}×V_{G}→[0,∞) d|_{T} =d_{T} d is a semi−metric} ∑_{{u,v}∈E_{G}} w(u, v)d(u, v).  (26)

The minimization in the right hand side of (26) amounts to a linear program because the constraint that d : V_{G} × V_{G} → [0, ∞) is a semi-metric that extends d_{T} corresponds to O(n^{3}) linear inequalities in the variables {d(u, v)}_{u,v∈V_{G}}. Therefore MET(G, w, d_{T}) can be computed in polynomial time.

A second relaxation for the 0-Extension problem, called the earthmover relaxation, was proposed in [CKNZ05] and studied extensively in [AFH^{+}04, KKMR09]. The idea is similar to (26), except that the semi-metric d : V_{G}×V_{G} → [0, ∞) is further restricted to a special class of semi-metrics, over which the corresponding minimization can still be cast as a linear program. Given two measures μ, ν on T with the same total mass, i.e., μ(T) = ν(T), let Π(μ, ν) be the set of all couplings of μ and ν. Thus, Π(μ, ν) consists of all the measures π on T × T such that ∑_{y∈T} π(x, y) = μ(x) and ∑_{y∈T} π(y, x) = ν(x) for every x ∈ T. The assumption that μ and ν have the same total mass ensures that Π(μ, ν) ≠ ∅; specifically (μ × ν)/μ(T) ∈ Π(μ, ν). The Wasserstein 1 distance between μ and ν (also known as the earthmover distance between μ and ν) is defined to be

W_{1}^{d_{T}} (μ, ν) =^{def} min_{π∈Π(μ,ν)} ∑_{x,y∈T} d_{T} (x, y)π(x, y).  (27)

Let 𝒫_{T} denote the set of all probability measures on T and define

EMD(G, w, d_{T}) =^{def} min_{\begin{matrix}\{μ_{u}\}_{u∈V_{G}}⊆𝒫_{T} \\ ∀ x∈T, μ_{x}=δ_{x} \end{matrix}} ∑_{\{u,v\}∈E_{G}} w(u, v)W_{1}^{d_{T}} (μ_{u}, μ_{v}).  (28)

Here for x ∈ T the point mass at x is denoted δ_{x}. The minimization in the right hand side of (28) also amounts to a linear program, with variables corresponding to couplings π_{uv} of the probability measures μ_{u} and μ_{v} for each {u, v} ∈ E_{G}, and objective ∑_{{u,v}∈E_{G}} ∑_{x,y∈T} w(u, v)d_{T} (x, y)π_{uv}(x, y); the requirements of being a probability measure or a coupling are clearly linear constraints. The quantity EMD(G, w, d_{T}) can therefore be computed in polynomial time.

If {μ_{u}}_{u∈V_{G}} ⊆ 𝒫_{T} are such that μ_{x} = δ_{x} for every x ∈ T then d(u, v) = W_{1}^{d_{T}} (μ_{u}, μ_{v}) is a semimetric on V_{G} that extends d_{T}. Consequently, the minimization in (28) is over a smaller set than the minimization in (26). At the same time, if {C_{x}}_{x∈T} is a partition of V_{G} with x ∈ C_{x} for every x ∈ T, then by defining μ_{u} = δ_{x} for every (u, x) ∈ V_{G} × T we see that the minimization in (25) is over a smaller set than the minimization in (28). These observations show that every instance of 0-Extension satisfies

MET(G, w, d_{T}) ⩽ EMD(G, w, d_{T}) ⩽ OPT(G, w, d_{T}).  (29)

Building on ideas of [CKR05], it was shown in [FHRT03] that every instance of 0-Extension satisfies OPT(G, w, d_{T})/MET(G, w, d_{T}) ≲ (log |T |)/ log log |T |. This yields the best known approximation algorithm for the 0-Extension problem, the algorithm being to compute the quantity MET(G, w, d_{T}), i.e., to apply the metric relaxation. It follows from (29) that by using the earthmover relaxation, i.e., by computing EMD(G, w, d_{T}), one could potentially obtain an even better algorithm. This was realized in [AFH^{+}04] in special cases (e.g. when (T, d_{T}) is a planar graph), but in [LN03] it was shown that the same approximation guarantees as in [AFH^{+}04] can be obtained by using the metric relaxation. Nevertheless, in [KKMR09] it was shown that in a certain sense the earthmover relaxation of 0-Extension does perform better than the metric relaxation: the earthmover relaxation behaves better than the metric relaxation if one measures the approximation factor in term of the ratio between the largest distance and the smallest nonzero distance in (T, d_{T}).

On the negative side, it was shown in [CKR05] that there exist instances of 0-Extension with |T | arbitrarily large and OPT(G, w, d_{T})/MET(G, w, d_{T}) ≳ \sqrt{log |T |}. More recently, in [KKMR09] it was shown that there also exist such instances with OPT(G, w, d_{T})/EMD(G, w, d_{T}) ≳ \sqrt{log |T |}.

As described above, the earthmover relaxation of 0-Extension is in principle better than the metric relaxation, but at present the general bounds that are available in the literature are to a large extent the same for both relaxations. Nevertheless, our approach to Theorem 1 is based on exploiting the differences between the metric relaxation and the earthmover relaxation. The idea is that if an instance of 0-Extension behaves significantly worse for the metric relaxation than for the earthmover relaxation then the terminal metric (T, d_{T}) can be embedded isometrically into a larger semi-metric (V_{G}, d) for which ∑_{{u,v}∈E_{G}} w(u, v)d(u, v) is much smaller than OPT(G, w, d_{T}), yet whenever one assigns to every vertex u ∈ V_{G} a probability measure μ_{u} ∈ 𝒫_{T} such that μ_{x} = δ_{x} for every x ∈ T, then ∑_{{u,v}∈E_{G}} w(u, v)W_{1}^{d_{T}} (μ_{u}, μ_{v}) must be close to OPT(G, w, d_{T}). This discrepancy between the two relaxations can be used to show that the mapping that assigns to every x ∈ T the point mass δ_{x} ∈ 𝒫_{T} cannot be extended to a function from (V_{G}, d) to (𝒫_{T} , W_{1}^{d_{T}}) that has a small Lipschitz constant. Here the target space (𝒫_{T} , W_{1}^{d_{T}}) is not a normed space, but this idea can be modified so as to yield a poorly extendable function with values in a related normed space, namely the dual of the space of real-valued Lipschitz functions on (T, d_{T}) that vanish at a fixed point. In the end, the entire argument as presented in Section 3 uses geometric and combinatorial considerations that are self-contained and do not make any reference to the clustering objective OPT(G, w, d_{T}). The examples of metric spaces that we use to prove Theorem 1 are modifications of the examples that were considered in [CKR05], which are themselves in the spirit of an example that was used in [JLS86] (and, we use yet another variant of the example of [JLS86] to prove Theorem 4).

3. Proof of Theorem 1

Before passing to the proof of Theorem 1, which appears in Section 3.4 below, we need to recall some (simple) background and to introduce some basic constructions.

3.1. The r-magnification of a metric space. Given a metric space (X, d_{X}) and r > 0, for every subset S ⊆ X we shall define a new metric space X_{r}(S) that we call the r-magnification of (X, d_{X}) at S. As a set, X_{r}(S) equals X. The new metric d_{X_{r}(S)} on X is defined by setting d_{X_{r}(S)}(x, x) = 0 for every x ∈ X, and by defining for every distinct x, y ∈ X,

d_{X_{r}(S)}(x, y) =^{def} d_{X}(x, y) + r|{x, y} ∩ S|.  (30)

It is immediate to check that d_{X_{r}(S)} is indeed a metric on S. Note that this construction increases all the positive pairwise distances within S while keeping the pairwise distances within X ∖ S unchanged. This is the reason for our choice of terminology. If G is a connected graph then d_{G} will always stand for the shortest-path metric on V_{G}, and for S ⊆ V_{G} and r > 0, the metric space G_{r}(S) will always be understood to be the r-magnification of (V_{G}, d_{G}) at S.

The relevance of the r-magnification of (X, d_{X}) at S ⊆ X to potentially proving impossibility results for Lipschitz extension is simple to explain. By making the positive pairwise distances within S larger, we make it easier for functions that are defined on S to be Lipschitz, so there are more “potential counterexamples” on (S, d_{X_{r}(S)}) than there were on (S, d_{X}). At the same time, by keeping the pairwise distances within X ∖ S unchanged, we do not make the Lipschitz condition on V ∖ S any less stringent. However, there is a limitation to this reasoning because as r becomes larger the minimum positive distance in (S, d_{X_{r}(S)}) becomes closer to the diameter of (S, d_{X_{r}(S)}), in which case bounds on 𝔞𝔢(ε) become relevant. Indeed, by (30) any distinct x, y ∈ S satisfy

d_{X_{r}(S)}(x, y) ⩾ 2r + 1 = \frac{2r + 1}{2r + diam(S, d_{X})}diam(S, d_{X_{r}(S)}).  (31)

Since 𝔞𝔢(ε) ≲ 1/ε, it follows that any 1-Lipschitz function from (S, d_{X_{r}(S)}) to any Banach space can be extended to a function defined on (X, d_{X_{r}(S)}) whose Lipschitz constant is at most a constant multiple of (2r + diam(S, d_{X}))/(2r + 1) ⩽ 1 + diam(S, d_{X})/r. There is therefore a tradeoff that limits how large r could be if one wishes to use the r-magnification for the purpose of obtaining a lower bound on 𝔞𝔢(n). Below we shall balance these constraints, for an appropriate choice of an initial metric space (X, d_{X}), so as to yield Theorem 1.

3.2. The Wasserstein 1 norm. For a finite set X we denote (as usual) by ℝ^{X} the |X|-dimensional vector space of all f : X → ℝ. We also denote by ℝ_{0}^{X} the subspace of ℝ^{X} consisting of those f : X → ℝ that satisfy ∑_{x∈X} f(x) = 0. The standard basis of ℝ^{X} will be denoted by {e_{x}}_{x∈X}, i.e., e_{x}(y) = 1_{{x=y}} for every x, y ∈ X. For f ∈ ℝ^{X} we shall use the (standard) notation

∥f∥_{ℓ_{1}(X)} =^{def} ∑_{x∈X} |f(x)|.

If (X, d_{X}) is a finite metric space then let K_{(X,d_{X})} ⊆ ℝ_{0}^{X} be the the following convex hull.

K_{(X,d_{X})} =^{def} conv \{\frac{e_{x} − e_{y}}{d_{X}(x, y)} : x, y ∈ X and x ≠ y\} .  (32)

K_{(X,d_{X})} is clearly an origin-symmetric convex body, so it is a unit ball of a norm on ℝ_{0}^{X}, called the Wasserstein 1 norm induced by X, which we denote by ∥·∥_{W_{1}(X,d_{X})}. By the Kantorovich–Rubinstein duality theorem (see [Vil03, Thm. 1.14]), denoting as usual f^{+} = max{f, 0} and f^{−} = max{−f, 0} for every f ∈ ℝ^{X}, and recalling (27), we have

∀ f ∈ ℝ_{0}^{X},  ∥f∥_{W_{1}(X,d_{X})} = W_{1}^{d_{X}} (f^{+}, f^{−}) = inf_{π∈Π(f^{+},f^{−})} ∑_{x,y∈X} d_{X}(x, y)π(x, y).  (33)

Observe that this makes sense because the assumption f ∈ ℝ_{0}^{X}, i.e., that ∑_{x∈X} f(x) = 0, implies that the nonnegative functions f^{+} and f^{−} satisfy, ∑_{x∈X} f^{+}(x) = ∑_{x∈X} f^{−}(x). So, f^{+} and f^{−} are nonnegative measures with the same total mass.

We record for future use the following very simple lemma.

Lemma 7. Let (X, d_{X}) be a finite metric space. Then ∥e_{x} − e_{y}∥_{W_{1}(X,d_{X})} = d_{X}(x, y) for every x, y ∈ X and

∀ f ∈ ℝ_{0}^{X},  \frac{1}{2} min_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} d_{X}(x, y)∥f∥_{ℓ_{1}(X)} ⩽ ∥f∥_{W_{1}(X,d_{X})} ⩽ \frac{1}{2}diam(X)∥f∥_{ℓ_{1}(X)}.  (34)

In particular, for every r > 0 and S ⊆ X we have

∀ f ∈ ℝ_{0}^{S},  r∥f∥_{ℓ_{1}(S)} ⩽ ∥f∥_{W_{1}(S,d_{Xr(S)})} ⩽ (r + \frac{diam(X)}{2}) ∥f∥_{ℓ_{1}(S)}.  (35)

Proof. The fact that ∥e_{x}−e_{y}∥_{W_{1}(X,d_{X})} = d_{X}(x, y) for every distinct x, y ∈ X is immediate from (33), and also directly from (32), which says that (e_{x} − e_{y})/d_{X}(x, y) has unit norm in W_{1}(X, d_{X}). To prove (34), denote by m the minimum nonzero value that d_{X} attains. For distinct x, y ∈ X,

max_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} ∥\frac{e_{x} − e_{y}}{d_{X}(x, y)}∥_{ℓ_{1}(X)} ⩽ max_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} \frac{∥e_{x} − e_{y}∥_{ℓ_{1}(X)}}{m} = \frac{2}{m}.

This means that for every distinct x, y ∈ X we have (e_{x}−e_{y})/d_{X}(x, y) ∈ (2/m)B_{ℓ_{1}(X)}, where B_{ℓ_{1}(X)} is the unit ball of ℓ_{1}(X). By (32) we therefore have K_{(X,d_{X})} ⊆ (2/m)B_{ℓ_{1}(X)}, which is the same as the first inequality in (34). The second inequality in (34) follows directly from (33), noting that the sum in the right hand side of (33) is at most diam(X) ∑_{x∈X} f^{+}(x) = diam(X)∥f∥_{ℓ_{1}(X)}/2. The estimate (35) is a special case of (34) because by (30) the minimum nonzero distance within S of the r-magnification of X at S is at least 2r, and the diameter of X_{r}(S) is at most 2r+diam(X). □

3.3. Properties of expanders. In the proof of Theorem 1 we shall use several properties of graphs in general, and expander graphs in particular. Here we collect these facts for ease of later reference. Fix two integers n, d ⩾ 3 and let G be a connected n-vertex d-regular graph. Recall that the shortest-path metric that G induces on V_{G} is denoted d_{G}. The following estimate is standard.

∀ ∅ ≠ S ⊆ V_{G},  \frac{1}{|S|^{2}} ∑_{x,y∈S} d_{G}(x, y) ⩾ \frac{log |S|}{4 log d}.  (36)

To quickly verify the validity of (36), observe that since the smallest nonzero distance in G is at least 1, the average that appears in the left hand side of (36) is always at least |S|(|S|−1)/|S|^{2} = 1−1/|S|. One checks directly that 1 − 1/a ⩾ (log a)/(4 log 3) for every a ∈ {1, …, 15}, so in order to establish (36) we may assume that |S| ⩾ 16. Denote k = 1 + ⌊log_{d}(|S|/4)⌋ and observe that for every x ∈ V_{G} the number of y ∈ V_{G} with d_{G}(x, y) ⩽ k−1 is at most 1+d+…+d^{k−1} ⩽ 2d^{k−1} ⩽ |S|/2. The average that appears in the left hand side of (36) is therefore at least k/2, and it remains to note that k ⩾ log_{d}(|S|/4) ⩾ (log |S|)/(2 log d), since |S| ⩾ 16.

Fixing S ⊆ V_{G} and r > 0, we shall need later the following straightforward evaluation of the average length of edges of G in the r-magnification of (G, d_{G}) at S.

\frac{1}{|E_{G}|} ∑_{\{x,y\}∈E_{G}} d_{G_{r}(S)}(x, y) = 1 + \frac{2r|S|}{n}.  (37)

Indeed, let E_{1} be those edges in E_{G} that are contained in S and let E_{2} be those edges in E_{G} that contain exactly one element of S. Because G is d-regular, we have 2|E_{1}| + |E_{2}| = d|S|.

Recalling (30), for every {x, y} ∈ E_{1} we have d_{G_{r}(S)}(x, y) = 2r + 1, for every {x, y} ∈ E_{2} we have d_{G_{r}(S)}(x, y) = r + 1, and for every {x, y} ∈ E_{G} ∖ (E_{1} ∪ E_{2}) we have d_{G_{r}(S)}(x, y) = 1. Consequently,

\frac{1}{|E_{G}|} ∑_{(x,y)∈E_{G}} d_{G_{r}(S)}(x, y) = \frac{(|E_{G}| − |E_{1}| − |E_{2}|) + (2r + 1)|E_{1}| + (r + 1)|E_{2}|}{|E_{G}|}

= 1 + \frac{r(2|E_{1}| + |E_{2}|)}{dn/2} = 1 + \frac{2r|S|}{n}.

Given two disjoint subsets S, T ⊆ V_{G}, denote the number of edges in E_{G} that intersect both S and T by E_{G}(S, T). The edge-expansion of G, denoted ϕ(G), is the largest ϕ ∈ [0, ∞) such that

∀ S ⊆ V_{G},  E_{G}(S, V_{G} ∖ S) ⩾ ϕ\frac{|S|(n − |S|)}{n^{2}}|E_{G}|.  (38)

It is well known that (38) is equivalent to the assertion that every h : V_{G} → ℓ_{1} satisfies.

\frac{ϕ}{n^{2}} ∑_{x,y∈V_{G}} ∥h(x) − h(y)∥_{1} ⩽ \frac{1}{|E_{G}|} ∑_{\{x,y\}∈E_{G}} ∥h(x) − h(y)∥_{1}.  (39)

The equivalence of (38) and (39) is a standard application of the cut-cone decomposition of subsets of ℓ_{1}; see e.g. inequality (4) in [Mat97] or [NRS05, Fact 2.1]. The following simple combination of (39) and Lemma 7 will be used later.

Lemma 8. Fix n ∈ ℕ and ϕ ∈ (0, 1]. Suppose that G be an n-vertex graph with ϕ(G) ⩾ ϕ. For every ∅ ≠ S ⊆ V_{G} and r > 0, every F : V_{G} → ℝ_{0}^{S} satisfies

\frac{1}{n^{2}} ∑_{x,y∈V_{G}} ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} ⩽ \frac{2r + diam(S, d_{G})}{(2r + 1)ϕ} · \frac{1}{|E_{G}|} ∑_{\{x,y\}∈E_{G}} ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} .

Proof. By (39) we have

\frac{1}{n^{2}} ∑_{x,y∈V_{G}} ∥F (x) − F (y)∥_{ℓ_{1}(S)} ⩽ \frac{1}{ϕ|E_{G}|} ∑_{\{x,y\}∈E_{G}} ∥F (x) − F (y)∥_{ℓ_{1}(S)}  (40)

Recalling (30), we have diam(S, d_{G_{r}(S)}) = 2r + diam(S, d_{G}) and the smallest positive distance in (S, d_{G_{r}(S)}) equals 2r + 1. So, by Lemma 7, every x, y ∈ V_{G} satisfy

\frac{2r + 1}{2} ∥F (x) − F (y)∥_{ℓ_{1}(S)} ⩽ ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} ⩽ \frac{2r + diam(S, d_{G})}{2} ∥F (x) − F (y)∥_{ℓ_{1}(S)} .

Lemma 8 now follows by substituting these estimates for pairwise distances into (40). □

We end by recording for future use the following direct consequence of Menger’s theorem [Men27].

Lemma 9. Let G be an n-vertex graph and A, B ⊆ V_{G} satisfy A ∩ B = ∅. Fix ϕ ∈ (0, ∞) and suppose that ϕ(G) ⩾ ϕ. Then the number of edge-disjoint paths joining A and B is at least ϕ min{|A|, |B|}|E_{G}|/(2n). In other words, there exists an integer m ⩾ ϕ min{|A|, |B|}|E_{G}|/(2n), k_{1}, …, k_{m} ∈ ℕ and {u_{i,1}, u_{i,2}, …, u_{i,k_{i}}}_{i=1}^{m} ⊆ V_{G} such that {u_{i,1}}_{i=1}^{m} ⊆ A, {u_{i,k_{i}}}_{i=1}^{m} ⊆ B. Moreover, {u_{i,s}, u_{i,s+1}} ∈ E_{G} for every i ∈ {1, …, m} and s ∈ {1, …, k_{i} − 1}, and if for some i, j ∈ {1, …, m}, s ∈ {1, …, k_{i} − 1} and t ∈ {1, …, k_{j} − 1} we have {u_{i,s}, u_{i,s+1}} = {u_{j,t}, u_{j,t+1}} then necessarily i = j and s = t.

Proof. Let m be the maximal number of edge-disjoint paths joining A and B. By the classical Menger theorem [Men27] (see also e.g. [Die10, Chapter 3]) there exists a subset of edges E^{∗} ⊆ E_{G} with |E^{∗}| = m such that every path in G that joins a vertex in A with a vertex in B contains an edge from E^{∗}. Since in the graph G^{∗} = (V_{G}, E_{G} ∖ E^{∗}) there is no path that joins an element of A with an element of B, if we let C ⊆ V_{G} be the union of all the connected components of G^{∗} that contain an element of A then C ⊇ A and C ∩ B = ∅. Since C is a union of connected components of G^{∗}, all the edges of E_{G} joining C and V_{G} ∖ C belong to E^{∗}. Hence, E_{G}(C, V_{G} ∖ C) ⩽ |E^{∗}| = m. It remains to note that by (38) we have

m ⩾ E_{G}(C, V_{G} ∖ C) ⩾ ϕ\frac{max\{|C|, n − |C|\} · min\{|C|, n − |C|\}}{n^{2}}|E_{G}| ⩾ \frac{ϕ min\{|A|, |B|\}|E_{G}|}{2n}, (41)

where the last step of (41) holds true because clearly max{|C|, n − |C|} ⩾ n/2, and since C ⊇ A and V_{G} ∖ C ⊇ B we have min{|C|, n − |C|} ⩾ min{|A|, |B|}. □

3.4. A Wasserstein-valued poorly extendable function. Fix d, n ∈ ℕ and ϕ ∈ (0, 1). Throughout this section, G will be fixed to be an n-vertex d-regular graph with ϕ(G) ⩾ ϕ. We shall also fix ∅ ≠ S ⊆ V_{G} and r > 0. Define a mapping

f : (S, d_{G_{r}(S)}) → (ℝ_{0}^{S}, ∥ · ∥_{W_{1}(S,d_{Gr(S)})})

by

∀ x ∈ S,  f(x) =^{def} e_{x} − \frac{1}{|S|} ∑_{z∈S} e_{z}.  (42)

Thus f is an isometry (recall Lemma 7). Suppose that F : V_{G} → ℝ_{0}^{S} extends f and for some L ∈ (0, ∞) we have

∀ x, y ∈ V_{G},  ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} ⩽ Ld_{G_{r}(S)}(x, y).  (43)

Our goal is to bound L from below.

For every x ∈ V_{G} and s ∈ (0, ∞) define ℬ_{s}(x) ⊆ V_{G} to be the inverse image under F of the W_{1}(S, d_{G_{r}(S)})-ball of radius s centered at F (x), i.e.,

ℬ_{s}(x) =^{def} {y ∈ V_{G} : ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} ⩽ s} .

By Lemma 9 there exists an integer

m ⩾ \frac{ϕd}{4} min \{|S ∖ ℬ_{s}(x)| , |ℬ_{s}(x)|\} ,  (44)

and m edge-disjoint paths joining S ∖ℬ_{s}(x) and ℬ_{s}(x). This means that we can find k_{1}, …, k_{m} ∈ ℕ and {z_{j,1}, z_{j,2}, …, z_{j,k_{j}}}_{j=1}^{m} ⊆ V_{G} such that {z_{j,1}}_{j=1}^{m} ⊆ S ∖ ℬ_{s}(x), {z_{j,k_{j}}}_{j=1}^{m} ⊆ ℬ_{s}(x), and such that {{z_{j,i}, z_{j,i+1}} : j ∈ {1, …, m} ∧ i ∈ {1, …, k_{j} − 1}} are distinct edges in E_{G}.

Let J ⊆ {1, …, m} be such that {z_{j,1}}_{j∈J} are distinct and {z_{j,1}}_{j∈J} = {z_{i,1}}_{i=1}^{m}. For every j ∈ J denote the number of those i ∈ {1, …, m} for which z_{j,1} = z_{i,1} by d_{j}. Since {{z_{i,1}, z_{i,2}}}_{i=1}^{m} are distinct edges in E_{G}, and G is d-regular, max_{j∈J} d_{j} ⩽ d. Because ∑_{j∈J} d_{j} = m, it follows that

|J| ⩾ \frac{m}{d} ⩾^{(44)} \frac{ϕ}{4} min \{|S ∖ ℬ_{s}(x)| , |ℬ_{s}(x)|\} .  (45)

The following lemma provides an upper bound on |J| that we will later contrast with (45).

Lemma 10. Under the above notation and assumptions we have

|J| ⩽ max \{d^{16(s−r)}, \frac{16nLd log d}{log n} (1 + \frac{2r|S|}{n})\} .  (46)

Proof. If |J| ⩽ d^{16(s−r)} then we are done, so we may assume that |J| > d^{16(s−r)}, or equivalently

s − r < \frac{log |J|}{16 log d}.  (47)

Observe that because {z_{j,1}}_{j∈J} ⊆ S and F |_{S} = f is an isometry on (S, d_{G_{r}(S)}),

∀ i, j ∈ J,  ∥F (z_{i,1}) − F (z_{j,1})∥_{W_{1}(S,d_{Gr(S)})} = d_{G_{r}(S)}(z_{i,1}, z_{j,1}) =^{(30)} 2r + d_{G}(z_{i,1}, z_{j,1}).  (48)

Hence,

∑_{j∈J} ∥F (z_{j,1}) − F (z_{j,k_{j}})∥_{W_{1}(S,d_{Gr(S)})}  (49)

= \frac{1}{2|J|} ∑_{i,j∈J} (∥F (z_{i,1}) − F (z_{i,k_{i}})∥_{W_{1}(S,d_{Gr(S)})} + ∥F (z_{j,1}) − F (z_{j,k_{j}})∥_{W_{1}(S,d_{Gr(S)})})

⩾ \frac{1}{2|J|} ∑_{i,j∈J} (∥F (z_{i,1}) − F (z_{j,1})∥_{W_{1}(S,d_{Gr(S)})} − ∥F (z_{i,k_{i}}) − F (z_{j,k_{j}})∥_{W_{1}(S,d_{Gr(S)})})

⩾ \frac{1}{2|J|} ∑_{i,j∈J} d_{G}(z_{i,1}, z_{j,1}) − (s − r)|J|  (50)

⩾ \frac{|J| log |J|}{8 log d} − (s − r)|J| > \frac{|J| log |J|}{16 log d},  (51)

where in (50) we used (48) and the fact that, because {z_{j,k_{j}}}_{j∈J} ⊆ ℬ_{s}(x), it follows from the definition of ℬ_{s}(x) that for every i, j ∈ J we have

∥F (z_{i,k_{i}}) − F (z_{j,k_{j}})∥_{W_{1}(S,d_{Gr(S)})} ⩽ ∥F (z_{i,k_{i}}) − F (x)∥_{W_{1}(S,d_{Gr(S)})} + ∥F (x) − F (z_{j,k_{j}})∥_{W_{1}(S,d_{Gr(S)})} ⩽ 2s.

The penultimate inequality in (51) is an application of (36), and the final inequality in (51) uses (47).

The quantity in (49) can be bounded from above using the Lipschitz condition (43) and the triangle inequality as follows.

∑_{j∈J} ∥F (z_{j,1}) − F (z_{j,k_{j}})∥_{W_{1}(S,d_{Gr(S)})} ⩽ L ∑_{j∈J} d_{G_{r}(S)}(z_{j,1}, z_{j,k_{j}}) ⩽ L ∑_{j∈J} ∑_{i=1}^{k_{j}−1} d_{G_{r}(S)}(z_{j,i}, z_{j,i+1}). (52)

Since {{z_{j,i}, z_{j,i+1}} : j ∈ J ∧ i ∈ {1, …, k_{j} − 1}} are distinct edges in E_{G},

∑_{j∈J} ∑_{i=1}^{k_{j}−1} d_{G_{r}(S)}(z_{j,i}, z_{j,i+1}) ⩽ ∑_{\{u,v\}∈E_{G}} d_{G_{r}(S)}(u, v) =^{(37)} \frac{nd}{2} (1 + \frac{2r|S|}{n}) .  (53)

A substitution of (53) into (52), and contrasting the resulting estimate with (51), yields

\frac{Lnd}{2} (1 + \frac{2r|S|}{n}) ⩾ \frac{|J| log |J|}{16 log d}.  (54)

It is elementary to check that if a ∈ [1, ∞) and b ∈ (1, ∞) satisfy a log a ⩽ b then a ⩽ 2b/ log b. By applying this with a = |J| and b = 8Lnd log d(1 + 2r|S|/n) ⩾ n, we see that (54) implies that

|J| ⩽ \frac{16nLd log d}{log n} (1 + \frac{2r|S|}{n}) ,

thus completing the proof of (46). □

Corollary 11. Suppose that the following conditions hold true.

d^{16(s−r)} ⩽ \frac{ϕ|S|}{8} and L ⩽ \frac{ϕ|S| log n}{128 (1 + \frac{2r|S|}{n}) nd log d}. (55)

Then

max_{x∈V_{G}} |ℬ_{s}(x)| < \frac{|S|}{2}.  (56)

Proof. Fix x ∈ V_{G}. If ℬ_{s}(x) ∩ S ≠ ∅ then it follows from (36) that there exist y, z ∈ ℬ_{s}(x) ∩ S with

d_{G}(y, z) ⩾ \frac{log |ℬ_{s}(x) ∩ S|}{4 log d}.  (57)

At the same time, since y, z ∈ S and F |_{S} = f is an isometry on (S, d_{G_{r}(S)}), we know that

d_{G}(y, z) + 2r =^{(30)} d_{G_{r}(S)}(y, z) = ∥F (y) − F (z)∥_{W_{1}(S,d_{Gr(S)})}

⩽ ∥F (y) − F (x)∥_{W_{1}(S,d_{Gr(S)})} + ∥F (x) − F (z)∥_{W_{1}(S,d_{Gr(S)})} ⩽ 2s, (58)

where in the last step of (58) we used the fact that y, z ∈ ℬ_{s}(x). Contrasting (57) and (58) yields

|ℬ_{s}(x) ∩ S| ⩽ d^{8(s−r)} ⩽ \sqrt{\frac{ϕ|S|}{8}} ⩽ \frac{2|S|}{5},  (59)

where we used the first assumption in (55) (and that ϕ ⩽ 1 ⩽ |S|). It follows from (59) that |S ∖ ℬ_{s}(x)| ⩾ 3|S|/5. By combining (45) and (46) with this lower bound on |S ∖ ℬ_{s}(x)| we see that

min \{\frac{3|S|}{5}, |ℬ_{s}(x)|\} < max \{\frac{4d^{16(s−r)}}{ϕ} , \frac{64nLd log d}{ϕ log n} (1 + \frac{2r|S|}{n})\} .  (60)

But, the two assumptions in (55) imply that 3|S|/5 is greater than the right hand side of (60), so

|ℬ_{s}(x)| ⩽ max \{\frac{4d^{16(s−r)}}{ϕ} , \frac{64nLd log d}{ϕ log n} (1 + \frac{2r|S|}{n})\} ⩽^{(55)} \frac{|S|}{2}.  □

Corollary 12. If the conditions in (55) are satisfied then

L ⩾ \frac{ϕs}{2 (1 + \frac{diam(G,d_{G})}{2r}) (1 + \frac{2r|S|}{n})}.  (61)

Proof. For every x ∈ V_{G} and y ∈ V_{G} ∖ ℬ_{s}(x) we have ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} > s. Hence,

\frac{1}{n^{2}} ∑_{x,y∈V_{G}} ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} ⩾ \frac{1}{n^{2}} ∑_{x∈V_{G}} ∑_{y∈V_{G}∖ℬ_{s}(x)} ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})}

⩾ \frac{s}{n^{2}} ∑_{x∈V_{G}} (n − |ℬ_{s}(x)|) ⩾ s (1 − \frac{max_{x∈V_{G}} |ℬ_{s}(x)|}{n}) ⩾^{(56)} \frac{s}{2}. (62)

At the same time, by Lemma 8 we have

\frac{1}{n^{2}} ∑_{x,y∈V_{G}} ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})} ⩽ \frac{2r + diam(S, d_{G})}{(2r + 1)ϕ|E_{G}|} ∑_{\{x,y\}∈E_{G}} ∥F (x) − F (y)∥_{W_{1}(S,d_{Gr(S)})}

⩽^{(43)} \frac{L (1 + \frac{diam(G,d_{G})}{2r})}{ϕ|E_{G}|} ∑_{\{x,y\}∈E_{G}} d_{G_{r}(S)}(x, y) =^{(37)} \frac{L (1 + \frac{diam(G,d_{G})}{2r}) (1 + \frac{2r|S|}{n})}{ϕ}. (63)

The desired estimate (61) follows by contrasting (62) with (63). □

Theorem 13. Continuing with the same notation as above, if 0 < r ⩽ diam(G, d_{G}) then

L ≳ \frac{ϕ}{1 + \frac{r|S|}{n}} · min \{\frac{|S| log n}{nd log d}, \frac{16r^{2} log d + r log(ϕ|S|/8)}{diam(G, d_{G}) log d}\} .  (64)

Proof. If 16r log d+log(ϕ|S|/8) ⩽ 0 then (64) is vacuous. Supposing that 16r log d+log(ϕ|S|/8) > 0, choose s = r + (log(ϕ|S|/8))/(16 log d), so s > 0 and d^{16(s−r)} = ϕ|S|/8. The first inequality of (55) is therefore satisfied, so either the second inequality in (55) fails, corresponding to a lower bound on L, or by Corollary 12 the lower bound on L in (61) is satisfied. This simplifies to give (64). □

For a wide range of the parameters (i.e., n, d, ϕ, diam(G, d_{G}), |S|, r), Theorem 13 yields a nontrivial lower bound on the Lipschitz constant of any mapping F that extends the 1-Lipschitz function f given in (42). Rather than treating the general case, we shall now proceed to compute an optimal setting of the parameters in (64) when G has the property that diam(G, d_{G}) ≍ (log n)/ log d and ϕ(G) ≍ 1. Such graphs exist for any degree d ⩾ 3 and arbitrarily large n ∈ ℕ, and in fact this holds true with probability tending to 1 as n → ∞ when G is chosen uniformly at random from the finite set of all n-vertex d-regular graphs; for the diameter of random regular graphs see e.g. [BFdlV82] and for the expansion of random regular graphs see e.g. [HLW06, Theorem 4.16].

So, if ϕ ≍ 1 and diam(G, d_{G}) ≍ (log n)/ log d, and continuing with the assumption of Theorem 13 that 0 < r ⩽ diam(G, d_{G}), the lower bound (64) becomes

L ≳ \frac{1}{1 + \frac{r|S|}{n}} · min \{\frac{|S| log n}{nd log d}, \frac{r (r log d + log |S|)}{log n}\} .

The optimal choice (up to constant factors) is to take S ⊆ V_{G} with |S| = ⌊n\sqrt{d log d}/\sqrt{log n}⌋ (this is allowed provided n is large enough so as to ensure that |S| ⩽ n, specifically it suffices to assume that n ⩾ d^{d}) and r ≍ \sqrt{log n}/\sqrt{d log d}. With these choices we see that L ≳ \sqrt{log n}/\sqrt{d log d}. Thus,

e_{⌊n\sqrt{d log d}/\sqrt{log n}⌋} (G_{r}(S), W_{1} (S, d_{G_{r}(S)})) ≳ \begin{matrix}√ & \overline{log n} \\ √ & \overline{d log d} \end{matrix}.  (65)

For fixed d (say, d = 4), the estimate (65) implies Theorem 1. □

Remark 14. The above reasoning also provides a new example showing that 𝔞𝔢(ε) ≳ 1/ε. Recalling (31), every distinct x, y ∈ S satisfy d_{G_{r}(S)}(x, y) ⩾ εdiam(S, d_{G_{r}(S)}) where ε ≍ r/diam(G, d_{G}). When diam(G, d_{G}) ≍ (log n)/ log d and r ≍ \sqrt{log n}/\sqrt{d log d}, this becomes ε ≍ \sqrt{log d}/\sqrt{d log n}. The lower bound L ≳ \sqrt{log n}/\sqrt{d log d} therefore becomes L ≳ 1/(εd).

4. Proof of Theorem 4

In Section 1.1 we defined the parameters e^{α}(X, Z) and e_{n}^{α}(X, Z), for every α ∈ (0, 1], n ∈ ℕ and every two metric spaces (X, d_{X}) and (Z, d_{Z}). Below it will be convenient to also use the analogous notation e^{α}(X, S, Z) for S ⊆ X, i.e.,

e^{α}(X, S, Z) =^{def} e((X, d_{X}^{α}), S, (Z, d_{Z})).

Theorem 4 asserts the validity of the following four lower bounds for every m, n ∈ ℕ.

e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ≳ m^{\frac{2α−1}{4α}}  and  e_{n}^{α}(ℓ_{∞}, ℓ_{2}) ≳ (log n)^{\frac{2α−1}{4α}} ,  (66)

and

e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ≳ m^{α^{2}− \frac{1}{2}}  and  e_{n}^{α}(ℓ_{∞}, ℓ_{2}) ≳ (\frac{log n}{log log n})^{α^{2}− \frac{1}{2}} .  (67)

The proof of (66) appears in Section 4.1 below, and the proof of (67) appears in Section 4.2 below.

4.1. Twisted unions of hypercubes. For m ∈ ℕ we identify the discrete hypercube {0, 1}^{m} with 𝔽_{2}^{m}, the vector space of dimension m over the field of size two 𝔽_{2}. We let e_{1}, …, e_{m} denote the standard basis of 𝔽_{2}^{m} and write e = e_{1} + … + e_{m}.

Lemma 15. Suppose that α ∈ (\frac{1}{2}, 1] and r, s ∈ (0, ∞) satisfy

(2α)^{2α}s(2r)^{2α−1} ⩾ ((2α)^{\frac{2α}{2α−1}} − 1)^{2α−1} .  (68)

Define for every (x, i), (y, j) ∈ 𝔽_{2}^{m} × 𝔽_{2},

d((x, i), (y, j)) =^{def} \{ \begin{matrix}min \{s∥x − y∥_{1}, 2r + ∥x − y∥1^{\frac{1}{2α}} \} & if i = j = 1, \\ ∥x − y∥1^{\frac{1}{2α}} & if i = j = 0, \\ r + min \{s∥x − y∥_{1}, ∥x − y∥1^{\frac{1}{2α}} \} & if i ≠ j. \end{matrix}  (69)

Then d is a metric on 𝔽_{2}^{m} × 𝔽_{2}.

Proof. Recall that if ω : [0, ∞) → [0, ∞) is concave, nondecreasing, and satisfies ω(0) = 0, then ω ∘ d_{X} is a metric on X for every metric space (X, d_{X}). An application of this observation to the mapping t ↦ t^{1/(2α)}, which is concave because α > \frac{1}{2}, shows that d is a metric on 𝔽_{2}^{m} × \{0\}. Also, since both of the mappings t ↦ st and t ↦ 2r + t^{1/(2α)} are concave and increasing, the mapping t ↦ min{st, 2r + t^{1/(2α)}} is concave and increasing. Consequently, d is a metric on 𝔽_{2}^{m} × {1}.

It therefore remains to show that if i, j, k ∈ {0, 1} satisfy {i, j, k} = {0, 1} and x, y, z ∈ 𝔽_{2}^{m} then d((x, i), (y, j)) ⩽ d((x, i), (z, k))+d((z, k), (y, j)). By translation and permutation of the coordinates we may assume that x = 0 and y = e_{1} +…+e_{a} for some a ∈ {1, …, m}. In this case, note that if z has a nonzero entry outside {1, …, a} then both ∥z∥_{1} and ∥y − z∥_{1} will decrease if we change that entry of z from 1 to 0. By the definition of d in (69), this shows that d((x, i), (z, k))+d((z, k), (y, j)) will decrease if we set all the entries of z that are outside {1, …, a} to be equal 0. It therefore suffices to prove that for every a ∈ {1, …, m} and b ∈ {1, …, a − 1} we have

d((0, i), (e_{1} + … + e_{a}, j)) ⩽ d((0, i), (e_{1} + … + e_{b}, k)) + d((e_{1} + … + e_{b}, k), (e_{1} + … + e_{a}, j)). (70)

We shall establish the validity of (70) through the following case analysis.

Case 1: i = j = 0. In this case necessarily k = 1, so by (69) the desired inequality (70) becomes

a^{\frac{1}{2α}} ⩽ 2r + min \{sb, b^{\frac{1}{2α}} \} + min \{s(a − b), (a − b)^{\frac{1}{2α}} \} .  (71)

The mapping ω : [0, ∞) → [0, ∞) given by ω(t) =^{def} min{st, t^{1/(2α)}} is concave, increasing and satisfies ω(0) = 0. Consequently, ω(b)+ω(a−b) ⩾ ω(a). So, in order to prove (71) it suffices to show that a^{1/(2α)} ⩽ 2r + ω(a) = 2r + min{sa, a^{1/(2α)}}. We therefore need to show that a^{1/(2α)} ⩽ 2r + sa. Define ϕ : [0, ∞) → [0, ∞) by ϕ(t) = 2r + st − t^{1/(2α)}. The minimum of ϕ on [0, ∞) is attained at t_{min} = 1/(2αs)^{2α/(2α−1)}. Hence, by our assumption (68) we have

ϕ(a) ⩾ ϕ(t_{min}) = 2r + \frac{s}{(2αs)^{\frac{2α}{2α−1}}} − \frac{1}{(2αs)^{\frac{1}{2α−1}}} = 2r − \frac{(2α)^{\frac{2α}{2α−1}} − 1}{((2α)^{2α}s)^{\frac{1}{2α−1}}} ⩾^{(68)} 0.

Case 2: i = j = 1. In this case necessarily k = 0, so by (69) the desired inequality (70) becomes

min \{sa, 2r + a^{\frac{1}{2α}} \} ⩽ 2r + min \{sb, b^{\frac{1}{2α}} \} + min \{s(a − b), (a − b)^{\frac{1}{2α}} \} .  (72)

As in Case 1, by the subadditivity of ω we see that in order to prove (72) it suffices to show that min{sa, 2r + a^{1/(2α)}} ⩽ 2r + ω(a) = 2r + min{sa, a^{1/(2α)}}, which is immediate.

Case 3: {i, j} = {0, 1}. In this case, by interchanging the roles of b and a − b, if necessary, in order to prove the desired inequality (70) one must show that the following two inequalities hold true

r + min \{sa, a^{\frac{1}{2α}} \} ⩽ b^{\frac{1}{2α}} + r + min \{s(a − b), (a − b)^{\frac{1}{2α}} \} ,

and

r + min \{sa, a^{\frac{1}{2α}} \} ⩽ r + min \{sb, b^{\frac{1}{2α}} \} + min \{s(a − b), 2r + (a − b)^{\frac{1}{2α}} \} .

Thus, we need to check that

min \{sa, a^{\frac{1}{2α}} \} ⩽ b^{\frac{1}{2α}} + min \{s(a − b), (a − b)^{\frac{1}{2α}} \} ,  (73)

and

min \{sa, a^{\frac{1}{2α}} \} ⩽ min \{sb, b^{\frac{1}{2α}} \} + min \{s(a − b), 2r + (a − b)^{\frac{1}{2α}} \} .  (74)

Inequality (74) follows immediately from the subadditivity of ω as follows.

min \{sb, b^{\frac{1}{2α}} \} + min \{s(a − b), 2r + (a − b)^{\frac{1}{2α}} \} ⩾ ω(b) + ω(a − b) ⩾ ω(a) = min \{sa, a^{\frac{1}{2α}} \} .

Since the mapping t ↦ t^{1/(2α)} is subadditive, we have b^{1/(2α)} + (a − b)^{1/(2α)} ⩾ a^{1/(2α)}. Therefore, in order to prove (73) it suffices to show that b^{1/(2α)}+s(a−b) ⩾ min{sa, a^{1/(2α)}}. Define ψ : [0, a] → ℝ by ψ(t) = t^{1/(2α)}+s(a−t). Then ψ is concave. It follows that the minimum of ψ on the interval [0, a] is attained at one of its endpoints, and therefore ψ(b) ⩾ min{ψ(0), ψ(a)} = min{sa, a^{1/(2α)}}. □

The proof of the following theorem is a variant of an argument of [JLS86].

Theorem 16. Continuing with the notation of Lemma 15 and assuming from now on that the condition (68) is satisfied, define f : 𝔽_{2}^{m} × {0} → ℓ_{2}^{m} by setting f(x, 0) = x for every x ∈ 𝔽_{2}^{m}. Then ∥f(x, 0) − f(y, 0)∥_{2} = d((x, 0), (y, 0))^{α} for every x, y ∈ 𝔽_{2}^{m}. At the same time, if F : 𝔽_{2}^{m} × 𝔽_{2} → ℓ_{2}^{m} extends f and satisfies ∥F (u) − F (v)∥_{2} ⩽ Ld(u, v)^{α} for some L ∈ (0, ∞) and every u, v ∈ 𝔽_{2}^{m} × 𝔽_{2} then we necessarily have

L ⩾ \frac{\sqrt{m}}{s^{α}\sqrt{m} + 2r^{α}} .  (75)

Proof. Note that for every x, y ∈ 𝔽_{2}^{m} we have

∥f(x, 0) − f(y, 0)∥_{2} = ∥x − y∥_{2} = \sqrt{∥x − y∥_{1}} = d((x, 0), (y, 0))^{α},

by the definition of d in (69). Next, the assumptions on F imply that for every x, y ∈ 𝔽_{2}^{m} and every j ∈ {1, …, m} we have

∥F (x + e_{j}, 1) − F (x, 1)∥_{2} ⩽ Ld((x + e_{j}, 1), (x, 1))^{α} =^{(69)} L min {s^{α}, (2r + 1)^{α}} ⩽ Ls^{α}.

Hence,

∑_{j=1}^{m} ∑_{x∈𝔽_{2}^{m}} ∥F (x + e_{j}, 1) − F (x, 1)∥_{2}^{2} ⩽ m2^{m}L^{2}s^{2α}.  (76)

Also, the following estimate holds true for every x ∈ 𝔽_{2}^{m}.

∥F (x + e, 1) − F (x, 1)∥_{2}

⩾ ∥F (x + e, 0) − F (x, 0)∥_{2} − ∥F (x + e, 1) − F (x + e, 0)∥_{2} − ∥F (x, 1) − F (x, 0)∥_{2}

⩾ ∥f(x + e, 0) − f(x, 0)∥_{2} − Ld((x + e, 1), (x + e, 0))^{α} − Ld((x, 1), (x, 0))^{α}
= \sqrt{m} − 2Lr^{α}.

Hence,

∑_{x∈𝔽_{2}^{m}} ∥F (x + e, 1) − F (x, 1)∥_{2}^{2} ⩾ 2^{m} (max \{\sqrt{m} − 2Lr^{α}, 0\})^{2} .  (77)

By a classical inequality of Enflo [Enf69] (see also [Mat02, § 15.4]),

∑_{x∈𝔽_{2}^{m}} ∥F (x + e, 1) − F (x, 1)∥_{2}^{2} ⩽ ∑_{j=1}^{m} ∑_{x∈𝔽_{2}^{m}} ∥F (x + e_{j}, 1) − F (x, 1)∥_{2}^{2}.  (78)

A substitution of (76) and (77) into (78) now yields the estimate

\sqrt{m} − 2Lr^{α} ⩽ Ls^{α}\sqrt{m} ⟹ L ⩾ \frac{\sqrt{m}}{s^{α}\sqrt{m} + 2r^{α}} .  □

One should clearly choose those r, s ∈ (0, ∞) that satisfy the constraint (68) and maximize the right hand side of (68). This yields better dependence (in terms of an α-dependent constant factor but not in term of dependence on n) than the following sub-optimal choices.

r =^{def} m^{\frac{1}{4α^{2}}}  and  s =^{def} m^{− \frac{2α−1}{4α^{2}}} .  (79)

It is elementary to check that under these choices the constraint (68) is satisfied, yielding the estimate L ≳ m^{(2α−1)/(4α)} in Theorem 16. This implies the validity of (66), i.e., the first half of Theorem 4. Namely, the following bounds hold true.

Corollary 17. Continuing with the notation of Lemma 15, we have

e^{α}(ℓ_{∞}, ℓ_{2}^{m}) ⩾ e^{α}((𝔽_{2}^{m} × 𝔽_{2}, d), 𝔽_{2}^{m} × \{0\}, ℓ_{2}^{m}) ≳ m^{\frac{2α−1}{4α}} .

Also, since m ≍ log |𝔽_{2}^{m}|, it follows that for arbitrarily large n ∈ ℕ we have

e_{n}^{α}(ℓ_{∞}, ℓ_{2}) ≳ (log n)^{\frac{2α−1}{4α}} .

Remark 18. Consider the mappings ω_{0}, ω_{1} : [0, ∞) → [0, ∞) given by

∀ t ⩾ 0,  ω_{0}(t) = t^{1/(2α)}  and  ω_{1}(t) = min{st, 2r + ω_{0}(t)}.

Both ω_{0} and ω_{1} are concave, increasing and vanish at the origin. The metric d given in (69) satisfies d((x, 0), d(y, 0)) = ω_{0}(∥x − y∥_{1}) and d((x, 1), (y, 1)) = ω_{1}(∥x − y∥_{1}). As explained in Remark 5.5 of [MN15], it follows that both of the metric spaces (𝔽_{2}^{m} × {0}, d) and (𝔽_{2}^{m} × {1}, d) embed into ℓ_{1} with O(1) distortion. We do not know whether the metric space (𝔽_{2}^{m} × 𝔽_{2}, d) admits an embedding into ℓ_{1} with O(1) distortion. If it were the case that any embedding of (𝔽_{2}^{m} × 𝔽_{2}, d) (say, when α = 1) into ℓ_{1} must incur bi-Lipschitz distortion that tends to ∞ as n → ∞, this would be the first known example of a metric space that can be partitioned into two subsets, each of which well-embeds into ℓ_{1} yet the entire space does not. For more on such questions, see [MN13b].

Remark 19. The metric d in (69), as well as the magnification of a metric space that was described in Section 3.1, are both special cases of a generalization of a construction that was used in [JLS86] for the purpose of proving a Lipschitz-nonextendability result. Variants of this construction were also used in [Lan99, CKR05]. The general idea is the following procedure to “glue” two metric spaces. Suppose that (X, d_{X}) and (Y, d_{Y}) are finite metric spaces with X and Y disjoint as sets. Suppose also that we are given a mapping σ : X → Y and r ∈ (0, ∞). Define a weighted graph structure on X ∪ Y as follows. If x_{1}, x_{2} ∈ X then join x_{1} and x_{2} by an edge of weight d_{X}(x_{1}, x_{2}). Similarly, if y_{1}, y_{2} ∈ Y then join y_{1} and y_{2} by an edge of weight d_{Y} (y_{1}, y_{2}). Also, for every x ∈ X join x and σ(x) by an edge of weight r (a further generalization of this procedure could allow the weight of the edge {x, σ(x)} to depend on x). Consider now the shortest-path metric that this weighted graph induces on X ∪Y. One can check that the above metric spaces can also be described as subsets of this general construction, whose usefulness is probably yet to be fully exploited.

4.2. Linearization. Our goal here is to prove (67), thus completing the proof of Theorem 4. The argument below is based on the linearization procedure of [JL84], with several modifications that yield quantitative improvements and, more importantly, allow us to to treat Hölder mappings.

In what follows, given a Banach space (W, ∥ · ∥_{W}) we denote

B_{W} =^{def} {x ∈ W : ∥x∥_{W} ⩽ 1}  and  S_{W} =^{def} ∂B_{W} = {x ∈ W : ∥x∥_{W} = 1}.

If V ⊆ W is a linear subspace then we will always consider it as being equipped with the norm inherited from W, thus slightly abusing notation by denoting the sets V ∩ B_{W} and V ∩ S_{W} by B_{V} and S_{V}, respectively. A mapping h : W_{1} → W_{2} between two real vector spaces W_{1}, W_{2} is said to be positively homogeneous if h(λx) = λh(x) for every λ ∈ [0, ∞).

Lemma 20 below is a variant of Lemma 5 in [JL84], with the difference being that in [JL84] the conclusion corresponding to (81) is weaker in the sense that the factor \sqrt{m}D is replaced by m. The difference between our proof and the proof in [JL84] is that we perform averaging in the image of T rather than in X itself, allowing for a more refined estimate that we shall use later.

Lemma 20. Fix m ∈ ℕ and D ∈ [1, ∞). Let (Y, ∥·∥_{Y}) and (Z, ∥·∥_{Z}) be Banach spaces and X ⊆ Y an m-dimensional linear subspace of Y. Suppose that T : X → ℓ_{2}^{m} is a linear operator that satisfies

∀ x ∈ X,  ∥x∥_{Y} ⩽ ∥T x∥_{2} ⩽ D∥x∥_{Y} .  (80)

Suppose also that we are given a positively homogeneous Lipschitz mapping ψ : X → Z and a linear operator U : X → Z. Then there exists a positively homogeneous mapping Ψ : Y → Z that satisfies

∥Ψ∥_{Lip} ≲ ∥ψ∥_{Lip}  and  ∥Ψ|_{X} − U∥_{Lip} ≲ \sqrt{m}D sup_{z∈S_{X}} ∥ψ(z) − Uz∥_{Z}.  (81)

Proof. Write B_{2}^{m} = B_{ℓ_{2}^{m}} and

v_{m} = vol (B_{2}^{m}) = \frac{π^{\frac{m}{2}}}{Γ (1 + \frac{m}{2})}.  (82)

Define ϕ : Y → Z as follows.

∀ y ∈ Y, ϕ(y) =^{def} \frac{1}{v_{m}} ∫_{B_{2}^{m}} ψ (y + T^{−1}w) dw = \frac{1}{v_{m}} ∫_{T y+B_{2}^{m}} ψ (T^{−1}w) dw.

Then, because ϕ is obtained by applying an averaging operator to ψ, we have

∥ϕ∥_{Lip} ⩽ ∥ψ∥_{Lip}.  (83)

Also, because ψ(0) = 0 (recall that ψ is positively homogeneous), we have

sup_{y∈S_{Y}} ∥ϕ(y)∥_{Z} ⩽ ∥ψ∥_{Lip} sup_{(y,w)∈S_{Y} ×B_{2}^{m}} ∥y + T^{−1}w∥_{Y} ⩽^{(80)} 2∥ψ∥_{Lip}.  (84)

Similarly,

sup_{y∈S_{X}} ∥ϕ(y) − Uy∥_{Z} = sup_{y∈S_{X}} ∥\frac{1}{v_{m}} ∫_{B_{2}^{m}}(ψ − U) (y + T^{−1}w) dw∥_{Z}

⩽ sup_{(y,w)∈S_{X}×B_{2}^{m}} ∥(ψ − U)(y + T^{−1}w)∥_{Z} ⩽ sup_{z∈2B_{X}} ∥ψ(z) − Uz∥_{Z} = 2 sup_{z∈S_{X}} ∥ψ(z) − Uz∥_{Z}, (85)

where the penultimate step in (85) holds true because, due to (80), we have T^{−1}B_{2}^{m} ⊆ B_{X}, so S_{X} + T^{−1}B_{2}^{m} ⊆ 2B_{X}. The final step of (85) holds true because ψ − U is positively homogeneous.

Fix distinct x, y ∈ S_{X} and write 2r =^{def} ∥x − y∥_{Y}. Then, since U and T are linear,

(ϕ − U)(x) − (ϕ − U)(y)

= \frac{1}{v_{m}} ∫_{(T x+B_{2}^{m})∖(T y+B_{2}^{m})}(ψ − U)(T^{−1}(w))dw − \frac{1}{v_{n}} ∫_{(T y+B_{2}^{m})∖(T x+B_{2}^{n})}(ψ − U)(T^{−1}(w))dw.

Consequently,

∥(ϕ − U)(x) − (ϕ − U)(y)∥_{Z} ⩽ \frac{1}{v_{m}} ∫_{(T x+B_{2}^{m})△(T y+B_{2}^{m})} ∥(ψ − U)(T^{−1}(w))∥_{Z}dw

⩽ \frac{vol ((T x + B_{2}^{m})△(T y + B_{2}^{m}))}{v_{n}} · sup_{z∈(x+T^{−1}B_{2}^{m})△(y+T^{−1}B_{2}^{m})} ∥ψ(z) − Uz∥_{Z}. (86)

We note that

vol ((T x + B_{2}^{m}) ∪ (T y + B_{2}^{m})) ⩽ v_{m} + ∥T x − T y∥_{2}v_{m−1}.  (87)

Indeed, by rotation invariance, it suffices to verify (87) when T x = re_{1} and T y = −re_{1}, where e_{1}, …, e_{m} is the standard basis of ℝ^{m} and we recall that ∥T x − T y∥_{2} = 2r. Identifying ℝ^{m} with ℝ×ℝ^{m−1}, the estimate (87) is a consequence of the fact that (re_{1} +B_{2}^{m})∪(−re_{1} +B_{2}^{m}) is contained in the union of the three sets ([r, ∞) × ℝ^{m−1}) ∩ (re_{1} + B_{2}^{m}), ((−∞, −r] × ℝ^{m−1}) ∩ (−re_{1} + B_{2}^{m}) and [−r, r] × B_{2}^{m−1}, whose interiors are disjoint.

Now, due to (87) we have

vol ((T x + B_{2}^{m})△(T y + B_{2}^{m})) = 2vol ((T x + B_{2}^{m}) ∪ (T y + B_{2}^{m})) − vol (T x + B_{2}^{m}) − vol (T y + B_{2}^{m})
⩽ 2∥T x − T y∥_{2}v_{m−1}.

So, the first term in the right hand side of (86) can be bounded as follows.

\frac{vol ((T x + B_{2}^{m})△(T y + B_{2}^{m}))}{v_{n}} ⩽ \frac{2v_{m−1}}{v_{m}} ∥T x − T y∥_{2} ⩽^{(80)} \sqrt{m}D∥x − y∥_{Y} ,  (88)

where we used the fact that 2v_{m−1}/v_{m} ⩽ \sqrt{m}, which follows from (82) and Stirling’s formula (in addition, we actually have lim_{m→∞} 2v_{m−1}/v_{m} = \sqrt{2/π}).

To bound the second term in the right hand side of (86), note that T^{−1}B_{2}^{m} ⊆ B_{X}, by (80). Therefore (x + T^{−1}B_{2}^{m})△(y + T^{−1}B_{2}^{m}) ⊆ 2B_{X}, since x, y ∈ S_{X}. So,

sup_{z∈(x+T^{−1}B_{2}^{m})△(y+T^{−1}B_{2}^{m})} ∥ψ(z) − Uz∥_{Z} ⩽ sup_{z∈2B_{X}} ∥ψ(z) − Uz∥_{Z} = 2 sup_{z∈S_{X}} ∥ψ(z) − Uz∥_{Z}, (89)

where we used the fact that ψ − U is positively homogeneous.

A substitution of (88) and (89) into (86) shows that

∥(ϕ − U)|_{S_{X}} ∥_{Lip} ⩽ 4\sqrt{m}D sup_{z∈S_{X}} ∥ψ(z) − Uz∥_{Z}.  (90)

Define Ψ : Y → Z to be the positively homogeneous extension of ϕ|_{S_{Y}}, i.e., Ψ(y) =^{def} ∥y∥_{Y} ϕ(y/∥y∥_{Y}) for every y ∈ Y ∖ {0} and Ψ(0) = 0. Then a simple computation (that is carried out in detail in [JL84, Lemma 2]) shows that

∥Ψ∥_{Lip} ⩽ 2∥ϕ|_{S_{Y}} ∥_{Lip} + sup_{y∈S_{Y}} ∥ϕ(y)∥_{Z} ⩽^{(83)∧(84)} 4∥ψ∥_{Lip}.

For the same reason, since Ψ − U is the positively homogeneous extension of (ϕ − U)|_{S_{X}} to X,

∥Ψ|_{X} − U∥_{Lip} ⩽ 2∥(ϕ − U)|_{S_{X}} ∥_{Lip} + sup_{y∈S_{X}} ∥ϕ(y) − Uy∥_{Z} ⩽^{(85)∧(90)} 10\sqrt{m}D sup_{z∈S_{X}} ∥ψ(z) − Uz∥_{Z}. □

We shall use below the following lemma of Begun [Beg99]; alternatively one could use below an argument of Bourgain [Bou87] that Begun significantly simplified in [Beg99].

Lemma 21. Fix δ, L, τ ∈ (0, ∞) and m ∈ ℕ. Suppose that (Y, ∥ · ∥_{Y}) is an m-dimensional normed space and that (Z, ∥ · ∥_{Z}) is a Banach space. Let K ⊆ Y be a convex set and suppose that we are given a mapping F : K + τB_{Y} → Z that satisfies

∀ x, y ∈ K + τB_{Y} , ∥F (x) − F (y)∥_{Z} ⩽ L(∥x − y∥_{Y} + δ).

Define h : K → Z by

∀ x ∈ K,  h(x) =^{def} \frac{1}{vol(τB_{Y})} ∫_{τB_{Y}} F (x + y)dy,  (91)

where the integration and vol(·) are interpreted through an identification of Y with ℝ^{m}. Then

∥h∥_{Lip} ⩽ L (1 + \frac{δm}{2τ}) .

Corollary 22. Fix τ ∈ (0, ∞), α ∈ (0, 1] and m ∈ ℕ. Suppose that (Y, ∥ · ∥_{Y}) is an m-dimensional normed space and that (Z, ∥ · ∥_{Z}) is a Banach space. Let K ⊆ Y be a convex set and suppose that F : K + τB_{Y} → Z is α-Hölder. Then there exists h : K → Z that satisfies

sup_{x∈K} ∥h(x) − F (x)∥_{Z} ⩽ τ^{α}∥F ∥_{Lip(α)}  and  ∥h∥_{Lip} ⩽ \frac{α^{2}(m/τ)^{1−α} + 1}{α}∥F ∥_{Lip(α)}.

Proof. Denote L = ∥F ∥_{Lip(α)}. Note that for every δ ∈ (0, ∞) and every x, y ∈ K + τB_{Y} we have

∥F (x) − F (y)∥_{Z} ⩽ L∥x − y∥_{Y}^{α} ⩽ L(∥x − y∥_{Z} + δ) sup_{t⩾0} \frac{t^{α}}{t + δ} = \frac{(1 − α)^{1−α}α^{α}L}{δ^{1−α}}(∥x − y∥_{Z} + δ).

We may therefore apply Lemma 21, deducing that for h defined as in (91) we have

∥h∥_{Lip} ⩽ \frac{(1 − α)^{1−α}α^{α}L}{δ^{1−α}} (1 + \frac{δm}{2τ}) .  (92)

The value of δ that minimizes the right hand side of (92) is δ = 2τ(1 − α)/(αm), which gives

∥h∥_{Lip} ⩽ (1 − α)^{1−α}α^{α} (\frac{α^{1−α}}{(1 − α)^{1−α}} (\frac{m}{2τ} )^{1−α} + \frac{1 − α}{α}) L ⩽ \frac{α^{2}(m/τ)^{1−α} + 1}{α}L.

It remains to note that for every x ∈ K we have

∥h(x)−F (x)∥_{Z} = ∥\frac{1}{vol(τB_{Y})} ∫_{τB_{Y}} (F (x+y)−F (x))dy∥_{Z} ⩽ \frac{1}{vol(τB_{Y})} ∫_{τB_{Y}} L∥y∥_{Y}^{α} dy ⩽ Lτ^{α}. □

Theorem 23. There is a universal constant κ ∈ (0, 1) with the following properties. Fix α ∈ (0, 1], M, m ∈ ℕ and C, D ∈ [1, ∞). Suppose that (Y, ∥ · ∥_{Y}) is an M-dimensional normed space and that (Z, ∥ · ∥_{Z}) is an m-dimensional normed space. Let X ⊆ Y be an m-dimensional subspace of Y whose Banach–Mazur distance to ℓ_{2}^{m} is at most D, i.e., there exists a linear operator T : X → ℓ_{2}^{m} satisfying (80). Suppose also that U : X → Z is a linear operator with

∀x ∈ X,  ∥x∥_{Y} ⩽ ∥Ux∥_{Z} ⩽ C∥x∥_{Y} .  (93)

For every ε ∈ (0, 1) let 𝒩_{ε} be an ε-net in S_{X}. Then, under the additional assumption that

ε ⩽ (\frac{κ}{\sqrt{m}CDe^{α}(Y, 𝒩_{ε}, Z)})^{\frac{1}{α}} ,  (94)

there exists a linear operator V : Y → Z that extends U and whose operator norm satisfies

∥V ∥_{Y →Z} ≲ αM^{1−α}m^{\frac{1−α}{2α}} C^{\frac{1}{α}} D^{\frac{1−α}{α}} e^{α}(Y, 𝒩_{ε}, Z)^{\frac{1}{α}} + \frac{C}{α} e^{α}(Y, 𝒩_{ε}, Z).  (95)

Proof. If x, y ∈ B_{X} then ∥x − y∥_{Y} ⩽ 2, hence ∥Ux − Uy∥_{Z} ⩽ C∥x − y∥_{Y} ⩽ 2^{1−α}C∥x − y∥_{Y}^{α}. This implies that the restriction of U to 𝒩_{ε} is α-Hölder with constant 2C. Denoting L = e^{α}(Y, 𝒩_{ε}, Z), it follows that there exists g : Y → Z that extends U|_{𝒩_{ε}} and is α-Hölder with constant 2CL.

Let ρ : Z → CB_{Z} be the radial retraction of Z onto CB_{Z}, i.e., ρ(z) = z if ∥z∥_{Z} ⩽ C and ρ(z) = Cz/∥z∥_{Z} if ∥z∥_{Z} > C. It is straightforward to check that ρ is 2-Lipschitz. Therefore, if we define F = ρ ∘ g then ∥F ∥_{Lip(α)} ⩽ 2∥g∥_{Lip(α)} ⩽ 4CL and ∥F (y)∥_{Z} ⩽ C for every y ∈ Y. Moreover, for every a ∈ 𝒩_{ε} we have ∥g(a)∥_{Z} = ∥Ua∥_{Z} ⩽ C, so F (a) = ρ(g(a)) = g(a). Thus F : Y → CB_{Z} is also an extension of U|_{A}. Fix τ ∈ (0, 1) that will be determined later. By Corollary 22 (applied with K = Y) there exists h : Y → Z that satisfies

∀ y ∈ Y  ∥h(y) − F (y)∥_{Z} ⩽ 4CLτ^{α},  (96)

and

∥h∥_{Lip} ⩽ 4\frac{α^{2}(M/τ)^{1−α} + 1}{α}CL.  (97)

Then

sup_{y∈S_{Y}} ∥h(y)∥_{Z} ⩽^{(96)} sup_{y∈S_{Y}} ∥F (y)∥_{Z} + 4CLτ^{α} ⩽ C + 4CLτ^{α},  (98)

where in the last step of (98) we used the fact that F takes values in CB_{Z}.

Denote by ψ : Y → Z the positively homogeneous extension of h|_{S_{Y}} to Y. By [JL84, Lemma 2],

∥ψ∥_{Lip} ⩽ 2∥h|_{S_{Y}} ∥_{Lip} + sup_{y∈S_{Y}} ∥h(y)∥_{Z} ⩽^{(97)∧(98)} 4\frac{α^{2}(M/τ)^{1−α} + 1}{α}CL + C + 4CLτ^{α}. (99)

Take x ∈ S_{X} (thus ψ(x) = h(x)) and a ∈ 𝒩_{ε} with ∥a − x∥_{Y} ⩽ ε. Then h(a) = F (a) = Ua. Hence,

∥ψ(x) − Ux∥_{Z} ⩽ ∥h(x) − F (x)∥_{Z} + ∥F (x) − F (a)∥_{Z} + ∥Ua − Ux∥_{Z} ⩽ 4CLτ^{α} + 4CL∥x − a∥_{Y}^{α} + C∥x − a∥_{Y} ⩽ 4CLτ^{α} + 4CLε^{α} + Cε ⩽ 5CL(τ^{α} + ε^{α}). (100)

Due to (99) and (100), Lemma 20 implies that there exists Ψ : Y → Z that satisfies

∥Ψ∥_{Lip} ≲ \frac{α^{2}(M/τ)^{1−α} + 1}{α}CL + C + CLτ^{α} ≲ \frac{α^{2}(M/τ)^{1−α} + 1}{α}CL,

and

∥Ψ|_{X} − U∥_{Lip} ≲ \sqrt{m}CDL(τ^{α} + ε^{α}).

By Proposition 1 in [JL84], which relies on an important linearization result due to Lindenstrauss [Lin64], there exists a linear operator S : Y → Z such that

∥S∥_{Y →Z} ⩽ ∥Ψ∥_{Lip} ≲ \frac{α^{2}(M/τ)^{1−α} + 1}{α}CL,  (101)

and

∥S|_{X} − U∥_{X→Z} ⩽ ∥Ψ|_{X} − U∥_{Lip} ≲ \sqrt{m}CDL(τ^{α} + ε^{α}).  (102)

Our assumption (94) says that \sqrt{m}CDLε^{α} ⩽ κ. So, if we choose τ = (κ/(\sqrt{m}CDL))^{1/α} and κ > 0 is a small enough universal constant then it would follow from (101) and (102) that

∥S∥_{Y →Z} ≲ αM^{1−α}m^{\frac{1−α}{2α}} C^{\frac{1}{α}} D^{\frac{1−α}{α}} L^{\frac{1}{α}} + \frac{CL}{α}  and  ∥S|_{X} − U∥_{X→Z} ⩽ \frac{1}{2}.  (103)

Letting I_{Z} : Z → Z denote the identity mapping on Z, we have

∥(S|_{X})U^{−1} − I_{Z} ∥_{Z→Z} = ∥(S|_{X} − U)U^{−1}∥_{Z→Z} ⩽ ∥S|_{X} − U∥_{X→Z}∥U^{−1}∥_{Z→X} ⩽^{(93)∧(103)} \frac{1}{2}.

Consequently, the operator (S|_{X})U^{−1} : Z → Z is invertible and ∥((S|_{X})U^{−1})^{−1}∥_{Z→Z} ⩽ 2. Define

V =^{def} ((S|_{X})U^{−1})^{−1}S : Y → Z.

Then V extends S and

∥V ∥_{Y →Z} ⩽ ∥((S|_{X})U^{−1})^{−1}∥_{Z→Z} ∥S∥_{Y →Z} ⩽ 2∥S∥_{Y →Z} ≲^{(103)} αM^{1−α}m^{\frac{1−α}{2α}} C^{\frac{1}{α}} D^{\frac{1−α}{α}} L^{\frac{1}{α}} + \frac{CL}{α}. □

Given a normed space (Y, ∥ · ∥_{Y}) and a linear subspace X ⊆ Y, the projection constant of X relative to Y is denoted λ(X, Y). Thus λ(X, Y) is the infimum over those λ ∈ [1, ∞] for which there exists a linear projection P from Y onto X with ∥P ∥_{Y →X} ⩽ λ.

Corollary 24. Let κ be the universal constant from Theorem 23. Fix α ∈ (0, 1], M, m ∈ ℕ and D ∈ [1, ∞). Let X ⊆ Y be an m-dimensional subspace of Y whose Banach–Mazur distance to ℓ_{2}^{m} is at most D. For every ε ∈ (0, 1) let 𝒩_{ε} be an ε-net in S_{X}. Then,

ε ⩽ \frac{κ^{\frac{1}{α}} M^{1−α}}{\sqrt{m}Dλ(X, Y)} ⟹ e^{α}(Y, 𝒩_{ε}, ℓ_{2}^{m}) ≳ \frac{λ(X, Y)^{α}}{m^{\frac{1−α}{2}} M^{α(1−α)}D^{2−α}} .  (104)

In particular, there exists n ∈ ℕ satisfying log n ≍ m (\frac{1}{α} + log m) for which

min \{e^{α}(Y, ℓ_{2}^{m}), e_{n}^{α}(Y, ℓ_{2}^{m})\} ≳ \frac{λ(X, Y)^{α}}{m^{\frac{1−α}{2}} M^{α(1−α)}D^{2−α}} .  (105)

Proof. Since the Banach–Mazur distance of X to ℓ_{2}^{m} is at most D, the lower bound on e^{α}(Y, 𝒩_{ε}, ℓ_{2}^{m}) that appears in (104) will follow if we show that

e^{α}(Y, 𝒩_{ε}, X) ≳ \frac{λ(X, Y)^{α}}{m^{\frac{1−α}{2}} M^{α(1−α)}D^{1−α}} .  (106)

We may assume from now on that

e^{α}(Y, 𝒩_{ε}, X) ⩽ \frac{λ(X, Y)^{α}}{m^{\frac{1−α}{2}} M^{α(1−α)}D^{1−α}} ,  (107)

since otherwise there is nothing to prove. By the assumption on ε in (104) combined with (107),

ε ⩽ \frac{κ^{\frac{1}{α}} M^{1−α}}{\sqrt{m}Dλ(X, Y)} ⩽ (\frac{κ}{\sqrt{m}De^{α}(Y, 𝒩_{ε}, Z)})^{\frac{1}{α}} .

We can therefore apply Theorem 23 with Z = X and U = I_{X} being the identity on X (in particular, C = 1). The operator V : Y → X thus obtained is a projection onto X, since V |_{X} = I_{X}. Hence,

λ(X, Y) ⩽ ∥V ∥_{Y →X} ≲^{(95)} αM^{1−α}m^{\frac{1−α}{2α}} D^{\frac{1−α}{α}} e^{α}(Y, 𝒩_{ε}, X)^{\frac{1}{α}} + \frac{e^{α}(Y, 𝒩_{ε}, X)}{α}

≲ \frac{M^{1−α}m^{\frac{1−α}{2α}} D^{\frac{1−α}{α}} e^{α}(Y, 𝒩_{ε}, X)^{\frac{1}{α}}}{α} ,

which simplifies to give the desired estimate (106).

To deduce (105), note that by the Kadec′–Snobar theorem [KS71] we have λ(X, Y) ⩽ \sqrt{m} and by John’s theorem [Joh48] we have D ⩽ \sqrt{m}. Therefore, if we choose ε = κ^{1/α}/m^{3/2} then the upper bound on ε that appears in (104) holds true. It remains to note that if we set n = |𝒩_{ε}| then min{e^{α}(X, ℓ_{2}^{m}), e_{n}^{α}(X, ℓ_{2}^{m})} ⩾ e^{α}(Y, 𝒩_{ε}, X), and by standard estimates (e.g. [MS86]) on the size of ε-nets in m-dimensional normed spaces we have log n ≍ m log(1/ε) ≍ m(log m + 1/α). □

The following corollary implies (67), thus completing the proof of Theorem 4.

Corollary 25. For arbitrarily large m, n ∈ ℕ and every α ∈ (1/2, 1] we have

e^{α}(ℓ_{1}, ℓ_{2}^{m}) ≳ m^{α^{2}− \frac{1}{2}}  and  e_{n}^{α}(ℓ_{1}, ℓ_{2}) ≳ (\frac{log n}{log log n})^{α^{2}− \frac{1}{2}} .

Proof. By [FLM77, Kaš77], for every m ∈ ℕ there exists an integer M = O(m) and an mdimensional subspace X of ℓ_{1}^{M} whose Banach–Mazur distance to ℓ_{2}^{m} is O(1). By [Rut65], we have λ(X, ℓ_{1}^{M}) ≳ \sqrt{m}. Therefore, an application of Corollary 24 with D = O(1), and M = O(m) shows that there exists n ∈ ℕ with log n ≍ m log m such that

min \{e^{α}(ℓ_{1}^{M}, ℓ_{2}^{m}), e_{n}^{α}(ℓ_{1}^{M}, ℓ_{2}^{m})\} ≳ \frac{m^{\frac{α}{2}}}{m^{\frac{1−α}{2} +α(1−α)}} = m^{α^{2}− \frac{1}{2}} ≍ (\frac{log n}{log log n})^{α^{2}− \frac{1}{2}} .  □

References

[Ach03] D. Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. System Sci., 66(4):671–687, 2003. Special issue on PODS 2001 (Santa Barbara, CA).

[AFH^{+}04] A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and É. Tardos. Approximate classification via earthmover metrics. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1079–1087 (electronic). ACM, New York, 2004.

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

[Bal13] K. Ball. The Ribe programme. Astérisque, (352):Exp. No. 1047, viii, 147–159, 2013. Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058.

[Beg99] B. Begun. A remark on almost extensions of Lipschitz functions. Israel J. Math., 109:151–155, 1999.

[BFdlV82] B. Bollobás and W. Fernandez de la Vega. The diameter of random regular graphs. Combinatorica, 2(2):125–134, 1982.

[BL00] 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. ISBN 0-8218-0835-4.

[Bou81] J. Bourgain. A counterexample to a complementation problem. Compositio Math., 43(1):133–144, 1981.

[Bou87] J. Bourgain. Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 157–167. Springer, Berlin, 1987. doi:10.1007/BFb0078143.

[CKNZ05] C. Chekuri, S. Khanna, J. Naor, and L. Zosin. A linear programming formulation and approximation algorithms for the metric labeling problem. SIAM J. Discrete Math., 18(3):608–625, 2004/05.

[CKR05] G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. SIAM J. Comput., 34(2):358–372, 2004/05.

[Die10] R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Heidelberg, fourth edition, 2010. ISBN 978-3-642-14278-9. doi:10.1007/978-3-642-14279-6.

[DJP^{+}94] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity

of multiterminal cuts. SIAM J. Comput., 23(4):864–894, 1994.

[Dvo61] A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pages 123–160. Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961.

[Enf69] P. Enflo. On the nonexistence of uniform homeomorphisms between L_{p}-spaces. Ark. Mat., 8:103–105, 1969.

[FHRT03] J. Fakcharoenphol, C. Harrelson, S. Rao, and K. Talwar. An improved approximation algorithm for the 0-extension problem. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), pages 257–265. ACM, New York, 2003.

[FJS88] T. Figiel, W. B. Johnson, and G. Schechtman. Factorizations of natural embeddings of l_{p}^{n} into L_{r}. I. Studia Math., 89(1):79–103, 1988.

[FLM77] T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53–94, 1977.

[FTJ79] T. Figiel and N. Tomczak-Jaegermann. Projections onto Hilbertian subspaces of Banach spaces. Israel J. Math., 33(2):155–171, 1979.

[HLW06] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439–561 (electronic), 2006.

[HW71] T. L. Hayden and J. H. Wells. On the extension of Lipschitz-Hölder maps of order β. J. Math. Anal. Appl., 33:627–640, 1971.

[JL84] 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.

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

[Joh48] F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187–204. Interscience Publishers, Inc., New York, N. Y., 1948.

[Kal04] N. J. Kalton. Spaces of Lipschitz and Hölder functions and their applications. Collect. Math., 55(2):171– 217, 2004.

[Kal12] N. J. Kalton. The uniform structure of Banach spaces. Math. Ann., 354(4):1247–1288, 2012.

[Kar98] A. V. Karzanov. Minimum 0-extensions of graph metrics. European J. Combin., 19(1):71–101, 1998. [Kaš77] B. S. Kašin. The widths of certain finite-dimensional sets and classes of smooth functions. Izv. Akad.

Nauk SSSR Ser. Mat., 41(2):334–351, 478, 1977.

[Kir34] M. D. Kirszbraun. Über die zusammenziehenden und Lipschitzchen Transformationen. Fundam. Math., 22:77–108, 1934.

[KKMR09] H. Karloff, S. Khot, A. Mehta, and Y. Rabani. On earthmover distance, metric labeling, and 0-extension. SIAM J. Comput., 39(2):371–387, 2009.

[KRTJ80] H. König, J. R. Retherford, and N. Tomczak-Jaegermann. On the eigenvalues of (p, 2)-summing operators and constants associated with normed spaces. J. Funct. Anal., 37(1):88–126, 1980.

[KS71] M. Ĭ. Kadec′ and M. G. Snobar. Certain functionals on the Minkowski compactum. Mat. Zametki, 10:453– 457, 1971.

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

[Lew78] D. R. Lewis. Finite dimensional subspaces of L_{p}. Studia Math., 63(2):207–212, 1978.

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

[LN03] J. R. Lee and A. Naor. Metric decomposition, smooth measures, and clustering, 2003. Preprint, available on request.

[LN04] J. R. Lee and A. Naor. Absolute Lipschitz extendability. C. R. Math. Acad. Sci. Paris, 338(11):859–862, 2004.

[LN05] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

[Mat97] J. Matoušek. On embedding expanders into l_{p} spaces. Israel J. Math., 102:189–197, 1997.

[Mat02] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. ISBN 0-387-95373-6. doi:10.1007/978-1-4613-0039-7.

[Mau74] B. Maurey. Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces L^{p}. Société Mathématique de France, Paris, 1974. With an English summary, Astérisque, No. 11.

[Men27] K. Menger. Zur allgemeinen Kurventheorie. Fundam. Math., 10:96–115, 1927.

[Min70] G. J. Minty. On the extension of Lipschitz, Lipschitz-Hölder continuous, and monotone functions. Bull. Amer. Math. Soc., 76:334–339, 1970.

[MM10] K. Makarychev and Y. Makarychev. Metric extension operators, vertex sparsifiers and Lipschitz extendability. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science FOCS 2010, pages 255–264. IEEE Computer Soc., Los Alamitos, CA, 2010.

[MN13a] M. Mendel and A. Naor. Spectral calculus and Lipschitz extension for barycentric metric spaces. Anal. Geom. Metr. Spaces, 1:163–199, 2013.

[MN13b] M. Mendel and A. Naor. Ultrametric skeletons. Proc. Natl. Acad. Sci. USA, 110(48):19256–19262, 2013.

[MN15] M. Mendel and A. Naor. Expanders with respect to Hadamard spaces and random graphs, 2015. To appear in Duke Math. J.

[MP84] 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.

[MS86] V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. ISBN 3-540-16769-2. With an appendix by M. Gromov.

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

[Nao12] A. Naor. An introduction to the Ribe program. Jpn. J. Math., 7(2):167–233, 2012.

[NPSS06] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromovhyperbolic metric spaces. Duke Math. J., 134(1):165–197, 2006.

[NRS05] A. Naor, Y. Rabani, and A. Sinclair. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal., 227(2):273–303, 2005.

[Pis79] G. Pisier. Estimations des distances à un espace euclidien et des constantes de projection des espaces de Banach de dimension finie; d’après H. König et al. In Séminaire d’Analyse Fonctionnelle (1978–1979), pages Exp. No. 10, 21. École Polytech., Palaiseau, 1979.

[Rut65] D. Rutovitz. Some parameters associated with finite-dimensional Banach spaces. J. London Math. Soc., 40:241–255, 1965.

[Vil03] C. Villani. Topics in optimal transportation, volume 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2003. ISBN 0-8218-3312-X.

[Woj91] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991.

Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544-1000, USA.

   E-mail address: naor@math.princeton.edu

The Rachel and Selim Benin School of Computer Science and Engineering, Jerusalem 91904, Israel.

   E-mail address: yrabani@cs.huji.ac.il