| Title:
|
Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces (English) |
| Author:
|
Matoušek, Jiří |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
33 |
| Issue:
|
3 |
| Year:
|
1992 |
| Pages:
|
451-463 |
| . |
| Category:
|
math |
| . |
| Summary:
|
Let $(X,\rho)$, $(Y,\sigma)$ be metric spaces and $f:X\to Y$ an injective mapping. We put $\|f\|_{Lip} = \sup \{\sigma (f(x),f(y))/\rho(x,y)$; $x,y\in X$, $x\neq y\}$, and $\operatorname{dist}(f)= \|f\|_{Lip}.\|f^{-1}\|_{Lip}$ (the {\sl distortion\/} of the mapping $f$). Some Ramsey-type questions for mappings of finite metric spaces with bounded distortion are studied; e.g., the following theorem is proved: Let $X$ be a finite metric space, and let $\varepsilon>0$, $K$ be given numbers. Then there exists a finite metric space $Y$, such that for every mapping $f:Y\to Z$ ($Z$ arbitrary metric space) with $\operatorname{dist}(f)<K$ one can find a mapping $g:X\to Y$, such that both the mappings $g$ and $f|_{g(X)}$ have distortion at most $(1+\varepsilon)$. If $X$ is isometrically embeddable into a $\ell_p$ space (for some $p\in [1,\infty]$), then also $Y$ can be chosen with this property. (English) |
| Keyword:
|
Ramsey theory |
| Keyword:
|
embedding of metric spaces |
| Keyword:
|
distortion |
| Keyword:
|
Lipschitz mapping |
| Keyword:
|
differentiability of Lipschitz mappings |
| MSC:
|
05C55 |
| MSC:
|
05D10 |
| MSC:
|
54C25 |
| MSC:
|
54E35 |
| idZBL:
|
Zbl 0769.05093 |
| idMR:
|
MR1209287 |
| . |
| Date available:
|
2009-01-08T17:57:10Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118513 |
| . |
| Reference:
|
[AM83] Alon N., Milman J.: Embeddings of $l^k_{\infty}$ in finite dimensional Banach spaces.Israel J. Math. 45 (1983), 265-280. MR 0720303 |
| Reference:
|
[Ar76] Aronszajn N.: Differentiability of Lipschitz mappings between Fréchet spaces.Studia Math. 57 (1976), 147-190. MR 0425608 |
| Reference:
|
[BDK66] Bretagnolle J., Dacunha-Castelle D., Krivine J.L.: Lois stables et espaces $L^p$.Ann. Inst. H. Poincaré, Sect. B 2(1966) pp. 231-259. MR 0203757 |
| Reference:
|
[Ben85] Benyamini Y.: The uniform classification of Banach spaces.Longhorn Notes, The Univ. of Texas at Austin, Functional analysis seminar 1984-85, pp. 15-38. Zbl 1095.46005, MR 0832247 |
| Reference:
|
[BFM86] Bourgain J., Figiel T., Milman V.: On Hilbertian subspaces of finite metric spaces.Israel J. Math. 55 (1986), 147-152. MR 0868175 |
| Reference:
|
[BMW86] Bourgain J., Milman V., Wolfson H.: On type of metric spaces.Trans. Am. Math. Soc. 294 (1986), 295-317. Zbl 0617.46024, MR 0819949 |
| Reference:
|
[DU77] Diestel J., Uhl J.J., Jr.: Vector measures.Math. Surveys 15, AMS, Providence, 1977. Zbl 0521.46035, MR 0453964 |
| Reference:
|
[Enf69a] Enflo P.: On a problem of Smirnov.Ark. Mat. 8 (1969), 107-109. MR 0415576 |
| Reference:
|
[Enf69b] Enflo P.: On the nonexistence of uniform homeomorphisms between $L_p$-spaces.Ark. Mat. 8 (1969), 103-105. MR 0271719 |
| Reference:
|
[Enf70] Enflo P.: Uniform structures and square roots in topological groups II.Israel J. Math. 8 (1970), 253-272. Zbl 0214.28501, MR 0263969 |
| Reference:
|
[Fi88] Fichet B.: $L_p$ spaces in data analysis.in: Classification and related methods of data analysis, H.H. Bock ed., North Holland, 1988, pp. 439-444. |
| Reference:
|
[GRS80] Graham R.L., Rothschild B.L., Spencer J.H.: Ramsey theory.J.Wiley & sons, 1980. Zbl 0705.05061, MR 0591457 |
| Reference:
|
[JS82] Johnson W., Schechtman G.: Embedding $l_p^m$ into $l_1^n$.Acta Math. 149 (1982), 71-85. MR 0674167 |
| Reference:
|
[Kir88] Kirchheim B.: Geometry of measures (in Czech).thesis, Charles University, Prague, 1988. MR 1029559 |
| Reference:
|
[Lin66] Lindenstrauss J.: On nonlinear projections in Banach spaces.Michigan Math. J. 11 (1966), 268-287. MR 0167821 |
| Reference:
|
[LT73] Lindenstrauss J., Tzafriri L.: Classical Banach spaces.Lecture Notes in Mathematics 338, Springer-Verlag, 1973. Zbl 0852.46015, MR 0415253 |
| Reference:
|
[Ma89] Matoušek J.: Lipschitz distance of metric spaces (in Czech).CSc. degree thesis, Charles University, 1989. |
| Reference:
|
[MiS86] Milman V.D., Schechtman G.: Asymptotic theory of finite dimensional normed spaces.Lecture Notes in Mathematics 1200, Springer-Verlag, 1986. Zbl 0606.46013, MR 0856576 |
| Reference:
|
[Neš91] Nešetřil J.: Ramsey Theory.Chapter for Handbook of Combinatorics, North-Holland, to appear. MR 1373681 |
| Reference:
|
[NR79] Nešetřil J., Rödl V.: Partition theory and its applications.in: Surveys in Combinatorics, (B. Bollobás ed.), Cambridge Univ. Press, Cambridge-London, 1979 pages 96-156. MR 0561308 |
| Reference:
|
[Pre88] Preiss D.: Differentiability of Lipschitz functions on Banach spaces.Journal of Functional Analysis 91 (1990), 312-345. Zbl 0711.46036, MR 1058975 |
| Reference:
|
[Sche81] Schechtman G.: Random embeddings of Euclidean spaces in sequence spaces.Israel J. Math. 40 (1981), 187-192. Zbl 0474.46004, MR 0634905 |
| . |
