The fractional weak discrepancy of $(M, 2)$-free posets
Bull. Korean Math. Soc. 2019 Vol. 56, No. 1, 1-12
https://doi.org/10.4134/BKMS.b170657
Published online 2019 Jan 31
Jeong-Ok Choi
Gwangju Institute of Science and Technology
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.
Keywords : poset, interval order, $(M, 2)$-free poset, fractional weak dis\-crepancy
MSC numbers : Primary 06A07, 05C78
Full-Text :

   

Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang.co., Ltd