On Some Low Distortion Metric Ramsey Problems

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

December 17, 2002

Abstract In this note, we consider the metric Ramsey problem for the normed spaces ℓ_{p}. Namely, given some 1 ≤ p ≤ ∞ and α ≥ 1, and an integer n, we ask for the largest m such that every n-point metric space contains an m-point subspace which embeds into ℓ_{p} with distortion ≤ α. In [1] it is shown that in the case of ℓ_{2}, the dependence of m on α undergoes a phase transition at α = 2. Here we consider this problem for other ℓ_{p}, and specifically the occurrence of a phase transition for p ≠ 2. It is shown that a phase transition occurs at 2 for every p ∈ [1, 2]. For p > 2 we are unable to determine the answer, but estimates are provided for the possible location of such a phase transition. We also study the analogous problem for isometric embedding and show that for every 1 < p < ∞ there are arbitrarily large metric spaces, no four points of which embed isometrically in ℓ_{p} .

1 Introduction

A Ramsey-type theorem states that large systems necessarily contain large, highly structured sub-systems. Here we consider Ramsey-type problem for finite metric spaces, interpreting “highly structured” as having low distortion embedding in ℓ_{p}.

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 required to embed M in X is denoted by c_{X}(M). When c_{X}(M) ≤ α we say that M α-embeds in X. In this note we study the following notion.

Definition 1 (Metric Ramsey function). We denote by R_{X}(α, n) the largest integer m such that every n-point metric space has a subspace of size m that α-embeds into X.

When X = ℓ_{p} we use the notations c_{p} and R_{p}. Note that for p ∈ [1, ∞], it is always true that R_{p}(α, n) ≥ R_{2}(α, n). When α = 1 we drop it from the notation, i.e., R_{X}(n) = R_{X}(1, n).

Bourgain, Figiel, and Milman [4] study this function for X = ℓ_{2}, as a non-linear analog of Dvoretzky’s theorem [6]. They prove

Theorem 1 ([4]). 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.

In [1] the metric Ramsey problem is studied comprehensively. In particular, the following phase transition is established in the case of X = ℓ_{2}.

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

1. For every 1 < α < 2: c(α) log n ≤ R_{2}(α, n) ≤ 2 log n + C(α), where c(α), C(α) may depend only on α.

2. For every α > 2: n^{c′(α)} ≤ R_{2}(α, n) ≤ n^{C′(α)}, where c′(α), C′(α) depend only on α and 0 < c′(α) ≤ C′(α) < 1. Moreover, c′(α) tends to 1 as α tends to ∞.

By Dvoretzky’s theorem, the lower bound in part 2 of Theorem 2 implies in particular that if α > 2, and X is any infinite dimensional normed space, then R_{X}(α, n) ≥ n^{c′(α)}. Therefore, in our search for a possible phase transition for R_{p}(·, n), p ≠ 2, it is natural to extend the upper bound in part 1 of Theorem 2 to this range. The main result proved in this note is the following:

Theorem 3. There is an absolute constant c > 0 such that for every 0 < δ < 1,

1. For 1 ≤ p < 2, R_{p}(2 − δ, n) ≤ e^{\frac{c}{δ^{2}}} log n.

2. For 2 < p < ∞, R_{p}(2^{2/p} − δ, n) ≤ e^{\frac{c}{p^{2}δ^{2}}} log n.

Thus we extend the result of [1] to show that a phase transition occurs in the metric Ramsey problem for ℓ_{p}, p ∈ [1, 2), at α = 2. The asymptotic behavior of R_{p}(α, n) for p > 2, and α ∈ [2^{2/p}, 2], is left as an open problem. In particular, we do not know whether or not this function undergoes a similar phase transition. We find this problem potentially significant: if there is a phase transition at 2 also in the range 2 < p < ∞, then this result will certainly be of great interest. On the other hand, if it is possible to improve the lower bound in part 2 of Theorem 2 for p > 2 and certain distortions strictly less than 2, then this would involve an embedding technique that is different from the method used in [1], which doesn’t distinguish between the various ℓ_{p} spaces.

The proof of the upper bound on R_{2}(α, n) for α < 2 stated in Theorem 2 uses the Johnson-Lindenstrauss dimension reduction lemma for ℓ_{2} [9]. For ℓ_{p}, p ≠ 2, no such dimension reduction is known to hold. Our proof is based on a non-trivial modification of the random construction in [4], in the spirit of Erdös’ upper bound on the Ramsey numbers [8, 3]. In the process we prove tight bounds on the embeddability of the metrics of complete bipartite graphs in ℓ_{p}. Specifically we show that

c_{p}(K_{n,n}) = \begin{cases}2 − Θ(n^{−1}) & p ∈ [1, 2] \\ 2^{2/p} − Θ((pn)^{−1}) & p > 2. \end{cases}

The second part of this note addresses the isometric Ramsey problem for p ∈ (1, ∞). It turns out that this problem is naturally tackled within the class of uniformly convex normed spaces (see Section 3 for the definition).

Theorem 4 (Isometric Ramsey Problem). Let X be a uniformly convex normed space with dim(X) ≥ 2. Then R_{X}(1, n) = 3 for n ≥ 3.

Since for p ∈ (1, ∞), ℓ_{p} is uniformly convex, the conclusion of Theorem 4 holds in these cases. Note that the theorem does not apply for ℓ_{1} and ℓ_{∞} which are not uniformly convex. Specifically, it is known that ℓ_{∞} is universal in that it contains an isometric copy of every finite metric space, whence R_{∞}(n) = n. It is known [5] that any 4-point metric space is isometrically embeddable in ℓ_{1}, and therefore R_{1}(n) ≥ 4 for n ≥ 4. The determination of R_{1}(n) is left as an open problem.

