Limitations to Fréchet’s Metric Embedding Method

Yair Bartal^{∗}  Nathan Linial^{†}  Manor Mendel^{‡}  Assaf Naor

July 10, 2003

Abstract

Fréchet’s classical isometric embedding argument has evolved to become a major tool in the study of metric spaces. An important example of a Fréchet embedding is Bourgain’s embedding [4]. The authors have recently shown [2] that for every ε > 0 any n-point metric space contains a subset of size at least n^{1−ε} which embeds into ℓ_{2} with distortion O(\frac{log(2/ε)}{ε}). The embedding used in [2] is non-Fréchet, and the purpose of this note is to show that this is not coincidental. Specifically, for every ϵ > 0, we construct arbitrarily large n-point metric spaces, such that the distortion of any Fréchet embedding into ℓ_{p} on subsets of size at least n^{1/2+ϵ} is Ω ((log n)^{1/p}).

1 Introduction

Given two metric spaces (X, d_{X}), (Y, d_{Y}) and an embedding f : X → Y, the distortion of f is defined as:

dist(f) = sup_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} \frac{d_{Y} (f(x), f(y))}{d_{X}(x, y)} · sup_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} \frac{d_{X}(x, y)}{d_{Y} (f(x), f(y))}.

We denote by c_{Y} (X) the least distortion with which X may be embedded in Y. When c_{Y} (X) ≤ α we say that X α-embeds into Y and denote X ↪^{α} Y. When there is a bijection f between two metric spaces X and Y with dist(f) ≤ α we say that X and Y are α-equivalent. For a class of metric spaces M, c_{M}(X) is the minimum α such that X α-embeds into some metric space in M. For p ≥ 1 we denote c_{ℓ_{p}}(X) by c_{p}(X). The parameter c_{2}(X) is known as the Euclidean distortion of X. A fundamental result of Bourgain [4] states that c_{2}(X) = O(log n) for every n-point metric space (X, d).

For a general metric space (X, d) with no additional a-priori structure, there is a dearth of genuinely ”interesting” constructions of Lipschitz mappings on X. One significant exception to this rule is provided by the distance functions x ↦ d(x, A) for some ∅ ≠ A ⊂ X. Of course, we can generate more examples by constructing Lipschitz functions to any finite dimensional normed space, the coordinates of which are distance functions. Observe that a mapping f : X → ℓ_{∞} is L-Lipschitz if and only if each of its coordinates is L-Lipschitz. These facts were put to good use in the classical observation of Fréchet that every metric space isometrically embeds into some ℓ_{∞}(Γ) (see [3, 9]). Fréchet’s embedding only uses distance functions for singleton A’s, but more sophisticated refinements of this basic idea have appeared over the years. In what follows we call an embedding f : X → ℝ^{2^{V} \{∅}} a Fréchet embedding if for every A ⊂ X there is α_{A} ∈ ℝ such that f(x) = (α_{A}d(x, A))_{A∈2^{X}\{∅}}.

∗Supported in part by a grant from the Israeli National Science Foundation

†Supported in part by a grant from the Israeli National Science Foundation

‡Supported in part by the Landau Center.

Bourgain’s embedding of finite metric spaces in ℓ_{2} [4] is an instance of a Fréchet embedding in which the coefficients α_{A} ∈ [0, 1] depends only on the cardinality of A. Bourgain’s probabilistic method of producing a good Fréchet embedding has subsequently found many applications [6, 7, 8, 10, 5, 12].

As stated in the abstract, the present note is motivated by our recent Ramsey-type result:

Theorem 1 ([2]). There exists an absolute constant C > 0 such that for every α > 2, any finite metric M contains a subset N ⊂ M for which |N| ≥ |M|^{1−C \frac{log α}{α}} and c_{2}(N) ≤ α.

The embedding used in Theorem 1 is not a Fréchet embedding. In view of the past success of Fréchet embeddings, and in particular Bourgain’s embedding which gives the asymptotically best possible bound for embedding the whole metric space, it is natural to ask whether this (by now standard) method is applicable to Ramsey-type problems. This note provides a negative answer to this question. We find a certain range of the parameters, for which Fréchet embeddings fail to achieve tight bounds for Ramsey type questions:

