کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420569 683956 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fractional weak discrepancy and interval orders
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Fractional weak discrepancy and interval orders
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 8, 28 April 2009, Pages 1873–1884
نویسندگان
, , ,