On Metric Ramsey-type Dichotomies

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

January 2, 2003

Abstract

The classical Ramsey theorem, states that every graph contains either a large clique or a large independent set. Here we investigate similar dichotomic phenomena in the context of finite metric spaces. Namely, we prove statements of the form ”Every finite metric space contains a large subspace that is nearly equilateral or far from being equilateral”. We consider two distinct interpretations for being ”far from equilateral”. Proximity among metric spaces is quantified through the metric distortion α. We provide tight asymptotic answers for these problems. In particular, we show that a phase transition occurs at α = 2.

1 Introduction

A Ramsey-type theorem states that large systems necessarily contain large, highly structured sub-systems. Here we consider Ramsey-type problems for finite metric spaces, and interpret “highly structured” as being embeddable with low distortion in some “simple” metric spaces.

A mapping between two metric spaces f : M → X, is called an embedding of M in X. The distortion of the embedding is defined as

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

The least distortion attainable by any embedding of M in X is denoted by c_{X}(M). When c_{X}(M) ≤ α we say that M α-embeds in X. When M α-embeds in X via a bijection, we say that M and X are α-equivalent.

This paper deals with the following notion.

Definition 1 (Metric Ramsey function). For a given class of metric spaces X we denote by R_{X} (α, n) the largest integer m such that any n-point metric space has a subspace of size m that α-embeds into some X ∈ X. When X = {ℓ_{p}} we use the notation R_{p}.

In [7], Bourgain, Figiel, and Milman study this function for X = {ℓ_{2}}, as a non-linear analog of the classical Dvoretzky theorem [8]. They prove

Theorem 1 ([7]). For any α > 1 there exists C(α) > 0 such that R_{2}(α, n) ≥ C(α) log n. Furthermore, there exists α_{0} > 1 such that R_{2}(α_{0}, n) = O(log n).

∗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.

Lower bounds which improve on Theorem 1 for large α were obtained in [2], and the Euclidean metric-Ramsey problem was comprehensively studied in [3]. There, the lower bound on R_{2} was achieved via embedding into a special type of ℓ_{2} metrics, namely ultrametrics. Denote by UM the class of ultrametrics. The following phase transition was established.

Theorem 2 ([3]). Let n ∈ ℕ. Then:

1. For every 1 < α < 2,

c(α) log n ≤ R_{UM}(α, n) ≤ R_{2}(α, n) ≤ 2 log n + C(α),

where c(α), C(α) may depend only on α.

2. For every α > 2,

n^{c′(α)} ≤ R_{UM}(α, n) ≤ R_{2}(α, n) ≤ n^{C′(α)},

where c′(α), C′(α) depend only on α and satisfy max \{0, 1 − \frac{c log α}{α}\} < c′(α) < C′(α) <

min \{1, 1 − \frac{C}{α} \}, with c, C > 0 universal constants.

In [4], a similar phase transition phenomenon is proved for embeddings in ℓ_{p}, p ∈ [1, 2).

A natural refinement of ultrametrics was suggested in [1].

Definition 2 ([1]). For k ≥ 1, a k-hierarchically well-separated tree (k-HST) is a metric space whose elements are the leaves of a rooted tree T. To each vertex u ∈ T, a label Δ(u) ≥ 0 is associated such that Δ(u) = 0 iff u is a leaf of T. The labels are such that if a vertex u is a child of a vertex v then Δ(u) ≤ Δ(v)/k . The distance between two leaves x, y ∈ T is defined as Δ(lca(x, y)), where lca(x, y) is the least common ancestor of x and y in T. T is called the defining tree of the HST.

The notion of an ultrametric is easily seen to coincide with that of a 1-HSTs.

In [3], the Ramsey problem of embedding into k-HSTs was also studied.

Theorem 3 ([3]). For any ε ∈ (0, 1], and any k ≥ 1,

R_{k-HST}(2 + ε, n) ≥ n^{\frac{cε}{log(2k/ε)}} .

In this note we study Ramsey problems closer in spirit to the original Ramsey problem in combinatorics, which is of a dichotomic nature. More specifically, such theorems state that every metric space contains a large subspace which is close to one of two extremal types of simple metric spaces. In this note we consider two different (but related) type of dichotomies.

We begin with some motivation. Since every 3-point metric is isometric to a Euclidean triangle, we can associate with it three angles. We say that two 3-point metrics are ϵ-similar, if the corresponding angles differ by at most ϵ. Fix some ϵ > 0. The collection of all 3-point metrics can be partitioned into a constant number of classes such that every two triples in the same class are ϵ-similar. By Ramsey’s theorem, every n-point metric space contains a large homogeneous subset, namely a set of f = f(n) elements, every two triples in which are ϵ-similar, where f tends to ∞ with n. It is not hard, however, to show that there are only two types of unboundedly large homogeneous sets. Either all triples in such a class are ϵ-similar to the equilateral triangle with angles (60^{∘}, 60^{∘}, 60^{∘}) or all are ϵ-similar to a triple in which the smallest angle is at most ϵ^{2}, say. In the latter case, in fact, more is true.

The Metric dichotomy. In the first type of dichotomy treated, which we call the metric dichotomy, we have on one hand equilateral spaces, i.e. metric spaces in which all pairwise distances are equal. The “opposite” extreme are spaces in which every triple of points is far (in the sense of metric distortion) from being an equilateral triangle. We define F_{k}(α, n) as the largest m such that any n point metric space contains an m-point subspace which is either α-equivalent to an equilateral space or α-equivalent to a space for which every triple of points has distortion at least k from an equilateral triangle.

The notion of spaces in which no triple is k-equivalent to an equilateral triangle is quite natural. It turns out, however, that in order to analyze the behavior of F_{k}, it is more convenient (and essentially equivalent) to consider instead binary k-HSTs, i.e. k-HSTs whose defining tree is binary (every vertex has at most two children). The relevant dichotomic Ramsey function is defined as

E_{k}(α, n) = R_{\begin{cases}binary k-HSTs \\ or equilateral spaces \end{cases}\}}(α, n).

