DIKUL - logo
E-viri
Recenzirano Odprti dostop
  • Fractional weak discrepancy...
    Shuchat, Alan; Shull, Randy; Trenk, Ann N.

    Discrete Applied Mathematics, 04/2009, Letnik: 157, Številka: 8
    Journal Article

    The fractional weak discrepancy w d F ( P ) of a poset 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 k for which there exists a function f : V → R satisfying (i) if a ≺ b then f ( a ) + 1 ≤ f ( b ) and (ii) if a ∥ b then | 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 w d F function for semiorders (interval orders with no induced 3 + 1 ) to interval orders with no n + 1 , where n ≥ 3 . In particular, we prove that the range for such posets P is the set of rationals that can be written as r / s , where 0 ≤ s − 1 ≤ r < ( n − 2 ) s . If w d F ( P ) = r / s and P has an optimal forcing cycle C with up ( C ) = r and side ( C ) = s , then r ≤ ( n − 2 ) ( s − 1 ) . Moreover when s ≥ 2 , for each r satisfying s − 1 ≤ r ≤ ( n − 2 ) ( s − 1 ) there is an interval order having such an optimal forcing cycle and containing no n + 1 .