Skip to main content
SpringerLink
Log in

On embedding trees into uniformly convex Banach spaces

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

We investigate the minimum value ofD =D(n) such that anyn-point tree metric space (T, ρ) can beD-embedded into a given Banach space (X, ∥·∥); that is, there exists a mappingf :T →X with 1/D ρ(x,y) ≤ ∥f(x) −f(y)∥ ≤ρ(x,y) for anyx,y εT. Bourgain showed thatD(n) grows to infinity for any superreflexiveX (and this characterized super-reflexivity), and forX =ℓ p, 1 <p < ∞, he proved a quantitative lower bound of const·(log logn)min(1/2,1/p). We give another, completely elementary proof of this lower bound, and we prove that it is tight (up to the value of the constant). In particular, we show that anyn-point tree metric space can beD-embedded into a Euclidean space, with no restriction on the dimension, withD =O(√log logn).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Arias-de-Reyna and L. Rodríguez-Piazza,Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces, Israel Journal of Mathematics79 (1992), 103–113.

    Article  MATH  MathSciNet  Google Scholar 

  2. J. Bourgain,On Lipschitz embedding of finite metric spaces in Hilbert space, Israel Journal of Mathematics52 (1985), 46–52.

    Article  MATH  MathSciNet  Google Scholar 

  3. J. Bourgain,The metrical interpretation of superreflexivity in Banach spaces, Israel Journal of Mathematics56 (1986), 222–230.

    Article  MATH  MathSciNet  Google Scholar 

  4. J. Bourgain, V. Milman and H. Wolfson,On type of metric spaces, Transactions of the American Mathematical Society294 (1986), 295–317.

    Article  MATH  MathSciNet  Google Scholar 

  5. A. W. M. Dress,Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Advances in Mathematics53 (1984), 321–402.

    Article  MATH  MathSciNet  Google Scholar 

  6. P. Enflo,On a problem of Smirnov, Arkiv för Matematik8 (1969), 107–109.

    Article  MathSciNet  Google Scholar 

  7. P. Enflo,On the nonexistence of uniform homeomorphisms between L p-spaces, Arkiv för Matematik8 (1969), 103–105.

    Article  MathSciNet  Google Scholar 

  8. W. Johnson and J. Lindenstrauss,Extensions of Lipschitz maps into a Hilbert space, Contemporary Mathematics26 (Conference in Modern Analysis and Probability), 1984, pp. 189–206.

    MATH  MathSciNet  Google Scholar 

  9. W. Johnson, J. Lindenstrauss and G. Schechtman,On Lipschitz embedding of finite metric spaces in low dimensional normed spaces, inGeometrical Aspects of Functional Analysis (J. Lindenstrauss and V. D. Milman, eds.), Lecture Notes in Mathematics1267, Springer-Verlag, Berlin-Heidelberg, 1987.

    Chapter  Google Scholar 

  10. N. Linial, E. London and Y. Rabinovich,The geometry of graphs and some of its algorithmic applications, Combinatorica15 (1995), 215–245.

    Article  MATH  MathSciNet  Google Scholar 

  11. J. Matoušek,Lipschitz distance of metric spaces, (in Czech, with English summary), CSc. degree thesis, Charles University, Prague, 1989.

    Google Scholar 

  12. J. Matoušek,Bi-Lipschitz embeddings into low-dimensional Euclidean spaces, Commentationes Mathematicae Universitatis Carolinae31 (1990), 589–600.

    MathSciNet  Google Scholar 

  13. J. Matoušek,On the distortion required for embedding finite metric spaces into normed spaces, Israel Journal of Mathematics93 (1996), 333–344.

    Article  MathSciNet  Google Scholar 

  14. V. D. Milman and G. Schechtman,Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Mathematics1200, Springer-Verlag, Berlin, 1986.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic

    Jiří Matoušek

Authors
  1. Jiří Matoušek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jiří Matoušek.

Additional information

This paper contains results from my thesis [Mat89] from 1989. Since the subject of bi-Lipschitz embeddings is becoming increasingly popular, in 1997 I finally decided to publish this English version.

Supported by Czech Republic Grant GAČR 0194 and by Charles University grants No. 193, 194.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Matoušek, J. On embedding trees into uniformly convex Banach spaces. Isr. J. Math. 114, 221–237 (1999). https://doi.org/10.1007/BF02785579

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02785579

Keywords

Search

Navigation