×

Width two posets are reconstructible. (English) Zbl 0874.06002

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.

MSC:

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

References:

[1] Basso-Gerbelli, M.; Ille, P., La reconstruction des relations définies par interdits, C.R. Acad. Sci. Paris, 316, 1229-1234 (1993), (Série I) · Zbl 0783.04001
[2] Bondy, J. A.; Hemminger, R. L., Graph reconstruction — a survey, J. Graph Theory, 1, 227-268 (1977) · Zbl 0375.05040
[3] Bondy, J. A., A graph reconstructor’s manual, (Surveys in Combinatorics, Proc. 13th British Combinatorial Conf. (1991)), 221-252 · Zbl 0741.05052
[4] Das, S. K., On the structure of finite \(T_0 + T_5\) spaces, Canad. J. Math., XXV, 1148-1158 (1973) · Zbl 0265.54018
[5] Das, S. K., Some studies in the theory of finite topologies, (Ph.D. Thesis (1981), University of Calcutta)
[6] Ille, P., Recognition problem in reconstruction for decomposable relations, (Sauer, N. W.; etal., Finite and Infinite Combinatorics in Sets and Logic (1993), Kluwer Academic: Kluwer Academic Dordrecht), 189-198 · Zbl 0845.04002
[7] Kratsch, D.; Rampon, J.-X., A counterexample about poset reconstruction, Order, 11, 95-96 (1994) · Zbl 0806.06003
[8] Kratsch, D.; Rampon, J.-X., Towards the reconstruction of posets, Order, 11, 317-341 (1994) · Zbl 0819.06002
[9] Sands, B., Unsolved problems, Order, 1, 311-313 (1985)
[10] Stockmeyer, P. K., The falsity of the reconstruction conjecture for tournaments, J. Graph Theory, 1, 19-25 (1977) · Zbl 0355.05026
[11] Trotter, W. T., Combinatorics and Partially Ordered Sets: Dimension Theory (1992), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, MD · Zbl 0764.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.