Article ID Journal Published Year Pages File Type
420569 Discrete Applied Mathematics 2009 12 Pages PDF
Abstract

The fractional weak discrepancy  wdF(P)wdF(P) of a poset P=(V,≺)P=(V,≺) was introduced in [A. Shuchat, R. Shull, A. Trenk, The fractional weak discrepancy of a partially ordered set, Discrete Applied Mathematics 155 (2007) 2227–2235] as the minimum nonnegative kk for which there exists a function f:V→R satisfying (i) if a≺ba≺b then f(a)+1≤f(b)f(a)+1≤f(b) and (ii) if a∥ba∥b then |f(a)−f(b)|≤k|f(a)−f(b)|≤k. In this paper we generalize results in [A. Shuchat, R. Shull, A. Trenk, Range of the fractional weak discrepancy function, ORDER 23 (2006) 51–63; A. Shuchat, R. Shull, A. Trenk, Fractional weak discrepancy of posets and certain forbidden configurations, in: S.J. Brams, W.V. Gehrlein, F.S. Roberts (Eds.), The Mathematics of Preference, Choice, and Order: Essays in Honor of Peter C. Fishburn, Springer, New York, 2009, pp. 291–302] on the range of the wdFwdF function for semiorders (interval orders with no induced 3+1) to interval orders with no n+1, where n≥3n≥3. In particular, we prove that the range for such posets PP is the set of rationals that can be written as r/sr/s, where 0≤s−1≤r<(n−2)s0≤s−1≤r<(n−2)s. If wdF(P)=r/swdF(P)=r/s and PP has an optimal forcing cycle CC with up(C)=r and side(C)=s, then r≤(n−2)(s−1)r≤(n−2)(s−1). Moreover when s≥2s≥2, for each rr satisfying s−1≤r≤(n−2)(s−1)s−1≤r≤(n−2)(s−1) there is an interval order having such an optimal forcing cycle and containing non+1.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,