HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Towards the reconstruction of poset

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 4:49:45 PM
Last modification on : Wednesday, April 6, 2022 - 8:54:04 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 7:59:13 PM


  • HAL Id : inria-00074897, version 1


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



Record views


Files downloads