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 let . A function is regressive iff for all in with . A set is min-homogeneous for iff whenever and .
Theorem. For all there exists such that if and is regressive, then there is of size at least and min-homogeneous for .
The theorem (due to Kanamori and McAloon) states a version of the classical Ramsey theorem for regressive functions. We cannot expect to be homogeneous, i.e., in general will not be constant. For example, consider . Notice also that without loss of generality , since . It is natural to try to establish the rate of growth of the function that to each assigns the least as in the theorem. Using tools of mathematical logic, as part of a more general result about regressive functions of variables, Kanamori and McAloon showed:
Theorem. The function grows faster than any primitive recursive function.
In my paper I show using finite combinatorics methods that grows precisely as fast as Ackermann’s function. This is obtained as part of an analysis of a more general function of two variables, defined as but with the additional requirement that . Obviously, and . The situation for is less clear, although it is of exponential growth.
Theorem. We have:
- , , , .
- , so for .
Question. Does hold?
Although I have not been able to prove this, I do not expect it to be particularly difficult.