Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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

Request Permissions   Purchase Content 
 

 

A packed Ramsey's theorem and computability theory


Author: Stephen Flood
Journal: Trans. Amer. Math. Soc. 367 (2015), 4957-4982
MSC (2010): Primary 03D80
DOI: https://doi.org/10.1090/S0002-9947-2015-06164-9
Published electronically: February 3, 2015
MathSciNet review: 3335406
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Ramsey's theorem states that each coloring has an infinite homogeneous set, but these sets can be arbitrarily spread out. Paul Erdős and Fred Galvin proved that for each coloring $ f$, there is an infinite set that is ``packed together'' which is given ``a small number'' of colors by $ f$.

We analyze the strength of this theorem from the perspective of computability theory and reverse mathematics. We show that this theorem is close in computational strength to the standard Ramsey's theorem by giving arithmetical upper and lower bounds for solutions to computable instances. In reverse mathematics, we show that that this packed Ramsey's theorem is equivalent to Ramsey's theorem for exponents $ n\neq 2$. When $ n=2$, we show that it implies Ramsey's theorem and that it does not imply $ \mathsf {ACA}_0$.


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


Similar Articles

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

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


Additional Information

Stephen Flood
Affiliation: Department of Mathematics, Pennsylvania State University, McAllister Building, University Park, Pennsylvania 16802
Address at time of publication: Department of Mathematics, University of Connecticut, Waterbury Campus, 99 East Main Street, Waterbury, Connecticut 06702
Email: sflood@alumni.nd.edu

DOI: https://doi.org/10.1090/S0002-9947-2015-06164-9
Keywords: Ramsey's theorem, computability theory, reverse mathematics
Received by editor(s): July 20, 2012
Received by editor(s) in revised form: February 8, 2013, and April 26, 2013
Published electronically: February 3, 2015
Additional Notes: The author was partially supported by EMSW21-RTG 0353748, 0739007, and 0838506.
Article copyright: © Copyright 2015 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.