The reverse mathematics of bounded Ramsey’s theorem for pairs

In this article, we study a degenerate version of Ramsey’s theorem for pairs and two colors (\( \mathsf{RT}^2_2 \)), in which the homogeneous sets for color \(1\) are of bounded size. By \( \mathsf{RT}^2_2 \), it follows that every such coloring admits an infinite homogeneous set for color 0. This statement, called \( \mathsf{BRT}^2_2 \), is known to be computably true, that is, every computable instance admits a computable solution, but the known proofs use \( \Sigma^0_2 \)-induction (\(\mathsf{I}\Sigma^0_2\)). We prove that \( \mathsf{BRT}^2_2 \) follows from the Erd\H{o}s-Moser theorem but not from the Ascending Descending sequence principle, and that its computably true version is equivalent to \(\mathsf{I}\Sigma^0_2\) over \( \mathsf{RCA}_0 \).

Recommended citation: Q. Le Houérou and L. Patey (2025). "The reverse mathematics of bounded Ramsey's theorem for pairs."
Download Paper