Regressions and monotone chains. II: the poset of integer intervals (Q1090686)

[For part I see \textit{D. B. West, W. T. Trotter} jun., \textit{G. W. Peck} and \textit{P. Shor}, Combinatorica 4, 117-119 (1984; Zbl 0541.05045).] A regressive function (also called a regression or contractive mapping) on a partial order P is a function \(\sigma\) mapping P to itself such that \(\sigma\) (x)\(\leq x\). A monotone k-chain for \(\sigma\) is a k-chain on which \(\sigma\) is order-preserving, i.e., a chain \(x_ 1<...<x_ k\) such that \(\sigma (x_ 1)\leq...\leq \sigma (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(e+\epsilon_ k,k)\), where \(\epsilon_ k\to 0\) as \(k\to \infty\). 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 applications 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.