Ramseyan property of structure

Question

A binary relation $R$ on $\mathbb{N}$ is $(n,k)$-Ramseyan iff for every coloring $f:[\mathbb{N}]^n\rightarrow l$, there exists a subset $G$ of $\mathbb{N}$ such that $(G,R)$ is isomorphic to $(\mathbb{N},R)$ and $|f([G]^n)|\leq k$ (i.e., there exists a 1-1 mapping $h:G\rightarrow \mathbb{N}$ such that $R(x,y)$ if and only if $R(h(x),h(y))$).

Question: Which binary relation is $(n,k)$-Ramseyan?

Is there any known result?

We know some special example. Say when $R$ is trivial ($R=\emptyset$), then it is $(n,1)$-Ramseyan (which is just the classic Ramsey theorem). When $(\mathbb{N},R)$ is a linear dense order structure then it is $(2,2)$-Ramseyan, $(3,12)$-Ramseyan and for every $n$ there exists $k_n$ such that it is $(n,k_n)$-Ramseyan.

Answer 1

This question is closely related to the problem of proving the existence of finite big Ramsey degrees. Namely, for a first-order language $L$ and an infinite $L$-structure $\textbf{B}$, we say $\textbf{B}$ has finite big Ramsey degrees if for every finite substructure $\textbf{A}$ there is an integer $T_{\textbf{A}}$ such that, whenever you colour all isomorphic copies of $\textbf{A}$ in $\textbf{B}$, there is a substructure $\textbf{B}'$ of $\textbf{B}$ which is isomorphic to $\textbf{B}$ with the property that the copies of $\textbf{A}$ in $\textbf{B}'$ take no more than $T_{\textbf{A}}$-many colours.

Of course, your property is slightly stronger since you're colouring all possible $n$-tuples rather than just the copies of a particular substructure $\textbf{A}$ of cardinality $n$. That said, not much is known even for the above version of the problem, but there are some positive results when $L$ consists of a single binary relation $R$. When $R$ is interpreted as a linear order then $\mathbb{N}$ has finite big Ramsey degrees by Ramsey's theorem, as you alluded to. $\mathbb{Q}$ with its usual order has finite big Ramsey degrees by a theorem of Denis Devlin (a proof of which can be found in Todorcevic's book Introduction to Ramsey Spaces). There are also known results in the case where $R$ is interpreted as an edge relation on a countably infinite graph. For instance, a paper of Laflamme, Sauer, and Vuksanovic shows that the Rado graph has finite Ramsey degrees, while a recent article of Dobrinen shows that the Henson graphs have finite big Ramsey degrees. The introduction of the latter paper also contains a nice overview of the literature on the subject.