Sharp thresholds for hypergraph regressive Ramsey numbers

摘要

The f-regressive Ramsey number R_~(reg)_f (d,n)| is the minimum N such that every coloring of the d-tuples of an N-element set mapping each x_1,...,x_d to a color below f(x_1) (when f(x_1) is positive) contains a min-homogeneous set of size n, where a set is called min-homogeneous if every two d-tuples from this set that have the same smallest element get the same color. If f is the identity, then we are dealing with the standard regressive Ramsey numbers as defined by Kanamori and McAloon. The existence of such numbers for hypergraphs or arbitrary dimension is unprovable from the axioms of Peano Arithmetic. In this paper we classify the growth-rate of the regressive Ramsey numbers for hypergraphs in dependence of the growth-rate of the parameter function f. We give a sharp classification of the thresholds at which the f-regressive Ramsey numbers undergo a drastical change in growth-rate. The growth-rate has to be measured against a scale of fast-growing recursive functions indexed by finite towers of exponentiation in base [omega] (the first limit ordinal). The case of graphs has been treated by Lee, Kojman, Omri and Weiermann. We extend their results to hypergraphs of arbitrary dimension. From the point of view of Logic, our results classify the provability of the Regressive Ramsey Theorem for hypergraphs of fixed dimension in subsystems of Peano Arithmetic with restricted induction principles.