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

The paper is devoted to the study of phase transition which is related to the (finite) Ramsey theorem and the Paris-Harrington theorem. Let \(g\) be a given number-theoretic function and let \(R_{c}^{d}(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))\}\). In the paper under review a sharp classification is given for the functions \(g\) for which the function \(m \longmapsto R_{m}^{d}(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 (for all \(d \geq 2\)). To obtain the results, certain suitable transfinite iterations of nonconstructive lower bound functions for Ramsey numbers are employed. The present results improve certain results from the first author's paper [Proc. Am. Math. Soc. 132, No. 2, 553--561 (2004; Zbl 1041.03044)].