The relation between these notions is clarified in the following proposition.

Proposition 1. The following two assertions hold:

1. Let M be a binary k-HST and let S ⊂ M, have cardinality |S| ≥ 3. Then

c_{{equilateral spaces}}(S) ≥ k.

2. Let M be a metric space in which c_{{equilateral spaces}}(S) ≥ k for every S ⊂ M with |S| ≥ 3, where k > 2. Then M is \frac{k}{k−2}-equivalent to a binary \frac{k}{2}-HST.

In particular

E_{k}(α, n) ≤ F_{k}(α, n) ≤ E_{k/2} (α\frac{k}{k−2}, n) .

Theorem 4 (The metric dichotomy).

1. For α > 2, k > 2:

exp (c(α, k)\sqrt{log n}) ≤ E_{k}(α, n) ≤ F_{k}(α, n) ≤ exp (C(α, k)\sqrt{log n})

2. For 1 < α < 2, k > 2:

c(α, k) · \frac{log n}{log log n} ≤ E_{k}(α, n) ≤ F_{k}(α, n) ≤ C(α, k)\frac{log n}{log log n}.

Here c(α, k), C(α, k) > 0 depend only on α and k. The bounds above on E_{k} also hold for k ∈ (1, 2).

This dichotomic Ramsey problem was first studied implicitly in [5]. It is possible to deduce from their work that E_{log n}(4, n) ≥ exp(c\sqrt{log n/ log log n}). A closely related problem was formulated in [2], where some bounds on E_{k}(α, n) were given.

The equilateral/lacunary dichotomy. Another type of dichotomy that we study, was first formulated in [10]. On the one hand, we have again the equilateral metric spaces. At the other extreme of the dichotomy is a class of metric spaces in which the set of pairwise distances are sparse, which we call lacunary metric spaces. Recall that the sequence a_{1} ≥ a_{2} ≥ … ≥ a_{n} > 0 is called k-lacunary for some k ≥ 1, if a_{i+1} ≤ a_{i}/k for i = 1, …, n − 1. A metric d on {1, …, n} is called k-lacunary if there exists a k-lacunary sequence a_{1} ≥ … ≥ a_{n} > 0 such that for 1 ≤ i < j ≤ n, d(i, j) = a_{i}. Alternatively, k-lacunary spaces can be defined using HSTs.

Definition 3. Let k > 1. A k-increasing metric space is a k-HST X such that in the tree defining X each vertex has at most one child which is not a leaf. A k-lacunary metric space is a k-increasing metric space X such that in the tree defining X, each vertex has at most two children.

Given integers n, k and α > 1, we ask for the largest integer m such that every n-point metric space contains an m-point subspace which is α embeddable in either an equilateral space or a k-lacunary space. Formally, we define this quantity to be

D_{k}(α, n) = R_{\begin{cases}k-lacunary spaces \\ or equilateral spaces \end{cases}\}}(α, n).

When k > 1, this function exhibits a phase transition at α = 2. When k = 1, no phase transition occurs:

Theorem 5 (The equilateral/lacunary dichotomy).

1. For α > 2, k > 1:

c(α, k) · \frac{log n}{log log n} ≤ D_{k}(α, n) ≤ C(α, k) · \frac{log n}{log log n}.

2. For 1 < α < 2, k > 1:

c(α, k)\sqrt{log n} ≤ D_{k}(α, n) ≤ C(k)\sqrt{log n}.

3. For any α > 1,

c(α) log n ≤ D_{1}(α, n) ≤ C log n.

Here c(α, k), C(α, k) > 0 depend only on α and k, c(α) > 0 depends only on α, C(k) > 0 depends only on k, and C > 0 is an absolute constant.

Dichotomic metric Ramsey problems have been studied for some time now. The proof of Theorem 1 in [7] uses embedding into 1-increasing spaces (a class which contains both k-lacunary spaces and equilateral spaces). Karloff, Rabani, and Ravid [10] have studied the dichotomic problem in the context of online computation, and obtained the lower bound above for D_{k}(4, n). In [2] some of the upper bounds in Theorem 5 are proved.

Remark. In graph theory, the study of dichotomic Ramsey problems is usually not restricted to the symmetric case. In our setting this translates to questions such as: Given α ≥ 1, k > 1, e, f ∈ ℕ, what is the smallest n such that every n-point metric space contains either an epoint subspace which is α equivalent to an equilateral space or an f-point subspace which is α equivalent to a k-lacunary space (respectively a binary k-HST)? All our proofs extend in a straightforward manner to give similarly tight bounds for the non-symmetric problems as well.

Structure of the paper. Our proof of Theorem 4 relies on Theorem 3. On the other hand, our proof for the equilateral/lacunary dichotomy is elementary. We therefore start with an elementary proof of Theorem 5 (Section 2), and then give a short proof, based on a tool from [3], of Theorem 4 (Section 3).

2 The Equilateral/Lacunary Dichotomy

In this section we prove Theorem 5. A careful reading of the proof in [7] shows that: Every n-point metric space M contains, for any ϵ > 0, a subspace Y which is (1 + ϵ) embeddable in a 1-increasing space, and |Y | = Ω (\frac{ϵ}{log(1/ϵ)} log n).

We begin with a simplified proof of this, that works for k-increasing space for any k ≥ 1.

Theorem 6. Fix an integer n, 0 < ϵ < 1 and k ≥ 1. Then any n point metric space X contains a subspace Y ⊂ X which is (1 + ϵ) embeddable in a k-increasing space and:

|Y | ≥ \frac{ϵ}{6 log(12/ϵ) log(2k)} · log n.

We start with the following simple lemma:

Lemma 2. Let M be an n-point metric space and 0 < ϵ < 1. Then there are x ∈ M, A ⊂ M and λ ∈ [1, 2] with the following properties:

1) |A| ≥ \frac{ϵn}{4}

2) For every z ∈ A, \frac{λ diam(M)}{2(1+ϵ)} ≤ d(x, z) < \frac{λ diam(M)}{2}.