Theorem 2. For every 1/2 < δ ≤ 1 there is a constant C(δ) > 0 such that for infinitely many integers n there are n-point metric spaces M_{n}, such that for any Fréchet embedding f : M_{n} → ℓ_{p}, and any subset V of M_{n} of size at least n^{δ}, dist(f|_{V}) ≥ (C(δ) · log n)^{1/p}.

We end the paper with a short discussion in which we comment on the embedding used in Theorem 1, showing that it can be viewed as a different natural generalization of Bourgain’s embedding.

2 The Construction

Theorem 2 is proved by exhibiting an explicit example of an unbounded family of metric spaces for which every Fréchet embedding fails to yield the appropriate Ramsey type result. The example, denoted Z = Z_{k,ε,h,m}, is an amalgamation of two types of metric spaces:

• The elements of the first metric space, called X = L_{h,k}, are the leaves of a complete binary tree T_{h} of height h. The metric on the leaves is defined by

d_{X}(x_{1}, c_{2}) = k^{−l(lca(x_{1},x_{2}))}.

Here lca(x_{1}, x_{2}) denotes the least common ancestor of x_{1} and x_{2} in T_{h} and l(u) is the depth of the vertex u in T. The parameter k > 1 will be be fixed later. A crucial property of X is that for any x, y, z ∈ X, if d_{X}(x, y) < d_{X}(x, z), then

d_{X}(x, z) = d_{X}(y, z) ≥ kd_{X}(x, y)  (1)

(Such a metric space is called a k-HST [1]).

• The second metric space, Y = Y_{m,ε}, is the one-dimensional metric on the points

Y = \{y_{0} = ε, y_{1} = ε (1 + \frac{1}{4}) , y_{2} = ε (1 + \frac{1}{4} + \frac{1}{16}) , …, y_{m−1} = ε (∑_{i=0}^{m−1} 4^{−i})\} .

k^{−3}^{k^{−2}}^{k^{−1}}^{1}  ^{k^{−3}}^{k^{−2}}^{k^{−1}}^{1} X=L_{h}^{k}^{h = 4 levels}  Z^{y_{0}} Y

Figure 1: The metric space Z serving as the example in Theorem 2.

The points set of Z is X × Y, hence its size is 2^{h}m. The distance is defined by

d_{Z}((x, y), (x′, y′)) = \begin{cases}d_{Y} (y, y′) & x = x′ \\ d_{Y} (y, y_{0}) + d_{X}(x, x′) + d_{Y} (y_{0}, y′) & x ≠ x′. \end{cases}

A schematic description of Z is given in Figure 1.

Here is a sketch of our proof. A preliminary step (Lemma 1) shows that all sufficiently large (of size ≥ n^{\frac{1}{2} +ϵ}) subsets V ⊆ Z have a structure that is similar to the whole of Z. Namely, there is a large subset U ⊆ V that spans a complete binary subtree (of a slight modification) of T . Moreover, in each copy of Y that U meets, it contains at least two elements.

From this point on, we may assume, then, that we are dealing with a space that is similar to the original Z with two modifications: The depth has shrunk to one half its original value, (since we moved from n to n^{\frac{1}{2} +ϵ} points) and attached to each leaf is a tail i.e., a two-point metric space. On the other hand, we are now considering the whole of this (sub)space, and not subsets thereof. (We actually cannot ignore the points in Z \ U, which may participate in the subsets to which Fréchet embedding assigns nonzero weights. However, this is only a technicality and can be ignored at this level of discussion.)

Recall that we are dealing with Fréchet embeddings f that are defined by assigning weights α_{A} to subsets A. Consider a tail {y_{1}, y_{2}}, and suppose that A is disjoint from the copy of Y to which y_{1}, y_{2} belong. Then |d(y_{1}, A) − d(y_{2}, A)| = d(y_{1}, y_{2}), entailing a lower bound on Lip(f). In other words, if large weights α_{A} are allotted to subsets A that miss many tails, then Lip(f) is big. This is made precise in Lemma 2, which gives a lower bound on Lip(f) in terms of the numbers α_{A} and ζ_{A} - the fraction of tails that A misses.

