The interval inclusion number of a partially ordered set
| Autor: | Douglas B. West, Tom Madej |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Discrete mathematics
010102 general mathematics 0102 computer and information sciences Composition (combinatorics) 01 natural sciences Upper and lower bounds Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Interval (graph theory) 0101 mathematics Partially ordered set Maximal element Mathematics |
| Zdroj: | Discrete Mathematics. (2-3):259-277 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/0012-365X(91)90014-S |
| Popis: | A containment representation for a poset P is a map ƒ such that x y in P if and only if ƒ(x) ⊂ ƒ(y) . We introduce the interval inclusion number (or interval number ) i ( P ) as the smallest t such that P has a containment representation f in which each f ( x ) is the union of at most t intervals. Trivially, i ( P )=1 if and only if dim( P )⩽2. Posets with i ( P )=2 include the standard n -dimensional poset and all interval orders; i.e. posets of arbitrarily high dimension. In general we have the upper bound i(P) ⩽ ⌈; dim (P) 2 ⌉ , with equality holding for the Boolean algebras. For lexicographic composition, i ( P ) = k and dim( Q ) = 2 k + 1 imply i ( P [ Q ]) = k + 1. This result and i ( B 2 k ) = k imply that testing i ( P ) ⩽ k for any fixed k ⩾ 2 is NP-complete. Concerning removal theorems, we prove that i ( P − x ) ⩾ i ( P ) − 1 when x is a maximal or minimal element of P , and in general i(P − x) ⩾ i(P) 2 . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|