The principle $RT^1_k$ states that given any partition of $\omega$ into $k$ parts, at least one part must be infinite. Of course, this is a very weak statement, and for every (standard) $k$ it is provable in the fragment $RCA_0$ of second-order arithmetic. In this sense, it is provable from every other principle one considers in reverse mathematics. If we move from proof theory to computability, and compare principles under computability-theoretic reducibilities rather than under provability over $RCA_0$, things become more interesting.

I will review several such reducibilities, focusing on strong computable (sc) and Weihrauch (W) reducibilities, and survey some examples. I will then outline a recent result (jointly with Patey, Solomon, and Westrick) that for $k > l$, $RT^1_k$ is not sc-reducible to $SRT^2_l$. This answers a question of Hirschfeldt and Jockusch. The proof is a forcing argument using the tree labeling method, a new technique of building homogeneous sets for stable colorings, which I will describe.