The minimal non-\((\leqslant k)\)-reconstructible relations (Q1772265)

Given a finite set \(E\), a relation with base \(E\) is a mapping \(R:E\times E \to \{+,-\}\) such that, for all \(x\in E\), \(R(x,x)=-\). A relation is therefore a loopless directed graph. The restriction of \(R\) to a subset \(X\) of \(E\) is \(R\) considered as a mapping from \(X\times X\) to \(\{+,-\}\). Given the relation \(R\), a \((\leq k)\)-reconstruction of \(R\) is any relation \(S\) with the same base \(E\) such that any restriction of \(S\) to a subset \(X\) of \(E\) with \(| X| \leq k\) is isomorphic to the restriction of \(R\) to \(X\); \(R\) is said to be \((\leq k)\)-reconstructible when each \((\leq k)\)-reconstruction of \(R\) is isomorphic to \(R\). \textit{R. Fraïssé} [Sympos. Math., Roma 5, Teoria Modelli 1969, 203--251 (1970; Zbl 0211.01802)] had asked whether there exists an integer \(k\geq1\) such that all relations with \(| E| >k\) are \((\leq k)\)-reconstructible. \textit{G. Lopez} [Z. Math. Logik Grundlagen Math. 24, 303--317 (1978; Zbl 0397.04002)] gave an affirmative answer to this question, showing that all relations are \((\leq 6)\)-reconstructible. In this paper the authors focus on the structure of relations which are not \((\leq k)\)-reconstructible, for \(1\leq k \leq 5\). By defining an order on such non-\((\leq k)\)-reconstructible relations they determine, for each \(3\leq k \leq 5\), the class of minimal non-\((\leq k)\)-reconstructible relations. The case \(k=3\) constitutes the main part of the paper while the case \(k=2\) remains an open question.