Geodesic
On the jump number of lexicographic sums of ordered sets
Czechoslovak Mathematical Journal, Tome 53 (2003) no. 2, pp. 343-349
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $Q$ be the lexicographic sum of finite ordered sets $Q_x$ over a finite ordered set $P$. For some $P$ we can give a formula for the jump number of $Q$ in terms of the jump numbers of $Q_x$ and $P$, that is, $s(Q)=s(P)+ \sum _{x\in P} s(Q_x)$, where $s(X)$ denotes the jump number of an ordered set $X$. We first show that $w(P)-1+\sum _{x\in P} s(Q_x)\le s(Q) \le s(P)+ \sum _{x\in P} s(Q_x)$, where $w(X)$ denotes the width of an ordered set $X$. Consequently, if $P$ is a Dilworth ordered set, that is, $s(P) = w(P)-1$, then the formula holds. We also show that it holds again if $P$ is bipartite. Finally, we prove that the lexicographic sum of certain jump-critical ordered sets is also jump-critical.
Let $Q$ be the lexicographic sum of finite ordered sets $Q_x$ over a finite ordered set $P$. For some $P$ we can give a formula for the jump number of $Q$ in terms of the jump numbers of $Q_x$ and $P$, that is, $s(Q)=s(P)+ \sum _{x\in P} s(Q_x)$, where $s(X)$ denotes the jump number of an ordered set $X$. We first show that $w(P)-1+\sum _{x\in P} s(Q_x)\le s(Q) \le s(P)+ \sum _{x\in P} s(Q_x)$, where $w(X)$ denotes the width of an ordered set $X$. Consequently, if $P$ is a Dilworth ordered set, that is, $s(P) = w(P)-1$, then the formula holds. We also show that it holds again if $P$ is bipartite. Finally, we prove that the lexicographic sum of certain jump-critical ordered sets is also jump-critical.
Classification : 06A07
Keywords: ordered set; jump (setup) number; lexicographic sum; jump-critical 
@article{CMJ_2003_53_2_a9,
     author = {Jung, Hyung Chan and Lee, Jeh Gwon},
     title = {On the jump number of lexicographic sums of ordered sets},
     journal = {Czechoslovak Mathematical Journal},
     pages = {343--349},
     year = {2003},
     volume = {53},
     number = {2},
     mrnumber = {1983456},
     zbl = {1024.06001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2003_53_2_a9/}
}
TY  - JOUR
AU  - Jung, Hyung Chan
AU  - Lee, Jeh Gwon
TI  - On the jump number of lexicographic sums of ordered sets
JO  - Czechoslovak Mathematical Journal
PY  - 2003
SP  - 343
EP  - 349
VL  - 53
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2003_53_2_a9/
LA  - en
ID  - CMJ_2003_53_2_a9
ER  - 
%0 Journal Article
%A Jung, Hyung Chan
%A Lee, Jeh Gwon
%T On the jump number of lexicographic sums of ordered sets
%J Czechoslovak Mathematical Journal
%D 2003
%P 343-349
%V 53
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2003_53_2_a9/
%G en
%F CMJ_2003_53_2_a9
Jung, Hyung Chan; Lee, Jeh Gwon. On the jump number of lexicographic sums of ordered sets. Czechoslovak Mathematical Journal, Tome 53 (2003) no. 2, pp. 343-349. http://geodesic.mathdoc.fr/item/CMJ_2003_53_2_a9/

[1] M.  Chein and M.  Habib: The jump number of dags and posets: an introduction. Ann. Discrete Math. 9 (1980), 189–194. | DOI | MR

[2] R. P.  Dilworth: A decomposition theorem for partially ordered sets. Ann. Math. 51 (1950), 161–166. | DOI | MR | Zbl

[3] M. H.  ElZahar and I.  Rival: Examples of jump-critical ordered sets. SIAM J.  Alg. Disc. Math. 6 (1985), 713–720. | DOI | MR

[4] M. H.  ElZahar and J. H.  Schmerl: On the size of jump-critical ordered sets. Order 1 (1984), 3–5. | DOI | MR

[5] M.  Habib: Comparability invariants. Ann. Discrete Math. 23 (1984), 371–386. | MR | Zbl

[6] M.  Habib and R. H.  Möhring: On some complexity properties of $N$-free posets with bounded decomposition diameter. Discrete Math. 63 (1987), 157–182. | DOI | MR

[7] H. C.  Jung: On the products of some posets: jump number, greediness. Ars Combin. 40 (1995), 109–120. | MR

[8] E.  Szpilrajn: Sur l’extension de l’ordre partiel. Fund. Math. 16 (1930), 386–389. | DOI