The fractional weak discrepancy of $(M, 2)$-free posets
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (12)
- J.-O. Choi, "Forbidden subposets for fractional weak discrepancy at most k", European J. Combin, 31(8), pp.1957~1963 (2010)
- P. C. Fishburn, "Interval orders and interval graphs" (1985), Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Ltd.
- J. G. Gimbel, "On the weakness of an ordered set", SIAM J. Discrete Math, 11(4), pp.655~663 (1998)
- D. M. Howard, "When linear and weak discrepancy are equal", Discrete Math, 311(4), pp.252~257 (2011)
- A. Shuchat, "Range of the fractional weak discrepancy func-tion", Order, 23(1), pp.51~63 (2006)
- A. Shuchat, "The fractional weak discrepancy of a partially ordered set", Discrete Appl. Math, 155(17), pp.2227~2235 (2007)
- A. Shuchat, "Fractional weak discrepancy and interval orders", Discrete Appl. Math, 157(8), pp.1873~1884 (2009)
- A. Shuchat, "The mathematics of preference, choice and order", pp.291~301 (2009), Springer
- A. Shuchat, "Fractional weak discrepancy and split semiorders", Discrete Appl. Math, 159(7), pp.647~660 (2011)
- A. Shuchat, "The total weak discrepancy of a partially ordered set", Ars Math. Contemp, 4(1), pp.95~109 (2011)
- P. J. Tanenbaum, "Linear discrepancy and weak dis-crepancy of partially ordered sets", Order, 18(3), pp.201~225 (2001)
- A. N. Trenk, "On k-weak orders: recognition and a tolerance result", Discrete Math, 181(1-3), pp.223~237 (1998)