Originators: Ann Trenk, Peter Fishburn, Paul Tanenbaum (presented by Douglas West - REGS 2012)
Definitions: A linear extension $L$ of a poset $P$ is $t$-tight if the heights in $L$ of any two incomparable elements of $P$ differ by at most $t$. The linear discrepancy of $P$, written ld($P$), is the least $t$ such that some linear extension of $P$ is $t$-tight. In other words, we seek a "good" linear extension in the sense that no two incomparable elements are ranked far apart.
Background: This problem is an update of part of Problem 29 from REGS 2010; see that link for further motivation and questions on related parameters. Here we concentrate on a refined problem arising from the disproof of a conjecture stated there.
The incomparability graph of a poset $P$ is the graph whose vertices are the elements of $P$ and whose edges are the incomparable pairs of elements in $P$. Fishburn-Tanenbaum-Trenk [FTT] proved that always the linear discrepancy of $P$ equals the bandwidth of its incomparability graph, where the bandwidth $B(G)$ of a graph $G$ is the minimum, over all indexings of the vertices, of the maximum difference between the indices of adjacent vertices. Since every linear extension provides an indexing, ld$(P)\ge B(G)$ when $G$ is the incomparability graph of $P$, but there might be better indexings for $G$ not achievable as linear extensions. The proof that equality holds is nontrivial; Brightwell [unpublished] provided a more direct proof.
Let $r$ denote the maximum degree of the incomparability graph of $P$. Tanenbaum-Trenk-Fishburn [TTF] conjectured that always ld$(P)\le (3r-1)/2$. This would be sharp, since the linear discrepancy of the poset consistency of two disjoint $r$-chains equals $(3r-1)/2$.
However, the conjecture is false. In REGS 2010, Kevin Milans proved by probabilistic methods that the linear discrepancy of $P$ can be asymptotic to the trivial upper bound $2r-1$ (every linear extension is $(2r-1)$-tight). [CMW] presents a refined version of the argument, proving the existence of an $n$-element poset with $r\le n+2\sqrt n$ and linear discrepancy at least $2n-6\sqrt n\ln n$.
On the other hand, the conjecture holds in various cases. The width of a poset is the maximum number of pairwise incomparable elements. [CMW] contains a proof that the conjecture does hold for graphs of width 2. In contrast, the random posets having linear discrepancy close to $2r$ have large width. This suggests a refined question for fixed width.
Question 1: Fix an integer $w$, and consider posets with width $w$. Letting $r$ denote the maximum degree of the incomparability graph of such a poset $P$, what is the smallest constant $c_w$ such that always ld$(P)\le c_w r$. In particular, what is $c_3$?
Comment: We know that $c_2=3/2$ and that $c_w$ must tend to $2$ as $w\rightarrow\infty$. Meanwhile, for those interested in the parameter, we briefly mention three questions on linear discrepancy from the earlier problem page.
Question 2: What bounds can be placed on ld$(P\times Q)$ in terms of the posets $P$ and $Q$?
Problem 3: Characterize the posets having linear discrepancy 3.
Comments: [TTF] showed that the posets with linear discrepancy 1 are precisely the semiorders having width 2. Howard, Keller, & Young [HKY] gave a forbidden subposet characterization of the posets having linear discrepancy at most 2 (there are infinitely many minimal forbidden subposets).
Question 4 ([TTF]): For which posets $P$ is the linear discrepancy at most the width?
Comments: Linear discrepancy is always at least (width-1).
References:
[CMW] Choi, Jeong-Ok; Milans, Kevin G.; West, Douglas B.; Bounds on linear
discrepancy of posets (in preparation).
[FTT] Fishburn, Peter C.; Tanenbaum, Paul J.; Trenk, Ann N.; Linear discrepancy
and bandwidth. Order 18 (2001), no. 3, 237--245.
[HKY] Howard, David M.; Keller, Mitchel T.; Young, Stephen J.; A
characterization of partially ordered sets with linear discrepancy equal to 2.
Order 24 (2007), no. 3, 139--153.
[TTF] Tanenbaum, Paul J.; Trenk, Ann N.; Fishburn, Peter C.; Linear discrepancy
and weak discrepancy of partially ordered sets. Order 18 (2001), no. 3,
201--225.