Ramsey’s theorem states that for any coloring of then-element subsets of ℕ with finitely many colors, there is an infinite setHsuch that alln-element subsets ofHhave the same color. The strength of consequences of Ramsey’s theorem has been extensively studied in reverse mathematics and under various reducibilities, namely, computable reducibility and uniform reducibility. Our understanding of the combinatorics of Ramsey’s theorem and its consequences has been greatly improved over the past decades. In this paper, we state some questions which naturally arose (...) during this study. The inability to answer those questions reveals some gaps in our understanding of the combinatorics of Ramsey’s theorem. (shrink)

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω (...) with its set of predecessors, so n = {0, 1, 2, …, n − 1}. (shrink)

In this paper, we propose a weak regularity principle which is similar to both weak König's lemma and Ramsey's theorem. We begin by studying the computational strength of this principle in the context of reverse mathematics. We then analyze different ways of generalizing this principle.

We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for ${\Sigma^0_2}$ formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs.

We study the reverse mathematics of pigeonhole principles for finite powers of the ordinal $\omega$ . Four natural formulations are presented, and their relative strengths are compared. In the analysis of the pigeonhole principle for $\omega^{2}$ , we uncover two weak variants of Ramsey’s theorem for pairs.