Accession Number : AD0703862

Title :   A New Characterization of Partial Orders of Dimension Two,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Roberts,Fred S. ; Baker,Kirby A. ; Fishburn,Peter C.

Report Date : MAR 1970

Pagination or Media Count : 4

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)

Descriptors :   (*COMBINATORIAL ANALYSIS, GRAPHICS), SET THEORY, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE