   ISSN 1088-6850(online) ISSN 0002-9947(print)

Thin set theorems and cone avoidance

Authors: Peter Cholak and Ludovic Patey
Journal: Trans. Amer. Math. Soc. 373 (2020), 2743-2773
MSC (2010): Primary 03B30
DOI: https://doi.org/10.1090/tran/7987
Published electronically: January 7, 2020
MathSciNet review: 4069232
Full-text PDF

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$.

[Enhancements On Off] (What's this?)

References

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03B30

Retrieve articles in all journals with MSC (2010): 03B30

Peter Cholak
Affiliation: Department of Mathematics, University of Notre Dame, Notre Dame, Indiana, 46556
MR Author ID: 290865
ORCID: 0000-0002-6547-5408
Email: Peter.Cholak.1@nd.edu

Ludovic Patey
Affiliation: Institut Camille Jordan, Université Claude Bernard Lyon 1, 43 boulevard du 11 novembre 1918, F-69622 Villeurbanne Cedex, France
MR Author ID: 1102703
ORCID: 0000-0002-0304-7926
Email: ludovic.patey@computability.fr

Received by editor(s): December 3, 2018
Received by editor(s) in revised form: March 15, 2019, August 19, 2019, and August 29, 2019
Published electronically: January 7, 2020
Additional Notes: The first author was partially supported by a grant from the Simons Foundation (#315283) and NSF Conference grants (DMS-1640836 and DMS-1822193)