Linear Discrepancy of Chain Products and Posets with Bounded Degree

The of a poset , denoted ld(), is the minimum, over all linear extensions , of the maximum distance in between two elements incomparable in . With denoting the maximum vertex degree in the incomparability graph of , we prove that when 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 2 − 1. For products of chains, we give alternative proofs of results obtained independently elsewhere.