The Weakness of an Ordered Set:
advice to your dean on how to pay faculty fairly

Ann Trenk, Wellesley College

Abstract: We extend the notion of a ranking of elements in a weak order to a ranking of elements in general ordered sets.

An ordered set P is k-weak if there exists an integer-valued function lev: X --> Z satisfying
(i) if x < y in P then lev(x) < lev(y), and
(ii) if x and y are incomparable in P then |lev(x) - lev(y)| <= k.

The weakness of an ordered set P is the minimum k for which P is k-weak. A forcing loop L in P is a sequence of elements of P x_1, x_2, x_3, ... ,x_n where x_1=x_n and for each i either x_i < x_{i+1} or x_i and x_{i+1} are incomparable in P.

In this talk we give polynomial-time algorithms for recognizing k-weak orders and for computing the weakness of an ordered set. We also present a result that relates weakness to forcing loops.