2 An Upper Bound For α < 2

In this section we prove that for any α < min{2, 2^{2/p}}, R_{p}(α, n) = O(log n). Our technique both improves and simplifies the technique of [4], which is itself in the spirit of Erdös’ original upper bound for the Ramsey coloring numbers. The basic idea is to exploit a universality property of random graphs G ∈ G(n, 1/2). Namely, that any fixed graph of constant size appears as induced subgraph of every induced subgraph of G of size Ω(log n). More precisely, we define the following notion of universality.

Definition 2. Let H be a graph. A graph G is called (H, s)-universal if every set of s vertices in G contains an induced subgraph isomorphic to H.

Proposition 1. For every k-vertex graph H there exists a constant C > 0 and an integer n_{0} such that for any n > n_{0} there exists a (H, C log n + 1)-universal graph. Furthermore,

C ≤ O (k^{2}2^{\binom{k}{2}}) and n_{0} ≤ O (k^{3}2^{\binom{k}{2}}) .

Such facts are well-known in random graph theory, and similar arguments can be found for example in [11]. We sketch the standard details for the sake of completeness.

Recall that a family of sets F is called almost disjoint if |A ∩ B| ≤ 1 for every A, B ∈ F.

Lemma 2. For every integer k and a finite set S with k < \sqrt{|S|/2}, there exists an almost disjoint family K ⊂ \binom{S}{k}, such that |K| ≥ ⌊\frac{s}{2k}⌋^{2}.

Proof. Let p be a prime satisfying \frac{s}{2k} ≤ p ≤ \frac{|S|}{k}, and assume that

L = {(i, j); i, j ∈ ℤ_{p}, i ∈ {0, …, k − 1}} ⊆ S.

For each a, b ∈ ℤ_{p}, define

A_{a,b} = {(i, j); j = ai + b (mod p), i ∈ {0, …, k − 1}},

and take K = {A_{a,b}|a, b ∈ ℤ_{p}}. The set K is easily checked to satisfy the requirements.

Lemma 3. Let H be a k-vertex graph and let s > 2k^{2}. The probability that a random graph G ∈ G(s, 1/2) does not contain an induced subgraph isomorphic to H, is at most (1 − 2^{−\binom{k}{2}})^{⌊^{\frac{s}{2k}}⌋}^{2}.

Proof. Construct, as in Lemma 2, an almost disjoint family F of ⌊\frac{s}{2k}⌋^{2} subsets of \{1, …, s\}, the vertex set of G. If F_{1} ≠ F_{2} ∈ F, then the event that the restriction of G to F_{1} (resp. F_{2}) is isomorphic to H are independent. Hence, the probability that none of the sets F ∈ F spans a subgraph isomorphic to H is at most (1 − 2^{−\binom{k}{2}})^{⌊^{\frac{s}{2k}}⌋}^{2}.

Proof of Proposition 1. Let G be a random graph in G(n, 1/2). By the previous lemma, the expected number of sets of s vertices which contain no induced isomorphic copy of H is at

most \binom{n}{s} (1 − 2^{−\binom{k}{2}})^{⌊^{\frac{s}{2k}}⌋}^{2}. If this number is < 1, then there is an (H, s)-universal graph, as claimed. It is an easy matter to check that this holds with the parameters as stated.

A class C of finite metric spaces is called a metric class if it is closed under isometries. C is said to be hereditary, if M ∈ C and N ⊂ M imply N ∈ C. We call a metric space (X, d) a {0, 1, 2} metric space if for all x, y ∈ X, d(x, y) ∈ {0, 1, 2}. There is a simple 1:1 correspondence between graphs and {0, 1, 2} metrics. Namely, associated with a {0, 1, 2} metric space M = (X, d) is the graph G = (X, E) where [x, y] ∈ E iff d_{M}(x, y) = 1.

Lemma 4. Let C be a hereditary metric class of finite metric spaces, and suppose that there exists some finite {0, 1, 2} metric space M_{0} which is not in P. Then there exist metric spaces M = M_{n} of arbitrarily large size n such that every subspace S ⊂ M_{n} with at least C log n points is not in C. The constant C depends only on the cardinality of M_{0}.

Proof. Let H_{0} be the graph corresponding to the metric space M_{0}. We apply Proposition 1, to construct arbitrarily large graphs G_{n} = (V_{n}, E_{n}) with |V_{n}| = n, in which every set of ≥ C log n vertices contains an induced subgraph isomorphic to H_{0}. Let M_{n} be the n-point metric space corresponding to G_{n}. It follows that every subspace of M_{n} of size ≥ C log n contains a metric subspace that is isometric to M_{0}. Since C is hereditary, S ∉ C.

Note that {M; M is a metric space, c_{p}(M) ≤ α} is a hereditary metric class. Therefore, in order to show that for α < 2, R_{p}(α, n) = O(log n), it is enough to find a {0, 1, 2} metric space whose ℓ_{p} distortion is greater than α. We use the complete bipartite graphs K_{n,n}. The ℓ_{p}-distortion of K_{n,n}, 1 ≤ p < ∞, is estimated in the following proposition.

Proposition 5. For every 1 ≤ p ≤ 2,

2 (\frac{n − 1}{n})^{1/p} ≤ c_{p}(K_{n,n}) ≤ 2\sqrt{\frac{n − 1}{n}}

For every 2 ≤ p < ∞,

2^{2/p} (\frac{n − 1}{n})^{1/p} ≤ c_{p}(K_{n,n}) ≤ 2^{2/p} (1 − \frac{1}{2n})^{1/p} .

Before proving Proposition 5, we will deduce the main result of this section:

