Linear discrepancy of the product of two chains
SCIE
SCOPUS
- Title
- Linear discrepancy of the product of two chains
- Authors
- Hong, SP; Hyun, JY; Kim, HK; Kim, SM
- Date Issued
- 2005-02
- Publisher
- SPRINGER
- 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.
- Keywords
- linear discrepancy; linear extension of a poset
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/29606
- DOI
- 10.1007/s11083-005-9006-9
- ISSN
- 0167-8094
- Article Type
- Article
- Citation
- ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, vol. 22, no. 1, page. 63 - 72, 2005-02
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.