Regressions and monotone chains: A Ramsey-type extremal problem for partial orders
type: Item
instance of: scholarly article
title: Regressions and monotone chains: A Ramsey-type extremal problem for partial orders
zbMATH Open document ID: 0541.05045
DOI: 10.1007/BF02579164
author: Douglas B. West
author: William T. Trotter
author: G. W. Peck
author: Peter W. Shor
published in: Combinatorica
publication date: 1984-01-01T00:00:00Z
review text: \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.\)
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3859169
zbMATH Keywords: regression chains
zbMATH Keywords: Ramsey-type extremal problem
MaRDI profile type: Publication
cites work: Combinatorial theorems on contractive mappings in power sets
cites work: A theorem on chains of finite sets, II
full work available at URL: https://doi.org/10.1007/bf02579164
OpenAlex ID: W2078040594
description: scientific article; zbMATH DE number 3859169