On embeddings of finite metric spaces in l n ∞
Fedor Vladimirovich Petrov, Dmitriy Mikhailovich Stolyarov, Pavel B. Zatitskiy · 2009
We prove that for any given integer c> 0 any metric space on n points may be isometrically embedded into ln−c ∞ provided n is large enough. Let (X, ρ) be a metric space on n points. Denote by m(X) the minimal k such that X may be isometrically embedded in lk ∞ and by m(n) the maximum value of m(X) for all metric spaces X on n points. Denote also α(X) = n − m(X), α(n) = n − m(n). It is well known that m(n) ≤ n − 1. For as a vector space of example, one may fix a point x0 ∈ X and realize the l n−1 functions on X, which vanish in x0, endorsed with max-norm. Then the map x → ρ(x, ·) − ρ(x0, ·) defines isometric embedding of X into this space. It is proved by D. Wolfe that if n ≥ 4, then m(n) ≤ n −2 [5]. Using Ramsey-type graphs with n vertices without 4-cycles and k-anticliques K. Ball has shown [3] that m(n) ≥ n − k. He refered to Alon’s [1] explicit construction of such