On the logical strengths of partial solutions to mathematical problems

We use the framework of reverse mathematics to address the question of, given a mathematical problem, whether or not it is easier to find an infinite partial solution than it is to find a complete solution. Following Flood [Reverse mathematics and a Ramsey-type Konig's lemma, J. Symb. Log. 77 (2012) 12721280], we say that a Ramsey-type variant of a problem is the problem with the same instances but whose solutions are the infinite partial solutions to the original problem. We study Ramsey-type variants of problems related to Konig's lemma, such as restrictions of Konig's lemma, Boolean satisfiability problems and graph coloring problems. We find that sometimes the Ramsey-type variant of a problem is strictly easier than the original problem (as Flood showed with weak Konig's lemma) and that sometimes the Ramsey-type variant of a problem is equivalent to the original problem. We show that the Ramsey-type variant of weak Konig's lemma is robust in the sense of Montalban [Open questions in reverse mathematics, Bull. Symb. Log. 17 (2011) 431454]: it is equivalent to several perturbations. We also clarify the relationship between Ramsey-type weak Konig's lemma and algorithmic randomness by showing that Ramsey-type weak weak Konig's lemma is equivalent to the problem of finding diagonally non-recursive functions and that these problems are strictly easier than Ramsey-type weak Konig's lemma. This answers a question of Flood