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 x1<...<xksuch that σ(x1)≤...≤σ(xk). Let Pnbe 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 Pnhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=xt(x,j-1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t(ye{cyrillic} + εk, k), where εk → 0 as k→∞. Alternatively, the largest k such that every regression on Pnis 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.
Original language | English (US) |
---|---|
Pages (from-to) | 155-164 |
Number of pages | 10 |
Journal | Order |
Volume | 4 |
Issue number | 2 |
DOIs | |
State | Published - Jun 1987 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Algebra and Number Theory
- Geometry and Topology
- Computational Theory and Mathematics
Keywords
- AMS subject classifications (1980): 05C55, 06A10, 62J
- Ramsey theory
- Regressions