Five-reconstructibility and indecomposability of binary relations

A binary relation is (less than or equal tok)-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 (less than or equal to6)-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 (less than or equal to5)-reconstructible. These extensions are obtained from the relations given, by creation of intervals. Rosenberg has then asked if all finite binary relations, not (less than or equal to5)-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 (less than or equal to5)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. (C) 2002 Elsevier Science Ltd. All rights reserved.