Orders with level diagrams (Q2640624): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Ivan Rival / rank | |||
Property / author | |||
Property / author: Ivan Rival / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Greedy linear extensions to minimize jumps / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Setup optimization problems with matroid structure / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity of diagrams / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3222890 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Antichain cutsets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3773302 / rank | |||
Normal rank |
Revision as of 14:34, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Orders with level diagrams |
scientific article |
Statements
Orders with level diagrams (English)
0 references
1991
0 references
For elements a and b in an ordered set P, a is called an upper cover of b and b a lower cover of a if \(a>b\) and, for each x in P, \(a>x\geq b\) implies \(x=b\). The ordered set P is called upper levelled (lower levelled) if there is a diagram of P such that all upper covers (lower covers) are on a horizontal level. It is proved that the following statements are equivalent: (a) P is upper levelled. (b) P is lower levelled. (c) P contains no alternating cover cycle, i.e. a subset \(\{x_ 1,a_ 1,a_ 2,...,a_ n,c_ 1,c_ 2,...,c_ n\},\) \(n\geq 2\), where \(c_ i\) covers \(a_ i\), for \(i\leq n\), \(c_{i+1}>a_ i\), for \(i\leq n-1\), \(c_ 1>x>a_ n\) are the only comparabilities. Finally efficient algorithms are described, both to check whether an ordered set has a given level-type property and, if it does, to draw a corresponding diagram.
0 references
levelled order
0 references
drawing of a diagram
0 references
ordered set
0 references
upper cover
0 references
lower cover
0 references
upper levelled
0 references
lower levelled
0 references
alternating cover cycle
0 references
efficient algorithms
0 references