• Calendar

November 14, Wednesday
12:00 – 14:00

For a function g from natural numbers to natural numbers, a g-regressive coloring of pairs of natural numbers is a coloring C satisfying $C(m,n) \le g(\min{m,n})$ for all $m,n$.

The g-regressive Ramsey number of k is the least N so that for every g-regressive coloring C there exists a subset H of of size at least k which is min-homogeneous for C, namely, the color $C(m,n)$ of a pair ${m,n}$ of H depends only on $\min(m,n)$.

We compute a sharp threshold on g at which g-regressive Ramsey numbers cease to be primitive recursive and become Ackermannian. We prove:

Suppose g is nondecreasing and unbounded. Then the g-regressive Ramsey number is bounded by some primitive recursive function in k if and only if for every $t>0$ there is some $M(t)$ so that for all $n \ge M(t)$, $g(n) < n^{1/t}$ and $M(t)$ is primitive recursive in t.

We also give an extremely large lower bound on the identity-regressive Ramsey number of k=82. Joint work with Menachem Kojman, Gyesik Lee and Andreas Weiermann.