Geodesic
On dual Ramsey theorems for relational structures
Czechoslovak Mathematical Journal, Tome 70 (2020) no. 2, pp. 553-585
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2020.0408-18
Classification : 05C55, 18A99
Keywords: dual Ramsey property; finite relational structure; category theory 
@article{10_21136_CMJ_2020_0408_18,
     author = {Ma\v{s}ulovi\'c, Dragan},
     title = {On dual {Ramsey} theorems for relational structures},
     journal = {Czechoslovak Mathematical Journal},
     pages = {553--585},
     year = {2020},
     volume = {70},
     number = {2},
     doi = {10.21136/CMJ.2020.0408-18},
     mrnumber = {4111859},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2020.0408-18/}
}
TY  - JOUR
AU  - Mašulović, Dragan
TI  - On dual Ramsey theorems for relational structures
JO  - Czechoslovak Mathematical Journal
PY  - 2020
SP  - 553
EP  - 585
VL  - 70
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2020.0408-18/
DO  - 10.21136/CMJ.2020.0408-18
LA  - en
ID  - 10_21136_CMJ_2020_0408_18
ER  - 
%0 Journal Article
%A Mašulović, Dragan
%T On dual Ramsey theorems for relational structures
%J Czechoslovak Mathematical Journal
%D 2020
%P 553-585
%V 70
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2020.0408-18/
%R 10.21136/CMJ.2020.0408-18
%G en
%F 10_21136_CMJ_2020_0408_18
Mašulović, Dragan. On dual Ramsey theorems for relational structures. Czechoslovak Mathematical Journal, Tome 70 (2020) no. 2, pp. 553-585. doi: 10.21136/CMJ.2020.0408-18

[1] Abramson, F. G., Harrington, L. A.: Models without indiscernibles. J. Symb. Log. 43 (1978), 572-600. | DOI | MR | JFM

[2] Adámek, J., Herrlich, H., Strecker, G. E.: Abstract and Concrete Categories: The Joy of Cats. Dover Books on Mathematics, Dover Publications, Mineola (2009). | MR | JFM

[3] Frankl, P., Graham, R. L., Rödl, V.: Induced restricted Ramsey theorems for spaces. J. Comb. Theory, Ser. A 44 (1987), 120-128. | DOI | MR | JFM

[4] Graham, R. L., Rothschild, B. L.: Ramsey's theorem for $n$-parameter sets. Trans. Am. Math. Soc. 159 (1971), 257-292. | DOI | MR | JFM

[5] Mašulović, D.: A dual Ramsey theorem for permutations. Electron. J. Comb. 24 (2017), Article ID P3.39, 12 pages. | MR | JFM

[6] Mašulović, D.: Pre-adjunctions and the Ramsey property. Eur. J. Comb. 70 (2018), 268-283. | DOI | MR | JFM

[7] Mašulović, D., Scow, L.: Categorical equivalence and the Ramsey property for finite powers of a primal algebra. Algebra Univers. 78 (2017), 159-179. | DOI | MR | JFM

[8] Nešetřil, J.: Ramsey theory. Handbook of Combinatorics, Vol. 2 R. L. Graham et al. Elsevier, Amsterdam, (1995), 1331-1403. | MR | JFM

[9] Nešetřil, J.: Metric spaces are Ramsey. Eur. J. Comb. 28 (2007), 457-468. | DOI | MR | JFM

[10] Nešetřil, J., Rödl, V.: Partitions of finite relational and set systems. J. Comb. Theory, Ser. A 22 (1977), 289-312. | DOI | MR | JFM

[11] Nešetřil, J., Rödl, V.: Dual Ramsey type theorems. Abstracta Eighth Winter School on Abstract Analysis, Mathematical Institute AS CR, Prague (1980), Z. Frolík 121-123.

[12] Nešetřil, J., Rödl, V.: Ramsey classes of set systems. J. Comb. Theory, Ser. A 34 (1983), 183-201. | DOI | MR | JFM

[13] Nešetřil, J., Rödl, V.: The partite construction and Ramsey set systems. Discrete Math. 75 (1989), 327-334. | DOI | MR | JFM

[14] Prömel, H. J.: Induced partition properties of combinatorial cubes. J. Comb. Theory, Ser. A 39 (1985), 177-208. | DOI | MR | JFM

[15] Prömel, H. J., Voigt, B.: Hereditary attributes of surjections and parameter sets. Eur. J. Comb. 7 (1986), 161-170. | DOI | MR | JFM

[16] Prömel, H. J., Voigt, B.: A sparse Graham-Rothschild theorem. Trans. Am. Math. Soc. 309 (1988), 113-137. | DOI | MR | JFM

[17] Ramsey, F. P.: On a problem of formal logic. Proc. Lond. Math. Soc. 30 (1930), 264-286 \99999JFM99999 55.0032.04. | DOI | MR

[18] Sokić, M.: Ramsey properties of finite posets II. Order 29 (2012), 31-47. | DOI | MR | JFM

[19] Solecki, S.: A Ramsey theorem for structures with both relations and functions. J. Comb. Theory, Ser. A 117 (2010), 704-714. | DOI | MR | JFM

Cité par Sources :