Thin set theorems and cone avoidance

Abstract:

The thin set theorem $\operatorname {\mathsf {RT}}^n_{<\infty ,\ell }$ asserts the existence, for every $k$-coloring of the subsets of natural numbers of size $n$, of an infinite set of natural numbers, all of whose subsets of size $n$ use at most $\ell$ colors. Whenever $\ell = 1$, the statement corresponds to Ramsey’s theorem. From a computational viewpoint, the thin set theorem admits a threshold phenomenon, in that whenever the number of colors $\ell$ is sufficiently large with respect to the size $n$ of the tuples, the thin set theorem admits strong cone avoidance.

Let $d_0, d_1, \dots$ be the sequence of Catalan numbers. For $n \geq 1$, $\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$ admits strong cone avoidance if and only if $\ell \geq d_n$ and cone avoidance if and only if $\ell \geq d_{n-1}$. We say that a set $A$ is $\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$-encodable if there is an instance of $\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$ such that every solution computes $A$. The $\operatorname {\mathsf {RT}}^n_{<\infty , \ell }$-encodable sets are precisely the hyperarithmetic sets if and only if $\ell < 2^{n-1}$, the arithmetic sets if and only if $2^{n-1} \leq \ell < d_n$, and the computable sets if and only if $d_n \leq \ell$.