Theorem 5. There is an absolute constant c > 0 such that for every 0 < δ < 1, if 1 ≤ p ≤ 2 then:

R_{p}(2 − δ, n) ≤ e^{\frac{c}{δ^{2}}} log n,

and if 2 < p < ∞ then:

R_{p}(2^{2/p} − δ, n) ≤ e^{\frac{c}{p^{2}δ^{2}}} log n.

Proof. Proposition 1 implies that there is an absolute constant C such that for every n ≥ 2^{Ck^{3}} there exists a {0, 1, 2} metric space M_{n} such that any subset S ⊂ M_{n} of cardinality at least 2^{Ck^{2}} log n contains an isometric copy of K_{k,k}.

We start with 1 ≤ p ≤ 2. Let k = ⌊\frac{2}{δ}⌋ + 1. By Proposition 5,

c_{p}(K_{k,k}) ≥ 2 (1 − \frac{1}{k} )^{1/p} > 2 (1 − \frac{δ}{2}) = 2 − δ,

so that for n large enough (≥ e^{\frac{C′}{δ^{3}}} ), and hence for all n (by proper choice of constants),

R_{p}(2 − δ, n) ≤ e^{\frac{C′}{δ^{2}}} log n.

When p > 2 take k = 2 ⌊\frac{4}{pδ} ⌋. In this case one easily verifies that:

c_{p}(K_{k,k}) ≥ 2^{2/p} (1 − \frac{1}{k} )^{1/p} ≥ 2^{2/p} − δ,

from which the required result follows as above.

Preliminary to the proof of Proposition 5, we require some preparation.

Lemma 6. Let A = (a_{ij}) be an n × n matrix and 2 ≤ p < ∞. Then:

∑_{i=1}^{n} ∑_{j=1}^{n} (|∑_{k=1}^{n} a_{ik} − ∑_{k=1}^{n} a_{jk}|^{p} + |∑_{k=1}^{n} a_{ki} − ∑_{k=1}^{n} a_{kj}|^{p}) ≤ \frac{(2n)^{p}}{2} ∑_{i=1}^{n} ∑_{j=1}^{n} |a_{ij}|^{p}.

Proof. We identify ℓ_{p}^{n^{2}} with space of all n × n matrices A = (a_{ij}), equipped with the ℓ_{p} norm:

∥A∥_{p} = (∑_{i=1}^{n} ∑_{j=1}^{n} |a_{ij}|^{p})^{1/p} .

Define a linear operator T : ℓ_{p}^{n^{2}} → ℓ_{p}^{n^{2}} ⊕ ℓ_{p}^{n^{2}} by:

T (a_{ij}) = (∑_{k=1}^{n} a_{ik} − ∑_{k=1}^{n} a_{jk})_{ij} ⊕ (∑_{k=1}^{n} a_{ki} − ∑_{k=1}^{n} a_{kj})_{ij} .

Our goal is to show that ∥T ∥_{p→p} ≤ 2^{1−1/p}n. By standard results from the complex interpolation theory (see [2]), it is enough to prove this estimate for p = 2 and p = ∞. The case p = ∞ is simple:

∥T (A)∥_{∞} = max_{1≤i,j≤n} max {|∑_{k=1}^{n} a_{ik} − ∑_{k=1}^{n} a_{jk}| , |∑_{k=1}^{n} a_{ki} − ∑_{k=1}^{n} a_{kj}|} ≤ 2n∥A∥_{∞}.

For p = 2 we have to show that:

∑_{i=1}^{n} ∑_{j=1}^{n} (|∑_{k=1}^{n} a_{ik} − ∑_{k=1}^{n} a_{jk}|^{2} + |∑_{k=1}^{n} a_{ki} − ∑_{k=1}^{n} a_{kj}|^{2}) ≤ 2n^{2} ∑_{i=1}^{n} ∑_{j=1}^{n} |a_{ij}|^{2}.

This inequality follows from the following elementary identity:

2n^{2} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}^{2}

= ∑_{i=1}^{n} ∑_{j=1}^{n} [(∑_{k=1}^{n} a_{ik} − ∑_{k=1}^{n} a_{jk})^{2} + (∑_{k=1}^{n} a_{ki} − ∑_{k=1}^{n} a_{kj})^{2}] +

+2 ∑_{i=1}^{n} ∑_{j=1}^{n} (na_{ij} − ∑_{k=1}^{n} a_{ik} − ∑_{k=1}^{n} a_{kj})^{2} .

Corollary 7. Let 1 ≤ p < ∞ and x_{1}, …, x_{n}, y_{1} … y_{n} ∈ ℓ_{p}. Then if 2 ≤ p < ∞,

∑_{i=1}^{n} ∑_{j=1}^{n} (∥x_{i} − x_{j}∥_{p}^{p} + ∥y_{i} − y_{j}∥_{p}^{p}) ≤ 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − y_{j}∥_{p}^{p}.

If 1 ≤ p ≤ 2 then:

∑_{i=1}^{n} ∑_{j=1}^{n} (∥x_{i} − x_{j}∥_{p}^{p} + ∥y_{i} − y_{j}∥_{p}^{p}) ≤ 2 ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − y_{j}∥_{p}^{p}.

Proof. By summation it is clearly enough to prove these inequalities for x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ ℝ. If 2 ≤ p < ∞ then the required result follows from an application of Lemma 6 to the matrix a_{ij} = x_{i} − y_{j}. If 1 ≤ p ≤ 2 then consider ℓ_{p} equipped with the metric d(x, y) = ∥x − y∥_{p}^{p/2}. It is well known (see [12]) that (ℓ_{p}, d) embeds isometrically in ℓ_{2}, so that the case 1 ≤ p ≤ 2 follows from the case p = 2.

