Towards the reconstruction of poset

Dieter Kratsch 1 Jean-Xavier Rampon 2
2 PAMPA - Models and Tools for Programming Distributed Parallel Architectures
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Abstract : 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.
Type de document :
[Research Report] RR-1660, INRIA. 1992
Liste complète des métadonnées
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:49:45
Dernière modification le : mercredi 16 mai 2018 - 11:23:04
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:59:13



  • HAL Id : inria-00074897, version 1


Dieter Kratsch, Jean-Xavier Rampon. Towards the reconstruction of poset. [Research Report] RR-1660, INRIA. 1992. 〈inria-00074897〉



Consultations de la notice


Téléchargements de fichiers