Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Some applications of Ball's extension theorem

Authors: Manor Mendel and Assaf Naor
Journal: Proc. Amer. Math. Soc. 134 (2006), 2577-2584
MSC (2000): Primary 46B20; Secondary 51F99
Published electronically: February 17, 2006
MathSciNet review: 2213735
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We present two applications of Ball's extension theorem. First we observe that Ball's extension theorem, together with the recent solution of Ball's Markov type $ 2$ problem due to Naor, Peres, Schramm and Sheffield, imply a generalization, and an alternative proof of, the Johnson-Lindenstrauss extension theorem. Second, we prove that the distortion required to embed the integer lattice $ \{0,1,\ldots,m\}^n$, equipped with the $ \ell_p^n$ metric, in any $ 2$-uniformly convex Banach space is of order $ \min \left\{n^{\frac12-\frac{1}{p}},m^{1-\frac{2}{p}}\right\}$.

References [Enhancements On Off] (What's this?)

  • 1. K. Ball.
    Markov chains, Riesz transforms and Lipschitz maps.
    Geom. Funct. Anal., 2(2):137-172, 1992. MR 1159828 (93b:46025)
  • 2. K. Ball, E. A. Carlen, and E. H. Lieb.
    Sharp uniform convexity and smoothness inequalities for trace norms.
    Invent. Math., 115(3):463-482, 1994. MR 1262940 (95e:47027)
  • 3. B. Begun.
    A remark on almost extensions of Lipschitz functions.
    Israel J. Math., 109:151-155, 1999. MR 1679594 (2000a:26002)
  • 4. Y. Benyamini and J. Lindenstrauss.
    Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications.
    American Mathematical Society, Providence, RI, 2000. MR 1727673 (2001b:46001)
  • 5. J. Bourgain.
    Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms.
    In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 157-167. Springer, Berlin, 1987. MR 0907692 (88m:46021)
  • 6. J. Bourgain, V. Milman, and H. Wolfson.
    On type of metric spaces.
    Trans. Amer. Math. Soc., 294(1):295-317, 1986. MR 0819949 (88h:46033)
  • 7. B. Brinkman and M. Charikar.
    On the impossibility of dimension reduction in $ \ell_1$.
    In Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science. ACM, 2003.
  • 8. P. Enflo.
    On the nonexistence of uniform homeomorphisms between $ {L}\sb{p}$-spaces.
    Ark. Mat., 8:103-105, 1969. MR 0271719 (42:6600)
  • 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. MR 0737400 (86a:46018)
  • 10. J. R. Lee, M. Mendel, and A. Naor.
    Metric structures in $ L_1$: Dimension, snowflakes, and average distortion.
    European J. Combin., 2004.
    To appear.
  • 11. J. R. Lee and A. Naor.
    Absolute Lipschitz extendability.
    C. R. Math. Acad. Sci. Paris, 338(11):859-862, 2004. MR 2059662 (2005a:46047)
  • 12. J. R. Lee and A. Naor.
    Embedding the diamond graph in $ {L}_p$ and dimension reduction in $ {L}_1$.
    Geom. Funct. Anal., 14(4):745-747, 2004. MR 2084978 (2005g:46035)
  • 13. J. R. Lee and A. Naor.
    Extending Lipschitz functions via random metric partitions.
    Invent. Math., 160(1):59-95, 2005. MR 2129708
  • 14. J. Lindenstrauss and L. Tzafriri.
    Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas].
    Springer-Verlag, Berlin, 1979. MR 0540367 (81c:46001)
  • 15. N. Linial, E. London, and Y. Rabinovich.
    The geometry of graphs and some of its algorithmic applications.
    Combinatorica, 15(2):215-245, 1995. MR 1337355 (96e:05158)
  • 16. M. B. Marcus and G. Pisier.
    Characterizations of almost surely continuous $ p$-stable random Fourier series and strongly stationary processes.
    Acta Math., 152(3-4):245-301, 1984. MR 0741056 (86b:60069)
  • 17. J. Matoušek.
    On embedding expanders into $ l\sb p$ spaces.
    Israel J. Math., 102:189-197, 1997. MR 1489105 (98k:46014)
  • 18. B. Maurey and G. Pisier.
    Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach.
    Studia Math., 58(1):45-90, 1976. MR 0443015 (56:1388)
  • 19. M. Mendel and A. Naor.
    Metric cotype.
    Manuscript, 2004.
  • 20. V. D. Milman and G. Schechtman.
    Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics.
    Springer-Verlag, Berlin, 1986.
    With an appendix by M. Gromov. MR 0856576 (87m:46038)
  • 21. A. Naor.
    A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between $ L\sb p$ spaces.
    Mathematika, 48(1-2):253-271 (2003), 2001. MR 1996375 (2004f:46013)
  • 22. A. Naor, Y. Peres, O. Schramm, and S. Sheffield.
    Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces.
    Preprint, 2004.
  • 23. A. Naor and G. Schechtman.
    Remarks on non linear type and Pisier's inequality.
    J. Reine Angew. Math., 552:213-236, 2002. MR 1940437 (2003j:46010)
  • 24. G. Pisier.
    Probabilistic methods in the geometry of Banach spaces.
    In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167-241. Springer, Berlin, 1986. MR 0864714 (88d:46032)
  • 25. M. Talagrand.
    Embedding subspaces of $ L\sb 1$ into $ l\sp N\sb 1$.
    Proc. Amer. Math. Soc., 108(2):363-369, 1990. MR 0994792 (90f:46035)
  • 26. N. Tomczak-Jaegermann.
    Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics.
    Longman Scientific & Technical, Harlow, 1989. MR 0993774 (90k:46039)
  • 27. S. S. Vempala.
    The random projection method.
    DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 65. American Mathematical Society, Providence, RI, 2004.
    With a foreword by Christos H. Papadimitriou. MR 2073630 (2005j:68002)
  • 28. J. H. Wells and L. R. Williams.
    Embeddings and extensions in analysis, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.
    Springer-Verlag, New York, 1975. MR 0461107 (57:1092)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 46B20, 51F99

Retrieve articles in all journals with MSC (2000): 46B20, 51F99

Additional Information

Manor Mendel
Affiliation: Department of Computer Science, California Institute of Technology, Pasadena, California 91125
Address at time of publication: Computer Science Division, The Open University of Israel, 108 Ravutski Street, P.O.B. 808, Raanana 43107, Israel

Assaf Naor
Affiliation: Theory Group, Microsoft Research, Redmond, Washington 90852

Keywords: Lipschitz extension, bi-Lipschitz embeddings
Received by editor(s): January 27, 2005
Received by editor(s) in revised form: March 18, 2005
Published electronically: February 17, 2006
Communicated by: David Preiss
Article copyright: © Copyright 2006 American Mathematical Society

American Mathematical Society