Colourful categories

M. L. Gromov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 70 (2015) no. 4, pp. 591-655

Résumé

This paper presents Ramsey theory in category-theoretic terms as a message from a non-expert author to a non-expert reader. Everything is explained starting from the level zero, and an attempt is made to be as self-explanatory in the terminology and notation as possible. For the sake of references, the paper also reproduces traditional terminology, with concepts and theorems often named after (presumed) discoverers who are largely unknown to outsiders to the field. The sources are referred to in a manner so as to make them easy to find on the web; only exceptionally are non-freely accessible items referred to. Certain questions are formulated as ‘conjectures’, not out of a deep belief in their validity but because they sound better stated explicitly. There are no new results in this article, no deepening of particular aspects of Ramsey theory, no attempts to be comprehensive. But, in the spirit of the ideas of Anatoly Vershik, an attempt is made to move transversally across common directions of research, to see interrelations between them and to formulate questions. In fact, the article reproduces a chapter from the author's as yet unfinished manuscript “A number of questions”.\footnote{http://www.ihes.fr/~gromov/PDF/Problems-marc6-11-2014.pdf.} Bibliography: 65 titles.

Détail

Keywords: Ramsey's theorem, Dvoretzky's theorem.

Bibliographie

[1] A. Akopyan, R. Karasev, A. Volovikov, Borsuk–Ulam type theorems for metric spaces, 2012, 11 pp., arXiv: 1209.1249

[2] A. Bak, M. Morimoto, F. Ushitaki (eds.), Current trends in transformation groups, $K$-Monogr. Math., 7, Kluwer Acad. Publ., Dordrecht, 2002, xii+249 pp. | DOI | MR | Zbl

[3] A. Barvinok, Measure concentration lecture notes, 2005, 119 pp. http://www.math.lsa.umich.edu/<nobr>$\sim$</nobr>barvinok/total710.pdf

[4] V. Bergelson, “Ultrafilters, IP sets, dynamics, and combinatorial number theory”, Ultrafilters across mathematics, Contemp. Math., 530, Amer. Math. Soc., Providence, RI, 2010, 23–47 | DOI | MR | Zbl

[5] P. V. M. Blagojević, R. Karasev, “Extensions of theorems of Rattray and Makeev”, Topol. Methods Nonlinear Anal., 40:1 (2012), 189–213 ; (2010 (v2 – 2012)), 15 pp., arXiv: 1011.0869 | MR | Zbl

[6] J. Bourgain, “On finite dimensional homogeneous Banach spaces”, Geometric aspects of functional analysis (1986/87), Lecture Notes in Math., 1317, Springer, Berlin, 1988, 232–238 | DOI | MR | Zbl

[7] J. Bourgain, J. Lindenstrauss, V. D. Milman, “Minkowski sums and symmetrizations”, Geometric aspects of functional analysis (1986/87), Lecture Notes in Math., 1317, Springer, Berlin, 1988, 44–66 | DOI | MR | Zbl

[8] T. C. Brown, P. J.-S. Shiue, “On the history of van der Waerden's theorem on arithmetic progressions”, Tamkang J. Math., 32:4 (2001), 335–341 | MR | Zbl

[9] B. Bukh, R. Karasev, “Suborbits in Knaster's problem”, Bull. London Math. Soc., 46:2 (2014), 269–278 ; (2012 (v3 – 2013)), 10 pp., arXiv: 1212.5351 | DOI | MR | Zbl

[10] D. Burago, S. Ivanov, S. Tabachnikov, “Topological aspects of the Dvoretzky theorem”, J. Topol. Anal., 2:4 (2010), 453–467 ; (2009), 17 pp., arXiv: 0907.5041 | DOI | MR | Zbl

[11] T. J. Carlson, “Some unifying principles in Ramsey theory”, Discrete Math., 68:2-3 (1988), 117–169 | DOI | MR | Zbl

[12] H. Cartan, “Filtres et ultrafiltres”, C. R. Acad. Sci. Paris, CCV (1937), 777–779

