| An industry has arisen dedicated to the study of the interplay between combinatorial principles and computational strength. In particular, much work has been done on theorems similar to Ramsey's Theorem and to Weak Konig's Lemma. We study two related principles, which are interesting both for their combinatorial form and for their computational content.;We begin by studying the computational strength of a version of Ramsey's Theorem that combines features of finite and infinite Ramsey theory. Paul Erdo&huml;s and Fred Galvin proved that for each coloring f, there is an infinite set that is "packed together" which is given "a small number" of colors by f. We show that this theorem is close in computational strength to standard Ramsey's Theorem, giving arithmetical bounds for solutions to computable instances. In reverse mathematics, we show that that this Packed Ramsey's Theorem is equivalent to Ramsey's Theorem for exponents n ≠ 2. When n = 2, we show that it implies Ramsey's Theorem, and that it does not imply ACA 0.;We next introduce a new combinatorial principle, called RKL, which combines features of Weak Konig's Lemma and Ramsey's Theorem. We show that this principle is strictly weaker than both WKL0 and RT22, and that it is strictly stronger than RCA0. We also consider two generalizations of this principle. We obtain the surprising result that these stronger principles are closer in strength to RT22 than they are to WKL0. |
