On the Weakness of an Ordered Set
John Gimbel, Ann N. Trenk · SIAM Journal on Discrete Mathematics · 1998
In this paper we extend the notion of a ranking of elements in a weak order to a ranking of elements in general ordered sets. The weakness of an ordered set P = (X,\prec) (denoted wk(P)) is the minimum integer k for which there exists an integer-valued function lev: X \to Z satisfying: (i) if x \prec y, then lev(x) < lev(y); and (ii) if x || y, then |lev(x) - lev(y)| \le k (where "||" denotes incomparability). A forcing cycleL in P is a sequence of elements L: x=v 0 , v 1 , . . ., v m = x of P so that for each i \in {0,1, . . ., m-1} either v i \prec v i +1 or v i || v i +1. Our main result relates these two concepts; we prove wk(P) = max L \llceil\frac{up(L)}{side(L)}\rrceil$, where up(L) = #{i : v i \prec v i +1}, side(L) = #{i : v i || v i +1} and the maximum is taken over all forcing cycles L in P. We also discuss algorithms for computing wk(P) and prove that wk(P) is a comparability invariant.