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

From MaRDI portal





scientific article; zbMATH DE number 6363130
Language Label Description Also known as
default for all languages
No label defined
    English
    Ordered sets that are reconstructible from two cards and the number of comparabilities.
    scientific article; zbMATH DE number 6363130

      Statements

      Ordered sets that are reconstructible from two cards and the number of comparabilities. (English)
      0 references
      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