A characterization of partially ordered sets with linear discrepancy equal to \(2\) (Q2464732): Difference between revisions

The linear discrepancy of a poset \((P,\leq )\) is the least natural number \(k\) such that there is a linear extension \(L\) of \(P\) such that if \(x\) and \(y\) are incomparable in \(P,\) then \(\left| h_{L}(x)-h_{L}(y)\right| \leq k\), where \(h_{L}(x)\) is the height of \(x\) in \(L.\) In this paper the authors characterize the posets of linear discrepancy \(2\) and 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. They 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.\)