The minimal non-\((\leqslant k)\)-reconstructible relations
type: Item
instance of: scholarly article
title: The minimal non-\((\leqslant k)\)-reconstructible relations
zbMATH Open document ID: 1059.05053
author: Youssef Boudabbous
author: Gérard Lopez
published in: Discrete Mathematics
publication date: 2005-04-18T00:00:00Z
review text: 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.
reviewed by: Josef Lauri
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 2157535
zbMATH Keywords: binary relations
zbMATH Keywords: reconstruction
zbMATH Keywords: indecomposability
zbMATH Keywords: duality
MaRDI profile type: Publication
full work available at URL: j.disc.2004.08.016
OpenAlex ID: W2006740807
cites work: La 5-reconstructibilité et l'indécomposabilité des relations binaires. (The 5-reconstructibility and indecomposability of binary relations)
cites work: La relation différence et l'anti‐isomorphie
cites work: Q3142964
cites work: Q5611770
cites work: Theory of relations. Transl. from the French by P. Clote
cites work: Q4000222
cites work: Transitiv orientierbare Graphen
cites work: Q3816105
cites work: Q4881848
cites work: L'Indeformabilite des Relations et Multirelations Binaires
cites work: RECONSTRUCTION OF BINARY RELATIONS FROM THEIR RESTRICTIONS OF CARDINALITY 2, 3, 4 and (n ‐ 1) I
DOI: 10.1016/J.DISC.2004.08.016
Recommended article: Procédé de construction des relations binaires non (≤ 3)-reconstructibles
Recommended article: La 5-reconstructibilité et l'indécomposabilité des relations binaires. (The 5-reconstructibility and indecomposability of binary relations)
Recommended article: RECONSTRUCTION OF BINARY RELATIONS FROM THEIR RESTRICTIONS OF CARDINALITY 2, 3, 4 and (n ‐ 1) II
Recommended article: RECONSTRUCTION OF BINARY RELATIONS FROM THEIR RESTRICTIONS OF CARDINALITY 2, 3, 4 and (n ‐ 1) I
Recommended article: \((\leq k)\)-reconstructible binary relations
Recommended article: Q4000222
Recommended article: La reconstruction au sens de Ulam de certaines multirelations binaires. (The reconstruction in Ulam's sense of some binary multirelations)
Recommended article: Q3778787
Recommended article: Q3807208
Recommended article: La dualité dans la demi-reconstruction des relations binaires finies
description: scientific article; zbMATH DE number 2157535