Proof. Denote Δ = diam(M). Take x, x̄ ∈ M such that d(x, x̄) = Δ. The two sets Z = {y ∈ M; d(y, x) < Δ/2} and Z′ = {y ∈ M; d(y, x̄) < Δ/2} are disjoint, so we may assume that |Z| ≥ n/2. We split this set into layers.

S_{i} = \{z ∈ M; (1 + ϵ)^{i−1} \frac{Δ}{2} ≤ d(x, z) < (1 + ϵ)^{i} \frac{Δ}{2}\} .

Since |Z| ≥ n/2, there exists 1 ≤ i_{0} ≤ ⌈log_{1+ϵ} 2⌉ such that

|S_{i_{0}}| ≥ \frac{n}{2⌈log_{1+ϵ} 2⌉} ≥ \frac{ϵn}{4}.

Take A = S_{i_{0}} and λ = min{2, (1 + ϵ)^{i_{0}}} to obtain the required result.

We also need the following numerical lemma.

Lemma 3. Let {a_{i}}_{i=1}^{m} a sequence of positive numbers, satisfying for any i < j, a_{j} ≤ 2a_{i}. Fix ϵ > 0 and k ≥ 1. Then there exists L ⊂ {1, …, m}, of cardinality |L| ≥ m/(⌈log_{1+ϵ}(2k)⌉ + 1), and a sequence {b_{i}}_{i∈L} such that for any i ∈ L, a_{i} ≤ b_{i} ≤ a_{i}(1 + ϵ), and for any i < j in L, either b_{i} = b_{j} or b_{j} ≤ b_{i}/k.

Proof. For every a > 0, let t(a) be the unique integer such that a ∈ ((1 + ϵ)^{t(a)−1}, (1 + ϵ)^{t(a)}]. Set r = ⌈log_{1+ϵ}(2k)⌉ + 1. For j ∈ {0, …, r − 1} define

L_{j} = {1 ≤ i ≤ m; t(a_{i}) ≡ j (mod r)}.

There is an integer 0 ≤ j ≤ r − 1 such that |L_{j}| ≥ m/r. Set L = L_{j}. Define for i ∈ L, b_{i} = (1 + ϵ)^{t(a_{i})}, hence a_{i} ≤ b_{i} ≤ a_{i}(1 + ϵ). Fix i, j ∈ L, i < j. Then either t(a_{i}) = t(a_{j}), in which case b_{i} = b_{j}, or otherwise t(a_{j}) ∉ (t(a_{i}) − r, t(a_{i}) + r). We claim that t(a_{j}) ≤ t(a_{i_{0}}) − r. Indeed, otherwise t(a_{j}) ≥ t(a_{i}) + r, and therefore a_{j} > a_{i}(1 + ϵ)^{r−1} ≥ 2a_{i}, which contradicts the assumptions. Therefore b_{j} ≤ b_{i}/(1 + ϵ)^{r} ≤ b_{i}/k.

Proof of Theorem 6. Set Δ = diam(M). Let x_{1} ∈ M, A_{1} ⊂ M, λ_{1} ∈ [1, 2] be as in Lemma 2. Iterate this construction for A_{1} until we reach a singleton. We construct in this way x_{1}, …, x_{m} ∈ M, λ_{1}, …, λ_{m} ∈ [1, 2] and A_{m} ⊂ A_{m−1} ⊂ … A_{1} ⊂ M = A_{0} with the following properties:

a) |A_{i+1}| ≥ \frac{ϵ}{4}|A_{i}|.

b) For every z ∈ A_{i+1}, \frac{λ_{i+1} diam(A_{i})}{2(1+ϵ)} ≤ d(x_{i+1}, z) < \frac{λ_{i+1} diam(A_{i})}{2}

c) A_{m} = {x_{m}} and |A_{m−1}| > 1.

These conditions imply in particular that m ≥ \frac{log n}{log(4/ϵ)}.

The set {x_{1}, …, x_{m}} is therefore (1+ϵ)-equivalent to a metric similar to an increasing space, but the labels are not monotonic. We solve this problem by an appropriate sparsification. Put l_{i} = \frac{λ_{i} diam(A_{i−1})}{2}. Note that if i > j then l_{i} ≤ 2l_{j}. Indeed, this follows from the fact that A_{i} ⊂ A_{j} and λ_{i}, λ_{j} ∈ [1, 2]. Apply Lemma 3 to the sequence {l_{i}}_{i=1}^{m}, and let {b_{i}}_{i∈L} be the resulting sequence. Let c_{1} > c_{2} > ⋯ > c_{s} be such that {c_{1}, …, c_{s}} = {b_{i}; i ∈ L}.

For i = 1, …, s define J_{i} = {h ∈ L; b_{h} = c_{i}} and put B_{i} = ∪_{h∈J_{i}}A_{h}. Set also B_{0} = M. We construct a labelled tree T as follows. The root of T is B_{1}, and the rest of the vertices are {x_{i}}_{i∈L} and {B_{i}}_{i=2}^{s}. For i ∈ L, x_{i} is a leaf of T. The children of B_{i} are B_{i+1} and each of {x_{h}}_{h∈J_{i}}. We label T by setting for each i ∈ L, Δ(x_{i}) = 0, for i = 1, … s and Δ(B_{i}) = c_{i}. By Lemma 3, Δ(B_{i+1}) ≤ Δ(B_{i})/k.

Set X = {x_{h}}_{h∈L_{j}}. We have proved that X is a k-increasing space. Take a, b ∈ L, a < b. Assume that a ∈ J_{p}, b ∈ J_{q}, p ≤ q. Since x_{b} ∈ A_{a} we get that:

d_{X}(x_{a}, x_{b}) = Δ(B_{p}) = b_{a} ≤ (1 + ϵ)l_{a} = \frac{(1 + ϵ)λ_{a} diam(A_{a−1})}{2} ≤ (1 + ϵ)^{2}d(x_{a}, x_{b}),

and

