Big Ramsey degrees and infinite languages
Samuel Braunfeld, David Chodounský, Noé de Rancourt, Jan Hubička, Jamal K. Kawach, Matěj Konečný · Advances in Combinatorics · 2024
One of the most well-known results in combinatorics is [Ramsey's Theorem](https://en.wikipedia.org/wiki/Ramsey%27s_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 $q_1,q_2,\ldots,$ of all rational numbers and color pairs of rational numbers as follows: the pair $q_i$ and $q_j$ is colored red if either $q_i q_j$ 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 $\ell$ 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 $\ell$ different colors. For example, if $B$ is a countably infinite complete graph and $A$ is the graph $K_{1,2}$, then the above property holds with $\ell=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.