La 5-reconstructibilité et L’indécomposabilité Des Relations Binaires

A binary relation is ( ≤ k)-reconstructible, if it is determined up to isomorphism by its restriction to subsets of at most k elements. In [8], Lopez has shown that finite binary relations are ( ≤ 6)-reconstructible. To prove that the value 6 of its result, is optimal, Lopez [3], associates to all finite binary relation, an infinity of finite extensions, that are not ( ≤ 5)-reconstructible. These extensions are obtained from the relations given, by creation of intervals. Rosenberg has then asked if all finite binary relations, not ( ≤ 5)-reconstructible, were obtained by the same process. In this paper, we give an affirmative answer to the question, by characterizing finite binary relations that are not ( ≤ 5)-reconstructible. We deduce the 5-reconstructibility of finite indecomposable binary relations, of at least 9 elements. We extend then this last result to the binary multirelations.