Towards the reconstruction of poset - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1992

Towards the reconstruction of poset

Résumé

The reconstruction conjecture for posets is the following : every finite poset P of more than three elements is uniquely determined - up to isomorphism - by its collection of (unlabelled) one-element-deleted subposets [ P - {x} : x V (P) ]. This conjecture belongs to the list of open problems in Order. We show that disconnected posets, posets with unique minimal (respectively, maximal) element and interval orders are reconstructible and that N-free orders are recognizable. We show that the following parameters are reconstructible : the number of minimal (respectively, maximal) elements, the level structure, the ideal-size sequence of the maximal elements, the ideal size (respectively, filter-size) sequence of any fixed level of the HASSE-diagram and the number of edges of the HASSE-diagram. This is considered to be a first step towards a proof of the reconstruction conjecture for posets.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-1660.pdf (993.25 Ko) Télécharger le fichier

Dates et versions

inria-00074897 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00074897 , version 1

Citer

Dieter Kratsch, Jean-Xavier Rampon. Towards the reconstruction of poset. [Research Report] RR-1660, INRIA. 1992. ⟨inria-00074897⟩
119 Consultations
98 Téléchargements

Partager

Gmail Facebook X LinkedIn More