## 496 – Regressive functions on pairs

[Updated September 4, 2009.]

(For background, see my paper Regressive functions on pairs, in my papers page.)

Here, ${{\mathbb N}=\{0,1,\dots\}.}$ For ${X\subseteq{\mathbb N},}$ we denote by ${X^{[2]}}$ the set of unordered pairs of elements of ${X.}$ We will use interval notation, with the understanding that our variables range over natural numbers so, for example, ${[3,6)=\{3,4,5\}.}$

Suppose that ${0\notin X.}$ A function ${f:X^{[2]}\rightarrow{\mathbb N}}$ is regressive iff ${f(t)<{\rm min}(t).}$ We will usually write ${f(a,b)}$ for ${f(\{a,b\})}$ with the understanding that ${a

A subset ${H\subseteq X}$ is min-homogeneous for ${f}$ iff whenever ${a are in ${H,}$ then ${f(a,b)=f(a,c).}$

Given ${0 denote by ${g(n)}$ the smallest integer ${N}$ such that whenever ${f:[n,N]^{[2]}\rightarrow{\mathbb N}}$ is regressive, there is a min-homogeneous set ${H\subset[n,N]}$ of size at least ${4.}$

We want to bound the function ${g(n)}$ as precisely as possible.

Here are some exact values and bounds:

• ${g(1)=5.}$
• ${g(2)=15.}$
• ${g(3)=37.}$
• ${g(n)\le 2^{n-1}(n+7)-3.}$
(In the paper, I prove the weaker bound ${g(n)\le 2^n n+12\cdot 2^{n-3}+1}$ for ${n\ge3.}$)
• ${g(n+1)\ge 2g(n)+3.}$

I will be modifying the table above if additional results are found.

Typeset using LaTeX2WP.