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
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
isomorphic cards
0 references
ordered sets
0 references
reconstruction problem
0 references
order reconstruction
0 references
2-cards
0 references
0 references