Regressive functions on pairs (Q966137): Difference between revisions

Let \([l,m]=\{l,l+1,\ldots ,m\}\) and \(X^{[k]}\) be the collection of \(k\)-sized subsets of \(X\). A function \(f: X^{[k]}\rightarrow N\) is called regressive if \(f(s)< \min (s)\) whenever \(s\in X^{[k]}\) and \(\min (s)>0\). For such an \(f\), a subset \(H\subseteq X\) is called min-homogeneous for \(f\) if \(0\notin H\) and, whenever \(s,t\in H^{[k]}\) and \(\min (s)= \min (t)\), then \(f(s)=f(t)\). The two-variable function \(g(n,m)\) is defined as the least \(l\) such that any regressive function \(f: [m,l]^{[2]}\rightarrow [0,l-2]\) admits a min-homogeneous set of size \(n\) and \(G(n,m)\) is the least \(l\) such that for any regressive \(f: [m,l]^{[2]}\rightarrow [0,l-2]\), there is a min-homogeneous set for \(f\) of size \(n\) whose minimum element is \(m\) (in the paper it is shown that this function is well defined). In the literature, the values of \(g\) (more precisely, the values of \(g(\cdot ,2)\)) are referred to as ``regressive Ramsey numbers''. In this paper it is shown by combinatorial arguments, that \(g(4,3)=37\), \(g(4,4)\leq 85\), \(g(5,2)\leq 41\times 2^{37}-1\), \(G(4,m)=2^{m}(m+2)-1\) and for all \(n\), there is a constant \(c_n\) such that \(G(n,m)<A_{n-1}(c_{n}m)\) for almost all \(m\). Here, \(A_n=A(n,\cdot)\), where \(A\) is Ackermann's function. Also, \(g(n,m)\geq A_{n-1}(m-1)\) holds for all \(n\geq 2\). These results also establish the rate of growth of the function \(g(n,\cdot)\) as being precisely that of the \((n-1)\)st level of the Ackermann hierarchy of fast growing functions.