A characterisation of posets that are nearly antichains
type: Item
instance of: scholarly article
title: A characterisation of posets that are nearly antichains
zbMATH Open document ID: 1060.06002
author: Siaw-Lynn Ng
published in: Order
publication date: 2005-02-25T00:00:00Z
review text: Let \(P=(P,\leq )\) be a finite \(n\)-element poset. If \(k\) is a non-negative integer, then a \(k\)-labelling of \(P\) is an injective function \(f:P\rightarrow \{1,\dots,n\}\) such that \(f(a)<f(b)\) if \(a<b\), and \(| f(a)-f(b)| \leq k\) if \(a\) and \(b\) are incomparable. The linear discrepancy ld\((P)\) of \(P\) is the least \(k\) for which there exists a \(k\)-linear labelling of \(P\). Then \(0\leq \text{ld}(P)\leq n-1\), and ld\((P)=0\) iff \(P\) is a chain, and ld\((P)=n-1\) iff \(P\) is an antichain. In the paper, posets \(P\) with ld\((P)=n-2\) are characterized.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 2138853
zbMATH Keywords: poset
zbMATH Keywords: linear discrepancy
zbMATH Keywords: antichain
reviewed by: Jiří Rachůnek
MaRDI profile type: Publication
full work available at URL: s11083-004-3984-x
OpenAlex ID: W2043708087
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Linear discrepancy and weak discrepancy of partially ordered sets
cites work: Linear discrepancy and bandwidth
cites work: Linear discrepancy of the product of two chains
cites work: The dimension of semiorders
DOI: 10.1007/S11083-004-3984-X
description: scientific article; zbMATH DE number 2138853