Linear Discrepancy of Chain Products and Posets with Bounded Degree

Abstract

The linear discrepancy of a poset P, denoted ld(P), is the minimum, over all linear extensions L, of the maximum distance in L between two elements incomparable in P. With r denoting the maximum vertex degree in the incomparability graph of P, we prove that ld(P) <= left perpendicular(3r -1)/2right perpendicular when P has width 2. Tanenbaum, Trenk, and Fishburn asked whether this upper bound holds for all posets. We give a negative answer using a randomized construction of bipartite posets whose linear discrepancy is asymptotic to the trivial upper bound 2r - 1. For products of chains, we give alternative proofs of results obtained independently elsewhere.