A Note on Linear Discrepancy and Bandwidth

Abstract

Fishburn, Tanenbaum, and Trenk define the linear discrepancy $\text{Id}(P)$ of a poset $P=(V,{<}_P)$ as the minimum integer $k\ge 0$ for which there exists a bijection $f:V\to \{1,2,\dots ,|V|\}$ such that $u{<}_{P}v$ implies $f(u)<f(v)$ and $u|{|}_{P}v$ implies $|f(u)–f(v)|\le k$. In their work, they prove that the linear discrepancy of a poset equals the bandwidth of its cocomparability graph. Here we provide partial solutions to some problems formulated in their study about the linear discrepancy and the bandwidth of cocomparability graphs.