Remark. In [7] P. Enflo defined the notion on generalized roundness of a metric space. A metric space (M, d) is said to have generalized roundness q ≥ 0 if for every x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ M,

∑_{i=1}^{n} ∑_{j=1}^{n}(d(x_{i}, x_{j})^{q} + d(y_{i}, y_{j})^{q}) ≤ 2 ∑_{i=1}^{n} ∑_{j=1}^{n} d(x_{i}, y_{j})^{q}.

Enflo proved that Hilbert space has generalized roundness 2 and in [10] the concept of generalized roundness was investigated and was shown to be equivalent to the notion of negative type (see [5, 12] for the definition). Particularly, it was proved in [10] that for 1 ≤ p < 2, ℓ_{p} has generalized roundness p, which is precisely the second statement in Corollary 7. In [10] it was also shown that for 2 ≤ p < ∞, ℓ_{p} doesn’t have generalized roundness q for any q > 0. Finally, we would like to remark that the case p = 1 of Corollary 7 has a particularly simple proof using density functions. As before it is enough to prove that for x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ ℝ,

∑_{i=1}^{n} ∑_{j=1}^{n}(|x_{i} − x_{j}| + |y_{i} − y_{j}|) ≤ 2 ∑_{i=1}^{n} ∑_{j=1}^{n} |x_{i} − y_{j}|.  (1)

Define for x ∈ ℝ:

I(x) = |{i ∈ {1, …, n}; x_{i} ≤ x}|,
J(x) = |{i ∈ {1, …, n}; y_{i} ≤ x}|.

Let:

f_{L}(x) = I(x)(n − I(x)) + J(x)(n − J(x)),
f_{R}(x) = I(x)(n − J(x)) + J(x)(n − I(x)).

Then:

2 ∑_{i=1}^{n} ∑_{j=1}^{n} |x_{i} − y_{j}| − ∑_{i=1}^{n} ∑_{j=1}^{n}(|x_{i} − x_{j}| + |y_{i} − y_{j}|)

= 2 ∫_{−∞}^{∞} f_{R}(x)dx − 2 ∫_{−∞}^{∞} f_{L}(x)dx
= 2 ∫_{−∞}^{∞}[I(x)(n − J(x)) + J(x)(n − I(x)) − I(x)(n − I(x)) − J(x)(n − J(x))]dx
= 2 ∫_{−∞}^{∞}[I(x) − J(x)]^{2}dx ≥ 0.

Proof of Proposition 5. We identify K_{n,n} with the metric on {u_{1}, …, u_{n}, v_{1}, …, v_{n}} where d(u_{i}, u_{j}) = d(v_{i}, v_{j}) = 2 for all i ≠ j, and d(u_{i}, v_{j}) = 1 for every 1 ≤ i, j ≤ n. Fix some 1 ≤ p < ∞ and let f : {u_{1}, …, u_{n}, v_{1}, …, v_{n}} → ℓ_{p} be an embedding such that for every x, y ∈ K_{n,n}, d(x, y) ≤ ∥f(x) − f(y)∥_{p} ≤ Ld(x, y). Then,

∑_{i=1}^{n} ∑_{j=1}^{n}(∥f(u_{i}) − f(u_{j})∥_{p}^{p} + ∥f(v_{i}) − f(v_{j})∥_{p}^{p}) ≥ 2n(n − 1)2^{p},

and

∑_{i=1}^{n} ∑_{j=1}^{n} ∥f(u_{i}) − f(v_{j})∥_{p}^{p} ≤ n^{2}L^{p}.

For 1 ≤ p ≤ 2 Corollary 7 gives:

2n(n − 1)^{p}2^{p} ≤ 2n^{2}L^{p} ⟹ L ≥ 2 (\frac{n − 1}{n})^{1/p} .

For 2 ≤ p < ∞ we get that:

2n(n − 1)2^{p} ≤ 2^{p−1}n^{2}L^{p} ⟹ L ≥ 2^{2/p} (\frac{n − 1}{n})^{1/p} .

This proves the required lower bounds on c_{p}(K_{n,n}).

To prove the upper bound assume first that p = 2 and denote by {e_{i}}_{i=1}^{∞} the standard unit vectors in ℓ_{2}. Define f : K_{n,n} → ℓ_{2}^{2n} by:

f(u_{i}) = \sqrt{2}(e_{i} − \frac{1}{n} ∑_{j=1}^{n} e_{j}),

f(v_{i}) = \sqrt{2}(e_{n+i} − \frac{1}{n} ∑_{j=1}^{n} e_{n+j}).

Then for i ≠ j, ∥f(u_{i}) − f(u_{j})∥_{2} = ∥f(v_{i}) − f(v_{j})∥_{2} = d(u_{i}, u_{j}) = d(v_{i}, v_{j}). On the other hand:

∥f(u_{i}) − f(v_{j})∥_{2} = \sqrt{∥f(u_{i})∥_{2}^{2} + ∥f(v_{j})∥_{2}^{2}}
= \sqrt{4 (1 − \frac{1}{n})^{2} + 4(n − 1) · \frac{1}{n^{2}}} = 2\sqrt{\frac{n − 1}{n}}.

This finishes the calculation of c_{2}(K_{n,n}). For 1 ≤ p < 2, since for every ϵ > 0 and for every

k, ℓ_{p} contains a (1 + ϵ) distorted copy of ℓ_{2}^{k}, we get the estimate c_{p}(K_{n,n}) ≤ 2\sqrt{\frac{n−1}{n}}.

