Irreducible Width 2 Posets of Linear Discrepancy 3 |
| |
Authors: | David M Howard Gab-Byung Chae Minseok Cheong Sang-Mok Kim |
| |
Institution: | (1) School of Mathematics, Georgia Institute of Technology, Atlanta, 30332, GA, USA;(2) Department of Mathematics, Yonsei University, Wonju, 220-710, Korea;(3) Department of Mathematics, Sogang University, Seoul, 121-741, Korea;(4) Division of General Education - Mathematics, Kwangwoon University, Seoul, 139-701, Korea |
| |
Abstract: | The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h
L
(x) − h
L
(y)| ≤ k, where h
L
(x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed
the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point
reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width
2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique
linear extension that witnesses linear discrepancy 2.
The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290. |
| |
Keywords: | Partially ordered set Linear discrepancy Linear extension |
本文献已被 SpringerLink 等数据库收录! |
|