THE LINEAR DISCREPANCY OF A PRODUCT OF TWO POSETS

Abstract

For a poset P = (X, <= p), the linear discrepancy of P is the minimum value of maximal differences of all incomparable elements for all possible labelings. In this paper, we find a lower bound and an upper bound of the linear discrepancy of a product of two posets. In order to give a lower bound, we use the known result, ld(m x n) = [mm/2] - 2. Next, we use Dilworth's chain decomposition to obtain an upper bound of the linear discrepancy of a product of a poset and a chain. Finally, we give an example touching this upper bound.