[Updated September 4, 2009.]
(For background, see my paper Regressive functions on pairs, in my papers page.)
Here, For we denote by the set of unordered pairs of elements of We will use interval notation, with the understanding that our variables range over natural numbers so, for example,
Suppose that A function is regressive iff We will usually write for with the understanding that
A subset is minhomogeneous for iff whenever are in then
Given denote by the smallest integer such that whenever is regressive, there is a minhomogeneous set of size at least
We want to bound the function as precisely as possible.
Here are some exact values and bounds:

(In the paper, I prove the weaker bound for )
I will be modifying the table above if additional results are found.
Typeset using LaTeX2WP.