×

All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms). (English) Zbl 1421.05091

Summary: We prove the Ramsey property for classes of ordered structures with closures and given local properties. This generalises earlier results: the Nešetřil-Rödl theorem, the Ramsey property of partial orders and metric spaces as well as the authors’ Ramsey lift of bowtie-free graphs. We use this framework to solve several open problems and give new examples of Ramsey classes. Among others, we find Ramsey lifts of convexly ordered \(S\)-metric spaces and prove the Ramsey theorem for finite models (i.e. structures with both functions and relations) thus providing the ultimate generalisation of the structural Ramsey theorem. Both of these results are natural, and easy to state, yet their proofs involve most of the theory developed here. We also characterise Ramsey lifts of classes of structures defined by finitely many forbidden homomorphisms and extend this to special cases of classes with closures. This has numerous applications. For example, we find Ramsey lifts of many Cherlin-Shelah-Shi classes.

MSC:

05D10 Ramsey theory
06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abramson, F. G.; Harrington, L. A., Models without indiscernibles, J. Symbolic Logic, 43, 572-600 (1978) · Zbl 0391.03027
[2] Bodirsky, M., Ramsey classes: examples and constructions, (Surveys in Combinatorics 2015, vol. 424 (2015)), 1 · Zbl 1352.05183
[3] Bodirsky, M.; Pinsker, M.; Tsankov, T., Decidability of definability, (Proceedings of the 2011 IEEE 26th Annual Symposium on Logic in Computer Science. Proceedings of the 2011 IEEE 26th Annual Symposium on Logic in Computer Science, LICS ’11 (2011), IEEE Computer Society: IEEE Computer Society Washington, DC, USA), 321-328
[4] Cherlin, G., The Classification of Countable Homogeneous Directed Graphs and Countable Homogeneous \(N\)-Tournaments, Memoirs of the American Mathematical Society, vol. 621 (1998), American Mathematical Society · Zbl 0978.03029
[5] Cherlin, G., Forbidden substructures and combinatorial dichotomies: WQO and universality, Discrete Math., 311, 15, 1543-1584 (2011) · Zbl 1223.05131
[6] G. Cherlin, Homogeneous ordered graphs and metrically homogeneous graphs, December 2017, in preparation.; G. Cherlin, Homogeneous ordered graphs and metrically homogeneous graphs, December 2017, in preparation.
[7] Cherlin, G.; Komjáth, P., There is no universal countable pentagon-free graph, J. Graph Theory, 18, 4, 337-341 (1994) · Zbl 0805.05044
[8] G. Cherlin, S. Shelah, Universal graphs with one forbidden subgraph: the generic case, in preparation.; G. Cherlin, S. Shelah, Universal graphs with one forbidden subgraph: the generic case, in preparation. · Zbl 1389.05112
[9] Cherlin, G.; Shelah, S., The tree conjecture for universal graphs, J. Combin. Theory Ser. B, 97, 293-333 (2007) · Zbl 1116.03026
[10] Cherlin, G.; Shelah, S., Universal graphs with a forbidden subtree, J. Combin. Theory Ser. B, 97, 3, 293-333 (2007) · Zbl 1116.03026
[11] Cherlin, G.; Shelah, S., Universal graphs with a forbidden subgraph: block path solidity, Combinatorica, 1-16 (2013)
[12] Cherlin, G.; Shelah, S.; Shi, N., Universal graphs with forbidden subgraphs and algebraic closure, Adv. in Appl. Math., 22, 4, 454-491 (1999) · Zbl 0928.03049
[13] Cherlin, G.; Shi, N., Graphs omitting a finite set of cycles, J. Graph Theory, 21, 3, 351-355 (1996) · Zbl 0845.05060
[14] Cherlin, G.; Shi, N., Forbidden subgraphs and forbidden substructures, J. Symbolic Logic, 1342-1352 (2001) · Zbl 0986.03029
[15] Cherlin, G.; Shi, N.; Tallgren, L., Graphs omitting a bushy tree, J. Graph Theory, 26, 4, 203-210 (1997) · Zbl 0918.05041
[16] Cherlin, G.; Tallgren, L., Universal graphs with a forbidden near-path or 2-bouquet, J. Graph Theory, 56, 1, 41-63 (2007) · Zbl 1131.03013
[17] Covington, J., Homogenizable relational structures, Illinois J. Math., 34, 4, 731-743 (1990) · Zbl 0706.03030
[18] Delhommé, C.; Laflamme, C.; Pouzet, M.; Sauer, N. W., Divisibility of countable metric spaces, European J. Combin., 28, 6, 1746-1769 (2007) · Zbl 1206.54025
[19] Dellamonica, D.; Rödl, V., Distance preserving Ramsey graphs, Combin. Probab. Comput., 21, 04, 554-581 (2012) · Zbl 1247.05148
[20] Erdős, P. L.; Pálvölgyi, D.; Tardif, C.; Tardos, G., Regular families of forests, antichains and duality pairs of relational structures, Combinatorica, 37, 4, 651-672 (2017) · Zbl 1399.68066
[21] D.M. Evans, Notes on topological dynamics of automorphism groups of Hrushovski constructions, Private communication.; D.M. Evans, Notes on topological dynamics of automorphism groups of Hrushovski constructions, Private communication.
[22] Evans, D. M.; Hubička, J.; Nešetřil, J., Ramsey properties and extending partial automorphisms for classes of finite structures, Fund. Math. (2017), in press
[23] Evans, D. M.; Hubička, J.; Nešetřil, J., Automorphism groups and Ramsey properties of sparse graphs, Proc. Lond. Math. Soc., 119, 2, 515-546 (2019) · Zbl 1425.05087
[24] Fouché, W. L., Symmetry and the Ramsey degree of posets, Discrete Math., 167, 309-315 (1997) · Zbl 0873.05076
[25] Fraïssé, R., Sur certaines relations qui généralisent l’ordre des nombres rationnels, C. R. Acad. Sci., 237, 540-542 (1953) · Zbl 0051.03803
[26] Fraïssé, R., Theory of Relations, Studies in Logic and the Foundations of Mathematics (1986), North-Holland · Zbl 0593.04001
[27] Füredi, Z.; Komjáth, P., Nonexistence of universal graphs without some trees, Combinatorica, 17, 2, 163-171 (1997) · Zbl 0889.05038
[28] Füredi, Z.; Komjáth, P., On the existence of countable universal graphs, J. Graph Theory, 25, 1, 53-58 (1997) · Zbl 0878.05064
[29] Graham, R. L.; Leeb, K.; Rothschild, B. L., Ramsey’s theorem for a class of categories, Adv. Math., 8, 3, 417-433 (1972) · Zbl 0243.18011
[30] Graham, R. L.; Rothschild, B. L., Ramsey’s theorem for \(n\)-parameter sets, Trans. Amer. Math. Soc., 159, 257-292 (1971) · Zbl 0233.05003
[31] Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory (1990), Wiley, a Wiley-Interscience Publication · Zbl 0705.05061
[32] Hales, A. W.; Jewett, R. I., Regularity and positional games, Trans. Amer. Math. Soc., 106, 222-229 (1963) · Zbl 0113.14802
[33] Halpern, J. D.; Läuchli, H., A partition theorem, Trans. Amer. Math. Soc., 124, 2, 360-367 (1966) · Zbl 0158.26902
[34] Hartman, D.; Hubička, J.; Nešetřil, J., Complexities of relational structures, Math. Slovaca, 65, 2, 229-246 (2015) · Zbl 1349.05283
[35] Hell, P.; Nešetřil, J., Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications (2004), Oxford University Press · Zbl 1062.05139
[36] Hodges, W., Model Theory, vol. 42 (1993), Cambridge University Press
[37] Hubička, J.; Nešetřil, J., Finite presentation of homogeneous graphs, posets and Ramsey classes, Israel J. Math., 149, 1, 21-44 (2005) · Zbl 1091.05070
[38] Hubička, J.; Nešetřil, J., Ramsey classes with forbidden homomorphisms and a closure, Electron. Notes Discrete Math., 49, 737-745 (2015) · Zbl 1346.05294
[39] Hubička, J.; Nešetřil, J., Universal structures with forbidden homomorphisms, (Hirvonen, Å.; Kontinen, J.; Kossak, R.; Villaveces, A., Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics. Logic Without Borders: Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics, Ontos Mathematical Logic Series (2015), De Gruyter), 241-264 · Zbl 1429.03133
[40] Hubička, J.; Nešetřil, J., Homomorphism and embedding universal structures for restricted classes, J. Mult.-Valued Logic Soft Comput., 27, 2-3, 229-253 (2016) · Zbl 1394.03058
[41] Hubička, J.; Nešetřil, J., Bowtie-free graphs have a Ramsey lift, Adv. in Appl. Math., 96, 286-311 (2018) · Zbl 1383.05206
[42] Ivanov, A. A.; Macpherson, D., Strongly determined types, Ann. Pure Appl. Logic, 99, 1, 197-230 (1999) · Zbl 0934.03049
[43] Jasiński, J.; Laflamme, C.; Nguyen Van Thé, L.; Woodrow, R., Ramsey precompact expansions of homogeneous directed graphs, Electron. J. Combin., 21 (2014) · Zbl 1305.05139
[44] Katětov, M., On universal metric spaces, (General Topology and Its Relations to Modern Analysis and Algebra, VI. General Topology and Its Relations to Modern Analysis and Algebra, VI, Prague, 1986. General Topology and Its Relations to Modern Analysis and Algebra, VI. General Topology and Its Relations to Modern Analysis and Algebra, VI, Prague, 1986, Research and Exposition in Mathematics, vol. 16 (1986)), 323-330
[45] Kechris, A. S.; Pestov, V. G.; Todorčević, S., Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geom. Funct. Anal., 15, 1, 106-189 (2005) · Zbl 1084.54014
[46] Komjáth, P., Some remarks on universal graphs, Discrete Math., 199, 1, 259-265 (1999) · Zbl 0930.05082
[47] Komjáth, P.; Mekler, A. H.; Pach, J., Some universal graphs, Israel J. Math., 64, 2, 158-168 (1988) · Zbl 0672.05074
[48] Kun, G.; Nešetřil, J., Forbidden lifts (NP and CSP for combinatorialists), European J. Combin., 29, 4, 930-945 (2008) · Zbl 1213.68323
[49] Lachlan, A. H.; Woodrow, R. E., Countable ultrahomogeneous undirected graphs, Trans. Amer. Math. Soc., 51-94 (1980) · Zbl 0471.03025
[50] Leeb, K., Vorlesungen über Pascaltheorie, Arb.ber. Inst. Math. Masch. Datenverarb., 6 (1973)
[51] Melleray, J.; Nguyen Van Thé, L.; Tsankov, T., Polish groups with metrizable universal minimal flows, Int. Math. Res. Not. (2015), rnv171 · Zbl 1359.37023
[52] Milliken, K. R., A Ramsey theorem for trees, J. Combin. Theory Ser. A, 26, 3, 215-237 (1979) · Zbl 0429.05035
[53] J. Nešetřil, Ramsey classes with forbidden homomorphisms, in preparation.; J. Nešetřil, Ramsey classes with forbidden homomorphisms, in preparation.
[54] Nešetřil, J., For graphs there are only four types of hereditary Ramsey classes, J. Combin. Theory Ser. B, 46, 2, 127-132 (1989) · Zbl 0736.05071
[55] Nešetřil, J., Ramsey theory, (Graham, R. L.; Grötschel, M.; Lovász, L., Handbook of Combinatorics, vol. 2 (1995), MIT Press: MIT Press Cambridge, MA, USA), 1331-1403 · Zbl 0848.05065
[56] Nešetril, J., Ramsey classes and homogeneous structures, Combin. Probab. Comput., 14, 1-2, 171-189 (2005) · Zbl 1059.05103
[57] Nešetřil, J., Metric spaces are Ramsey, European J. Combin., 28, 1, 457-468 (2007) · Zbl 1106.05099
[58] Nešetřil, J.; Rödl, V., The Ramsey property for graphs with forbidden complete subgraphs, J. Combin. Theory Ser. B, 20, 3, 243-249 (1976) · Zbl 0329.05115
[59] Nešetřil, J.; Rödl, V., A structural generalization of the Ramsey theorem, Bull. Amer. Math. Soc., 83, 1, 127-128 (1977) · Zbl 0344.05002
[60] Nešetřil, J.; Rödl, V., A short proof of the existence of highly chromatic hypergraphs without short cycles, J. Combin. Theory Ser. B, 27, 2, 225-227 (1979) · Zbl 0413.05039
[61] Nešetřil, J.; Rödl, V., Simple proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica, 1, 2, 199-202 (1981) · Zbl 0491.05044
[62] Nešetřil, J.; Rödl, V., Two proofs of the Ramsey property of the class of finite hypergraphs, European J. Combin., 3, 4, 347-352 (1982) · Zbl 0505.05047
[63] Nešetřil, J.; Rödl, V., Ramsey classes of set systems, J. Combin. Theory Ser. A, 34, 2, 183-201 (1983) · Zbl 0515.05010
[64] Nešetřil, J.; Rödl, V., Combinatorial partitions of finite posets and lattices Ramsey lattices, Algebra Universalis, 19, 1, 106-119 (1984) · Zbl 0546.06002
[65] Nešetřil, J.; Rödl, V., Strong Ramsey theorems for Steiner systems, Trans. Amer. Math. Soc., 303, 1, 183-192 (1987) · Zbl 0632.05040
[66] Nešetřil, J.; Rödl, V., The partite construction and Ramsey set systems, Discrete Math., 75, 1, 327-334 (1989) · Zbl 0671.05006
[67] Nešetřil, J.; Rödl, V., Partite construction and Ramsey space systems, (Mathematics of Ramsey Theory. Mathematics of Ramsey Theory, Algorithms and Combinatorics, vol. 5 (1990), Springer), 98-112 · Zbl 0743.05071
[68] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. B, 80, 1, 80-97 (2000) · Zbl 1024.05078
[69] Nguyen Van Thé, L., Structural Ramsey Theory of Metric Spaces and Topological Dynamics of Isometry Groups, Memoirs of the American Mathematical Society (2010), American Mathematical Society · Zbl 1203.05159
[70] Nguyen Van Thé, L., More on the Kechris-Pestov-Todorcevic correspondence: precompact expansions, Fund. Math., 222, 19-47 (2013) · Zbl 1293.37006
[71] L. Nguyen Van Thé, Structural Ramsey theory with the Kechris-Pestov-Todorcevic correspondence in mind, Habilitation memoir, 2013.; L. Nguyen Van Thé, Structural Ramsey theory with the Kechris-Pestov-Todorcevic correspondence in mind, Habilitation memoir, 2013.
[72] Paoli, M.; Trotter, W. T.; Walker, J. W., Graphs and orders in Ramsey theory and in dimension theory, (Rival, I., Graphs and Order. Graphs and Order, NATO AST Series, vol. 147 (1985), Springer), 351-394 · Zbl 0566.05045
[73] Prak, D., Set Theoretic Constructions in Model Theory (1964), Massachusetts Institute of Technology, PhD thesis
[74] Sauer, N. W., Vertex partitions of metric spaces with finite distance sets, Discrete Math., 312, 1, 119-128 (2012) · Zbl 1238.05270
[75] Sauer, N. W., Distance sets of Urysohn metric spaces, Canad. J. Math., 65, 1, 222-240 (2013) · Zbl 1270.03070
[76] Sauer, N. W., Oscillation of Urysohn type spaces, (Asymptotic Geometric Analysis (2013), Springer), 247-270 · Zbl 1281.51010
[77] Shelah, S., Classification Theory and the Number of Non-Isomorphic Models (1990), Elsevier · Zbl 0713.03013
[78] Sokić, M., Unary functions, European J. Combin., 52, 79-94 (2016) · Zbl 1327.05330
[79] Solecki, S., Direct Ramsey theorem for structures involving relations and functions, J. Combin. Theory Ser. A, 119, 2, 440-449 (2012) · Zbl 1232.05226
[80] Urysohn, P. S., Sur un espace métrique universel, Bull. Sci. Math., 51, 2, 43-64 (1927) · JFM 53.0556.01
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.