# How to computably reduce the number of colors in (infinite) Ramsey's theorem

Suppose we have an "oracle" that gives a homogeneous set for a 2-coloring $\hat c : [\omega]^2 \rightarrow 2$ of pairs of integers. Using this oracle, can we "compute" a homogeneous set for a 3-coloring $c : [\omega]^2\rightarrow 3$ for pairs of integers? The answer is an obvious yes - you can use the oracle twice to do that. But what if we are allowed to use the oracle only once?

More technically, for every 3-coloring $c : [\omega]^2 \rightarrow 3$, does there exist a 2-coloring $\hat c : [\omega]^2\rightarrow 2$, computable from $c$, such that for any homogeneous set $\hat H$ for $\hat c$ there exists a homogeneous set $H$ for $c$ computable from $\hat H$ and $c$?

Background : It is a "fact", supposedly easy to prove, stated in a paper by Hirschfeldt and Jockusch, that such $\hat c$ exists. Addendum It's at the bottom of page 34.

• Could you mention where in the linked paper this claim is made? It is a subtle issue, because it is known from a result of Dorais, Dzhafarov, Hirst, Mileti, and Shafer that the construction cannot be uniform in a particular sense. – Carl Mummert Apr 6 '15 at 11:45
• @Pteromys: If this doesn't get answered eventually, you could always ask Hirschfeldt on MO. – Kyle Gannon Apr 6 '15 at 15:05
• @CarlMummert I added it in the problem statement. – Pteromys Apr 6 '15 at 16:43
• Thank you. I was confused at first because I thought the word "fact" was a direct quote from the preprint. – Carl Mummert Apr 6 '15 at 17:48

During the final stages of preparation of this paper, we were informed that in his upcoming paper [40], Patey has proved the stronger result that $RT^n_k \not \leq_c RT^n_j$ for all $n \geq 2$ and $k > j \geq 2$ (with a proof considerably more involved than the one we give for our weaker result).
Clearly, Patey's result as stated there would imply $RT^n_3 \not \leq_c RT^n_2$ for $n \geq 2$. Therefore, there is a typo in the following claim on page 34:
For example, consider $RT^n_3$ and $RT^n_2$. While $RT^n_3 \leq_c RT^n_2$, we have seen in Theorem 3.3 that $RT^n_3 \not\leq_u RT^n_2$.
I suspect the authors meant to say that $RT^n_3 \leq_\omega RT^n_2$, which is to say that every $\omega$-model of $RT^n_2$ is an model of $RT^n_3$. That is an easy fact, because in that context we can apply $RT^n_2$ more than once.