Big Ramsey degrees and infinite languages

- Computer Science Institute of Charles University, Charles University
**ORCID iD:**0000-0003-3531-9970

- Department of Applied Mathematics, Charles University
- Institute of Mathematics, Czech Academy of Sciences
**ORCID iD:**0000-0002-3352-9213

- Department of Applied Mathematics, Charles University
**ORCID iD:**0000-0001-8704-0803

- Department of Mathematics, University of Toronto
**ORCID iD:**0000-0002-5587-1175

- Institute of Algebra, TU Dresden
- Department of Applied Mathematics, Charles University
**ORCID iD:**0000-0001-7391-3247

- Laboratoire Paul Painlevé, Université de Lille & CNRS

*Advances in Combinatorics*, August. https://doi.org/10.19086/aic.2024.4.

### Editorial introduction

One of the most well-known results in combinatorics is Ramsey’s Theorem, which asserts that for every two positive integers k and n, there exists a positive integer N such that every k-edge-coloring of the N-vertex complete graph contains a monochromatic copy of the complete graph with n vertices. Ramsey’s Theorem has been extended and generalized in numerous ways. The starting point for research presented in this paper is the following generalization: for every positive integer k, every k-edge-coloring of the edges of a countably infinite complete graph contains a monochromatic countably infinite complete graph.

It is not true that it is always possible to find a monochromatic infinite substructure isomorphic to the host structure as demonstrated by the following example due to Sierpiński. Consider an arbitrary order q1,q2,…, of all rational numbers and color pairs of rational numbers as follows: the pair qi and qj is colored red if either qi<qj and i<j or qi>qj and i>j; otherwise it is blue. It is easy to show that any subset of rational numbers isomorphic to the set of all rational numbers contains pairs of both colors. This example is also tight in the sense that Galvin showed that any coloring of pairs of rational numbers with a finite number of colors contains a bichromatic subset isomorphic to the set of all rational numbers. Galvin’s result leads to the following definition: a countably infinite structure B has *finite big Ramsey degrees* if for every finite structure A, there exists ℓ such that every coloring of copies of A in B with finitely many colors contains a copy of B where the copies of A have at most ℓ different colors. For example, if B is a countably infinite complete graph and A is the graph K1,2, then the above property holds with ℓ=3 (which is the smallest possible value in this setting). The main result of the paper asserts that a countably infinite structure has finite big Ramsey degrees whenever it possesses a certain universality property, has only injective relations, and has only finitely many relations of each arity greater than one.