The fractional weak discrepancy of a partially ordered set
In this paper we introduce the notion of the fractional weak discrepancy of a poset, building on previous work on weak discrepancy in [J.G. Gimbel and A.N. Trenk, On the weakness of an ordered set, SIAM J. Discrete Math. 11 (1998) 655663; P.J. Tanenbaum, A.N. Trenk, P.C. Fishburn, Linear discrepancy and weak discrepancy of partially ordered sets, ORDER 18 (2001) 201225; A.N. Trenk, On k-weak orders: recognition and a tolerance result, Discrete Math. 181 (1998) 223237]. The fractional weak discrepancy wdF(P) wd F ( P ) of a poset P=(V,?) P = ( V , ? ) is the minimum nonnegative k  for which there exists a function f:V?R f : V ? R satisfying (1) if a?b a ? b then f(a)+1?f(b) f ( a ) + 1 ? f ( b ) and (2) if a?b a ? b then |f(a)-f(b)|?k | f ( a ) - f ( b ) | ? k . We formulate the fractional weak discrepancy problem as a linear program and show how its solution can also be used to calculate the (integral) weak discrepancy. We interpret the dual linear program as a circulation problem in a related directed graph and use this to give a structural characterization of the fractional weak discrepancy of a poset.
fractional weak discrepancy weak discrepancy partially ordered sets