On \(k\)-weak orders: Recognition and a tolerance result
type: Item
instance of: scholarly article
title: On \(k\)-weak orders: Recognition and a tolerance result
zbMATH Open document ID: 0895.06001
DOI: 10.1016/S0012-365X(97)00038-1
published in: Discrete Mathematics
publication date: 1998-06-01T00:00:00Z
review text: Given a poset \(P= (X,<)\), an integer valued function lev: \(X\to Z\) is a \(k\)-leveling function of \(P\) if it is strictly order preserving, i.e., \(x<y\) implies \(\text{lev} (x)< \text{lev} (y)\), while if \(x\) and \(y\) are incomparable (parallel, free) then \(| \text{lev} (x)-\text{lev} (y) | <k\). If such a function is also an injection, then \(k\) is a controller of the maximum size of an antichain if it is minimal under these circumstances and it is also correlated with such parameters of posets as jump number, etc. The author provides a polynomial time algorithm for recognizing when a poset is \(k\)-weak, i.e., when it has a \(k\)-leveling function. Taking advantage of the structure of the correctness proof of the algorithm, she is able to make progress towards partial characterization of \(k\)-weak posets, more so in the special case that \(k=1\), when the shows that bounded bitolerance posets are also totally bounded.
reviewed by: J. Neggers
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1135967
zbMATH Keywords: \(k\)-leveling function
zbMATH Keywords: \(k\)-weak posets
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: bitolerance posets
author: Ann Trenk
MaRDI profile type: Publication
cites work: Proper and unit tolerance graphs
cites work: Tolerance orders and bipartite unit tolerance graphs
cites work: Q3335786
cites work: Bipartite tolerance orders
cites work: Q4281627
cites work: On the Weakness of an Ordered Set
cites work: Q3328583
cites work: Q3322150
cites work: Tolerance graphs
cites work: General results on tolerance intersection graphs
cites work: A recognition algorithm for orders of interval dimension two
cites work: Foundational aspects of theories of measurement
cites work: Q4004146
description: scientific article; zbMATH DE number 1135967