Previous |  Up |  Next


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:
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 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 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


Files Size Format View
CommentatMathUnivCarolRetro_33-1992-3_8.pdf 260.4Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo