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

Abstract : 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.
Document type :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101757
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:05:28 AM
Last modification on : Wednesday, November 20, 2019 - 2:50:25 AM

File

RR2003-47.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101757, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

13

Files downloads

15