Degree bounds for linear discrepancy of interval orders and disconnected posets

Let PP be a poset in which each point is incomparable to at most ΔΔ others. Tanenbaum, Trenk, and Fishburn asked in a 2001 paper if the linear discrepancy of such a poset is bounded above by ⌊(3Δ−1)/2⌋⌊(3Δ−1)/2⌋. This paper answers their question in the affirmative for two classes of posets. The first class is the interval orders, which are shown to have linear discrepancy at most ΔΔ, with equality precisely for interval orders containing an antichain of size Δ+1Δ+1. The stronger bound is tight even for interval orders of width 2. The second class of posets considered is the disconnected posets, which have linear discrepancy at most ⌊(3Δ−1)/2⌋⌊(3Δ−1)/2⌋. This paper also contains lemmas on the role of critical pairs in linear discrepancy as well as a theorem establishing that every poset contains a point whose removal decreases the linear discrepancy by at most 1.