Ordered sets that are reconstructible from two cards and the number of comparabilities.

DOI10.1007/S11083-013-9306-4MaRDI QIDQ466874zbMATH OpenOpenAlexFDO

Publication date 31 October 2014

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-013-9306-4

2-cards isomorphic cards order reconstruction ordered sets reconstruction problem

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

Review text

In the reconstruction problem for ordered sets it is asked whether an order set is uniquely reconstructible from the collection of its cards (the deck). In detail, the question is whether, for two ordered sets \(P\) and \(P^*\), the existence of a bijective function (also called hypomorphism) \(*\colon P\to P^*\), so that for all \(x\in P\) the card \(P\setminus\{x\}\) is isomorphic to the card \(P^*\setminus\{x^*\}\), implies that \(P\) is isomorphic to \(P^*\). -- A two point deleted subset \(T\) of \(P\) is called a \(2\)-card. The author proves that in a non reconstructible ordered set \(P\) each of its \(2\)-cards must be isomorphic to another one, or, it must violate a specific condition that is related to, but weaker than, rigidity. The result is inspired by an argument by \textit{B. Bollobás} [J. Graph Theory 14, No. 1, 1-4 (1990; Zbl 0702.05061)], and provides a connection between positive reconstruction results and partial counterexamples that was, so far, nonexistent in order reconstruction literature.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Ordered sets that are reconstructible from two cards and the number of comparabilities.

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