Le seuil de reconstructibilité par le haut modulo la dualité des relations binaires finies
DOI:
https://doi.org/10.4067/S0716-09172003000300004Keywords:
Relation de difference, Relation binaire, Graphe, Hypomorphe, Hémimorphe, Reconstruction.Abstract
Etant donnée une relation binaire R, de base E, on définit sa duale RB par RB(x, y) = R(y, x). La relation R est dite auto-duale si elle est isomorphe à RB. Une relation binaire R0 est hémimorphe à R, si elle est isomorphe à R ou à RB. Une relation binaire à n éléments est (?k)-demi-reconstructible, si elle est déterminée à l’hémimorphie près, par la donnée à l’hémimorphie près de ses restrictions de cardinal (n ? k). L’étude faite en [8] entraine la (-d)- demi-reconstructibilité des relations binaires finies pour tout d ? 12. Nous étabissons la (?d)-demi-reconstructibilité des relations binaires finies pour tout d ? {11, 10, 9, 8, 7, 6}. Given a binary relation R of basis E, we define its dual RB by RB(x, y) = R(y, x). A relation R is self-dual if it is isomorphic to RB. A binary relation R0 is hemimorphic to R, if it is isomorphic to R or to RB. A relation R defined on n elements is (?k)- half - reconstructible if it is determined, up to hemimorphism, by its restrictions of cardinality (n ? k). From [8] follows the (?d)-halfreconstructibility of finite binary relations, for all d ? 12. We establish the (?d)-half-reconstructibility of finite binary relations, for all d ? {11, 10, 9, 8, 7, 6}.
References
[2] A. BOUSSAIRI : Thèse de doctorat de mathématiques. Soutenue à l’Université Claude Bernard, le 12 Juin, (1995).
[3] J. DAMMAK : Caractérisation des relations binaires finies d-demireconstructibiles. Proyecciones, Volume 22, N 1, (2003).
[4] J. DAMMAK : La dualité dans la demi-reconstruction des relations binaires finies, CRAS, Série I 327, pp. 861-864, (1998).
[5] J. DAMMAK : La (-5)-demi-reconstructibilité des relations binaires connexes finies. Proyecciones, Volume 22, N 3, (2003).
[6] R. FRAÏSSE : L’intervalle en théorie des relations, in orders, descriptions and roles, M. Pouzet et D. Richard ´ed. North-Holland, pp. 313- 342, (1984).
[7] C. GNANVO et P.ILLE : La reconstruction des tournois. C. R. Acad. Sci. Paris, t. 306, série I, pp. 577-580, (1988).
[8] J. G. HAGENDORF et G. LOPEZ : La demi-reconstructibilité des relations binaires d’au moins 13 éléments. C. R. Acad. Sci. Paris, série I, 317, pp. 7-12, (1993).
[9] G. LOPEZ : L’indéformabilité des relations et multirelations binaires. Zeitschrift. Math. Logik Grundlagen Math. 24, pp. 303-317, (1978).
[10] G. LOPEZ et C. RAUZY : Reconstruction of binary relations from their restrictions of cardinality 2,3,4 and (n-1), I. Zeitschr. f. Math. Logik und Grundlagen d. Math. Bd. 38, S. 27-37, (1992).
[11] G. LOPEZ et C. RAUZY : Reconstruction of binary relations from their restrictions of cardinality 2,3,4 and (n-1), II. Zeitschr. f. Math. Logik und Grundlagen d. Math. Bd 38, S. 157-168, (1992).
[12] M. POUZET : Application d’une propriété combinatoire des parties d’un ensemble aux groupes et aux relations. Math. Zeitschr. 150, pp. 117-134, (1976).
Published
How to Cite
Issue
Section
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.