On \(k\)-weak orders: Recognition and a tolerance result (Q1381859)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On \(k\)-weak orders: Recognition and a tolerance result |
scientific article |
Statements
On \(k\)-weak orders: Recognition and a tolerance result (English)
0 references
1 June 1998
0 references
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.
0 references
\(k\)-leveling function
0 references
\(k\)-weak posets
0 references
polynomial time algorithm
0 references
bitolerance posets
0 references