Ann Trenk (Wellesley College and Cornell University)
In this talk, we discuss criteria for assigning integer ranks to elements of a partially ordered set. In particular, we wish to assign ranks that respect the order of the poset and minimize the discrepancy ranks given to incomparable elements.
The linear discrepancy of an ordered set P = (X, <) is the least integer k for which there exists a 1-1 function f from the ground set X to the integers satisfying:
(i) If x < y in P then f(x) < f(y), and
(ii) If x is incomparable to y in P then |f(x) - f(y)| <= k.
A related concept is the bandwidth of a graph. The bandwidth of a graph G = (V,E) is the smallest integer k for which there exists a 1-1 function from the vertex set V to the integers that satisfies:
(ii') |f(x) - f(y)| <= k for each edge xy in E.
It follows from the definitions that the linear discrepancy of P is at least as large as bandwidth(G), where G is the incomparability graph of P. We prove that these quantites are in fact equal.
This is joint work with Peter Fishburn and Paul Tanenbaum.