Regressions and monotone chains: A Ramsey-type extremal problem for partial orders (Q794668): Difference between revisions

\textit{R. Rado} [Acta Arith. 18, 257-261 (1971; Zbl 0227.05006)] generalizing a previous result of \textit{E. Harzheim} [Discrete Math. 40, 193-201 (1982; Zbl 0486.05007)] showed that for n large enough and every function \(f:\quad 2^ n\to 2^ n\) with \(f(X)\subset X\) there exists a chain \(X_ 1\subset X_ 2\subset...\subset X_ k\) such that also \(f(X_ 1)\subset f(X_ 2)\subset...\subset f(X_ k).\) Subsequently Leeb suggested to investigate analogous phenomena for arbitrary posets. A (w,k)-poset is a poset of width \(\leq w\) admitting a regression with no monotone \(k+1\)-chain. The authors study f(w,k), the least number such that there is no (w,k)-poset with that many elements. This number can be determined. In fact, Theorem: \(f(w,k)=(w+1)^ k.\)