On \(k\)-weak orders: Recognition and a tolerance result (Q1381859)

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.