It follows that in order to keep Lip(f) small, we ought to put significant weights α_{A} on subsets with large ζ_{A} i.e., those that meet many tails. This, however, tends to increase Lip(f^{−1}), as we now explain. Let z_{1} and z_{2} belong to two distinct tails. In order for |d(z_{1}, A)− d(z_{2}, A)| to be nearly equal to d(z_{1}, z_{2}), the set A must meet exactly one of the two tails containing the z_{i} (in which case we say that A splits the least common ancestor of z_{1}, z_{2}). It is not hard to see (Equation 4) that if ζ_{A} is large, then A can split only a few vertices, and these necessarily reside far from the root. Note also that if A fails to split lca(z_{1}, z_{2}), then |d(z_{1}, A) − d(z_{2}, A)| ≤ \frac{1}{k}d(z_{1}, z_{2}), which is significant, since k is large. The precise argument is made in Lemma 4.

Omitting some additional technicalities (Lemma 3), these two considerations can be traded off against each other to yield the desired result.

Some notations and definitions concerning trees:

1. Let T be a tree. We denote its root by r(T ) and its set of leaves by leaves(T ). For a subset A ⊂ leaves(T ) let T (A) be the subtree spanned by A, i.e. the union of all the simple paths between elements of A and lca(A). The subtree T_{u} rooted at u consists of the union of all the monotone paths in T between u and its descendants. We recall that l_{T} (u) is the depth of u, i.e. its distance from r(T ).

2. Let T = (V, E) be a tree and suppose that T contains a vertex u ≠ r(T ) with exactly two neighbors v and w. We simplify T by removing the vertex u and adding the edge (v, w). Another type of simplification step takes place, if r(T ) has a single neighbor v. In this case, we remove r(T ) and declare v as the root. The skeleton skel(T ) is the (uniquely defined) tree obtained from T by carrying out all possible simplifications.

3. For a subset U ⊂ Z, we denote U_{X} = {x ∈ X; ({x} × Y) ∩ U ≠ ∅}.

Lemma 1. Let h, m ≥ 2 be integers, and Z = Z_{k,ε,h,m}. Let V ⊂ Z be such that |V | > 2m+2^{h}. Denote

ρ = (\frac{|V | − 2^{h}}{m} )^{1/h} − 1.

Then there is a subset U ⊂ V such that for every x ∈ U_{X}, |({x}×Y)∩U| ≥ 2 and skel(T_{h}(U_{X})) is a complete binary tree of depth at least \frac{ρ}{6 log(2/ρ)}h.

Proof. Denote S = {x ∈ X; |V ∩ ({x} × Y)| ≥ 2}. Since |S|m + 2^{h} ≥ |V |, we have that

|S| ≥ \frac{|V | − 2^{h}}{m} = (1 + ρ)^{h} > 2.

Set 0 < η = \frac{ρ}{2+ρ} < 0.5. We will first construct inductively a subtree T′ of T , as follows. Let r be the root of T and u_{1}, u_{2} its two children. Recursively, assume that we have constructed T′_{u_{1}}, T′_{u_{2}}. T′ is constructed according to the following rule: if min{|leaves(T_{u_{1}}) ∩ S|, |leaves(T_{u_{2}}) ∩ S|} ≥ η|S| then T′ is obtained by attaching T′_{u_{1}} and T′_{u_{2}} to r. Otherwise, assume without loss of generality that |leaves(T_{u_{1}}) ∩ S| > (1 − η)|S|. In this case T′ is obtained by attaching only T_{u_{1}} to r. Note that in the previous step of this procedure, T′_{u_{i}} were constructed with respect to sets leaves(T_{u_{i}}) ∩ S.

Let u be a leaf of skel(T′) and denote its distance from the root of skel(T′) by λ. Consider the path in T between r (the root of T ) and u. Clearly λ is precisely the number of times along this path that the first option was taken in the above construction. We prove by induction on h, the height of T , that |S|η^{λ}(1 − η)^{h−λ} ≤ 1. The case h = 0 is trivial, so assume that h > 0.

Let r, u_{1}, u_{2} be as above, and assume that u_{1} belongs to the path connecting r and u. In the first case of the above construction, we get by the induction hypothesis that:

1 ≥ |leaves(T_{u_{1}}) ∩ S|η^{λ−1}(1 − η)^{h−1−(λ−1)} ≥ |S|η^{λ}(1 − η)^{h−λ}.

