A new bound on the 2-dimension of partially ordered sets. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2003

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

(1)
1

Résumé

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.
Fichier principal
Vignette du fichier
RR2003-47.pdf (211.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101757 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101757 , version 1

Citer

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⟩
14 Consultations
20 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More