# Strong reductions between combinatorial problems

## Speaker:

## Institution:

## Time:

## Host:

## Location:

I will discuss recent investigations of various reducibility notions between Pi^1_2 principles of second-order arithmetic, the most familiar of which is implication over the subsystem RCA_0. In many cases, such an implication is actually due to a considerably stronger reduction holding, such as a uniform (a.k.a. Weihrauch) reduction. (Here, we say a principle P is uniformly reducible to a principle Q if there are fixed reduction procedures Phi and Gamma such that for every instance A of P, Phi(A) is an instance of Q, and for every solution S to Phi(A), Gamma(A + S) is a solution to A.) As an example, nearly all the implications between principles lying below Ramsey's theorem for pairs are uniform reductions. In general, the study of when such stronger implications hold and when they do not gives a finer way of calibrating the relative strength of mathematical propositions, and has led to the development of a number of new forcing techniques for constructing models of second-order arithmetic with prescribed combinatorial properties. In addition, this analysis sheds light on several open questions from reverse mathematics, including that of whether the stable form of Ramsey's theorem for pairs (SRT^2_2) implies the cohesive principle (COH) in \omega (standard) models of RCA_0.