Regressions and monotone chains II: The poset of integer intervals

Noga Alon, W. T. Trotter, Douglas B. West

Research output: Contribution to journalArticlepeer-review


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 languageEnglish (US)
Pages (from-to)155-164
Number of pages10
Issue number2
StatePublished - Jun 1 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Geometry and Topology
  • Computational Theory and Mathematics


  • AMS subject classifications (1980): 05C55, 06A10, 62J
  • Ramsey theory
  • Regressions


Dive into the research topics of 'Regressions and monotone chains II: The poset of integer intervals'. Together they form a unique fingerprint.

Cite this