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

✍ Scribed by Youssef Boudabbous

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 151 KB
• Volume: 23
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.2001.0562

✦ Synopsis

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.