Regressive functions on pairs
type: Item
instance of: scholarly article
title: Regressive functions on pairs
zbMATH Open document ID: 1247.05255
author: Andrés Eduardo Caicedo
published in: European Journal of Combinatorics
publication date: 2010-04-27T00:00:00Z
full work available at URL: https://scholarworks.boisestate.edu/math_facpubs/13
review text: 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.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05D10
zbMATH DE Number: 5702075
zbMATH Keywords: regressive function
zbMATH Keywords: regressive Ramsey number
zbMATH Keywords: Ackermann's function
zbMATH Keywords: primitive recursive function
zbMATH Keywords: Ackermannian growth
zbMATH Keywords: min-homogeneous set
MaRDI profile type: Publication
OpenAlex ID: W1986884734
cites work: On regressive Ramsey numbers
cites work: Sharp thresholds for hypergraph regressive Ramsey numbers
cites work: Mathematical logic. A course with exercises. Part II. Recursion theory, Gödel's theorems, set theory, model theory. Translated from the 1993 French original by Donald H. Pelletier
cites work: Q3997075
cites work: On Gödel incompleteness and finite combinatorics
cites work: Sharp thresholds for the phase transition between primitive recursive and Ackermannian Ramsey numbers
cites work: Regressive Ramsey numbers are Ackermannian
cites work: Recursion and double recursion
DOI: 10.1016/J.EJC.2009.07.010
description: scientific article; zbMATH DE number 5702075