AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Structural Ramsey theory of metric spaces and topological dynamics of isometry groups
About this Title
L. Nguyen Van Thé, Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, Canada, T2N1N4
Publication: Memoirs of the American Mathematical Society
Publication Year:
2010; Volume 206, Number 968
ISBNs: 978-0-8218-4711-4 (print); 978-1-4704-0582-3 (online)
DOI: https://doi.org/10.1090/S0065-9266-10-00586-7
Published electronically: February 19, 2010
Keywords: Ramsey theory,
Metric geometry,
Fraïssé theory,
Topological groups actions,
Extreme amenability,
Universal minimal flows,
Oscillation stability,
Urysohn metric space.
MSC: Primary 03E02; Secondary 05C55, 05D10, 22A05, 22F05, 51F99
Table of Contents
Chapters
- Preamble
- Preliminary remarks
- Introduction
- 1. Fraïssé classes of finite metric spaces and Urysohn spaces
- 2. Ramsey calculus, Ramsey degrees and universal minimal flows
- 3. Big Ramsey degrees, indivisibility and oscillation stability
- Appendix A. Amalgamation classes $\mathcal {M}_S$ when $|S| \leqslant 4$
- Appendix B. Indivisibility of $\textbf {U}_S$ when $|S| \leqslant 4$
- Appendix C. On the universal Urysohn space $\textbf {U}$
Abstract
In 2003, Kechris, Pestov and Todorcevic showed that the structure of certain separable metric spaces - called ultrahomogeneous - is closely related to the combinatorial behavior of the class of their finite metric spaces. The purpose of the present paper is to explore different aspects of this connection.- Joseph Auslander, Minimal flows and their extensions, North-Holland Mathematics Studies, vol. 153, North-Holland Publishing Co., Amsterdam, 1988. Notas de Matemática [Mathematical Notes], 122. MR 956049
- E. Ben Ami, Private communication, 2005.
- S. A. Bogatyĭ, A universal uniform rational ultrametric on the space irrational numbers, Vestnik Moskov. Univ. Ser. I Mat. Mekh. 6 (2000), 20–24, 86 (Russian, with Russian summary); English transl., Moscow Univ. Math. Bull. 55 (2000), no. 6, 20–24 (2001). MR 1843595
- S. A. Bogatyĭ, Metrically homogeneous spaces, Uspekhi Mat. Nauk 57 (2002), no. 2(344), 3–22 (Russian, with Russian summary); English transl., Russian Math. Surveys 57 (2002), no. 2, 221–240. MR 1918193, DOI 10.1070/RM2002v057n02ABEH000495
- Félix Cabello Sánchez, Regards sur le problème des rotations de Mazur, Extracta Math. 12 (1997), no. 2, 97–116 (French). II Congress on Examples and Counterexamples in Banach Spaces (Badajoz, 1996). MR 1607201
- Félix Cabello Sánchez, A theorem on isotropic spaces, Studia Math. 133 (1999), no. 3, 257–260. MR 1687219, DOI 10.4064/sm-133-3-257-260
- P. J. Cameron and A. M. Vershik, Some isometry groups of the Urysohn space, Ann. Pure Appl. Logic 143 (2006), no. 1-3, 70–78. MR 2258622, DOI 10.1016/j.apal.2005.08.001
- Françoise Delon, Espaces ultramétriques, J. Symbolic Logic 49 (1984), no. 2, 405–424 (French). MR 745369, DOI 10.2307/2274173
- Christian Delhommé, Claude Laflamme, Maurice Pouzet, and Norbert Sauer, Divisibility of countable metric spaces, European J. Combin. 28 (2007), no. 6, 1746–1769. MR 2339500, DOI 10.1016/j.ejc.2006.06.024
- Jean Dieudonné, Sur la complétion des groupes topologiques, C. R. Acad. Sci. Paris 218 (1944), 774–776 (French). MR 14103
- M. El-Zahar and N. Sauer, The indivisibility of the homogeneous $K_n$-free graphs, J. Combin. Theory Ser. B 47 (1989), no. 2, 162–170. MR 1047784, DOI 10.1016/0095-8956(89)90017-8
- M. El-Zahar and N. Sauer, On the divisibility of homogeneous hypergraphs, Combinatorica 14 (1994), no. 2, 159–165. MR 1289070, DOI 10.1007/BF01215348
- Mohamed El-Zahar and N. W. Sauer, Indivisible homogeneous directed graphs and a game for vertex partitions, Discrete Math. 291 (2005), no. 1-3, 99–113. MR 2124058, DOI 10.1016/j.disc.2004.04.023
- P. Erdős, R. L. Graham, P. Montgomery, B. L. Rothschild, J. Spencer, and E. G. Straus, Euclidean Ramsey theorems. I, J. Combinatorial Theory Ser. A 14 (1973), 341–363. MR 316277, DOI 10.1016/0097-3165(73)90011-3
- P. Erdős and A. Hajnal, Unsolved problems in set theory, Axiomatic Set Theory (Proc. Sympos. Pure Math., Vol. XIII, Part I, Univ. California, Los Angeles, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1971, pp. 17–48. MR 0280381
- P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315. MR 156334, DOI 10.1007/BF01895716
- Hans H. Bock (ed.), Classification and related methods of data analysis, North-Holland Publishing Co., Amsterdam, 1988. MR 999548
- J. Flood, Free Topological Vector Spaces, Ph.D. thesis, Australian National University, Canberra, 1975.
- Joe Flood, Free topological vector spaces, Dissertationes Math. (Rozprawy Mat.) 221 (1984), 95. MR 741750
- W. L. Fouché, Symmetries and Ramsey properties of trees, Discrete Math. 197/198 (1999), 325–330. 16th British Combinatorial Conference (London, 1997). MR 1674871
- Roland Fraïssé, Sur l’extension aux relations de quelques propriétés des ordres, Ann. Sci. École Norm. Sup. (3) 71 (1954), 363–388 (French). MR 0069239
- Roland Fraïssé, Theory of relations, Revised edition, Studies in Logic and the Foundations of Mathematics, vol. 145, North-Holland Publishing Co., Amsterdam, 2000. With an appendix by Norbert Sauer. MR 1808172
- P. Frankl and V. Rödl, A partition property of simplices in Euclidean space, J. Amer. Math. Soc. 3 (1990), no. 1, 1–7. MR 1020148, DOI 10.1090/S0894-0347-1990-1020148-2
- M. Fréchet, Sur quelques points du calcul fonctionnel, Rend. Circ. Mat. Palermo, 22, 1–74, 1906.
- Su Gao and Alexander S. Kechris, On the classification of Polish metric spaces up to isometry, Mem. Amer. Math. Soc. 161 (2003), no. 766, viii+78. MR 1950332, DOI 10.1090/memo/0766
- E. Glasner and B. Weiss, Minimal actions of the group $\Bbb S(\Bbb Z)$ of permutations of the integers, Geom. Funct. Anal. 12 (2002), no. 5, 964–988. MR 1937832, DOI 10.1007/PL00012651
- G. Godefroy and N. J. Kalton, Lipschitz-free Banach spaces, Studia Math. 159 (2003), no. 1, 121–141. Dedicated to Professor Aleksander Pełczyński on the occasion of his 70th birthday. MR 2030906, DOI 10.4064/sm159-1-6
- W. T. Gowers, Lipschitz functions on classical spaces, European J. Combin. 13 (1992), no. 3, 141–151. MR 1164759, DOI 10.1016/0195-6698(92)90020-Z
- R. L. Graham, Recent trends in Euclidean Ramsey theory, Discrete Math. 136 (1994), no. 1-3, 119–127. Trends in discrete mathematics. MR 1313284, DOI 10.1016/0012-365X(94)00110-5
- R. L. Graham, K. Leeb, and B. L. Rothschild, Ramsey’s theorem for a class of categories, Advances in Math. 8 (1972), 417–433. MR 306010, DOI 10.1016/0001-8708(72)90005-9
- R. L. Graham and B. L. Rothschild, Ramsey’s theorem for $n$-parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257–292. MR 284352, DOI 10.1090/S0002-9947-1971-0284352-8
- Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR 1044995
- M. Gromov and V. D. Milman, A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), no. 4, 843–854. MR 708367, DOI 10.2307/2374298
- Labib Haddad and Gabriel Sabbagh, Sur une extension des nombres de Ramsey aux ordinaux, C. R. Acad. Sci. Paris Sér. A-B 268 (1969), A1165–A1167 (French). MR 246778
- Labib Haddad and Gabriel Sabbagh, Calcul de certains nombres de Ramsey généralisés, C. R. Acad. Sci. Paris Sér. A-B 268 (1969), A1233–A1234 (French). MR 248030
- Labib Haddad and Gabriel Sabbagh, Nouveaux résultats sur les nombres de Ramsey généralisés, C. R. Acad. Sci. Paris Sér. A-B 268 (1969), A1516–A1518 (French). MR 248031
- A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229. MR 143712, DOI 10.1090/S0002-9947-1963-0143712-1
- Pierre de la Harpe and Alain Valette, La propriété $(T)$ de Kazhdan pour les groupes localement compacts (avec un appendice de Marc Burger), Astérisque 175 (1989), 158 (French, with English summary). With an appendix by M. Burger. MR 1023471
- Greg Hjorth, An oscillation theorem for groups of isometries, Geom. Funct. Anal. 18 (2008), no. 2, 489–521. MR 2421546, DOI 10.1007/s00039-008-0664-9
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- M. Randall Holmes, The universal separable metric space of Urysohn and isometric embeddings thereof in Banach spaces, Fund. Math. 140 (1992), no. 3, 199–223. MR 1173763, DOI 10.4064/fm-140-3-199-223
- Ehud Hrushovski, Extending partial isomorphisms of graphs, Combinatorica 12 (1992), no. 4, 411–416. MR 1194731, DOI 10.1007/BF01305233
- G. E. Huhunaišvili, On a property of Uryson’s universal metric space, Dokl. Akad. Nauk SSSR (N.S.) 101 (1955), 607–610 (Russian). MR 0072454
- J. R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964), 65–76. MR 182949, DOI 10.1007/BF02566944
- M. Katětov, On universal metric spaces, General topology and its relations to modern analysis and algebra, VI (Prague, 1986) Res. Exp. Math., vol. 16, Heldermann, Berlin, 1988, pp. 323–330. MR 952617
- A. S. Kechris, V. G. Pestov, and S. Todorcevic, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geom. Funct. Anal. 15 (2005), no. 1, 106–189. MR 2140630, DOI 10.1007/s00039-005-0503-1
- W. Kubiś and M. Rubin, Extension theorems and reconstruction theorems for the Urysohn universal space, Czechoslovak Math. J., to appear [preprint arxiv:math.MG/0504357].
- C. Laflamme, N. W. Sauer, and V. Vuksanovic, Canonical partitions of universal structures, Combinatorica 26 (2006), no. 2, 183–205. MR 2223634, DOI 10.1007/s00493-006-0013-2
- J. A. Larson, Counting canonical partitions of the Rado graph, preprint, 2005.
- K. Leeb, Vorlesungen über Pascaltheorie, Universität Erlangen, 1973.
- A. Yu. Lemin, Isometric imbedding of isosceles (non-Archimedean) spaces into Euclidean ones, Dokl. Akad. Nauk SSSR 285 (1985), no. 3, 558–562 (Russian). MR 821340
- J. Lopez-Abad and L. Nguyen Van Thé, The oscillation stability problem for the Urysohn sphere: a combinatorial approach, Topology Appl. 155 (2008), no. 14, 1516–1530. MR 2435147, DOI 10.1016/j.topol.2008.03.011
- Jiří Matoušek and Vojtěch Rödl, On Ramsey sets in spheres, J. Combin. Theory Ser. A 70 (1995), no. 1, 30–44. MR 1323999, DOI 10.1016/0097-3165(95)90078-0
- S. Mazur, Quelques propriétés des espaces euclidiens, C. R. Acad. Sc. Paris, 207, 761–764, 1938.
- Julien Melleray, Stabilizers of closed sets in the Urysohn space, Fund. Math. 189 (2006), no. 1, 53–60. MR 2213162, DOI 10.4064/fm189-1-4
- Julien Melleray, On the geometry of Urysohn’s universal metric space, Topology Appl. 154 (2007), no. 2, 384–403. MR 2278687, DOI 10.1016/j.topol.2006.05.005
- Julien Melleray, Computing the complexity of the relation of isometry between separable Banach spaces, MLQ Math. Log. Q. 53 (2007), no. 2, 128–131. MR 2308492, DOI 10.1002/malq.200610032
- Keith R. Milliken, A Ramsey theorem for trees, J. Combin. Theory Ser. A 26 (1979), no. 3, 215–237. MR 535155, DOI 10.1016/0097-3165(79)90101-8
- V. D. Milman, A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies, Funkcional. Anal. i Priložen. 5 (1971), no. 4, 28–37 (Russian). MR 0293374
- E. C. Milner, A finite algorithm for the partition calculus, Proceedings of the Twenty-Fifth Summer Meeting of the Canadian Mathematical Congress (Lakehead Univ., Thunder Bay, Ont., 1971) Lakehead Univ., Thunder Bay, Ont., 1971, pp. 117–128. MR 0332507
- Jaroslav Ne et il, Ramsey theory, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1331–1403. MR 1373681
- Jaroslav Ne et il, Ramsey classes and homogeneous structures, Combin. Probab. Comput. 14 (2005), no. 1-2, 171–189. MR 2128088, DOI 10.1017/S0963548304006716
- Jaroslav Ne et il, Metric spaces are Ramsey, European J. Combin. 28 (2007), no. 1, 457–468. MR 2261831, DOI 10.1016/j.ejc.2004.11.003
- Jaroslav Ne et il and Vojtěch Rödl, Type theory of partition properties of graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 405–412. MR 0409259
- Jaroslav Ne et il and Vojtěch Rödl, Partitions of finite relational and set systems, J. Combinatorial Theory Ser. A 22 (1977), no. 3, 289–312. MR 437351, DOI 10.1016/0097-3165(77)90004-8
- J. Nešetřil and V. Rödl, Ramsey topological spaces, General topology and its relations to modern analysis and algebra, IV (Proc. Fourth Prague Topological Sympos., Prague, 1976) Soc. Czechoslovak Mathematicians and Physicists, Prague, 1977, pp. 333–337. MR 0458361
- Jaroslav Ne et il and Vojtěch Rödl, Ramsey classes of set systems, J. Combin. Theory Ser. A 34 (1983), no. 2, 183–201. MR 692827, DOI 10.1016/0097-3165(83)90055-9
- Lionel Nguyen Van The, Ramsey degrees of finite ultrametric spaces, ultrametric Urysohn spaces and dynamics of their isometry groups, European J. Combin. 30 (2009), no. 4, 934–945. MR 2504653, DOI 10.1016/j.ejc.2008.07.007
- L. Nguyen Van Thé, Big Ramsey degrees and divisibility in classes of ultrametric spaces, Canad. Math. Bull. 51 (2008), no. 3, 413–423. MR 2436932, DOI 10.4153/CMB-2008-042-7
- L. Nguyen Van Thé and N. W. Sauer, The Urysohn sphere is oscillation stable, GAFA, to appear [preprint arXiv:math.MG/0710.2884].
- Edward Odell and Thomas Schlumprecht, The distortion problem, Acta Math. 173 (1994), no. 2, 259–281. MR 1301394, DOI 10.1007/BF02398436
- Vladimir G. Pestov, On free actions, minimal flows, and a problem by Ellis, Trans. Amer. Math. Soc. 350 (1998), no. 10, 4149–4165. MR 1608494, DOI 10.1090/S0002-9947-98-02329-0
- Vladimir Pestov, Ramsey-Milman phenomenon, Urysohn metric spaces, and extremely amenable groups, Israel J. Math. 127 (2002), 317–357. MR 1900705, DOI 10.1007/BF02784537
- Vladimir Pestov, Dynamics of infinite-dimensional groups and Ramsey-type phenomena, Publicações Matemáticas do IMPA. [IMPA Mathematical Publications], Instituto Nacional de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 2005. 25$^\textrm {o}$ Colóquio Brasileiro de Matemática. [25th Brazilian Mathematics Colloquium]. MR 2164572
- Vladimir Pestov, Dynamics of infinite-dimensional groups, University Lecture Series, vol. 40, American Mathematical Society, Providence, RI, 2006. The Ramsey-Dvoretzky-Milman phenomenon; Revised edition of Dynamics of infinite-dimensional groups and Ramsey-type phenomena [Inst. Mat. Pura. Apl. (IMPA), Rio de Janeiro, 2005; MR2164572]. MR 2277969, DOI 10.1090/ulect/040
- Vladimir Pestov, The isometry group of the Urysohn space as a Lev́y group, Topology Appl. 154 (2007), no. 10, 2173–2184. MR 2324929, DOI 10.1016/j.topol.2006.02.010
- A. Pełczinski and S. Rolewicz, Best norms with respect to isometry groups in normed linear spaces, Short Communications on International Math. Congress in Stockholm, 104, 1962.
- Bruno Poizat, A course in model theory, Universitext, Springer-Verlag, New York, 2000. An introduction to contemporary mathematical logic; Translated from the French by Moses Klein and revised by the author. MR 1757487, DOI 10.1007/978-1-4419-8622-1
- Maurice Pouzet and Bernard Roux, Ubiquity in category for metric spaces and transition systems, European J. Combin. 17 (1996), no. 2-3, 291–307. Discrete metric spaces (Bielefeld, 1994). MR 1379379, DOI 10.1006/eujc.1996.0025
- Arkady Leiderman, Vladimir Pestov, Matatyahu Rubin, Slawomir Solecki, and Vladimir Uspenskij, Preface [Special issue: Workshop on the Urysohn space], Topology Appl. 155 (2008), no. 14, 1451–1452. Held at Ben-Gurion University of the Negev, Beer Sheva, May 21–24, 2006. MR 2435140, DOI 10.1016/j.topol.2008.03.003
- F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc., 30, 264–286, 1930.
- Beata Randrianantoanina, A note on the Banach-Mazur problem, Glasg. Math. J. 44 (2002), no. 1, 159–165. MR 1892292, DOI 10.1017/S001708950201011X
- W. Roelke and S. Dierolf, Uniform structures on topological groups and their quotients, McGraw-Hill, 1973.
- N. W. Sauer, A Ramsey theorem for countable homogeneous directed graphs, Discrete Math. 253 (2002), no. 1-3, 45–61. Combinatorics and algorithms (Hsin Chu/Kaohsiung, 2000). MR 1905956, DOI 10.1016/S0012-365X(01)00448-4
- N. W. Sauer, Canonical vertex partitions, Combin. Probab. Comput. 12 (2003), no. 5-6, 671–704. Special issue on Ramsey theory. MR 2037079, DOI 10.1017/S0963548303005765
- S. A. Shkarin, Isometric embedding of finite ultrametric spaces in Banach spaces, Topology Appl. 142 (2004), no. 1-3, 13–17. MR 2071289, DOI 10.1016/j.topol.2003.12.002
- Waclaw Sierpiński, Sur un espace métrique séparable universel, Fund. Math. 33 (1945), 115–122 (French). MR 15451, DOI 10.4064/fm-33-1-115-122
- Sławomir Solecki, Extending partial isometries, Israel J. Math. 150 (2005), 315–331. MR 2255813, DOI 10.1007/BF02762385
- Stevo Todorcevic, Topics in topology, Lecture Notes in Mathematics, vol. 1652, Springer-Verlag, Berlin, 1997. MR 1442262, DOI 10.1007/BFb0096295
- S. Todorcevic, Introduction to Ramsey spaces, to appear.
- P. Urysohn, Sur un espace métrique universel, Bull. Sci. Math., 51, 43–64, 74–90, 1927.
- V. V. Uspenskij, On the group of isometries of the Urysohn universal metric space, Comment. Math. Univ. Carolin. 31 (1990), no. 1, 181–182. MR 1056185
- Vladimir Uspenskij, The Urysohn universal metric space is homeomorphic to a Hilbert space, Topology Appl. 139 (2004), no. 1-3, 145–149. MR 2051102, DOI 10.1016/j.topol.2003.09.008
- A. M. Vershik, Random metric spaces and universality, Uspekhi Mat. Nauk 59 (2004), no. 2(356), 65–104 (Russian, with Russian summary); English transl., Russian Math. Surveys 59 (2004), no. 2, 259–295. MR 2086637, DOI 10.1070/RM2004v059n02ABEH000718
- A. M. Vershik, Globalization of the partial isometries of metric spaces and local approximation of the group of isometries of Urysohn space, Topology Appl. 155 (2008), no. 14, 1618–1626. MR 2435153, DOI 10.1016/j.topol.2008.03.007
- I. A. Vestfrid, On a universal ultrametric space, Ukraïn. Mat. Zh. 46 (1994), no. 12, 1700–1706 (Russian, with English and Ukrainian summaries); English transl., Ukrainian Math. J. 46 (1994), no. 12, 1890–1898 (1996). MR 1354831, DOI 10.1007/BF01063173
- I. A. Vestfrid and A. F. Timan, A universality property of Hilbert spaces, Dokl. Akad. Nauk SSSR 246 (1979), no. 3, 528–530 (Russian). MR 534045
- A. F. Timan and I. A. Vestfrid, Any separable ultrametric space is isometrically embeddable in $l_{2}$, Funktsional. Anal. i Prilozhen. 17 (1983), no. 1, 85–86 (Russian). MR 695109
- Stephen Watson, The classification of metrics and multivariate statistical analysis, Topology Appl. 99 (1999), no. 2-3, 237–261. 8th Prague Topological Symposium on General Topology and its Relations to Modern Analysis and Algebra, Part II (1996). MR 1728852, DOI 10.1016/S0166-8641(99)00157-1