Record number :

1531587

Title of article :

Sharp thresholds for hypergraph regressive Ramsey numbers

Author/Authors :

Carlucci، نويسنده , , Lorenzo and Lee، نويسنده , , Gyesik and Weiermann، نويسنده , , Andreas، نويسنده ,

Issue Information :

روزنامه با شماره پیاپی سال 2011

Pages :

28

From page :

558

To page :

585

Abstract :

The f-regressive Ramsey number R f reg ( 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 ω (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.

Keywords :

Regressive Ramsey Theorem , Rapidly growing Ramsey functions , Fast-growing hierarchies , Independence results

Journal title :

Journal of Combinatorial Theory Series A

Serial Year :

2011

Link To Document :