| Title:
|
On the jump number of lexicographic sums of ordered sets (English) |
| Author:
|
Jung, Hyung Chan |
| Author:
|
Lee, Jeh Gwon |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
53 |
| Issue:
|
2 |
| Year:
|
2003 |
| Pages:
|
343-349 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
ordered set |
| Keyword:
|
jump (setup) number |
| Keyword:
|
lexicographic sum |
| Keyword:
|
jump-critical |
| MSC:
|
06A07 |
| idZBL:
|
Zbl 1024.06001 |
| idMR:
|
MR1983456 |
| . |
| Date available:
|
2009-09-24T11:02:06Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127804 |
| . |
| Reference:
|
[1] M. Chein and M. Habib: The jump number of dags and posets: an introduction.Ann. Discrete Math. 9 (1980), 189–194. MR 0597371, 10.1016/S0167-5060(08)70060-8 |
| Reference:
|
[2] R. P. Dilworth: A decomposition theorem for partially ordered sets.Ann. Math. 51 (1950), 161–166. Zbl 0038.02003, MR 0032578, 10.2307/1969503 |
| Reference:
|
[3] M. H. ElZahar and I. Rival: Examples of jump-critical ordered sets.SIAM J. Alg. Disc. Math. 6 (1985), 713–720. MR 0801000, 10.1137/0606069 |
| Reference:
|
[4] M. H. ElZahar and J. H. Schmerl: On the size of jump-critical ordered sets.Order 1 (1984), 3–5. MR 0745584, 10.1007/BF00396268 |
| Reference:
|
[5] M. Habib: Comparability invariants.Ann. Discrete Math. 23 (1984), 371–386. Zbl 0561.05046, MR 0779861 |
| Reference:
|
[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. MR 0885495, 10.1016/0012-365X(87)90006-9 |
| Reference:
|
[7] H. C. Jung: On the products of some posets: jump number, greediness.Ars Combin. 40 (1995), 109–120. MR 1352773 |
| Reference:
|
[8] E. Szpilrajn: Sur l’extension de l’ordre partiel.Fund. Math. 16 (1930), 386–389. 10.4064/fm-16-1-386-389 |
| . |
