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.

  • $\begingroup$ 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. $\endgroup$ – Carl Mummert Apr 6 '15 at 11:45
  • 1
    $\begingroup$ @Pteromys: If this doesn't get answered eventually, you could always ask Hirschfeldt on MO. $\endgroup$ – Kyle Gannon Apr 6 '15 at 15:05
  • $\begingroup$ @CarlMummert I added it in the problem statement. $\endgroup$ – Pteromys Apr 6 '15 at 16:43
  • $\begingroup$ Thank you. I was confused at first because I thought the word "fact" was a direct quote from the preprint. $\endgroup$ – Carl Mummert Apr 6 '15 at 17:48

On page 17 of the linked paper, near the top, the authors write,

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.

I think it is worth pointing out that this issue of how it is possible to reduce the number of colors and/or the exponent in Ramsey's theorem is a very active area of research right now, related to Weihrauch redicibility. There are many subtleties in terms of "how uniform" of a reduction is requested, and the differences between the different types of reduction can be subtle.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.