[13] D. Conlon, J. Fox, B. Sudakov, “Hypergraph Ramsey numbers”, J. Amer. Math. Soc., 23:1 (2010), 247–266 ; 20 pp. http://people.maths.ox.ac.uk/<nobr>$\sim$</nobr>conlond/offdiagonal-hypergraph.pdf | DOI | MR | Zbl

[14] J. Davidoff, P. Sarnak, A. Valette, Elementary number theory, group theory and Ramanujan graphs, London Math. Soc. Stud. Texts, 55, Cambridge Univ. Press, Cambridge, 2003, 156 pp. | DOI | MR | Zbl

[15] P. Dodos, Some recent results in Ramsey Theory, 2015, 11 pp. http://users.uoa.gr/<nobr>$\sim$</nobr>pdodos/Publications/35-DK

[16] V. L. Dol'nikov, R. N. Karasev, “Dvoretzky type theorems for multivariate polynomials and sections of convex bodies”, Geom. Funct. Anal., 21:2 (2011), 301–318 ; (2010 (v3 – 2011)), 17 pp., arXiv: 1009.0392 | DOI | MR | Zbl

[17] A. Dvoretzky, “Some results on convex bodies and Banach spaces”, Proceedings of the International Symposium on Linear Spaces (Jerusalem, 1960), Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961, 123–160 | MR | Zbl

[18] H. Furstenberg, Y. Katznelson, “Idempotents in compact semigroups and Ramsey theory”, Israel J. Math., 68:3 (1989), 257–270 | DOI | MR | Zbl

[19] H. Furstenberg, B. Weiss, “Topological dynamics and combinatorial number theory”, J. Analyse Math., 34 (1978), 61–85 | DOI | MR | Zbl

[20] J. Geelen, P. Nelson, “A density Hales–Jewett theorem for matroids”, J. Combin. Theory Ser. B, 112 (2015), 70–77 ; (2012), 9 pp., arXiv: 1210.4522 | DOI | MR | Zbl

[21] J.-Y. Girard, Proof theory and logical complexity, Stud. Proof Theory Monogr., 1, Bibliopolis, Naples, 1987, 505 pp. | MR | Zbl

[22] R. L. Graham, K. Leeb, B. L. Rothschild, “Ramsey's theorem for a class of categories”, Adv. Math., 8 (1972), 417–433 | DOI | MR | Zbl

[23] R. L. Graham, B. L. Rothschild, “Ramsey's theorem for $n$-parameter sets”, Trans. Amer. Math. Soc., 159 (1971), 257–292 | DOI | MR | Zbl

[24] R. L. Graham, B. L. Rothschild, “A short proof of van der Waerden's theorem on arithmetic progressions”, Proc. Amer. Math. Soc., 42:2 (1974), 385–386 | DOI | MR | Zbl

[25] R. L. Graham, J. H. Spencer, “A general Ramsey product theorem”, Proc. Amer. Math. Soc., 73:1 (1979), 137–139 | DOI | MR | Zbl

[26] M. Gromov, “Filling Riemannian manifolds”, J. Differential Geom., 18:1 (1983), 1–147 | MR | Zbl

[27] M. Gromov, “Dimension, non-linear spectra and width”, Geometric aspects of functional analysis (1986/87), Lecture Notes in Math., 1317, Springer, Berlin, 1988, 132–184 | DOI | MR | Zbl

[28] M. Gromov, Metric structures for Riemannian and non-Riemannian spaces, Progr. Math., 152, Birkhäuser Boston, Inc., Boston, MA, 1999, xx+585 pp. | MR | Zbl

[29] M. Gromov, “Endomorphisms of symbolic algebraic varieties”, J. Eur. Math. Soc. (JEMS), 1:2 (1999), 109–197 | DOI | MR | Zbl

[30] M. Gromov, “Spaces and questions”, GAFA 2000 (Tel Aviv, 1999), Geom. Funct. Anal., Special volume, Part I, 2000, 118–161 | DOI | MR | Zbl

