Originators: Ann Trenk, Peter Fishburn, Paul Tanenbaum (presented by David Howard - REGS 2010)
Definitions: Let P be a poset. Each x∈P will be assigned an integer label f(x) in an order-preserving manner: x<y implies f(x)<f(y). Several models of discrepancy measure the minimum, over all allowable such f, of the maximum difference between the labels of two incomparable elements.
The linear discrepancy, written ld(P), is the value of the parameter when the elements must have distinct labels (the minimum will occur when |P| consecutive labels are used, so we may assume that f is a linear extension. The weak discrepancy, written wd(P), is the value of the parameter when incomparable elements may receive the same labels (i.e., when f is a weak labeling). The t-discrepancy is the minimum value when f is a weak labeling and each label is used at most t times. the total discrepancy is the minimum of the total of the differences in labels of pairs of incomparable elements when the labels must be distinct.
Background: Discrepancy of posets was introduced by Tanenbaum, Trenk, and Fishburn [TTF]. The aim is to find a "fair" linear extension. For example, patients in an emergency room must be treated in a linear order, but the relation of ``more urgent'' is only a partial order P. Certainly x should be treated before y if x<y in P. For fairness, patients with incomparable urgencies should be treated not long apart. (Fairness in weak discrepancy might be appropriate in assigning salaries, for example, where repeated values can be used.) [FTT] showed that testing ld(P)≤k is NP-complete, even for interval orders, by relating it to the bandwidth of graphs. Also t-discrepancy is NP-complete for any fixed t, by reducing linear discrepancy using a "blowup" of the poset.
The difficulty of computing ld(P) motivates extremal questions and the study of values on special classes. For example, if r≥s, then ld(r+s)=⌈r/2⌉+s-1, where r+s is the disjoint union of an r-element chain and an s-element chain.
Result 1: [TTF] conjectured that if every element of P is incomparable to at most r other elements, then ld(P)≤(3r-1)/2. Equality holds when P=r+r. Rautenbach [R] observed that always r/2≤ld(P)≤2r-1; to prove the upper bound, observe that when x and y are incomparable elements farthest apart in a linear extension, there are at most 2r-2 elements between them, because no element betweeen them is comparable to both. However, the conjecture is false: In REGS 2010, Kevin Milans constructed posets with ld(P)=2(1-o(1))r.
Better bounds are known for special classes. The width w(P) is the maximum size of an antichain in P; note that w(P)≤r+1. The conjectured bound holds when P has width 2 (Choi & West [CW2]) and when the diagram of the poset is disconnected (Keller & Young [KY]). [FTT] proved that ldP=w(P)-1 when P is a semiorder. Keller & Young [KY] proved that ldP≤r when P is an interval order, with equality if and only if w(P)=r+1.
Question 2: What bounds can be placed on ld(P×Q) in terms of the posets P and Q?
Comments: [FTT] determined ld(P) when P is the n-dimensional subset lattice 2n. [HHKK] determined it for the product of two chains. [CW1] determined it for the product of three or four chains of the same size and presented upper bounds for general products of three chains.
Question 3: Can the t-discrepancy be computed in polynomial time when the input poset is restricted to the family of interval orders?
Comments: The reduction of linear discrepancy to t-discrepancy to prove NP-completeness of t-discrepancy creates copies of 2+2 in the poset to which the t-discrepancy algorithm will be applied. Hence it possibly there is a fast algorithm within the family of interval orders. Howard and Trenk [HT] obtained an O(n4)-time algorithm to compute t-discrepancy for semiorders.
The computational behavior of weak discrepancy is much different from that of linear discrepancy or t-discrepancy, now that labels may be used any number of times. Gimbel & Trenk [GT] showed that wd(P) can be computed in polynomial time, with a min-max relation for the answer. A forcing cycle is a cyclic arrangement C of a subset of the elements of P such that each successive element is above or incomparable to its predecessor; these are called up-steps and side-steps, respectively. Using the pigeonhole principle, wd(P)≥⌈u(C)/s(C)⌉ where u(C) and s(C) are the numbers of up-steps and side-steps in a forcing cycle C. In fact, wd(P) equals the maximum of this lower bound over all forcing cycles. For example, wd(r+s)=⌈(r+s)/2⌉-1.
The fractional weak discrepancy fwd(P) minimizes the maximum difference between labels on incomparable elements over all real labelings such that x<y implies f(x)≤f(y)-1. The pigeonhole argument yields fwd(P)≥u(C)/s(C) (without taking the ceiling); Shuchat, Shull, and Trenk [SST2] proved that fwd(P) always equals the largest such lower bound. In [SST1,SST3,SST4], they study the possible values of fwd(P) over all posets and over interval orders with no k+1.
The total weak discrepancy of a poset P, introduced in [SST5], is the minimum, over all (integer) weak labelings f of P, of ∑|f(x)-f(y)|, summed over all pairs of incomparable elements.
Problem 4: Find a fast algorithm to compute total weak discrepancy without using linear programming.
Problem 5: 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). Choi & West [CW1] characterized the posets having weak discrepancy at most k. Howard & Young [HY] determined the posets for which linear and weak discrepancy are equal.
Question 6 ([TTF]): For which posets P is it true that ld(P)≤w(P)?
Conjecture 7 (Trotter): If P has dimension at least 5, then ld(P)≥dim(P), with equality only when P contains the "standard example" Sn as a subposet.
Comments: (Definitions for dimension are found here.) We have observed that ld(P)≥w(P)-1, and it is well-known using Dilworth's Theorem that dim(P)≤w(P); hence always ld(P)≥dim(P)-1. There seem to be few minimal posets where equality holds. There is one 6-element poset with dimension 3 (and its dual) and one 13-element poset with dimension 4 (found by Brightwell); there may be a few others.
Finally, we consider the on-line linear discrepancy game. The Devil presents a poset one element at a time (giving the relations to earlier elements), perhaps constrained to keep the poset within a given family. The Computer must insert the new point into a linear extension of the elements so far (after the elements below it and before the elements above it), and the ordering of earlier elements cannot be changed later. Keller, Streib, and Trotter [KST] showed that when the Devil is restricted to posets with linear discrepancy at most k, the Computer can guarantee building a linear extension in which the positions of comparable elements differ by at most 3k-1, and the Devil can force the Computer to create an extension in which there is distance 3k-1 between two incomparable elements. This is not a big win for the Computer, since in every linear extension the positions of comparable elements differ by at most 3k. When the Devil is further restricted to present semiorders, the Computer can ensure difference at most 2k. Semiorders are the posets not containing 2+2 or 3+1; interval orders forbid only 2+2. The Devil's strategy to force 3k-1 makes use of the subposet 4+1.
Problem 8: What is the smallest allowable difference that enables the Computer to survive in the on-line linear discrepancy game when the Devil is restricted to posets not containing 2+2 or 4+1? What is the behavior of on-line versions of other discrepancy parameters, especially the total discrepancy?
Comments: When the full poset is visible, the total discrepancy is easy to compute: assign each element x the value d(x)-u(x), where the poset has d(x) elements below x and u(x) elements above it. Break ties arbitrarily. The resulting linear order minimizes the sum of the differences between positions of incomparable elements [HSST].
References:
[CW1] J. Choi and D.B. West, Forbidden subposets for fractional weak
discrepancy at most k, Europ. J. Combinatorics (2010).
[CW2] J. Choi and D.B. West, Linear discrepancy of chain products and posets
having width 2 (preprint).
[FTT] Fishburn, Peter C.; Tanenbaum, Paul J.; Trenk, Ann N.; Linear discrepancy
and bandwidth. Order 18 (2001), no. 3, 237--245.
[GT] Gimbel, John G.; Trenk, Ann N. On the weakness of an ordered set.
SIAM J. Discrete Math. 11 (1998), no. 4, 655--663
[HHKK] S. Hong, J. Hyun, H. Kim and S. Kim, Linear discrepancy of the
product of two chains, \emph{Order} 22 (2005), 63--72.
[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.
[HSST] D. Howard, R. Shull, N. Streib, and A.N. Trenk; The Total Linear
Discrepancy of an Ordered Set , submitted (2009)
[HT] D. Howard and A.N. Trenk; The t-Discrepancy of a Poset
submitted (2009).
[HY] D. Howard and S.J. Young; When linear and weak discrepancy are equal,
submitted (2009).
[KY] Keller, M.T.; Young, S.J.; Degree bounds for linear discrepancy of
interval orders and disconnected posets. Discrete Math. 310 (2010), nos. 15-16,
2198-2203.
[R] Rautenbach, Dieter; A note on linear discrepancy and bandwidth. J. Combin.
Math. Combin. Comput. 55 (2005), 199--208.
[SST1] Shuchat, Alan; Shull, Randy; Trenk, Ann N.; Range of the fractional
weak discrepancy function. Order 23 (2006), no. 1, 51--63.
[SST2] Shuchat, Alan; Shull, Randy; Trenk, Ann N.; The fractional weak
discrepancy of a partially ordered set. Discrete Appl. Math. 155 (2007),
no. 17, 2227--2235.
[SST3] Shuchat, Alan; Shull, Randy; Trenk, Ann N.; Fractional weak discrepancy
and interval orders. Discrete Appl. Math. 157 (2009), no. 8, 1873--1884.
[SST4] Shuchat, Alan; Shull, Randy; Trenk, Ann N.; Fractional weak discrepancy
of posets and certain forbidden configuarations, in The Mathematics of
Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, eds.
Steven J. Brams, William V. Gehrlein and Fred S. Roberts. Springer, New York,
291-301 (2009).
[SST5] Shuchat, Alan; Shull, Randy; Trenk, Ann N.; The total weak discrepancy
of a partially ordered set (preprint)
[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.