F3-Reconstruction and Bi-Founded 2-Structures.

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 (under some slight restriction). 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 characterisation 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 Boudabbous and Lopez (Discrete Math. 291, 19–40, 3): a bi-founded tournament is(≤ 3)-reconstructibleif and only if all its modules are selfdual. Furthermore we show that the restrictions on structuration above do not characterise (≤ 3)-reconstructibility on any of the following two classes, of which the class of bi-founded structures is the intersection, namely the class of founded structures (the class of structures the collection of strong modules of which is well-founded for inclusion), and the class of co-founded structures (the class of structures the collection of strong modules of which is well-founded for the reverse of inclusion, equivalently every strong module of which is robust, corresponding to [15]'s class of completely decomposable structures). Indeed we provide examples of founded, resp. co-founded, non (≤ 3)-reconstructible tournaments every module of which is selfdual. [ABSTRACT FROM AUTHOR]