Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Thin set theorems and cone avoidance
HTML articles powered by AMS MathViewer

by Peter Cholak and Ludovic Patey PDF
Trans. Amer. Math. Soc. 373 (2020), 2743-2773 Request permission

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

References
Similar Articles
  • Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03B30
  • Retrieve articles in all journals with MSC (2010): 03B30
Additional Information
  • 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)
  • © Copyright 2019 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 373 (2020), 2743-2773
  • MSC (2010): Primary 03B30
  • DOI: https://doi.org/10.1090/tran/7987
  • MathSciNet review: 4069232