Sharp thresholds for hypergraph regressive Ramsey numbers

详细信息    查看全文

• 作者：Lorenzo Carlucci ; Gyesik Lee ; Andreas Weiermann
• 关键词：Regressive Ramsey Theorem ; Rapidly growing Ramsey functions ; Independence results ; Fast-growing hierarchies
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2011
• 出版时间：February 2011
• 年：2011
• 卷：118
• 期：2
• 页码：558-585
• 全文大小：335 K

文摘

The f-regressive Ramsey number is the minimum N such that every coloring of the d-tuples of an N-element set mapping each x₁,…,x_d to a color below f(x₁) (when f(x₁) 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.