The case 2 < p < ∞ requires a different embedding. We begin by describing an embedding with distortion 2^{2/p} and then explain how to modify it so as to reduce the distortion by a factor of (1 − \frac{1}{2n})^{1/p}. Let z_{1}, …, z_{n} be a collection of n mutually orthogonal ±1 vectors of dimension m = O(n). (For example the first n rows in an m × m Hadamard matrix). In our first embedding we define f(u_{i}) as the (2m)-dimensional vector (z_{i}, 0), namely, z_{i} concatenated with m zeros. Likewise, f(v_{i}) = (0, z_{i}) for all i. Now ∥f(u_{i}) − f(u_{j})∥_{p} = 2 (\frac{m}{2})^{1/p} and ∥f(u_{i}) − f(v_{j})∥_{p} = (2m)^{1/p}, and so f has distortion 2^{2/p}. To get the (1 − \frac{1}{2n})^{1/p} improvement, note that for some m ≤ 4n it is possible to select the z_{i} so that the m-th coordinate in all of them is +1. Modify the previous construction to an embedding into 2m − 1 dimensions as follows: Now g(u_{i}) is z_{i} concatenated with m − 1 zeros, whereas g(v_{i}) has zeros in the first m − 1 coordinates, 1 in the m-th and this is followed by the first m − 1 coordinates of the vector z_{i}. The easy details are omitted.

Remark: The upper bounds in Proposition 5 were not used in the proof of Theorem 5. Apart from their intrinsic interest, these upper estimates show that the above technique cannot prove an upper bound of O(log n) on R_{2}(2 − ϵ, n) which is independent of ϵ. In fact, this can never be achieved using {0, 1, 2} metric spaces due to the following proposition.

Proposition 8. Let X be an n-point \{0, 1, 2\} metric space. Then c_{2}(X) ≤ 2\sqrt{\frac{n−1}{n}}.

Proof. We think of X as a metric on {1, …, n} and denote d(i, j) = d_{ij}. Define an n × n matrix A as follows:

A_{ij} = \begin{cases}2 & if i = j \\ 0 & if d_{ij} = 2 \\ \frac{2}{n} & if d_{ij} = 1 \end{cases} .

We claim that A is positive semi-definite. Indeed, for any z ∈ ℝ^{n}

⟨Az, z⟩ = ∑_{i=1}^{n} ∑_{j=1}^{n} A_{ij}z_{i}z_{j}

≥ ∑_{i=1}^{n} 2z_{i}^{2} − ∑_{i≠j} \frac{2}{n}|z_{i}| · |z_{j}|

≥ ∑_{i=1}^{n} 2z_{i}^{2} − ∑_{i=1}^{n} ∑_{j=1}^{n} \frac{2}{n}|z_{i}| · |z_{j}|

= 2∥z∥_{2}^{2} − \frac{2}{n}∥z∥_{1}^{2} ≥ 2∥z∥_{2}^{2} − \frac{2}{n}n∥z∥_{2}^{2} = 0.

Let e_{1}, …, e_{n} be the standard unit vectors in ℝ^{n}. Define f : X → ℝ^{n} by f(i) = A^{1/2}e_{i}. Now,

∥f(i) − f(j)∥_{2}^{2} = ⟨Ae_{i}, e_{i}⟩ + ⟨Ae_{j}, e_{j}⟩ − 2⟨Ae_{i}, e_{j}⟩ = A_{ii} + A_{jj} − 2A_{ij},

so that if d_{ij} = 1 then ∥f(i) − f(j)∥_{2} = \sqrt{4 − \frac{4}{n}} and if d_{ij} = 2 then ∥f(i) − f(j)∥_{2} = 2. It follows that

dist(f) = 2\sqrt{\frac{n − 1}{n}}.

3 The Isometric Ramsey Problem

In this section we prove that for n ≥ 3, 1 < p < ∞, R_{p}(n) = R_{p}(1, n) = 3. In fact, we show that this is true for any uniformly convex normed space. We begin by sketching an argument that is specific to ℓ_{2}:

Proposition 9. R_{2}(n) = 3 for n ≥ 3.

Proof. That R_{2}(n) ≥ 3 follows since any metric space on 3 points embeds isometrically in ℓ_{2}^{2}. To show that R_{2}(n) ≤ 3, we construct a metric space on n > 3 points, no 4 point subspace of which embeds isometrically in ℓ_{2}. Fix an integer n > 3 and let {a_{i}}_{i=0}^{n} be an increasing sequence such that a_{0} = 0, a_{1} = 1 and for 1 ≤ i < n, a_{i+1} ≥ 2(n + 1)a_{i}. Fix some 0 < ϵ < 1/(2a_{n}). It is easily verified that d(i, j) = |i − j| − ϵa_{|i−j|} is a metric on {1, 2, …, n}. We show that for ϵ small enough no four points in ({1, …, }, d) embed isometrically in ℓ_{2}. Fix four integers 1 ≤ i_{1} < i_{2} < i_{3} < i_{4} ≤ n and set j = i_{2} − i_{1}, k = i_{3} − i_{2}, l = i_{4} − i_{3}. Suppose that for every ϵ > 0 there exists an isometric embedding f : ({i_{1}, i_{2}, i_{3}, i_{4}}, d) → ℓ_{2}^{3}. Without loss of generality we may assume that f(i_{1}) = (α, β, γ), f(i_{2}) = (0, 0, 0), f(i_{3}) = (k − ϵa_{k}, 0, 0) and f(i_{4}) = (p, q, 0). Then:

2α(k − ϵa_{k}) = 2⟨f(i_{1}), f(i_{3})⟩
= ∥f(i_{1}) − f(i_{2})∥_{2}^{2} + ∥f(i_{3}) − f(i_{2})∥_{2}^{2} − ∥f(i_{3}) − f(i_{1})∥_{2}^{2}
= (j − ϵa_{j})^{2} + (k − ϵa_{k})^{2} − (j + k − ϵa_{j+k})^{2}.