d_{X}(x_{a}, x_{b}) = Δ(B_{p}) = b_{a} ≥ l_{a} = \frac{λ_{a} diam(A_{a−1})}{2} ≥ d(x_{a}, x_{b}).

This proves that {x_{h}}_{h∈L} is (1 + ϵ)^{2} equivalent to a k-increasing space. The estimate on |L| gives the required result.

We can now deduce that any large metric space contains a large subspace which is close to either an equilateral space or to a lacunary space.

Proposition 4. Let X be an n point metric space, k ≥ 1, and ϵ > 0. Then X contains a subspace Y which is (1 + ϵ) equivalent to either an equilateral space or a k-lacunary space, and such that:

|Y | ≥ c\sqrt{\frac{ϵ}{log(2/ϵ)} · \frac{log n}{log k}},

where c is an absolute constant.

Proof. By Theorem 6, it is enough to prove that any m point k-increasing metric space contains (isometrically) either an equilateral space of size \sqrt{m} or a k-lacunary space of size \sqrt{m}.

Let X be an m point k-increasing space. Let T be the tree defining X. If T contains an internal vertex with \sqrt{m} leaves then these leaves form an equilateral space. Otherwise T contains at least \sqrt{m} internal vertices which have at least one child which is a leaf. These leaves form a k-lacunary metric space.

For distortion α < 2, Proposition 4 is tight. Here is a matching upper bound.

Proposition 5. For any α ∈ [1, 2), any k > 1 and any integer n there exists an n-point metric space X such that no subset of X with cardinality greater that \frac{c}{log k} \sqrt{log n} is α equivalent to an equilateral space or a k-lacunary space. Here c is an absolute constant.

The proof of Proposition 5 is based on the notion of simple metric composition. This is a special case of a more general definition that was introduced in [3].

Definition 4 (Simple Metric Composition). Let M, N be two finite metric spaces and let β ≥ 1. The β-composition of M and N is a metric space on M × N which we denote by L = M_{β}[N]. Distances in L are defined by:

d_{L}((i, j), (k, l)) = \begin{cases}d_{N}(j, l) & i = k \\ βγd_{M}(i, k) & i ≠ k. \end{cases}

where γ = \frac{diam(N)}{min_{i≠k} d_{M} (i,k)}. It is easily checked that the choice of the factor β · γ guarantees that d_{L} is indeed a metric.

In words, first multiply the distances in M by β · γ, and then replace each point of M by an isometric copy of N.

We also use the notation Φ(X) = \frac{diam(X)}{min_{x,y∈X, x≠y} d_{X}(x,y)}. This is the aspect ratio of the metric space X, and in other words, the Lipschitz distance between X and an equilateral space. We begin with three simple lemmas:

Lemma 6. Let X be a finite metric space which is α embeddable in a k-lacunary metric space for some k, α > 1. Then |X| ≤ 2 + log_{k} (αΦ(X)) .

Proof. Let Y be a k-lacunary space that is α equivalent to X. Hence Φ(Y) ≤ αΦ(X). A simple induction on |Y | shows that for any k-lacunary space Y, Φ(Y) ≥ k^{|Y |−2}.

Lemma 7. Let M, N be finite metric spaces, and let β > α ≥ 1. Then every subset S ⊂ M_{β}[N] with Φ(S) ≤ α is 1-embeddable either in M or in N.

Proof. For every x ∈ M denote D_{x} = {(x, y) ∈ M × N; y ∈ N}. If S ⊂ D_{x} for some x ∈ M then S is 1-embeddable in N. If for each x ∈ M, |S ∩ D_{x}| ≤ 1 then S is 1-embeddable in M. Otherwise there are a, b, c ∈ S and x, y ∈ M, a ≠ b, x ≠ y, such that a, b ∈ D_{x} and c ∈ D_{y}. Hence:

\frac{d_{S}(a, c)}{d_{S}(a, b)} ≥ \frac{βγ min_{u≠v} d_{M}(u, v)}{max_{u,v∈N} d_{N}(u, v)} ≥ β > α,

which contradicts the fact that Φ(S) ≤ α.

Lemma 8. Let M, N be finite metric spaces. Fix k, α ≥ 1 and β ≥ max \{1, \frac{α}{k}\}. Then every S ⊂ M_{β}[N] which is α-embeddable in a k-lacunary metric space has a subset T ⊂ S that is 1-embeddable in M and S \ T is 1-embeddable in N.

Proof. Let a_{1} ≥ … ≥ a_{n} > 0 be a k-lacunary sequence, i.e., a_{i+1} ≤ a_{i}/k. It is easy to verify that for every four distinct integers 1 ≤ i_{1}, i_{2}, i_{3}, i_{4}, ≤ n,

max{a_{min{i_{1},i_{2}}}, a_{min{i_{3},i_{4}}}} ≥ k min{a_{min{i_{1},i_{3}}}, a_{min{i_{1},i_{4}}}, a_{min{i_{2},i_{3}}}, a_{min{i_{2},i_{4}}}}.

Since S is α-embeddable in a k-lacunary space, it follows that for every distinct x_{1}, x_{2}, x_{3}, x_{4} ∈ S,

max\{d_{S}(x_{1}, x_{2}), d_{S}(x_{3}, x_{4})\} ≥ \frac{k}{α} min\{d_{S}(x_{1}, x_{3}), d_{S}(x_{1}, x_{4}), d_{S}(x_{2}, x_{3}), d_{S}(x_{2}, x_{4})\}.  (1)

As before, denote γ = \frac{max_{x,y∈N} d_{N} (x,y)}{min_{x≠y} d_{M} (x,y)} and for x ∈ M, D_{x} = \{(x, y) ∈ M × N; y ∈ N\}. It is sufficient to prove that there is at most one x ∈ M such that |S ∩ D_{x}| > 1. This is true since otherwise there would be four distinct points p, q, r, s ∈ N and two distinct points x, y ∈ M such that p, q ∈ D_{x} and r, s ∈ D_{y}. Now:

