A characterization of partially ordered sets with linear discrepancy equal to 2

DM Howard, MT Keller, SJ Young - Order, 2007 - Springer
DM Howard, MT Keller, SJ Young
Order, 2007Springer
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. Tanenbaum, Trenk, and Fishburn characterized the posets of linear
discrepancy 1 as the semiorders of width 2 and posed the problem of characterizing the
posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets
with linear discrepancy equal to 3 having the property that the deletion of any point results in …
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. Tanenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem of characterizing the posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets with linear discrepancy equal to 3 having the property that the deletion of any point results in a reduction in the linear discrepancy. Howard determined that there are infinitely many such posets of width 2. We complete the forbidden subposet characterization of posets with linear discrepancy equal to 2 by finding the minimal posets of width 3 with linear discrepancy equal to 3. We do so by showing that, with a small number of exceptions, they can all be derived from the list for width 2 by the removal of specific comparisons.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果