no. 15-16
Logique/Combinatoire
Isomorphie héréditaire et {−4}-hypomorphie pour les tournois

Présenté par : Jean-Yves Girard

Boudabbous, Youssef1
1 Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie
Comptes Rendus. Mathématique, Tome 347 (2009) no. 15-16, pp. 841-844.

Étant donné un tournoi T=(S,A), pour toute partie X de S, le sous-tournoi de T induit par X est noté T[X]. Nous montrons : Étant donnés deux tournois T et T′ de même ensemble de sommets S à n⩾10 éléments, si pour toute partie X à n−4 éléments de S, les sous-tournois T[X] et T′[X] sont isomorphes, alors pour toute partie Y de S, les sous-tournois T[Y] et T′[Y] sont isomorphes. Il en découle un corollaire analogue pour les parties à n−5 éléments.

Given a tournament T=(V,A), for every subset X of V the subtournament of T induced by X is denoted T[X]. We prove: Given two tournaments T and T′ on the same vertex set V with n⩾10 elements, if for each subset X with n−4 elements of V, the subtournaments T[X] and T′[X] are isomorphic, then for every subset Y of V, the subtournaments T[Y] and T′[Y] are isomorphic. An analogous corollary for the subsets with n−5 elements is deduced.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2009.06.002
Boudabbous, Youssef 1

1 Faculté des sciences de Sfax, BP 802, 3018 Sfax, Tunisie 
@article{CRMATH_2009__347_15-16_841_0,
     author = {Boudabbous, Youssef},
     title = {Isomorphie h\'er\'editaire et $ \{-4\}$-hypomorphie pour les tournois},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {841--844},
     publisher = {Elsevier},
     volume = {347},
     number = {15-16},
     year = {2009},
     doi = {10.1016/j.crma.2009.06.002},
     language = {fr},
     url = {http://archive.numdam.org/articles/10.1016/j.crma.2009.06.002/}
}
TY  - JOUR
AU  - Boudabbous, Youssef
TI  - Isomorphie héréditaire et $ \{-4\}$-hypomorphie pour les tournois
JO  - Comptes Rendus. Mathématique
PY  - 2009
SP  - 841
EP  - 844
VL  - 347
IS  - 15-16
PB  - Elsevier
UR  - http://archive.numdam.org/articles/10.1016/j.crma.2009.06.002/
DO  - 10.1016/j.crma.2009.06.002
LA  - fr
ID  - CRMATH_2009__347_15-16_841_0
ER  - 
%0 Journal Article
%A Boudabbous, Youssef
%T Isomorphie héréditaire et $ \{-4\}$-hypomorphie pour les tournois
%J Comptes Rendus. Mathématique
%D 2009
%P 841-844
%V 347
%N 15-16
%I Elsevier
%U http://archive.numdam.org/articles/10.1016/j.crma.2009.06.002/
%R 10.1016/j.crma.2009.06.002
%G fr
%F CRMATH_2009__347_15-16_841_0
Boudabbous, Youssef. Isomorphie héréditaire et $ \{-4\}$-hypomorphie pour les tournois. Comptes Rendus. Mathématique, Tome 347 (2009) no. 15-16, pp. 841-844. doi : 10.1016/j.crma.2009.06.002. http://archive.numdam.org/articles/10.1016/j.crma.2009.06.002/

[1] Bondy, J.A. A graph reconstructor's manual (Keendwell, O., ed.), Surveys in Combinatorics, London. Math. Soc. Lecture Note Ser., Cambridge Univ. Press, 1991, pp. 221-252

[2] Bondy, J.A.; Hemminger, R.L. Graph reconstruction, a survey, J. Graph Theory, Volume 1 (1977), pp. 227-268

[3] Bouaziz, M.; Boudabbous, Y. La demi-isomorphie et les tournois fortement connexes finis, C. R. Acad. Sci. Paris, Sér. I, Volume 335 (2002), pp. 105-110

[4] Bouchaala, H.; Boudabbous, Y. La {−k}-autodualité des sommes lexicographiques finies de tournois suivant un 3-cycle ou un tournoi critique, Ars Combin., Volume 81 (2006), pp. 33-64

[5] Boussaïri, A.; Ille, P.; Lopez, G.; Thomassé, S. The C3-structure of tournaments, Discrete Math., Volume 277 (2004), pp. 29-43

[6] R. Fraïssé, Abritement entre relations et spécialement entre chaînes, Symposi. Math. Instituto Nazionale di Alta Matematica 5, 1970, pp. 203–251

[7] Gallai, T. Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., Volume 18 (1967), pp. 25-66

[8] Lopez, G. Deux résultats concernant la détermination d'une relation par les types d'isomorphie de ses restrictions, C. R. Acad. Sci. Paris, Sér. A, Volume 274 (1972), pp. 1525-1528

[9] Lopez, G. Sur la détermination d'une relation par les types d'isomorphie de ses restrictions, C. R. Acad. Sci. Paris, Sér. A, Volume 275 (1972), pp. 951-953

[10] Lopez, G.; Rauzy, C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n−1), I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37

[11] Lopez, G.; Rauzy, C. Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and (n−1), II, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 157-168

[12] Pouzet, M. Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations, Math. Z., Volume 150 (1976), pp. 117-134

[13] Pouzet, M. Relations non reconstructibles par leurs restrictions, J. Combin. Theory B, Volume 1.26 (1979), pp. 22-34

[14] Reid, K.B.; Thomassen, C. Strongly self-complementary and hereditarily isomorphic tournaments, Monatsh. Math., Volume 81 (1976), pp. 291-304

Cité par Sources :