The linear discrepancy of a product of two posets
0
조회
0
다운로드
1
인용
0
참고문헌
키워드
초록
For a poset $P=(X, \le_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(\mathbf{m} \times \mathbf{n}) = \left\lceil \frac{mn}{2} \right\rceil -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.
Abstract
For a poset $P=(X, \le_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(\mathbf{m} \times \mathbf{n}) = \left\lceil \frac{mn}{2} \right\rceil -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.
참고문헌 (9)
- 채갑병, "THE LINEAR DISCREPANCY OF 3 × 3 × 3", 대한수학회논문집, 25(1), pp.19~25 (2010), 대한수학회
- M. Cheong, "The linear discrepancy of the product of three chains of the same size"
- M. Cheong, "Asymptotic results on linear discrepancy of the product of chains from its new bounds"
- M. Cheong, "The linear discrepancy of the product of three chains of size 2n", Far East J. Math. Sci. (FJMS), 30(2), pp.285~298 (2008)
- R. P. Dilworth, "A decomposition theorem for partially ordered sets", Ann. of Math, 51(1), pp.161~166 (1950)
- P. Fishburn, "Linear discrepancy and bandwidth", Order, 18(3), pp.237~245 (2001)
- S. P. Hong, "Linear discrepancy of the product of two chains", Order, 22(1), pp.63~72 (2005)
- M. T. Keller, "Degree bounds for linear discrepancy of interval orders and disconnected posets", Discrete Math, 310(15-16), pp.2198~2203 (2010)
- P. Tanenbaum, "Linear discrepancy and weak discrepancy of partially ordered sets", Order, 18(3), pp.201~225 (2001)