A New Characterization of Partial Orders of Dimension Two,
Abstract
It follows from a theorem of Szpilrajn that any partial order (X, <) is the intersection of a collection of linear orders on X. Dushnik and Miller define the dimension D(<) of the partial order to be the cardinality of the smallest such collection of linear orders, and characterize the partial orders of dimension at most 2. In this note we combine this characterization with a theorem of Ghouila-Houri and Gilmore and Hoffman to obtain a new characterization of the partial orders of dimension at most 2. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1970
- Accession Number
- AD0703862
Entities
People
- Fred S. Roberts
- Kirby A. Baker
- Peter C. Fishburn
Organizations
- RAND Corporation