Metric cotype

ABSTRACT

We introduce the notion of metric cotype, a property of metric spaces related to a property of normed spaces, called Rademacher cotype. Apart from settling a long standing open problem in metric geometry, this property is used to prove the following dichotomy: A family of metric spaces F is either almost universal (i.e., contains any finite metric space with any distortion > 1), or there exists α > 0, and arbitrarily large n-point metrics whose distortion when embedded in any member of F is at least Ω((log n)^α). The same property is also used to prove strong non-embeddability theorems of Lq into Lp, when q > max{2, p}. Finally we use metric cotype to obtain a new type of isoperimetric inequality on the discrete torus.

REFERENCES

• 1: Noga Alon , Richard M. Karp , David Peleg , Douglas West, A Graph-Theoretic Game and its Application to the $k$-Server Problem, SIAM Journal on Computing, v.24 n.1, p.78-100, Feb. 1995 [doi>10.1137/S0097539792224474]
• 2: Dan Amir, Characterizations of inner product spaces, Birkhauser Verlag, Basel, Switzerland, 1986
• 3: Sanjeev Arora , László Lovász , Ilan Newman , Yuval Rabani , Yuri Rabinovich , Santosh Vempala, Local versus global properties of metric spaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.41-50, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109563]
• 4: K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137--172, 1992.
• 5: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 6: Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. of Math., 2005. To appear.
• 7: 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.
• 8: J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46--52, 1985.
• 9: J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222--230, 1986.
• 10: J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295--317, 1986.
• 11: M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.
• 12: P. Enflo. On the nonexistence of uniform homeomorphisms between Lp-spaces. Ark. Mat., 8:103--105, 1969.
• 13: P. Enflo. Topological groups in which multiplication on one side is differentiable or linear. Math. Scand., 24:195--207 (1970), 1969.
• 14: P. Enflo. Uniform structures and square roots in topological groups. I, II. Israel J. Math. 8 (1970), 230--252; ibid., 8:253--272, 1970.
• 15: P. Enflo. On infinite-dimensional topological groups. In Séminaire sur la Géométrie des Espaces de Banach (1977--1978), pages Exp. No. 10--11, 11. École Polytech., Palaiseau, 1978.
• 16: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 17: T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53--94, 1977.
• 18: M. Gromov. Metric structures for Riemannian and non-Riemannian spaces, volume 152 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, 1999. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates.
• 19: A. Gupta. Embedding tree metrics into low-dimensional Euclidean spaces. Discrete Comput. Geom., 24(1):105--116, 2000.
• 20: Anupam Gupta , Alistair Sinclair , Ilan Newman , Yuri Rabinovich, Cuts, Trees and -Embeddings of Graphs, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.399, October 17-18, 1999
• 21: P. Indyk and J. Matoušek. Low Distortion Embeddings of Finite Metric Spaces, chapter 8. CRC Press, second edition edition, 2004.
• 22: F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187--204. Interscience Publishers, Inc., New York, N. Y., 1948.
• 23: W. B. Johnson and N. L. Randrianarivony. lp (p > 2) does not coarsely embed into a Hilbert space. Manuscript, 2004.
• 24: S. Kwapien. Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients. Studia Math., 44:583--595, 1972.
• 25: James R. Lee , Assaf Naor , Yuval Peres, Trees and Markov convexity, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1028-1037, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109671]
• 26: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 27: N. Linial, A. Magen, and A. Naor. Girth and Euclidean distortion. Geom. Funct. Anal., 12(2):380--394, 2002.
• 28: N. Linial, A. Magen, and M. E. Saks. Low distortion Euclidean embeddings of trees. Israel J. Math., 106:339--348, 1998.
• 29: J. Matoušek. Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces. Comment. Math. Univ. Carolin., 33(3):451--463, 1992.
• 30: J. Matoušek. On embedding trees into uniformly convex Banach spaces. Israel J. Math., 114:221--237, 1999.
• 31: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 32: 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.
• 33: M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451--494, 2004.
• 34: A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces. Preprint, 2004.
• 35: G. Pisier. Sur les espaces qui ne contiennent pas de l1n uniformement. In Sémin. Maurey-Schwartz 1973--1974, Espaces Lp, Appl. radonif., Géom. Espaces de Banach, Exposé VII. 1974.
• 36: 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.
• 37: 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.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory