Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 4:49:45 PM
Last modification on : Friday, February 12, 2021 - 3:33:12 AM
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