A new bound on the 2-dimension of partially ordered sets.

Eric Thierry (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

This paper provides a new upper bound on the 2-dimension of partially ordered sets. The 2-dimension of an ordered set P is the smallest cardinality of a set S such that there exists an order-embedding of P into te boolean lattice 2S (all the subsets of S ordered by inclusion). The proof is non-constructive and uses a probabilistic argument. We link the resulrs and trhe proof with two known theorems of the theory of ordered sets.

Ce papier présente une nouvelle borne supérieure sur la 2-dimension des ensembles ordonnées. La 2-dimension d'un ordre P est le cardinal minium d'un ensemble S tel qu'il existe un plongement d'ordre de P dans le treillis booléen S (composée de tous les sous-ensembles de S ordonnées par l'inclusion). La preuve est non-constructive et utilise un argument probabiliste. Nous rapprochons ce résultat et sa preuve de deux théorèmes connus en théorie des ensembles ordonnés.

Mots clés: 2-dimension; Boolean Lattice; Order-embedding; Partially Ordered Set

Mots clés: Ensemble ordonnées; Plongements d'ordre; Treillis booléen

Domaines: Informatique [cs]

Eric Thierry. A new bound on the 2-dimension of partially ordered sets.. [Research Report] LIP RR-2003-47, Laboratoire de l'informatique du parallélisme. 2003, 2+5p. ⟨hal-02101757⟩