In the second case of the above construction we get

1 ≥ |leaves(T_{u_{1}}) ∩ S|η^{λ}(1 − η)^{h−1−λ} ≥ |S|η^{λ}(1 − η)^{h−λ}.

Let ĥ be the minimal distance between a leaf of skel(T′) and its root. From the discussion above (and noting that ρ < 1) it follows that:

ĥ ≥ \frac{log |S| + h log(1 − η)}{log (\frac{1−η}{η} )} ≥ \frac{h log(1 + ρ) + h log(\frac{2}{2+ρ})}{log (\frac{2}{ρ})} ≥ \frac{ρ}{6 log(2/ρ)}h.

Consider all the vertices of depth exactly ĥ in skel(T′). The tree skel(T′) truncated at these points forms a complete binary tree of height ĥ. For each such vertex u we choose some s_{u} ∈ S ∩ T′_{u}. The set S′ = {s_{u}; u has depth ĥ in skel(T′)} is easily seen to have the required properties.

Our next two lemmas provide a lower bound on the expansion of any Fréchet embedding Z ↪ ℓ_{p}, using (almost) only the structure of Y.

Let f : Z → ℓ_{p}^{2^{Z}\{∅}}, 1 ≤ p < ∞, be a Fréchet embedding given by f(x)_{A} = α_{A}d(x, A), let V ⊆ Z be a large set as in Theorem 2 and Let U ⊂ V be a subset as in Lemma 1. For every ∅ ≠ A ⊂ Z write:

ζ_{A} = \frac{|\{x ∈ U_{X}; (\{x\} × Y) ∩ A = ∅\}|}{|U_{X}|}.

Namely, ζ_{A} is the fraction of of the tails in U that A misses. Define

β(f, U) = ( ∑_{∅≠A⊂Z} |α_{A}|^{p}ζ_{A})^{1/p} .  (2)

Informally, β(f) is a weighted average of the fraction of tails {x} × Y, x ∈ U, that are missed by a subset of Z. If a subset A is disjoint from a tail {x} × Y, that contains the points (x, u), (x, v), then |d_{Z}((x, u), A) − d_{Z}((x, v), A)| = d_{Y} (u, v). Consequently, we can expect to obtain lower bound on the Lipschitz constant of f in terms of β. Indeed:

Lemma 2. Let U ⊂ Z be a subset as in Lemma 1. Then Lip(f|_{U}) ≥ β(f, U).

Proof. We may assume without loss of generality that α_{A} ≥ 0 for every ∅ ≠ A ⊂ Z. Set β = β(f, U). Note that

\frac{1}{|U_{X}|} ∑_{x∈U_{X}} ( ∑_{A: A∩Z_{x}=∅} α_{A}^{p}) = ∑_{∅≠A⊂Z} α_{A}^{p} \frac{|\{x ∈ U_{X}; A ∩ (\{x\} × Y) = ∅\}|}{|U_{X}|} = β^{p}.

Hence there is some x ∈ U_{X} such that ∑_{A: A∩Z_{x}=∅} α_{A}^{p} ≥ β^{p}. As mentioned, if ∅ ≠ A ⊂ Z is disjoint from {x} × Y, then d_{Z}((x, y), A) = d_{Y} (y, y_{0}) + d_{Z}((x, y_{0}), A) for every (x, y) ∈ Z.

Recall that for x ∈ U_{X}, there are y ≠ y′ such that (x, y), (x, y′) ∈ ({x} × Y) ∩ U. Therefore

∥f(x, y) − f(x, y′)∥_{p}^{p} = ∑_{A⊂Z} α_{A}^{p}|d_{Z}((x, y), A) − d_{Z}((x, y′), A)|^{p}

≥ ∑_{\begin{matrix}A⊂Z \\ A∩(\{x\}×Y)=∅ \end{matrix}} α_{A}^{p}|d_{Y} (y_{0}, y) − d_{Y} (y_{0}, y′)|^{p} ≥ β^{p}d_{Z}((x, y), (x, y′))^{p},

so that Lip(f|_{U}) ≥ β.

Similar to the definition of β(f, U), we also define

γ(f, U) = ( ∑_{∅≠A⊅U} α_{A}^{p})^{1/p} .  (3)