Hence,

α ≤ −j + \frac{ϵ}{k} [(k + j)a_{k+j} − ja_{j} − ka_{k} − ja_{k}] + O(ϵ^{2}).

Similarly:

p ≥ (k + l) + \frac{ϵ}{k} [(k + l)a_{k} − (k + l)a_{k+l} − ka_{k} + la_{l}] + O(ϵ^{2}).

Now:

j + k + l − ϵa_{j+k+l} =
= ∥f(i_{4}) − f(i_{1})∥_{2}
≥ p − α
≥ j + k + l + \frac{ϵ}{k} [(k + l)a_{k} − (k + l)a_{k+l} + la_{l} − (k + j)a_{k+j} + ja_{j} + ja_{k}] + O(ϵ^{2}).

Letting ϵ tend to zero we deduce that:

a_{j+k+l} ≤
≤ (1 + \frac{j}{k} ) a_{k+j} + (1 + \frac{l}{k} ) a_{k+l} − \frac{l}{k} a_{l} − \frac{j}{k} a_{j} − \frac{j + k + l}{k}a_{k} < 2(n + 1)a_{j+k+l−1},

which is a contradiction.

The argument above is quite specific to ℓ_{2}, and so we now consider any uniformly convex normed space. The modulus of uniform convexity of a normed space X is defined by:

δ_{X}(ϵ) = inf \{1 − \frac{∥a + b∥}{2}; ∥a∥, ∥b∥ ≤ 1 and ∥a − b∥ ≥ ϵ\} .

X is said to be uniformly convex if δ_{X}(ϵ) > 0 for every 0 < ϵ ≤ 2. The L_{p} spaces 1 < p < ∞, are known to be uniformly convex. For a uniformly convex space X, δ_{X} is known to be continuous and strictly increasing on (0, 2].

Assume that X is a uniformly convex normed space and a, b ∈ X \ {0}. Then:

∥\frac{a}{∥a∥} + \frac{b}{∥b∥}∥ =
= ∥(\frac{1}{∥a∥} + \frac{1}{∥b∥}) (a + b) − \frac{a}{∥b∥} − \frac{b}{∥a∥}∥
≥ (\frac{1}{∥a∥} + \frac{1}{∥b∥}) ∥a + b∥ − \frac{∥a∥}{∥b∥} − \frac{∥b∥}{∥a∥}
= 2 − (\frac{1}{∥a∥} + \frac{1}{∥b∥}) (∥a∥ + ∥b∥ − ∥a + b∥).

Now,

δ_{X} (∥\frac{a}{∥a∥} − \frac{b}{∥b∥}∥) ≤
≤ 1 − \frac{1}{2} · ∥\frac{a}{∥a∥} + \frac{b}{∥b∥}∥ ≤ \frac{1}{2} · (\frac{1}{∥a∥} + \frac{1}{∥b∥}) (∥a∥ + ∥b∥ − ∥a + b∥).

Hence

∥\frac{a}{∥a∥} − \frac{b}{∥b∥}∥ ≤ δ_{X}^{−1} (\frac{1}{2} · (\frac{1}{∥a∥} + \frac{1}{∥b∥}) (∥a∥ + ∥b∥ − ∥a + b∥)) .

Take x, y, z ∈ X and apply this inequality for a = x − y, b = y − z. It follows that:

∥y − (\frac{∥y − z∥}{∥x − y∥ + ∥y − z∥} · x + \frac{∥x − y∥}{∥x − y∥ + ∥y − z∥} · z)∥ ≤

≤ \frac{∥x − y∥ · ∥y − z∥}{∥x − y∥ + ∥y − z∥} · δ_{X}^{−1} (\frac{∥x − y∥ + ∥y − z∥ − ∥x − z∥}{min\{∥x − y∥, ∥y − z∥\}}) .

This inequality is the way uniform convexity is going to be applied in the sequel. Indeed, we have the following “metric” consequence of it:

Lemma 10. Let X be a uniformly convex normed space and x_{1}, x_{2}, x_{3}, x_{4} ∈ X be distinct. Then:

\frac{∥x_{1} − x_{2}∥ + ∥x_{2} − x_{3}∥ − ∥x_{1} − x_{3}∥}{2∥x_{2} − x_{3}∥} ≤
≤ δ_{X}^{−1} (\frac{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{1} − x_{4}∥}{min\{∥x_{1} − x_{3}∥, ∥x_{3} − x_{4}∥\}}) +

+δ_{X}^{−1} (\frac{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{2} − x_{4}∥}{min\{∥x_{2} − x_{3}∥, ∥x_{3} − x_{4}∥\}}) .

Proof. Define:

λ = \frac{∥x_{3} − x_{4}∥}{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥} and μ = \frac{∥x_{3} − x_{4}∥}{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥}.

An application of the above inequality twice gives:

∥x_{3} −(λx_{1} +(1−λ)x_{4})∥ ≤ \frac{∥x_{1} − ∥x_{3}∥ · ∥x_{3} − x_{4}∥}{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥} ·δ_{X}^{−1} (\frac{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{1} − x_{4}∥}{min\{∥x_{1} − x_{3}∥, ∥x_{3} − x_{4}∥\}}) ,

and

∥x_{3}−(μx_{2}+(1−μ)x_{4})∥ ≤ \frac{∥x − 2 − x_{3}∥ · ∥x_{3} − x_{4}∥}{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥} ·δ_{X}^{−1} (\frac{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{2} − x_{4}∥}{min\{∥x_{2} − x_{3}∥, ∥x_{3} − x_{4}∥\}})

