𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Poset Dimension Algorithm

✍ Scribed by Javier Yáñez; Javier Montero

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
154 KB
Volume
30
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

This article presents an algorithm which computes the dimension of an arbitrary Ž . finite poset partial order set . This algorithm is based on the chromatic number of a graph instead of the classical approach based on the chromatic number of some hypergraph. The relation between both approaches is analyzed. With this algorithm, the dimension of many modest size posets can be computed. Otherwise, an upper bound for the poset dimension is obtained. Some computational results are included.

📜 SIMILAR VOLUMES

Planarity and Edge Poset Dimension
Planarity and Edge Poset Dimension
✍ Hubert de Fraysseix; Patrice Ossona de Mendez 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 291 KB
A note on the dimension of a poset
A note on the dimension of a poset
✍ E. C. Milner; M. Pouzet 📂 Article 📅 1990 🏛 Springer Netherlands 🌐 English ⚖ 93 KB

It is shown that the dimension of a poset is the smallest cardinal number I such that there is an embedding of the poset into a strict product of I, linear orders.

The dimension of planar posets
The dimension of planar posets
✍ William T Trotter Jr.; John I Moore Jr. 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 845 KB
The dimension of the cartesian product o
The dimension of the cartesian product of posets
✍ Chiang Lin 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 775 KB

Lin, C., The dimension of the Cartesian product of posets, Discrete Mathematics 88 (1991) 79-92. We give a characterization of nonforced pairs in the Cartesian product of two posets, and apply this to determine the dimension of P X Q, where P, Q are some subposets of 2" and 2" respectively. One of