On the greedy dimension of a partial order

✍ Scribed by V. Bouchitte; M. Habib; R. Jegou

• Publisher: Springer Netherlands
• Year: 1985
• Tongue: English
• Weight: 279 KB
• Volume: 1
• Category: Article
• ISSN: 0167-8094
• DOI: 10.1007/bf00383597

✦ Synopsis

This paper introduces a new concept of dimension for partially ordered sets. Dushnik and Miller in 1941 introduced the concept of dimension of a partial order P, as the minimum cardinality of a realizer, (i.e., a set of linear extensions of P whose intersection is P). Every poser has a greedy realizer (i.e., a realizer consisting of greedy linear extensions). We begin the study of the notion of greedy dimension of a poser and its relationship with the usual dimension by proving that equality holds for a wide class of posets including N-free posets, two-dimensional posets and distributive lattices.