Linear discrepancy of the product of two chains

Abstract

The linear discrepancy of a partially ordered set P = (X, <) is the minimum integer l such that vertical bar(a) - f(b)vertical bar <= l for any injective isotone f : P -> Z and any pair of incomparable elements a, b in X. It measures the degree of difference of P from a chain. Despite of increasing demands to the applications, the discrepancies of just few simple partially ordered sets are known. In this paper, we obtain the linear discrepancy of the product of two chains. For this, we firstly give a lower bound of the linear discrepancy and then we construct injective isotones on the product of two chains, which show that the obtained lower bound is tight.