Towards the reconstruction of posets
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 theorem that interval orders are reconstructible, making use of a number of interesting other results, such as a poset version of the Kelly Lemma, obtained in this important contribution to this extensive area of research, which may also serve as an excellent introduction to any newcomer wishing to get a good start in the subject discussed here.
scientific article; zbMATH DE number 743933