The reconstruction of multirelations, at least one component of which is a chain
type: Item
instance of: scholarly article
title: The reconstruction of multirelations, at least one component of which is a chain
zbMATH Open document ID: 0772.04003
DOI: 10.1016/0097-3165(92)90024-O
author: P. Ille
published in: Journal of Combinatorial Theory. Series A
publication date: 1993-01-17T00:00:00Z
review text: 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)].
reviewed by: Egbert Harzheim
Mathematics Subject Classification ID: 03E20
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 96579
zbMATH Keywords: reconstruction
zbMATH Keywords: multirelation
zbMATH Keywords: transitive tournament
MaRDI profile type: Publication
cites work: Graph reconstruction—a survey
cites work: Q3816105
cites work: Rélations non reconstructibles par leurs restrictions
cites work: Note sur le problème de Ulam
cites work: The falsity of the reconstruction conjecture for tournaments
cites work: Q3259049
description: scientific article; zbMATH DE number 96579