Degree bounds for linear discrepancy of interval orders and disconnected posets

Let P be a poset in which each point is incomparable to at most Delta others. Tanenbaum, Trenk, and Fishburn asked in a 2001 paper if the linear discrepancy of such a poset is bounded above by left perpendicular (3 Delta - 1)/2 right perpendicular. 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 Delta, with equality precisely for interval orders containing an antichain of size Delta + 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 left perpendicular (3 Delta - 1)/2 right perpendicular. 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. (C) 2010 Elsevier B.V. All rights reserved.