[31] M. Gromov, “Isoperimetry of waists and concentration of maps”, Geom. Funct. Anal., 13:1 (2003), 178–215 | DOI | MR | Zbl

[32] M. Gromov, “Entropy and isoperimetry for linear and non-linear group actions”, Groups Geom. Dyn., 2:4 (2008), 499–593 | DOI | MR | Zbl

[33] M. Gromov, “Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry”, Geom. Funct. Anal., 20:2 (2010), 416–526 | DOI | MR | Zbl

[34] M. Gromov, “Manifolds: Where do we come from? What are we? Where are we going”, The Poincaré conjecture, Clay Math. Proc., 19, Amer. Math. Soc., Providence, RI, 2014, 81–144 ; 2010, 68 pp. http://www.ihes.fr/<nobr>$\sim$</nobr>gromov/PDF/manifolds-Poincare.pdf | MR | Zbl

[35] M. Gromov, V. D. Milman, “A topological application of the isoperimetric inequality”, Amer. J. Math., 105:4 (1983), 843–854 | DOI | MR | Zbl

[36] L. J. Halbeisen, Combinatorial set theory. With a gentle introduction to forcing, Springer Monogr. Math., Springer, London, 2012, xvi+453 pp. | DOI | MR | Zbl

[37] N. Hindman, “Ultrafilters and combinatorial number theory”, Number theory (Southern Illinois Univ., Carbondale, IL, 1979), Lecture Notes in Math., 751, Springer, Berlin, 1979, 119–184 | DOI | MR | Zbl

[38] A. S. Kechris, V. G. Pestov, S. Todorcevic, “Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups”, Geom. Funct. Anal., 15:1 (2005), 106–189 | DOI | MR | Zbl

[39] A. Ya. Khinchin, Three pearls of number theory, Graylock Press, Rochester, N. Y., 1952, 64 pp. | MR | MR | Zbl | Zbl

[40] B. Klartag, “On nearly radial marginals of high-dimensional probability measures”, J. Eur. Math. Soc. (JEMS), 12:3 (2010), 723–754 ; (2008 (v2 – 2009)), 32 pp., arXiv: 0810.4700 | DOI | MR | Zbl

[41] M. Ledoux, The concentration of measure phenomenon, Math. Surveys Monogr., 89, Amer. Math. Soc., Providence, RI, 2001, x+181 pp. | MR | Zbl

[42] P. Lévy, Problèmes concrets d'analyse fonctionnelle, 2nd ed., Gauthier-Villars, Paris, 1951, xiv+484 pp. | MR | MR | Zbl

[43] G. L. Litvinov, “Tropical mathematics, idempotent analysis, classical mechanics and geometry”, Spectral theory and geometric analysis, Contemp. Math., 535, Amer. Math. Soc., Providence, RI, 2011, 159–186 | DOI | MR | Zbl

[44] J. Matoušek, Lectures on topological methods in combinatorics and geometry, Universitext, 2nd corr. print., Springer-Verlag, Berlin, 2008, xii+214 pp. | MR | Zbl

[45] V. D. Milman, “New proof of the theorem of A. Dvoretzky on intersections of convex bodies”, Funct. Anal. Appl., 5:4 (1971), 288–295 | DOI | MR | Zbl

[46] V. D. Milman, “Almost Euclidean quotient spaces of subspaces of a finite-dimensional normed space”, Proc. Amer. Math. Soc., 94:3 (1985), 445–449 | DOI | MR | Zbl

[47] V. D. Milman, “A few observations on the connections between local theory and some other fields”, Geometric aspects of functional analysis (1986/87), Lecture Notes in Math., 1317, Springer, Berlin, 1988, 283–289 | DOI | MR | Zbl