In words, γ(f, U) is the weighted average of weights assigned to subsets that do not contain U. The metric of Y, was purposely chosen so that no two distances are equal. Consequently, a subset A ⊅ U makes a nonzero contribution to Lip(f|_{U}). Indeed:

Lemma 3. Let U ⊆ Z be as in Lemma 2. Assume that k ≥ 4, and k^{−h} ≥ ε. Then Lip(f|_{U}) ≥

4^{−m}2^{− \frac{|X|·|Y |}{p}} γ(f, U).

Proof. We may assume again that α_{A} ≥ 0 for every ∅ ≠ A ⊂ Z. Let A_{0} be such that α_{A_{0}} = max{α_{A}; ∅ ≠ A ⊅ U}. Clearly:

α_{A_{0}}^{p} ≥ 2^{−|X|·|Y |} ∑_{∅≠A⊅V} α_{A}^{p}.

Since A_{0} ⊅ U, there is some (x, u) ∈ U \ A_{0}. By assumption, U contains some (x, v) with v ≠ u. It is enough to show that |d_{Z}((x, u), A_{0}) − d_{Z}((x, v), A_{0})| ≥ 4^{−m} · diam(Y), since then:

∥f(x, u)−f(x, v)∥_{p} ≥ α_{A_{0}}|d_{Z}((x, u), A_{0})−d_{Z}((x, v), A_{0})| ≥ 4^{−m}α_{A_{0}}diam(Y) ≥ 4^{−m}α_{A_{0}}d_{Y} (u, v),

and the result will follow from the lower estimate for α_{A_{0}}.

To verify that |d_{Z}((x, u), A_{0}) − d_{Z}((x, v), A_{0})| ≥ 4^{−m} · diam(Y), distinguish between the possible points where the distances d_{Z}((x, u), A_{0}) and d_{Z}((x, v), A_{0}) are attained. Let (x′, a) ∈ A_{0}, (x′′, b) ∈ A_{0} satisfy d_{Z}((x, u), A_{0}) = d_{Z}((x, u), (x′, a)), d_{Z}((x, v), A_{0}) = d_{Z}((x, v), (x′′, b)). Observe that since k^{−h} > ε/3 > diam(Y), if x ∈ {x′, x′′} then x′ = x′′ = x, in which case d_{Z}((x, u), A_{0}) = d_{Y} (u, a), d_{Z}((x, v), A_{0}) = d_{Y} (v, b), and we conclude since the definition of the metric on Y implies that |d_{Y} (u, a) − d_{Y} (u, b)| ≥ 4^{−m+1}ε > 4^{−m} diam(Y). Therefore, assuming that x ∉ {x′, x′′}, d_{Z}((x, u), A_{0}) = d_{Y} (u, y_{0}) + d_{X}(x, x′) + d_{Y} (y_{0}, a) and d_{Z}((x, v), A_{0}) = d_{Y} (v, y_{0}) + d_{X}(x, x′′) + d_{Y} (y_{0}, b). If d_{X}(x, x′) = d_{X}(x, x′′), we use the fact that if a, b, u, v ∈ Y but {a, b} ≠ {u, v} then |[d_{Y} (u, y_{0}) + d_{Y} (y_{0}, a)] − [d_{Y} (v, y_{0}) + d_{Y} (y_{0}, b)]| ≥ 4^{−m} diam(Y). On the other hand, if d_{X}(x, x′) ≠ d_{X}(x, x′′) then |d_{X}(x, x′) − d_{X}(x, x′′)| ≥ k^{−h} ≥ ε, and so

|d_{Z}((x, u), A_{0}) − d_{Z}((x, v), A_{0})| ≥ |d_{X}(x, x′) − d_{X}(x, x′′)| −
|d_{Y} (u, y_{0}) − d_{Y} (v, y_{0})| − |d_{Y} (a, y_{0}) − d_{Y} (b, y_{0})|
≥ ε − 2diam(Y) ≥ diam(Y).

Our next lemma uses the special structure of X = L_{h,k} to bound from below the inverse of the contraction, Lip((f|_{U})^{−1}), in terms of β(f, U) and γ(f, U). In what follows we always use the convention that Lip(f^{−1}) = ∞ if f is non injective.

