The minimal non-(≤ k)-reconstructible relations

Given a finite set E, a relation with base E is a mapping R: E x E -> {+, -} such that for all x is an element of E, R(x, x) The restriction of R to a subset X of E is R considered as a mapping from X x X into {+, -}. Given an integer k >= 1 and a relation R with base E, we call (<= k)-reconstruction of R every relation with the same base, any restriction of which to a subset X of E with up to k elements is isomorphic to the restriction of R to X. The relation R is (<= k)-reconstructible when each k) -reconstruction of R is isomorphic to R. In this work, the structure of the non-(<= k)-reconstructible relations is studied for all k >= 1. This study leads to an introduction of the minimal non-(<= k)-reconstructible relations and to characterization of the class of such relations for all k not equivalent to 2. This class includes in particular the class of the indecomposable non-(<= k)-reconstructible relations. (c) 2004 Elsevier B.V. All rights reserved.