Paths, trees, and the computational strength of some Ramsey-type theorems.

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 Kšnig'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 Erdő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 other than 2. When n=2, we show that it implies Ramsey's Theorem, and that it does not imply ACA.

We next introduce a new combinatorial principle, called RKL, which combines features of Weak Kšnig's Lemma and Ramsey's Theorem. We show that this principle is strictly weaker than both WKL and RT22, and that it is strictly stronger than RCA. 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 WKL.