Towards the reconstruction of posets
type: Item
instance of: scholarly article
title: Towards the reconstruction of posets
zbMATH Open document ID: 0819.06002
DOI: 10.1007/BF01108765
author: Dieter Kratsch
author: Jean-Xavier Rampon
published in: Order
publication date: 1995-08-24T00:00:00Z
review text: The reconstruction conjecture for posets can be expressed as follows: ``Every finite poset \(P\) of more than three elements is uniquely determined -- up to isomorphism -- by its collection of (unlabeled) one- element deleted subposets \(\langle P-\{ x\}\): \(x\in V(P) \rangle\), where \(V(P)\) is the set of vertices of \(P\)''. If instead of order-isomorphisms the class of `isomorphisms' is expanded to all bijections, then since the number of one-element deleted subposets determines the number of elements of \(P\) and since any two posets of the same size are `isomorphic' in this sense the reconstruction conjecture is trivial if we take it in this sense. Similarly, the poset reconstruction conjecture for finite posets can be rephrased as: ``the class of order-isomorphisms on finite posets is sufficient to resolve the reconstruction conjecture for this class of posets (as long as the posets contain more than three elements)''. The three point counterexample as well as hints in the proofs of theorems suggest that one class of isomorphisms for which the poset reconstruction conjecture may be proven is the class of `incomparability preserving isomorphisms' taking note that an order-preserving isomorphism (not an order-preserving bijection) also preserves incomparability, whence this class of mappings is somewhat larger and makes the three point counterexample vanish. The paper discussed here is much more than `a first step towards the proof of the reconstruction conjecture for posets'. Indeed, it provides a very substantial supply of classes of posets in which the poset reconstruction conjecture holds and (universal) poset parameters which are reconstructible as well. The notions of `recognizability' along with the orthogonal one of `weakly reconstructible' whose intersection provides `reconstructibility' in analogy with the classical graph reconstruction definitions are made excellent use of in the strategy of proofs of some quite formidable results, including the the…
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 743933
zbMATH Keywords: reconstructible parameter
zbMATH Keywords: recognizable class of posets
zbMATH Keywords: Kelly lemma
zbMATH Keywords: reconstruction
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Q3975132
cites work: Graph reconstruction—a survey
cites work: Q4918389
cites work: Complement reducible graphs
cites work: Q3328583
cites work: Q5572939
cites work: Q5578819
cites work: A congruence theorem for trees
cites work: On the complexity of graph reconstruction
cites work: A counterexample about poset reconstruction
cites work: The falsity of the reconstruction conjecture for tournaments
cites work: Q4004146
cites work: Reconstructibility and perfect graphs
full work available at URL: https://doi.org/10.1007/bf01108765
OpenAlex ID: W2082138862
Recommended article: A counterexample about poset reconstruction
Recommended article: Reconstruction of posets with the same comparability graph
Recommended article: Q4816064
Recommended article: Realization of Posets
Recommended article: Constructions of ranked posets
Recommended article: Q3992246
Recommended article: Q4397554
Recommended article: Posets, homomorphisms and homogeneity
Recommended article: Residuation in finite posets
Recommended article: Q4925584
description: scientific article; zbMATH DE number 743933