\frac{max\{d_{S}(p, q), d_{S}(r, s)\}}{min\{d(p, r), d(p, s), d(q, r), d(q, s)\}} ≤ \frac{max_{u,v∈N} d_{N}(u, v)}{βγ min_{u≠v} d_{M}(u, v)} = \frac{1}{β} < \frac{k}{α},

which contradicts (1).

Proof of Proposition 5. Let G = (V, E) be a graph of diameter 2 on ⌈2^{\sqrt{log n}}⌉ vertices, with no independent sets and no cliques larger than C\sqrt{log n}, here C is an absolute constant. It is well-known and easy to prove that almost all graphs have these properties, see [9, 6].

Let M be the metric defined by G. Define M_{1} = M, and M_{i} = M_{β}[M_{i−1}], where β = 2. First we prove by induction that for each i ≥ 1, if S ⊂ M_{i} is α embeddable in an equilateral space then |S| ≤ C\sqrt{log n}. For i = 1 consider a subset S ⊂ M that is α-embeddable in an equilateral space. Since α < 2, and G has diameter 2, all the distances in S must be either 1 or 2. Thus S is either a clique or an independent set, so that |S| ≤ C\sqrt{log n}. Now let i > 1 and consider S ⊂ M_{i} = M_{β}[M_{i−1}] that is α-embeddable in an equilateral space. By Lemma 7, S is 1-embeddable in either M or M_{i−1}, which by induction implies that |S| ≤ C\sqrt{log n}.

We now prove by induction on i that if S ⊂ M_{i} is α-embeddable in a k-lacunary space then |S| ≤ i (1 + log_{k}(2α)). For i = 1 this follows from Lemma 6. For i > 1 let S ⊂ M_{i} = M_{β}[M_{i−1}] be α-embeddable in a k-lacunary space. By Lemma 8 this implies that there is A ⊂ S that 1-embeds into M and S \ A 1-embeds into M_{i−1}. By the induction hypothesis:

|S| = |A| + |S \ A| ≤ 1 + log_{k}(2α) + (i − 1) (1 + log_{k}(2α)) = i (1 + log_{k}(2α)) .

Take t = ⌈\sqrt{log n}⌉ and note that |M_{t}| ≥ n. The space X = M_{t} satisfies our claim.

For every b > a > 1, it is easy to extract from every a-lacunary sequence a long b-lacunary subsequence, by skipping each time appropriately many terms in the sequence. We record this simple fact for future reference.

Lemma 9. For every b > a > 1, every a-lacunary sequence of length n contains a subsequence of length \frac{n}{⌈1+log_{a} b⌉} which is b-lacunary. Hence, any n point a-lacunary metric space contains a b-lacunary subspace of the above size.

Using a technique similar to [10], we now prove:

Proposition 10. For any k > 1, α > 2 and any integer n, every n point metric space contains a subspace of cardinality at least \frac{log(α/2)}{2 log(αk)} · \frac{log n}{log log n} which is α-embeddable in either an equilateral space or a k-lacunary space.

Proof. Let (M, d) be an n-point metric space. Denote Δ = diam(M), and let x, x̄ ∈ M be a diametrical pair, i.e., d(x, x̄) = Δ. Let x = x_{1}, …, x_{s} be a maximal subset in M containing x such that for every i ≠ j, d(x_{i}, x_{j}) ≥ Δ/α. Clearly {x_{1}, … x_{s}} is α-equivalent to an equilateral space, so that if s ≥ log n we are done. As usual, we denote by B(x, r) = {y ∈ M; d(x, y) < r} the open ball of radius r around x. Let

A_{1} = B (x_{1}, \frac{Δ}{α}) and A_{i+1} = B (x_{i+1}, \frac{Δ}{α}) \ ⋃_{j=1}^{i} B (x_{j}, \frac{Δ}{α}) .

Assume that s < log n. Since ∪_{i=1}^{s}A_{i} = ∪_{i=1}^{s}B(x_{i}, Δ/α) = M, it follows that there exists 1 ≤ i ≤ n such that |A_{i}| ≥ n/ log n. Observe that there exists y ∈ M such that d(y, A_{i}) ≥ Δ/α. Indeed, if i > 1 then A_{i} ⊂ M \ B(x, Δ/α) so that we can take y = x. Otherwise, since α > 2, for every z ∈ A_{1} = B(x, Δ/α),

d(z, x̄) ≥ d(x̄, x) − d(x, z) ≥ Δ − \frac{Δ}{α} > \frac{Δ}{α},

so that we can take y = x̄. Note also that diam(A_{i}) ≤ diam(B(x_{i}, Δ/α)) ≤ \frac{2}{α}Δ.

Iterating this construction we get a sequence of points z_{1}, …, z_{m} ∈ M, and a decreasing sequence of subsets {z_{m}} = F_{m} ⊂ F_{m−1} ⊂ … ⊂ F_{1} ⊂ F_{0} = M such that for each i, z_{i} ∈ F_{i−1}, d(z_{i}, F_{i}) ≥ diam(F_{i−1})/α, diam(F_{i}) ≤ \frac{2}{α} diam(F_{i−1}) and |F_{i}| ≥ |F_{i−1}|/ log n. By induction, |F_{i}| ≥ n/(log n)^{i} and since |F_{m}| = 1, necessarily m ≥ log n/ log log n. Moreover, the sequence {diam(F_{i})}_{i=0}^{m−1} is (α/2)-lacunary and for 1 ≤ i < j ≤ m,

\frac{diam(F_{i−1})}{α} ≤ d(z_{i}, F_{i}) ≤ d(z_{i}, z_{j}) ≤ diam(F_{i−1}).

This proves that {z_{i}, …, z_{m}} is α equivalent to a (α/2)-lacunary metric space. If k < α/2 we are done. Otherwise, we can apply Lemma 9 to find a subset of {z_{1}, …, z_{m}} which is α embeddable in a k-lacunary space and with cardinality at least:

\frac{m}{⌈1 + log_{α/2} k⌉} ≥ \frac{log(α/2)}{2 log(αk)} · \frac{log n}{log log n}.

We can now establish the equilateral/lacunary dichotomy:

Proof of Theorem 5. The lower bound in part 1) was proved in Proposition 10. In [2], Proposition 29 it is proved that for 2 < α < k,

D_{α}(n, k) ≤ C \frac{log α}{log k} · \frac{log n}{log log n}.

In the case α ≥ k, let M be a metric space and N ⊂ M a subset which is α embeddable in either an equilateral space or a k-lacunary space. Apply Lemma 9 with b = α^{2} and a = k.

We deduce that there is N′ ⊂ N which is α embeddable in either an equilateral space or a α^{2}-lacunary space such that |N′| ≥ \frac{|N| log k}{2 log α}. By the above stated result from [2],

\frac{|N| log k}{2 log α} ≤ |N′| ≤ C \frac{log α}{log(α^{2})} · \frac{log n}{log log n},

which implies the required result.

Part b) is a combination of Proposition 4 and Proposition 5. Part c) is a combination of Theorem 6 and part 4 of Proposition 29 in [2].

3 The Metric Dichotomy

Our main aim in this section is to prove Theorem 4. We begin, however, with a proof of Proposition 1.

Proof of Proposition 1. To prove the first assertion note that if x, y, z are three distinct leaves in a binary tree T, then there are p, q ∈ T such that p ≠ q, q is a descendant of p and {lca(x, y), lca(x, z), lca(y, z)} = {p, q}. Since Δ(p)/Δ(q) ≥ k, the Lipschitz distance between the triangle {x, y, z} and an equilateral triangle is at least k.

To prove the second assertion, denote Δ = diam(M), and let x, x̄ ∈ M be a diametrical pair: d(x, x̄) = Δ. Let B_{x} = B(x, Δ/k), and Bx̄ = B(x̄, Δ/k). Since k > 2, the triangle inequality implies that B_{x} ∩ Bx̄ = ∅. We claim that B_{x} ∪ Bx̄ = M. Otherwise, there is a y ∈ M such that d(x, y) ≥ Δ/k, and d(x̄, y) ≥ Δ/k. But this implies that x, x̄, y are three points for which c_{{equilateral spaces}}({x, x̄, y}) ≤ k, contrary to our assumption.

We proceed to construct a binary \frac{k}{2}-HST L with diam(L) = diam(M), and a non-contractive embedding g : M ↪ L with ∥g∥_{lip} ≤ \frac{k}{k−2}. Inductively, assume we have already constructed g_{1} : B_{x} ↪ L_{1}, g_{2} : Bx̄ ↪ L_{2}, where L_{1}, L_{2} are binary k-HSTs with diam(L_{1}) = diam(B_{x}), diam(L_{2}) = diam(Bx̄), and g_{1}, g_{2} are non-contractive embeddings with ∥g_{1}∥_{lip} ≤ \frac{k}{k−2}, and ∥g_{2}∥_{lip} ≤ \frac{k}{k−2}. Define L = L_{1} ∪ L_{2}, and g : M ↪ L by g|_{B_{x}} = g_{1}, g|_{Bx̄} = g_{2}. Set the distance between any point in L_{1} and any point in L_{2} to be Δ. Since max\{diam(L_{1}), diam(L_{2})\} ≤ \frac{2Δ}{k}, L is a binary \frac{k}{2}-HST, g is non-contractive, diam(L) = diam(M), and

∥g∥_{lip} ≤ max\{∥g_{1}∥_{lip}, ∥g_{2}∥_{lip}, \frac{Δ}{Δ − 2Δ/k} \} ≤ \frac{k}{k − 2}.

We begin with the upper bounds on E_{k} and F_{k} for distortions smaller than 2. We give both a bound for E_{k} and for F_{k}, since the bound for E_{k} holds for any k > 1, whereas for F_{k}, it holds only for k > 2.

Lemma 11. Let X be a finite metric space which is α-embeddable in a binary k-HST for some k, α > 1. Then |X| ≤ 2^{1+log_{k}(αΦ(X))}.

Proof. Let Y be a binary k-HST that is α equivalent to X. Hence Φ(Y) ≤ αΦ(X). The tree defining Y is binary and its depth is therefore ≥ log_{2} |Y |. A simple induction on |Y | proves that for any binary k-HST Y, Φ(Y) ≥ k^{log_{2} |Y |−1}.

Proposition 12. For any α ∈ [1, 2), any k > 1 and any integer n there exists an n point metric space X such that no subset of X with cardinality greater than \frac{c}{log k} \frac{log n}{log log n} is α-equivalent to an equilateral space or a binary k-HST. Here c is an absolute constant.

Proof. Again we recall that almost every graph on s = ⌈2^{2(1+log_{k}(2α)) \frac{log n}{log log n}} ⌉ vertices has diameter 2 and its independence number and clique number are ≤ C log s, for some absolute constant C.

Let G be such a graph and let M be its metric. Next, define M_{0} = {a}, and M_{i} = M_{β}[M_{i−1}], where β = 2.

Similarly to the proof of Proposition 5, for each i ≥ 1, if S ⊂ M_{i} is α-embeddable in an equilateral space then |S| ≤ C log s. For i = 1, if S ⊂ M is α-embeddable in an equilateral space, then S must either be a clique or an independent set, since α < 2. Consequently, |S| ≤ C log s. Now let S ⊂ M_{i} = M_{β}[M_{i−1}] be α-embeddable in an equilateral space for some i > 1. By Lemma 7, S is 1-embeddable in either M or M_{i−1}, which by induction implies that |S| ≤ C log s.

We now prove by induction on i that if S ⊂ M_{i} is α-embeddable in a binary k-HST then |S| ≤ 2^{i(1+log_{k}(2α))}. For i = 0 this is obvious. Assume that i > 0 and S ⊂ M_{i} = M_{β}[M_{i−1}] is α embeddable in a binary k-HST. Partition S to S = S_{1} ∪ … ∪ S_{ℓ} such that each S_{j} is a subset of a different “copy” of M_{i−1}. Note that S_{j} ⊂ M_{i−1} is α embeddable in a binary k-HST, and by the inductive hypothesis |S_{j}| ≤ 2^{(i−1)(1+log_{k}(2α))}. Pick a representative from each S_{j}, and denote the set of representatives by S′, |S′| = ℓ. As S′ ⊂ S it is also α embeddable in a binary k-HST (the defining tree is a subtree of the tree defining the HST of S). The metric of S′ is a dilation of a subset of M, and so by Lemma 11, ℓ ≤ 2^{1+log_{k}(2α)}. We can therefore estimate

