The reconstruction of multirelations, at least one component of which is a chain (Q1200002): Difference between revisions

A relation \(R\) of arity \(k\) on a finite set \(E\) is a function of \(E^ k\) into the set \(\{+,-\}\). A multirelation \(M\) on a set \(E\) is a sequence \(R_ 1,\dots,R_ h\) of relations (which are called components of \(M\)) on \(E\). For \(X\subseteq E\) the restriction \(M\upharpoonright X\) is the multirelation \(R_ 1\upharpoonright X,\dots,R_ h\upharpoonright X\). Two multirelations \(M\), \(M'\) on the same set \(E\) are said to be hypomorphic if for every \(x\in E\) the restriction \(M\upharpoonright(E\backslash\{x\})\) and \(M'\upharpoonright(E\backslash\{x\})\) are isomorphic. A multirelation \(M\) is called reconstructible if for every multirelation \(M'\), which is hypomorphic to \(M\), there holds: \(M\) and \(M'\) are isomorphic. The author proves (not in full details, which are given in his Thesis) that a multirelation, at least one component of which is a chain, is reconstructible. Here a chain \(C\) on a set \(E\) is a transitive tournament, that means a binary and reflexive relation \(C\) on \(E\) such that \(C(x,y)\neq C(y,x)\) for \(x\neq y\in E\), and \(C(x,y)=C(y,z)=+\Rightarrow C(x,z)=+\). The proof makes use of a result of \textit{M. Pouzet} [J. Comb. Theory, Ser. B 27, 231-236 (1979; Zbl 0349.05103)].