Sharp thresholds for the phase transition between primitive recursive

Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey number. (Combinatorial Theory 2008)

Menachem Kojman, Gyesik Lee, Eran Omri, Andreas Weiermann.

Journal of Combinatorial Theory, Series A, 115(6):1036–1055

Abstract

We compute the sharp thresholds on g at which g-large and g-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian.

We also identify the threshold below which g-regressive colorings have usual Ramsey numbers, that is, admit homogeneous, rather than just min-homogeneous sets.