Available in electronic format
Available in print format
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826 (e) ISSN 0002-9939 (p)
     

Some applications of Ball's extension theorem

Author(s): Manor Mendel; Assaf Naor
Journal: Proc. Amer. Math. Soc. 134 (2006), 2577-2584.
MSC (2000): Primary 46B20; Secondary 51F99
Posted: February 17, 2006
Retrieve article in: PDF DVI PostScript

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:

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
Email: manorme@openu.ac.il

Assaf Naor
Affiliation: Theory Group, Microsoft Research, Redmond, Washington 90852
Email: anaor@microsoft.com

DOI: 10.1090/S0002-9939-06-08298-0
PII: S 0002-9939(06)08298-0
Keywords: Lipschitz extension, bi-Lipschitz embeddings
Received by editor(s): January 27, 2005
Received by editor(s) in revised form: March 18, 2005
Posted: February 17, 2006
Communicated by: David Preiss
Copyright of article: Copyright 2006, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google