Lemma 4. Let U ⊂ Z be as in Lemma 1 . Then for every Fréchet embedding f : Z → ℓ_{p}^{2^{Z}\{∅}},

Lip ((f|_{U})^{−1}) ≥ [\frac{2β(f, U)^{p}}{ĥ} + (\frac{2 + 2k^{h} diam(Y)}{k})^{p} γ(f, U)^{p}]^{−1/p} .

Proof. We use a shorthand notation T = T_{h}, γ = γ(f, U) and β = β(f, U). We assume as usual that α_{A} ≥ 0 for every ∅ ≠ A ⊂ Z. Denote by T′ = T_{h}(U_{X}) the subtree generated by U_{X}. By our assumption skel(T′) is a complete binary tree of depth ĥ. Let u; u_{1}, u_{2} be a vertex in skel(T′) and its two children in T . We say that a subset A ⊂ Z splits u if A intersects exactly one of the sets leaves(T_{u_{1}}) × Y, leaves(T_{u_{2}}) × Y.

For u ∈ skel(T′), denote by l(u) = l_{skel(T′)}(u) the depth of u in skel(T′). We first claim that for ∅ ≠ A ⊂ Z,

∑_{u∈skel(T′) ; A splits u} 2^{−l(u)} ≤ 2ζ_{A}.  (4)

The proof is by induction on ĥ, the height of skel(T′). Let r be the root of skel(T′). Denote by u_{1}, u_{2} the children of r in T , and by v_{1}, v_{2} the children of r in skel(T′). Set ζ = ζ_{A} and define ζ_{1}, ζ_{2} by:

ζ_{i} = \frac{|\{x ∈ leaves(T′_{v_{i}}); (\{x\} × Y) ∩ A = ∅\}|}{|leaves(T′_{v_{i}})|}, i = 1, 2.

Note that since skel(T′) is a complete binary tree ζ = (ζ_{1} + ζ_{2})/2. If A does not split r then by induction:

∑_{u∈skel(T′) ; A splits u} 2^{−l(u)} = \frac{1}{2} ( ∑_{u∈skel(T′_{v_{1}}) A splits u} 2^{−(l(u)−1)} + ∑_{u∈skel(T′_{v_{2}}) A splits u} 2^{−(l(u)−1)})

≤ \frac{1}{2}(2ζ_{1} + 2ζ_{2}) = 2ζ.

On the other hand, if A splits r, it does not intersect one of leaves(T_{u_{1}})×Y, leaves(T_{u_{2}})×Y, say it does not intersect leaves(T_{u_{2}})×Y. In this case ζ_{2} = 1 so that by the induction hypothesis:

∑_{u∈skel(T′) ; A splits u} 2^{−l(u)} = 1 + \frac{1}{2} ( ∑_{u∈skel(T′_{v_{1}}) A splits u} 2^{−(l(u)−1)}) ≤ 1 + \frac{1}{2}2ζ_{1} = ζ_{2} + ζ_{1} = 2ζ.

This finishes the proof of (4). Now, by the definition of β = β(f, U),

∑_{l=0}^{ĥ−1} ∑_{u∈skel(T′) ; u in depth l ; in skel(T′)} 2^{−l} ∑_{\begin{matrix}∅≠A⊂Z \\ A splits u \end{matrix}} α_{A}^{p} = ∑_{∅≠A⊂Z} α_{A}^{p} ∑_{u∈skel(T′) ; A splits u} 2^{−l(u)} ≤ ∑_{∅≠A⊂Z} α_{A}^{p}2ζ_{A} = 2β^{p}.

It follows that there exists some l ∈ {0, …, ĥ − 1} such that

2^{−l} ∑_{u∈skel(T′) ; u in depth l ; in skel(T′)} ( ∑_{\begin{matrix}∅≠A⊂Z \\ A splits u \end{matrix}} α_{A}^{p}) ≤ \frac{2β^{p}}{ĥ} .

So there exists a vertex u ∈ skel(T′) (in depth l in skel(T′)) such that

∑_{\begin{matrix}∅≠A⊂Z \\ A splits u \end{matrix}} α_{A}^{p} ≤ \frac{2β^{p}}{ĥ} .