By symmetry, we may assume without loss of generality that λ ≤ μ. Now,

∥x_{2} − \frac{λ(1 − μ)}{μ(1 − λ)}x_{1} − \frac{μ − λ}{μ(1 − λ)}x_{3}∥ ≤
= \frac{1}{μ} ∥μx_{2} + (1 − μ)x_{4} − x_{3} + \frac{1 − μ}{1 − λ}(x_{3} − λx_{1} − (1 − λ)x_{4})∥
≤ \frac{1}{μ}∥x_{3} − μx_{2} − (1 − μ)x_{4}∥ + \frac{1 − μ}{μ(1 − λ)} · ∥x_{3} − λx_{1} − (1 − λ)x_{4}∥
≤ \frac{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥}{∥x_{3} − x_{4}∥} · \frac{∥x_{2} − x_{3}∥ · ∥x_{3} − x_{4}∥}{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥} ·

·δ_{X}^{−1} (\frac{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{2} − x_{4}∥}{min\{∥x_{2} − x_{3}∥, ∥x_{3} − x_{4}∥\}}) +

+\frac{∥x_{2} − x_{3}∥}{∥x_{3} − x_{4}∥} \frac{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥}{∥x_{1} − x_{3}∥} \frac{∥x_{1} − ∥x_{3}∥ · ∥x_{3} − x_{4}∥}{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥} ·

·δ_{X}^{−1} (\frac{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{1} − x_{4}∥}{min\{∥x_{1} − x_{3}∥, ∥x_{3} − x_{4}∥\}})

= ∥x_{2} − x_{3}∥δ_{X}^{−1} (\frac{∥x_{1} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{1} − x_{4}∥}{min\{∥x_{1} − x_{3}∥, ∥x_{3} − x_{4}∥\}}) +

+∥x_{2} − x_{3}∥δ_{X}^{−1} (\frac{∥x_{2} − x_{3}∥ + ∥x_{3} − x_{4}∥ − ∥x_{2} − x_{4}∥}{min\{∥x_{2} − x_{3}∥, ∥x_{3} − x_{4}∥\}}) .

Additionally,

∥x_{2} − x_{1}∥ ≤
≤ ∥x_{2} − \frac{λ(1 − μ)}{μ(1 − λ)}x_{1} − \frac{μ − λ}{μ(1 − λ)}x_{3}∥ + ∥x_{1} − \frac{λ(1 − μ)}{μ(1 − λ)}x_{1} − \frac{μ − λ}{μ(1 − λ)}x_{3}∥
= ∥x_{2} − \frac{λ(1 − μ)}{μ(1 − λ)}x_{1} − \frac{μ − λ}{μ(1 − λ)}x_{3}∥ + \frac{μ − λ}{μ(1 − λ)}∥x_{1} − x_{3}∥,

and

∥x_{2} − x_{3}∥ ≤
≤ ∥x_{2} − \frac{λ(1 − μ)}{μ(1 − λ)}x_{1} − \frac{μ − λ}{μ(1 − λ)}x_{3}∥ + ∥x_{3} − \frac{λ(1 − μ)}{μ(1 − λ)}x_{1} − \frac{μ − λ}{μ(1 − λ)}x_{3}∥
= ∥x_{2} − \frac{λ(1 − μ)}{μ(1 − λ)}x_{1} − \frac{μ − λ}{μ(1 − λ)}x_{3}∥ + \frac{λ(1 − μ)}{μ(1 − λ)}∥x_{1} − x_{3}∥.

Summing up these estimates gives the required result.

We can now prove the main result of this section:

Theorem 6. Let X be a uniformly convex normed space with dim(X) ≥ 2. Then for every n ≥ 3, R_{X}(n) = 3. Moreover, for every δ : (0, 2] → (0, ∞) which is continuous, increasing and δ ≤ δ_{ℓ_{2}}, let UC_{δ} be the class of all normed spaces X with δ_{X} ≥ δ. Then for each n ≥ 3 there is a constant ϵ_{n}(δ) > 0 such that R_{UC_{δ}}(1 + ϵ_{n}(δ), n) = 3.

Proof. That R_{X}(n) ≥ 3 follows since any 3 point metric embeds isometrically into any 2 dimensional normed space, by a standard continuity argument.

Fix some δ : (0, 2] → (0, ∞) which is continuous, increasing and δ ≤ δ_{ℓ_{2}}. We shall construct inductively a sequence {M_{n}}_{n=3}^{∞} of metric spaces and numbers {η_{n}}_{n=3}^{∞} such that:

a) For every n ≥ 3, η_{n} > 0. Each M_{n} is a metric on {1, …, n}, and we denote d_{ij}^{n} = d_{M_{n}}(i, j).

b) For every 1 ≤ i < j < k ≤ n,

d_{i,j}^{n} + d_{jk}^{n} − d_{i,k}^{n} − η_{n} ≥ 2d_{j,k}^{n} [δ^{−1} (\frac{d_{i,k}^{n} + d_{k,n}^{n} − d_{i,n}^{n}}{min\{d_{i,k}^{n}, d_{k,n}^{n}\}} ) + δ^{−1} (\frac{d_{j,k}^{n} + d_{k,n}^{n} − d_{j,n}^{n}}{min\{d_{j,k}^{n}, d_{k,n}^{n}\}} )] .

Lemma 10 immediately implies that there is a constant ϵ_{n}(δ) > 0 such that for every 1 ≤ i < j < k < l ≤ n and for every normed space X with δ_{X} ≥ δ:

c_{X}({i, j, k, l}, d_{M_{n}}) ≥ 1 + ϵ_{n}(δ),

as required.

