For a finite poset $P = (X, \preceq)$ the {\it fractional weak discrepancy} of $P$, denoted $wd_F(P)$, is the minimum value $t$ for which there is a function $f: X \longrightarrow \mathbb{R}$ ...satisfying (1) $f(x) + 1 \le f(y)$ whenever $x \prec y$ and (2) $|f(x) - f(y)| \le t$ whenever $x \| y$. In this paper, we determine the range of the fractional weak discrepancy of $(M, 2)$-free posets for $M \ge 5$, which is a problem asked in \cite{sst3}. More precisely, we showed that (1) the range of the fractional weak discrepancy of $(M, 2)$-free interval orders is $W = \{ \frac{r}{r+1} \colon r \in \mathbb{N} \cup \{ 0 \} \} \cup \{ t \in \mathbb{Q} \colon 1 \le t < M - 3 \}$ and (2) the range of the fractional weak discrepancy of $(M, 2)$-free non-interval orders is $\{ t \in \mathbb{Q} \colon 1 \le t < M - 3 \}$. The result is a generalization of a well-known result for semiorders and the main result for split semiorders of \cite{sst3} since the family of semiorders is the family of $(4, 2)$-free posets. KCI Citation Count: 1
The
fractional weak discrepancy
w
d
F
(
P
)
of a poset
P
=
(
V
,
≺
)
was introduced in Shuchat et al. (2007)
6 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 Shuchat et al. (2006, 2009)
5,7 on the range of
w
d
F
for semiorders to the larger class of split semiorders. In particular, we prove that for such posets the range is the set of rationals that can be represented as
r
/
s
for which
0
≤
s
−
1
≤
r
<
2
s
.
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
.
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) 655–663; P.J. Tanenbaum, A.N. Trenk, P.C. Fishburn, Linear discrepancy and weak discrepancy of partially ordered sets, ORDER 18 (2001) 201–225; A.N. Trenk, On
k-weak orders: recognition and a tolerance result, Discrete Math. 181 (1998) 223–237. The
fractional weak discrepancy
wd
F
(
P
)
of a poset
P
=
(
V
,
≺
)
is the minimum nonnegative
k for which there exists a function
f
:
V
→
R
satisfying (1) if
a
≺
b
then
f
(
a
)
+
1
⩽
f
(
b
)
and (2) if
a
∥
b
then
|
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.
PDF
