Line directionality of orders (Q1311417): Difference between revisions
From MaRDI portal
Revision as of 12:18, 22 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Line directionality of orders |
scientific article |
Statements
Line directionality of orders (English)
0 references
13 January 1994
0 references
The authors extend a result given by I. Rival and J. Urrutia proving that any class of ordered sets, closed by the substitution of antichains and whose chromatic number of the diagram is unbounded, contains for any positive integer \(k\) an ordered set which is not \(k\)-directional. As a consequence, \(N\)-free orders, interval orders and two-dimensional orders may require an arbitrary number of directions. They also give a sufficient condition on \(\text{Succ}(P)\) for the line- directionality of \(P\). Using this condition, they establish the line- directionality of \(N\)-free orders and interval orders using at most \(|\text{Succ}(P)|\) directions. In the last section, they state the line-two-directionality of weak orders, tree-like orders and two-dimensional orders of height one.
0 references
motion planning
0 references
convex figure
0 references
separability
0 references
directional order
0 references
\(N\)-free orders
0 references
interval orders
0 references
two-dimensional orders
0 references
weak orders
0 references
tree-like orders
0 references
0 references