Interval orders based on arbitrary ordered sets

DOI10.1016/0012-365X(94)00288-TMaRDI QIDQ1898345zbMATH OpenFDO

Authors Jutta Mitas

Publication date 13 May 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00288-T

zbMATH Keywords

concept latticeDedekind- MacNeille completionforbidden suborderinterval dimensioninterval orders over arbitrary classes of ordered setsorder dimension

Mathematics Subject Classification ID

Partial orders, general (06A06)

Review text

Interval orders are defined as ordered sets having interval representations on linearly ordered sets. In this paper the author investigates a more general situation in that the underlying sets may be members of any class of ordered sets. If \(C\) is a class of ordered sets then \(I(C)\) denotes the class of ordered sets having an interval representation in \(C\). The author proves, for example, that if \(C\) is a class of ordered sets which is closed under Dedekind-MacNeille completion and retracts, then \(P \in I(C)\) iff \(B(P,P,<) \in C\), where \(B(P,P,<)\) is the concept lattice of \(P\). If \(Q\) is an ordered set, denote by \(C_Q\) the class of ordered sets for which \(Q\) is a forbidden suborder. Finite ordered sets \(Q\) for which \(C_Q\) is closed under Dedekind-MacNeille completion are described. The author also shows connections between order dimension and interval dimension for general classes of ordered sets.

Recommendations

• Interval orders and dimension
• Interval orders and reverse mathematics
• Interval orders based on weak orders
• Interval dimension is a comparability invariant
• Basic interval orders

Cites work

• An obvious proof of Fishburn's interval order theorem
• Betweenness, orders and interval graphs
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3771669 (Why is no real title available?)
• scientific article; zbMATH DE number 6157238 (Why is no real title available?)
• Interval orders based on weak orders
• On realizable biorders and the biorder dimension of a relation
• On the Ferrers dimension of a digraph
• On trees and tree dimension of ordered sets
• Optimal Linear Extensions by Interchanging Chains
• Removing critical pairs
• Separable subsets of a finite lattice
• Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Menge

Cited in

(21)

• Scott-suppes representability of semiorders: Internal conditions
• Representing interval orders by weighted bases: some complexity results
• Transversals for ordinal intervals
• Counting interval orders
• Preference structures and their numerical representations
• 3-interval irreducible partially ordered sets
• Generalized dimension of an ordered set and its MacNeille completion
• Partial orders and their convex subsets
• Generalizations of semiorders: A review note
• Basic interval orders
• Some remarks on a problem of J. D. Monk
• Numerical representability of semiorders
• A characterization of PQI interval orders.
• Interval orders and dimension
• Dimension of restricted classes of interval orders
• Ordered sets with interval representation and (m,n)-Ferrers relation
• A generalization of interval orders
• On generalized interval orders
• Interval Space Representation of interval Structures
• On covering numbers, Young diagrams, and the local dimension of posets
• Numerical representations of interval orders

This page was built for publication: Interval orders based on arbitrary ordered sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1898345)