Metric Cotype
- Creators
- Mendel, Manor
- Naor, Assaf
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 L_q into L_p, when q > max{2,p}. Finally we use metric cotype to obtain a new type of isoperimetric inequality on the discrete torus.
Additional Information
© 2006 Association for Computing Machinery. Extended abstract. A full version of this paper with all the details is available at http://arxiv.org/math.FA/0506201. We are grateful to Keith Ball for several valuable discussions. We thank Yuri Rabinovich for pointing out the connection to Matousek's BD Ramsey theorem. Comments from the SODA's referees helped in improving the presentation.Attached Files
Published - 0506201v4.pdf
Published - Mendel2006p11463Proceedings_Of_The_Seventheenth_Annual_Acm-Siam_Symposium_On_Discrete_Algorithms.pdf
Files
Name | Size | Download all |
---|---|---|
md5:f968f8a138a34b1ae0e2db14c55b5b9c
|
515.9 kB | Preview Download |
Mendel2006p11463Proceedings_Of_The_Seventheenth_Annual_Acm-Siam_Symposium_On_Discrete_Algorithms.pdf
md5:09c213ae40818bea1a07edbf5f3448fd
|
621.3 kB | Preview Download |
Additional details
- Eprint ID
- 20317
- Resolver ID
- CaltechAUTHORS:20101006-090230854
- Created
-
2010-11-17Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field