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
    0 references

    Identifiers