Abstract
The linear discrepancy of a partially ordered set P = (X, ≺) is the minimum integer l such that ∣f(a) − f(b)∣ ≤ l for any injective isotone \( f:P \to \mathbb{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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Tanenbaum, P., Trenk, A. and Fishburn, P.: Linear discrepancy and weak discrepancy of partially ordered sets, Order 18 (2001), 201–225.
Fishburn, P., Tanenbaum, P. and Trenk, A.: Linear discrepancy and bandwidth, Order 18 (2001), 237–245.
Trotter, W.: Combinatorics and Partially Ordered Sets: Dimension Theory, Johns Hopkins University Press, Baltimore.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hong, S., Hyun, JY., Kim, H.K. et al. Linear Discrepancy of the Product of Two Chains. Order 22, 63–72 (2005). https://doi.org/10.1007/s11083-005-9006-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-005-9006-9