SHARP PHASE TRANSITION THRESHOLDS FOR THE PARIS HARRINGTON RAMSEY NUMBERS FOR A FIXED DIMENSION

摘要

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_c~d(g)(k) be the least natural number R such that for all colourings P of the d-element subsets of {0,... , R - 1} with at most c colours there exists a subset H of {0, , 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_c~d(g)(k) is equal to the usual Ramsey number R_c~d(max{e, k}); and if g is the identity function, then R_c~d(g)(k) is the corresponding Paris-Harrington number, which typically is much larger than R_c~d(k). In this article we give for all d ≥ 2 a sharp classification of the functions g for which the function m → 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. Such a quick growth will in particular happen for any function g growing at least as fast as i → ε ? log(…(log(i)…) (where ε > 0 is fixed) but not for the function (d-1)-times g(i) = 1/(log~*(i)) ? log(… (log(i)…). (Here log~* denotes the functional inverse (d-1)—times 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.