| Title:
|
On dual Ramsey theorems for relational structures (English) |
| Author:
|
Mašulović, Dragan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
70 |
| Issue:
|
2 |
| Year:
|
2020 |
| Pages:
|
553-585 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
dual Ramsey property |
| Keyword:
|
finite relational structure |
| Keyword:
|
category theory |
| MSC:
|
05C55 |
| MSC:
|
18A99 |
| idZBL:
|
07217151 |
| idMR:
|
MR4111859 |
| DOI:
|
10.21136/CMJ.2020.0408-18 |
| . |
| Date available:
|
2020-06-17T12:37:25Z |
| Last updated:
|
2022-07-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148245 |
| . |
| Reference:
|
[1] Abramson, F. G., Harrington, L. A.: Models without indiscernibles.J. Symb. Log. 43 (1978), 572-600. Zbl 0391.03027, MR 0503795, 10.2307/2273534 |
| Reference:
|
[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). Zbl 0695.18001, MR 1051419 |
| Reference:
|
[3] Frankl, P., Graham, R. L., Rödl, V.: Induced restricted Ramsey theorems for spaces.J. Comb. Theory, Ser. A 44 (1987), 120-128. Zbl 0608.05059, MR 0871393, 10.1016/0097-3165(87)90064-1 |
| Reference:
|
[4] Graham, R. L., Rothschild, B. L.: Ramsey's theorem for $n$-parameter sets.Trans. Am. Math. Soc. 159 (1971), 257-292. Zbl 0233.05003, MR 0284352, 10.1090/S0002-9947-1971-0284352-8 |
| Reference:
|
[5] Mašulović, D.: A dual Ramsey theorem for permutations.Electron. J. Comb. 24 (2017), Article ID P3.39, 12 pages. Zbl 1369.05200, MR 3691556 |
| Reference:
|
[6] Mašulović, D.: Pre-adjunctions and the Ramsey property.Eur. J. Comb. 70 (2018), 268-283. Zbl 1384.05153, MR 3779618, 10.1016/j.ejc.2018.01.006 |
| Reference:
|
[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. Zbl 1421.08003, MR 3697187, 10.1007/s00012-017-0453-0 |
| Reference:
|
[8] Nešetřil, J.: Ramsey theory.Handbook of Combinatorics, Vol. 2 R. L. Graham et al. Elsevier, Amsterdam, (1995), 1331-1403. Zbl 0848.05065, MR 1373681 |
| Reference:
|
[9] Nešetřil, J.: Metric spaces are Ramsey.Eur. J. Comb. 28 (2007), 457-468. Zbl 1106.05099, MR 2261831, 10.1016/j.ejc.2004.11.003 |
| Reference:
|
[10] Nešetřil, J., Rödl, V.: Partitions of finite relational and set systems.J. Comb. Theory, Ser. A 22 (1977), 289-312. Zbl 0361.05017, MR 0437351, 10.1016/0097-3165(77)90004-8 |
| Reference:
|
[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. |
| Reference:
|
[12] Nešetřil, J., Rödl, V.: Ramsey classes of set systems.J. Comb. Theory, Ser. A 34 (1983), 183-201. Zbl 0515.05010, MR 0692827, 10.1016/0097-3165(83)90055-9 |
| Reference:
|
[13] Nešetřil, J., Rödl, V.: The partite construction and Ramsey set systems.Discrete Math. 75 (1989), 327-334. Zbl 0671.05006, MR 1001405, 10.1016/0012-365X(89)90097-6 |
| Reference:
|
[14] Prömel, H. J.: Induced partition properties of combinatorial cubes.J. Comb. Theory, Ser. A 39 (1985), 177-208. Zbl 0638.05005, MR 0793270, 10.1016/0097-3165(85)90036-6 |
| Reference:
|
[15] Prömel, H. J., Voigt, B.: Hereditary attributes of surjections and parameter sets.Eur. J. Comb. 7 (1986), 161-170. Zbl 0606.05002, MR 0856329, 10.1016/S0195-6698(86)80042-7 |
| Reference:
|
[16] Prömel, H. J., Voigt, B.: A sparse Graham-Rothschild theorem.Trans. Am. Math. Soc. 309 (1988), 113-137. Zbl 0662.05006, MR 0957064, 10.1090/S0002-9947-1988-0957064-5 |
| Reference:
|
[17] Ramsey, F. P.: On a problem of formal logic.Proc. Lond. Math. Soc. 30 (1930), 264-286 \99999JFM99999 55.0032.04. MR 1576401, 10.1112/plms/s2-30.1.264 |
| Reference:
|
[18] Sokić, M.: Ramsey properties of finite posets II.Order 29 (2012), 31-47. Zbl 1254.03067, MR 2948747, 10.1007/s11083-011-9196-2 |
| Reference:
|
[19] Solecki, S.: A Ramsey theorem for structures with both relations and functions.J. Comb. Theory, Ser. A 117 (2010), 704-714. Zbl 1247.05256, MR 2645186, 10.1016/j.jcta.2009.12.004 |
| . |