|S| ≤ ℓ max_{1≤j≤ℓ} |S_{j}| ≤ 2^{1+log_{k}(2α)}2^{(i−1)(1+log_{k}(2α))} = 2^{i(1+log_{k}(2α))}.

Note that |M_{t}| ≥ n for t = ⌈\frac{log log n}{2(1+log_{k}(2α))}⌉. The space X = M_{t} satisfies the Proposition.

We give a similar upper bound for the equilateral/triangular variant of this dichotomy.

Proposition 13. For any α ∈ [1, 2), any k > 2 and any integer n there exists an n-point metric space M such that no subset of M with cardinality greater than c log_{k/2} \frac{k}{k−2} · \frac{log n}{log log n} is α-equivalent to an equilateral space or a space in which no triangle is k-equivalent to an equilateral triangle. Here c is an absolute constant.

Proof. The proof is almost identical to the proof of Proposition 12. The only change is the reference to Lemma 11. Here instead we use the following claim: Any finite metric space X which is α embeddable in space in which no triangle is ≤ k-equilateral, for some k > 2, α > 1 satisfies |X| ≤ 2^{1+log_{k/2}(α \frac{k}{k−2} Φ(X))}. This fact is an immediate consequence of Lemma 11 and Proposition 1.

The proofs of the lower bounds on E_{k} use the following simple structural lemma.

Lemma 14. Let T be a rooted tree with n leaves, in which each vertex has at most h ≥ 2 children. Then T contains a binary subtree with at least n^{1/ log_{2} h} leaves.

Proof. By induction on the size of T. Let h′ ≤ h be the number of children of T ’s root r. Let T_{i} be the subtree rooted at r-th i-th child and let n_{i} be the number of leaves in T_{i}, where n_{1} ≥ n_{2} ≥ … ≥ n_{h′} and ∑_{i=1}^{h′} n_{i} = n. By the induction hypothesis, T_{i} has a binary subtree with at least n_{i}^{1/ log_{2} h} leaves. We form a binary subtree of T by joining the binary subtrees of T_{1} and T_{2}. Together they have at least n_{1}^{1/ log_{2} h} + n_{2}^{1/ log_{2} h} leaves, which is ≥ n^{1/ log_{2} h} as we now show. First, n_{1}^{1/ log_{2} h} + n_{2}^{1/ log_{2} h} ≥ 2(\frac{n_{1}+n_{2}}{2} )^{1/ log_{2} h} since the function f(x) = x^{1/ log_{2} h} is concave. Also, f is increasing, and \frac{n_{1}+n_{2}}{2} ≥ \frac{n}{h′} ≥ \frac{n}{h}. Consequently, n_{1}^{1/ log_{2} h} + n_{2}^{1/ log_{2} h} ≥ 2(\frac{n}{h})^{1/ log_{2} h} = n^{1/ log_{2} h}, as claimed.

The following is a short argument proving the lower bound on E_{k} for distortions larger than 2.

Proposition 15. For any ε ∈ (0, 1), and k ≥ 1,

E_{k}(2 + ε, n) ≥ exp (\sqrt{\frac{cε}{log(2k/ε)} log n}) .

Proof. Let M be an arbitrary n-point metric space. By Theorem 3, it contains a subset N ⊂ M that is (2 + ε)-equivalent to a k-HST and |N| ≥ n^{\frac{cε}{log(2k/ε)}} . Let T be the tree defining this k-HST. The claim is now proved by taking either a large equilateral subspace of T or a large binary subtree of T according to Lemma 14, where h = exp(\sqrt{\frac{cε}{log(2k/ε)} log n}).

We note that the above proposition can also be proved by arguments similar to those from [5].

The lower bound on E_{k} for distortions smaller than 2 is only slightly more complicated:

Proposition 16. For any > ε > 0, k ≥ 1,

E_{k}(1 + ε, n) ≥ \frac{cε}{log(1/ε) log(k/ε)} · \frac{log n}{log log n},

where c is a universal constant.

Proof. Essentially, we repeat the argument from Proposition 15, and find either an h-point subspace that is 3-equivalent to equilateral space or an n^{1/ log h}-point subspace that is 3 equivalent to binary k-HST. In order to improve the distortion to 1 + ε, we invoke in the first case the classical Ramsey theorem to find a ≥ log h-point subspace which is (1+ε)-equivalent to an equilateral space, whereas in the second case we observe that by optimizing the distances in the binary k-HST, we improve the distortion. We choose h ≈ n^{1/ log log n}, so that log h ≈ n^{1/ log h}. We now turn to the actual arguments.

Let M be an n-point metric space. Denote k′ = max{k, 2 + 2/ε}. By Theorem 3, M contains a subspace N ⊂ M that is 3-equivalent to a (3k′)-HST, X, via a non-contractive bijection f : N → X, and |N| ≥ n^{\frac{c}{log k′}} = s. Let h = s^{1/ log log n}. Denote by T the tree defining X. We distinguish between two cases.

Case 1. T has a vertex u with out-degree exceeding h. Let v_{0}, …, v_{h} be distinct children of u. For each 0 ≤ i ≤ h take x_{i} ∈ N such that f(x_{i}) is a leaf of T which is a descendant of v_{i}. For every 0 ≤ i < j ≤ h, d(x_{i}, x_{j}) ∈ [Δ(u)/3, Δ(u)], so that there is a unique integer c(i, j) ∈ {1, 2, …, ⌊log_{1+ε} 3⌋} for which:

d(x_{i}, x_{j}) ∈ [\frac{Δ(u)}{(1 + ε)^{c(i,j)+1}} , \frac{Δ(u)}{(1 + ε)^{c(i,j)}} ) .

Set D = ⌊log_{1+ε} 3⌋ and color the edges of the complete graph on {0, …, h} by assigning the color c(i, j) to the edge [i, j]. By the classical Ramsey theorem there is a subset N′ ⊂ \{x_{1}, …, x_{h}\} of size at least \frac{log h}{D log D} ≥ \frac{cε}{log(1/ε)} \frac{log s}{log log n} on which the induced complete subgraph is monochromatic. This subset is (1 + ε)-equivalent to an equilateral space.

Case 2. All the vertices in T have out-degree at most h. In this case, by Lemma 14, T contains a binary subtree S with at least s^{1/ log_{2} h} = log n leaves. Set L = f^{−1}(S). Then |L| = |S| ≥ log n and L is 3-equivalent to a binary (3k′)-HST S. In order to improve the distortion we change the labels of S. Denote by Δ(·) the original labels on S (inherited from T). We define new labels Δ′(·) on S as follows. For each vertex u ∈ S, denote by T_{1} and T_{2} the subtrees rooted at u’s children. We define Δ′(u) = max{d_{M}(x, y); x ∈ f^{−1}(T_{1}), y ∈ f^{−1}(T_{2})}, and claim that the resulting labelled tree is a binary k′-HST which is \frac{k′}{k′−2} equivalent to L. Indeed, let u, v ∈ S with v a child of u. Since the distances in (S, Δ) are larger than the distances in M by a factor at most 3, Δ(u)/3 ≤ Δ′(u). On the other hand, since Δ defines 3k′-HST, Δ′(v) ≤ Δ(v) ≤ Δ(u)/(3k′), so that the resulting tree (S, Δ′) is indeed k-HST. To bound the distortion, let x, y be two distinct points in L. So f(x), f(y) are distinct leaves of S and assume that lca(f(x), f(y)) = u, f(x) ∈ T_{1}, f(y) ∈ T_{2}, where T_{1} and T_{2} are subtrees rooted at children of u. Then d_{M}(x, y) ≤ Δ′(u). On the other hand fix a ∈ f^{−1}(T_{1}) and b ∈ f^{−1}(T_{2}) for which d_{M}(a, b) = Δ′(u). Then

d_{L}(x, y) ≥ d_{L}(a, b) − d_{L}(a, x) − d_{L}(b, y)
≥ Δ′(u) − Δ(lca(f(a), f(x))) − Δ(lca(f(b), f(y)))
≥ Δ′(u) − 2\frac{Δ(u)}{3k′}
≥ Δ′(u) − \frac{2Δ′(u)}{k′} = \frac{k′ − 2}{k′}Δ′(u).

since k′ ≥ k, and \frac{k′}{k′−2} ≤ 1 + ε, L is (1 + ε)-equivalent to binary k-HST (S, Δ′).

Proof of Theorem 4. The lower bound for E_{k}(α, n), α > 2, is contained in Proposition 15. The upper bound for F_{k}(α, n), α, k > 2 can be derived from results of [2], where it is proved

that for 1 < α < k, E_{k}(α, n) ≤ 2^{2\sqrt{\frac{log α}{log k} log n}}. In order to prove the upper bound on E_{k}(α, n) for 1 < k ≤ α, we use another lemma from [2]: for any k > 1 and any h ∈ ℕ, any n-point k-HST contains isometrically a subspace of size n^{1/h} which is a k^{h}-HST. It is easy to observe that if we start with a binary k-HST the resulting subspace is a binary k^{h}-HST. Therefore, if 1 < k ≤ α, we take h = ⌊1 + log_{k} α⌋. Using the discussion above, and the fact h ≥ 1, we deduce that

[E_{k}(α, n)]^{1/h} ≤ E_{k^{h}}(α, n) ≤ 2^{2\sqrt{\frac{log α}{h log k} log n}}.

As \frac{log α}{h log k} ≤ 1, we conclude that E_{k}(α, n) ≤ 2^{2h\sqrt{log n}}. For α, k > 2, by Proposition 1,

F_{k}(α, n) ≤ E_{k/2}(α\frac{k}{k−2}, n) ≤ 2^{2[1+log_{k/2}( \frac{k}{k−2} α)]\sqrt{log n}}.

The lower bound for E_{k}(α, n), α ∈ (1, 2), is contained in Proposition 16. The upper bound for F_{k}(α, n) k > 2, α ∈ (1, 2) is contained in Proposition 13. The extension of this upper bound for E_{k}(α, n), k ≥ 1, α ∈ (1, 2), is contained in Proposition 12.

References

[1] Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), pages 184–193. IEEE Comput. Soc. Press, Los Alamitos, CA, 1996.

[2] Y. Bartal, B. Bollobás, and M. Mendel. Ramsey-type theorems for metric spaces with applications to online problems, 2002. To appear in Special issue of Journal of Computer and System Science. http://www.cs.huji.ac.il/∼mendelma/mypapers.

[3] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Metric Ramsey-type Phenomena, 2002. Preprint.

[4] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Some Low Distortion Metric Ramsey Problems, 2002. Preprint.

[5] A. Blum, H. Karloff, Y. Rabani, and M. Saks. A decomposition theorem for task systems and bounds for randomized server problems. SIAM J. Comput., 30(5):1624–1661 (electronic), 2000.

[6] B. Bollobás. Extremal graph theory. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1978.

[7] J. Bourgain, T. Figiel, and V. Milman. On Hilbertian subsets of finite metric spaces. Israel J. Math., 55(2):147–152, 1986.

[8] 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, 1961.

[9] P. Erdös. Some remarks on the theory of graphs. Bull. Amer. Math. Soc., 53:292–294, 1947.

[10] H. Karloff, Y. Rabani, and Y. Ravid. Lower bounds for randomized k-server and motionplanning algorithms. SIAM J. Comput., 23(2):293–312, 1994.

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

2000 AMS Mathematics Subject Classification: 52C45, 05C55, 54E40, 05C12, 54E40.