M_{3} is the equilateral metric on {1, 2, 3}, in which case η_{3} = 1. We construct M_{n+1} = ({1, …, n + 1}, d^{n+1}) as an extension of M_{n}, by setting

d_{n,n+1}^{n+1} = 1 − s/2 and ∀1 ≤ i < n, d_{i,n+1}^{n+1} = d_{in}^{n} + 1 − s.

This is indeed a definition of a metric as long as 0 < s ≤ min{1, 2 min_{1≤i<n} d_{i,n}^{n}} (this fact follows from a simple case analysis).

We are left to check condition b). Fix 1 ≤ i < j < k ≤ n. If k ≠ n then:

d_{i,j}^{n+1} + d_{j,k}^{n+1} − d_{i,k}^{n+1} − η_{n} = d_{i,j}^{n} + d_{j,k}^{n} − d_{i,k}^{n} − η_{n}
≥ 2d_{j,k}^{n} [δ^{−1} (\frac{d_{i,k}^{n} + d_{k,n}^{n} − d_{i,n}^{n}}{min\{d_{i,k}^{n}, d_{k,n}^{n}\}} ) + δ^{−1} (\frac{d_{j,k}^{n} + d_{k,n}^{n} − d_{j,n}^{n}}{min\{d_{j,k}^{n}, d_{k,n}^{n}\}} )]

≥ 2d_{j,k}^{n} [δ^{−1} (\frac{d_{i,k}^{n} + (d_{k,n}^{n} + 1 − s) − (d_{i,n}^{n} + 1 − s)}{min\{d_{i,k}^{n}, d_{k,n}^{n} + 1 − s\}})

+δ^{−1} (\frac{d_{j,k}^{n} + (d_{k,n}^{n} + 1 − s) − (d_{j,n}^{n} + 1 − s)}{min\{d_{j,k}^{n}, d_{k,n}^{n} + 1 − s\}})]

= 2d_{j,k}^{n+1} [δ^{−1} (\frac{d_{i,k}^{n+1} + d_{k,n+1}^{n+1} − d_{i,n+1}^{n+1}}{min\{d_{i,k}^{n+1}, d_{k,n+1}^{n+1}\}} ) + δ^{−1} (\frac{d_{j,k}^{n+1} + d_{k,n+1}^{n+1} − d_{j,n+1}^{n+1}}{min\{d_{j,k}^{n+1}, d_{k,n+1}^{n+1}\}} )] .

It remains to check b) for the quadruple {i, j, n, n + 1}. Condition b) for M_{n} implies that:

d_{ij}^{n+1} + d_{jn}^{n+1} − d_{in}^{n+1} ≥ η_{n}.

On the other hand,

2d_{j,n}^{n+1} [δ^{−1} (\frac{d_{i,n}^{n+1} + d_{n,n+1}^{n+1} − d_{i,n+1}^{n+1}}{min\{d_{i,n}^{n+1}, d_{n,n+1}^{n+1}\}} ) + δ^{−1} (\frac{d_{j,n}^{n+1} + d_{n,n+1}^{n+1} − d_{j,n+1}^{n+1}}{min\{d_{j,n}^{n+1}, d_{n,n+1}^{n+1}\}} )] =

= 2d_{j,n}^{n} [δ^{−1} (\frac{s/2}{min\{d_{i,n}^{n}, 1 − s/2\}}) + δ^{−1} (\frac{s/2}{min\{d_{j,n}^{n}, 1 − s/2\}})] ,

so that condition b) will hold when s is small enough such that the quantity above is at most η_{n}/2 and with η_{n+1} = η_{n}/2.

Corollary 11. For all 1 < p < ∞, R_{p}(n) = 3 for n ≥ 3.

We end this section with a simple lower bound for the isometric Ramsey problem for graphs. We do not know what is the asymptotically correct bound in this setting.

Proposition 12. Let G be an un-weighted graph of order n. Then there is a set of Ω (\sqrt{\frac{log n}{log log n}}) vertices in G whose metric embeds isometrically into ℓ_{2}.

Proof. Let Δ be the diameter of G. The shortest path between two diameterically far vertices is isometrically embeddable in ℓ_{2}. On the other hand, the Bourgain,Figiel, Milman theorem [4] yields that for every 0 < ϵ < 1 a subset N ⊂ V which is (1 + ϵ) embeddable in Hilbert space and |N| = Ω (\frac{ϵ}{log(2/ϵ)} log n). When ϵ = \frac{1}{2Δ}, such an embedding is an isometry. Hence we can always extract a subset of V which is isometrically embeddable in ℓ_{2} with cardinality

Ω (max \{Δ, \frac{log n}{Δ log Δ}\}) = Ω (\sqrt{\frac{log n}{log log n}}) ,

as claimed.

Acknowledgments: The authors would like to express their gratitude to Guy Kindler for some helpful discussions.

References

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

[2] J. Bergh and J. Löfström. Interpolation spaces. An introduction. Springer-Verlag, Berlin, 1976. Grundlehren der Mathematischen Wissenschaften, No. 223.

[3] B. Bollobás. Random graphs. Cambridge University Press, Cambridge, second edition, 2001.

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

[5] M. M. Deza and M. Laurent. Geometry of cuts and metrics. Springer-Verlag, Berlin, 1997.

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

[7] P. Enflo. On a problem of Smirnov. Ark. Mat., 8:107–109, 1969.

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

[9] 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), pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

[10] C. J. Lennard, A. M. Tonge, and A. Weston. Generalized roundness and negative type. Michigan Math. J., 44(1):37–45, 1997.

[11] C. Lund and M. Yannakakis. The approximation of maximum subgraph problems. In ICALP, volume 700 of Lecture Notes in Computer Science. Springer, 1993.

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

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.