Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Sharp phase transition thresholds for the Paris Harrington Ramsey numbers for a fixed dimension


Authors: Andreas Weiermann and Wim Van Hoof
Journal: Proc. Amer. Math. Soc. 140 (2012), 2913-2927
MSC (2010): Primary 03F30; Secondary 03D20, 03C62, 05D10
Published electronically: December 1, 2011
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This article is concerned with investigations on a phase transition which is related to the (finite) Ramsey theorem and the Paris-Harrington theorem. For a given number-theoretic function $ g$, let $ R^d_c(g)(k)$ be the least natural number $ R$ such that for all colourings $ P$ of the $ d$-element subsets of $ \{0,\ldots ,R-1\}$ with at most $ c$ colours there exists a subset $ H$ of $ \{0,\ldots ,R-1\}$ such that $ P$ has constant value on all $ d$-element subsets of $ H$ and such that the cardinality of $ H$ is not smaller than $ \max \{k,g(\min (H))\}$. If $ g$ is a constant function with value $ e$, then $ R^d_c(g)(k)$ is equal to the usual Ramsey number $ R^d_c(\max \{e,k\})$; and if $ g$ is the identity function, then $ R^d_c(g)(k)$ is the corresponding Paris-Harrington number, which typically is much larger than $ R^d_c(k)$. In this article we give for all $ d\geq 2$ a sharp classification of the functions $ g$ for which the function % latex2html id marker 308 $ m\mapsto R^d_m(g)(m)$ grows so quickly that it is no longer provably total in the subsystem of Peano arithmetic, where the induction scheme is restricted to formulas with at most $ (d-1)$-quantifiers. Such a quick growth will in particular happen for any function $ g$ growing at least as fast as % latex2html id marker 314 $ i\mapsto \varepsilon \cdot \underbrace {\log (\cdots (\log (}_{(d-1)-\mbox {times}}i)\cdots )$ (where $ \varepsilon >0$ is fixed) but not for the function $ g(i)=\frac {1}{\log ^*(i)}\cdot \underbrace {\log (\cdots (\log (}_{(d-1)-\mbox {times}}i)\cdots )$. (Here $ \log ^*$ denotes the functional inverse of the tower function.) To obtain such results and even sharper bounds we employ certain suitable transfinite iterations of nonconstructive lower bound functions for Ramsey numbers. Thereby we improve certain results from the article A classification of rapidly growing Ramsey numbers (PAMS 132 (2004), 553-561) of the first author, which were obtained by employing constructive ordinal partitions.


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


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03F30, 03D20, 03C62, 05D10

Retrieve articles in all journals with MSC (2010): 03F30, 03D20, 03C62, 05D10


Additional Information

Andreas Weiermann
Affiliation: Department of Mathematics, Ghent University, Krijgslaan 281 S22, B-9000 Ghent, Belgium
Email: Andreas.Weiermann@UGent.be

Wim Van Hoof
Affiliation: Department of Mathematics, Ghent University, Krijgslaan 281 S22, B-9000 Ghent, Belgium
Email: Wim.Vanhoof@UGent.be

DOI: http://dx.doi.org/10.1090/S0002-9939-2011-11121-3
PII: S 0002-9939(2011)11121-3
Keywords: Ramsey theorem, rapidly growing Ramsey functions, fast growing hierarchies, Peano arithmetic
Received by editor(s): May 16, 2008
Received by editor(s) in revised form: January 22, 2011, and March 4, 2011
Published electronically: December 1, 2011
Communicated by: Julia Knight
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.