ISSN:
1572-9273
Keywords:
05C55
;
06A10
;
62J
;
Regressions
;
Ramsey theory
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A regressive function (also called a regression or contractive mapping) on a partial order P is a function σ mapping P to itself such that σ(x)≤x. A monotone k-chain for σ is a k-chain on which σ is order-preserving; i.e., a chain x 1〈...〈xksuch that σ(x 1)≤...≤σ(xk). Let P nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x t(x,j−1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) 〈 f(K) 〈t(е + εk, k) , where εk → 0 as k→∞. Alternatively, the largest k such that every regression on P nis guaranteed to have a monotone k-chain lies between lg*(n) and lg*(n)−2, inclusive, where lg*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00337694
Permalink
