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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Ordered sets that are reconstructible from two cards and the number of comparabilities.
scientific article

    Statements

    Ordered sets that are reconstructible from two cards and the number of comparabilities. (English)
    0 references
    0 references
    31 October 2014
    0 references
    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.
    0 references
    0 references
    isomorphic cards
    0 references
    ordered sets
    0 references
    reconstruction problem
    0 references
    order reconstruction
    0 references
    2-cards
    0 references

    Identifiers