[48] D. Mubayi, V. Rödl, “On the chromatic number and independence number of hypergraph products”, J. Combin. Theory Ser. B, 97:1 (2007), 151–155 ; 2004, 6 pp. http://www.math.cmu.edu/<nobr>$\sim$</nobr>mubayi/papers/bergesimon.pdf | DOI | MR | Zbl

[49] M. B. Nathanson, Additive number theory. The classical bases, Grad. Texts in Math., 164, Springer-Verlag, New York, 1996, xiv+342 pp. | DOI | MR | Zbl

[50] A. Papadopoulos, “Hilbert's fourth problem”, Handbook of Hilbert geometry, IRMA Lect. Math. Theor. Phys., 22, Eur. Math. Soc., Zürich, 2014, 391–431 ; 2013, 43 pp., arXiv: 1312.3172 | DOI | MR | Zbl

[51] J. Paris, L. Harrington, “A mathematical incompleteness in Peano arithmetic”, Handbook of mathematical logic, Stud. Logic Found. Math., 90, ed. J. Barwise, North-Holland Publ. Co., Amsterdam–New York–Oxford, 1977, 1133–1142 | DOI | MR | Zbl | Zbl

[52] V. Pestov, Dynamics of infinite-dimensional groups. The Ramsey–Dvoretzky–Milman phenomenon, Univ. Lecture Ser., 40, Amer. Math. Soc., Providence, RI, 2006, viii+192 pp. | DOI | MR | Zbl

[53] G. Pisier, “Probabilistic methods in the geometry of Banach spaces”, Probability and analysis (Varenna, 1985), Lecture Notes in Math., 1206, Springer, Berlin, 1986, 167–241 | DOI | MR | Zbl

[54] D. H. J. Polymath, “A new proof of the density Hales–Jewett theorem”, Ann. of Math. (2), 175:3 (2012), 1283–1327 ; (2009 (v2 – 2010)), 34 pp., arXiv: 0910.3926 | DOI | MR | Zbl

[55] E. Schmidt, “Beweis der isoperimetrischen Eigenschaft der Kugel im hyperbolischen und sphärischen Raum jeder Dimensionszahl”, Math. Z., 49 (1943/44), 1–109 | DOI | MR | Zbl

[56] I. Schur, “Über die Kongruenz $x^m+y^m\equiv z^m \pmod p$”, Jahresber. Deutsch. Math.-Verein., 25 (1916), 114–117 | Zbl

[57] S. Shelah, “Primitive recursive bounds for van der Waerden numbers”, J. Amer. Math. Soc., 1:3 (1988), 683–697 | DOI | MR | Zbl

[58] A. Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators, Springer, New York, 2009, xxx+607 pp. | DOI | MR | Zbl

[59] A. Soifer (ed.), Ramsey theory. Yesterday, today, and tomorrow (Rutgers Univ., Piscataway, NJ, May 27–29, 2009), Progr. Math., 285, Birkhäuser/Springer, New York, 2011, xiv+189 pp. | DOI | MR | Zbl

[60] S. Solecki, “Abstract approach to finite Ramsey theory and a self-dual Ramsey theorem”, Adv. Math., 248 (2013), 1156–1198 ; (2011 (v3 – 2013)), 50 pp., arXiv: 1104.3950 | DOI | MR | Zbl

[61] J. H. Spencer, “Ramsey's theorem for spaces”, Trans. Amer. Math. Soc., 249:2 (1979), 363–371 | DOI | MR | Zbl

[62] M. Talagrand, “Concentration of measure and isoperimetric inequalities in product spaces”, Inst. Hautes Études Sci. Publ. Math., 81:1 (1995), 73–205 | DOI | MR | Zbl

[63] S. B. Todorcevic, Introduction to Ramsey spaces, Ann. of Math. Stud., 174, Princeton Univ. Press, Princeton, NJ, 2010, viii+287 pp. | DOI | MR | Zbl

[64] R. Vershynin, Lectures in geometric functional analysis, 2009, 76 pp. http://www-personal.umich.edu/<nobr>$\sim$</nobr>romanv/papers/GFA-book/GFA-book.pdf