Czechoslovak Mathematical Journal, Vol. 70, No. 2, pp. 553-585, 2020


On dual Ramsey theorems for relational structures

Dragan Mašulović

Received September 18, 2018.   Published online February 7, 2020.

Abstract:  We discuss dual Ramsey statements for several classes of finite relational structures (such as finite linearly ordered graphs, finite linearly ordered metric spaces and finite posets with a linear extension) and conclude the paper with another rendering of the Nešetřil-Rödl Theorem for relational structures. Instead of embeddings which are crucial for "direct" Ramsey results, for each class of structures under consideration we propose a special class of quotient maps and prove a dual Ramsey theorem in such a setting. Although our methods are based on reinterpreting the (dual) Ramsey property in the language of category theory, all our results are about classes of finite structures.
Keywords:  dual Ramsey property; finite relational structure; category theory
Classification MSC:  05C55, 18A99
DOI:  10.21136/CMJ.2020.0408-18


References:
[1] F. G. Abramson, L. A. Harrington: Models without indiscernibles. J. Symb. Log. 43 (1978), 572-600. DOI 10.2307/2273534 | MR 0503795 | Zbl 0391.03027
[2] J. Adámek, H. Herrlich, G. E. Strecker: Abstract and Concrete Categories: The Joy of Cats. Dover Books on Mathematics, Dover Publications, Mineola (2009). MR 1051419 | Zbl 0695.18001
[3] P. Frankl, R. L. Graham, V. Rödl: Induced restricted Ramsey theorems for spaces. J. Comb. Theory, Ser. A 44 (1987), 120-128. DOI 10.1016/0097-3165(87)90064-1 | MR 0871393 | Zbl 0608.05059
[4] R. L. Graham, B. L. Rothschild: Ramsey's theorem for $n$-parameter sets. Trans. Am. Math. Soc. 159 (1971), 257-292. DOI 10.1090/S0002-9947-1971-0284352-8 | MR 0284352 | Zbl 0233.05003
[5] D. Mašulović: A dual Ramsey theorem for permutations. Electron. J. Comb. 24 (2017), Article ID P3.39, 12 pages. MR 3691556 | Zbl 1369.05200
[6] D. Mašulović: Pre-adjunctions and the Ramsey property. Eur. J. Comb. 70 (2018), 268-283. DOI 10.1016/j.ejc.2018.01.006 | MR 3779618 | Zbl 1384.05153
[7] D. Mašulović, L. Scow: Categorical equivalence and the Ramsey property for finite powers of a primal algebra. Algebra Univers. 78 (2017), 159-179. DOI 10.1007/s00012-017-0453-0 | MR 3697187 | Zbl 1421.08003
[8] J. Nešetřil: Ramsey theory. Handbook of Combinatorics, Vol. 2 (R. L. Graham et al., eds.). Elsevier, Amsterdam, (1995), 1331-1403. MR 1373681 | Zbl 0848.05065
[9] J. Nešetřil: Metric spaces are Ramsey. Eur. J. Comb. 28 (2007), 457-468. DOI 10.1016/j.ejc.2004.11.003 | MR 2261831 | Zbl 1106.05099
[10] J. Nešetřil, V. Rödl: Partitions of finite relational and set systems. J. Comb. Theory, Ser. A 22 (1977), 289-312. DOI 10.1016/0097-3165(77)90004-8 | MR 0437351 | Zbl 0361.05017
[11] J. Nešetřil, V. Rödl: Dual Ramsey type theorems. Abstracta Eighth Winter School on Abstract Analysis, Mathematical Institute AS CR, Prague (Z. Frolík, ed.). (1980), 121-123.
[12] J. Nešetřil, V. Rödl: Ramsey classes of set systems. J. Comb. Theory, Ser. A 34 (1983), 183-201. DOI 10.1016/0097-3165(83)90055-9 | MR 0692827 | Zbl 0515.05010
[13] J. Nešetřil, V. Rödl: The partite construction and Ramsey set systems. Discrete Math. 75 (1989), 327-334. DOI 10.1016/0012-365X(89)90097-6 | MR 1001405 | Zbl 0671.05006
[14] H. J. Prömel: Induced partition properties of combinatorial cubes. J. Comb. Theory, Ser. A 39 (1985), 177-208. DOI 10.1016/0097-3165(85)90036-6 | MR 0793270 | Zbl 0638.05005
[15] H. J. Prömel, B. Voigt: Hereditary attributes of surjections and parameter sets. Eur. J. Comb. 7 (1986), 161-170. DOI 10.1016/S0195-6698(86)80042-7 | MR 0856329 | Zbl 0606.05002
[16] H. J. Prömel, B. Voigt: A sparse Graham-Rothschild theorem. Trans. Am. Math. Soc. 309 (1988), 113-137. DOI 10.1090/S0002-9947-1988-0957064-5 | MR 0957064 | Zbl 0662.05006
[17] F. P. Ramsey: On a problem of formal logic. Proc. Lond. Math. Soc. 30 (1930), 264-286. DOI 10.1112/plms/s2-30.1.264 | MR 1576401 | JFM 55.0032.04
[18] M. Sokić: Ramsey properties of finite posets II. Order 29 (2012), 31-47. DOI 10.1007/s11083-011-9196-2 | MR 2948747 | Zbl 1254.03067
[19] S. Solecki: A Ramsey theorem for structures with both relations and functions. J. Comb. Theory, Ser. A 117 (2010), 704-714. DOI 10.1016/j.jcta.2009.12.004 | MR 2645186 | Zbl 1247.05256

Affiliations:   Dragan Mašulović, Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Trg Dositeja Obradovića, 21000 Novi Sad, Serbia, e-mail: dragan.masulovic@dmi.uns.ac.rs


 
PDF available at: