DIMACS TR: 2002-53

A Note on Linear Discrepancy and Bandwidth

Authors: Dieter Rautenbach


Fishburn, Tanenbaum and Trenk \cite{FTT01a} define the linear discrepancy ${\rm ld}(P)$ of a poset $P=(V,<_P)$ as the minimum integer $k\geq 0$ for which there exists a bijection $f:V\to\{ 1,2,\ldots,|V|\}$ such that $u<_P v$ implies $f(u) < f(v)$ and $u||_P v$ implies $|f(u)-f(v)|\leq k$. In \cite{FTT01b} 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 \cite{FTT01a} about the linear discrepancy and the bandwidth of cocomparability graphs.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-53.ps.gz

DIMACS Home Page