## 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}<...<x_{k}such that σ(x_{1})≤...≤σ(x_{k}). Let P_{n}be 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_{n}has 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(ye{cyrillic} + ε_{k}, k), where ε_{k} → 0 as k→∞. Alternatively, the largest k such that every regression on P_{n}is 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 1 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