×

Colourful categories. (English. Russian original) Zbl 1329.05206

Russ. Math. Surv. 70, No. 4, 591-655 (2015); translation from Usp. Mat. Nauk 70, No. 4, 3-76 (2015).
Summary: 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”.

MSC:

05C55 Generalized Ramsey theory
05C15 Coloring of graphs and hypergraphs
05D10 Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Akopyan, R. Karasev, and A. Volovikov 2012 Borsuk–Ulam type theorems for metric spaces 1209.1249 11 pp.
[2] A. Bak, M. Morimoto, and F. Ushitaki (eds.) 2002 Current trends in transformation groupsK-Monogr. Math. 7 Kluwer Acad. Publ., Dordrecht xii+249 pp. · doi:10.1007/978-94-009-0003-5
[3] A. Barvinok 2005 Measure concentration lecture notes 119 pp. http://www.math.lsa.umich.edu/ barvinok/total710.pdf
[4] V. Bergelson 2010 Ultrafilters, IP sets, dynamics, and combinatorial number theory Ultrafilters across mathematics Contemp. Math. 530 Amer. Math. Soc., Providence, RI 23–47 · Zbl 1237.05205 · doi:10.1090/conm/530
[5] P. V. M. Blagojevic\acute{} and R. Karasev 2012 Extensions of theorems of Rattray and Makeev Topol. Methods Nonlinear Anal.40 1 189–213 · Zbl 1282.55008
[6] P. V. M. Blagojevic\acute{} and R. Karasev 2010 (v2 – 2012) 1011.0869 15 pp.
[7] J. Bourgain 1988 On finite dimensional homogeneous Banach spaces Geometric aspects of functional analysis1986/87 Lecture Notes in Math. 1317 Springer, Berlin 232–238 · doi:10.1007/BFb0081744
[8] J. Bourgain, J. Lindenstrauss, and V. D. Milman 1988 Minkowski sums and symmetrizations Geometric aspects of functional analysis1986/87 Lecture Notes in Math. 1317 Springer, Berlin 44–66 · doi:10.1007/BFb0081735
[9] T. C. Brown and P. J.-S. Shiue 2001 On the history of van der Waerden’s theorem on arithmetic progressions Tamkang J. Math.32 4 335–341 · Zbl 0996.05115
[10] B. Bukh and R. Karasev 2014 Suborbits in Knaster’s problem Bull. London Math. Soc.46 2 269–278 · Zbl 1300.55003 · doi:10.1112/blms/bdt088
[11] B. Bukh and R. Karasev 2012 (v3 – 2013) 1212.5351 10 pp.
[12] D. Burago, S. Ivanov, and S. Tabachnikov 2010 Topological aspects of the Dvoretzky theorem J. Topol. Anal.2 4 453–467 · Zbl 1222.52004 · doi:10.1142/S1793525310000410
[13] D. Burago, S. Ivanov, and S. Tabachnikov 2009 0907.5041 17 pp.
[14] T. J. Carlson 1988 Some unifying principles in Ramsey theory Discrete Math.68 2-3 117–169 · Zbl 0817.04002 · doi:10.1016/0012-365X(88)90109-4
[15] H. Cartan 1937 Filtres et ultrafiltres C. R. Acad. Sci. ParisCCV 777–779 · Zbl 0018.00302
[16] D. Conlon, J. Fox, and B. Sudakov 2010 Hypergraph Ramsey numbers J. Amer. Math. Soc.23 1 247–266 · Zbl 1287.05087 · doi:10.1090/S0894-0347-09-00645-6
[17] D. Conlon, J. Fox, and B. Sudakov 2010 J. Amer. Math. Soc. 20 pp. http://people.maths.ox.ac.uk/ conlond/offdiagonal-hypergraph.pdf
[18] J. Davidoff, P. Sarnak, and A. Valette 2003 Elementary number theory, group theory and Ramanujan graphs London Math. Soc. Stud. Texts 55 Cambridge Univ. Press, Cambridge 156 pp. · Zbl 1032.11001 · doi:10.1017/CBO9780511615825
[19] P. Dodos 2015 Some recent results in Ramsey Theoryhttp://users.uoa.gr/ pdodos/Publications/35-DK (Survey).pdf 11 pp.
[20] V. L. Dol’nikov and R. N. Karasev 2011 Dvoretzky type theorems for multivariate polynomials and sections of convex bodies Geom. Funct. Anal.21 2 301–318 · Zbl 1232.46043 · doi:10.1007/s00039-011-0109-8
[21] V. L. Dol’nikov and R. N. Karasev 2010 (v3 – 2011) 1009.0392 17 pp.
[22] A. Dvoretzky 1961 Some results on convex bodies and Banach spaces Proceedings of the International Symposium on Linear SpacesJerusalem 1960 Jerusalem Academic Press, Jerusalem, Pergamon, Oxford 123–160
[23] H. Furstenberg and Y. Katznelson 1989 Idempotents in compact semigroups and Ramsey theory Israel J. Math.68 3 257–270 · Zbl 0714.05059 · doi:10.1007/BF02764984
[24] H. Furstenberg and B. Weiss 1978 Topological dynamics and combinatorial number theory J. Analyse Math.34 61–85 · Zbl 0425.54023 · doi:10.1007/BF02790008
[25] J. Geelen and P. Nelson 2015 A density Hales–Jewett theorem for matroids J. Combin. Theory Ser. B112 70–77 · Zbl 1310.05047 · doi:10.1016/j.jctb.2014.11.008
[26] J. Geelen and P. Nelson 2012 1210.4522 9 pp.
[27] J.-Y. Girard 1987 Proof theory and logical complexity Stud. Proof Theory Monogr. 1 Bibliopolis, Naples 505 pp.
[28] R. L. Graham, K. Leeb, and B. L. Rothschild 1972 Ramsey’s theorem for a class of categories Adv. Math.8 417–433 · Zbl 0243.18011 · doi:10.1016/0001-8708(72)90005-9
[29] R. L. Graham and B. L. Rothschild 1971 Ramsey’s theorem for n-parameter sets Trans. Amer. Math. Soc.159 257–292 · Zbl 0233.05003 · doi:10.2307/1996010
[30] R. L. Graham and B. L. Rothschild 1974 A short proof of van der Waerden’s theorem on arithmetic progressions Proc. Amer. Math. Soc.42 2 385–386 · Zbl 0278.05001 · doi:10.2307/2039512
[31] R. L. Graham and J. H. Spencer 1979 A general Ramsey product theorem Proc. Amer. Math. Soc.73 1 137–139 · Zbl 0408.05039 · doi:10.2307/2042899
[32] M. Gromov 1983 Filling Riemannian manifolds J. Differential Geom.18 1 1–147 · Zbl 0515.53037
[33] M. Gromov 1988 Dimension, non-linear spectra and width Geometric aspects of functional analysis1986/87 Lecture Notes in Math. 1317 Springer, Berlin 132–184 · doi:10.1007/BFb0081739
[34] M. Gromov 1999 Metric structures for Riemannian and non-Riemannian spaces Progr. Math. 152 Birkha\ddot{}user Boston, Inc., Boston, MA xx+585 pp.
[35] M. Gromov 1999 Endomorphisms of symbolic algebraic varieties J. Eur. Math. Soc. (JEMS)1 2 109–197 · Zbl 0998.14001 · doi:10.1007/PL00011162
[36] M. Gromov 2000 Spaces and questions Geom. Funct. Anal.GAFA 2000, Tel Aviv 1999 118–161 Special volume, Part I · Zbl 1006.53035 · doi:10.1007/978-3-0346-0422-2_5
[37] M. Gromov 2003 Isoperimetry of waists and concentration of maps Geom. Funct. Anal.13 1 178–215 · Zbl 1044.46057 · doi:10.1007/s000390300004
[38] M. Gromov 2008 Entropy and isoperimetry for linear and non-linear group actions Groups Geom. Dyn.2 4 499–593 · Zbl 1280.20043 · doi:10.4171/GGD/48
[39] M. Gromov 2010 Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry Geom. Funct. Anal.20 2 416–526 · Zbl 1251.05039 · doi:10.1007/s00039-010-0073-8
[40] M. Gromov 2014 Manifolds: Where do we come from? What are we? Where are we going The Poincare\acute{} conjecture Clay Math. Proc. 19 Amer. Math. Soc., Providence, RI 81–144 68 pp. http://www.ihes.fr/ gromov/PDF/manifolds-Poincare.pdf · Zbl 1304.57006
[41] M. Gromov and V. D. Milman 1983 A topological application of the isoperimetric inequality Amer. J. Math.105 4 843–854 · Zbl 0522.53039 · doi:10.2307/2374298
[42] L. J. Halbeisen 2012 Combinatorial set theory. With a gentle introduction to forcing Springer Monogr. Math. Springer, London xvi+453 pp. · Zbl 1237.03001 · doi:10.1007/978-1-4471-2173-2
[43] N. Hindman 1979 Ultrafilters and combinatorial number theory Number theorySouthern Illinois Univ., Carbondale, IL, 1979 Lecture Notes in Math. 751 Springer, Berlin 119–184 · doi:10.1007/BFb0062706
[44] A. S. Kechris, V. G. Pestov, and S. Todorcevic 2005 Frai\ddot{}sse\acute{} limits, Ramsey theory, and topological dynamics of automorphism groups Geom. Funct. Anal.15 1 106–189 · Zbl 1084.54014 · doi:10.1007/s00039-005-0503-1
[45] А. Я. Хинчин 1947 Три жемчужины теории чисел Гостехиздат, М.–Л. 72 pp. · Zbl 1222.11084
[46] English transl. of 2nd ed. A. Ya. Khinchin 1952 Three pearls of number theory Graylock Press, Rochester, N. Y. 64 pp.
[47] B. Klartag 2010 On nearly radial marginals of high-dimensional probability measures J. Eur. Math. Soc. (JEMS)12 3 723–754 · Zbl 1200.28015 · doi:10.4171/JEMS/213
[48] B. Klartag 2008 (v2 – 2009) 0810.4700 32 pp.
[49] M. Ledoux 2001 The concentration of measure phenomenon Math. Surveys Monogr. 89 Amer. Math. Soc., Providence, RI x+181 pp.
[50] P. Le\acute{}vy 1951 Proble\grave{}mes concrets d’analyse fonctionnelle Gauthier-Villars, Paris 2nd ed., xiv+484 pp.
[51] G. L. Litvinov 2011 Tropical mathematics, idempotent analysis, classical mechanics and geometry Spectral theory and geometric analysis Contemp. Math. 535 Amer. Math. Soc., Providence, RI 159–186 · Zbl 1207.58001 · doi:10.1090/conm/535
[52] J. Matoušek 2008 Using the Borsuk–Ulam theorem, Lectures on topological methods in combinatorics and geometry Universitext Springer-Verlag, Berlin 2nd corr. print.xii+214 pp. · Zbl 1234.05002 · doi:10.1007/978-3-540-76649-0
[53] В. Д. Мильман 1971 Новое доказательство теоремы А. Дворецкого о сечениях выпуклых тел Функц. анализ и его прил.5 4 28–37 · Zbl 1154.68045
[54] English transl. V. D. Milman 1971 New proof of the theorem of A. Dvoretzky on intersections of convex bodies Funct. Anal. Appl.5 4 288–295 · Zbl 0239.46018 · doi:10.1007/BF01086740
[55] V. D. Milman 1985 Almost Euclidean quotient spaces of subspaces of a finite-dimensional normed space Proc. Amer. Math. Soc.94 3 445–449 · Zbl 0239.46018 · doi:10.1007/BF01086740
[56] V. D. Milman 1988 A few observations on the connections between local theory and some other fields Geometric aspects of functional analysis1986/87 Lecture Notes in Math. 1317 Springer, Berlin 283–289 · doi:10.1007/BFb0081748
[57] D. Mubayi and V. Rödl 2007 On the chromatic number and independence number of hypergraph products J. Combin. Theory Ser. B97 1 151–155 · Zbl 1108.05042 · doi:10.1016/j.jctb.2006.03.005
[58] D. Mubayi and V. Rödl 2004 J. Combin. Theory Ser. B 6 pp. http://www.math.cmu.edu/ mubayi/papers/bergesimon.pdf
[59] M. B. Nathanson 1996 Additive number theory. The classical bases Grad. Texts in Math. 164 Springer-Verlag, New York xiv+342 pp. · doi:10.1007/978-1-4757-3845-2
[60] A. Papadopoulos 2014 Hilbert’s fourth problem Handbook of Hilbert geometry IRMA Lect. Math. Theor. Phys. 22 Eur. Math. Soc., Zürich 391–431 · doi:10.4171/147-1/15
[61] A. Papadopoulos 2013 Handbook of Hilbert geometry 1312.3172 43 pp.
[62] J. Paris and L. HarringtonJ. Barwise (Eds) 1977 A mathematical incompleteness in Peano arithmetic Handbook of mathematical logic Stud. Logic Found. Math. 90 North-Holland Publ. Co., Amsterdam–New York–Oxford 1133–1142 · doi:10.1016/S0049-237X(08)71130-3
[63] V. Pestov 2006 Dynamics of infinite-dimensional groups. The Ramsey–Dvoretzky–Milman phenomenon Univ. Lecture Ser. 40 Amer. Math. Soc., Providence, RI viii+192 pp. · Zbl 1123.37003 · doi:10.1090/ulect/040
[64] G. Pisier 1986 Probabilistic methods in the geometry of Banach spaces Probability and analysisVarenna, 1985 Lecture Notes in Math. 1206 Springer, Berlin 167–241 · doi:10.1007/BFb0076302
[65] D. H. J. Polymath 2012 A new proof of the density Hales–Jewett theorem Ann. of Math. (2)175 3 1283–1327 · Zbl 1267.11010 · doi:10.4007/annals.2012.175.3.6
[66] D. H. J. Polymath 2009 (v2 – 2010) 0910.3926 34 pp.
[67] E. Schmidt 1943/44 Beweis der isoperimetrischen Eigenschaft der Kugel im hyperbolischen und spha\ddot{}rischen Raum jeder Dimensionszahl Math. Z.49 1–109 · Zbl 0028.31303 · doi:10.1007/BF01174192
[68] I. Schur 1916 Über die Kongruenz x^{m}+y^{m}\equiv z^{m} (mod p)Jahresber. Deutsch. Math.-Verein.25 114–117 · JFM 46.0193.02
[69] S. Shelah 1988 Primitive recursive bounds for van der Waerden numbers J. Amer. Math. Soc.1 3 683–697 · Zbl 0649.05010 · doi:10.1090/S0894-0347-1988-0929498-X
[70] A. Soifer 2009 The mathematical coloring book. Mathematics of coloring and the colorful life of its creators Springer, New York xxx+607 pp. · Zbl 1221.05001 · doi:10.1007/978-0-387-74642-5
[71] A. Soifer (ed.) 2011 Ramsey theory. Yesterday, today, and tomorrowRutgers Univ., Piscataway, NJ, May 27–29, 2009 Progr. Math. 285 Birkha\ddot{}user/Springer, New York xiv+189 pp. · Zbl 1202.05004 · doi:10.1007/978-0-8176-8092-3
[72] S. Solecki 2013 Abstract approach to finite Ramsey theory and a self-dual Ramsey theorem Adv. Math.248 1156–1198 · Zbl 1283.05176 · doi:10.1016/j.aim.2013.07.021
[73] S. Solecki 2011 (v3 – 2013) 1104.3950 50 pp.
[74] J. H. Spencer 1979 Ramsey’s theorem for spaces Trans. Amer. Math. Soc.249 2 363–371 · Zbl 0387.05018 · doi:10.2307/1998796
[75] M. Talagrand 1995 Concentration of measure and isoperimetric inequalities in product spaces Inst. Hautes E\acute{}tudes Sci. Publ. Math.81 1 73–205 · Zbl 0864.60013 · doi:10.1007/BF02699376
[76] S. B. Todorcevic 2010 Introduction to Ramsey spaces Ann. of Math. Stud. 174 Princeton Univ. Press, Princeton, NJ viii+287 pp. · Zbl 0864.60013 · doi:10.1007/BF02699376
[77] R. Vershynin 2009 Lectures in geometric functional analysis 76 pp. http://www-personal.umich.edu/ romanv/papers/GFA-book/GFA-book.pdf
[78] D. Masulovic and L. Scow 2015 Categorical constructions and the Ramsey property 1506.01221v4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.