F3-Reconstruction and Bi-Founded 2-Structures
Résumé
Two binary relational structures of a same signature are (≤ k)-hypomorphic if they have the
same vertex set and their restrictions to each set of at most k vertices are isomorphic. A binary relational structure is (≤ k)-reconstructible if it is isomorphic with each structure it is (≤ k)-hypomorphic with. We establish an inductive characterisation of pairs of (≤ 3)-hypomorphic binary relational structures. We infer a characterisation of (≤ 3)-reconstructibility for bi-founded binary relational structures. A binary relational structure is bi-founded if it has no infinite set of pairwise comparable strong modules. On the one hand, we describe operations generating exactly the class of (≤ 3)-reconstructible bi-founded binary relational
structures from singleton ones. On the other hand, this caracterisation can be formulated in terms of restrictions on the structuration of the tree of robust modules of the structure. This allows in particular the extension of [YB-GL 05] : a bi-founded tournament is (≤ 3)-reconstructible if and only if all its modules are selfdual. Furthermore we show that the restrictions on structuration above do not characterise (≤ 3)-reconstructibility on the natural next classes generalising bi-founded structures, namely the class of founded
structures (the class of structures of which the collection of strong modules is well-founded for inclusion), and the class of co-founded structures (the class of structures of which the collection of strong modules is well-founded for the reverse of inclusion, equivalently of which every strong module is robust, corresponding to [HR 94]’s class of completely decomposable structures). Indeed we provide examples of founded, resp. co-founded, non (≤ 3)-reconstructible tournaments of which every module is selfdual.