## Regressive functions on pairs

I recently gave a talk at the Claremont Colleges Algebra/Number Theory/Combinatorics Seminar on the topic of this paper, which can be found in my papers page.

For a set $X\subseteq{\mathbb N}^2$ let $X^{[2]}=\{(n,m)\in X^2:n. A function $f:X^{[2]}\to{\mathbb N}$ is regressive iff $f(u_1,u_2) for all $u_1 in $X$ with $0. A set $H\subseteq X$ is min-homogeneous for $f$ iff $f(u,u_1)=f(u,u_2)$ whenever $0 and $u,u_1,u_2\in H$.

Theorem. For all $n$ there exists $m$ such that if $X=\{1,2,\dots,m\}$ and $f:X^{[2]}\to{\mathbb N}$ is regressive, then there is $H\subseteq X$ of size at least $n$ and min-homogeneous for $f$.

The theorem (due to Kanamori and McAloon) states a version of the classical Ramsey theorem for regressive functions. We cannot expect $H$ to be homogeneous, i.e., in general $f\upharpoonright H^{[2]}$ will not be constant. For example, consider $f(u,v)=u-1$. Notice also that without loss of generality $1\in H$, since $f(1,u)=0$. It is natural to try to establish the rate of growth of the function $g$ that to each $n$ assigns the least $m$ as in the theorem. Using tools of mathematical logic, as part of a more general result about regressive functions of $k$ variables, Kanamori and McAloon showed:

Theorem. The function $g$ grows faster than any primitive recursive function.

In my paper I show using finite combinatorics methods that $g$ grows precisely as fast as Ackermann’s function. This is obtained as part of an analysis of a more general function $g(n,k)$ of two variables, defined as $g$ but with the additional requirement that ${\rm min}(H)\ge k$. Obviously, $g(2,k)=k+1$ and $g(3,k)=2k+1$. The situation for $g(4,k)$ is less clear, although it is of exponential growth.

Theorem. We have:

1. $g(4,1)=5$, $g(4,2)=15$, $g(4,3)=37$, $g(4,4)\le85$.
2. $2g(4,m)+3\le g(4,m+1)$, so $g(4,m)\ge 5\times 2^m-3$ for $m\ge3$.
3. $g(4,m+1)\le 2^m(m+2)-2^{m-1}+1$.

Question. Does $g(4,m)\ge 2^{m-1}m$ hold?

Although I have not been able to prove this, I do not expect it to be particularly difficult.