Width two posets are reconstructible

DOI10.1016/0012-365X(95)00295-8MaRDI QIDQ1356683zbMATH OpenFDO

Authors Dieter Kratsch, Jean-Xavier Rampon

Publication date 5 November 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00295-8

deck of a poset reconstruction width 4 width two posets

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorics of partially ordered sets (06A07)

Review text

Given a poset \(P\) with vertex set \(V(P)\), the collection of subposets \(D(P)= \{V(P)-X\mid X\in V(P)\}\) with the order inherited from \(P\) is the deck of \(P\). For posets ``the reconstruction problem is to determine whether \(D(P)= D(Q)\) implies \(P=Q\) (up to isomorphism). The reconstruction problem can be viewed in more general settings but is probably most interesting for classes of finite posets. Thus counterexamples exist for Ulam's unrestricted version. The authors of this very useful addition look at the class of width two posets and in their constructive proof are able to take advantage of known results (classes where the reconstruction conjecture holds) to construct a proof which also uses earlier technical results by these same authors. It is observed that at width 4 there may exist counterexamples since ``weak counterexamples do exist and also that the methods used here are width 2 specific. Thus a width \(n\to \text{width } (n-1)\) reduction method may be unavailable and the search for some other ``general parameter by means of which a ``most general method for handling this problem may be constructed is still wide open. Nevertheless, the class of width 2 posets includes many new examples not handled in other ways.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Width two posets are reconstructible

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356683)