Denote by u_{1}, u_{2} the two children of u in T . Since u is a vertex of skel(T′) there are x_{1} ∈ leaves(T_{u_{1}})∩U_{X} and x_{2} ∈ leaves(T_{u_{2}})∩U_{X} (in particular lca(x_{1}, x_{2}) = u). Fix (x_{1}, y_{1}) ∈ U and (x_{2}, y_{2}) ∈ U. The observation here is that if a subset A ⊂ Z does not split u then one of the following two cases happens:

1. A ∩ (T_{u} × Y) = ∅. In this case, d_{Z}((x_{1}, y_{1}), A) = d_{Z}((x_{2}, y_{2}), A), and therefore

|d_{Z}((x_{1}, y_{1}), A) − d_{Z}((x_{2}, y_{2}), A)| = 0.

2. For i = 1, 2 there is x′_{i} ∈ leaves(T_{u_{i}}) and y′_{i}, y′′_{i} ∈ Y such that d_{Z}((x_{i}, y_{i}), A) = d_{Y} (y_{i}, y′_{i})+ d_{X}(x_{i}, x′_{i}) + d_{Y} (y_{0}, y′′_{i}). Hence,

|d_{Z}((x_{1}, y_{1}), A) − d_{Z}((x_{2}, y_{2}), A)| ≤ d_{X}(x_{1}, x′_{1}) + d_{X}(x_{2}, x′_{2}) + 2 diam(Y)
≤ \frac{2}{k} d_{X}(x_{1}, x_{2}) + 2 diam(Y)
≤ \frac{2 + 2k^{h} diam(Y)}{k}d_{Z}((x_{1}, y_{1}), (x_{2}, y_{2})).

Therefore

∥f((x_{1}, y_{1})) − f((x_{2}, y_{2}))∥_{p}^{p} =
= ∑_{\begin{matrix}∅≠A⊂Z \\ A splits u \end{matrix}} α_{A}^{p}|d_{Z}((x_{1}, y_{1}), A) − d_{Z}((x_{2}, y_{2}), A)|^{p}

+ ∑_{∅≠A⊂Z A doesn’t splits u} α_{A}^{p}|d_{Z}((x_{1}, y_{1}), A) − d_{Z}((x_{2}, y_{2}), A)|^{p}

≤ [d_{Z}((x_{1}, y_{1}), (x_{2}, y_{2}))]^{p} ∑_{\begin{matrix}∅≠A⊂Z \\ A splits u \end{matrix}} α_{A}^{p}

+ (\frac{2 + 2k^{h} diam(Y)}{k}d_{Z}((x_{1}, y_{1}), (x_{2}, y_{2})))^{p} ∑_{∅≠A⊅U} α_{A}^{p}

≤ [\frac{2β^{p}}{ĥ} + (\frac{2 + 2k^{h} diam(Y)}{k})^{p} γ^{p}] [d_{Z}((x_{1}, y_{1}), (x_{2}, y_{2}))]^{p}.

Proof of Theorem 2. Let h, m ≥ 2 where ϵ = k^{−h}/2 Define n = m2^{h}, so that |Z| = n.

Let f : Z → ℓ_{p}^{2^{Z}\{∅}} be a Fréchet embedding. Fix 0.5 < δ < 1. We can always choose h and m such that n^{δ} = Ω(2^{h} + mn^{2δ−1}) (2^{h} of order n^{δ} and m of order n^{1−δ}). Fix such h and m, and let V ⊂ Z be such that |V | ≥ n^{δ}. By Lemma 1 there is a subset U ⊂ V which satisfies the conditions of Lemma 4 with ĥ ≥ C(δ) log n. Set β = β(f, U), γ = γ(f, U). It follows from Lemmas 2, 3, 4 that:

dist(f|_{V}) ≥ dist(f|_{U}) ≥ c\frac{max\{β, 2^{−n/p}4^{−m}γ\}}{max \{\frac{β}{(C(δ) log n)^{1/p}} , \frac{γ}{k} \}},

for some universal constant c > 0.

If \frac{β}{(C(δ) log n)^{1/p}} ≥ \frac{γ}{k} then we deduce that dist(f|_{V}) ≥ (C(δ) log n)^{1/p}, as required. Otherwise

we get the lower bound dist(f|_{V}) ≥ ck2^{−n/p}4^{−m}. Recall that we are still free to choose k, so that the required result also follows from this case provided that k is large enough.

3 Discussion

The goal of Theorem 2 has been to provide an example for which Fréchet embeddings fail to achieve the best possible bounds. This is done for the problem of embedding subsets of size at least n^{δ} into ℓ_{p}, where δ > 1/2. We suspect that the same holds also for δ ≤ 1/2. However, the example presented here does not immediately apply to this case.

Finally we comment on a concept due to Matoušek and Rabinovich [11] which is a different natural generalization of Bourgain’s embedding. Given a finite metric space (V, ρ), we say that a one-dimensional metric σ on V is dominated by ρ if ρ(x, y) ≥ σ(x, y) for every x, y ∈ V. The polytope ℓ_{1}^{dom}(ρ) is the convex hull of all one-dimensional metrics dominated by ρ. It is natural to ask whether embeddings into ℓ_{1}^{dom} can be used for Ramsey-type problems. We observe that this is indeed the case. The following theorem is a consequence of the main Ramsey-type theorem of [2]:

Theorem 3. For every finite metric M, and every α > 2, there exists a subset N ⊂ M of cardinality ≥ |M|^{1−C \frac{log α}{α}} that is α-equivalent to some metric in ℓ_{1}^{dom}(N). Here C > 0 is an absolute constant.

The proof of Theorem 3 is in two steps: (i) We recall that Theorem 1 follows from a Ramsey-type theorem of [2] where the target metric space for the embedding is an ultrametric (which is isometrically embeddable in ℓ_{2}). (ii) Every ultrametric ρ is O(1)-equivalent to some metric in ℓ_{1}^{dom}(ρ). This is a simple fact, a proof of which, is sketched below.

Proposition 5. Every ultrametric ρ is 16-equivalent to some metric in ℓ_{1}^{dom}(ρ).

Sketch of a proof. As shown in [2], ρ has a 4-embedding in some 4-HST. So, it suffices to prove that ρ is 4 equivalent to some metric in ℓ_{1}^{dom}(ρ) for the case where ρ itself is a 4-HST metric. Let us recall: A k-HST is defined by a tree T in which every internal vertex v is assigned a weight Δ(v) > 0. If v is a child of u then Δ(u) ≥ kΔ(v). The metric is defined of T ’s leaves via d(x, y) = Δ(lca(x, y)). The metric in ℓ_{1}^{dom}(ρ) that is 4-equivalent to ρ is constructed through a probabilistic argument. Associate with every edge e = uv a weight ϵ_{e} ∈ \{−\frac{3}{8}, \frac{3}{8}\}. This is done uniformly and independently over all edges. Associated with this is a mapping φ = φ_{ϵ} of T ’s leaves to the real line, φ(x) = ∑ Δ(u)ϵ_{uv}. This sum extends over all edges uv in the directed path from T ’s root to x. It is easy to verify that the one dimensional metric induced on the leaves is dominated by ρ. This is now averaged over all possible choices of the ϵ_{e}’s.

References

[1] Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, pages 184–193, 1996.

[2] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Metric Ramsey-type Phenomena. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003.

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

[4] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[5] U. Feige. Approximating the bandwidth via volume respecting embeddings. J. Comput. System Sci., 60(3):510–539, 2000.

[6] William B. Johnson, Joram Lindenstrauss, and Gideon Schechtman. On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 177–184. Springer, Berlin, 1987.

[7] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

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

[9] J. Matoušek. Lectures on discrete geometry. Springer-Verlag, New York, 2002.

[10] Jiří Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math., 93:333–344, 1996.

[11] Jiří Matoušek and Yuri Rabinovich. On dominated l_{1} metrics. Israel J. Math., 123:285– 301, 2001.

[12] M. Thorup and U. Zwick. Approximate distance oracles. In 33rd Annual ACM Symposium on Theory of Computing, pages 183–192, 2001.

Yair Bartal, Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. yair@cs.huji.ac.il

Nathan Linial, Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. nati@cs.huji.ac.il

Manor Mendel, Institute of Computer Science, Hebrew University, Jerusalem 91904, Israel. mendelma@cs.huji.ac.il

Assaf Naor, Theory Group, Microsoft Research, One Microsoft Way 113/2131, Redmond WA 98052-6399, USA. anaor@microsoft.com